aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--common/array.h6
-rw-r--r--common/list.h109
-rw-r--r--common/list_intern.h4
-rw-r--r--test/common/list.h85
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);
}
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-21 02:55:39 +0000