data_structs.py

class KeyNotFoundException(Exception):
    pass

class NotANodeError(TypeError):
    pass

class Node(object):

    def __init__(self, value, next=None):
        self.__value__ = value
        self.__next__ = next

    def __valid_node__(self, next_node):
        if next_node is None or isinstance(next_node, Node):
            return True
        else:
            return False

    def __next_or_not_node__(self, next):
        if self.__valid_node__(next):
            self.__next__ = next
        else:
            raise NotANodeError
                
    def set_next(self, next):
        self.__next_or_not_node__(next)

    def next(self):
        return self.__next__

    def value(self):
        return self.__value__

def get_value_at_index(node, index):
    def index_count(current_iter, rec_node):
        if current_iter == index:
            return rec_node.value()
        else:
            return index_count(current_iter +1, rec_node.next())
    return index_count(0, node)
    
    
class Hash(object):

    def __init__(self, **kwargs):
        first_node = None
        old_node = None
        for key, value in kwargs.items():
            new_node = Node(Node(key, Node(value)))
            if old_node:
                old_node.set_next(node)
            else:
                self.__node_tree__ = first_node
            old_node = new_node
        else:
            self.__node_tree__ = None

    def insert(self, key, value):
        key_value = Node(key, Node(value))
        new_tree = Node(key_value, self.__node_tree__)
        self.__node_tree__ = new_tree
        return self
        
    def search(self, requested_key):
        def search_requested_nodes(node):
            if not node:
                return node
                
            key_value_nodes = node.value()
            key = key_value_nodes.value()
            if key == requested_key:
                return key_value_nodes.next().value()
            return search_requested_nodes(node.next())            
        value = search_requested_nodes(self.__node_tree__)
        if value:
            return value    
        raise KeyNotFoundException
        
    def delete(self, deleted_key):
        def search_deleted_nodes(node, last_node):
            if not node:
                return node
            key_value_nodes = node.value()
            key = key_value_nodes.value()
            if key == deleted_key:
                node.set_next(None)
                if last_node:
                    return last_node.set_next(node.next())
                else:
                    return node.next()
            last_node = node
            return search_deleted_nodes(node.next(), last_node)
        value = search_deleted_nodes(self.__node_tree__, None)
        self.__node_tree__ = value    
            
def test_hash():
    new_hash =  Hash(key='value')
    new_hash.delete('key')
    try:
        new_hash.search('key')
    except KeyNotFoundException:
        print 'HASH PASS 1'
    new_hash.insert('key', 'value')
    value = new_hash.search('key')
    if value == 'value':
        print 'HASH PASS 2'
            
def test_nodes():
    first_node = Node('first')
    old_node = first_node
    for i in xrange(1, 10):
        next_node = Node(i)
        old_node.set_next(next_node)
        old_node = next_node
    if get_value_at_index(first_node, 0) == 'first':
        print 'NODE PASS 1'
    if get_value_at_index(first_node, 1) == 1:
        print 'NODE PASS 2'
    if get_value_at_index(first_node, 9) == 9:
        print 'NODE PASS 3'
    try:
        first_node.set_next('this is not a node')
    except NotANodeError:
        print 'NODE PASS 4'
    
test_hash()
test_nodes()