• Main Page
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List

List.hpp

00001 /* This file is part of Raul.
00002  * Copyright (C) 2007-2009 David Robillard <http://drobilla.net>
00003  *
00004  * Raul is free software; you can redistribute it and/or modify it under the
00005  * terms of the GNU General Public License as published by the Free Software
00006  * Foundation; either version 2 of the License, or (at your option) any later
00007  * version.
00008  *
00009  * Raul is distributed in the hope that it will be useful, but WITHOUT ANY
00010  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00011  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for details.
00012  *
00013  * You should have received a copy of the GNU General Public License along
00014  * with this program; if not, write to the Free Software Foundation, Inc.,
00015  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
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 static_cast<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 } // namespace Raul
00173 
00174 #endif // RAUL_LIST_HPP
00175 
00176 #include "ListImpl.hpp"
00177 

Generated on Sun Sep 12 2010 for RAUL by  doxygen 1.7.1