November 18, 2017, 11:02:36 PM

Author Topic: [bmx] ObjectList by Perturbatio [ 1+ years ago ]  (Read 168 times)

Offline BlitzBot

  • Newbie
  • *
  • Posts: 0
[bmx] ObjectList by Perturbatio [ 1+ years ago ]
« on: June 29, 2017, 12:28:43 AM »
Title : ObjectList
Author : Perturbatio
Posted : 1+ years ago

Description : (BMax)

Functions:
Create(StepSize=10) - returns a TObjectList
Destroy(List) - Pass a TObjectList to destroy it
FromObjectArray(val) - Convert an Object Array to an ObjectList

Methods:
AddFirst(val) - add an object to the beginning of the list
AddLast(val) - add an object to the end of the list
ToDelimString(Delimiter) - Returns a delimited string containing all the objects.  Relies on a toString method being implemented in the objects
ToString - Same as ToDelimString but without a delimiter
Count - returns the number of items in the list
Contains(val) - Searches the list for the specified item and returns it's index or -1 if not found
Insert(val, index, AutoAddToEnd=False) - Insert Val at Index, if AutoAddToEnd is true then it will use AddLast if the Index is greater than the number of items in the list
RemoveByIndex(Index) - removes an item by index
RemoveByObject(val, RemoveAll=False) - removes the first item specified by val from the list, if RemoveAll is true, it removes all of them
Clear - clears the list
ToArray - Returns an object array containing the items in the list
ToList - converts the ObjectList to a Standard TList
GetStepSize - returns the current StepSize
SetStepSize - set the StepSize
Sort() - not currently working because of an issue with sorting null object arrays
Free() - Free the list (equivalent to calling TObjectList.Destroy(list))
SwapByIndex(FirstIndex, SecondIndex) - Swap the first index with the second, returns true if successful, false if not
SwapByVal(FirstObject, SecondObject) - Swap the first object matching FirstObject with the first one matching SecondObject


Code :
Code: BlitzMax
  1. SuperStrict
  2.  
  3. Framework BRL.Retro
  4. Import BRL.System
  5.  
  6. Rem
  7. ObjectList created by Kris Kelly (Perturbatio) Dec 2005
  8. purpose: faster access to a list of objects with less mem usage
  9. it's performance is comparable to a TList when using a small number of strings
  10. but when you are using a large amount, it is much better (and uses less memory).
  11.  
  12. When invoking the create method, you can specify the StepSize, this is the amount that
  13. the Items Array will be increased by each time it is in danger of running out of space.
  14. It is faster to do it in large blocks than in hundreds of little ones.
  15. End Rem
  16.  
  17. Type TObjectList
  18.         Field Items:Object[]
  19.         Field _Size:Int = 0 'DO NOT MANUALLY MODIFY THIS!!!
  20.         Field StepSize:Int
  21.        
  22.         Method AddFirst(val:Object)
  23.                 Local i:Int
  24.  
  25.                 'grow Items array by 1
  26.                 'Items = Items[..Items.Length + 1]
  27.                 _Size:+1
  28.                 'resize in bulk
  29.                 If Items.Length < _Size Then Items = Items[.._Size+StepSize]
  30.                
  31.                
  32.                 'shift Items to the rightt, overwriting val
  33.                 For i = 1 To _Size-1 'Items.Length - 1
  34.                         Items[i] = Items[i - 1]
  35.                 Next
  36.                
  37.                 Items[0] = val
  38.                 'no need to return anything here since we know it was added at 0
  39.         End Method
  40.        
  41.        
  42.         Method AddLast:Int(val:Object)
  43.                 'grow Items array by 1
  44.                 'Items = Items[..Items.Length + 1]
  45.                 _Size:+1
  46.                 'resize in bulk
  47.                 If Items.Length < _Size Then Items = Items[.._Size+StepSize]
  48.                
  49.                 'set the last index to val
  50.                 'Items[Items.Length - 1] = val
  51.  
  52.                 Items[_Size-1] = val
  53.                
  54.                 Return _Size 'Items.Length - 1 'return the index it was added at
  55.         End Method
  56.        
  57.        
  58.         'return the entire list as a concatenated string with optional delimiter
  59.         'because base objects have ToString, cannot override with different parameters
  60.         Method ToDelimString:String(Delim:String = "")
  61.                 Local result:String
  62.                 Local i:Int
  63.                
  64.                 For i = 0 To _Size-2
  65.                         result:+Items[i].ToString() + Delim
  66.                 Next
  67.                 result:+ Items[_Size-1].ToString()
  68.                
  69.                 Return result
  70.         End Method
  71.        
  72.        
  73.         Method ToString:String()
  74.                 Return ToDelimString() 'just call ToDelimString with no parameters
  75.         End Method
  76.        
  77.         'You could just reference the field _Size (which is what is done throughout the code),
  78.         'but that could result in an unsafe type if you
  79.         Method Count:Int()
  80.                 Return _Size
  81.         End Method
  82.        
  83.        
  84.         'return the first index where the list contains val, else return -1
  85.         Method Contains:Int(val:Object)
  86.                 Local i:Int
  87.                
  88.                 For i = 0 To _Size-1
  89.                         If val = Items[i] Then Return i        
  90.                 Next
  91.                
  92.                 Return -1
  93.         End Method
  94.        
  95.        
  96.         Function FromObjectArray:TObjectList(val:Object[])
  97.                 Local tempList:TObjectList = TObjectList.Create()
  98.                
  99.                 Try
  100.                         tempList.Items = val
  101.                 Catch err:String
  102.                         RuntimeError("Error when converting from Object Array to TObjectList, error: ~n"+err$)
  103.                         Return Null
  104.                 End Try
  105.                
  106.                 Return tempList
  107.         End Function
  108.        
  109. Rem    
  110.         Function FromString:TObjectList(val:String, Delim:String)
  111.                 Local tempList:TObjectList = TObjectList.Create()
  112.                 Local currentChar : String = ""
  113.                 Local count : Int = 0
  114.                 Local TokenStart : Int = 0
  115.                         If Delim.Length <0 Or Delim.Length > 1 Then Return Null
  116.        
  117.                         If Len(Delim)<>1 Then Return Null
  118.        
  119.                         val = Trim(val)
  120.        
  121.                         For count = 0 Until Len(val)
  122.                                 If val[count..count+1] = delim Then
  123.                                         tempList.AddLast(val[TokenStart..Count])
  124.                                         TokenStart = count + 1
  125.                                 End If
  126.                         Next
  127.                         tempList.AddLast(val[TokenStart..Count])       
  128.                        
  129.                 Return tempList
  130.         End Function
  131. EndRem
  132.  
  133.         'if AutoAddToEnd is true then if the index specified is greater than size, use AddLast
  134.         Method Insert:Int(val:Object, index:Int, AutoAddToEnd:Int = False)
  135.                 Local i:Int
  136.                
  137.                 'If index is out of range, Return False
  138.                 If index < 0 Then Return False
  139.                 If index > _Size Then
  140.                         If Not AutoAddToEnd Then
  141.                                 Return False
  142.                         Else
  143.                                 AddLast(val)
  144.                                 Return True
  145.                         EndIf
  146.                 EndIf
  147.                
  148.                 'if the index is equal to Size then addlast
  149.                 If index = _Size Then
  150.                         AddLast(val)
  151.                         Return True
  152.                 EndIf
  153.  
  154.                 'resize Items
  155.                 'Items = Items[..Items.Length]
  156.                 _Size:+1
  157.                 'resize in bulk
  158.                 If Items.Length < _Size Then Items = Items[.._Size + StepSize]
  159.  
  160.                
  161.                 'shift Items to the right from index
  162.                 For i = _Size-1 To index+1 Step -1
  163.                         Items[i] = Items[i - 1]
  164.                         'Print "index "+ i + " " + items[i]
  165.                 Next
  166.                
  167.                 'then insert val
  168.                 Items[index] = val
  169.                 Return True
  170.         End Method
  171.        
  172.        
  173.         Method RemoveByIndex:Int(index:Int)
  174.                 Local i:Int
  175.  
  176.                 'shift Items to the left, overwriting index
  177.                 For i = index To _Size - 2
  178.                         Items[i] = Items[i + 1]
  179.                 Next
  180.                
  181.                 'shrink Items by 1
  182.                 'Items = Items[..Items.Length]
  183.                 _Size:-1
  184.                 'if the length of items is at least (2 *StepSize) larger than Size, resize the array
  185.                 'this should help prevent the size from getting out of control but keep it reasonably fast
  186.                 If _Size < Items.Length - (StepSize * 2) Then Items = Items[.._Size]
  187.                 If _Size < 0 Then _Size = 0
  188.                 'null the end one
  189.                 Items[_Size] = Null
  190.         End Method
  191.        
  192.        
  193.         Method RemoveByObject:Int(val:Object, RemoveAll:Int = False)
  194.                 Local i:Int
  195.  
  196.                 i = Contains(val)
  197.                 While i > -1
  198.                        
  199.                         RemoveByIndex(i)
  200.                         If Not RemoveAll Then Exit
  201.                         i = Contains(val)
  202.  
  203.                 Wend
  204.                
  205.                 Return True
  206.         End Method
  207.        
  208.        
  209.         Method Clear()
  210.                 Items = Items[..0]
  211.                 _Size = 0
  212.         End Method
  213.  
  214.        
  215.         Method ToArray:Object[]()
  216.                 Return Items[.._Size-1]
  217.         End Method
  218.        
  219.        
  220.         Method ToList(List:TList Var)
  221.                 For Local s:Object = EachIn items
  222.                         List.AddLast(s)
  223.                 Next
  224.         End Method
  225.        
  226.        
  227.         Method GetStepSize:Int()
  228.                 Return StepSize
  229.         End Method
  230.        
  231.         Method SetStepSize(val:Int)
  232.                 If val < 1 Then val = 1 'don't allow negative values
  233.                 StepSize = val
  234.         End Method
  235.        
  236.        
  237.         Method Sort()
  238.                 'Items[.._Size].Sort() 'sort causes a problem with null objects, so have disabled this just now.
  239.         End Method
  240.        
  241.        
  242.         Method Free()
  243.                 TObjectList.Destroy(Self)
  244.         End Method
  245.  
  246.         'returns true if swap occurred 
  247.         Method SwapByIndex:Int(FirstIndex:Int, SecondIndex:Int)
  248.                 If FirstIndex<0 Or FirstIndex > _Size-1 Or SecondIndex<0 Or SecondIndex > _Size-1 Then Return False 'if out of bounds then return false
  249.                 Local tempObject:Object
  250.                
  251.                 tempObject = items[FirstIndex]
  252.                 items[FirstIndex] = items[SecondIndex]
  253.                 items[SecondIndex] = tempObject
  254.                 Return True
  255.                
  256.         End Method
  257.        
  258.         'returns true if swap occurred 
  259.         Method SwapByVal:Int(FirstObject:Object, SecondObject:Object)
  260.                 If FirstObject = Null Or SecondObject=Null Then Return False
  261.                 Local tempObject:Object
  262.                 Local FirstIndex:Int, SecondIndex:Int
  263.                
  264.                 FirstIndex = Contains(FirstObject)
  265.                 SecondIndex = Contains(SecondObject)
  266.                
  267.                 If FirstIndex > -1 And SecondIndex > -1 Then
  268.                         tempObject = items[FirstIndex]
  269.                         items[FirstIndex] = items[SecondIndex]
  270.                         items[SecondIndex] = tempObject
  271.                         Return True
  272.                 EndIf
  273.                
  274.                 Return False
  275.         End Method
  276.  
  277.        
  278.         Function Destroy(List:TObjectList)
  279.                 List.Clear()
  280.                 List = Null
  281.                 GCCollect
  282.         End Function
  283.        
  284.        
  285.         Function Create:TObjectList(StepSize:Int = 10)
  286.                 Local tempList:TObjectList = New TObjectList
  287.                 tempList.StepSize = StepSize
  288.                 Return tempList
  289.         End Function
  290. End Type
  291.  
  292.  
  293. 'Rem test speed
  294. SeedRnd MilliSecs()
  295.  
  296. Global numberOfIterations:Int = 9999 'increase this to see the performance difference
  297.  
  298.  
  299. 'Test a TObjectList
  300. Print "~nTObjectList:~n"
  301. Global sl:TObjectList = TObjectList.Create(1000) 'change this to a 1 and see the performance change
  302.  
  303.  
  304. Local starttime:Int = MilliSecs()
  305.  
  306. For Local i:Int = 0 To numberOfIterations
  307.         sl.AddLast(Chr(Rand(65,90)) + Chr(Rand(65,90)))
  308. Next
  309.  
  310. sl.Sort()
  311.  
  312. Print MilliSecs()-Starttime + "ms"
  313. GCCollect()
  314. Print (GCMemAlloced()/1024)+"kb used"
  315.  
  316. sl.Free()
  317. Print (GCMemAlloced()/1024)+"kb after free"
  318.  
  319.  
  320. 'test a TList
  321. Print "~nTList:~n"
  322. Global sl2:TList = New TList
  323.  
  324.  
  325. starttime:Int = MilliSecs()
  326.  
  327. For Local i:Int = 0 To numberOfIterations
  328.         sl2.AddLast(Chr(Rand(65,90)) + Chr(Rand(65,90)))
  329. Next
  330.  
  331. sl2.Sort()
  332.  
  333.  
  334. Print MilliSecs()-Starttime + "ms"
  335. GCCollect()
  336. Print (GCMemAlloced()/1024)+"kb used"
  337. sl2 = Null
  338. GCCollect()
  339. Print (GCMemAlloced()/1024)+"kb after free"
  340.  
  341. 'EndRem


Comments : none...