1package arbo
  2
  3import (
  4	"bytes"
  5	"fmt"
  6)
  7
  8type node struct {
  9	l    *node
 10	r    *node
 11	k    []byte
 12	v    []byte
 13	path []bool
 14	h    []byte
 15}
 16
 17type params struct {
 18	maxLevels    int
 19	hashFunction HashFunction
 20	emptyHash    []byte
 21}
 22
 23// vt stands for virtual tree. It's a tree that does not have any computed hash
 24// while placing the leafs. Once all the leafs are placed, it computes all the
 25// hashes. In this way, each node hash is only computed one time.
 26type vt struct {
 27	root   *node
 28	params *params
 29}
 30
 31func newVT(maxLevels int, hash HashFunction) vt {
 32	return vt{
 33		root: nil,
 34		params: &params{
 35			maxLevels:    maxLevels,
 36			hashFunction: hash,
 37			emptyHash:    make([]byte, hash.Len()), // empty
 38		},
 39	}
 40}
 41
 42func (t *vt) add(k, v []byte) error {
 43	leaf := newLeafNode(t.params, k, v)
 44	if t.root == nil {
 45		t.root = leaf
 46		return nil
 47	}
 48
 49	if err := t.root.add(t.params, 0, leaf); err != nil {
 50		return err
 51	}
 52
 53	return nil
 54}
 55
 56func newLeafNode(p *params, k, v []byte) *node {
 57	keyPath := make([]byte, p.hashFunction.Len())
 58	copy(keyPath[:], k)
 59	path := getPath(p.maxLevels, keyPath)
 60	n := &node{
 61		k:    k,
 62		v:    v,
 63		path: path,
 64	}
 65	return n
 66}
 67
 68type virtualNodeType int
 69
 70const (
 71	vtEmpty = 0 // for convenience uses same value that PrefixValueEmpty
 72	vtLeaf  = 1 // for convenience uses same value that PrefixValueLeaf
 73	vtMid   = 2 // for convenience uses same value that PrefixValueIntermediate
 74)
 75
 76func (n *node) typ() virtualNodeType {
 77	if n.l == nil && n.r == nil && n.k != nil {
 78		return vtLeaf
 79	}
 80	if n.l != nil || n.r != nil {
 81		return vtMid
 82	}
 83	return vtEmpty
 84}
 85
 86func (n *node) add(p *params, currLvl int, leaf *node) error {
 87	if currLvl > p.maxLevels-1 {
 88		return fmt.Errorf("max virtual level %d", currLvl)
 89	}
 90
 91	if n == nil {
 92		// n = leaf // TMP!
 93		return nil
 94	}
 95
 96	t := n.typ()
 97	switch t {
 98	case vtMid:
 99		if leaf.path[currLvl] {
100			//right
101			if n.r == nil {
102				// empty sub-node, add the leaf here
103				n.r = leaf
104			}
105			if err := n.r.add(p, currLvl+1, leaf); err != nil {
106				return err
107			}
108		} else {
109			if n.l == nil {
110				// empty sub-node, add the leaf here
111				n.l = leaf
112			}
113			if err := n.l.add(p, currLvl+1, leaf); err != nil {
114				return err
115			}
116		}
117	case vtLeaf:
118		if bytes.Equal(n.k, leaf.k) {
119			return fmt.Errorf("key already exists")
120		}
121
122		oldLeaf := &node{
123			k:    n.k,
124			v:    n.v,
125			path: n.path,
126		}
127		// remove values from current node (converting it to mid node)
128		n.k = nil
129		n.v = nil
130		n.path = nil
131		if err := n.downUntilDivergence(p, currLvl, oldLeaf, leaf); err != nil {
132			return err
133		}
134	default:
135		return fmt.Errorf("ERR")
136	}
137
138	return nil
139}
140
141func (n *node) downUntilDivergence(p *params, currLvl int, oldLeaf, newLeaf *node) error {
142	if currLvl > p.maxLevels-1 {
143		return fmt.Errorf("max virtual level %d", currLvl)
144	}
145
146	// if oldLeaf.path[currLvl+1] != newLeaf.path[currLvl+1] {
147	if oldLeaf.path[currLvl] != newLeaf.path[currLvl] {
148		// reached divergence in next level
149		// if newLeaf.path[currLvl+1] {
150		if newLeaf.path[currLvl] {
151			n.l = oldLeaf
152			n.r = newLeaf
153		} else {
154			n.l = newLeaf
155			n.r = oldLeaf
156		}
157		return nil
158	}
159	// no divergence yet, continue going down
160	if newLeaf.path[currLvl] {
161		// right
162		n.r = &node{}
163		if err := n.r.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
164			return err
165		}
166	} else {
167		// left
168		n.l = &node{}
169		if err := n.l.downUntilDivergence(p, currLvl+1, oldLeaf, newLeaf); err != nil {
170			return err
171		}
172	}
173
174	return nil
175}
176
177func (n *node) computeHashes() ([]kv, error) {
178	return nil, nil
179}