/builddir/build/BUILD/raul-0.4.0/raul/TableImpl.hpp

00001 /* This file is part of Raul.
00002  * Copyright (C) 2007 Dave 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     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         // Hit
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         // Miss
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     /* FIXME: _way_ too slow */
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     /*std::cerr << "********************************\n";
00243     for (size_t i=0; i < size(); ++i) {
00244         std::cerr << _entries[i].first << std::endl;
00245     }
00246     std::cerr << "********************************\n";*/
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     // Find the earliest element > key
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     // Lil' off by one touchup :)
00308     if (i < size() && _entries[i].first <= key)
00309         ++i;
00310     
00311     _entries.push_back(_entries.back());
00312 
00313     // Shift everything beyond i right
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     // Shift left
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     // Shift left
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 } // namespace Raul
00414 
00415 #endif // RAUL_TABLE_IMLP_HPP
00416 

Generated on Wed Apr 9 08:14:41 2008 for RAUL by  doxygen 1.5.1