Applying sorting criteria generically in a multiply ordered linked list

closed account (D80DSL3A)
kbw posted an interesting idea for an ordered linked list (called a Plex) in which each node has an array of next*'s to facilitate ordering the list in numerous ways simultaneously:
http://www.cplusplus.com/forum/general/55448/#msg298488

I have this working on a template basis, but one aspect of my solution seems less than ideal.
In order to write a template function for plex::insert() I must rank objects in the list without referencing specific member names.

Here is my simple solution for a multiply ordered list of person objects:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// person structure and supporting functions ( Less() and operator<<() )
struct person
{
    string name;
    int age;
    string job;
    person(const char* Name, int Age, const char* Job): name(Name), age(Age), job(Job){}
};

// for use by plex<T>::print()
ostream& operator<<(ostream& os, const person& X)
{
    os << X.name << "  " << X.age << "  " << X.job;
    return os;
}

// for use by plex<T>::insert()
bool Less( const person& A, const person& B, int idx )
{
    switch(idx)
    {
        case 0:
            return A.name < B.name;
        case 1:
            return A.age < B.age;
        case 2:
            return A.job < B.job;
    }
    return true;
}

This Less() allows members to be compared by index # rather than by name, which works well in my plex::insert():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<class T>
void plex<T>::insert(const T& X)
{
    node* newNode = new node(X, numPaths);// numPaths = # of next*'s for each node

    for(int i=0; i<numPaths; ++i)// for each path through the list
    {
        if( Less( X, head[i]->x, i ) )// insert as new head of path i
        {
            newNode->next[i] = head[i];
            head[i] = newNode;
        }
        else// insert along path i
        {
            node* iter = head[i];
            while( iter->next[i] )
            {
                if( Less( iter->next[i]->x, X, i ) )
                    iter = iter->next[i];
                else
                    break;
            }
            // insert newNode between iter and iter->next[i]
            newNode->next[i] = iter->next[i];
            iter->next[i] = newNode;
        }
    }

}// end of insert() 

However, kbws description of this structure, specifically:
When an item is inserted, it's inserted into each link using that link's sort criteria.
suggests to me that the sort criterion is somehow managed within the node structure instead of by a helper function for the objects being sorted.

Does anyone see how this can be done?

Here's my plex structure in case anyone wishes to tinker with it:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
template<class T>
struct plex
{
    struct node
    {
        T x;// the data
        node** next;// for array of node*'s
        node(const T& X, int N): x(X), next(new node*[N]) {}
        ~node(){ delete [] next; cout << "node deleted\n"; }
    };

    node** head;// for array of head*'s
    int numPaths;// = # of head nodes and # of next node*'s for each node
    plex(const T& X, int Npaths);
    ~plex();
    void insert(const T& X);
    void print(int idx);// idx = path number through list
};

template<class T>
plex<T>::plex(const T& X, int Npaths): head( new node*[Npaths] ), numPaths( Npaths )
{
    node* firstNode = new node(X, numPaths);
    for(int i=0; i<numPaths; ++i)
    {
        head[i] = firstNode;// all paths initially start at firstNode
        firstNode->next[i] = NULL;// and end there too
    }
}

template<class T>
plex<T>::~plex()
{
    // choose one path through the list
    while( head[0] )
    {
        node* temp = head[0];
        head[0] = head[0]->next[0];
        delete temp;
    }
    delete [] head;
    cout << "plex deleted\n";
}

template<class T>
void plex<T>::insert(const T& X)
{
    node* newNode = new node(X, numPaths);

    for(int i=0; i<numPaths; ++i)// for each path through the list
    {
        if( Less( X, head[i]->x, i ) )// insert as new head of path i
        {
            newNode->next[i] = head[i];
            head[i] = newNode;
        }
        else// insert along path i
        {
            node* iter = head[i];
            while( iter->next[i] )
            {
                if( Less( iter->next[i]->x, X, i ) )
                    iter = iter->next[i];
                else
                    break;
            }
            // insert newNode between iter and iter->next[i]
            newNode->next[i] = iter->next[i];
            iter->next[i] = newNode;
        }
    }

}// end of insert()

template<class T>
void plex<T>::print(int idx)// idx = index to path through the list
{
    node* iter = head[idx];
    while( iter )
    {
        cout << iter->x << endl;
        iter = iter->next[idx];
    }
}// end of print() 

Example implementation using the person structure (working):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
using namespace std;

// person structure definition here
// plex structure definition here

int main()
{
    plex<person> Lp( person("Derek", 48, "Electrician"), 3 );
    Lp.insert( person("Ann", 52, "Baker") );
    Lp.insert( person("Frank", 22, "Driver") );

    // show all paths through the list of persons
    for(int i=0; i<Lp.numPaths; ++i)
    {
        Lp.print(i);
        cout << endl << endl;
    }

    return 0;
}

The following output is produced:

Ann  52  Baker
Derek  48  Electrician
Frank  22  Driver


Frank  22  Driver
Derek  48  Electrician
Ann  52  Baker


Ann  52  Baker
Frank  22  Driver
Derek  48  Electrician


node deleted
node deleted
node deleted
plex deleted
Last edited on
closed account (D80DSL3A)
Bump.
Summary: Above is a template class which is an ordered linked list. This 'plex' list sets up links so that the list can be traversed in multiple ways. Example: In the output at the end of my opening post a list of persons is traversed by name, then by age and then by job.

My question is this: Must I write a helper function to accompany each type of structure That I would store in the plex list? Example for a person structure:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// for use by plex<T>::insert()
bool Less( const person& A, const person& B, int idx )
{
    switch(idx)
    {
        case 0:
            return A.name < B.name;
        case 1:
            return A.age < B.age;
        case 2:
            return A.job < B.job;
    }
    return true;
}

I think it is needed to provide a map of the structure data members to the index values used in the plex::insert(), but does anyone see a better way?
Last edited on
Topic archived. No new replies allowed.