diff options
| -rw-r--r-- | raul/Makefile.am | 1 | ||||
| -rw-r--r-- | raul/Path.hpp | 9 | ||||
| -rw-r--r-- | raul/PathTable.hpp | 45 | ||||
| -rw-r--r-- | raul/Table.hpp | 8 | ||||
| -rw-r--r-- | raul/TableImpl.hpp | 103 | ||||
| -rw-r--r-- | tests/table_test.cpp | 64 |
6 files changed, 224 insertions, 6 deletions
diff --git a/raul/Makefile.am b/raul/Makefile.am index 7f47a50..cd44b73 100644 --- a/raul/Makefile.am +++ b/raul/Makefile.am @@ -13,6 +13,7 @@ raulinclude_HEADERS = \ Maid.hpp \ Namespaces.hpp \ Path.hpp \ + PathTable.hpp \ Process.hpp \ Quantizer.hpp \ RDFModel.hpp \ diff --git a/raul/Path.hpp b/raul/Path.hpp index 5776309..d8ef751 100644 --- a/raul/Path.hpp +++ b/raul/Path.hpp @@ -21,6 +21,7 @@ #include <cctype> #include <string> #include <cassert> +#include <iostream> using std::string; namespace Raul { @@ -120,6 +121,14 @@ public: else return (*this) + "/"; } + + /** Return true if \a child is equal to, or a descendant of \a parent */ + static bool descendant_comparator(const Path& parent, const Path& child) + { + return ( child == parent + || (!strncmp(parent.c_str(), child.c_str(), parent.length()) + && child[parent.length()] == '/') ); + } }; diff --git a/raul/PathTable.hpp b/raul/PathTable.hpp new file mode 100644 index 0000000..6754b14 --- /dev/null +++ b/raul/PathTable.hpp @@ -0,0 +1,45 @@ +/* This file is part of Raul. + * Copyright (C) 2007 Dave Robillard <http://drobilla.net> + * + * Raul is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Raul is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef RAUL_PATH_TABLE_HPP +#define RAUL_PATH_TABLE_HPP + +#include <raul/Path.hpp> +#include <raul/Table.hpp> + +namespace Raul { + +template <typename T> +class PathTable : public Table<Path, T> { +public: + /** Find all descendants of a Path key in the Table. + * It is guaranteed that (parent, parent+1, parent+2, ..., ret-1) are all + * descendants of parent. The return value is never a descendent of + * parent, and may be end(). + */ + typename Table<Path, T>::const_iterator find_descendants_end( + typename Table<Path, T>::const_iterator parent) const + { + return find_range_end(parent, &Path::descendant_comparator); + } +}; + + +} // namespace Raul + +#endif // RAUL_PATH_TABLE_HPP + diff --git a/raul/Table.hpp b/raul/Table.hpp index d30b23e..e4d4fa5 100644 --- a/raul/Table.hpp +++ b/raul/Table.hpp @@ -75,12 +75,16 @@ public: void erase(const K& key); void erase(iterator i); - void erase(iterator begin, iterator end); - void erase(size_t begin, size_t end); + void erase(iterator start, iterator end); + void erase(size_t start, size_t end); const_iterator find(const K& key) const; iterator find(const K& key); + const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const; + const_iterator find_in_range(const K& key, const_iterator start, const_iterator end, + bool (*comp)(const K&,const K&)) const; + T& operator[](const K& key); const_iterator begin() const { return const_iterator(*this, 0); } diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp index 5b4946e..5da9715 100644 --- a/raul/TableImpl.hpp +++ b/raul/TableImpl.hpp @@ -86,6 +86,107 @@ Table<K,T>::find(const K& key) } +/** Binary search (O(log(end-begin))) */ +template <typename K, typename T> +typename Table<K,T>::const_iterator +Table<K,T>::find_in_range(const K& key, const_iterator start, const_iterator end, bool (*comp)(const K&,const K&)) const +{ + if (size() == 0) + return this->end(); + + size_t lower = start._index; + size_t upper = end._index; + + if (lower == upper) + if (comp(key, _entries[lower].first)) + return const_iterator(*this, lower); + else + return this->end(); + + size_t i = lower + ((upper - lower) / 2); + + while (upper >= lower) { + + const Entry& elem = _entries[i]; + + if (comp(key, elem.first)) + if (i == size()-1 || !comp(elem.first, _entries[i+1].first)) + return const_iterator(*this, i); + else if (comp(_entries[lower].first, elem.first)) + lower = i; + + if (comp(_entries[lower].first, _entries[upper].first)) + upper = i - 1; + } + + assert(comp(start->first, _entries[lower].first)); + assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first)); + + return const_iterator(*this, lower); +} + + +/** Find the end of a range using a custom comparator. + * Two entries a, b are considered in the range if comp(a, b) returns true. + * + * Returns an iterator exactly one entry past the end of the range (possibly end()). + * + * WARNING: The restrictions on \a comparator are very strict: ALL items + * considered equal by \a comparator must be stored in the Table consecutively + * i.e. there are no 3 values a, b, c S.T. comp(a) && ! comp(b) && comp(c). + * + * This is useful for very quickly finding all children of a Path, which + * obey the above rule with lexicographical order. + */ +template <typename K, typename T> +typename Table<K,T>::const_iterator +Table<K,T>::find_range_end(const_iterator start, bool (*comp)(const K&,const K&)) const +{ + if (size() == 0) + return this->end(); + + const K& key = start->first; + + size_t lower = start._index; + size_t upper = size() - 1; + + if (lower == upper) + if (comp(key, _entries[lower].first)) + return const_iterator(*this, lower); + else + return this->end(); + + size_t i; + + while (upper > lower) { + + i = lower + ((upper - lower) / 2); + + const Entry& elem = _entries[i]; + + // Hit + if (comp(key, elem.first)) { + + if (i == size()-1 || !comp(key, _entries[i+1].first)) + return const_iterator(*this, i+1); + else + lower = i; + + // Miss + } else { + + upper = i; + + } + } + + assert(comp(start->first, _entries[lower].first)); + assert(lower == size()-1 || !comp(start->first, _entries[lower+1].first)); + + return const_iterator(*this, lower+1); +} + + /** Add an item to the table, using \a entry.first as the search key. * An iterator to the element where value was set is returned, and a bool which * is true if an insertion took place, or false if an existing entry was updated. @@ -94,7 +195,7 @@ Table<K,T>::find(const K& key) * O(log(n)) best case (capacity is large enough) */ template <typename K, typename T> -std::pair<typename Table<K,T>::iterator,bool> +std::pair<typename Table<K,T>::iterator, bool> Table<K,T>::insert(const std::pair<K, T>& entry) { const K& key = entry.first; diff --git a/tests/table_test.cpp b/tests/table_test.cpp index 3ed3c7e..35bc408 100644 --- a/tests/table_test.cpp +++ b/tests/table_test.cpp @@ -1,15 +1,30 @@ #include <string> #include <iostream> #include <utility> +#include <raul/PathTable.hpp> #include <raul/Table.hpp> #include <raul/TableImpl.hpp> using namespace Raul; using namespace std; +int range_end_val; + +bool range_comparator(const int& a, const int& b) +{ + bool ret = (b >= a && b <= range_end_val); + //cout << "COMP: " << a << " . " << b << " = " << ret << endl; + return ret; +} + + int main() { + srand(time(NULL)); + + range_end_val = rand()%10; + Table<int, int> t; for (size_t i=0; i < 20; ++i) { int val = rand()%10; @@ -18,10 +33,22 @@ main() t[20] = 20; t[21] = 21; - + + cout << "Contents:" << endl; for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) cout << i->first << " "; cout << endl; + + std::cout << "Range " << t.begin()->first << " .. " << range_end_val << std::endl; + + Table<int,int>::const_iterator range_begin = t.begin(); + ++range_begin; ++range_begin; + + Table<int,int>::const_iterator range_end = t.find_range_end(t.begin(), range_comparator); + + for (Table<int,int>::const_iterator i = t.begin(); i != range_end; ++i) + cout << i->first << " "; + cout << endl; Table<int, int>::iterator first = t.begin(); ++first; @@ -66,9 +93,40 @@ main() /* **** */ - cout << "Assuming you built with debugging, if this continues to run " + PathTable<char> pt; + pt.insert(make_pair("/foo", 'a')); + pt.insert(make_pair("/bar", 'a')); + pt.insert(make_pair("/bar/baz", 'b')); + pt.insert(make_pair("/bar/bazz/NO", 'c')); + pt.insert(make_pair("/bar/baz/YEEEAH", 'c')); + pt.insert(make_pair("/bar/baz/YEEEAH/BOOOEEEEE", 'c')); + pt.insert(make_pair("/bar/buzz", 'b')); + pt.insert(make_pair("/bar/buzz/WHAT", 'c')); + pt.insert(make_pair("/bar/buzz/WHHHhhhhhAT", 'c')); + pt.insert(make_pair("/quux", 'a')); + + cout << "Paths: " << endl; + for (PathTable<char>::const_iterator i = pt.begin(); i != pt.end(); ++i) + cout << i->first << " "; + cout << endl; + + PathTable<char>::const_iterator descendants_begin = pt.begin(); + size_t begin_index = rand() % pt.size(); + for (size_t i=0; i < begin_index; ++i) + ++descendants_begin; + + cout << "\nDescendants of " << descendants_begin->first << endl; + PathTable<char>::const_iterator descendants_end = pt.find_descendants_end(descendants_begin); + + for (PathTable<char>::const_iterator i = pt.begin(); i != descendants_end; ++i) + cout << i->first << " "; + cout << endl; + + /* **** */ + + cout << "\nAssuming you built with debugging, if this continues to run " << "and chews your CPU without dying, everything's good." << endl; - srand(time(NULL)); + Table<string, string> st; |