January 19, 2021, 05:04:08 AM

### Author Topic: [bmx] Number maps by Warpy [ 1+ years ago ]  (Read 673 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bmx] Number maps by Warpy [ 1+ years ago ]
« 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