Last Modified: Tue Sep 17 19:01:23 EDT 2002
|
C M S C 2 1 4 C o m p u t e r S c i e n c e I I F a l l 2 0 0 2 |
| ItemSortedList |
An ItemSortedList is a SortedList ADT (abstract data type) implement using a doubly linked list. SortedList is a sorted list where elements are sorted in increasing order by a key. In this case, the key can only appear once in a list.
The operations supported by the list are: add, remove, contains, and update.
An ItemSortedList is a container class: that is, it stores many elements of the same type. A container class is a generalization of an array.
| Declaration | Description |
| Node * first, * last ; | Pointer to the first and last node of DLL |
You may add the following additional private data members, although it is optional:
| ItemSortedList() ; |
| Default constructor. Sets first and last to NULL. Should call init() to do this. |
| bool add( const Item &dataIn ) ; |
| Add a Item object to the DLL, only if the Item's name does not already exist in the DLL. If it does NOT, then return true. If the item's name already exists, return false. You MUST use locate() to implement. |
| bool remove( const string & keyIn ) ; |
|
Remove a Item object from the DLL, with the same name as
keyIn (the points are ignored when checking if item is in the
list). Return true if such a node was successfully removed.
Return false if the node is not in the tree, and therefore not
removed.
You MUST use locate() to implement this method. |
| bool contains( const string & keyIn ) const ; |
| Return true if there exists a node in the DLL with the
same name as keyIn. Return false if
the DLL does not contain a Item by the same name.
(Points from keyIn are ignored).
You MUST use locate() to implement this method. |
| bool update( const Item &dataIn ) ; |
| Return true if there exists a node in the DLL with the
same name as the name data member of dataIn. If so, it
updates the node with dataIn
and returns true. This update should be done by calling
setData() on the Node object.
If there does not exist a node with the same name as dataIn return false, and do not alter the DLL. You MUST use locate() to implement this method. |
| int size() const ; |
| Returns the number of nodes in the DLL. |
| void clear() ; |
| Removes all nodes in the DLL, and deallocates the memory of the nodes. Also, sets first and last to NULL. May want to call helper functions. |
| ConstIterator cbegin() const ; |
| Returns an iterator whose curr points to the node in the DLL with the smallest key value. If the DLL is empty, curr should be NULL. |
| ConstIterator clast() const ; |
| Returns an iterator whose curr points to the node in the DLL with the largest key value. If the DLL is empty, curr should be NULL. |
| ConstIterator cend() const ; |
| Returns an iterator with curr set to NULL. This is a pointer that's "one past the end" on either end of a DLL. |
| string toString() const ; |
|
This should create a string that will be used by the overloaded
output operator. When printed, the output should look like
the output required by the project, i.e. it should print out
a number (indicating the item in the list), the item name, and
the points, for each item in the list.
Must be called in implementation of operator<<. |
The following methods should be implemented, if you feel they are NECESSARY (meaning that the implicit versions of these methods are inadequate).
| ItemSortedList( const ItemSortedList &other ) ; |
| Copy constructor. Copies the entire same structure as other. You must use helper methods: freeMem(), init(), and/or copy(). |
| ItemSortedList &operator=( const ItemSortedList &other ) ; |
| Assignment operator. Copies the entire DLL. It must first deallocate all nodes in the DLL, before making the copy. If you choose to implement, you must use helper methods: freeMem(), init(), and/or copy(). |
| ~ItemSortedList(); |
| Destructor. Deallocates all nodes in DLL. If you choose to implement, you must use helper methods: freeMem(), init(), and/or copy(). |
| bool locate( const string & keyIn, ItemSortedList::Node * & curr ) const ; |
|
You can either to successor locate or predecessor
locate. Unlike singly linked lists, either version works well
(predecessor locate works best, but read on).
In successor locate, locate() places curr at the node with the same value as keyIn (if it's in the DLL), or to its successor (if it's not in the DLL). That successor may be NULL (which indicates that keyIn will be the largest value in the list, once added). In predecessor locate, locate() places curr at the node with the same value as keyIn (if it's in the DLL), or to its predecessor (if it's not in the DLL). That predecessor may be NULL (which indicates that keyIn will be the smallest value in the list, once added). If you use predecessor locate, you should start from the last element in the list (it can be done forwards, but there's some advantages when copying to do it backwards).
Precondition: (successor locate) curr == first
(9/20) Since there is no getKey() method1,
you can call curr->getData() (which returns an Item
reference) and create a local variable of type, Item, (call
this search) and set the name of that item to keyIn.
You can then compare the two items by using the relational
operators of Item.
(9/28) locate() returns true if keyIn
is in the list, and false if it is not in the list.
|
If you do choose to implement the copy constructor, assignment operator, and destructor, implement the following methods and use them as helper functions for the three methods.
| void init() ; |
| Set first and last to NULL. |
| void copy( const ItemSortedList & other ) ; |
| Creates a copy of the DLL in other, allocate the same number
of nodes as other.
Precondition: first == NULL && last == NULL. Do NOT deallocate nodes (see precondition). |
| void freeMem() ; |
| Deallocates nodes in DLL. |
You may add other private methods.
| ItemSortedList::Node |
This is a private, nested class of ItemSortedList.
| Declaration | Description |
| Item data | Stores a Item object |
| Node * prev | Points to predecessor (node with next smallest value) |
| Node * next | Points to successor (node with next largest value) |
| Node( const Item & dataIn = Item() ) ; |
| Default constructor. Copies data to dataIn. |
| Node * getPrev() const ; |
| Returns prev. |
| Node * getNext() const ; |
| Returns next. |
| void setNext( Node * nextIn ) ; |
| Sets next to nextIn |
| void setPrev( Node * prevIn ) ; |
| Sets prev to prevIn |
| const Item & getData() const ; |
|
(9/19) Now returns it by reference, so it can work with iterators.
Returns data. (Thought question: should this function return a const reference instead? Don't make the change, but think about the advantages/disadvatanges). |
| bool setData( const Item & item ) ; |
|
Copies item over data, but ONLY if item
and data contain the same name. Returns true if data
was set. Returns false if the names are different and does
NOT update the node. (Used by: update()).
(9/18) Removed const from method |
| ItemSortedList::ConstIterator |
This is a nested class inside the private section of ItemSortedList.
| Declaration | Description |
| Node * curr | Points to a Node |
| ConstIterator( Node *currIn = NULL ) ; |
| Sets curr to currIn |
| const Item * operator->() const ; |
| Returns pointer to Item object stored inside Node pointed to by curr. |
| const Item & operator*() const ; |
| Returns a reference to Item object stored inside Node pointed to by curr. |
| ConstIterator & operator++() ; ConstIterator operator++( int ) ; |
| Pre-increment operator and post-increment operator, respectively. The preincrement operator move curr to its successor, and returns *this. The postincrement operator creates a temp ConstIterator object, which is a copy of *this, then moves curr to its successor, and returns temp, which still has its curr pointing to the original Node prior to calling this method. |
| ConstIterator & operator--() ; ConstIterator operator--( int ) ; |
| Pre-decrement operator and post-decrement operator, respectively. The pre-decrement operator move curr to its predecessor, and returns *this. The post-decrement operator creates a temp ConstIterator object, which is a copy of *this, then moves curr to its predecessor, and returns temp, which still has its curr pointing to the original Node prior to calling this method. |
| bool operator==( const ConstIterator &other ) const ; |
| Returns true if curr and other.curr point to the same Node (i.e., both store the same address). Returns false otherwise. |
| bool operator!=( const ConstIterator &other ) const ; |
| Returns false if curr and other.curr point to the same Node (i.e., both store the same address). Returns true otherwise. |
|
See the class syllabus for policies concerning email Last Modified: Tue Sep 17 19:01:23 EDT 2002 |
|
|
|
|
|