Wiki

Ticket #263: Treap.cobra

File Treap.cobra, 15.2 KB (added by hopscc, 7 years ago)
Line 
1#   An implementation of a treap data structure. (Generic)
2#
3#   A treap is based upon a randomized binary Tree whose nodes have keys and
4#   which also have priorities associated with them in a heap - hence the
5#   name (tre)e h(eap).
6#
7#   A Tree is a `heap' if each node has a priority such that the priority of
8#   each child is greater than the priority of its parent (trees that are heaps
9#   can also called "priority queues", and are the basis of a heap sort).
10#
11#   The priorities are a means to randomize the Tree. Randomized trees are better
12#   balanced (essentially meaning less depth) so that seach time is minimized.
13#
14#   Treaps were first introduced by Seidel and Aragon in
15#   R. Seidel and C. R. Aragon. Randomized Binary Search Trees.
16#   Algorithmica, 16(4/5):464-497, 1996.
17#
18#   Most methods run in O(log n) randomized time, where n is the number of keys in
19#   the treap. The exceptions are clone() and toString() that run in time
20#   proportional to the elementCount of their output.
21#
22#   This code was was ultimately based upon the Java treap implementation by Stefan Nilsson
23#   published in Dr. Dobb's Journal, pp. 40-44, Vol. 267, July 1997
24
25#   Translated to Cobra and genericised by Mike Hopkirk Oct-2010 from the C# implementation
26#   done by RoyClem posted to http://www.codeproject.com/KB/recipes/treapcs.aspx
27#
28
29use System.Text
30use System.Collections
31
32namespace Treap
33
34    # The TreapException class distinguishes treap exceptions from .NET
35    # exceptions. It notifies the caller that an exception has occurred in the
36    # treap class.
37    class TreapException inherits Exception
38        cue init
39            base.init
40
41        cue init(msg as String)
42            base.init(msg) 
43           
44    # The TreapNode class encapsulates a node in the treap
45    class TreapNode<of KT, VT>
46        where KT must be IComparable
47   
48        var __ordKey as KT              # key provided by the calling class
49        var __objData as VT             # the data or value associated with the key
50        var __intPriority as int        # random priority to balance the tree
51        var __tnLeft as TreapNode<of KT, VT>?   # left node of the tree
52        var __tnRight as TreapNode<of KT, VT>?  # right node of the tree
53       
54        pro key from __ordKey
55        pro value from __objData
56
57        get priority from __intPriority
58        pro left from __tnLeft
59        pro right from __tnRight
60           
61        cue init(key as KT, value as VT, priority as int)
62            base.init
63            __ordKey = key
64            __objData = value
65            __intPriority = priority
66
67        # Rebalance the tree by rotating the nodes to the left
68        def rotateLeft as TreapNode<of KT, VT>?
69            temp      = .right
70            .right    = .right.left
71            temp.left = this
72            return temp
73       
74        # Rebalance the tree by rotating the nodes to the right
75        def rotateRight as TreapNode<of KT, VT>? 
76            temp       = .left
77            .left      = .left.right
78            temp.right = this
79            return temp
80       
81        # If one of the children is an empty subtree, remove the root and put the other
82        # child in its place. If both children are nonempty, rotate the treapTree at
83        # the root so that the child with the smallest priority number comes to the
84        # top, then delete the root from the other subtree.
85        #
86        # NOTE: This method is recursive
87        def deleteRoot as TreapNode<of KT, VT>?
88            if .left == nil
89                return .right
90            if .right == nil
91                return .left
92           
93            if .left.priority < .right.priority
94                temp        = .rotateRight
95                temp.right  = .deleteRoot
96            else
97                temp        = .rotateLeft
98                temp.left   = .deleteRoot
99            return temp
100       
101        def toString as String is override
102            return '([.key]:[.value])'
103   
104               
105    #
106    # Treap data structure (a collection)
107    # For IDictionary needs support ICollection<KeyValuePair<TKey, TValue>>,
108    #       IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
109
110    class Treap<of KT, VT> implements ICollection, ICollection<of KeyValuePair<of KT, VT>>, System.Collections.IEnumerable, IEnumerable<of KeyValuePair<of KT, VT>>
111        where KT must be IComparable 
112        #where VT must be callable
113       
114        var __rndPriority as Random     # random priority to keep the treap balanced
115        var __nodeCount as int          # the number of key-and-value pairs (nodes) contained in the treap
116        var __intHashCode as int        # used for quick comparisons
117
118        var __strIdentifier='unspec'    # optionally identifies the owner of the treap
119
120        var __treapRoot as TreapNode<of KT, VT>?   # the tree heap
121        var __keyFound as bool       
122        #var __prevData as Object?     
123       
124        cue init
125            base.init
126            __rndPriority = Random()
127            __intHashCode = __rndPriority.next
128       
129       
130        cue init(strIdentifier as String) 
131            .init
132            __strIdentifier  = strIdentifier
133       
134        #
135        # IDictionary
136        #
137       
138        def add(key as KT, value as VT)
139            """
140            Add key and value pair to the treap.
141           
142            args: key As IComparable generic Keytype , value As generic ValueType
143            key is a Type that implements IComparable interface
144            """
145
146            node = TreapNode<of KT,VT>(key, value, __rndPriority.next )
147            # generate random priority
148            #node.priority   = __rndPriority.next
149       
150            # insert node into treapTree
151            __keyFound    = false
152            __treapRoot = _insertNode(node, __treapRoot)
153            if __keyFound
154                #TODO: provide knob to configure disallow replacing dups
155                #throw TreapException('A TreapNode with the same key "[key.toString]" already exists in the Treap')
156                return 
157            __nodeCount += 1
158           
159        # Inserts a node into the tree (recursively)
160        # This method rebalances the tree using the priorities
161        #
162        # Note: The lower the number, the higher the priority
163        def _insertNode(node as TreapNode<of KT, VT>, tree as TreapNode<of KT, VT>?) as TreapNode<of KT, VT>?
164            if not tree
165                return node
166           
167            result = node.key.compareTo(tree.key)
168            if result < 0
169                tree.left = _insertNode(node, tree.left)
170                if tree.left.priority < tree.priority
171                    tree = tree.rotateRight
172            else if result > 0
173                tree.right = _insertNode(node, tree.right)
174                if tree.right.priority < tree.priority
175                    tree = tree.rotateLeft
176            else
177                __keyFound    = true
178                #__prevData  = tree.value
179                tree.value   = node.value
180                ##print __prevData, node.value
181            return tree
182       
183        def getValue(key as KT) as VT
184            """
185            Gets the data value associated with the specified key
186            Throw exception if key not found
187            """
188            result as VT
189            if not .tryGetValue(key, out result)
190                throw TreapException('Treap key [key.toString] was not found')
191            return result
192       
193        def tryGetValue(key as KT, value as out VT?) as bool   
194            """
195            Get data value for associated key;
196            Return true if key found and place value in 'value' out param
197            Return false if key not found and set value result param to nil.
198            """
199            treeNode = __treapRoot
200            value = sharp'default(VT)' # pending same capability in cobra otherwise must be callable and use VT()
201            cmp = 0
202            while treeNode
203                cmp = key.compareTo(treeNode.key)
204                if cmp == 0 
205                    value = treeNode.value
206                    return true
207                if cmp < 0
208                    treeNode = treeNode.left
209                else
210                    treeNode = treeNode.right
211            return false
212
213        def clear
214            """Clear out all nodes in the treap."""
215            __treapRoot   = nil
216            __nodeCount    = 0
217       
218        def contains(key as KT) as bool
219            """
220            Determines whether the treap contains an element with the specified key.
221            """
222            treeNode = __treapRoot
223            cmp = 0
224            while treeNode
225                cmp = key.compareTo(treeNode.key)
226                if cmp == 0 
227                    return true
228                if cmp < 0
229                    treeNode = treeNode.left
230                else
231                    treeNode = treeNode.right
232            return false
233       
234        def remove(key as KT) as bool
235            """ 
236            Removes any treap node for the provided key.
237            Return true if the key was found and key and value removed, false otherwise.   
238            """
239            __keyFound = false
240            __treapRoot  = _delete(key, __treapRoot)
241            if __keyFound
242                __nodeCount -= 1
243            return  __keyFound
244               
245        # Deletes a node (recursively).
246        # Deletes works by "bubbling down" the node until it is a leaf, and then
247        # pruning it off the tree
248        def _delete(key as KT, tNode as TreapNode<of KT, VT>?) as TreapNode<of KT, VT>?
249            if not tNode
250                return nil
251            result = key.compareTo(tNode.key)
252            if result < 0
253                tNode.left = _delete(key, tNode.left)
254            else if result > 0
255                tNode.right = _delete(key, tNode.right)
256            else
257                __keyFound    = true
258                #__prevData    = tNode.value
259                tNode         = tNode.deleteRoot
260            return tNode
261               
262        get isFixedSize as bool
263            return false
264
265        get isReadOnly as bool
266            return false
267   
268        get keys as ICollection<of KT>
269            keyList = List<of KT>()
270            for kvp in .ascendingOrder
271                keyList.add(kvp.key)
272            return keyList
273       
274        get values as ICollection<of VT>
275            valuesList = List<of VT>()
276            for kvp in .ascendingOrder
277                valuesList.add(kvp.value)
278            return valuesList
279           
280        pro [key as KT] as VT? #IComparable
281            get 
282                #value as VT
283                #if .tryGetValue(key, out value)
284                #   return value
285                #return sharp'default(VT)' # nil
286                return .getValue(key)
287            set
288                #trace key, value
289                .add(key, value to !)
290
291        # ICollection   
292        get count as int
293            """Return number of elements/keys in the treap."""
294            return __nodeCount
295       
296        get isSynchronized as bool
297            return false
298
299        get syncRoot as Object
300            return this
301   
302        def copyTo(arr as KeyValuePair<of KT,VT>[], index as int)
303            for kvp in this
304                arr[index] = kvp
305                index += 1
306           
307        def copyTo(arr as Array, index as int) 
308            implements System.Collections.ICollection
309            for tn in this
310                arr.setValue(tn, index)
311                index += 1
312               
313        # ICollection<of KeyValuePair<of KT, VT>>
314        def add(kvp as KeyValuePair<of KT, VT>)
315            .add(kvp.key, kvp.value)
316           
317        def remove(kvp as KeyValuePair<of KT, VT>) as bool
318            return .remove(kvp.key)
319           
320        def contains(kvp as KeyValuePair<of KT, VT>) as bool
321            if not .contains(kvp.key), return false
322            return this[kvp.key] == kvp.value   
323           
324        # ICollection, IEnumerable
325        # GetEnumerator
326        def getEnumerator as IEnumerator<of KeyValuePair<of KT, VT>>
327            """
328            Get Enumerator for Treap Nodes in ascending order.
329            fulfills IDictionary interface method
330            """
331            return .ascendingOrder.getEnumerator
332
333        def getEnumerator as System.Collections.IEnumerator
334            implements System.Collections.IEnumerable
335            #print 'getenumerator '
336            return .getEnumerator to System.Collections.IEnumerator # .ascendingOrder.getEnumerator
337       
338        get ascendingOrder as IEnumerable<of KeyValuePair<of KT, VT>>
339            return _scanAscendingOrder(__treapRoot, 0)
340       
341        get descendingOrder as IEnumerable<of KeyValuePair<of KT, VT>>
342            return _scanDescendingOrder(__treapRoot, 0)
343       
344        def _scanAscendingOrder(node as TreapNode<of KT, VT>?, level) as IEnumerable<of KeyValuePair<of KT, VT>>
345            if not node
346                yield break
347            if node.left
348                for tn in _scanAscendingOrder(node.left to !, level+1)
349                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
350            #print node.key, level
351            #yield node to !
352            yield KeyValuePair<of KT, VT>(node.key, node.value)
353            if node.right
354                for tn in _scanAscendingOrder(node.right to !, level+1)
355                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
356                   
357               
358        def _scanDescendingOrder(node as TreapNode<of KT, VT>?, level) as IEnumerable<of KeyValuePair<of KT, VT>>
359            if not node
360                yield break
361            if node.right
362                for tn in _scanDescendingOrder(node.right to !, level+1)
363                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
364            yield KeyValuePair<of KT, VT>(node.key, node.value)
365            if node.left
366                for tn in _scanDescendingOrder(node.left to !, level+1)
367                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
368                   
369           
370        #
371        # Convenience Enumerators for keys and values in {as,des}cending order
372        #
373        # def keyEnumerator(ascending as bool) as IEnumerable<of KT>
374        # def valueEnumerator(ascending as bool) as IEnumerable<of VT>
375       
376        def isEmpty as bool
377            """Return an indication the Treap has been cleared or has had nothing added to it."""
378            return __treapRoot == nil
379       
380        #
381        #Convenience   
382        #
383       
384        def getMinKey as KT
385            """ Returns the minimum key value in the treap."""
386            if not __treapRoot
387                throw TreapException('Treap is empty')
388            treeNode = __treapRoot
389            while treeNode.left
390                treeNode = treeNode.left
391            return treeNode.key
392           
393       
394        def getMaxKey as KT
395            """ Returns the maximum key value in the treap. """
396            if not __treapRoot
397                throw TreapException('Treap is empty')
398            treeNode = __treapRoot
399            while treeNode.right
400                treeNode = treeNode.right
401            return treeNode.key
402           
403       
404        def getMinValue as VT
405            """Returns the object having the minimum key value."""
406            return .getValue(.getMinKey)
407       
408           
409        def getMaxValue as VT 
410            """Returns the object having the maximum key."""
411            return .getValue(.getMaxKey)
412       
413        def removeMin as VT
414            """
415            Removes the node with the minimum key.
416            Returns the node value
417            """
418            if not __treapRoot
419                throw  TreapException('Treap is empty')
420           
421            # start at top
422            treeNode = __treapRoot
423            prevTreapNode as TreapNode<of KT, VT>?
424           
425            if not treeNode.left
426                # remove top node by replacing with right
427                __treapRoot = treeNode.right
428            else
429                while true
430                    # find the minimum node
431                    prevTreapNode   = treeNode
432                    treeNode        = treeNode.left
433                    if not treeNode.left
434                        break
435                # remove left node by replacing with right node
436                prevTreapNode.left  = treeNode.right
437           
438            __nodeCount -= 1
439            return treeNode.value
440           
441           
442        def removeMax as VT
443            """
444            Removes the node with the maximum key.
445            Returns the node Value
446            """
447            if not __treapRoot
448                throw  TreapException('Treap is empty')
449           
450            # start at top
451            treeNode = __treapRoot
452            prevTreapNode as TreapNode<of KT, VT>? 
453           
454            if not treeNode.right
455                # remove top node by replacing with left
456                __treapRoot = treeNode.left
457            else
458                while true
459                    # find the maximum node
460                    prevTreapNode = treeNode
461                    treeNode = treeNode.right
462                    if not treeNode.right
463                        break
464                # remove right node by replacing with left node
465                prevTreapNode.right = treeNode.left
466
467            __nodeCount -= 1
468            return treeNode.value
469       
470        #
471        # IEquatable - need this for use as a Dict Key (or in a Set)
472        #
473        def equals(obj as Treap<of KT, VT>) as bool
474            #implements IEquatable<of Treap<of KT,VT>>
475            #if not obj
476            #   return false
477            #if not (obj inherits Treap<of KT, VT>)
478            #   return false
479            if this == obj
480                return true
481            return .toString == obj.toString
482       
483        #
484        # Object
485        #
486        def equals(obj as Object?) as bool is override
487            if not obj
488                return false
489            if obj to? Treap<of KT, VT> == nil
490                return false
491            return .equals(obj to Treap<of KT, VT>)
492           
493        def getHashCode as int is override
494            return __intHashCode
495       
496
497        def toString as String is override
498            return 'Treap-[__strIdentifier]-[.getHashCode]'
499           
500       
501    class Test
502        def main is shared
503            treap = Treap<of String, int>()
504            assert not treap.count
505            treap.add( 'hotel', 99)
506            treap.add( 'alpha', 1)
507            treap.add( 'zebra', 147)
508            assert treap.count == 3
509            assert treap.keys == ['alpha', 'hotel', 'zebra']
510            assert treap.values == [1, 99, 147]
511            assert treap.getMaxKey == 'zebra'
512            assert treap.getMinKey == 'alpha'
513            assert treap.getMinValue == 1   
514            expect AssertException
515                assert treap.getMinValue == 11 
516