RAUL 0.8.0

- 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
    00024 #include <boost/utility.hpp>
    00025
    00026 #include "raul/AtomicInt.hpp"
    00027 #include "raul/AtomicPtr.hpp"
    00028 #include "raul/Deletable.hpp"
    00029
    00030 namespace Raul {
    00031
    00032
    00040 template <typename T>
    00041 class List : public Raul::Deletable, public boost::noncopyable
    00042 {
    00043 public:
    00044
    00051     class Node : public Raul::Deletable {
    00052     public:
    00053         explicit Node(T elem) : _elem(elem) {}
    00054         virtual ~Node() {}
    00055
    00056         template <typename Y>
    00057         explicit Node(const typename List<Y>::Node& copy)
    00058             : _elem(copy._elem), _prev(copy._prev), _next(copy._next)
    00059         {}
    00060
    00061         Node*     prev() const   { return _prev.get(); }
    00062         void      prev(Node* ln) { _prev = ln; }
    00063         Node*     next() const   { return _next.get(); }
    00064         void      next(Node* ln) { _next = ln; }
    00065         T&        elem()         { return _elem;}
    00066         const T&  elem() const   { return _elem; }
    00067
    00068     private:
    00069         T               _elem;
    00070         AtomicPtr<Node> _prev;
    00071         AtomicPtr<Node> _next;
    00072     };
    00073
    00074
    00075     List(size_t size=0, Node* head=NULL, Node* tail=NULL)
    00076         : _size(size)
    00077         , _end_iter(this)
    00078         , _const_end_iter(this)
    00079     {
    00080         _head = head;
    00081         _tail = tail;
    00082         _end_iter._listnode = NULL;
    00083         _const_end_iter._listnode = NULL;
    00084     }
    00085
    00086     ~List();
    00087
    00088     void push_back(Node* elem);
    00089     void push_back(T& elem);
    00090
    00091     void append(List<T>& list);
    00092
    00093     void clear();
    00094
    00096     unsigned size() const { return static_cast<unsigned>(_size.get()); }
    00097
    00099     bool empty() { return (_head.get() == NULL); }
    00100
    00101     class iterator;
    00102
    00104     class const_iterator {
    00105     public:
    00106         explicit const_iterator(const List<T>* const list);
    00107         const_iterator(const iterator& i)
    00108         : _list(i._list), _listnode(i._listnode) {}
    00109
    00110         inline const T&        operator*();
    00111         inline const T*        operator->();
    00112         inline const_iterator& operator++();
    00113         inline bool            operator!=(const const_iterator& iter) const;
    00114         inline bool            operator!=(const iterator& iter) const;
    00115         inline bool            operator==(const const_iterator& iter) const;
    00116         inline bool            operator==(const iterator& iter) const;
    00117
    00118         inline       typename List<T>::Node* node()       { return _listnode; }
    00119         inline const typename List<T>::Node* node() const { return _listnode; }
    00120
    00121         friend class List<T>;
    00122
    00123     private:
    00124         const List<T>*                _list;
    00125         const typename List<T>::Node* _listnode;
    00126     };
    00127
    00128
    00130     class iterator {
    00131     public:
    00132         explicit iterator(List<T>* const list);
    00133
    00134         inline T&        operator*();
    00135         inline T*        operator->();
    00136         inline iterator& operator++();
    00137         inline bool      operator!=(const iterator& iter) const;
    00138         inline bool      operator!=(const const_iterator& iter) const;
    00139         inline bool      operator==(const iterator& iter) const;
    00140         inline bool      operator==(const const_iterator& iter) const;
    00141
    00142         friend class List<T>;
    00143         friend class List<T>::const_iterator;
    00144
    00145     private:
    00146         const List<T>*          _list;
    00147         typename List<T>::Node* _listnode;
    00148     };
    00149
    00150     void chop_front(List<T>& front, size_t front_size, Node* front_tail);
    00151
    00152     Node* erase(const iterator iter);
    00153
    00154     iterator find(const T& val);
    00155
    00156     iterator       begin();
    00157     const_iterator begin() const;
    00158     const iterator end()   const;
    00159
    00160     T&       front()       { return *begin(); }
    00161     const T& front() const { return *begin(); }
    00162
    00163     Node*       head()       { return _head.get(); }
    00164     const Node* head() const { return _head.get(); }
    00165
    00166 private:
    00167     AtomicPtr<Node> _head;
    00168     AtomicPtr<Node> _tail;
    00169     AtomicInt       _size;
    00170     iterator        _end_iter;
    00171     const_iterator  _const_end_iter;
    00172 };
    00173
    00174
    00175 } // namespace Raul
    00176
    00177 #endif // RAUL_LIST_HPP
    00178
    00179 #include "ListImpl.hpp"
    00180