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
|