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