RAUL 0.8.0

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List

TableImpl.hpp

    00001 /* This file is part of Raul.
    00002  * Copyright (C) 2007-2009 David Robillard <http://drobilla.net>
    00003  *
    00004  * Raul is free software; you can redistribute it and/or modify it under the
    00005  * terms of the GNU General Public License as published by the Free Software
    00006  * Foundation; either version 2 of the License, or (at your option) any later
    00007  * version.
    00008  *
    00009  * Raul is distributed in the hope that it will be useful, but WITHOUT ANY
    00010  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    00011  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for details.
    00012  *
    00013  * You should have received a copy of the GNU General Public License along
    00014  * with this program; if not, write to the Free Software Foundation, Inc.,
    00015  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
    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 /* FIXME: This could be a lot less code... */
    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         // Hit
    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         // Miss
    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     /* FIXME: _way_ too slow */
    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     // Find the earliest element > key
    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     // Lil' off by one touchup :)
    00307     if (i < size() && _entries[i].first <= key)
    00308         ++i;
    00309
    00310     _entries.push_back(_entries.back());
    00311
    00312     // Shift everything beyond i right
    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     // Shift left
    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     // Shift left
    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 } // namespace Raul
    00413
    00414 #endif // RAUL_TABLE_IMLP_HPP
    00415