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 assert(size() == orig_size + range.size());
00245 #ifdef TABLE_SORT_DEBUG
00246 assert(is_sorted());
00247 #endif
00248
00249 return make_pair(iterator(*this, insert_index), true);
00250 }
00251
00252
00260 template <typename K, typename T>
00261 std::pair<typename Table<K,T>::iterator, bool>
00262 Table<K,T>::insert(const std::pair<K, T>& entry)
00263 {
00264 const K& key = entry.first;
00265 const T& value = entry.second;
00266
00267 if (size() == 0 || (size() == 1 && _entries[0].first < key)) {
00268 _entries.push_back(entry);
00269 return std::make_pair(iterator(*this, size()-1), true);
00270 } else if (size() == 1) {
00271 _entries.push_back(_entries[0]);
00272 _entries[0] = entry;
00273 return std::make_pair(begin(), true);
00274 }
00275
00276 size_t lower = 0;
00277 size_t upper = size() - 1;
00278 size_t i;
00279
00280
00281 while (upper >= lower) {
00282 i = lower + ((upper - lower) / 2);
00283 assert(i >= lower);
00284 assert(i <= upper);
00285 assert(_entries[lower].first <= _entries[i].first);
00286 assert(_entries[i].first <= _entries[upper].first);
00287
00288 assert(i < size());
00289 Entry& elem = _entries[i];
00290
00291 if (elem.first == key) {
00292 elem.second = value;
00293 return std::make_pair(iterator(*this, i), false);
00294 } else if (key < elem.first) {
00295 if (i == 0 || _entries[i-1].first < key)
00296 break;
00297 upper = i - 1;
00298 } else {
00299 lower = i + 1;
00300 }
00301 }
00302
00303
00304 if (i < size() && _entries[i].first <= key)
00305 ++i;
00306
00307 _entries.push_back(_entries.back());
00308
00309
00310 for (size_t j = size()-2; j > i; --j)
00311 _entries[j] = _entries[j-1];
00312
00313 _entries[i] = entry;
00314
00315 #ifdef TABLE_SORT_DEBUG
00316 assert(is_sorted());
00317 #endif
00318
00319 return std::make_pair(iterator(*this, i), true);
00320 }
00321
00322
00331 template <typename K, typename T>
00332 T&
00333 Table<K, T>::operator[](const K& key)
00334 {
00335 iterator i = find(key);
00336 if (i != end()) {
00337 return i->second;
00338 } else {
00339 std::pair<iterator,bool> ret = insert(make_pair(key, T()));
00340 return ret.first->second;
00341 }
00342 }
00343
00344
00345 template <typename K, typename T>
00346 void
00347 Table<K,T>::erase(const K& key)
00348 {
00349 erase(find(key));
00350 }
00351
00352
00353 template <typename K, typename T>
00354 void
00355 Table<K,T>::erase(iterator i)
00356 {
00357 if (i == end())
00358 return;
00359
00360 const size_t index = i._index;
00361
00362
00363 for (size_t j=index; j < size()-1; ++j)
00364 _entries[j] = _entries[j+1];
00365
00366 _entries.pop_back();
00367
00368 #ifdef TABLE_SORT_DEBUG
00369 assert(is_sorted());
00370 #endif
00371 }
00372
00373
00377 template <typename K, typename T>
00378 void
00379 Table<K,T>::erase(iterator first, iterator last)
00380 {
00381 const size_t first_index = first._index;
00382 const size_t last_index = last._index;
00383
00384 Table<K,T>::erase_by_index(first_index, last_index);
00385 }
00386
00387
00391 template <typename K, typename T>
00392 void
00393 Table<K,T>::erase_by_index(size_t first_index, size_t last_index)
00394 {
00395 const size_t num_removed = last_index - first_index;
00396
00397
00398 for (size_t j=first_index; j < size() - num_removed; ++j)
00399 _entries[j] = _entries[j + num_removed];
00400
00401 _entries.resize(size() - num_removed);
00402
00403 #ifdef TABLE_SORT_DEBUG
00404 assert(is_sorted());
00405 #endif
00406 }
00407
00408
00409 }
00410
00411 #endif // RAUL_TABLE_IMLP_HPP
00412