root/trunk/Library/SkipList.fss

Revision 4130, 30.9 KB (checked in by sukyoungryu, 3 months ago)

[disambiguator] Fixed handling getters and setters in ExprDisambiguator?. Fixed libraries and tests using getters.
Line 
1(*******************************************************************************
2    Copyright 2009 Sun Microsystems, Inc.,
3    4150 Network Circle, Santa Clara, California 95054, U.S.A.
4    All rights reserved.
5
6    U.S. Government Rights - Commercial software.
7    Government users are subject to the Sun Microsystems, Inc. standard
8    license agreement and applicable provisions of the FAR and its supplements.
9
10    Use is subject to license terms.
11
12    This distribution may include materials developed by third parties.
13
14    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
15    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
16 ******************************************************************************)
17
18component SkipList
19import PureList.{...}
20export SkipList
21
22(*****************************************************************************
23   An implementation of Skip Lists, based on Pugh, William (June 1990).
24   "Skip lists: a probabilistic alternative to balanced trees". Communications
25   of the ACM 33: 668-676. The expected time for searching, inserting, or deleting
26   a key-element pair is O(log n). Skip Lists are represented here in a tree
27   structure, based on Xavier Messeguer (1997). "Skip Trees, an Alternative Data
28   Structure to Skip Lists in a Concurrent Approach". ITA 31(3): 251-269.
29
30   A skip tree is a variant of a B-tree.  It shares the B-tree property that
31   every path from the root to a leaf has the same length.  Every node contains
32   some number of keys (n) and exactly n + 1 children nodes. Skip trees do not
33   share the B-tree property of a minimum or a maximum number of keys per node.
34   All leaves live in level 0 of the tree, and values are stored only in the leaf
35   nodes.
36
37   This implementation of skip trees supports multiple values for a unique key.
38   If a key contains multiple values, then an arbitrary value is returned on
39   a search for that key.
40
41***************************************************************************)
42
43(* A SkipList type consists of a root node and pInverse = 1/p, where the fraction
44   p is used in the negative binomial distribution to select random levels for insertion.
45*)
46object SkipList[\Key,Val,nat pInverse\](root:Node[\Key,Val\])
47
48  p:RR64 = 1.0 / pInverse
49
50  getter asString():String = root.asString
51
52  (* The number of values stored. *)
53  getter size():ZZ32 = |root|
54  opr |self| : ZZ32 = |root|
55
56  (* Given a key, try to return a value that matches that key. *)
57  search(k:Key):Maybe[\Val\] = root.search(k)
58
59  (* Add a (key, value) pair. *)
60  add(k:Key, v:Val):SkipList[\Key,Val,pInverse\] = do
61    level:ZZ32 = randomLevel()
62    values:Array[\Val,ZZ32\] = array[\Val\](1)
63    values[0] := v
64    leaf:LeafNode[\Key,Val\] = LeafNode[\Key,Val\](k, values)
65    SkipList[\Key,Val,pInverse\](root.add(leaf, level))
66  end
67
68  (* Remove a (key, value) pair. *)
69  remove(k:Key):SkipList[\Key,Val,pInverse\] = do
70    (root', maybe) = root.remove(k)
71    SkipList[\Key,Val,pInverse\](root')
72  end
73
74  (* Merge two Skip Lists. *)
75  merge(other:SkipList[\Key,Val,pInverse\]):SkipList[\Key,Val,pInverse\] = do
76    (larger, smaller) = if |self| > |other| then (self, other) else (other, self) end
77    smallList = singleton[\Node[\Key,Val\]\](smaller.root)
78    SkipList[\Key,Val,pInverse\](larger.root.merge(smallList))
79  end
80
81  (* Return a random level >= 1 with a negative binomial distribution. *)
82  randomLevel():ZZ32 = do
83    level':ZZ32 := 1
84    while random(1.0) < p do
85      level' += 1
86    end
87    level'
88  end
89
90end
91
92(* Construct an empty Skip List. *)
93NewList[\Key,Val,nat pInverse\]():SkipList[\Key,Val,pInverse\] =
94  SkipList[\Key,Val,pInverse\](EmptyNode[\Key,Val\])
95
96
97(* A Node is the basic type for the Skip List data structure.
98   There are four types of Nodes:
99    i)   Empty Nodes - represents an empty tree.
100    ii)  Leaf Nodes - stores a (key,val) pair. Lives at the bottom of the tree.
101    iii) Internal Nodes - stores N keys and N+1 children for N > 0.
102    iv)  White Nodes - stores exactly zero keys and one child.
103*)
104trait Node[\Key,Val\]
105(*
106      comprises {EmptyNode[\Key,Val\], LeafNode[\Key,Val\],
107                 NonLeafNode[\Key,Val\],
108                 WhiteNodeHelper[\Key,Val,ChildType\]
109                     where [\ChildType extends Node[\Key,Val\]\],
110                 InternalNodeHelper[\SelfType,Key,Val,ChildType\]
111                     where [\SelfType extends InternalNodeHelper[\SelfType,Key,Val,ChildType\],
112                             ChildType extends Node[\KeyVal\]\],
113                 WhiteNode[\Key,Val\], InternalNode[\Key,Val\]}
114*)
115
116  (* The height of the current node.  Height = 0 must be a leaf *)
117  getter height():ZZ32
118
119  (* Deprecated.  Use |size| *)
120  getter size():ZZ32
121
122  (* The number of values stores in this subtree.  The number of
123     values is greater than or equal to the number of keys,
124     as duplicates are allowed in this implementation. *)
125  opr |self| : ZZ32
126
127  (* given a search key, try to return a value that matches that key *)
128  search(k:Key):Maybe[\Val\]
129
130  (* toGraphViz():String   wait until hashCode() is implemented*)
131
132  (* the add method will grow the tree if level > root height *)
133  add(leaf:LeafNode[\Key,Val\], level:ZZ32):Node[\Key,Val\]
134
135  (* the add_helper method is only invoked if level <= root height *)
136  (* returns the new node and whether a new key was inserted *)
137  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):(Node[\Key,Val\], Boolean)
138
139  (* perform a search operation, and remove a value if it is found *)
140  remove(k:Key):(Node[\Key,Val\],Maybe[\Val\])
141
142  (* merge must always be invoked with at least one element in the merge list *)
143  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\]
144
145  (* return the list of leaves that are under the current subtree *)
146  getLeaves():List[\LeafNode[\Key,Val\]\]
147
148end
149
150
151(* There are two types of white nodes:
152    a) WhiteLevel1 are white nodes that live at level 1 of the tree.  Their children are leaves.
153    b) WhiteLevelN are white nodes that live at level > 1 of the tree. Their children are non-leaves. *)
154trait WhiteNode[\Key,Val\]
155      extends Node[\Key,Val\]
156      excludes InternalNode[\Key,Val\]
157      comprises {WhiteLevel1[\Key,Val\], WhiteLevelN[\Key,Val\]}
158end
159
160(* There are two types of internal nodes:
161    a) InternalLevel1 are internal nodes that live at level 1 of the tree.  Their children are leaves.
162    b) InternalLevelN are internal nodes that live at level > 1 of the tree. Their children are non-leaves. *)
163trait InternalNode[\Key,Val\]
164      extends Node[\Key,Val\]
165      excludes WhiteNode[\Key,Val\]
166      comprises {InternalLevel1[\Key,Val\], InternalLevelN[\Key, Val\]}
167end
168
169(* There are four types of NonLeafNodes and they are the union of the WhiteNode types and InternalNode types *)
170trait NonLeafNode[\Key,Val\]
171      extends Node[\Key,Val\]
172      comprises {WhiteLevel1[\Key,Val\], WhiteLevelN[\Key,Val\],
173                 InternalLevel1[\Key,Val\], InternalLevelN[\Key, Val\]}
174end
175
176(* WhiteNodeHelper is the trait that is used to distinguish between WhiteLevel1 and WhiteLevelN *)
177trait WhiteNodeHelper[\Key,Val,ChildType extends Node[\Key,Val\]\]
178      extends Node[\Key,Val\]
179      comprises {WhiteLevel1[\Key,Val\], WhiteLevelN[\Key,Val\]}
180
181  getter child():ChildType
182  getter size():ZZ32 = |self.child|
183  getter height():ZZ32 = self.child.height + 1
184  getter asString():String = "{ [], [" self.child.asString "] }"
185
186  opr |self| : ZZ32 = |self.child|
187
188  search(k:Key):Maybe[\Val\] = self.child.search(k)
189
190  add(leaf:LeafNode[\Key,Val\], level:ZZ32):Node[\Key,Val\] = do
191    tail:Node[\Key,Val\] = generate_tail[\Key,Val\](self, level - self.height)
192    (newNode, newKey) = tail.add_helper(leaf, level)
193    newNode
194  end
195
196  getLeaves():List[\LeafNode[\Key,Val\]\] = self.child.getLeaves()
197
198end
199
200(* InternalNodeHelper is the trait that is used to distinguish between InternalLevel1 and InternalLevelN *)
201trait InternalNodeHelper[\SelfType extends InternalNodeHelper[\SelfType,Key,Val,ChildType\],Key,Val,ChildType extends Node[\Key,Val\]\]
202      extends Node[\Key,Val\]
203      comprises {InternalLevel1[\Key,Val\], InternalLevelN[\Key,Val\]}
204
205  getter keys():Array[\Key,ZZ32\]
206  getter children():Array[\ChildType,ZZ32\]
207
208  getter size():ZZ32 = |self|
209
210  getter height():ZZ32 = self.children[0].height + 1
211
212  getter asString():String = "{" self.keys.asString ", " self.children.asString "}"
213
214  opr |self| : ZZ32 = SUM [node <- self.children] |node|
215
216  (* given an instance of SelfType, generate a singleton SelfType *)
217  singleton(keys':Array[\Key,ZZ32\], children':Array[\ChildType,ZZ32\]) : SelfType
218
219  (* given a key k, return the largest offset with a value less than or equal to k *)
220  find_index(k:Key):ZZ32 = do
221    index:ZZ32 := 0
222    while (index < |self.keys| AND: k >= self.keys[index]) do
223      index += 1
224    end
225    index
226  end
227
228  search(k:Key):Maybe[\Val\] = do
229    index:ZZ32 = find_index(k)
230    self.children[index].search(k)
231  end
232
233  add(leaf:LeafNode[\Key,Val\], level:ZZ32):Node[\Key,Val\] = do
234    tail:Node[\Key,Val\] = generate_tail[\Key,Val\](self, level - self.height)
235    (newNode, newKey) = tail.add_helper(leaf, level)
236    newNode
237  end
238
239  getLeaves():List[\LeafNode[\Key,Val\]\] = self.children.generate[\List[\LeafNode[\Key,Val\]\]\](
240    Concat[\LeafNode[\Key,Val\]\],
241    fn (node:Node[\Key,Val\]): List[\LeafNode[\Key,Val\]\] => node.getLeaves())
242
243  (* break this internal node.
244     Returns the two halves along with an key array of size quantity used for splitting.
245     The values array is of size quantitiy - 1. *)
246  break(quantity:ZZ32):(NonLeafNode[\Key,Val\],NonLeafNode[\Key,Val\],Array[\Key,ZZ32\],Array[\NonLeafNode[\Key,Val\],ZZ32\]) =
247  if |self.keys| = quantity then
248    onekey_break(quantity)
249  elif |self.keys| - 1 = quantity then
250    twokeys_break(quantity)
251  else
252    nkeys_break(quantity)
253  end
254
255  (* perform the break operation when we have a key count of quantity *)
256  onekey_break(quantity:ZZ32):(NonLeafNode[\Key,Val\],NonLeafNode[\Key,Val\],Array[\Key,ZZ32\],Array[\NonLeafNode[\Key,Val\],ZZ32\]) = do
257    keys':Array[\Key,ZZ32\] = self.keys.copy()
258    children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](|self.keys| - 1)
259    for i <- 0 # |children'| do
260      children'[i] := generate_tail[\Key,Val\](self.children[i + 1], 1)
261    end
262    smaller:Node[\Key,Val\] = self.children[0]
263    larger:Node[\Key,Val\] = self.children[|self.children| - 1]
264    left:NonLeafNode[\Key,Val\] = generate_tail[\Key,Val\](smaller, 1)
265    right:NonLeafNode[\Key,Val\] = generate_tail[\Key,Val\](larger, 1)
266    (left, right, keys', children')
267  end
268
269  (* perform the break operation when we have a key count of (quantity + 1) *)
270  twokeys_break(quantity:ZZ32):(NonLeafNode[\Key,Val\],NonLeafNode[\Key,Val\],Array[\Key,ZZ32\],Array[\NonLeafNode[\Key,Val\],ZZ32\]) = do
271    smaller:Node[\Key,Val\] = self.children[0]
272    keys':Array[\Key,ZZ32\] = self.keys[0 # (|self.keys| - 1)]
273    children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](|self.keys| - 2)
274    for i <- children'.indices do
275      children'[i] := generate_tail[\Key,Val\](self.children[i + 1], 1)
276    end
277    rkeys:Array[\Key,ZZ32\] = array[\Key\](1)
278    rchildren:Array[\ChildType,ZZ32\] = array[\ChildType\](2)
279    rkeys[0] := self.keys[|self.keys| - 1]
280    rchildren[0#2] := self.children[(|self.keys| - 1) # 2]
281    left:NonLeafNode[\Key,Val\] = generate_tail[\Key,Val\](smaller, 1)
282    right:NonLeafNode[\Key,Val\] = singleton(rkeys,rchildren)
283    (left, right, keys', children')
284  end
285
286  (* perform the break operation when we have a key count > (quantity + 1) *)
287  nkeys_break(quantity:ZZ32):(NonLeafNode[\Key,Val\],NonLeafNode[\Key,Val\],Array[\Key,ZZ32\],Array[\NonLeafNode[\Key,Val\],ZZ32\]) = do
288    leftovers:ZZ32 = |self.keys| - quantity
289    lsize:ZZ32 = leftovers DIV 2
290    rsize:ZZ32 = leftovers - lsize
291    (* make the left child *)
292    lkeys:Array[\Key,ZZ32\] = array[\Key\](lsize)
293    lchildren:Array[\ChildType,ZZ32\] = array[\ChildType\](lsize + 1)
294    lkeys[0 # lsize] := self.keys[0 # lsize]
295    lchildren[0 # (lsize + 1)] := self.children[0 # (lsize + 1)]
296    left:NonLeafNode[\Key,Val\] = singleton(lkeys,lchildren)
297    (* make the right child *)
298    rkeys:Array[\Key,ZZ32\] = array[\Key\](rsize)
299    rchildren:Array[\ChildType,ZZ32\] = array[\ChildType\](rsize + 1)
300    rkeys[0 # rsize] := self.keys[(|self.keys| - rsize) # rsize]
301    rchildren[0 # (rsize + 1)] := self.children[(|self.keys| - rsize) # (rsize + 1)]
302    right:NonLeafNode[\Key,Val\] = singleton(rkeys,rchildren)
303    (* make the center child *)
304    keys':Array[\Key,ZZ32\] = self.keys[lsize # quantity]
305    children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](quantity - 1)
306    for i <- children'.indices do
307      children'[i] := generate_tail[\Key,Val\](self.children[i + lsize + 1], 1)
308    end
309    (left, right, keys', children')
310  end
311
312  (* return a new internal node that has self.children[index] and self.keys[index - 1] missing *)
313  index_remove(index:ZZ32): SelfType = do
314    keys':Array[\Key,ZZ32\] = array[\Key\](|self.keys| - 1)
315    children':Array[\ChildType,ZZ32\] = array[\ChildType\](|self.children| - 1)
316    replace:ZZ32 = 0 MAX (index - 1)
317    keys'[0 # replace] := self.keys[0 # replace]
318    keys'[replace # (|keys'| - replace)] := self.keys[(replace + 1) # (|keys'| - replace)]
319    children'[0 # index] := self.children[0 # index]
320    children'[index # (|children'| - index)] := self.children[(index + 1) # (|children'| - index)]
321    singleton(keys', children')
322  end
323
324end
325
326(* Helper function to generate a tail of white nodes coming off a leaf node *)
327generate_tail[\Key,Val\](node:LeafNode[\Key,Val\], length:ZZ32):Node[\Key,Val\] =
328if length > 0 then
329  generate_tail[\Key,Val\](WhiteLevel1[\Key,Val\](node), length - 1)
330else
331  node
332end
333
334(* Helper function to generate a tail of white nodes coming off a non leaf node *)
335generate_tail[\Key,Val\](node:NonLeafNode[\Key,Val\], length:ZZ32):Node[\Key,Val\] =
336if length > 0 then
337  generate_tail[\Key,Val\](WhiteLevelN[\Key,Val\](node), length - 1)
338else
339  node
340end
341
342(* A white node stores exactly zero keys and contains one child. White nodes are
343   used as placeholders to keep the height of all branches identical. A white node
344   has a height > 0 *)
345object WhiteLevel1[\Key,Val\](child:LeafNode[\Key,Val\])
346       extends {WhiteNode[\Key,Val\],
347                WhiteNodeHelper[\Key,Val,LeafNode[\Key,Val\]\],
348                NonLeafNode[\Key,Val\]}
349
350  getter child():LeafNode[\Key,Val\] = child
351
352  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):(Node[\Key,Val\], Boolean) = do
353    k:Key = leaf.key
354    k':Key = child.key
355    if k = k' then
356      values:Array[\Val,ZZ32\] = array[\Val\](|leaf.values| + |child.values|)
357      values[0 # |leaf.values|] := leaf.values[0 # |leaf.values|]
358      values[|leaf.values| # |child.values|] := child.values[#]
359      newleaf:LeafNode[\Key,Val\] = LeafNode[\Key,Val\](k, values)
360      (WhiteLevel1[\Key,Val\](newleaf), false)
361    else
362      keys:Array[\Key,ZZ32\] = array[\Key\](1)
363      children:Array[\LeafNode[\Key,Val\],ZZ32\] = array[\LeafNode[\Key,Val\]\](2)
364      (smaller,larger,lkey) = if k > k' then (child,leaf,k) else (leaf,child,k') end
365      keys[0] := lkey
366      children[0] := smaller
367      children[1] := larger
368      (InternalLevel1[\Key,Val\](keys,children), true)
369    end
370  end
371
372  remove(k:Key):(Node[\Key,Val\],Maybe[\Val\]) = do
373    if child.getKey() = k then
374      if |child.values| = 1 then
375        (EmptyNode[\Key,Val\], Just[\Val\](child.values[0]))
376      else
377        values:Array[\Val,ZZ32\] = array[\Val\](|child.values| - 1)
378        values[#] := child.values[0 # |values|]
379        newLeaf = LeafNode[\Key,Val\](k, values)
380        (WhiteLevel1[\Key,Val\](newLeaf), Just[\Val\](child.values[|values|]))
381      end
382    else
383      (self, Nothing[\Val\])
384    end
385  end
386
387  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] =
388    height1_merge_leaves(nodes.generate[\List[\LeafNode[\Key,Val\]\]\](
389      Concat[\LeafNode[\Key,Val\]\],
390      fn (node:Node[\Key,Val\]): List[\LeafNode[\Key,Val\]\] => node.getLeaves()))
391
392  (* helper function for height1_merge where nodes is a list of all leaves *)
393  height1_merge_leaves(nodes:List[\LeafNode[\Key,Val\]\]):Node[\Key,Val\] = do
394    (* TODO: A bulk insert could be implemented that does not used serialized single inserts *)
395    newNode:Node[\Key,Val\] := self
396    for leaf <- seq(nodes) do
397      (tempNode, newKey) = newNode.add_helper(leaf, 1)
398      newNode := tempNode
399    end
400    newNode
401  end
402
403end
404
405
406(* A white node stores exactly zero keys and contains one child. White nodes are
407   used as placeholders to keep the height of all branches identical. A white node
408   has a height > 0 *)
409object WhiteLevelN[\Key,Val\](child:NonLeafNode[\Key,Val\])
410       extends {WhiteNode[\Key,Val\],
411                WhiteNodeHelper[\Key,Val,NonLeafNode[\Key,Val\]\],
412                NonLeafNode[\Key,Val\]}
413
414  getter child():NonLeafNode[\Key,Val\] = child
415
416  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):(Node[\Key,Val\], Boolean) = do
417    (child':Node[\Key,Val\], newKey:Boolean) = child.add_helper(leaf,level)
418    if level < self.height OR newKey = false then
419      (WhiteLevelN[\Key,Val\](child'), newKey)
420    else
421      (split(0, 1, child'), newKey)
422    end
423  end
424
425  remove(k:Key):(Node[\Key,Val\],Maybe[\Val\]) = do
426    (child':Node[\Key,Val\], maybe:Maybe[\Val\]) = child.remove(k)
427    if instanceOf[\EmptyNode[\Key,Val\]\](child') then
428      (child', maybe)
429    else
430      (WhiteLevelN[\Key,Val\](child'), maybe)
431    end
432  end
433
434  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] = WhiteLevelN[\Key,Val\](child.merge(nodes))
435
436  (* breaks the new child and sucks the split keys to this level *)
437  split(index:ZZ32, quantity:ZZ32, heir:InternalNode[\Key,Val\]):InternalLevelN[\Key,Val\] = do
438    children:Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](quantity + 1)
439    (left, right, keys, children') = heir.break(quantity)
440    children[0] := left
441    children[1 # |children'|] := children'[#]
442    children[|children| - 1] := right
443    InternalLevelN[\Key,Val\](keys,children)
444  end
445
446end
447
448(* An internal node stores N keys and N + 1 children where N > 0.
449   An internal nodes has a height > 0. *)
450object InternalLevel1[\Key,Val\](keys:Array[\Key,ZZ32\],
451                                 children:Array[\LeafNode[\Key,Val\],ZZ32\])
452       extends {InternalNode[\Key,Val\],
453                InternalNodeHelper[\InternalLevel1[\Key,Val\],Key,Val,LeafNode[\Key,Val\]\],
454                NonLeafNode[\Key,Val\]}
455
456  getter keys():Array[\Key,ZZ32\] = keys
457  getter children():Array[\LeafNode[\Key,Val\],ZZ32\] = children
458
459  singleton(keys':Array[\Key,ZZ32\], children':Array[\LeafNode[\Key,Val\],ZZ32\]) : InternalLevel1[\Key,Val\] = InternalLevel1[\Key,Val\](keys',children')
460
461  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):(Node[\Key,Val\],Boolean) = do
462    index:ZZ32 = find_index(leaf.getKey())
463    if children[index].getKey() = leaf.getKey() then
464      values:Array[\Val,ZZ32\] = array[\Val\](|leaf.values| + |children[index].values|)
465      values[0 # |leaf.values|] := leaf.values[#]
466      values[|leaf.values| # |children[index].values|] := children[index].values[#]
467      newleaf:LeafNode[\Key,Val\] = LeafNode[\Key,Val\](leaf.getKey(), values)
468      children':Array[\LeafNode[\Key,Val\],ZZ32\] = children.copy()
469      children'[index] := newleaf
470      (InternalLevel1[\Key,Val\](keys,children'), false)
471    else
472      keys':Array[\Key,ZZ32\] = array[\Key\](|keys| + 1)
473      children':Array[\LeafNode[\Key,Val\],ZZ32\] = array[\LeafNode[\Key,Val\]\](|children| + 1)
474      keysplit:ZZ32 = |keys| - index
475      (smaller,larger) = if leaf.getKey() > children[index].getKey() then (children[index], leaf) else (leaf, children[index]) end
476      children'[index] := smaller
477      children'[index + 1] := larger
478      children'[0 # index] := children[0 # index]
479      children'[(index + 2) # keysplit] := children[(index + 1) # keysplit]
480      keys'[index] := larger.getKey()
481      keys'[0 # index] := keys[0 # index]
482      keys'[(index + 1) # keysplit] := keys[index # keysplit]
483      (InternalLevel1[\Key,Val\](keys',children'), true)
484    end
485  end
486
487  remove(k:Key):(Node[\Key,Val\],Maybe[\Val\]) = do
488    index:ZZ32 = find_index(k)
489    if children[index].getKey() = k then
490      height1_remove_helper(k, index)
491    else
492      (self, Nothing[\Val\])
493    end
494  end
495
496  height1_remove_helper(k:Key, index:ZZ32):(Node[\Key,Val\], Maybe[\Val\]) = do
497    values:Array[\Val,ZZ32\] = children[index].values
498    val:Val = values[|values| - 1]
499    if |values| > 1 then
500      values':Array[\Val,ZZ32\] = array[\Val\](|values| - 1)
501      values'[#] := values[0 # |values'|]
502      newleaf:LeafNode[\Key,Val\] = LeafNode[\Key,Val\](k, values')
503      children':Array[\LeafNode[\Key,Val\],ZZ32\] = children.copy()
504      children'[index] := newleaf
505      InternalLevel1[\Key,Val\](keys,children')
506    elif |keys| = 1 then
507      (WhiteLevel1[\Key,Val\](children[(index + 1) MOD 2]), Just[\Val\](val))
508    else
509      (index_remove(index), Just[\Val\](val))
510    end
511  end
512
513  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] =
514    height1_merge_leaves(nodes.generate[\List[\LeafNode[\Key,Val\]\]\](
515      Concat[\LeafNode[\Key,Val\]\],
516      fn (node:Node[\Key,Val\]): List[\LeafNode[\Key,Val\]\] => node.getLeaves()))
517
518  (* helper function for height1_merge where nodes is a list of all leaves *)
519  height1_merge_leaves(nodes:List[\LeafNode[\Key,Val\]\]):Node[\Key,Val\] = do
520    (* TODO: A bulk insert could be implemented that does not used serialized single inserts *)
521    newNode:Node[\Key,Val\] := self
522    for leaf <- seq(nodes) do
523      (tempNode, newKey) = newNode.add_helper(leaf, 1)
524      newNode := tempNode
525    end
526    newNode
527  end
528
529
530end
531
532(* An internal node stores N keys and N + 1 children where N > 0.
533   An internal nodes has a height > 0. *)
534object InternalLevelN[\Key,Val\](keys:Array[\Key,ZZ32\],
535                                 children:Array[\NonLeafNode[\Key,Val\],ZZ32\])
536       extends {InternalNode[\Key,Val\],
537                InternalNodeHelper[\InternalLevelN[\Key,Val\],Key,Val,NonLeafNode[\Key,Val\]\],
538                NonLeafNode[\Key,Val\]}
539
540  getter keys():Array[\Key,ZZ32\] = keys
541  getter children():Array[\NonLeafNode[\Key,Val\],ZZ32\] = children
542
543  singleton(keys':Array[\Key,ZZ32\], children':Array[\NonLeafNode[\Key,Val\],ZZ32\]) : InternalLevelN[\Key,Val\] = InternalLevelN[\Key,Val\](keys',children')
544
545  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):(Node[\Key,Val\],Boolean) = do
546    index:ZZ32 = find_index(leaf.getKey())
547    (child':Node[\Key,Val\], newKey:Boolean) = children[index].add_helper(leaf, level)
548    if level < self.height OR newKey = false then
549      children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](|children|)
550      children'[0 # |children|] := children[#]
551      children'[index] := child'
552      (InternalLevelN[\Key,Val\](keys,children'), newKey)
553    else
554      (split(index, 1, child'), newKey)
555    end
556  end
557
558  remove(k:Key):(Node[\Key,Val\],Maybe[\Val\]) = do
559    index:ZZ32 = find_index(k)
560    (child':Node[\Key,Val\], maybe:Maybe[\Val\]) = children[index].remove(k)
561    if |keys| = 1 then
562      (heightn_remove_1key(index,child'), maybe)
563    else
564      (heightn_remove_nkeys(index,child'), maybe)
565    end
566  end
567
568  (* breaks the new child and sucks the split keys to this level *)
569  split(index:ZZ32, quantity:ZZ32, heir:InternalNode[\Key,Val\]):InternalLevelN[\Key,Val\] = do
570    keysplit:ZZ32 = |keys| - index
571    keys':Array[\Key,ZZ32\] = array[\Key\](|keys| + quantity)
572    children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](|children| + quantity)
573    (left, right, newkeys, newchildren) = heir.break(quantity)
574    keys'[0 # index] := keys[0 # index]
575    keys'[index # |newkeys|] := newkeys[#]
576    keys'[(index + |newkeys|) # keysplit] := keys[index # keysplit]
577    children'[0 # index] := children[0 # index]
578    children'[index] := left
579    children'[(index + 1) # |newchildren|] := newchildren[#]
580    children'[index + |newchildren| + 1] := right
581    children'[(index + |newchildren| + 2) # keysplit] := children[(index + 1) # keysplit]
582    InternalLevelN[\Key,Val\](keys',children')
583  end
584
585  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] = heightn_merge(nodes)
586
587  (* perform the remove operation when height > 1 and keys = 1 *)
588  heightn_remove_1key(index:ZZ32, child':Node[\Key,Val\]):Node[\Key,Val\] = do
589    other:ZZ32 = (index + 1) MOD 2
590    if instanceOf[\EmptyNode[\Key,Val\]\](child') then
591      WhiteLevelN[\Key,Val\](children[other])
592    else
593      keys':Array[\Key,ZZ32\] = array[\Key\](1)
594      children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](2)
595      keys'[0] := keys[0]
596      children'[index] := child'
597      children'[other] := children[other]
598      InternalLevelN[\Key,Val\](keys', children')
599    end
600  end
601
602  (* perform the remove operation when height > 1 and keys > 1 *)
603  heightn_remove_nkeys(index:ZZ32, child':Node[\Key,Val\]):Node[\Key,Val\] = do
604    if instanceOf[\EmptyNode[\Key,Val\]\](child') then
605      index_remove(index)
606    else
607      keys':Array[\Key,ZZ32\] = array[\Key\](|keys|)
608      children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](|children|)
609      keys'[0 # |keys|] := keys[#]
610      children'[0 # |children|] := children[#]
611      children'[index] := child'
612      InternalLevelN[\Key,Val\](keys', children')
613    end
614  end
615
616  (* perform the merge operation when the height is greater than one *)
617  heightn_merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] = do
618    destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\] = array[\List[\Node[\Key,Val\]\]\](|children|)
619    empty:List[\Node[\Key,Val\]\] = <|[\Node[\Key,Val\]\] |>
620    destinations.fill(empty)
621    for node <- nodes do
622      merge_destination_insert(node, destinations)
623    end
624    keys':Array[\Key,ZZ32\] = keys.copy()
625    children':Array[\NonLeafNode[\Key,Val\],ZZ32\] = array[\NonLeafNode[\Key,Val\]\](|children|)
626    for index <- children.indices do
627      if destinations[index].isEmpty then
628        children'[index] := children[index]
629      else
630        children'[index] := children[index].merge(destinations[index])
631      end
632    end
633    InternalLevelN[\Key,Val\](keys',children')
634  end
635
636  (* The following are a set of helper function for heightn_merge.
637     They try to unambiguously merge a target node into one of the children
638     of this node.  If an ambiguity occurs, then look at the children of the target node
639     and recursively repeat this process. *)
640
641  (* helper function for heightn_merge on EmptyNodes *)
642  merge_destination_insert(node:EmptyNode[\Key,Val\], destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() = ()
643
644  (* helper function for heightn_merge on LeafNodes *)
645  merge_destination_insert(node:LeafNode[\Key,Val\], destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() = do
646    index:ZZ32 = find_index(node.getKey())
647    atomic do
648      destinations[index] := destinations[index].addLeft(node)
649    end
650  end
651
652  (* helper function for heightn_merge on WhiteNodes *)
653  merge_destination_insert(node:WhiteNode[\Key,Val\], destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() = do
654    merge_destination_insert(node.child, destinations)
655  end
656
657  (* helper function for heightn_merge on InternalNodes *)
658  merge_destination_insert(node:InternalNode[\Key,Val\], destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() = do
659    for index <- node.children.indices do
660      merge_destination_insert_helper(node, index, destinations)
661    end
662  end
663
664  (* these method should be rewritten once intervals are implemened *)
665  merge_destination_insert_helper(node:InternalNode[\Key,Val\], index:ZZ32, destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() =
666  if index = 0 then
667    merge_destination_lower(node, index, destinations)
668  elif index = |node.keys| then
669    merge_destination_upper(node, index, destinations)
670  else
671    merge_destination_middle(node, index, destinations)
672  end
673
674  (* take care of intervals of the form (-INFINITY, x] *)
675  merge_destination_lower(node:InternalNode[\Key,Val\], index:ZZ32, destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() =
676  if node.keys[index] <= keys[0] then
677    atomic do
678      destinations[0] := destinations[0].addLeft(node.children[index])
679    end
680  else
681    merge_destination_insert(node.children[index], destinations)
682  end
683
684  (* take care of intervals of the form [x, INFINITY) *)
685  merge_destination_upper(node:InternalNode[\Key,Val\], index:ZZ32, destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() =
686  if node.keys[index - 1] >= keys[|keys| - 1] then
687    atomic do
688      destinations[|keys|] := destinations[|keys|].addLeft(node.children[index])
689    end
690  else
691    merge_destination_insert(node.children[index], destinations)
692  end
693
694  (* take care of all other intervals *)
695  merge_destination_middle(node:InternalNode[\Key,Val\], index:ZZ32, destinations:Array[\List[\Node[\Key,Val\]\],ZZ32\]):() = do
696    index':ZZ32 = find_unique(node, index)
697    if index' >= 0 then
698      atomic do
699        destinations[index'] := destinations[index'].addLeft(node.children[index])
700      end
701    else
702      merge_destination_insert(node.children[index], destinations)
703    end
704  end
705
706  (* find the unique interval in self that encompasses node.children[index], or return -1 *)
707  find_unique(node:InternalNode[\Key,Val\], index:ZZ32):ZZ32 = do
708    index':ZZ32 := -1
709    lower:Key = node.keys[index - 1]
710    upper:Key = node.keys[index]
711    for i <- 0 # (|keys| - 1) do
712      if (keys[i] <= lower AND keys[i + 1] >= upper) then
713        index' := (i + 1)
714      end
715    end
716    index'
717  end
718
719end
720
721(* The empty node represents an empty tree. It is neither a leaf node nor
722   an internal node, and the empty node does not have a height. *)
723object EmptyNode[\Key,Val\] extends Node[\Key,Val\]
724
725  getter height():ZZ32 = fail("Cannot get height of an empty tree")
726  getter size():ZZ32 = 0
727  getter asString():String = "{}"
728
729  opr |self| : ZZ32 = 0
730
731  search(k:Key):Maybe[\Val\] = Nothing[\Val\]
732
733  remove(k:Key):Node[\Key,Val\] = self
734
735  add(leaf:LeafNode[\Key,Val\], level:ZZ32):Node[\Key,Val\] = do
736    (newNode, newKey) = add_helper(leaf, level)
737    newNode
738  end
739
740  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):(Node[\Key,Val\], Boolean) = do
741    parent:WhiteLevel1[\Key,Val\] = WhiteLevel1[\Key,Val\](leaf)
742    (parent, true)
743  end
744
745  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] = nodes[0]
746
747  getLeaves():List[\LeafNode[\Key,Val\]\] =  <|[\LeafNode[\Key,Val\]\] |>
748
749end
750
751(* Leaf nodes are the only nodes that store values.  All leaf
752   nodes live at the bottom of the tree, and they all have height 0. *)
753object LeafNode[\Key,Val\](key: Key, values: Array[\Val,ZZ32\])
754       extends Node[\Key,Val\]
755
756  getter size():ZZ32 = |values|
757  getter asString():String = "<<" key ">>"
758  getter height():ZZ32 = 0
759  getKey():Key = key
760  getValues():Array[\Val,ZZ32\] = values
761
762  opr |self| : ZZ32 = |values|
763
764  search(k:Key):Maybe[\Val\] = if k = key then Just[\Val\](values[0]) else Nothing[\Val\] end
765
766  add(leaf:LeafNode[\Key,Val\], level:ZZ32):Node[\Key,Val\] = fail("Cannot add a new node into a leaf node.")
767  add_helper(leaf:LeafNode[\Key,Val\], level:ZZ32):Node[\Key,Val\] = fail("Cannot add a new node into a leaf node.")
768  remove(k:Key):Node[\Key,Val\] = fail("Cannot remove a key from a leaf node.")
769
770  merge(nodes:List[\Node[\Key,Val\]\]):Node[\Key,Val\] = fail("Cannot merge into a leaf node.")
771
772  getLeaves():List[\LeafNode[\Key,Val\]\] = singleton[\LeafNode[\Key,Val\]\](self)
773
774
775end
776
777
778end
Note: See TracBrowser for help on using the browser.