btree.py

#!/usr/bin/env python

# FIXME: write code

hashtable.py

#!/usr/bin/env python

import hashlib

class HashTable:

    def __init__(self, hash_size = 8): 
        self._hash = HashGenerator()
        self._hash_size = hash_size
        self._table = [ ChainList() for i in range(0, self._hash_size) ]
    
    def show(self):
        for cl in self._table:
            print('-'.join(map(str, cl)))

    def insert(self, obj):
        key = self._generate_key(obj)
        pair = Pair(key, obj)
        self._set(pair)

    def delete(self, obj):
        key = self._generate_key(obj)
        # FIXME: YATTSUKE
        pair = Pair(key, obj)
        self._delete(pair)

    def search(self, key):
        print 'search'

    def _get_index(self, key):
        return key % self._hash_size

    def _generate_key(self, obj):
        return self._hash.digest(obj)

    def _set(self, pair):
        index = self._get_index(pair.key)
        print index
        self._table[index].append(pair)

    def _delete(self, pair):
        index = self._get_index(pair.key)
        self._table[index].remove(pair)

class HashGenerator:
    def __init__(self, hashfunc = hashlib.sha1):
        self._hashfunc = hashfunc

    def digest(self, obj):
        return int(self._hashfunc(str(id(obj))).hexdigest(),16)


class Pair:

    def __init__(self, key, value):
        self.key = key
        self.value = value


class ChainList:

    def __init__(self):
        self._nodes = []
        self._index = 0

    def append(self, pair):
        # FIXME : implement without list && this is YATTSUKE implementation!
        p = self.search(pair.key)
        if p == None:
            self._nodes.append(pair)

    def remove(self, pair):
        # FIXME : O(M) implementation when M is the length of hashchain.
        p = self.search(pair.key)
        if p:
            self._nodes.remove(p)

    def search(self, key):
        for p in self._nodes:
            if p.key == key:
                return p

    def show(self):
        ','.join(map(str,self._nodes))

    def __iter__(self):
        return self

    def next(self):
        i = self._index
        size = len(self._nodes)
        if size <= 0:
            raise StopIteration
        elif i >= size:
            index = 0
            raise StopIteration

        pair = self._nodes[i]
        ret = [pair.key, pair.value]
        self._index += 1

        return ret


#h = HashGenerator()
#digest = h.digest('hoge')
#print(digest)

#l = ChainList()
#l.append('hoge')
#l.append('huga')
#l.remove('huga')
#l.show()

t = HashTable()
t.show()
s = 'hoge'
t.insert(s)
t.insert(s)
t.insert(s)
t.show()

t.delete(s)
t.show()

for x in range(1,1024):
    t.insert(x)

t.show()