18 #ifndef RAUL_TABLE_IMPL_HPP
19 #define RAUL_TABLE_IMPL_HPP
25 #include <raul/Table.hpp>
31 #ifdef TABLE_SORT_DEBUG
32 template <
typename K,
typename T>
34 Table<K,T>::is_sorted()
const
39 K prev_key = _entries[0].first;
41 for (
size_t i=1; i < size(); ++i)
42 if (_entries[i].first < prev_key)
45 prev_key = _entries[i].first;
53 template <
typename K,
typename T>
54 typename Table<K,T>::const_iterator
62 template <
typename K,
typename T>
66 return find(begin(), end(), key);
71 template <
typename K,
typename T>
75 return ((
Table<K,T>*)
this)->find(start, finish, key);
80 template <
typename K,
typename T>
87 size_t lower = start._index;
88 size_t upper = finish._index - 1;
91 while (upper >= lower) {
92 i = lower + ((upper - lower) / 2);
93 const Entry& elem = _entries[i];
95 if (elem.first == key)
96 return iterator(*
this, i);
97 else if (i < size()-1 && elem.first < key)
121 template <
typename K,
typename T>
125 return (
const_cast<Table<K, T>&
>(*
this)).find_range_end(*((iterator*)&start), comp);
141 template <
typename K,
typename T>
145 if (size() == 0 || start == end())
148 const K& key = start->first;
150 size_t lower = start._index;
151 size_t upper = size() - 1;
153 if (lower == upper) {
154 if (comp(key, _entries[lower].first))
155 return iterator(*
this, lower+1);
162 while (upper > lower) {
164 i = lower + ((upper - lower) / 2);
166 if (upper - lower == 1) {
167 if (comp(key, _entries[upper].first) && upper < size())
168 return iterator(*
this, upper+1);
169 else if (lower < size())
170 return iterator(*
this, lower+1);
173 const Entry& elem = _entries[i];
176 if (comp(key, elem.first)) {
178 if (i == size()-1 || !comp(key, _entries[i+1].first))
179 return iterator(*
this, i+1);
191 assert(comp(start->first, _entries[lower].first));
192 assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
194 return iterator(*
this, lower+1);
199 template <
typename K,
typename T>
200 SharedPtr< Table<K, T> >
203 SharedPtr< Table<K, T> > ret(
new Table<K, T>(end._index - start._index));
204 for (
size_t i=start._index; i < end._index; ++i)
205 ret->_entries.at(i - start._index) = _entries[i];
214 template <
typename K,
typename T>
215 std::pair<typename Table<K,T>::iterator,
bool>
220 const size_t orig_size = size();
222 if (range.size() == 0)
223 return std::make_pair(end(),
false);
225 std::pair<iterator, bool> ret = insert(range._entries.front());
226 if (range.size() == 1)
229 const size_t insert_index = ret.first._index;
231 std::vector<Entry> new_entries(orig_size + range.size());
233 for (
size_t i=0; i <= insert_index; ++i)
234 new_entries.at(i) = _entries.at(i);
236 for (
size_t i=0; i < size() - insert_index; ++i)
237 new_entries.at(new_entries.size() - 1 - i) = _entries.at(size() - 1 - i);
239 for (
size_t i=1; i < range.size(); ++i)
240 new_entries.at(insert_index + i) = range._entries.at(i);
242 _entries = new_entries;
250 assert(size() == orig_size + range.size());
251 #ifdef TABLE_SORT_DEBUG
255 return make_pair(iterator(*
this, insert_index),
true);
266 template <
typename K,
typename T>
267 std::pair<typename Table<K,T>::iterator,
bool>
270 const K& key = entry.first;
271 const T& value = entry.second;
273 if (size() == 0 || (size() == 1 && key > _entries[0].first)) {
274 _entries.push_back(entry);
275 return std::make_pair(iterator(*
this, size()-1),
true);
276 }
else if (size() == 1) {
277 _entries.push_back(_entries[0]);
279 return std::make_pair(begin(),
true);
283 size_t upper = size() - 1;
287 while (upper >= lower) {
288 i = lower + ((upper - lower) / 2);
291 assert(_entries[lower].first <= _entries[i].first);
292 assert(_entries[i].first <= _entries[upper].first);
295 Entry& elem = _entries[i];
297 if (elem.first == key) {
299 return std::make_pair(iterator(*
this, i),
false);
300 }
else if (elem.first > key) {
301 if (i == 0 || _entries[i-1].first < key)
310 if (i < size() && _entries[i].first <= key)
313 _entries.push_back(_entries.back());
316 for (
size_t j = size()-2; j > i; --j)
317 _entries[j] = _entries[j-1];
321 #ifdef TABLE_SORT_DEBUG
325 return std::make_pair(iterator(*
this, i),
true);
337 template <
typename K,
typename T>
341 iterator i = find(key);
345 std::pair<iterator,bool> ret = insert(make_pair(key, T()));
346 return ret.first->second;
351 template <
typename K,
typename T>
359 template <
typename K,
typename T>
361 Table<K,T>::erase(iterator i)
366 const size_t index = i._index;
369 for (
size_t j=index; j < size()-1; ++j)
370 _entries[j] = _entries[j+1];
374 #ifdef TABLE_SORT_DEBUG
383 template <
typename K,
typename T>
387 const size_t first_index = first._index;
388 const size_t last_index = last._index;
397 template <
typename K,
typename T>
401 const size_t num_removed = last_index - first_index;
404 for (
size_t j=first_index; j < size() - num_removed; ++j)
405 _entries[j] = _entries[j + num_removed];
407 _entries.resize(size() - num_removed);
409 #ifdef TABLE_SORT_DEBUG
417 #endif // RAUL_TABLE_IMLP_HPP
SharedPtr< Table< K, T > > yank(iterator start, iterator end)
Erase and return a range of entries.
Definition: TableImpl.hpp:201
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:268
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:399
T & operator[](const K &key)
Insert an item, and return a reference to it's value.
Definition: TableImpl.hpp:339
Slow insertion, fast lookup, cache optimized, super fast sorted iteration.
Definition: Table.hpp:38
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:123
std::pair< iterator, bool > cram(const Table< K, T > &range)
Cram a range of entries back in.
Definition: TableImpl.hpp:216
const_iterator find(const_iterator start, const_iterator end, const K &key) const
Binary search (O(log(end - start)))
Definition: TableImpl.hpp:73