• 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 <cassert>
00022 #include <stdexcept>
00023 #include <algorithm>
00024 #include <iostream>
00025 #include "raul/Table.hpp"
00026 
00027 namespace Raul {
00028 
00029 /* FIXME: This could be a lot less code... */
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         // Hit
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         // Miss
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     /* FIXME: _way_ too slow */
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     // Find the earliest element > key
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     // Lil' off by one touchup :)
00304     if (i < size() && _entries[i].first <= key)
00305         ++i;
00306 
00307     _entries.push_back(_entries.back());
00308 
00309     // Shift everything beyond i right
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     // Shift left
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     // Shift left
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 } // namespace Raul
00410 
00411 #endif // RAUL_TABLE_IMLP_HPP
00412 

Generated on Sun Sep 12 2010 for RAUL by  doxygen 1.7.1