Section 6 - Building On Top of lists: An iTunes Application
2B.6.1 Inserting In Order
We have seen an example of sorting an array. Now that we have a list ADT at our disposal, we can try our hand at building the list in an orderly fashion so that no sorting is necessary, that is, so that all the items in the list are placed in their correct order. Of course this pre-supposes two things:
- The underlying Object class has some natural ordering.
- The natural ordering is reflected by the < operator.
What we propose to do next is write a main() and global scope function insert( theList, itemToInsert ) that will put the itemToInsert into the list in its correct position. While this could be the basis of some reusable data type or template, for this example, we'll show how a programmer might use the FHlist data structure directly, without adding any such new layers of abstraction. Many programmers like to just get a program to work, without creating their own mini classes for future use. This section honors such a situation.
We will use the iTunesEntry objects as an entertaining base type for our effort.
2B.6.2 iTunesEntry (Again) ... And How To Implement an Ordering Switch
As we have seen, the iTunesEntry class does have a natural ordering -- in fact it has three natural orderings, and there is a switch that will select the ordering that we want the < operator to observe. The "switch" takes the form of a static method, whose calling syntax is:
iTunesEntry::setSortType( iTunesEntry::SORT_BY_TIME );
The three static constants we can pass in are case SORT_BY_TITLE, SORT_BY_ARTIST, SORT_BY_TIME, with iTunesEntry:: prepended, of course.
Since we will find it useful to use this technique to select one of several sorting switches in a class that has multiple potential fields on which to compare, I'll show you exactly how this is done. You can do it in any class you write.
First, we set up the class prototype:
class iTunesEntry
{
private:
static int sortKey;
public:
static enum { SORT_BY_TITLE, SORT_BY_ARTIST, SORT_BY_TIME } eSortType;
static bool setSortType( int whichType );
bool operator<(const iTunesEntry &other) const;
};
The static sortKey is the member that remembers what our sort key is at any given moment. We could define our sort types using static const int, but doing so with more than two or three constants is tedious. Therefore, we often use the enum type, which accomplishes the exact same thing - enums are ints. The above syntax for the enum eSortType (which type name we never actually use anywhere, by the way) causes SORT_BY_TITLE = 0, SORT_BY_ARTIST = 1, etc. You can look up enum if you want more information about variations.
Next, the setSortType() method is written like so:
bool iTunesEntry::setSortType( int whichType )
{
switch (whichType)
{
case SORT_BY_TITLE:
case SORT_BY_ARTIST:
case SORT_BY_TIME:
sortKey = whichType;
return true;
default:
return false;
}
return true;
}
As you can see, it's pretty straightforward. Finally, we need an operator<() method which, in the case of iTunesEntry looks like:
bool iTunesEntry::operator<(const iTunesEntry &other) const
{
switch (sortKey)
{
case SORT_BY_TITLE:
return (title < other.title);
case SORT_BY_ARTIST:
// get last name from string
// stack the last name before the first - no worries about trailing last
return
(
getArtistLastName() + artist
<
other.getArtistLastName() + other.getArtist()
);
case SORT_BY_TIME:
return (tuneTime < other.tuneTime);
default:
return false;
}
return true;
}
You don't need to see the getArtistLastName() to get the idea, but if you are curious, it is in iTunesEntry.cpp. The point is, each case has its own way to interpret what "less than" means, and you can make it mean whatever you want in each case.
You may also define the operators >, ==, !=, <= and >= similarly, but once you have < the rest can (and usually should) be done "on top" of it, rather than defining each one from scratch. One has to be careful because in some situations == should not be overloaded to have a meaning less strict than total object equality. However, if you have a sort key which is guaranteed to be unique, it is arguably a good idea to define it according to that key, just as we did above. These are topics open for discussion. The most important thing is that we have meaning for <. Everything after that is easy.
2B.6.3 Inserting an iTunesEntry With a Global Scope Function
In order to make this work somewhat cleanly, we create a global scope method, insertInOrder(), which will take a list and an iTunesEntry and insert the iTuneEntry into the list in its correct place as controlled by the < operator of iTunesEntry. There is one important assumption about this method: it assumes that the list was correctly sorted before it was called. If you pass in some randomly built list, it can't possibly put the new iTunesEntry into its proper place. But this assumption is justified since we would presumably use only this method to insert new tunes into the list.
To get you thinking about it correctly, let's remember that the list that we are going to pass in is a specialization of the FHlist template -- in particular, we are assuming this is a list of iTunesEntrys, so the list will be of type FHlist<iTunesEntry>. Also, the tune to insert will be a const iTunesEntry &, since we always prefer to pass references for efficiency and we want the const to protect it. Without further ado, let's put up the code for the method.
void insertInOrder( FHlist<iTunesEntry> &theList, const iTunesEntry & theTune )
{
FHlist<iTunesEntry>::iterator
iter,
theEnd = theList.end();
for (iter = theList.begin(); iter != theEnd; ++iter )
if ( theTune < *iter)
break;
// regardless of how we ended loop, we can insert (before iter)
theList.insert(iter, theTune);
}
This is simple, but it could even be simpler by omitting the iterator theEnd. I put that in to speed processing. We would not want to compute theList.end() every darn loop pass. Observant students, take note.
The logic for this is somewhat universal so memorize the idea. You will move up the list looking for the first item that is greater than the item you want to insert.
2B.6.4 A Test main()
Here is the test main() that will read the tunes into an array, put them into a list haphazardly, show the unordered times, clear the list, re-insert them all (this time using the insertInOrder() function) then finally and proudly show the ordered times.
// Sample main() for creating an ordered list of iTunesEntry objects
// CS 2C, Foothill College, Michael Loceff, creator
#include <iostream>
using namespace std;
#include "iTunes.h"
#include "FHlist.h"
void insertInOrder( FHlist<iTunesEntry> &theList, const iTunesEntry & theTune );
// --------------- main ---------------
int main()
{
// read the data from file
iTunesEntryReader tunesInput("itunes_file.txt");
int arraySize, k;
// test the success of the read
if (tunesInput.readError())
{
cout << "Couldn't open " << tunesInput.getFileName() << " for input.\n";
exit(1);
}
arraySize = tunesInput.getNumTunes();
cout << "\nSuccessfully read " << arraySize << " tunes from file "
<< tunesInput.getFileName() << endl << endl;
// prepare to build a list of iTunes
FHlist<iTunesEntry> tunesList;
FHlist<iTunesEntry>::const_iterator iter;
// prepare to insert into the list by the time, from shortest to longest
iTunesEntry::setSortType(iTunesEntry::SORT_BY_TIME);
// load the list first unsorted and display times
for (k = 0; k < arraySize; k++)
tunesList.push_back( tunesInput[k] );
cout << "\n---------- out-of-order list ----------------\n";
for (iter = tunesList.begin(); iter != tunesList.end(); iter++)
cout << (*iter).convertTimeToString() << " ";
cout << endl;
// repeat, this time inserting in sorted order
tunesList.clear();
for (k = 0; k < arraySize; k++)
insertInOrder( tunesList, tunesInput[k] );
cout << "\n---------- ordered list ----------------\n";
for (iter = tunesList.begin(); iter != tunesList.end(); iter++)
cout << (*iter).convertTimeToString() << " ";
cout << endl;
return 0;
}
void insertInOrder( FHlist<iTunesEntry> &theList, const iTunesEntry & theTune )
// definition given above { }
/* --------------- Tail End of Run ----------------
Successfully read 79 tunes from file itunes_file.txt
---------- out-of-order list ----------------
3:56 3:40 3:48 4:23 3:50 4:43 5:08 2:58 2:55 3:36 3:14 3:28 7:23 3:
50 4:36 3:07 3:02 5:43 4:17 3:21 3:12 3:04 1:09 13:59 13:20 2:21 2:
34 2:55 2:48 3:24 4:58 4:30 1:19 2:35 5:48 4:55 3:59 3:24 3:48 3:38
4:03 4:36 3:37 3:15 3:30 5:56 4:59 4:12 2:27 7:14 7:25 6:42 3:06
2:57 7:42 4:16 3:24 3:12 6:07 12:22 5:11 3:27 5:10 4:38 5:51 7:31 5
:25 15:41 5:13 3:51 3:55 3:47 5:31 2:51 3:31 4:20 3:20 5:47 3:50
---------- ordered list ----------------
1:09 1:19 2:21 2:27 2:34 2:35 2:48 2:51 2:55 2:55 2:57 2:58 3:02 3:
04 3:06 3:07 3:12 3:12 3:14 3:15 3:20 3:21 3:24 3:24 3:24 3:27 3:28
3:30 3:31 3:36 3:37 3:38 3:40 3:47 3:48 3:48 3:50 3:50 3:50 3:51
3:55 3:56 3:59 4:03 4:12 4:16 4:17 4:20 4:23 4:30 4:36 4:36 4:38 4:
43 4:55 4:58 4:59 5:08 5:10 5:11 5:13 5:25 5:31 5:43 5:47 5:48 5:51
5:56 6:07 6:42 7:14 7:23 7:25 7:31 7:42 12:22 13:20 13:59 15:41
Press any key to continue . . .
---------------------------------------------------- */
2B.6.5 Sorting a List vs. Building A Sorted List
Let's reflect on the difference between applying a sorting algorithm to an array (or list) as we did last week, and building a sorted list from scratch, as we did above These are two different things. As you get deeper into data structures, you'll see how important it is to know which one you are doing. In the early tree data structures, we'll be inserting things in an orderly way into a tree that was somewhat ordered to begin with. That parallels the above approach. Later when we get to sort algorithms, we'll be working with an unsorted structure that needs to be reorganized from scratch. We will even mix the ideas in some situations, where we apply an algorithm after inserting a new element into a data structure, but even then, it will be important to separate in our minds the act of inserting something and the act of sorting (reorganizing) the data after the insertion.