Monthly Archive for April, 2007

I was testing my algorithm/data structures chops by implementing a Linked List from scratch using no reference material (not very difficult, I know), and I must say that using BDD was incredibly helpful. I’m calling it “BDD” instead of “TDD” just because the test class names describe a context and the method names in the test classes are behavior-oriented, inspired by the style found on the RSpec site.

I didn’t write the tests/specs up front like you’re “supposed” to. Instead, I thought about what I was trying to do, came up with an initial idea for the implementation, started writing code, and then added a test to make sure I was on the right track. This worked out pretty well. I also used the tests during refactoring. Writing the tests first might have worked out better, but I can’t say for sure.

Now, for some real fun, implement a linked list based on only the test code below.

class LinkedList(object):
    def __init__(self, *values):
        self._size = 0
        if values:
            for v in values:
                self.add(v)
        else:
            self.head = self.tail = None

    def is_empty(self):
        return len(self) == 0

    def add(self, val):
        node = Node(val)
        if self.is_empty():
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self._size += 1

    def get(self, index, get_prev=False):
        if index < 0:
            index = self._size + index
        if index < 0 or index >= self.length:
            raise IndexError
        prev = None
        for i, node in enumerate(self):
            if i == index:
                if get_prev:
                    return node, prev
                else:
                    return node
            prev = node

    def remove(self, index):
        node, prev = self.get(index, get_prev=True)
        if node is self.head:
            self.head = node.next
        else:
            prev.next = node.next
        self._size -= 1
        return node

    def pop(self):
        return self.remove(self.length - 1)

    def __len__(self):
        return self._size
    length = property(__len__)
    size = property(__len__)

    def __iter__(self):
        curr = self.head
        while curr is not None:
            yield curr
            curr = curr.next
        raise StopIteration

    def __str__(self):
        return ', '.join([str(node.value) for node in self])

class Node(object):
    def __init__(self, val, next=None):
        self.value = val
        self.next = next

import unittest
class Test_A_New_Linked_List(unittest.TestCase):

    def test_given_no_values_should_be_empty(self):
        list_ = LinkedList()
        assert list_.is_empty()

    def test_given_no_values_should_have_size_0(self):
        list_ = LinkedList()
        assert list_.size == list_.length == 0

    def test_given_values_should_not_be_empty(self):
        list_ = LinkedList(1, 2, 3)
        assert not list_.is_empty()
        assert [node.value for node in list_] == [1, 2, 3]

    def test_given_4_values_should_have_size_4(self):
        list_ = LinkedList(1, '2', 3, '4th value')
        assert list_.size == 4

class Test_An_Empty_List(unittest.TestCase):

    def test_should_have_size_1_after_add(self):
        list_ = LinkedList()
        val = 15
        list_.add(val)
        assert list_.head.value == list_.tail.value == val
        assert len(list_) == list_.length == list_.size == 1

    def test_should_raise_an_index_error_on_get(self):
        list_ = LinkedList()
        self.assertRaises(IndexError, list_.get, 1)
        list_ = LinkedList(1, 2, 3)
        list_.remove(0); list_.remove(0); list_.remove(0)
        self.assertRaises(IndexError, list_.get, 0)

    def test_should_raise_an_index_error_on_remove(self):
        list_ = LinkedList()
        self.assertRaises(IndexError, list_.remove, 1)
        list_ = LinkedList(1, 2, 3)
        list_.remove(0); list_.remove(0); list_.remove(0)
        self.assertRaises(IndexError, list_.remove, 0)

    def test_should_raise_an_index_error_on_pop(self):
        list_ = LinkedList()
        self.assertRaises(IndexError, list_.pop)

class Test_A_Non_Empty_List(unittest.TestCase):

    def test_should_increase_its_size_by_1_on_add(self):
        list_ = LinkedList(1, 2, 4, 5)
        starting_size = list_.size
        list_.add(13)
        assert len(list_) == list_.length == list_.size == (starting_size + 1)

    def test_should_return_a_node_on_get(self):
        list_ = LinkedList(1, 2, '3rd value')
        node = list_.get(0)
        assert isinstance(node, Node)
        assert node.value == 1
        node = list_.get(1)
        assert isinstance(node, Node)
        assert node.value == 2
        node = list_.get(2)
        assert isinstance(node, Node)
        assert node.value == '3rd value'

    def test_should_decrease_its_size_by_1_on_remove(self):
        list_ = LinkedList(1, 2, 4, 5)
        starting_size = list_.size
        list_.remove(0)
        assert len(list_) == list_.length == list_.size == (starting_size - 1)

    def test_should_decrease_its_size_by_1_on_pop(self):
        list_ = LinkedList(1, 2, 4, 5)
        starting_size = list_.size
        list_.pop()
        assert len(list_) == list_.length == list_.size == (starting_size - 1)