LinkedHashTable Implementation, Python 3

LinkedHashTable Implementation

"""
LinkedHashSet
"""

class Node:
    __slots__ = "data", "chain_next", "order_previous", "order_next"
    
    def __init__(self, data):
        self.data = data
        self.chain_next = None
        self.order_previous = None
        self.order_next = None
        
    def __str__(self):
        return "{" + str(self.data) + "}"
    
class LinkedHashSet:
    __slots__ = "table", "currentSize", "capacity", "front", "back", "load_limit", "load_factor"
    
    def __init__(self, capacity = 100):
        self.table = capacity * [None]
        self.capacity = capacity
        self.front = None
        self.back = None
        self.currentSize = 0
        self.load_limit = 0.85
        self.load_factor = 0.0
        
    def add(self, item):
        self._add(item)
        self._rehash()
    
    def _add(self, item):
        if self.contains(item):
            return
        
        index = self._hash(item)
        chain = self.table[index]
        
        # print('Adding ' + str(item) + ' at ' + str(index))
        
        newnode = Node(item)
        
        # Handle ordering related links
        if self.front is None:
            self.front = newnode
            self.back = newnode
            newnode.order_previous = None
            newnode.order_next = None
        else:
            self.back.order_next = newnode
            newnode.order_previous = self.back
            self.back = newnode
        
        # Order chaining related links
        if chain is not None:
            current = chain
            while current is not None:
                if current.chain_next is None:
                    break
                current = current.chain_next
            current.chain_next = newnode
        else:
            chain = newnode
            
        self.table[index] = chain
        self.currentSize += 1
        
    def remove(self, item):
        if not self.contains(item):
            return
        
        index = self._hash(item)
        chain = self.table[index]
        
        if chain is not None:
            # Remove node from order chain
            if chain.order_previous is not None:
                chain.order_previous.order_next = chain.order_next
                if chain.order_next is not None:
                    chain.order_next.order_previous = chain.order_previous

self.currentSize -= 1
                if self.currentSize <= 0:
                    self.front = None
                    self.back = None
                    self.table[index] = None
                chain = chain.chain_next

if chain == self.front:
                    self.back = chain
            else:
                self.currentSize -= 1
                self.front = chain.order_next
                if self.front is not None:
                    self.front.order_previous = None
                chain = chain.chain_next
                
            self.table[index] = chain
            self._rehash()
    
    def contains(self, item):
        index = self._hash(item)
        chain = self.table[index]
        
        if chain is not None:
            current = chain
            while current is not None:
                #print(current.data + " == " + item + " : " + str(current.data == item))
                if current.data == item:
                    return True
                current = current.chain_next
                
        return False
        
    def size(self):
        return self.currentSize
    
    def __iter__(self):
        current = self.front
        while current is not None:
            yield current.data
            current = current.order_next
    
    def _hash(self, item):
        return hash(item) % self.capacity
    
    def _rehash(self):
        self.load_factor = self.currentSize / self.capacity
        
        #if self.currentSize >= (self.capacity * self.load_limit):
        if self.load_factor >= (self.load_limit):
            # increase table size
            new_cap = 2 * self.capacity
            print( "Rehashing from", self.capacity, "to", new_cap )
            new_map = LinkedHashSet( new_cap )
            for key in self:
                new_map._add(key)
            self.capacity = new_map.capacity
            self.table = new_map.table
            
        #elif self.currentSize <= ((1 - self.load_limit) * self.capacity):
        elif self.load_factor <= (1 - self.load_limit):
            # decrease table size
            new_cap = self.capacity // 2
            print( "Rehashing from", self.capacity, "to", new_cap )
            new_map = LinkedHashSet( new_cap )
            for key in self:
                new_map._add(key)
            self.capacity = new_map.capacity
            self.table = new_map.table
    
    def print(self):
        current = self.front
        while current is not None:
            print("{" + str(self._hash(current.data)) + ':' + str(current.data) + "}")
            current = current.order_next
            
    def print_table(self):
        print()
        print('Table Contents: ')
        print()
        for i in range(self.capacity):
            print(str(i) + ': ', end = ' ')
            items = []
            
            current = self.table[i]
            if current is not None:
                while current is not None:
                    #print("{" + str(i) + ": " + str(current.data) + "}", end = ' ')
                    items.append(current.data)
                    current = current.chain_next
            print(items)
    
def testLinkedHashTable():
    table = LinkedHashSet(100)
    
    for i in range(100):
        table.add("batman"+str(i))
    
    print("Size = " + str(table.size()))
        
    result = True
    
    # Test for membership
    for i in range(100):
        #print('contains batman'+str(i) + ' = ' + str(table.contains("batman"+str(i))))
        result &= table.contains("batman"+str(i))
        
    # Test for removal and membership
    for i in range(100):
        result &= table.contains("batman"+str(i))
        table.remove("batman"+str(i))
        print("Size = " + str(table.size()))
        result &= not table.contains('batman'+str(i))
        
    print('Test result = ' + str('Passed' if result else 'Failed'))
    
    print("Size = " + str(table.size()))
    
    table.print_table()
        
if __name__ == "__main__":
    testLinkedHashTable()


run \| edit \| history \| help	0