RAUL 0.7.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 <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