(C++)

SortedBag Implementation Using Doubly Linked Ring

Realize this class using a sorted doubly linked ring structure, in which the elements are sorted by their values of search keys and are linked to form a ring.

 template struct Node { Node() : m_next(this), m_prev(this) {} Node(const T& val, Node* n =this, Node* p =this) : m_val(val), m_next(n), m_prev(p) {} T m_val; Node* m_next; // pointer to successor element. Node* m_prev; // pointer to predecessor element. }; template class SortedBag { public: SortedBag() : m_data(0), m_size(0), m_asc(true), m_curr(0) {} SortedBag(const SortedBag&); void operator =(const SortedBag&); ~SortedBag(); bool erase_one(const T&); long erase(const T&); void insert(const T&); void operator +=(const SortedBag&); long size() const { return m_size; } long count(const T&) const; // SIMPLE ITERATOR void begin(const bool ascending =true); bool end() const; void operator++(); void operator--(); T& get(); private: Node* m_data; // pointer to ring structure. long m_size; // number of elements in the Bag. bool m_asc; // flag to indicate iteration in ascending order or not. Node* m_curr; // iterator's current position. }; template SortedBag operator+(const SortedBag&, const SortedBag&); 

Notice that the above class has a simple iterator that facilitates access to the elements in the collection object, for ascending order using operator()++ to follow the successor links and descending order using operator()-- to follow the predecessor links. To test your implementation, produce the following main program using your implementation of SortedBag:

Create three empty sorted bags L1, L2, and L3. Generate 200 student records randomly into L1, iterate forward to visit each element of L1, insert it into L2, and check if both L1 and L2 are identical at the end of this process. Similarly, iterate backward to visit each element of L1, insert it into L3, and check if L1 and L3 are identical.

Erase the first element and last element from L1 and L2, and check if L1 and L2 are identical. Erase all elements in L1 by iterating L2 forward and finding the same element in L1. Check if L1 in fact gets empty at the end of this process.

Randomly choose 50 positions of L2, erase the elements in such positions (by iterating to the selected potions) from L2, and subsequently insert the erased elements into L1. After completing, insert all the elements of L2 into L1. Erase the first element and last element from L3, and check if L1 is identical to L3.

Use ssid field for the search key of the student record.