18 #ifndef RAUL_TABLE_IMPL_HPP
19 #define RAUL_TABLE_IMPL_HPP
28 #include "raul/Table.hpp"
34 #ifdef TABLE_SORT_DEBUG
35 template <
typename K,
typename T>
37 Table<K,T>::is_sorted()
const
42 K prev_key = _entries[0].first;
44 for (
size_t i=1; i < size(); ++i)
45 if (_entries[i].first < prev_key)
48 prev_key = _entries[i].first;
56 template <
typename K,
typename T>
57 typename Table<K,T>::const_iterator
65 template <
typename K,
typename T>
69 return find(begin(), end(), key);
74 template <
typename K,
typename T>
78 return ((
Table<K,T>*)
this)->find(start, finish, key);
83 template <
typename K,
typename T>
90 size_t lower = start._index;
91 size_t upper = finish._index - 1;
94 while (upper >= lower) {
95 i = lower + ((upper - lower) / 2);
96 const Entry& elem = _entries[i];
98 if (elem.first == key)
99 return iterator(*
this, i);
100 else if (i < size()-1 && elem.first < key)
124 template <
typename K,
typename T>
125 typename Table<K,T>::const_iterator
128 return (
const_cast<Table<K, T>&
>(*
this)).find_range_end(*((iterator*)&start), comp);
144 template <
typename K,
typename T>
148 if (size() == 0 || start == end())
151 const K& key = start->first;
153 size_t lower = start._index;
154 size_t upper = size() - 1;
156 if (lower == upper) {
157 if (comp(key, _entries[lower].first))
158 return iterator(*
this, lower+1);
165 while (upper > lower) {
167 i = lower + ((upper - lower) / 2);
169 if (upper - lower == 1) {
170 if (comp(key, _entries[upper].first) && upper < size())
171 return iterator(*
this, upper+1);
172 else if (lower < size())
173 return iterator(*
this, lower+1);
176 const Entry& elem = _entries[i];
179 if (comp(key, elem.first)) {
181 if (i == size()-1 || !comp(key, _entries[i+1].first))
182 return iterator(*
this, i+1);
194 assert(comp(start->first, _entries[lower].first));
195 assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
197 return iterator(*
this, lower+1);
202 template <
typename K,
typename T>
203 SharedPtr< Table<K, T> >
206 SharedPtr< Table<K, T> > ret(
new Table<K, T>(end._index - start._index));
207 for (
size_t i=start._index; i < end._index; ++i)
208 ret->_entries.at(i - start._index) = _entries[i];
217 template <
typename K,
typename T>
218 std::pair<typename Table<K,T>::iterator,
bool>
223 const size_t orig_size = size();
225 if (range.size() == 0)
226 return std::make_pair(end(),
false);
228 std::pair<iterator, bool> ret = insert(range._entries.front());
229 if (range.size() == 1)
232 const size_t insert_index = ret.first._index;
234 std::vector<Entry> new_entries(orig_size + range.size());
236 for (
size_t i=0; i <= insert_index; ++i)
237 new_entries.at(i) = _entries.at(i);
239 for (
size_t i=0; i < size() - insert_index; ++i)
240 new_entries.at(new_entries.size() - 1 - i) = _entries.at(size() - 1 - i);
242 for (
size_t i=1; i < range.size(); ++i)
243 new_entries.at(insert_index + i) = range._entries.at(i);
245 _entries = new_entries;
247 assert(size() == orig_size + range.size());
248 #ifdef TABLE_SORT_DEBUG
252 return make_pair(iterator(*
this, insert_index),
true);
263 template <
typename K,
typename T>
264 std::pair<typename Table<K,T>::iterator,
bool>
267 const K& key = entry.first;
268 const T& value = entry.second;
270 if (size() == 0 || (size() == 1 && _entries[0].first < key)) {
271 _entries.push_back(entry);
272 return std::make_pair(iterator(*
this, size()-1),
true);
273 }
else if (size() == 1) {
274 _entries.push_back(_entries[0]);
276 return std::make_pair(begin(),
true);
280 size_t upper = size() - 1;
284 while (upper >= lower) {
285 i = lower + ((upper - lower) / 2);
288 assert(_entries[lower].first <= _entries[i].first);
289 assert(_entries[i].first <= _entries[upper].first);
292 Entry& elem = _entries[i];
294 if (elem.first == key) {
296 return std::make_pair(iterator(*
this, i),
false);
297 }
else if (key < elem.first) {
298 if (i == 0 || _entries[i-1].first < key)
307 if (i < size() && _entries[i].first <= key)
310 _entries.push_back(_entries.back());
313 for (
size_t j = size()-2; j > i; --j)
314 _entries[j] = _entries[j-1];
318 #ifdef TABLE_SORT_DEBUG
322 return std::make_pair(iterator(*
this, i),
true);
334 template <
typename K,
typename T>
338 iterator i = find(key);
342 std::pair<iterator,bool> ret = insert(make_pair(key, T()));
343 return ret.first->second;
348 template <
typename K,
typename T>
356 template <
typename K,
typename T>
358 Table<K,T>::erase(iterator i)
363 const size_t index = i._index;
366 for (
size_t j=index; j < size()-1; ++j)
367 _entries[j] = _entries[j+1];
371 #ifdef TABLE_SORT_DEBUG
380 template <
typename K,
typename T>
384 const size_t first_index = first._index;
385 const size_t last_index = last._index;
394 template <
typename K,
typename T>
398 const size_t num_removed = last_index - first_index;
401 for (
size_t j=first_index; j < size() - num_removed; ++j)
402 _entries[j] = _entries[j + num_removed];
404 _entries.resize(size() - num_removed);
406 #ifdef TABLE_SORT_DEBUG
Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
Definition: Table.hpp:42
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
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
SharedPtr< Table< K, T > > yank(iterator start, iterator end)
Erase and return a range of entries.
Definition: TableImpl.hpp:204
const_iterator find(const_iterator start, const_iterator end, const K &key) const
Binary search (O(log(end - start)))
Definition: TableImpl.hpp:76
std::pair< iterator, bool > cram(const Table< K, T > &range)
Cram a range of entries back in.
Definition: TableImpl.hpp:219
T & operator[](const K &key)
Insert an item, and return a reference to it's value.
Definition: TableImpl.hpp:336
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