00001 #ifndef QPID_ILIST_H
00002 #define QPID_ILIST_H
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "ISList.h"
00026
00027 namespace qpid {
00028
00029 template <class> class IList;
00030
00036 template <class Pointer> class IListNode {
00037 public:
00038 typedef Pointer pointer;
00039 typedef typename Pointee<Pointer>::type NodeType;
00040 typedef typename pointer_to_other<Pointer, const NodeType>::type const_pointer;
00041
00042 protected:
00043 IListNode() : prev() {}
00044 IListNode(const IListNode&) {}
00045
00046 pointer getNext() { return next; }
00047 const_pointer getNext() const { return next; }
00048 pointer getPrev() { return prev; }
00049 const_pointer getPrev() const { return prev; }
00050
00051 private:
00052 pointer prev, next;
00053 friend class IList<NodeType>;
00054 };
00055
00056
00077 template<class Node> class IList {
00078 template <class> class Iterator;
00079 public:
00080 typedef Node value_type;
00081 typedef typename Node::pointer pointer;
00082 typedef typename Node::const_pointer const_pointer;
00083 typedef value_type& reference;
00084 typedef const value_type& const_reference;
00085 typedef size_t size_type;
00086 typedef ptrdiff_t difference_type;
00087 typedef Iterator<value_type> iterator;
00088 typedef Iterator<const value_type> const_iterator;
00089
00090 IList() : begin_(), last_() {}
00091
00092 iterator begin() { return begin_; }
00093 const_iterator begin() const { return begin_; }
00094 iterator end() { return 0; }
00095 const_iterator end() const { return 0; }
00096
00097 bool empty() const { return begin() == end(); }
00098
00099 size_type size() const {
00100 int s = 0;
00101 for (const_iterator i=begin(); i != end(); ++i)
00102 ++s;
00103 return s;
00104 }
00105
00106 void swap(IList &x) { swap(begin_, x.begin_); swap(last_, x.last_); }
00107
00108 iterator insert(iterator i, const pointer& p) {
00109 if (empty()) {
00110 begin_ = last_ = p;
00111 insert(0, p, 0);
00112 }
00113 else if (i) {
00114 insert(i->prev, p, i);
00115 if (i == begin_) --begin_;
00116 }
00117 else {
00118 insert(last_, p, 0) ;
00119 last_ = p;
00120 }
00121 return p;
00122 }
00123
00124 void erase(iterator i) {
00125 if (begin_ == last_)
00126 begin_ = last_ = 0;
00127 else {
00128 if (i == begin_) ++begin_;
00129 else i->prev->next = i->next;
00130 if (i == last_) --last_;
00131 else i->next->prev = i->prev;
00132 }
00133 i->prev = i->next = pointer(0);
00134 }
00135
00136 void erase(iterator i, iterator j) { while(i != j) erase(i); }
00137 void clear() { while (!empty()) { erase(begin()); } }
00138
00139 reference front() { return *begin(); }
00140 const_reference front() const { return *begin(); }
00141 void push_front(const pointer& p) { insert(begin(), p); }
00142 void pop_front() { erase(begin()); }
00143
00145 iterator last() { return last_; }
00146 const_iterator last() const { return last_; }
00147
00148 reference back() { return *last(); }
00149 const_reference back() const { return *last(); }
00150 void push_back(const pointer& p) { insert(end(), p); }
00151 void pop_back() { erase(last()); }
00152
00153 private:
00154 void insert(pointer a, pointer b, pointer c) {
00155 b->prev = a;
00156 if (a) a->next = b;
00157 b->next = c;
00158 if (c) c->prev = b;
00159 }
00160
00161 template <class T>
00162 class Iterator : public boost::iterator_facade<
00163 Iterator<T>, T, boost::bidirectional_traversal_tag>
00164 {
00165 public:
00166 Iterator() : ptr() {};
00167
00168 template <class U> Iterator(
00169 const Iterator<U>& i,
00170 typename boost::enable_if_convertible<U*, T*>::type* = 0
00171 ) : ptr(i.ptr) {}
00172
00173 operator pointer() { return ptr; }
00174 operator const_pointer() const { return ptr; }
00175
00176 private:
00177 friend class boost::iterator_core_access;
00178
00179 Iterator(const_pointer p) : ptr(const_cast<pointer>(p)) {};
00180
00181 T& dereference() const { return *ptr; }
00182 void increment() { ptr = ptr->next; }
00183 void decrement() { ptr = ptr->prev; }
00184 bool equal(const Iterator& x) const { return ptr == x.ptr; }
00185
00186 pointer ptr;
00187
00188 friend class IList<Node>;
00189 };
00190
00191 iterator begin_, last_;
00192 };
00193
00194 }
00195
00196 #endif