Adaptation of the libstdc++ unordered_set implementation

_hashset.py

# "Internal policy header for TR1 unordered_set and unordered_map"

# A VERY approximate adaptation to Python by 6.006 staff. Original file at:
# https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a01895.html
#  If you want something tricky to gnaw on, take a look at the original C++ implementation
# Among other things, we stripped out code that does caching, error handling, and more.

# This library is free software; you can redistribute it and/or modify it under the
# terms of the GNU General Public License as published by the
# Free Software Foundation; either version 2, or any later version.

import hashset_sizing_policy

class _HashSet:
    class _HashNode:
       def __init__(self, __num):
            self.__next = None
            self.__num = __num

        def __set_next(self, next)
            self.__next = next

    def __init__(self):
       self.table = [None] * hashset_sizing_policy.sizes[0]
       self.element_count = 0
       self.load_factor = 0.9

    # Default range hashing function: use division to fold a large number
    # into the range [0, N).

    
    class _Mod_range_hashing:
        @staticmethod
        def operator(__num, __den):
            return __num % __den;
    
    @staticmethod
    def __insert_table(table, num):
        ''' must check to have sufficient space before calling '''
        idx = _Mod_range_hashing.operator(num, len(new_alloc))
        if new_alloc[idx]:
            last_node = get_last_node_in_chain(new_alloc[idx])
            last_node.next = _HashNode(__num)
        else:
            new_alloc[idx] = _HashNode(__num)

    def insert(self, __num):
        if (element_count+1) > load_factor*len(table):
            # Table is full, time to re-allocate and re-hash
            new_alloc = [None]*hashset_sizing_policy.get_next_larger_size(len(self.table))
            for elm in self.table:
                if elm != None: __insert_table(new_alloc, elm)
            self.alloc = new_alloc
        else:
            __insert_table(self.alloc, __num)


    def delete(self, __num):
        pass # not translated