linked_lists.py

#!/usr/bin/env python

'''
Linked list Python style

See cpp submission for function descriptions

Will Farmer
CSCI2270

'''

def append(head, attach_node):
    '''
    Appends node class instance to end of list
    '''
    if head == None:
        print 'ERROR --> Must pass existing node instance. Please initialize a list.'
    else:
        cursor = head
        while cursor.link != None:
            cursor = cursor.link
        cursor.link = attach_node

def append_data(head, data):
    '''
    Appends node class instance to end of list
    '''
    new_node = init_node(data)
    append(head, new_node)

def contains(head, data):
    '''
    Tests and determine if a given list contains a given node
    '''
    if head == None:
        print 'ERROR --> Must pass existing node instance. Please initialize a list.'
        return False
    else:
        cursor = head
        while cursor.link != None:
            if cursor.data == data:
                return True
            cursor = cursor.link
        if cursor.data == data:
            return True
        else:
            return False

def init_node(data):
    '''
    Initiate a new node class instance and return it with given data values
    '''
    new_node = Node()
    new_node.data = data
    return new_node

def insert(head, new_node, offset):
    '''
    Inserts a given node instance to a specific offset location
    '''
    if head == None:
        print 'ERROR --> Must pass existing node instance. Please initialize a list.'
    else:
        if offset == 0:
            head_data     = head.data
            head_link     = head.link
            head.data     = new_node.data
            head.link     = new_node
            new_node.data = head_data
            new_node.link = head_link
        else:
            cursor = head
            count  = 0
            while cursor.link != None:
                count += 1
                if count >= offset:
                    break
                cursor = cursor.link
            new_node.link = cursor.link
            cursor.link = new_node

def insert_data(head, data, offset):
    '''
    Insert a new node at the specified offset location
    '''
    new_node = init_node(data)
    insert(head, new_node, offset)

def remove(head, offset):
    '''
    Remove the specified node in the specified offset location
    '''
    if head == None:
        print 'ERROR --> Must pass existing node instance. Please initialize a list.'
    else:
        if offset == 0:
            head.data = head.link.data
            head.link = head.link.link
        else:
            cursor = head
            count  = 0
            while cursor.link != None:
                count += 1
                if count >= offset:
                    break
                cursor = cursor.link
            cursor.link = cursor.link.link


def report(head):
    '''
    Reports on the contents of the list
    '''
    if head == None:
        return ''
    report_string = ''
    cursor = head
    report_string += '%i ' %cursor.data
    while cursor.link != None:
        cursor = cursor.link
        report_string += '%i ' %cursor.data
    return report_string

def size(head):
    '''
    Return the size of the list
    '''
    if head == None:
        print 'ERROR --> Must pass existing node instance. Please initialize a list.'
        return 0
    else:
        cursor = head
        count  = 1
        while cursor.link != None:
            count += 1
            cursor = cursor.link
        return count

class Node:
    '''
    Node class object
    '''
    def __init__(self):
        self.data = None
        self.link = None

list_test.py

#!/usr/bin/env python

'''
Linked list Python style -- TESTER

See cpp submission for function descriptions

Will Farmer
CSCI2270

'''


import sys
import unittest
import linked_lists

class TestLinkedLists(unittest.TestCase):

    def __init__(self, *args, **kwargs):
        unittest.TestCase.__init__(self, *args, **kwargs)

    def setUp(self):
        self.full_list = linked_lists.init_node(5)
        linked_lists.append_data(self.full_list, 4)
        linked_lists.append_data(self.full_list, 3)
        linked_lists.append_data(self.full_list, 2)
        linked_lists.append_data(self.full_list, 1)
        linked_lists.append_data(self.full_list, 0)

    def append(self):
        new_list    = linked_lists.init_node(5)
        attach_node = linked_lists.init_node(4)
        linked_lists.append_data(new_list, attach_node)
        assert(new_list.data == 5)
        assert(new_list.link.data == 4)

    def test_append_data(self):
        new_list = linked_lists.init_node(5)
        linked_lists.append_data(new_list, 4)
        assert(new_list.data == 5)
        assert(new_list.link.data == 4)

    def test_contains(self):
        assert(linked_lists.contains(self.full_list, 3) == True)
        assert(linked_lists.contains(self.full_list, 5) == True)
        assert(linked_lists.contains(self.full_list, 0) == True)
        assert(linked_lists.contains(self.full_list, 30) == False)
        assert(linked_lists.contains(self.full_list, 6) == False)
        assert(linked_lists.contains(self.full_list, -1) == False)

    def test_init_node(self):
        node = linked_lists.init_node(5)
        assert(node.data == 5)
        assert(node.link == None)

    def test_insert_data(self):
        linked_lists.insert_data(self.full_list, 90, 0)
        report_string_offset_0 = linked_lists.report(self.full_list)
        assert(report_string_offset_0 == '90 5 4 3 2 1 0 ')

        linked_lists.insert_data(self.full_list, 70, 3)
        report_string_offset_3 = linked_lists.report(self.full_list)
        assert(report_string_offset_3 == '90 5 4 70 3 2 1 0 ')

        linked_lists.insert_data(self.full_list, 60, 1)
        report_string_offset_1 = linked_lists.report(self.full_list)
        assert(report_string_offset_1 == '90 60 5 4 70 3 2 1 0 ')

    def test_insert(self):
        insert_node_90 = linked_lists.init_node(90)
        insert_node_70 = linked_lists.init_node(70)
        insert_node_60 = linked_lists.init_node(60)

        report_string = linked_lists.report(self.full_list)

        linked_lists.insert(self.full_list, insert_node_90, 0)
        report_string_offset_0 = linked_lists.report(self.full_list)

        linked_lists.insert(self.full_list, insert_node_70, 3)
        report_string_offset_3 = linked_lists.report(self.full_list)

        linked_lists.insert(self.full_list, insert_node_60, 1)
        report_string_offset_1 = linked_lists.report(self.full_list)

        assert(report_string_offset_0 == '90 5 4 3 2 1 0 ')
        assert(report_string_offset_3 == '90 5 4 70 3 2 1 0 ')
        assert(report_string_offset_1 == '90 60 5 4 70 3 2 1 0 ')

    def test_node_class(self):
        new_node = linked_lists.Node()
        assert(new_node.data == None)
        assert(new_node.link == None)

    def test_remove(self):
        linked_lists.remove(self.full_list, 0)
        report_string_offset_0 = linked_lists.report(self.full_list)
        assert(report_string_offset_0 == '4 3 2 1 0 ')

        linked_lists.remove(self.full_list, 2)
        report_string_offset_2 = linked_lists.report(self.full_list)
        assert(report_string_offset_2 == '4 3 1 0 ')

        linked_lists.remove(self.full_list, 3)
        report_string_offset_3 = linked_lists.report(self.full_list)
        assert(report_string_offset_3 == '4 3 1 ')

    def test_report(self):
        report_string = linked_lists.report(self.full_list)
        assert(report_string == '5 4 3 2 1 0 ')

    def test_size(self):
        list_size = linked_lists.size(self.full_list)
        assert(list_size == 6)

        new_list = linked_lists.init_node(29)
        assert(linked_lists.size(new_list) == 1)

if __name__ == "__main__":
    unittest.main()