RAUL 0.7.0

Table.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_TABLE_HPP
00019 #define RAUL_TABLE_HPP
00020 
00021 #include <vector>
00022 #include <algorithm>
00023 #include <boost/utility.hpp>
00024 #include "SharedPtr.hpp"
00025 
00026 //#define TABLE_SORT_DEBUG
00027 
00028 namespace Raul {
00029 
00030 
00037 template <typename K, typename T>
00038 class Table : public boost::noncopyable {
00039 public:
00040     Table<K, T>() : _entries() {}
00041     Table<K, T>(size_t capacity) : _entries(capacity) {}
00042 
00043     void clear() { _entries.clear(); }
00044     bool empty() const { return _entries.empty(); }
00045     void reserve(size_t n) { _entries.reserve(n); }
00046 
00047     struct const_iterator {
00048         const_iterator(const Table<K,T>& t, size_t i) : _table(&t), _index(i) {}
00049         inline const std::pair<const K, T> operator*() const { return _table->_entries[_index]; }
00050         inline const std::pair<const K, T>* operator->() const { return (std::pair<const K, T>*)&_table->_entries[_index]; }
00051         inline const_iterator& operator++() { ++_index; return *this; }
00052         inline const_iterator& operator--() { --_index; return *this; }
00053         inline bool operator==(const const_iterator& i) const { return _index == i._index; }
00054         inline bool operator!=(const const_iterator& i) const { return _index != i._index; }
00055         void operator=(const const_iterator& i) { _table = i._table; _index = i._index; }
00056     private:
00057         friend class Table<K,T>;
00058         const Table<K,T>* _table;
00059         size_t _index;
00060     };
00061 
00062     struct iterator {
00063         iterator(Table<K,T>& t, size_t i) : _table(&t), _index(i) {}
00064         inline std::pair<K, T>& operator*() const { return (std::pair<K, T>&)_table->_entries[_index]; }
00065         inline std::pair<K, T>* operator->() const { return (std::pair<K, T>*)&_table->_entries[_index]; }
00066         inline iterator& operator++() { ++_index; return *this; }
00067         inline iterator& operator--() { --_index; return *this; }
00068         inline bool operator==(const iterator& i) const { return _index == i._index; }
00069         inline bool operator!=(const iterator& i) const { return _index != i._index; }
00070         operator const_iterator() { return *(const_iterator*)this; }
00071         iterator& operator=(const iterator& i) { _table = i._table; _index = i._index; return *this; }
00072     private:
00073         friend class Table<K,T>;
00074         Table<K,T>* _table;
00075         size_t _index;
00076     };
00077 
00078     inline size_t size() const { return _entries.size(); }
00079 
00080     std::pair<iterator,bool> insert(const std::pair<K, T>& entry);
00081 
00082     void erase(const K& key);
00083     void erase(iterator i);
00084     void erase(iterator start, iterator end);
00085     void erase_by_index(size_t start, size_t end);
00086 
00087     SharedPtr< Table<K, T> > yank(iterator start, iterator end);
00088 
00089     std::pair<iterator, bool> cram(const Table<K, T>& range);
00090 
00091     const_iterator find(const_iterator start, const_iterator end, const K& key) const;
00092     const_iterator find(const K& key) const;
00093 
00094     iterator find(const_iterator start, const_iterator end, const K& key);
00095     iterator find(const K& key);
00096 
00097     const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const;
00098     iterator find_range_end(iterator left, bool (*comp)(const K&,const K&));
00099 
00100     T& operator[](const K& key);
00101 
00102     const_iterator begin() const { return const_iterator(*this, 0); }
00103     const_iterator end()   const { return const_iterator(*this, size()); }
00104     iterator       begin()       { return iterator(*this, 0); }
00105     iterator       end()         { return iterator(*this, size()); }
00106 
00107 private:
00108 #ifdef TABLE_SORT_DEBUG
00109     bool is_sorted() const;
00110 #endif
00111 
00112     friend class iterator;
00113 
00114     typedef std::pair<K, T> Entry;
00115 
00116     std::vector<Entry> _entries;
00117 };
00118 
00119 
00120 } // namespace Raul
00121 
00122 #endif // RAUL_TABLE_HPP