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 size_t i;
00160
00161 while (upper > lower) {
00162
00163 i = lower + ((upper - lower) / 2);
00164
00165 if (upper - lower == 1)
00166 if (comp(key, _entries[upper].first) && upper < size())
00167 return iterator(*this, upper+1);
00168 else if (lower < size())
00169 return iterator(*this, lower+1);
00170
00171 const Entry& elem = _entries[i];
00172
00173
00174 if (comp(key, elem.first)) {
00175
00176 if (i == size()-1 || !comp(key, _entries[i+1].first))
00177 return iterator(*this, i+1);
00178 else
00179 lower = i;
00180
00181
00182 } else {
00183
00184 upper = i;
00185
00186 }
00187 }
00188
00189 assert(comp(start->first, _entries[lower].first));
00190 assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first));
00191
00192 return iterator(*this, lower+1);
00193 }
00194
00195
00197 template <typename K, typename T>
00198 SharedPtr< Table<K, T> >
00199 Table<K, T>::yank(iterator start, iterator end)
00200 {
00201 SharedPtr< Table<K, T> > ret(new Table<K, T>(end._index - start._index));
00202 for (size_t i=start._index; i < end._index; ++i)
00203 ret->_entries.at(i - start._index) = _entries[i];
00204 erase(start, end);
00205 return ret;
00206 }
00207
00208
00212 template <typename K, typename T>
00213 std::pair<typename Table<K,T>::iterator, bool>
00214 Table<K, T>::cram(const Table<K,T>& range)
00215 {
00216
00217
00218 const size_t orig_size = size();
00219
00220 if (range.size() == 0)
00221 return std::make_pair(end(), false);
00222
00223 std::pair<iterator, bool> ret = insert(range._entries.front());
00224 if (range.size() == 1)
00225 return ret;
00226
00227 const size_t insert_index = ret.first._index;
00228
00229 std::vector<Entry> new_entries(orig_size + range.size());
00230
00231 for (size_t i=0; i <= insert_index; ++i)
00232 new_entries.at(i) = _entries.at(i);
00233
00234 for (size_t i=0; i < size() - insert_index; ++i)
00235 new_entries.at(new_entries.size() - 1 - i) = _entries.at(size() - 1 - i);
00236
00237 for (size_t i=1; i < range.size(); ++i)
00238 new_entries.at(insert_index + i) = range._entries.at(i);
00239
00240 _entries = new_entries;
00241
00242
00243
00244
00245
00246
00247
00248 assert(size() == orig_size + range.size());
00249 #ifdef TABLE_SORT_DEBUG
00250 assert(is_sorted());
00251 #endif
00252
00253 return make_pair(iterator(*this, insert_index), true);
00254 }
00255
00256
00264 template <typename K, typename T>
00265 std::pair<typename Table<K,T>::iterator, bool>
00266 Table<K,T>::insert(const std::pair<K, T>& entry)
00267 {
00268 const K& key = entry.first;
00269 const T& value = entry.second;
00270
00271 if (size() == 0 || size() == 1 && key > _entries[0].first) {
00272 _entries.push_back(entry);
00273 return std::make_pair(iterator(*this, size()-1), true);
00274 } else if (size() == 1) {
00275 _entries.push_back(_entries[0]);
00276 _entries[0] = entry;
00277 return std::make_pair(begin(), true);
00278 }
00279
00280 size_t lower = 0;
00281 size_t upper = size() - 1;
00282 size_t i;
00283
00284
00285 while (upper >= lower) {
00286 i = lower + ((upper - lower) / 2);
00287 assert(i >= lower);
00288 assert(i <= upper);
00289 assert(_entries[lower].first <= _entries[i].first);
00290 assert(_entries[i].first <= _entries[upper].first);
00291
00292 assert(i < size());
00293 Entry& elem = _entries[i];
00294
00295 if (elem.first == key) {
00296 elem.second = value;
00297 return std::make_pair(iterator(*this, i), false);
00298 } else if (elem.first > key) {
00299 if (i == 0 || _entries[i-1].first < key)
00300 break;
00301 upper = i - 1;
00302 } else {
00303 lower = i + 1;
00304 }
00305 }
00306
00307
00308 if (i < size() && _entries[i].first <= key)
00309 ++i;
00310
00311 _entries.push_back(_entries.back());
00312
00313
00314 for (size_t j = size()-2; j > i; --j)
00315 _entries[j] = _entries[j-1];
00316
00317 _entries[i] = entry;
00318
00319 #ifdef TABLE_SORT_DEBUG
00320 assert(is_sorted());
00321 #endif
00322
00323 return std::make_pair(iterator(*this, i), true);
00324 }
00325
00326
00335 template <typename K, typename T>
00336 T&
00337 Table<K, T>::operator[](const K& key)
00338 {
00339 iterator i = find(key);
00340 if (i != end()) {
00341 return i->second;
00342 } else {
00343 std::pair<iterator,bool> ret = insert(make_pair(key, T()));
00344 return ret.first->second;
00345 }
00346 }
00347
00348
00349 template <typename K, typename T>
00350 void
00351 Table<K,T>::erase(const K& key)
00352 {
00353 erase(find(key));
00354 }
00355
00356
00357 template <typename K, typename T>
00358 void
00359 Table<K,T>::erase(iterator i)
00360 {
00361 if (i == end())
00362 return;
00363
00364 const size_t index = i._index;
00365
00366
00367 for (size_t j=index; j < size()-1; ++j)
00368 _entries[j] = _entries[j+1];
00369
00370 _entries.pop_back();
00371
00372 #ifdef TABLE_SORT_DEBUG
00373 assert(is_sorted());
00374 #endif
00375 }
00376
00377
00381 template <typename K, typename T>
00382 void
00383 Table<K,T>::erase(iterator first, iterator last)
00384 {
00385 const size_t first_index = first._index;
00386 const size_t last_index = last._index;
00387
00388 Table<K,T>::erase_by_index(first_index, last_index);
00389 }
00390
00391
00395 template <typename K, typename T>
00396 void
00397 Table<K,T>::erase_by_index(size_t first_index, size_t last_index)
00398 {
00399 const size_t num_removed = last_index - first_index;
00400
00401
00402 for (size_t j=first_index; j < size() - num_removed; ++j)
00403 _entries[j] = _entries[j + num_removed];
00404
00405 _entries.resize(size() - num_removed);
00406
00407 #ifdef TABLE_SORT_DEBUG
00408 assert(is_sorted());
00409 #endif
00410 }
00411
00412
00413 }
00414
00415 #endif // RAUL_TABLE_IMLP_HPP
00416