Add Table unit test.

Match std::map interface for empty and insert (more powerful insert interface).


git-svn-id: http://svn.drobilla.net/lad/raul@631 a436a847-0d15-0410-975c-d299462d15a1

3 files changed, 133 insertions, 10 deletions

diff --git a/raul/Table.hpp b/raul/Table.hpp
index 524d11c..db5216f 100644
--- a/raul/Table.hpp
+++ b/raul/Table.hpp
@@ -36,10 +36,11 @@ public:
 	Table<K, T>()  {}
 	
 	void clear() { _entries.clear(); }
+	bool empty() const { return _entries.empty(); }
 
 	struct const_iterator {
 		const_iterator(const Table<K,T>& t, size_t i) : _table(t), _index(i) {}
-		inline const std::pair<const K, T>& operator*() const { return _table._entries[_index]; }
+		inline const std::pair<const K, T> operator*() const { return _table._entries[_index]; }
 		inline const std::pair<const K, T>* operator->() const { return (std::pair<const K, T>*)&_table._entries[_index]; }
 		inline const_iterator& operator++() { ++_index; return *this; }
 		inline const_iterator& operator--() { --_index; return *this; }
@@ -70,7 +71,8 @@ public:
 
 	inline size_t size() const { return _entries.size(); }
 
-	void insert(const K& key, const T& value);
+	std::pair<iterator,bool> insert(const std::pair<K, T>& entry);
+
 	void erase(const K& key);
 	void erase(iterator i);
 	void erase(iterator begin, iterator end);
diff --git a/raul/TableImpl.hpp b/raul/TableImpl.hpp
index ab79b7f..35bf2f6 100644
--- a/raul/TableImpl.hpp
+++ b/raul/TableImpl.hpp
@@ -74,17 +74,27 @@ Table<K,T>::find(const K& key)
 }
 
 
+/** 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.
+ * Matches std::map::insert interface.
+ * O(n) worst case
+ * O(log(n)) best case (capacity is large enough)
+ */
 template <typename K, typename T>
-void
-Table<K,T>::insert(const K& key, const T& value)
+std::pair<typename Table<K,T>::iterator,bool>
+Table<K,T>::insert(const std::pair<K, T>& entry)
 {
+	const K& key = entry.first;
+	const T& value = entry.second;
+	
 	if (size() == 0 || size() == 1 && key > _entries[0].first) {
-		_entries.push_back(make_pair(key, value));
-		return;
+		_entries.push_back(entry);
+		return make_pair(iterator(*this, size()-1), true);
 	} else if (size() == 1) {
 		_entries.push_back(_entries[0]);
-		_entries[0] = make_pair(key, value);
-		return;
+		_entries[0] = entry;
+		return make_pair(begin(), true);
 	}
 
 	size_t lower = 0;
@@ -103,7 +113,8 @@ Table<K,T>::insert(const K& key, const T& value)
 		Entry& elem = _entries[i];
 
 		if (elem.first == key) {
-			break;
+			elem.second = value;
+			return make_pair(iterator(*this, i), false);
 		} else if (elem.first > key) {
 			if (i == 0 || _entries[i-1].first < key)
 				break;
@@ -123,9 +134,11 @@ Table<K,T>::insert(const K& key, const T& value)
 	for (size_t j = size()-1; j > i; --j)
 		_entries[j] = _entries[j-1];
 	
-	_entries[i] = make_pair(key, value);
+	_entries[i] = entry;
 
 	assert(is_sorted());
+	
+	return make_pair(iterator(*this, i), true);
 }
 
 
diff --git a/tests/table_test.cpp b/tests/table_test.cpp
new file mode 100644
index 0000000..06bf489
--- /dev/null
+++ b/tests/table_test.cpp
@@ -0,0 +1,108 @@
+#include <string>
+#include <iostream>
+#include <utility>
+#include <raul/Table.hpp>
+#include <raul/TableImpl.hpp>
+
+using namespace Raul;
+using namespace std;
+
+int
+main()
+{
+	Table<int, int> t;
+	for (size_t i=0; i < 20; ++i) {
+		int val = rand()%10;
+		t.insert(make_pair(val, val));
+	}
+
+	for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+
+	Table<int, int>::iterator first = t.begin();
+	++first;
+	Table<int, int>::iterator last = first;
+	++last; ++last; ++last;
+
+	cout << "Erasing elements 1..3:" << endl;
+	t.erase(first, last);
+
+	for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+	
+	cout << "Erasing elements 0..3" << endl;
+	first = t.begin();
+	last = first;
+	++last; ++last; ++last;
+	t.erase(first, last);
+
+	for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+	
+	cout << "Erasing elements end()-2..end()" << endl;
+	last = t.end();
+	first = last;
+	--first; --first;
+	t.erase(first, last);
+
+	for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+	
+	cout << "Erasing everything" << endl;
+	first = t.begin();
+	last = t.end();
+	t.erase(first, last);
+
+	for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i)
+		cout << i->first << " ";
+	cout << endl;
+	
+	/* **** */
+
+	cout << "Assuming 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;
+
+	st.insert(make_pair("apple", "core"));
+	st.insert(make_pair("candy", "cane"));
+	st.insert(make_pair("banana", "peel"));
+
+	st.erase("apple");
+
+	while (true) {
+		Table<int, int> t;
+
+		size_t table_size = (rand() % 1000) + 1;
+
+		for (size_t i=0; i < table_size; ++i) {
+			int val = rand()%100;
+			t.insert(make_pair(val, ((val + 3) * 17)));
+		}
+
+		for (int i=0; i < (int)table_size; ++i) {
+			int val = rand()%100;
+			Table<int, int>::iterator iter = t.find(val);
+			assert(iter == t.end() || iter->second == (val + 3) * 17);
+		}
+
+		/*cout << "CONTENTS:" << endl;
+
+		  for (Table<int,int>::const_iterator i = t.begin(); i != t.end(); ++i) {
+		  cout << i->first << ": " << i->second << endl;
+		  }
+
+		  Table<int,int>::iterator i = t.find(7);
+		  if (i != t.end())
+		  cout << "Find: 7: " << i->second << endl;
+		  */
+	}
+
+	return 0;
+}
+