1 #ifndef RING_H 2 #define RING_H 3 // Making a "ring" data structure from the STL 4 #include <list> 5 using namespace std; 6 7 template<class T> 8 class ring { 9 list<T> lst; 10 public: 11 12 ring &operator=(const ring *r) { 13 lst = r->lst; 14 } 15 // Declaration necessary so the following 16 // 'friend' statement sees this 'iterator' 17 // instead of std::iterator: 18 class iterator; 19 friend class iterator; 20 class iterator : 21 public std::iterator<std::bidirectional_iterator_tag, T, ptrdiff_t> { 22 23 public: 24 typename list<T>::iterator it; 25 list<T>* r; 26 27 28 // "typename" necessary to resolve nesting: 29 iterator()30 iterator(): r(NULL) {} iterator(list<T> & lst,const typename list<T>::iterator & i)31 iterator(list<T>& lst, const typename list<T>::iterator& i) 32 : r(&lst), it(i) {} 33 34 iterator &operator=(const iterator& x) { 35 it = x.it; 36 r = x.r; 37 return *this; 38 } 39 40 bool operator==(const iterator& x) const { 41 return it == x.it; 42 } 43 44 bool operator!=(const iterator& x) const { 45 return !(*this == x); 46 } 47 48 typename list<T>::reference operator*() const { 49 return *it; 50 } 51 52 iterator& operator++() { 53 ++it; 54 if(it == r->end()) 55 it = r->begin(); 56 return *this; 57 } 58 59 iterator operator++(int) { 60 iterator tmp = *this; 61 ++*this; 62 return tmp; 63 } 64 65 iterator& operator--() { 66 if(it == r->begin()) 67 it = r->end(); 68 --it; 69 return *this; 70 } 71 72 iterator operator--(int) { 73 iterator tmp = *this; 74 --*this; 75 return tmp; 76 } 77 78 iterator operator+(int i) { 79 iterator tmp = *this; 80 while(i--) ++tmp; 81 return tmp; 82 } 83 84 iterator operator-(int i) { 85 iterator tmp = *this; 86 while(i--) --tmp; 87 return tmp; 88 } 89 insert(const T & x)90 iterator insert(const T& x){ 91 return iterator(*r, r->insert(it, x)); 92 } 93 erase()94 iterator erase() { 95 iterator tmp = iterator(*r, r->erase(it)); 96 97 if (tmp.it == r->end()) tmp.it = r->begin(); 98 99 return tmp; 100 } 101 }; 102 insert(iterator & i,const T & x)103 iterator insert(iterator &i, const T& x) { 104 typename list<T>::iterator it; 105 it = lst.insert(i.it, x); 106 return iterator(lst, it); 107 } 108 push_back(const T & x)109 iterator push_back(const T& x) { 110 typename list<T>::iterator it; 111 it = lst.insert(lst.end(), x); 112 return iterator(lst, it); 113 114 } 115 /* void push_back(const T& x) { 116 lst.push_back(x); 117 }*/ 118 begin()119 iterator begin() { 120 return iterator(lst, lst.begin()); 121 } 122 size()123 int size() { return lst.size(); } clear()124 void clear() { lst.clear(); } reverse()125 void reverse() { lst.reverse(); } erase(iterator & i)126 void erase(iterator &i) { lst.erase(i.it); } 127 }; 128 129 #endif 130