I have a class, record, with 15 member variables (fields). Objects of type record are stored in an AVL tree with the primary key being the member variable, ID. I need to print the records in the tree sorted by a user chosen field (anything but the primary key). Not only that, but I must apply a secondary sort based on a user chosen field. For example, if output is to be sorted by first name, if 2 or more 1st names are the same, then the output is further sorted by the secondary sort field.

I thought about reading the contents of the tree into a vector or something. But, I might lose track of a record. The user needs to be able to edit a record. So, if the record is in a vector and, say, that the user wants to edit the 3rd record printed, then when that record is updated, the update has to be applied in the tree.

Is there a way to sort my tree by a non primary key? Any thoughts would be appreciated!

What language? Are you allowed to use the sorting library of that language? Are the sort fields fixed, or can the user change them between queries to the tree?

I'd keep this simple. Read the tree into a vector, sort it by the user-choosen fields and print it out. When a user updates a record, update it in the AVL tree only, throw away the vector when you're done.

Sorry, c++, we can use anything available as long as we keep the main data structure the AVL tree (our own version). So, I can add members to my AVL class. And, it is OK to use any temp data structure.

If I understand you correctly, the user makes a query and a sub-tree is returned, but not printed yet (or, maybe report that x number of records have been found). The user then decides which fields to display and which field is the primary sort field and which field is the secondary sort field. The results are printed. The user then can choose to edit a record or search the sub-tree to narrow the results further, or start over. A search on the sub-tree may produce another sub-tree. Then, again, the user chooses which fields to print and which to sort by. As long as there are records in the sub-tree, the user can repeat the process. So, the sort fields are not fixed, yeah?

I've been thinking about this idea as well. I'm having a hard time visualizing how, when a record in the vector is updated, that is reflected in the tree as well. Also, if I go this route I'm going to need to define 15 different sorting functions to handle all the cases. Seems like there should be a better way. I'm just worried that better way is over my head.

What types are the fields? Are they all integers, strings? You should not have to write 15 sort functions.

Use pointers to store the records in the tree, copy the pointers from the subtree into a vector, sort them, and return. And the logic that updates records should be separate from the sorting. THe record update functionality only needs access to the AVL subtree for fast lookup and editing records.

You could write a template function that sorts based on the template parameter (the member variable).

Yes, all the fields are strings. I'm going to go with vector<record*>. I just never seem to think in terms of pointers, thanks for the advice. So, as long as I pass my original tree as well as any sub-tree by reference and then create a container of pointers pointing to records in the tree, I can edit records via the pointers and those edits will reflect in the original structure? I can then sort the vector by what ever field. I'm thinking, one function with the vector and field-to-edit as the params and then a switch or something to handle the cases.

I guess this wasn't so hard. It's an online course, just sucks not to be able to talk things though with anyone.

There are few ways to solve the sorting by field problem. Some are straightforward, and some are more complex and require knowledge of templates.

One simple approach: Create new class that holds Record* and you can define the operator< on that class.

eg.

Struct RecordForSort
{
RecordForSort(Record* rec, string field) : mRecord(rec), mSortField(field) {}

bool operator<(const Record& rhs)
{
return mSortField < rhs.mSortField;
}

Record* mRecord;
string mSortField;
};

Now you can create an object of this class for each record, based on the field you want to sort.

class Record{
string a;
string b;
// rest of your class..
};

Then when you want to sort by field b, you create a bunch of RecordForSort objects, passing in the Record pointer and the value of b. Then you can use stdlib sort function and it will sort by your field.

Eg. sort by field b.
vector<Record*> myRecords = GetRecordsFromSomewhere();
vector<RecordForSort> sortedRecs;
for (auto iter = myRecords.begin(); iter != myRecords.end(); ++iter)
{
sortedRecs.add(new RecordForSort(*iter, (*iter).b));
}

// since we defined operator<, sort will sort by field b values.
std:sort(sortedRecs.begin(), sortedRecs.end());

This is kind of a roundabout way to do things. And that's what lambdas are meant to solve. Although depends on what c++ compiler you are using.