RAUL 0.7.0
|
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