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

5 files changed, 163 insertions, 3 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;