What is a bucket deque?
It is a collection class, like a deque, but the data is kept in 2^n bucket arrays as a list. This allows quick allocation for increasing the deque, but at the cost of random access speed.
An enumerator search is a tad slower than a normal array deque, but memory efficiency is greater at higher capacities. (Probably completely pointless for most uses, but the second step for this would be to make an unrolled linked list.)
Example of usage:
Const MAX_DOGS:Int = 20
Function Main()
Local dq:BucketDeque<Dog> = New BucketDeque<Dog>
dq.Clear()
Print "length "+dq.Length()
For Local j:=0 To MAX_DOGS
dq.PushLast(New Dog(5,6,"larry"+j))
dq.PushFirst(New Dog(1,3.5,"curly"+j))
dq.PushFirst(New Dog(10,15,"moe"+j))
Next
Print "length "+dq.Length()
dq.DumpBuckets() ''debugging
For Local dx:Dog = Eachin dq
dx.x=2.0
Next
Print "..."
Local j:Int=dq.Length()/2
For Local i:Int = 0 To j-1
Local r:Int=Rnd(0,dq.Length()-1)
Local dg:Dog = dq.Get(r)
Print r+" "+dg.name
'Local dd:Dog = dq.PopFirst()
'Print dd.name
'dd = dq.PopLast()
'Print dd.name
Next
Print ""
Print dq.Get(dq.Length()-1).name
Print dq.Get(0).name
Print "length "+dq.Length()
'dq.DumpBuckets()
Print "done."
End
Class Dog
Field x:Float
Field y:Float
Field name:String
Method New(x#,y#,n$)
self.x=x
self.y=y
self.name = n
End
End
CLASS CODE
|