RAUL  0.8.0
Table.hpp
1 /* This file is part of Raul.
2  * Copyright (C) 2007-2009 David Robillard <http://drobilla.net>
3  *
4  * Raul is free software; you can redistribute it and/or modify it under the
5  * terms of the GNU General Public License as published by the Free Software
6  * Foundation; either version 2 of the License, or (at your option) any later
7  * version.
8  *
9  * Raul is distributed in the hope that it will be useful, but WITHOUT ANY
10  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.
12  *
13  * You should have received a copy of the GNU General Public License along
14  * with this program; if not, write to the Free Software Foundation, Inc.,
15  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
16  */
17 
18 #ifndef RAUL_TABLE_HPP
19 #define RAUL_TABLE_HPP
20 
21 #include <algorithm>
22 #include <utility>
23 #include <vector>
24 
25 #include <boost/utility.hpp>
26 
27 #include "raul/SharedPtr.hpp"
28 
29 //#define TABLE_SORT_DEBUG
30 
31 namespace Raul {
32 
33 
41 template <typename K, typename T>
42 class Table : public boost::noncopyable {
43 public:
44  Table<K, T>() : _entries() {}
45  Table<K, T>(size_t capacity) : _entries(capacity) {}
46 
47  void clear() { _entries.clear(); }
48  bool empty() const { return _entries.empty(); }
49  void reserve(size_t n) { _entries.reserve(n); }
50 
51  struct const_iterator {
52  const_iterator(const Table<K,T>& t, size_t i) : _table(&t), _index(i) {}
53  inline const std::pair<const K, T> operator*() const { return _table->_entries[_index]; }
54  inline const std::pair<const K, T>* operator->() const { return (std::pair<const K, T>*)&_table->_entries[_index]; }
55  inline const_iterator& operator++() { ++_index; return *this; }
56  inline const_iterator& operator--() { --_index; return *this; }
57  inline bool operator==(const const_iterator& i) const { return _index == i._index; }
58  inline bool operator!=(const const_iterator& i) const { return _index != i._index; }
59  void operator=(const const_iterator& i) { _table = i._table; _index = i._index; }
60  private:
61  friend class Table<K,T>;
62  const Table<K,T>* _table;
63  size_t _index;
64  };
65 
66  struct iterator {
67  iterator(Table<K,T>& t, size_t i) : _table(&t), _index(i) {}
68  inline std::pair<K, T>& operator*() const { return (std::pair<K, T>&)_table->_entries[_index]; }
69  inline std::pair<K, T>* operator->() const { return (std::pair<K, T>*)&_table->_entries[_index]; }
70  inline iterator& operator++() { ++_index; return *this; }
71  inline iterator& operator--() { --_index; return *this; }
72  inline bool operator==(const iterator& i) const { return _index == i._index; }
73  inline bool operator!=(const iterator& i) const { return _index != i._index; }
74  operator const_iterator() { return *(const_iterator*)this; }
75  iterator& operator=(const iterator& i) { _table = i._table; _index = i._index; return *this; }
76  private:
77  friend class Table<K,T>;
78  Table<K,T>* _table;
79  size_t _index;
80  };
81 
82  inline size_t size() const { return _entries.size(); }
83 
84  std::pair<iterator,bool> insert(const std::pair<K, T>& entry);
85 
86  void erase(const K& key);
87  void erase(iterator i);
88  void erase(iterator start, iterator end);
89  void erase_by_index(size_t start, size_t end);
90 
91  SharedPtr< Table<K, T> > yank(iterator start, iterator end);
92 
93  std::pair<iterator, bool> cram(const Table<K, T>& range);
94 
95  const_iterator find(const_iterator start, const_iterator end, const K& key) const;
96  const_iterator find(const K& key) const;
97 
98  iterator find(const_iterator start, const_iterator end, const K& key);
99  iterator find(const K& key);
100 
101  const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const;
102  iterator find_range_end(iterator left, bool (*comp)(const K&,const K&));
103 
104  T& operator[](const K& key);
105 
106  const_iterator begin() const { return const_iterator(*this, 0); }
107  const_iterator end() const { return const_iterator(*this, size()); }
108  iterator begin() { return iterator(*this, 0); }
109  iterator end() { return iterator(*this, size()); }
110 
111 private:
112 #ifdef TABLE_SORT_DEBUG
113  bool is_sorted() const;
114 #endif
115 
116  friend class iterator;
117 
118  typedef std::pair<K, T> Entry;
119 
120  std::vector<Entry> _entries;
121 };
122 
123 
124 } // namespace Raul
125 
126 #endif // RAUL_TABLE_HPP
Raul::Table::erase_by_index
void erase_by_index(size_t start, size_t end)
Erase a range of elements from first_index to last_index, including first_index but not including las...
Definition: TableImpl.hpp:396
Raul::Table
Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
Definition: Table.hpp:42
Raul::Table::find
const_iterator find(const_iterator start, const_iterator end, const K &key) const
Binary search (O(log(end - start)))
Definition: TableImpl.hpp:76
Raul::Table::find_range_end
const_iterator find_range_end(const_iterator left, bool(*comp)(const K &, const K &)) const
Find the end of a range using a custom comparator.
Definition: TableImpl.hpp:126
Raul::Table::insert
std::pair< iterator, bool > insert(const std::pair< K, T > &entry)
Add an item to the table, using entry.first as the search key.
Definition: TableImpl.hpp:265
Raul::Table::operator[]
T & operator[](const K &key)
Insert an item, and return a reference to it's value.
Definition: TableImpl.hpp:336
Raul::Table::yank
SharedPtr< Table< K, T > > yank(iterator start, iterator end)
Erase and return a range of entries.
Definition: TableImpl.hpp:204
Raul::Table::cram
std::pair< iterator, bool > cram(const Table< K, T > &range)
Cram a range of entries back in.
Definition: TableImpl.hpp:219