00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef RAUL_LIST_HPP
00019 #define RAUL_LIST_HPP
00020
00021 #include <cstddef>
00022 #include <cassert>
00023 #include <boost/utility.hpp>
00024 #include "raul/Deletable.hpp"
00025 #include "raul/AtomicPtr.hpp"
00026 #include "raul/AtomicInt.hpp"
00027
00028 namespace Raul {
00029
00030
00037 template <typename T>
00038 class List : public Raul::Deletable, public boost::noncopyable
00039 {
00040 public:
00041
00048 class Node : public Raul::Deletable {
00049 public:
00050 Node(T elem) : _elem(elem) {}
00051 virtual ~Node() {}
00052
00053 template <typename Y>
00054 Node(const typename List<Y>::Node& copy)
00055 : _elem(copy._elem), _prev(copy._prev), _next(copy._next)
00056 {}
00057
00058 Node* prev() const { return _prev.get(); }
00059 void prev(Node* ln) { _prev = ln; }
00060 Node* next() const { return _next.get(); }
00061 void next(Node* ln) { _next = ln; }
00062 T& elem() { return _elem;}
00063 const T& elem() const { return _elem; }
00064
00065 private:
00066 T _elem;
00067 AtomicPtr<Node> _prev;
00068 AtomicPtr<Node> _next;
00069 };
00070
00071
00072 List(size_t size=0, Node* head=NULL, Node* tail=NULL)
00073 : _size(size)
00074 , _end_iter(this)
00075 , _const_end_iter(this)
00076 {
00077 _head = head;
00078 _tail = tail;
00079 _end_iter._listnode = NULL;
00080 _const_end_iter._listnode = NULL;
00081 }
00082
00083 ~List();
00084
00085 void push_back(Node* elem);
00086 void push_back(T& elem);
00087
00088 void append(List<T>& list);
00089
00090 void clear();
00091
00093 unsigned size() const { return (unsigned)_size.get(); }
00094
00096 bool empty() { return (_head.get() == NULL); }
00097
00098 class iterator;
00099
00101 class const_iterator {
00102 public:
00103 const_iterator(const List<T>* const list);
00104 const_iterator(const iterator& i)
00105 : _list(i._list), _listnode(i._listnode) {}
00106
00107 inline const T& operator*();
00108 inline const T* operator->();
00109 inline const_iterator& operator++();
00110 inline bool operator!=(const const_iterator& iter) const;
00111 inline bool operator!=(const iterator& iter) const;
00112 inline bool operator==(const const_iterator& iter) const;
00113 inline bool operator==(const iterator& iter) const;
00114
00115 inline typename List<T>::Node* node() { return _listnode; }
00116 inline const typename List<T>::Node* node() const { return _listnode; }
00117
00118 friend class List<T>;
00119
00120 private:
00121 const List<T>* _list;
00122 const typename List<T>::Node* _listnode;
00123 };
00124
00125
00127 class iterator {
00128 public:
00129 iterator(List<T>* const list);
00130
00131 inline T& operator*();
00132 inline T* operator->();
00133 inline iterator& operator++();
00134 inline bool operator!=(const iterator& iter) const;
00135 inline bool operator!=(const const_iterator& iter) const;
00136 inline bool operator==(const iterator& iter) const;
00137 inline bool operator==(const const_iterator& iter) const;
00138
00139 friend class List<T>;
00140 friend class List<T>::const_iterator;
00141
00142 private:
00143 const List<T>* _list;
00144 typename List<T>::Node* _listnode;
00145 };
00146
00147 void chop_front(List<T>& front, size_t front_size, Node* new_head);
00148
00149 Node* erase(const iterator iter);
00150
00151 iterator find(const T& val);
00152
00153 iterator begin();
00154 const_iterator begin() const;
00155 const iterator end() const;
00156
00157 T& front() { return *begin(); }
00158 const T& front() const { return *begin(); }
00159
00160 Node* head() { return _head.get(); }
00161 const Node* head() const { return _head.get(); }
00162
00163 private:
00164 AtomicPtr<Node> _head;
00165 AtomicPtr<Node> _tail;
00166 AtomicInt _size;
00167 iterator _end_iter;
00168 const_iterator _const_end_iter;
00169 };
00170
00171
00172 }
00173
00174 #endif // RAUL_LIST_HPP
00175
00176 #include "ListImpl.hpp"
00177