The SortedList class is the base class for all of the queues. The SortedList maintains a logical list of pointers to Elements. An Element can be anything, including a predefined C++ type, a user defined class, or a pointer to one of these things. The distinction between the logical list and a list data structure is important, since the internal structure of the class might not be a list at all - it could be a b-tree or a hash table. A logical list refers to the outside user's view of the list - no matter how the data is stored internally, the user's perception is that a sorted list is being maintained. This was done so that the internal structure of the list could change without changing the interface. For instance, the internal data structure of the SortedList could be based on a singly linked list, a doubly linked list, or a tree, and the interface will remain the same. This provides for flexibility in changing the data structures of the TimeWarp object's queues. If one wanted create a SortedList using an AVL tree as the data structure the information was being kept in, then the queues would continue to operate correctly, and all of the benefits of this using this data structure would automatically become benefits in the simulation queues as well.
As was previously stated, the SortedList class actually holds pointers to its elements rather than copies. This is to make the insertion and removal as efficient as possible - a pointer is copied rather than copying large chunks of memory. A consequence of this style of storage is that data that appears to be ``in'' the list, and therefore protected by the list, is not. For instance, if there is a pointer to element ``foo,'' and it is inserted into the list, if I keep the pointer to foo and modify the data in foo, the data in the list is modified too.
A feature of the SortedList class is that the list has state. The list keeps track of a "current" position that the user of the list can control, the last place that an element was inserted, and last element found in the list. This state information will be referred to as currentPos, insertPos, and findPos from here on.
Since the list is a template class that can store any type, the list cannot know in advance how to sort the data it is storing. Some means must be made to tell it how to sort the stored data. This is accomplished by supplying a comparison function to the list class that is specific to the data. This function should have the following form:
int <func_name>(Element * a, Element * b) {
if (a goes before b in the list) return (integer less than 0)
if (b goes before a in the list) return (integer greater than 0)
else return (int) 0
}
Here is a list of the functions of the SortedList class:
The following commands do not modify currentPos:
void insert(Element *) - insert <Element> into the right place in the logical list, using the comparison function provided by the user.
Element * front() - return a pointer to the front of the logical list. Return NULL if list is empty.
Element * back() - return a pointer to the back of the logical list. Return NULL if list is empty.
Element * get() - return pointer to the element at currentPos. If currentPos is NULL, return NULL and leave currentPos set to NULL.
The following commands do not modify the currentPos pointer, but modify the findPos pointer. They also return a Element *:
find(Element * key, findMode_t ) - pass in a pointer to a key which should have fields defined such that the comparison function can be invoked to find an element. This function has a default findMode defined as EQUAL.
Element * findMode_t is defined as an enum:
enum findMode_t LESS,LESSEQUAL,EQUAL,GREATEREQUAL,GREATER
This list will be used as an example: 1,2,2,2,3,3,5,6,7,9
The operation on a mode basis is as described below: LESS - Find the first element in the logical list with a value less than the key. If a find(3,LESS) was executed on the example list, the findPos pointer would be pointed at the third 2 in the list, and the Element * returned in will equal that to 2. If a find(1,LESS) was called, the findPos will be set NULL and the return value will be NULL.
LESSEQUAL - Find the first element in the logical list with a value equal to the key, if no such element exists, return the first element less than the key. If a find(3,LESSEQUAL) was executed, the findPos pointer would be pointed at the first 3 in the list, the Element * returned will point at that 3. If a find(4,LESSEQUAL) is executed on the example list, the Element * returned will point at the second 3 and findPos will be set there as well. If no element exists matching either criteria (find(0,LESSEQUAL)), then a NULL is returned, and findPos is set to NULL.
EQUAL - Find the first element in the logical list with a value equal to the key. If a find(3,EQUAL) was executed, the findPos pointer would be pointed at the first 3 in the list, and the function will return the same pointer. If a find(4, EQUAL) is executed on the list, then a NULL is returned, and findPos is set to NULL.
GREATEREQUAL - The same as LESSEQUAL, except if an exact match isn't found, return the first element that is greater then the key.
GREATER - The same as LESS, except that the first element greater than the key should be returned.
findNext() - Find the next Element that has the same key values as the list element currently pointed to by the findPos pointer. Start the search from the current findPos. If findPos is NULL, then return NULL and leave findPos set to NULL. If matching element exists to the right of findPos: Return Element * equal to the first matching element in the list. Set findPos to this element as well.
If no matching element exists to the right of findPos: Return NULL and set findPos to NULL as well.
These functions modify the currentPos pointer, but don't modify the findPos pointer: Element * setCurrentToFind() - Set currentPos equal to findPos, and return Element that currentPos now points at.
Element * seek(int, seekMode_t) - return a status, update the currentPos pointer according to parameters passed into function. The int is an offset, and the mode_t tells the function where to start seeking from. The definition of mode_t follows: enum mode_t START, CURRENT, END;
If any seek request goes off of the end of the list, return NULL and set currentPos to NULL.
The int size() command returns an integer equal to the number of elements in the list.
The Element * removeCurrent() command removes the element at currentPos. If currentPos is NULL return NULL and do nothing. If currentPos isn't NULL, then remove the element, increment currentPos, and return a pointer to the Element removed. If findPos is pointing at the element being removed, increment it too. It is important to note that the Container is being removed from the SortedList, but the object pointed to by the container is not deleted.
The Element * removeFind() command removes the element at findPos. If findPos is NULL return NULL and do nothing. If findPos isn't NULL, then remove the element, increment findPos, and return a pointer to the Element removed. If currentPos pointing at the element being removed, increment it too. It is important to note that the Container is being removed from the SortedList, but the object pointed to by the container is not deleted.
The SortedList class has two constructors. One takes an argument in the form of SortedList(int (*)(Element *, Element *)), which sets the compare function at the beginning. The other takes no arguments. If the list is constructed with no arguments, the function void setFunc ( int (*)(Element *, Element *) ); should be called before a find or insert is called. Otherwise, the result is undefined, but a segmentation fault will probably occur.
The default implementation of the specification presented is based on a doubly linked list. Theoretically any class conforming to this specification will work with the WARPED kernel. Users of the WARPED kernel are encouraged to develop more efficient list classes, and let the authors use them.
The interface for the default SortedList class follows:
template < class Element > class SortedList {
public:
SortedList();
SortedList( int (*)(Element*, Element*) ); // construct with compare func
~SortedList();
void setFunc( int (*)(Element*, Element*) );
int size() { return listsize; };
Element* front();
Element* back();
Element* seek (int, listMode_t);
void insert(Element*);
Element* get();
Element* removeFind();
Element* removeCurrent();
Element* find(Element*, findMode_t mode = EQUAL);
Element* findNext();
void print();
Element* setCurrentToInsert();
Element* setCurrentToFind();
protected:
Container< Element > *head;
Container< Element > *tail;
Container< Element > *insertPos;
Container< Element > *currentPos;
Container< Element > *findPos;
int (*compare)(Element*, Element*);
Element* remove(Container<Element> *);
private:
int listsize;
Element* findElement (Element*, Container<Element>*, findMode_t);
};