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(0), _end_iter(this), _const_end_iter(this) {
00073 _end_iter._listnode = NULL;
00074 _const_end_iter._listnode = NULL;
00075 }
00076
00077 ~List();
00078
00079 void push_back(Node* elem);
00080 void push_back(T& elem);
00081
00082 void append(List<T>& list);
00083
00084 void clear();
00085
00087 unsigned size() const { return (unsigned)_size.get(); }
00088
00090 bool empty() { return (_head.get() == NULL); }
00091
00092 class iterator;
00093
00095 class const_iterator {
00096 public:
00097 const_iterator(const List<T>* const list);
00098 const_iterator(const iterator& i)
00099 : _list(i._list), _listnode(i._listnode) {}
00100
00101 inline const T& operator*();
00102 inline const T* operator->();
00103 inline const_iterator& operator++();
00104 inline bool operator!=(const const_iterator& iter) const;
00105 inline bool operator!=(const iterator& iter) const;
00106 inline bool operator==(const const_iterator& iter) const;
00107 inline bool operator==(const iterator& iter) const;
00108
00109 friend class List<T>;
00110
00111 private:
00112 const List<T>* _list;
00113 const typename List<T>::Node* _listnode;
00114 };
00115
00116
00118 class iterator {
00119 public:
00120 iterator(List<T>* const list);
00121
00122 inline T& operator*();
00123 inline T* operator->();
00124 inline iterator& operator++();
00125 inline bool operator!=(const iterator& iter) const;
00126 inline bool operator!=(const const_iterator& iter) const;
00127 inline bool operator==(const iterator& iter) const;
00128 inline bool operator==(const const_iterator& iter) const;
00129
00130 friend class List<T>;
00131 friend class List<T>::const_iterator;
00132
00133 private:
00134 const List<T>* _list;
00135 typename List<T>::Node* _listnode;
00136 };
00137
00138
00139 Node* erase(const iterator iter);
00140
00141 iterator find(const T& val);
00142
00143 iterator begin();
00144 const_iterator begin() const;
00145 const iterator end() const;
00146
00147 private:
00148 AtomicPtr<Node> _head;
00149 AtomicPtr<Node> _tail;
00150 AtomicInt _size;
00151 iterator _end_iter;
00152 const_iterator _const_end_iter;
00153 };
00154
00155
00156 }
00157
00158 #include "ListImpl.hpp"
00159
00160 #endif