00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef RAUL_TABLE_IMPL_HPP
00019 #define RAUL_TABLE_IMPL_HPP
00020
00021 #include <cassert>
00022 #include <stdexcept>
00023 #include <algorithm>
00024 #include <iostream>
00025 #include "raul/Table.hpp"
00026
00027 namespace Raul {
00028
00029
00030
00031 #ifdef TABLE_SORT_DEBUG
00032 template <typename K, typename T>
00033 bool
00034 Table<K,T>::is_sorted() const
00035 {
00036 if (size() <= 1)
00037 return true;
00038
00039 K prev_key = _entries[0].first;
00040
00041 for (size_t i=1; i < size(); ++i)
00042 if (_entries[i].first < prev_key)
00043 return false;
00044 else
00045 prev_key = _entries[i].first;
00046
00047 return true;
00048 }
00049 #endif
00050
00051
00053 template <typename K, typename T>
00054 typename Table<K,T>::const_iterator
00055 Table<K,T>::find(const K& key) const
00056 {
00057 return ((Table<K,T>*)this)->find(key);
00058 }
00059
00060
00062 template <typename K, typename T>
00063 typename Table<K,T>::iterator
00064 Table<K,T>::find(const K& key)
00065 {
00066 return find(begin(), end(), key);
00067 }
00068
00069
00071 template <typename K, typename T>
00072 typename Table<K,T>::const_iterator
00073 Table<K,T>::find(const_iterator start, const_iterator finish, const K& key) const
00074 {
00075 return ((Table<K,T>*)this)->find(start, finish, key);
00076 }
00077
00078
00080 template <typename K, typename T>
00081 typename Table<K,T>::iterator
00082 Table<K,T>::find(const_iterator start, const_iterator finish, const K& key)
00083 {
00084 if (size() == 0)
00085 return end();
00086
00087 size_t lower = start._index;
00088 size_t upper = finish._index - 1;
00089 size_t i;
00090
00091 while (upper >= lower) {
00092 i = lower + ((upper - lower) / 2);
00093 const Entry& elem = _entries[i];
00094
00095 if (elem.first == key)
00096 return iterator(*this, i);
00097 else if (i < size()-1 && elem.first < key)
00098 lower = i + 1;
00099 else if (i > 0)
00100 upper = i - 1;
00101 else
00102 break;
00103 }
00104
00105 return end();
00106 }
00107
00108
00121 template <typename K, typename T>
00122 typename Table<K,T>::const_iterator
00123 Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)) const
00124 {
00125 return (const_cast<Table<K, T>&>(*this)).find_range_end(*((iterator*)&start), comp);
00126 }
00127
00128
00141 template <typename K, typename T>
00142 typename Table<K,T>::iterator
00143 Table<K,T>::find_range_end(iterator start, bool (*comp)(const K&,const K&))
00144 {
00145 if (size() == 0 || start == end())
00146 return this->end();
00147
00148 const K& key = start->first;
00149
00150 size_t lower = start._index;
00151 size_t upper = size() - 1;
00152
00153 if (lower == upper) {
00154 if (comp(key, _entries[lower].first))
00155 return iterator(*this, lower+1);
00156 else
00157 return this->end();
00158 }
00159
00160 size_t i;
00161
00162 while (upper > lower) {
00163
00164 i = lower + ((upper - lower) / 2);
00165
00166 if (upper - lower == 1) {
00167 if (comp(key, _entries[upper].first) && upper < size())
00168 return iterator(*this, upper+1);
00169 else if (lower < size())
00170 return iterator(*this, lower+1);
00171 }
00172
00173 const Entry& elem = _entries[i];
00174
00175
00176 if (comp(key, elem.first)) {
00177
00178 if (i == size()-1 || !comp(key, _entries[i+1].first))
00179 return iterator(*this, i+1);
00180 else
00181 lower = i;
00182
00183
00184 } else {
00185
00186 upper = i;
00187
00188 }
00189 }
00190
00191 assert(comp(start->first, _entries[lower].first));
00192 assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
00193
00194 return iterator(*this, lower+1);
00195 }
00196
00197
00199 template <typename K, typename T>
00200 SharedPtr< Table<K, T> >
00201 Table<K, T>::yank(iterator start, iterator end)
00202 {
00203 SharedPtr< Table<K, T> > ret(new Table<K, T>(end._index - start._index));
00204 for (size_t i=start._index; i < end._index; ++i)
00205 ret->_entries.at(i - start._index) = _entries[i];
00206 erase(start, end);
00207 return ret;
00208 }
00209
00210
00214 template <typename K, typename T>
00215 std::pair<typename Table<K,T>::iterator, bool>
00216 Table<K, T>::cram(const Table<K,T>& range)
00217 {
00218
00219
00220 const size_t orig_size = size();
00221
00222 if (range.size() == 0)
00223 return std::make_pair(end(), false);
00224
00225 std::pair<iterator, bool> ret = insert(range._entries.front());
00226 if (range.size() == 1)
00227 return ret;
00228
00229 const size_t insert_index = ret.first._index;
00230
00231 std::vector<Entry> new_entries(orig_size + range.size());
00232
00233 for (size_t i=0; i <= insert_index; ++i)
00234 new_entries.at(i) = _entries.at(i);
00235
00236 for (size_t i=0; i < size() - insert_index; ++i)
00237 new_entries.at(new_entries.size() - 1 - i) = _entries.at(size() - 1 - i);
00238
00239 for (size_t i=1; i < range.size(); ++i)
00240 new_entries.at(insert_index + i) = range._entries.at(i);
00241
00242 _entries = new_entries;
00243
00244
00245
00246
00247
00248
00249
00250 assert(size() == orig_size + range.size());
00251 #ifdef TABLE_SORT_DEBUG
00252 assert(is_sorted());
00253 #endif
00254
00255 return make_pair(iterator(*this, insert_index), true);
00256 }
00257
00258
00266 template <typename K, typename T>
00267 std::pair<typename Table<K,T>::iterator, bool>
00268 Table<K,T>::insert(const std::pair<K, T>& entry)
00269 {
00270 const K& key = entry.first;
00271 const T& value = entry.second;
00272
00273 if (size() == 0 || (size() == 1 && key > _entries[0].first)) {
00274 _entries.push_back(entry);
00275 return std::make_pair(iterator(*this, size()-1), true);
00276 } else if (size() == 1) {
00277 _entries.push_back(_entries[0]);
00278 _entries[0] = entry;
00279 return std::make_pair(begin(), true);
00280 }
00281
00282 size_t lower = 0;
00283 size_t upper = size() - 1;
00284 size_t i;
00285
00286
00287 while (upper >= lower) {
00288 i = lower + ((upper - lower) / 2);
00289 assert(i >= lower);
00290 assert(i <= upper);
00291 assert(_entries[lower].first <= _entries[i].first);
00292 assert(_entries[i].first <= _entries[upper].first);
00293
00294 assert(i < size());
00295 Entry& elem = _entries[i];
00296
00297 if (elem.first == key) {
00298 elem.second = value;
00299 return std::make_pair(iterator(*this, i), false);
00300 } else if (elem.first > key) {
00301 if (i == 0 || _entries[i-1].first < key)
00302 break;
00303 upper = i - 1;
00304 } else {
00305 lower = i + 1;
00306 }
00307 }
00308
00309
00310 if (i < size() && _entries[i].first <= key)
00311 ++i;
00312
00313 _entries.push_back(_entries.back());
00314
00315
00316 for (size_t j = size()-2; j > i; --j)
00317 _entries[j] = _entries[j-1];
00318
00319 _entries[i] = entry;
00320
00321 #ifdef TABLE_SORT_DEBUG
00322 assert(is_sorted());
00323 #endif
00324
00325 return std::make_pair(iterator(*this, i), true);
00326 }
00327
00328
00337 template <typename K, typename T>
00338 T&
00339 Table<K, T>::operator[](const K& key)
00340 {
00341 iterator i = find(key);
00342 if (i != end()) {
00343 return i->second;
00344 } else {
00345 std::pair<iterator,bool> ret = insert(make_pair(key, T()));
00346 return ret.first->second;
00347 }
00348 }
00349
00350
00351 template <typename K, typename T>
00352 void
00353 Table<K,T>::erase(const K& key)
00354 {
00355 erase(find(key));
00356 }
00357
00358
00359 template <typename K, typename T>
00360 void
00361 Table<K,T>::erase(iterator i)
00362 {
00363 if (i == end())
00364 return;
00365
00366 const size_t index = i._index;
00367
00368
00369 for (size_t j=index; j < size()-1; ++j)
00370 _entries[j] = _entries[j+1];
00371
00372 _entries.pop_back();
00373
00374 #ifdef TABLE_SORT_DEBUG
00375 assert(is_sorted());
00376 #endif
00377 }
00378
00379
00383 template <typename K, typename T>
00384 void
00385 Table<K,T>::erase(iterator first, iterator last)
00386 {
00387 const size_t first_index = first._index;
00388 const size_t last_index = last._index;
00389
00390 Table<K,T>::erase_by_index(first_index, last_index);
00391 }
00392
00393
00397 template <typename K, typename T>
00398 void
00399 Table<K,T>::erase_by_index(size_t first_index, size_t last_index)
00400 {
00401 const size_t num_removed = last_index - first_index;
00402
00403
00404 for (size_t j=first_index; j < size() - num_removed; ++j)
00405 _entries[j] = _entries[j + num_removed];
00406
00407 _entries.resize(size() - num_removed);
00408
00409 #ifdef TABLE_SORT_DEBUG
00410 assert(is_sorted());
00411 #endif
00412 }
00413
00414
00415 }
00416
00417 #endif // RAUL_TABLE_IMLP_HPP
00418