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