class LinkedSortedList
1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 12-2
6: /** ADT sorted list: Link-based implementation.
7: @file LinkedSortedList.h */
8: #ifndef LINKED_SORTED_LIST_
9: #define LINKED_SORTED_LIST_
10: #include <memory>
11: #include "SortedListInterface.h"
12: #include "Node.h"
13: #include "PrecondViolatedExcept.h"
15: template<class ItemType>
16: class LinkedSortedList : public SortedListInterface<ItemType>
17: {
18: private:
19: std::shared_ptr<Node<ItemType>> headPtr; // Pointer to first node in chain
20: int itemCount; // Current count of list items
21:
22: // Locates the node that is before the node that should or does
23: // contain the given entry.
24: // @param anEntry The entry to find.
25: // @return Either a pointer to the node before the node that contains
26: // or should contain the given entry, or nullptr if no prior node exists.
27: auto getNodeBefore(const ItemType& anEntry) const;
28:
29: // Locates the node at a given position within the chain.
30: auto getNodeAt(int position) const;
31:
32: // Returns a pointer to a copy of the chain to which origChainPtr points.
33: auto copyChain(const std::shared_ptr<Node<ItemType>>& origChainPtr);
34:
35: public:
36: LinkedSortedList();
37: LinkedSortedList(const LinkedSortedList<ItemType>& aList);
38: virtual ~LinkedSortedList();
39: bool insertSorted(const ItemType& newEntry);
40: bool removeSorted(const ItemType& anEntry);
41: int getPosition(const ItemType& newEntry) const;
42:
43: // The following methods are the same as given in ListInterface:
44: bool isEmpty() const;
45: int getLength() const;
46: bool remove(int position);
47: void clear();
48: ItemType getEntry(int position) const throw(PrecondViolatedExcept);
49: }; // end LinkedSortedList
50: #include "LinkedSortedList.cpp"
51: #endif