00001 #ifndef QPID_ISLIST_H
00002 #define QPID_ISLIST_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 <boost/iterator/iterator_adaptor.hpp>
00026 #include <boost/noncopyable.hpp>
00027 #include "pointer_to_other.h"
00028
00029 namespace qpid {
00030
00031 template <class Pointer> struct Pointee {
00032 typedef typename Pointer::element_type type;
00033 };
00034
00035 template <class T> struct Pointee<T*> {
00036 typedef T type;
00037 };
00038
00039 template <class> class ISList;
00040 template <class> class IList;
00041
00047 template <class Pointer> class ISListNode {
00048 public:
00049 typedef Pointer pointer;
00050 typedef typename Pointee<Pointer>::type NodeType;
00051 typedef typename pointer_to_other<Pointer, const NodeType>::type const_pointer;
00052
00053 pointer getNext() { return next; }
00054 pointer * getNextPtr() { return & next; }
00055 const_pointer getNext() const { return next; }
00056
00057 protected:
00058 ISListNode() : next() {}
00059 ISListNode(const ISListNode&) {}
00060
00061
00062 private:
00063 pointer next;
00064 friend class ISList<NodeType>;
00065 };
00066
00067
00084 template <class Node> class ISList : private boost::noncopyable {
00085 template <class> class Iterator;
00086 public:
00087 typedef Node value_type;
00088 typedef typename Node::pointer pointer;
00089 typedef typename Node::const_pointer const_pointer;
00090 typedef value_type& reference;
00091 typedef const value_type& const_reference;
00092 typedef size_t size_type;
00093 typedef ptrdiff_t difference_type;
00094 typedef Iterator<value_type> iterator;
00095 typedef Iterator<const value_type> const_iterator;
00096
00097 ISList() : first(pointer()), end_(&first) {}
00098
00099 iterator begin() { return iterator(&first); }
00100 const_iterator begin() const { return const_iterator(&first); }
00101 iterator end() { return end_; }
00102 const_iterator end() const { return end_; }
00103
00104 bool empty() const { return begin() == end(); }
00105
00106 size_type size() const {
00107 int s = 0;
00108 for (const_iterator i=begin(); i != end(); ++i)
00109 ++s;
00110 return s;
00111 }
00112
00113 void swap(ISList &x) { swap(first, x.first); swap(end_, x.end_); }
00114
00118 iterator insert(iterator i, const pointer& p) {
00119 p->next = *(i.pptr);
00120 *(i.pptr) = p;
00121 if (i==end_) ++end_;
00122 return i;
00123 }
00124
00125 void erase(iterator i) {
00126 if (&i->next == end_.pptr)
00127 end_ = i;
00128 *(i.pptr) = (**(i.pptr)).next;
00129 }
00130
00131 void erase(iterator i, iterator j) { while(i != j) erase(i); }
00132 void clear() { while (!empty()) { erase(begin()); } }
00133
00134 reference front() { return *begin(); }
00135 const_reference front() const { return *begin(); }
00136 void pop_front() { erase(begin()); }
00137 void push_front(pointer x) { insert(begin(), x); }
00138
00139 void push_back(pointer x) { insert(end(), x); }
00140
00141 private:
00142 template <class T>
00143 class Iterator : public boost::iterator_facade <
00144 Iterator<T>, T, boost::forward_traversal_tag>
00145 {
00146 public:
00147 Iterator() {};
00148
00149 template <class U> Iterator(
00150 const Iterator<U>& i,
00151 typename boost::enable_if_convertible<U*, T*>::type* = 0
00152 ) : pptr(i.pptr) {}
00153
00154 operator pointer() { return *pptr; }
00155 operator const_pointer() const { return *pptr; }
00156 pointer* pptr;
00157
00158 private:
00159 friend class boost::iterator_core_access;
00160
00161 Iterator(const pointer* pp) : pptr(const_cast<pointer*>(pp)) {};
00162
00163 T& dereference() const { return **pptr; }
00164 void increment() { pptr = (**pptr).getNextPtr(); }
00165 bool equal(const Iterator& x) const { return pptr == x.pptr; }
00166
00167
00168 friend class ISList<Node>;
00169 };
00170
00171 private:
00172 pointer first;
00173 iterator end_;
00174 };
00175
00176 }
00177
00178 #endif