Geeks With Blogs
Robert's Blog ideas about design and development

Now that insert is fully functional, we are going to want to implement RemoveAt.

        [Test]
public void RemoveAtWorks()
{
list.Add(name);
list.Add(name1);
string name2 = "James";
list.Add(name2);
list.RemoveAt(1);
enumerator.MoveNext();
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name2));
}

That test looks pretty good. Now let's go implement RemoveAt.

        public void RemoveAt(int index)
{
int position = -1;
MyListNode<T> node = null;
if (index == 0) RemoveFirst();
else if (index == Count - 1) RemoveLast();
else
{
do
{
position++;
if (node == null) node = head;
else node = node.next;
} while (position < index);
if (node.next != null && node.previous != null)
{
node.previous.next = node.next;
node.next.previous = node.previous;
}
node.Clear();
}
}

Here is an interesting situation. We've identified that removing the first and last node in sequence are in fact special cases. So we'll skip on and write a test for RemoveFirst.

        [Test]
public void RemoveFirstWorks()
{
list.Add(name);
list.Add(name1);
list.RemoveFirst();
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name1));
}

That's a reasonable looking test, so now we'll go implement RemoveFirst.

        public void RemoveFirst()
{
if (Count == 0)
throw new Exception(
"Cannot remove first node of an empty list.");
if (head.next != null) head = head.next;
count--;
}

Moving on to RemoveLast.

        [Test]
public void RemoveLastWorks()
{
list.Add(name);
list.Add(name1);
list.RemoveLast();
enumerator.MoveNext();
Assert.IsFalse(enumerator.MoveNext());
Assert.IsTrue(list.Count == 1);
}

That's a decent test. Let's implement the RemoveLast method now.

public void RemoveLast()
{
if (Count == 0)
throw new Exception(
"Cannot remove last node of an empty list.");
if (tail.previous != null) tail = tail.previous;
else tail = null;
count--;
}

Oops! Our test is still failing, I am not meeting one of my assumptions, that the new tail's next field is getting set to null. Let's go back and do that.

        public void RemoveLast()
{
if (Count == 0)
throw new Exception(
"Cannot remove last node of an empty list.");
if (tail.previous != null)
{
MyListNode<T> node = head;
tail = tail.previous;
tail.next = null;
node.Clear();
}
else tail = null;
count--;
}

This highlighted a similar problem with RemoveFirst. The new head's previous field is not being set to null. Now we'll go back and fix that.

        public void RemoveFirst()
{
if (Count == 0)
throw new Exception(
"Cannot remove first node of an empty list.");
if (head.next != null)
{
MyListNode<T> node = head;
head = head.next;
head.previous = null;
node.Clear();
}
else head = null;
count--;
}

Now that all of our tests are passing, we'll move forward by writing a test for Contains.

        [Test]
public void ContainsWorks()
{
list.Add(name);
Assert.IsTrue(list.Contains(name));
list.Add(name1);
Assert.IsTrue(list.Contains(name1));
}

This test looks good. We'll go implement Contains now.

        public bool Contains(T item)
{
MyListNode<T> node;
Contains(item, out node);
return node != null;
}

public bool Contains(T item, out MyListNode<T> node)
{
node = null;
MyListNode<T> current = null;
do
{
if (current == null) current = head;
else current = current.next;
if(current.item.Equals(item))
{
node = current;
return true;
}
} while ((current != null && current.next != null));
return false;
}

The Contains method makes a call to its overload which returns an out parameter. This will be useful later. All of our tests pass. Now let's write a test for Remove.

        [Test]
public void RemoveWorks()
{
list.Add(name);
list.Add(name1);
list.Remove(name);
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name1));
}

Okay, that looks sufficient. Now lets go implement remove.

        public bool Remove(T item)
{
MyListNode<T> node;
if(Contains(item, out node))
{
DereferenceNode(node);
return true;
}
return false;
}

protected void DereferenceNode(MyListNode<T> node)
{
if (node.Equals(head))
{
if(head.next != null) head = head.next;
else head = null;
}
else if (node.Equals(tail))
{
if (tail.previous != null) tail = tail.previous;
else tail = null;
}

if(node.next != null && node.previous != null)
{
node.previous.next = node.next;
node.next.previous = node.previous;
}
else if(node.next != null)
{
node.next.previous = null;
}
else if(node.previous != null) node.previous.next = null;
}

One thing that all the Remove functions have in common is that they need to dereference the node containing the item they are removing. So we'll go back and refactor them to use DereferenceNode.

        public void RemoveAt(int index)
{
int position = -1;
MyListNode<T> node = null;
if (index == 0) RemoveFirst();
else if (index == Count - 1) RemoveLast();
else
{
do
{
position++;
if (node == null) node = head;
else node = node.next;
} while (position < index);
DereferenceNode(node);
node.Clear();
count--;
}
}

public void RemoveFirst()
{
if (Count == 0)
throw new Exception(
"Cannot remove first node of an empty list.");
MyListNode<T> node = head;
DereferenceNode(node);
node.Clear();
count--;
}

public void RemoveLast()
{
if (Count == 0)
throw new Exception(
"Cannot remove last node of an empty list.");
MyListNode<T> node = tail;
DereferenceNode(node);
node.Clear();
count--;
}

We'll run all our tests again. All the tests pass, now we should implement IndexOf.

        [Test]
public void IndexOfWorks()
{
list.Add(name);
list.Add(name1);
Assert.IsTrue(list.IndexOf(name1) == 1);
}

That test was pretty straightforward. Let's go write some code to make it pass.

        public int IndexOf(T item)
{
int index;
MyListNode<T> node;
Contains(item, out node, out index);
return index;
}

...

public bool Contains(T item, out MyListNode<T> node)
{
int index;
return Contains(item, out node, out index);
}

public bool Contains(T item, out MyListNode<T> node, out int index)
{
node = null;
index = -1;
int position = -1;
MyListNode<T> current = null;
do
{
position++;
if (current == null) current = head;
else current = current.next;
if(current.item.Equals(item))
{
node = current;
index = position;
return true;
}
} while ((current != null && current.next != null));
return false;
}

We've refactored Contains to take an integer out parameter that represents the index of the item in the list, and we've added an overload for it that does not require the integer out parameter. Now we'll write a test for the indexer.

        [Test]
public void GetIndexerWorks()
{
list.Add(name);
list.Add(name1);
list[0].Equals(name);
list[1].Equals(name1);
}

Looking sharp. And now to implement the get indexer.

        public T this[int index]
{
get
{
IEnumerator<T> enumerator = GetEnumerator();
int position = -1;
while (enumerator.MoveNext())
{
position++;
if (position == index) return enumerator.Current;
}
return default(T);
}
...

Cool, lets go ahead and implement our set indexer. Since it will use Insert, which is tested, we really have no need to write a test for it.

        public T this[int index]
{
get
{
IEnumerator<T> enumerator = GetEnumerator();
int position = -1;
while (enumerator.MoveNext())
{
position++;
if (position == index) return enumerator.Current;
}
return default(T);
}
set
{
Insert(index, value);
}
}

Continued ...

Posted on Friday, December 21, 2007 6:59 AM Unit Testing , C# | Back to top


Comments on this post: Writing a Linked List: Then vs Now (part 2)

No comments posted yet.
Your comment:
 (will show your gravatar)


Copyright © Robery Stackhouse | Powered by: GeeksWithBlogs.net