compile python3 online

Language: Layout:

"""
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]
        
        # Handle chaining related links
        current = chain
        previous = current
        while current is not None:
            if current.data == item:
                print("Removing " + item)
                previous.chain_next = current.chain_next
                current.chain_next = None
                break
            previous = current
            current = current.chain_next
        
        # Handle ordering related links
        if current.order_previous is not None:
            current.order_previous.order_next = current.order_next
        if current.order_next is not None:
            current.order_next.order_previous = current.order_previous
        current.order_next = None
        current.order_previous = None
        
        self.table[index] = chain
        
        self.currentSize -= 1
        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))
        #result &= not table.contains('batman'+str(i))
        
    print('Test result = ' + str('Passed' if result else 'Failed'))
    
    print("Size = " + str(table.size()))
    
    for item in table:
        print(item, end = ' ')

table.print_table()
        
if __name__ == "__main__":
    testLinkedHashTable()

[ + ] Show input
Absolute running time: 0.14 sec, cpu time: 0.03 sec, memory peak: 8 Mb, absolute service time: 0.15 sec