From 47fb95d6086c2c67086316a25b4c0858783d3c2b Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 26 Jul 2007 11:29:31 +0000 Subject: Added PathTable, simple pretty wrapper around Table which provides super fast "find all descendants". I couldn't deal with the 'one big table' or 'parents own/lookup children' decision, so I came up with this thing instead. It's pretty cool I guess. git-svn-id: http://svn.drobilla.net/lad/raul@635 a436a847-0d15-0410-975c-d299462d15a1 --- raul/Makefile.am | 1 + raul/Path.hpp | 9 +++++ raul/PathTable.hpp | 45 +++++++++++++++++++++++ raul/Table.hpp | 8 +++-- raul/TableImpl.hpp | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 5 files changed, 163 insertions(+), 3 deletions(-) create mode 100644 raul/PathTable.hpp (limited to 'raul') 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 #include #include +#include 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 + * + * 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 +#include + +namespace Raul { + +template +class PathTable : public Table { +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::const_iterator find_descendants_end( + typename Table::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::find(const K& key) } +/** Binary search (O(log(end-begin))) */ +template +typename Table::const_iterator +Table::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 Table::const_iterator +Table::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::find(const K& key) * O(log(n)) best case (capacity is large enough) */ template -std::pair::iterator,bool> +std::pair::iterator, bool> Table::insert(const std::pair& entry) { const K& key = entry.first; -- cgit v1.2.1