btreeset.gno

  1package btreeset
  2
  3type bTreeSet struct {
  4	degree    int
  5	size      int
  6	root      *node
  7	iterating int
  8}
  9
 10func newBTreeSet(degree int) *bTreeSet {
 11	if degree <= 1 {
 12		panic("degree must be greater than 1")
 13	}
 14	return &bTreeSet{degree: degree}
 15}
 16
 17func (t *bTreeSet) maxKeys() int { return t.degree*2 - 1 }
 18func (t *bTreeSet) minKeys() int { return t.degree - 1 }
 19func (t *bTreeSet) Size() int    { return t.size }
 20
 21func (t *bTreeSet) Set(key key) (existed bool) {
 22	t.assertNotIterating()
 23
 24	maxKeys := t.degree*2 - 1
 25	if t.root == nil {
 26		t.root = newNodeWithEntry(key, maxKeys)
 27		t.size = 1
 28		return false
 29	}
 30
 31	if t.root.has(key) {
 32		return true
 33	}
 34
 35	if t.root.size() >= maxKeys {
 36		t.splitRoot(maxKeys, t.root.lastKey().Less(key))
 37	}
 38
 39	inserted := t.root.setNonFull(key, maxKeys)
 40	if inserted {
 41		t.size++
 42	}
 43
 44	return !inserted
 45}
 46
 47func (t *bTreeSet) splitRoot(maxKeys int, appendSplit bool) {
 48	newRoot := newNode(maxKeys)
 49	newRoot.children = []*node{t.root}
 50	newRoot.split(0, maxKeys, appendSplit)
 51	t.root = newRoot
 52}
 53
 54func (t *bTreeSet) Has(key key) bool {
 55	if t.root == nil {
 56		return false
 57	}
 58
 59	return t.root.has(key)
 60}
 61
 62func (t *bTreeSet) Remove(key key) (removed bool) {
 63	t.assertNotIterating()
 64
 65	if t.root == nil {
 66		return false
 67	}
 68
 69	removed = t.root.remove(key, t.minKeys())
 70	if !removed {
 71		return false
 72	}
 73
 74	t.size--
 75
 76	if t.root.size() == 0 && !t.root.isLeaf() {
 77		t.root = t.root.firstChild()
 78	} else if t.root.size() == 0 {
 79		t.root = nil
 80	}
 81
 82	return true
 83}
 84
 85func (t *bTreeSet) GetByIndex(index int) key {
 86	if t.root == nil || index < 0 || index >= t.size {
 87		panic("GetByIndex asked for invalid index")
 88	}
 89	return t.root.getByIndex(index)
 90}
 91
 92// Iterate visits keys in ascending order over [start, end).
 93// A nil start means no lower bound, and a nil end means no upper bound.
 94func (t *bTreeSet) Iterate(start, end key, cb iterCbFn) bool {
 95	t.assertNotIteratingForIteration()
 96	if t.root == nil {
 97		return false
 98	}
 99	t.beginIteration()
100	defer t.endIteration()
101	return t.root.iterate(start, end, cb)
102}
103
104// ReverseIterate visits keys in descending order over (start, end].
105// A nil start means no lower bound, and a nil end means no upper bound.
106func (t *bTreeSet) ReverseIterate(start, end key, cb iterCbFn) bool {
107	t.assertNotIteratingForIteration()
108	if t.root == nil {
109		return false
110	}
111	t.beginIteration()
112	defer t.endIteration()
113	return t.root.reverseIterate(start, end, cb)
114}
115
116func (t *bTreeSet) IterateByOffset(offset int, count int, cb iterCbFn) bool {
117	t.assertNotIteratingForIteration()
118	if t.root == nil || offset < 0 || offset >= t.size || count <= 0 {
119		return false
120	}
121	seen := 0
122	visited := 0
123	t.beginIteration()
124	defer t.endIteration()
125	return t.root.iterateByOffset(offset, count, false, &seen, &visited, cb)
126}
127
128func (t *bTreeSet) ReverseIterateByOffset(offset int, count int, cb iterCbFn) bool {
129	t.assertNotIteratingForIteration()
130	if t.root == nil || offset < 0 || offset >= t.size || count <= 0 {
131		return false
132	}
133	seen := 0
134	visited := 0
135	t.beginIteration()
136	defer t.endIteration()
137	return t.root.iterateByOffset(offset, count, true, &seen, &visited, cb)
138}
139
140func (t *bTreeSet) beginIteration() {
141	t.iterating++
142}
143
144func (t *bTreeSet) endIteration() {
145	t.iterating--
146}
147
148func (t *bTreeSet) assertNotIterating() {
149	if t.iterating > 0 {
150		panic("btreeset mutation during iteration")
151	}
152}
153
154func (t *bTreeSet) assertNotIteratingForIteration() {
155	if t.iterating > 0 {
156		panic("btreeset iteration during iteration")
157	}
158}