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 protected:
00054 ISListNode() : next() {}
00055 ISListNode(const ISListNode&) {}
00056
00057 pointer getNext() { return next; }
00058 const_pointer getNext() const { return next; }
00059
00060 private:
00061 pointer next;
00062 friend class ISList<NodeType>;
00063 };
00064
00065
00082 template <class Node> class ISList : private boost::noncopyable {
00083 template <class> class Iterator;
00084 public:
00085 typedef Node value_type;
00086 typedef typename Node::pointer pointer;
00087 typedef typename Node::const_pointer const_pointer;
00088 typedef value_type& reference;
00089 typedef const value_type& const_reference;
00090 typedef size_t size_type;
00091 typedef ptrdiff_t difference_type;
00092 typedef Iterator<value_type> iterator;
00093 typedef Iterator<const value_type> const_iterator;
00094
00095 ISList() : first(pointer()), end_(&first) {}
00096
00097 iterator begin() { return iterator(&first); }
00098 const_iterator begin() const { return const_iterator(&first); }
00099 iterator end() { return end_; }
00100 const_iterator end() const { return end_; }
00101
00102 bool empty() const { return begin() == end(); }
00103
00104 size_type size() const {
00105 int s = 0;
00106 for (const_iterator i=begin(); i != end(); ++i)
00107 ++s;
00108 return s;
00109 }
00110
00111 void swap(ISList &x) { swap(first, x.first); swap(end_, x.end_); }
00112
00116 iterator insert(iterator i, const pointer& p) {
00117 p->next = *(i.pptr);
00118 *(i.pptr) = p;
00119 if (i==end_) ++end_;
00120 return i;
00121 }
00122
00123 void erase(iterator i) {
00124 if (&i->next == end_.pptr)
00125 end_ = i;
00126 *(i.pptr) = (**(i.pptr)).next;
00127 }
00128
00129 void erase(iterator i, iterator j) { while(i != j) erase(i); }
00130 void clear() { while (!empty()) { erase(begin()); } }
00131
00132 reference front() { return *begin(); }
00133 const_reference front() const { return *begin(); }
00134 void pop_front() { erase(begin()); }
00135 void push_front(pointer x) { insert(begin(), x); }
00136
00137 void push_back(pointer x) { insert(end(), x); }
00138
00139 private:
00140 template <class T>
00141 class Iterator : public boost::iterator_facade <
00142 Iterator<T>, T, boost::forward_traversal_tag>
00143 {
00144 public:
00145 Iterator() {};
00146
00147 template <class U> Iterator(
00148 const Iterator<U>& i,
00149 typename boost::enable_if_convertible<U*, T*>::type* = 0
00150 ) : pptr(i.pptr) {}
00151
00152 operator pointer() { return *pptr; }
00153 operator const_pointer() const { return *pptr; }
00154
00155 private:
00156 friend class boost::iterator_core_access;
00157
00158 Iterator(const pointer* pp) : pptr(const_cast<pointer*>(pp)) {};
00159
00160 T& dereference() const { return **pptr; }
00161 void increment() { pptr = &(**pptr).next; }
00162 bool equal(const Iterator& x) const { return pptr == x.pptr; }
00163
00164 pointer* pptr;
00165
00166 friend class ISList<Node>;
00167 };
00168
00169 private:
00170 pointer first;
00171 iterator end_;
00172 };
00173
00174 }
00175
00176 #endif