Ticket #263: Treap.cobra

#   An implementation of a treap data structure. (Generic)
#
#   A treap is based upon a randomized binary Tree whose nodes have keys and
#   which also have priorities associated with them in a heap - hence the
#   name (tre)e h(eap).
#
#   A Tree is a `heap' if each node has a priority such that the priority of
#   each child is greater than the priority of its parent (trees that are heaps
#   can also called "priority queues", and are the basis of a heap sort).
#
#   The priorities are a means to randomize the Tree. Randomized trees are better
#   balanced (essentially meaning less depth) so that seach time is minimized.
#
#   Treaps were first introduced by Seidel and Aragon in
#   R. Seidel and C. R. Aragon. Randomized Binary Search Trees.
#   Algorithmica, 16(4/5):464-497, 1996.
#
#   Most methods run in O(log n) randomized time, where n is the number of keys in
#   the treap. The exceptions are clone() and toString() that run in time
#   proportional to the elementCount of their output.
#
#   This code was was ultimately based upon the Java treap implementation by Stefan Nilsson
#   published in Dr. Dobb's Journal, pp. 40-44, Vol. 267, July 1997

#   Translated to Cobra and genericised by Mike Hopkirk Oct-2010 from the C# implementation 
#   done by RoyClem posted to http://www.codeproject.com/KB/recipes/treapcs.aspx
#

use System.Text
use System.Collections

namespace Treap

    # The TreapException class distinguishes treap exceptions from .NET
    # exceptions. It notifies the caller that an exception has occurred in the
    # treap class.
    class TreapException inherits Exception
        cue init
            base.init

        cue init(msg as String)
            base.init(msg) 
            
    # The TreapNode class encapsulates a node in the treap
    class TreapNode<of KT, VT>
        where KT must be IComparable
    
        var __ordKey as KT              # key provided by the calling class
        var __objData as VT             # the data or value associated with the key
        var __intPriority as int        # random priority to balance the tree
        var __tnLeft as TreapNode<of KT, VT>?   # left node of the tree
        var __tnRight as TreapNode<of KT, VT>?  # right node of the tree
        
        pro key from __ordKey
        pro value from __objData

        get priority from __intPriority 
        pro left from __tnLeft
        pro right from __tnRight
            
        cue init(key as KT, value as VT, priority as int)
            base.init
            __ordKey = key
            __objData = value
            __intPriority = priority

        # Rebalance the tree by rotating the nodes to the left
        def rotateLeft as TreapNode<of KT, VT>?
            temp      = .right
            .right    = .right.left
            temp.left = this
            return temp
        
        # Rebalance the tree by rotating the nodes to the right
        def rotateRight as TreapNode<of KT, VT>? 
            temp       = .left
            .left      = .left.right
            temp.right = this
            return temp
        
        # If one of the children is an empty subtree, remove the root and put the other
        # child in its place. If both children are nonempty, rotate the treapTree at
        # the root so that the child with the smallest priority number comes to the
        # top, then delete the root from the other subtree.
        #
        # NOTE: This method is recursive
        def deleteRoot as TreapNode<of KT, VT>?
            if .left == nil
                return .right
            if .right == nil
                return .left
            
            if .left.priority < .right.priority
                temp        = .rotateRight
                temp.right  = .deleteRoot
            else
                temp        = .rotateLeft
                temp.left   = .deleteRoot
            return temp
        
        def toString as String is override
            return '([.key]:[.value])'
    
                
    #
    # Treap data structure (a collection)
    # For IDictionary needs support ICollection<KeyValuePair<TKey, TValue>>, 
    #       IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable

    class Treap<of KT, VT> implements ICollection, ICollection<of KeyValuePair<of KT, VT>>, System.Collections.IEnumerable, IEnumerable<of KeyValuePair<of KT, VT>>
        where KT must be IComparable 
        #where VT must be callable
        
        var __rndPriority as Random     # random priority to keep the treap balanced
        var __nodeCount as int          # the number of key-and-value pairs (nodes) contained in the treap
        var __intHashCode as int        # used for quick comparisons

        var __strIdentifier='unspec'    # optionally identifies the owner of the treap

        var __treapRoot as TreapNode<of KT, VT>?   # the tree heap
        var __keyFound as bool        
        #var __prevData as Object?      
        
        cue init
            base.init
            __rndPriority = Random()
            __intHashCode = __rndPriority.next
        
        
        cue init(strIdentifier as String) 
            .init
            __strIdentifier  = strIdentifier
        
        #
        # IDictionary
        #
        
        def add(key as KT, value as VT)
            """
            Add key and value pair to the treap.
            
            args: key As IComparable generic Keytype , value As generic ValueType
            key is a Type that implements IComparable interface
            """ 

            node = TreapNode<of KT,VT>(key, value, __rndPriority.next )
            # generate random priority
            #node.priority   = __rndPriority.next
        
            # insert node into treapTree
            __keyFound    = false
            __treapRoot = _insertNode(node, __treapRoot)
            if __keyFound
                #TODO: provide knob to configure disallow replacing dups
                #throw TreapException('A TreapNode with the same key "[key.toString]" already exists in the Treap')
                return  
            __nodeCount += 1
            
        # Inserts a node into the tree (recursively)
        # This method rebalances the tree using the priorities
        #
        # Note: The lower the number, the higher the priority
        def _insertNode(node as TreapNode<of KT, VT>, tree as TreapNode<of KT, VT>?) as TreapNode<of KT, VT>?
            if not tree
                return node
            
            result = node.key.compareTo(tree.key)
            if result < 0
                tree.left = _insertNode(node, tree.left)
                if tree.left.priority < tree.priority
                    tree = tree.rotateRight
            else if result > 0
                tree.right = _insertNode(node, tree.right)
                if tree.right.priority < tree.priority
                    tree = tree.rotateLeft
            else
                __keyFound    = true
                #__prevData  = tree.value
                tree.value   = node.value
                ##print __prevData, node.value
            return tree
        
        def getValue(key as KT) as VT
            """
            Gets the data value associated with the specified key
            Throw exception if key not found
            """ 
            result as VT
            if not .tryGetValue(key, out result)
                throw TreapException('Treap key [key.toString] was not found')
            return result
        
        def tryGetValue(key as KT, value as out VT?) as bool    
            """
            Get data value for associated key; 
            Return true if key found and place value in 'value' out param
            Return false if key not found and set value result param to nil.
            """ 
            treeNode = __treapRoot
            value = sharp'default(VT)' # pending same capability in cobra otherwise must be callable and use VT()
            cmp = 0
            while treeNode
                cmp = key.compareTo(treeNode.key)
                if cmp == 0 
                    value = treeNode.value
                    return true
                if cmp < 0
                    treeNode = treeNode.left
                else
                    treeNode = treeNode.right
            return false

        def clear
            """Clear out all nodes in the treap."""
            __treapRoot   = nil
            __nodeCount    = 0
        
        def contains(key as KT) as bool
            """
            Determines whether the treap contains an element with the specified key.
            """
            treeNode = __treapRoot
            cmp = 0
            while treeNode
                cmp = key.compareTo(treeNode.key)
                if cmp == 0 
                    return true
                if cmp < 0
                    treeNode = treeNode.left
                else
                    treeNode = treeNode.right
            return false
        
        def remove(key as KT) as bool
            """ 
            Removes any treap node for the provided key.
            Return true if the key was found and key and value removed, false otherwise.    
            """
            __keyFound = false
            __treapRoot  = _delete(key, __treapRoot)
            if __keyFound
                __nodeCount -= 1
            return  __keyFound
                
        # Deletes a node (recursively).
        # Deletes works by "bubbling down" the node until it is a leaf, and then
        # pruning it off the tree
        def _delete(key as KT, tNode as TreapNode<of KT, VT>?) as TreapNode<of KT, VT>?
            if not tNode
                return nil
            result = key.compareTo(tNode.key)
            if result < 0
                tNode.left = _delete(key, tNode.left)
            else if result > 0
                tNode.right = _delete(key, tNode.right)
            else
                __keyFound    = true
                #__prevData    = tNode.value
                tNode         = tNode.deleteRoot
            return tNode
                
        get isFixedSize as bool
            return false

        get isReadOnly as bool
            return false
    
        get keys as ICollection<of KT>
            keyList = List<of KT>()
            for kvp in .ascendingOrder
                keyList.add(kvp.key)
            return keyList
        
        get values as ICollection<of VT>
            valuesList = List<of VT>()
            for kvp in .ascendingOrder
                valuesList.add(kvp.value)
            return valuesList
            
        pro [key as KT] as VT? #IComparable 
            get 
                #value as VT
                #if .tryGetValue(key, out value)
                #   return value
                #return sharp'default(VT)' # nil
                return .getValue(key)
            set
                #trace key, value
                .add(key, value to !)

        # ICollection   
        get count as int
            """Return number of elements/keys in the treap."""
            return __nodeCount
        
        get isSynchronized as bool
            return false

        get syncRoot as Object
            return this
    
        def copyTo(arr as KeyValuePair<of KT,VT>[], index as int)
            for kvp in this
                arr[index] = kvp
                index += 1
            
        def copyTo(arr as Array, index as int) 
            implements System.Collections.ICollection
            for tn in this
                arr.setValue(tn, index)
                index += 1
                
        # ICollection<of KeyValuePair<of KT, VT>>
        def add(kvp as KeyValuePair<of KT, VT>)
            .add(kvp.key, kvp.value)
            
        def remove(kvp as KeyValuePair<of KT, VT>) as bool
            return .remove(kvp.key)
            
        def contains(kvp as KeyValuePair<of KT, VT>) as bool
            if not .contains(kvp.key), return false
            return this[kvp.key] == kvp.value   
            
        # ICollection, IEnumerable
        # GetEnumerator
        def getEnumerator as IEnumerator<of KeyValuePair<of KT, VT>>
            """
            Get Enumerator for Treap Nodes in ascending order.
            fulfills IDictionary interface method
            """
            return .ascendingOrder.getEnumerator

        def getEnumerator as System.Collections.IEnumerator
            implements System.Collections.IEnumerable
            #print 'getenumerator '
            return .getEnumerator to System.Collections.IEnumerator # .ascendingOrder.getEnumerator
        
        get ascendingOrder as IEnumerable<of KeyValuePair<of KT, VT>>
            return _scanAscendingOrder(__treapRoot, 0)
        
        get descendingOrder as IEnumerable<of KeyValuePair<of KT, VT>>
            return _scanDescendingOrder(__treapRoot, 0)
        
        def _scanAscendingOrder(node as TreapNode<of KT, VT>?, level) as IEnumerable<of KeyValuePair<of KT, VT>>
            if not node
                yield break
            if node.left
                for tn in _scanAscendingOrder(node.left to !, level+1)
                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
            #print node.key, level
            #yield node to !
            yield KeyValuePair<of KT, VT>(node.key, node.value)
            if node.right
                for tn in _scanAscendingOrder(node.right to !, level+1)
                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
                    
                
        def _scanDescendingOrder(node as TreapNode<of KT, VT>?, level) as IEnumerable<of KeyValuePair<of KT, VT>>
            if not node
                yield break
            if node.right
                for tn in _scanDescendingOrder(node.right to !, level+1)
                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
            yield KeyValuePair<of KT, VT>(node.key, node.value)
            if node.left
                for tn in _scanDescendingOrder(node.left to !, level+1)
                    yield KeyValuePair<of KT, VT>(tn.key, tn.value)
                    
            
        #
        # Convenience Enumerators for keys and values in {as,des}cending order
        #
        # def keyEnumerator(ascending as bool) as IEnumerable<of KT>
        # def valueEnumerator(ascending as bool) as IEnumerable<of VT>
        
        def isEmpty as bool
            """Return an indication the Treap has been cleared or has had nothing added to it."""
            return __treapRoot == nil
        
        #
        #Convenience    
        #
        
        def getMinKey as KT 
            """ Returns the minimum key value in the treap."""
            if not __treapRoot
                throw TreapException('Treap is empty')
            treeNode = __treapRoot
            while treeNode.left
                treeNode = treeNode.left
            return treeNode.key
            
        
        def getMaxKey as KT
            """ Returns the maximum key value in the treap. """
            if not __treapRoot
                throw TreapException('Treap is empty')
            treeNode = __treapRoot
            while treeNode.right
                treeNode = treeNode.right
            return treeNode.key
            
        
        def getMinValue as VT
            """Returns the object having the minimum key value."""
            return .getValue(.getMinKey)
        
            
        def getMaxValue as VT 
            """Returns the object having the maximum key."""
            return .getValue(.getMaxKey)
        
        def removeMin as VT
            """
            Removes the node with the minimum key. 
            Returns the node value
            """
            if not __treapRoot
                throw  TreapException('Treap is empty')
            
            # start at top
            treeNode = __treapRoot
            prevTreapNode as TreapNode<of KT, VT>?
            
            if not treeNode.left
                # remove top node by replacing with right
                __treapRoot = treeNode.right
            else
                while true
                    # find the minimum node
                    prevTreapNode   = treeNode
                    treeNode        = treeNode.left
                    if not treeNode.left
                        break
                # remove left node by replacing with right node
                prevTreapNode.left  = treeNode.right
            
            __nodeCount -= 1
            return treeNode.value
            
            
        def removeMax as VT
            """
            Removes the node with the maximum key.
            Returns the node Value
            """
            if not __treapRoot
                throw  TreapException('Treap is empty')
            
            # start at top
            treeNode = __treapRoot
            prevTreapNode as TreapNode<of KT, VT>? 
            
            if not treeNode.right
                # remove top node by replacing with left
                __treapRoot = treeNode.left
            else
                while true
                    # find the maximum node
                    prevTreapNode = treeNode
                    treeNode = treeNode.right
                    if not treeNode.right
                        break
                # remove right node by replacing with left node
                prevTreapNode.right = treeNode.left

            __nodeCount -= 1
            return treeNode.value
        
        #
        # IEquatable - need this for use as a Dict Key (or in a Set)
        #
        def equals(obj as Treap<of KT, VT>) as bool
            #implements IEquatable<of Treap<of KT,VT>>
            #if not obj 
            #   return false
            #if not (obj inherits Treap<of KT, VT>)
            #   return false
            if this == obj
                return true
            return .toString == obj.toString
        
        #
        # Object
        #
        def equals(obj as Object?) as bool is override
            if not obj
                return false
            if obj to? Treap<of KT, VT> == nil
                return false
            return .equals(obj to Treap<of KT, VT>)
            
        def getHashCode as int is override
            return __intHashCode
        

        def toString as String is override
            return 'Treap-[__strIdentifier]-[.getHashCode]'
            
        
    class Test
        def main is shared
            treap = Treap<of String, int>()
            assert not treap.count
            treap.add( 'hotel', 99)
            treap.add( 'alpha', 1)
            treap.add( 'zebra', 147)
            assert treap.count == 3
            assert treap.keys == ['alpha', 'hotel', 'zebra']
            assert treap.values == [1, 99, 147]
            assert treap.getMaxKey == 'zebra'
            assert treap.getMinKey == 'alpha'
            assert treap.getMinValue == 1   
            expect AssertException
                assert treap.getMinValue == 11