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