RAUL  0.8.0
TableImpl.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_IMPL_HPP
19 #define RAUL_TABLE_IMPL_HPP
20 
21 #include <algorithm>
22 #include <cassert>
23 #include <iostream>
24 #include <stdexcept>
25 #include <utility>
26 #include <vector>
27 
28 #include "raul/Table.hpp"
29 
30 namespace Raul {
31 
32 /* FIXME: This could be a lot less code... */
33 
34 #ifdef TABLE_SORT_DEBUG
35 template <typename K, typename T>
36 bool
37 Table<K,T>::is_sorted() const
38 {
39  if (size() <= 1)
40  return true;
41 
42  K prev_key = _entries[0].first;
43 
44  for (size_t i=1; i < size(); ++i)
45  if (_entries[i].first < prev_key)
46  return false;
47  else
48  prev_key = _entries[i].first;
49 
50  return true;
51 }
52 #endif
53 
54 
56 template <typename K, typename T>
57 typename Table<K,T>::const_iterator
58 Table<K,T>::find(const K& key) const
59 {
60  return ((Table<K,T>*)this)->find(key);
61 }
62 
63 
65 template <typename K, typename T>
66 typename Table<K,T>::iterator
67 Table<K,T>::find(const K& key)
68 {
69  return find(begin(), end(), key);
70 }
71 
72 
74 template <typename K, typename T>
76 Table<K,T>::find(const_iterator start, const_iterator finish, const K& key) const
77 {
78  return ((Table<K,T>*)this)->find(start, finish, key);
79 }
80 
81 
83 template <typename K, typename T>
84 typename Table<K,T>::iterator
85 Table<K,T>::find(const_iterator start, const_iterator finish, const K& key)
86 {
87  if (size() == 0)
88  return end();
89 
90  size_t lower = start._index;
91  size_t upper = finish._index - 1;
92  size_t i;
93 
94  while (upper >= lower) {
95  i = lower + ((upper - lower) / 2);
96  const Entry& elem = _entries[i];
97 
98  if (elem.first == key)
99  return iterator(*this, i);
100  else if (i < size()-1 && elem.first < key)
101  lower = i + 1;
102  else if (i > 0)
103  upper = i - 1;
104  else
105  break;
106  }
107 
108  return end();
109 }
110 
111 
124 template <typename K, typename T>
126 Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)) const
127 {
128  return (const_cast<Table<K, T>&>(*this)).find_range_end(*((iterator*)&start), comp);
129 }
130 
131 
144 template <typename K, typename T>
145 typename Table<K,T>::iterator
146 Table<K,T>::find_range_end(iterator start, bool (*comp)(const K&,const K&))
147 {
148  if (size() == 0 || start == end())
149  return this->end();
150 
151  const K& key = start->first;
152 
153  size_t lower = start._index;
154  size_t upper = size() - 1;
155 
156  if (lower == upper) {
157  if (comp(key, _entries[lower].first))
158  return iterator(*this, lower+1);
159  else
160  return this->end();
161  }
162 
163  size_t i;
164 
165  while (upper > lower) {
166 
167  i = lower + ((upper - lower) / 2);
168 
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);
174  }
175 
176  const Entry& elem = _entries[i];
177 
178  // Hit
179  if (comp(key, elem.first)) {
180 
181  if (i == size()-1 || !comp(key, _entries[i+1].first))
182  return iterator(*this, i+1);
183  else
184  lower = i;
185 
186  // Miss
187  } else {
188 
189  upper = i;
190 
191  }
192  }
193 
194  assert(comp(start->first, _entries[lower].first));
195  assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
196 
197  return iterator(*this, lower+1);
198 }
199 
200 
202 template <typename K, typename T>
203 SharedPtr< Table<K, T> >
204 Table<K, T>::yank(iterator start, iterator end)
205 {
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];
209  erase(start, end);
210  return ret;
211 }
212 
213 
217 template <typename K, typename T>
218 std::pair<typename Table<K,T>::iterator, bool>
220 {
221  /* FIXME: _way_ too slow */
222 
223  const size_t orig_size = size();
224 
225  if (range.size() == 0)
226  return std::make_pair(end(), false);
227 
228  std::pair<iterator, bool> ret = insert(range._entries.front());
229  if (range.size() == 1)
230  return ret;
231 
232  const size_t insert_index = ret.first._index;
233 
234  std::vector<Entry> new_entries(orig_size + range.size());
235 
236  for (size_t i=0; i <= insert_index; ++i)
237  new_entries.at(i) = _entries.at(i);
238 
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);
241 
242  for (size_t i=1; i < range.size(); ++i)
243  new_entries.at(insert_index + i) = range._entries.at(i);
244 
245  _entries = new_entries;
246 
247  assert(size() == orig_size + range.size());
248 #ifdef TABLE_SORT_DEBUG
249  assert(is_sorted());
250 #endif
251 
252  return make_pair(iterator(*this, insert_index), true);
253 }
254 
255 
263 template <typename K, typename T>
264 std::pair<typename Table<K,T>::iterator, bool>
265 Table<K,T>::insert(const std::pair<K, T>& entry)
266 {
267  const K& key = entry.first;
268  const T& value = entry.second;
269 
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]);
275  _entries[0] = entry;
276  return std::make_pair(begin(), true);
277  }
278 
279  size_t lower = 0;
280  size_t upper = size() - 1;
281  size_t i;
282 
283  // Find the earliest element > key
284  while (upper >= lower) {
285  i = lower + ((upper - lower) / 2);
286  assert(i >= lower);
287  assert(i <= upper);
288  assert(_entries[lower].first <= _entries[i].first);
289  assert(_entries[i].first <= _entries[upper].first);
290 
291  assert(i < size());
292  Entry& elem = _entries[i];
293 
294  if (elem.first == key) {
295  elem.second = value;
296  return std::make_pair(iterator(*this, i), false);
297  } else if (key < elem.first) {
298  if (i == 0 || _entries[i-1].first < key)
299  break;
300  upper = i - 1;
301  } else {
302  lower = i + 1;
303  }
304  }
305 
306  // Lil' off by one touchup :)
307  if (i < size() && _entries[i].first <= key)
308  ++i;
309 
310  _entries.push_back(_entries.back());
311 
312  // Shift everything beyond i right
313  for (size_t j = size()-2; j > i; --j)
314  _entries[j] = _entries[j-1];
315 
316  _entries[i] = entry;
317 
318 #ifdef TABLE_SORT_DEBUG
319  assert(is_sorted());
320 #endif
321 
322  return std::make_pair(iterator(*this, i), true);
323 }
324 
325 
334 template <typename K, typename T>
335 T&
337 {
338  iterator i = find(key);
339  if (i != end()) {
340  return i->second;
341  } else {
342  std::pair<iterator,bool> ret = insert(make_pair(key, T()));
343  return ret.first->second;
344  }
345 }
346 
347 
348 template <typename K, typename T>
349 void
350 Table<K,T>::erase(const K& key)
351 {
352  erase(find(key));
353 }
354 
355 
356 template <typename K, typename T>
357 void
358 Table<K,T>::erase(iterator i)
359 {
360  if (i == end())
361  return;
362 
363  const size_t index = i._index;
364 
365  // Shift left
366  for (size_t j=index; j < size()-1; ++j)
367  _entries[j] = _entries[j+1];
368 
369  _entries.pop_back();
370 
371 #ifdef TABLE_SORT_DEBUG
372  assert(is_sorted());
373 #endif
374 }
375 
376 
380 template <typename K, typename T>
381 void
382 Table<K,T>::erase(iterator first, iterator last)
383 {
384  const size_t first_index = first._index;
385  const size_t last_index = last._index;
386 
387  Table<K,T>::erase_by_index(first_index, last_index);
388 }
389 
390 
394 template <typename K, typename T>
395 void
396 Table<K,T>::erase_by_index(size_t first_index, size_t last_index)
397 {
398  const size_t num_removed = last_index - first_index;
399 
400  // Shift left
401  for (size_t j=first_index; j < size() - num_removed; ++j)
402  _entries[j] = _entries[j + num_removed];
403 
404  _entries.resize(size() - num_removed);
405 
406 #ifdef TABLE_SORT_DEBUG
407  assert(is_sorted());
408 #endif
409 }
410 
411 
412 } // namespace Raul
413 
414 #endif // RAUL_TABLE_IMLP_HPP
415 
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