1package hashtable
2
3import (
4	"github.com/timtadh/data-structures/tree/avl"
5	. "github.com/timtadh/data-structures/types"
6)
7
8const (
9	UTILIZATION       = .75
10	RECORDS_PER_BLOCK = 16
11)
12
13type bst struct {
14	hash  int
15	key   Hashable
16	value interface{}
17	left  *bst
18	right *bst
19}
20
21type LinearHash struct {
22	table []*avl.AvlNode
23	n     uint
24	r     uint
25	i     uint
26}
27
28func NewLinearHash() *LinearHash {
29	N := uint(32)
30	I := uint(5)
31	return &LinearHash{
32		table: make([]*avl.AvlNode, N),
33		n:     N,
34		r:     0,
35		i:     I,
36	}
37}
38
39func (self *LinearHash) bucket(key Hashable) uint {
40	m := uint(key.Hash() & ((1 << self.i) - 1))
41	if m < self.n {
42		return m
43	} else {
44		return m ^ (1 << (self.i - 1))
45	}
46}
47
48func (self *LinearHash) Size() int {
49	return int(self.r)
50}
51
52func (self *LinearHash) Put(key Hashable, value interface{}) (err error) {
53	var updated bool
54	bkt_idx := self.bucket(key)
55	self.table[bkt_idx], updated = self.table[bkt_idx].Put(key, value)
56	if !updated {
57		self.r += 1
58	}
59	if float64(self.r) > UTILIZATION*float64(self.n)*float64(RECORDS_PER_BLOCK) {
60		return self.split()
61	}
62	return nil
63}
64
65func (self *LinearHash) Get(key Hashable) (value interface{}, err error) {
66	bkt_idx := self.bucket(key)
67	return self.table[bkt_idx].Get(key)
68}
69
70func (self *LinearHash) Has(key Hashable) bool {
71	bkt_idx := self.bucket(key)
72	return self.table[bkt_idx].Has(key)
73}
74
75func (self *LinearHash) Remove(key Hashable) (value interface{}, err error) {
76	bkt_idx := self.bucket(key)
77	self.table[bkt_idx], value, err = self.table[bkt_idx].Remove(key)
78	if err == nil {
79		self.r -= 1
80	}
81	return
82}
83
84func (self *LinearHash) split() (err error) {
85	bkt_idx := self.n % (1 << (self.i - 1))
86	old_bkt := self.table[bkt_idx]
87	var bkt_a, bkt_b *avl.AvlNode
88	self.n += 1
89	if self.n > (1 << self.i) {
90		self.i += 1
91	}
92	for key, value, next := old_bkt.Iterate()(); next != nil; key, value, next = next() {
93		if self.bucket(key.(Hashable)) == bkt_idx {
94			bkt_a, _ = bkt_a.Put(key.(Hashable), value)
95		} else {
96			bkt_b, _ = bkt_b.Put(key.(Hashable), value)
97		}
98	}
99	self.table[bkt_idx] = bkt_a
100	self.table = append(self.table, bkt_b)
101	return nil
102}
103
104func (self *LinearHash) Iterate() KVIterator {
105	table := self.table
106	i := 0
107	iter := table[i].Iterate()
108	var kv_iterator KVIterator
109	kv_iterator = func() (key Hashable, val interface{}, next KVIterator) {
110		key, val, iter = iter()
111		for iter == nil {
112			i++
113			if i >= len(table) {
114				return nil, nil, nil
115			}
116			key, val, iter = table[i].Iterate()()
117		}
118		return key, val, kv_iterator
119	}
120	return kv_iterator
121}
122
123func (self *LinearHash) Items() (vi KIterator) {
124	return MakeItemsIterator(self)
125}
126
127func (self *LinearHash) Keys() KIterator {
128	return MakeKeysIterator(self)
129}
130
131func (self *LinearHash) Values() Iterator {
132	return MakeValuesIterator(self)
133}
134