COMMON: Improved efficiency of some Common::List methods; added more unit tests and some doxygen comments for Common::List and Common::Array

svn-id: r40164

4 files changed, 163 insertions, 41 deletions

diff --git a/common/array.h b/common/array.h
index 097dcbfdca..1ce8df55a7 100644
--- a/common/array.h
+++ b/common/array.h
@@ -65,6 +65,7 @@ public:
 		delete[] _storage;
 	}
 
+	/** Appends element to the end of the array. */
 	void push_back(const T &element) {
 		ensureCapacity(_size + 1);
 		_storage[_size++] = element;
@@ -76,26 +77,31 @@ public:
 		_size += array._size;
 	}
 
+	/** Removes the last element of the array. */
 	void pop_back() {
 		assert(_size > 0);
 		_size--;
 	}
 
+	/** Returns a reference to the first element of the array. */
 	T &front() {
 		assert(_size > 0);
 		return _storage[0];
 	}
 
+	/** Returns a reference to the first element of the array. */
 	const T &front() const {
 		assert(_size > 0);
 		return _storage[0];
 	}
 
+	/** Returns a reference to the last element of the array. */
 	T &back() {
 		assert(_size > 0);
 		return _storage[_size-1];
 	}
 
+	/** Returns a reference to the last element of the array. */
 	const T &back() const {
 		assert(_size > 0);
 		return _storage[_size-1];
diff --git a/common/list.h b/common/list.h
index d4252db8bb..b05a2b4e16 100644
--- a/common/list.h
+++ b/common/list.h
@@ -63,94 +63,103 @@ public:
 		clear();
 	}
 
+	/**
+	 * Inserts element before pos.
+	 */
 	void insert(iterator pos, const t_T &element) {
-		ListInternal::NodeBase *newNode = new Node(element);
-
-		newNode->_next = pos._node;
-		newNode->_prev = pos._node->_prev;
-		newNode->_prev->_next = newNode;
-		newNode->_next->_prev = newNode;
+		insert(pos._node, element);
 	}
 
+	/**
+	 * Inserts the elements from first to last before pos.
+	 */
 	template<typename iterator2>
 	void insert(iterator pos, iterator2 first, iterator2 last) {
 		for (; first != last; ++first)
 			insert(pos, *first);
 	}
 
+	/**
+	 * Deletes the element at location pos and returns an iterator pointing
+	 * to the element after the one which was deleted.
+	 */
 	iterator erase(iterator pos) {
 		assert(pos != end());
-
-		NodeBase *next = pos._node->_next;
-		NodeBase *prev = pos._node->_prev;
-		Node *node = static_cast<Node *>(pos._node);
-		prev->_next = next;
-		next->_prev = prev;
-		delete node;
-		return iterator(next);
+		return iterator(erase(pos._node)._next);
 	}
 
+	/**
+	 * Deletes the element at location pos and returns an iterator pointing
+	 * to the element before the one which was deleted.
+	 */
 	iterator reverse_erase(iterator pos) {
 		assert(pos != end());
-
-		NodeBase *next = pos._node->_next;
-		NodeBase *prev = pos._node->_prev;
-		Node *node = static_cast<Node *>(pos._node);
-		prev->_next = next;
-		next->_prev = prev;
-		delete node;
-		return iterator(prev);
+		return iterator(erase(pos._node)._prev);
 	}
 
+	/**
+	 * Deletes the elements between first and last (including first but not
+	 * last) and returns an iterator pointing to the element after the one
+	 * which was deleted (i.e., last).
+	 */
 	iterator erase(iterator first, iterator last) {
-		while (first != last)
-			erase(first++);
-
+		NodeBase *f = first._node;
+		NodeBase *l = last._node;
+		while (f != l)
+			f = erase(f)._next;
 		return last;
 	}
 
+	/**
+	 * Removes all elements that are equal to val from the list.
+	 */
 	void remove(const t_T &val) {
-		iterator i = begin();
-		const iterator e = end();
-		while (i != e)
-			if (val == *i)
-				i = erase(i);
+		NodeBase *i = _anchor._next;
+		while (i != &_anchor)
+			if (val == static_cast<Node *>(i)->_data)
+				i = erase(i)._next;
 			else
-				++i;
+				i = i->_next;
 	}
 
+	/** Inserts element at the start of the list. */
 	void push_front(const t_T &element) {
-		// TODO: Bypass iterators here for improved efficency
-		insert(begin(), element);
+		insert(_anchor._next, element);
 	}
 
+	/** Appends element to the end of the list. */
 	void push_back(const t_T &element) {
-		// TODO: Bypass iterators here for improved efficency
-		insert(end(), element);
+		insert(&_anchor, element);
 	}
 
+	/** Removes the first element of the list. */
 	void pop_front() {
-		// TODO: Bypass iterators here for improved efficency
-		erase(begin());
+		assert(!empty());
+		erase(_anchor._next);
 	}
 
+	/** Removes the last element of the list. */
 	void pop_back() {
-		// TODO: Bypass iterators here for improved efficency
-		erase(reverse_begin());
+		assert(!empty());
+		erase(_anchor._prev);
 	}
 
+	/** Returns a reference to the first element of the list. */
 	t_T &front() {
 		return static_cast<Node *>(_anchor._next)->_data;
 	}
 
+	/** Returns a reference to the first element of the list. */
 	const t_T &front() const {
 		return static_cast<Node *>(_anchor._next)->_data;
 	}
 
+	/** Returns a reference to the last element of the list. */
 	t_T &back() {
 		return static_cast<Node *>(_anchor._prev)->_data;
 	}
 
+	/** Returns a reference to the last element of the list. */
 	const t_T &back() const {
 		return static_cast<Node *>(_anchor._prev)->_data;
 	}
@@ -214,6 +223,28 @@ public:
 	const_iterator	end() const {
 		return const_iterator(const_cast<NodeBase*>(&_anchor));
 	}
+
+protected:
+	NodeBase erase(NodeBase *pos) {
+		NodeBase n = *pos;
+		Node *node = static_cast<Node *>(pos);
+		n._prev->_next = n._next;
+		n._next->_prev = n._prev;
+		delete node;
+		return n;
+	}
+
+	/**
+	 * Inserts element before pos.
+	 */
+	void insert(NodeBase *pos, const t_T &element) {
+		ListInternal::NodeBase *newNode = new Node(element);
+
+		newNode->_next = pos;
+		newNode->_prev = pos->_prev;
+		newNode->_prev->_next = newNode;
+		newNode->_next->_prev = newNode;
+	}
 };
 
 } // End of namespace Common
diff --git a/common/list_intern.h b/common/list_intern.h
index 772ca649f7..7ec7fdfd41 100644
--- a/common/list_intern.h
+++ b/common/list_intern.h
@@ -57,7 +57,7 @@ namespace ListInternal {
 		NodeBase *_node;
 
 		Iterator() : _node(0) {}
-		Iterator(NodeBase *node) : _node(node) {}
+		explicit Iterator(NodeBase *node) : _node(node) {}
 
 		// Prefix inc
 		Self &operator++() {
@@ -110,7 +110,7 @@ namespace ListInternal {
 		const NodeBase *_node;
 
 		ConstIterator() : _node(0) {}
-		ConstIterator(const NodeBase *node) : _node(node) {}
+		explicit ConstIterator(const NodeBase *node) : _node(node) {}
 		ConstIterator(const Iterator<T> &x) : _node(x._node) {}
 
 		// Prefix inc
diff --git a/test/common/list.h b/test/common/list.h
index 67db1e1a42..3b6b9a1721 100644
--- a/test/common/list.h
+++ b/test/common/list.h
@@ -104,6 +104,7 @@ class ListTestSuite : public CxxTest::TestSuite
 		container.insert(iter, 42);
 		container.insert(iter, 43);
 
+		// Verify contents are correct
 		iter = container.begin();
 
 		TS_ASSERT_EQUALS( *iter, 17 );
@@ -127,6 +128,82 @@ class ListTestSuite : public CxxTest::TestSuite
 		TS_ASSERT( iter == container.end() );
 	}
 
+	void test_erase() {
+		Common::List<int> container;
+		Common::List<int>::iterator first, last;
+
+		// Fill the container with some random data
+		container.push_back(17);
+		container.push_back(33);
+		container.push_back(-11);
+		container.push_back(42);
+		container.push_back(43);
+
+		// Iterate to after the second element
+		first = container.begin();
+		++first;
+		++first;
+
+		// Iterate to after the fourth element
+		last = first;
+		++last;
+		++last;
+
+		// Now erase that range
+		container.erase(first, last);
+
+		// Verify contents are correct
+		Common::List<int>::iterator iter = container.begin();
+
+		TS_ASSERT_EQUALS( *iter, 17 );
+		++iter;
+		TS_ASSERT( iter != container.end() );
+
+		TS_ASSERT_EQUALS( *iter, 33 );
+		++iter;
+		TS_ASSERT( iter != container.end() );
+
+		TS_ASSERT_EQUALS( *iter, 43 );
+		++iter;
+		TS_ASSERT( iter == container.end() );
+	}
+
+	void test_remove() {
+		Common::List<int> container;
+		Common::List<int>::iterator first, last;
+
+		// Fill the container with some random data
+		container.push_back(-11);
+		container.push_back(17);
+		container.push_back(33);
+		container.push_back(42);
+		container.push_back(-11);
+		container.push_back(42);
+		container.push_back(43);
+
+		// Remove some stuff
+		container.remove(42);
+		container.remove(-11);
+
+		// Now erase that range
+		container.erase(first, last);
+
+		// Verify contents are correct
+		Common::List<int>::iterator iter = container.begin();
+
+		TS_ASSERT_EQUALS( *iter, 17 );
+		++iter;
+		TS_ASSERT( iter != container.end() );
+
+		TS_ASSERT_EQUALS( *iter, 33 );
+		++iter;
+		TS_ASSERT( iter != container.end() );
+
+		TS_ASSERT_EQUALS( *iter, 43 );
+		++iter;
+		TS_ASSERT( iter == container.end() );
+	}
+
 	void test_reverse() {
 		Common::List<int> container;
 		Common::List<int>::iterator iter;
@@ -186,5 +263,13 @@ class ListTestSuite : public CxxTest::TestSuite
 		container.pop_front();
 		TS_ASSERT_EQUALS(container.front(), 163);
 		TS_ASSERT_EQUALS(container.back(),  163);
+
+		container.push_front(99);
+		TS_ASSERT_EQUALS(container.front(), 99);
+		TS_ASSERT_EQUALS(container.back(),  163);
+
+		container.pop_back();
+		TS_ASSERT_EQUALS(container.front(), 99);
+		TS_ASSERT_EQUALS(container.back(),  99);
 	}
 };