SyntaxBomb - Indie Coders

Languages & Coding => Blitz Code Archives => Algorithms => Topic started by: BlitzBot on June 29, 2017, 12:28:38 AM

Title: [bmx] Number maps by Warpy [ 1+ years ago ]
Post by: BlitzBot on June 29, 2017, 12:28:38 AM
Title : Number maps
Author : Warpy
Posted : 1+ years ago

Description : It's been discussed at length that bmax doesn't treat numbers as objects, which makes it hard to use them in lists and maps. Well, here's a modification of the TMap type to make the values Doubles instead of Objects.

Here's an example use:

Local n:TNumberMap=New TNumberMap
n.insert "Jim",1
n.insert "Bob",2
For Local k$=EachIn n.keys()
   Print k+" : "+n.valueforkey(k)
Next

For Local d#=EachIn n.toarray()
   Print d
Next

Code :
Code: BlitzMax
  1. Strict
  2.  
  3. Private
  4.  
  5. Global nil:TNumberNode=New TNumberNode
  6.  
  7. nil._color=TNumberMap.BLACK
  8. nil._parent=nil
  9. nil._left=nil
  10. nil._right=nil
  11.  
  12. Public
  13.  
  14. Type TKeyValue
  15.  
  16.  
  17. End Type
  18.  
  19. Type TNumberNode
  20.         Method Key:Object()
  21.                 Return _key
  22.         End Method
  23.        
  24.         Method Value:Double()
  25.                 Return _value
  26.         End Method
  27.        
  28.         Method nextnode:TNumberNode()
  29.                 Local node:TNumberNode=Self
  30.                 If node._right<>nil
  31.                         node=_right
  32.                         While node._left<>nil
  33.                                 node=node._left
  34.                         Wend
  35.                         Return node
  36.                 EndIf
  37.                 Local parent:TNumberNode=_parent
  38.                 While node=parent._right
  39.                         node=parent
  40.                         parent=parent._parent
  41.                 Wend
  42.                 Return parent
  43.         End Method
  44.        
  45.         Method PrevNode:TNumberNode()
  46.                 Local node:TNumberNode=Self
  47.                 If node._left<>nil
  48.                         node=node._left
  49.                         While node._right<>nil
  50.                                 node=node._right
  51.                         Wend
  52.                         Return node
  53.                 EndIf
  54.                 Local parent:TNumberNode=node._parent
  55.                 While node=parent._left
  56.                         node=parent
  57.                         parent=node._parent
  58.                 Wend
  59.                 Return parent
  60.         End Method
  61.        
  62.         Method Clear()
  63.                 _parent=Null
  64.                 If _left<>nil _left.Clear
  65.                 If _right<>nil _right.Clear
  66.         End Method
  67.        
  68.         Method Copy:TNumberNode( parent:TNumberNode )
  69.                 Local t:TNumberNode=New TNumberNode
  70.                 t._key=_key
  71.                 t._value=_value
  72.                 t._color=_color
  73.                 t._parent=parent
  74.                 If _left<>nil t._left=_left.Copy( t )
  75.                 If _right<>nil t._right=_right.Copy( t )
  76.                 Return t
  77.         End Method
  78.        
  79.         '***** PRIVATE *****
  80.        
  81.         Field _color,_parent:TNumberNode=nil,_left:TNumberNode=nil,_right:TNumberNode=nil
  82.  
  83.         '***** PRIVATE *****
  84.  
  85.         Field _key:Object,_value:Double
  86.  
  87.  
  88. End Type
  89.  
  90. Type TNumberNodeEnumerator
  91.         Method HasNext()
  92.                 Return _node<>nil
  93.         End Method
  94.        
  95.         Method NextObject:Object()
  96.                 Local node:TNumberNode=_node
  97.                 _node=_node.nextnode()
  98.                 Return node
  99.         End Method
  100.  
  101.         '***** PRIVATE *****
  102.                
  103.         Field _node:TNumberNode
  104. End Type
  105.  
  106. Type TKeyEnumerator Extends TNumberNodeEnumerator
  107.         Method NextObject:Object()
  108.                 Local node:TNumberNode=_node
  109.                 _node=_node.nextnode()
  110.                 Return node._key
  111.         End Method
  112. End Type
  113.  
  114. Rem
  115. Type TValueEnumerator Extends TNumberNodeEnumerator
  116.         Method NextObject:Object()
  117.                 Local node:TNumberNode=_node
  118.                 _node=_node.nextnode()
  119.                 Return node._value
  120.         End Method
  121. End Type
  122. EndRem
  123.  
  124. Type TNumberMapEnumerator
  125.         Method ObjectEnumerator:TNumberNodeEnumerator()
  126.                 Return _enumerator
  127.         End Method
  128.         Field _enumerator:TNumberNodeEnumerator
  129. End Type
  130.  
  131.  
  132. '***** PUBLIC *****
  133.  
  134. Type TNumberMap
  135.  
  136.         Method Delete()
  137.                 Clear
  138.         End Method
  139.  
  140.         Method Clear()
  141.                 If _root=nil Return
  142.                 _root.Clear
  143.                 _root=nil
  144.         End Method
  145.        
  146.         Method IsEmpty()
  147.                 Return _root=nil
  148.         End Method
  149.        
  150.         Method Insert( key:Object,value:Double )
  151.  
  152.                 Assert key Else "Can't insert Null key into map"
  153.  
  154.                 Local node:TNumberNode=_root,parent:TNumberNode=nil,cmp
  155.                
  156.                 While node<>nil
  157.                         parent=node
  158.                         cmp=key.Compare( node._key )
  159.                         If cmp>0
  160.                                 node=node._right
  161.                         Else If cmp<0
  162.                                 node=node._left
  163.                         Else
  164.                                 node._value=value
  165.                                 Return
  166.                         EndIf
  167.                 Wend
  168.                
  169.                 node=New TNumberNode
  170.                 node._key=key
  171.                 node._value=value
  172.                 node._color=RED
  173.                 node._parent=parent
  174.                
  175.                 If parent=nil
  176.                         _root=node
  177.                         Return
  178.                 EndIf
  179.                 If cmp>0
  180.                         parent._right=node
  181.                 Else
  182.                         parent._left=node
  183.                 EndIf
  184.                
  185.                 _InsertFixup node
  186.         End Method
  187.        
  188.         Method Contains( key:Object )
  189.                 Return _FindNode( key )<>nil
  190.         End Method
  191.  
  192.         Method ValueForKey:Double( key:Object )
  193.                 Local node:TNumberNode=_FindNode( key )
  194.                 If node<>nil Return node._value
  195.         End Method
  196.        
  197.         Method Remove( key:Object )
  198.                 Local node:TNumberNode=_FindNode( key )
  199.                 If node=nil Return 0
  200.                  _RemoveNode node
  201.                 Return 1
  202.         End Method
  203.        
  204.         Method Keys:TNumberMapEnumerator()
  205.                 Local nodeenum:TNumberNodeEnumerator=New TKeyEnumerator
  206.                 nodeenum._node=_FirstNode()
  207.                 Local mapenum:TNumberMapEnumerator=New TNumberMapEnumerator
  208.                 mapenum._enumerator=nodeenum
  209.                 Return mapenum
  210.         End Method
  211.        
  212.         Method ToArray:Double[]()
  213.                 Local o:Double[]
  214.                 Local n:TNumberNode=_FirstNode()
  215.                 While n<>nil
  216.                         o:+[n._value]
  217.                         n=n.nextnode()
  218.                 Wend
  219.                 Return o
  220.         End Method
  221.        
  222.         Rem
  223.         Method Values:TNumberMapEnumerator()
  224.                 Local nodeenum:TNumberNodeEnumerator=New TValueEnumerator
  225.                 nodeenum._node=_FirstNode()
  226.                 Local mapenum:TNumberMapEnumerator=New TNumberMapEnumerator
  227.                 mapenum._enumerator=nodeenum
  228.                 Return mapenum
  229.         End Method
  230.         EndRem
  231.        
  232.         Method Copy:TNumberMap()
  233.                 Local map:TNumberMap=New TNumberMap
  234.                 map._root=_root.Copy( nil )
  235.                 Return map
  236.         End Method
  237.        
  238.         Rem
  239.         Method ObjectEnumerator:TNumberNodeEnumerator()
  240.                 Local nodeenum:TNumberNodeEnumerator=New TNumberNodeEnumerator
  241.                 nodeenum._node=_FirstNode()
  242.                 Return nodeenum
  243.         End Method
  244.         EndRem
  245.        
  246.         '***** PRIVATE *****
  247.        
  248.         Method _FirstNode:TNumberNode()
  249.                 Local node:TNumberNode=_root
  250.                 While node._left<>nil
  251.                         node=node._left
  252.                 Wend
  253.                 Return node
  254.         End Method
  255.        
  256.         Method _LastNode:TNumberNode()
  257.                 Local node:TNumberNode=_root
  258.                 While node._right<>nil
  259.                         node=node._right
  260.                 Wend
  261.                 Return node
  262.         End Method
  263.        
  264.         Method _FindNode:TNumberNode( key:Object )
  265.                 Local node:TNumberNode=_root
  266.                 While node<>nil
  267.                         Local cmp=key.Compare( node._key )
  268.                         If cmp>0
  269.                                 node=node._right
  270.                         Else If cmp<0
  271.                                 node=node._left
  272.                         Else
  273.                                 Return node
  274.                         EndIf
  275.                 Wend
  276.                 Return node
  277.         End Method
  278.        
  279.         Method _RemoveNode( node:TNumberNode )
  280.                 Local splice:TNumberNode,child:TNumberNode
  281.                
  282.                 If node._left=nil
  283.                         splice=node
  284.                         child=node._right
  285.                 Else If node._right=nil
  286.                         splice=node
  287.                         child=node._left
  288.                 Else
  289.                         splice=node._left
  290.                         While splice._right<>nil
  291.                                 splice=splice._right
  292.                         Wend
  293.                         child=splice._left
  294.                         node._key=splice._key
  295.                         node._value=splice._value
  296.                 EndIf
  297.                 Local parent:TNumberNode=splice._parent
  298.                 If child<>nil
  299.                         child._parent=parent
  300.                 EndIf
  301.                 If parent=nil
  302.                         _root=child
  303.                         Return
  304.                 EndIf
  305.                 If splice=parent._left
  306.                         parent._left=child
  307.                 Else
  308.                         parent._right=child
  309.                 EndIf
  310.                
  311.                 If splice._color=BLACK _DeleteFixup child,parent
  312.         End Method
  313.        
  314.         Method _InsertFixup( node:TNumberNode )
  315.                 While node._parent._color=RED And node._parent._parent<>nil
  316.                         If node._parent=node._parent._parent._left
  317.                                 Local uncle:TNumberNode=node._parent._parent._right
  318.                                 If uncle._color=RED
  319.                                         node._parent._color=BLACK
  320.                                         uncle._color=BLACK
  321.                                         uncle._parent._color=RED
  322.                                         node=uncle._parent
  323.                                 Else
  324.                                         If node=node._parent._right
  325.                                                 node=node._parent
  326.                                                 _RotateLeft node
  327.                                         EndIf
  328.                                         node._parent._color=BLACK
  329.                                         node._parent._parent._color=RED
  330.                                         _RotateRight node._parent._parent
  331.                                 EndIf
  332.                         Else
  333.                                 Local uncle:TNumberNode=node._parent._parent._left
  334.                                 If uncle._color=RED
  335.                                         node._parent._color=BLACK
  336.                                         uncle._color=BLACK
  337.                                         uncle._parent._color=RED
  338.                                         node=uncle._parent
  339.                                 Else
  340.                                         If node=node._parent._left
  341.                                                 node=node._parent
  342.                                                 _RotateRight node
  343.                                         EndIf
  344.                                         node._parent._color=BLACK
  345.                                         node._parent._parent._color=RED
  346.                                         _RotateLeft node._parent._parent
  347.                                 EndIf
  348.                         EndIf
  349.                 Wend
  350.                 _root._color=BLACK
  351.         End Method
  352.        
  353.         Method _RotateLeft( node:TNumberNode )
  354.                 Local child:TNumberNode=node._right
  355.                 node._right=child._left
  356.                 If child._left<>nil
  357.                         child._left._parent=node
  358.                 EndIf
  359.                 child._parent=node._parent
  360.                 If node._parent<>nil
  361.                         If node=node._parent._left
  362.                                 node._parent._left=child
  363.                         Else
  364.                                 node._parent._right=child
  365.                         EndIf
  366.                 Else
  367.                         _root=child
  368.                 EndIf
  369.                 child._left=node
  370.                 node._parent=child
  371.         End Method
  372.        
  373.         Method _RotateRight( node:TNumberNode )
  374.                 Local child:TNumberNode=node._left
  375.                 node._left=child._right
  376.                 If child._right<>nil
  377.                         child._right._parent=node
  378.                 EndIf
  379.                 child._parent=node._parent
  380.                 If node._parent<>nil
  381.                         If node=node._parent._right
  382.                                 node._parent._right=child
  383.                         Else
  384.                                 node._parent._left=child
  385.                         EndIf
  386.                 Else
  387.                         _root=child
  388.                 EndIf
  389.                 child._right=node
  390.                 node._parent=child
  391.         End Method
  392.        
  393.         Method _DeleteFixup( node:TNumberNode,parent:TNumberNode )
  394.                 While node<>_root And node._color=BLACK
  395.                         If node=parent._left
  396.                                 Local sib:TNumberNode=parent._right
  397.                                 If sib._color=RED
  398.                                         sib._color=BLACK
  399.                                         parent._color=RED
  400.                                         _RotateLeft parent
  401.                                         sib=parent._right
  402.                                 EndIf
  403.                                 If sib._left._color=BLACK And sib._right._color=BLACK
  404.                                         sib._color=RED
  405.                                         node=parent
  406.                                         parent=parent._parent
  407.                                 Else
  408.                                         If sib._right._color=BLACK
  409.                                                 sib._left._color=BLACK
  410.                                                 sib._color=RED
  411.                                                 _RotateRight sib
  412.                                                 sib=parent._right
  413.                                         EndIf
  414.                                         sib._color=parent._color
  415.                                         parent._color=BLACK
  416.                                         sib._right._color=BLACK
  417.                                         _RotateLeft parent
  418.                                         node=_root
  419.                                 EndIf
  420.                         Else   
  421.                                 Local sib:TNumberNode=parent._left
  422.                                 If sib._color=RED
  423.                                         sib._color=BLACK
  424.                                         parent._color=RED
  425.                                         _RotateRight parent
  426.                                         sib=parent._left
  427.                                 EndIf
  428.                                 If sib._right._color=BLACK And sib._left._color=BLACK
  429.                                         sib._color=RED
  430.                                         node=parent
  431.                                         parent=parent._parent
  432.                                 Else
  433.                                         If sib._left._color=BLACK
  434.                                                 sib._right._color=BLACK
  435.                                                 sib._color=RED
  436.                                                 _RotateLeft sib
  437.                                                 sib=parent._left
  438.                                         EndIf
  439.                                         sib._color=parent._color
  440.                                         parent._color=BLACK
  441.                                         sib._left._color=BLACK
  442.                                         _RotateRight parent
  443.                                         node=_root
  444.                                 EndIf
  445.                         EndIf
  446.                 Wend
  447.                 node._color=BLACK
  448.         End Method
  449.        
  450.         Const RED=-1,BLACK=1
  451.        
  452.         Field _root:TNumberNode=nil
  453.        
  454. End Type


Comments : none...
SimplePortal 2.3.6 © 2008-2014, SimplePortal