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 pointer prev, next;
00043
00044 protected:
00045 IListNode() : prev() {}
00046 IListNode(const IListNode&) {}
00047
00048 pointer getNext() { return next; }
00049 const_pointer getNext() const { return next; }
00050 pointer getPrev() { return prev; }
00051 const_pointer getPrev() const { return prev; }
00052
00053 private:
00054 friend class IList<NodeType>;
00055 };
00056
00057
00078 template<class Node> class IList {
00079 template <class> class Iterator;
00080 public:
00081 typedef Node value_type;
00082 typedef typename Node::pointer pointer;
00083 typedef typename Node::const_pointer const_pointer;
00084 typedef value_type& reference;
00085 typedef const value_type& const_reference;
00086 typedef size_t size_type;
00087 typedef ptrdiff_t difference_type;
00088 typedef Iterator<value_type> iterator;
00089 typedef Iterator<const value_type> const_iterator;
00090
00091 IList() : begin_(), last_() {}
00092
00093 iterator begin() { return begin_; }
00094 const_iterator begin() const { return begin_; }
00095 iterator end() { return 0; }
00096 const_iterator end() const { return 0; }
00097
00098 bool empty() const { return begin() == end(); }
00099
00100 size_type size() const {
00101 int s = 0;
00102 for (const_iterator i=begin(); i != end(); ++i)
00103 ++s;
00104 return s;
00105 }
00106
00107 void swap(IList &x) { swap(begin_, x.begin_); swap(last_, x.last_); }
00108
00109 iterator insert(iterator i, const pointer& p) {
00110 if (empty()) {
00111 begin_ = last_ = p;
00112 insert(0, p, 0);
00113 }
00114 else if (i) {
00115 insert(i->prev, p, i);
00116 if (i == begin_) --begin_;
00117 }
00118 else {
00119 insert(last_, p, 0) ;
00120 last_ = p;
00121 }
00122 return p;
00123 }
00124
00125 void erase(iterator i) {
00126 if (begin_ == last_)
00127 begin_ = last_ = 0;
00128 else {
00129 if (i == begin_) ++begin_;
00130 else i->prev->next = i->next;
00131 if (i == last_) --last_;
00132 else i->next->prev = i->prev;
00133 }
00134 i->prev = i->next = pointer(0);
00135 }
00136
00137 void erase(iterator i, iterator j) { while(i != j) erase(i); }
00138 void clear() { while (!empty()) { erase(begin()); } }
00139
00140 reference front() { return *begin(); }
00141 const_reference front() const { return *begin(); }
00142 void push_front(const pointer& p) { insert(begin(), p); }
00143 void pop_front() { erase(begin()); }
00144
00146 iterator last() { return last_; }
00147 const_iterator last() const { return last_; }
00148
00149 reference back() { return *last(); }
00150 const_reference back() const { return *last(); }
00151 void push_back(const pointer& p) { insert(end(), p); }
00152 void pop_back() { erase(last()); }
00153
00154 private:
00155 void insert(pointer a, pointer b, pointer c) {
00156 b->prev = a;
00157 if (a) a->next = b;
00158 b->next = c;
00159 if (c) c->prev = b;
00160 }
00161
00162 template <class T>
00163 class Iterator : public boost::iterator_facade<
00164 Iterator<T>, T, boost::bidirectional_traversal_tag>
00165 {
00166 public:
00167 Iterator() : ptr() {};
00168
00169 template <class U> Iterator(
00170 const Iterator<U>& i,
00171 typename boost::enable_if_convertible<U*, T*>::type* = 0
00172 ) : ptr(i.ptr) {}
00173
00174 operator pointer() { return ptr; }
00175 operator const_pointer() const { return ptr; }
00176
00177
00178 pointer ptr;
00179
00180
00181 private:
00182 friend class boost::iterator_core_access;
00183
00184 Iterator(const_pointer p) : ptr(const_cast<pointer>(p)) {};
00185
00186 T& dereference() const { return *ptr; }
00187 void increment() { ptr = ptr->next; }
00188 void decrement() { ptr = ptr->prev; }
00189 bool equal(const Iterator& x) const { return ptr == x.ptr; }
00190
00191
00192 friend class IList<Node>;
00193 };
00194
00195 iterator begin_, last_;
00196 };
00197
00198 }
00199
00200 #endif