Bucket Deque

AdamRedwoods

(Posted 2013) [#1]

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


Class BucketDeque<T>
	
	Const CAPACITY:Int = 64 ''** MUST be power of 2 **
	Const CAPACITY_SHR:Int = 8 ''n is 2^n=capacity
	
	Field bucketList:List<BucketBase<T>> = New List<BucketBase<T>>
	
	Field topBucketNode:list.Node<BucketBase<T>>
	Field botBucketNode:list.Node<BucketBase<T>>
	Field topBucket:BucketBase<T>
	Field botBucket:BucketBase<T>
	Field length:int
	
	Method New()
		Self.Clear()

	End
	
	Method Clear:Void()
		bucketList.Clear()

		topBucket = New BucketBase<T>
		topBucketNode = bucketList.AddLast(topBucket)
		botBucket = topBucket
		botBucketNode =topBucketNode

	End
	
	Method Length:Int() Property
		Return length
	End
	
	Method GetTopIndex:Int()
		Return topBucket.top
	End
	
	Method GetBottomIndex:Int()
		Return botBucket.bot
	End
	
	
	Method PushFirst:Void(value:T)
		
		If topBucket.top= 0
			''add new bucket to top
			topBucket = New BucketBase<T>
			topBucketNode = bucketList.AddFirst(topBucket)
			topBucket.top=CAPACITY
		Endif
		
		topBucket.top-=1
		length+=1
		topBucket.data[topBucket.top] = value
'Print "add top "+topBucket.top+" len:"+length		
	End
	
	Method PushLast:Void(value:T)
		
		If botBucket.bot=CAPACITY-1
			''add new bottom bucket
			botBucket = New BucketBase<T>
			botBucketNode = bucketList.AddLast(botBucket)
			botBucket.bot = -1
		Endif
		
		botBucket.bot+=1
		length+=1
		botBucket.data[botBucket.bot] = value	
'Print "add bot "+botBucket.bot+" len:"+length		
	End

	
	Method PopFirst:T()
		
		If topBucket.top=CAPACITY
			topBucketNode = topBucketNode.NextNode()
			topBucket = topBucketNode.Value()
			
			If topBucket = Null Then Return Null
			topBucket.top = 0
		Endif
		
		If topBucket=botBucket And topBucket.top>botBucket.bot Then Return Null
		
		Local rv:T = topBucket.data[topBucket.top]
		topBucket.data[topBucket.top] = Null
		
		topBucket.top +=1
		If length>0 Then length-=1
		
		Return rv
		
	End
	
	Method PopLast:T()
		
		If botBucket.bot<0
			botBucketNode = botBucketNode.PrevNode()
			botBucket = botBucketNode.Value()
			
			If botBucket = Null Then Return null
			botBucket.bot = CAPACITY-1
		Endif
		
		If topBucket=botBucket And topBucket.top>botBucket.bot Then Return Null
		
		Local rv:T = botBucket.data[botBucket.bot]
		botBucket.data[botBucket.bot] = Null
		
		botBucket.bot -=1
		If length>0 Then length-=1
		
		Return rv
		
	End
	
	
	Private ''
	
	Field _curBucket:list.Node<BucketBase<T>>
	Field _curBucketNum:Int
	Field _offset:int
	
	Public ''
	
	Method Get:T( index:Int)

#If CONFIG="debug"	
		If index<0 Then Error "Error: No neg index"
#Endif
		
		index = index+topBucket.top
		Local num:Int = index Shr CAPACITY_SHR 'index/(CAPACITY+1)
		index = index-(num Shl CAPACITY_SHR) '*(CAPACITY+1)
'Print "get "+num+" "+index


		If _curBucket = Null
			_curBucket = topBucketNode
			If _curBucket = Null Then Return null
		Endif
		
		While (num<>_curBucketNum)
			If num>_curBucketNum
				_curBucket = _curBucket.NextNode()
				If _curBucket=Null Then Exit
				_curBucketNum +=1
			Else If num<_curBucketNum
				_curBucket = _curBucket.PrevNode()
				If _curBucket=Null Then Exit
				_curBucketNum -=1
			Endif
		Wend
		
		Return _curBucket.Value().data[index]
		
	End
	
	
	Method ObjectEnumerator:Enumerator<T>()
		Return New Enumerator<T>(Self)
	End
	
	Method DumpBuckets:Void( )
		For Local b:BucketBase<T> = Eachin bucketList
			Print "-bucket"
			For Local i:Int=0 To b.CAPACITY-1
				If b.data[i] Then Print "i:"+i+" "+b.data[i].name ''this may error out if data has no name
			Next
		Next
	End
End



Class BucketBase<T>

	Field data:T[]
	Field top:Int=0
	Field bot:Int=-1
	
	Method New()
		data = New T[BucketDeque<T>.CAPACITY]
	End

End


Class Enumerator<T>

	Method New( stack:BucketDeque<T> )
		Self.stack=stack
		Self.bucket = stack.bucketList.FirstNode()
		Self.offset = bucket.Value().top-1
		Self.index = 0
		Self.sub_index = offset
		
	End

	Method HasNext:Bool()
		Return index<stack.Length()
	End

	Method NextObject:T()
	
		sub_index +=1
		index+=1
		
		'' bucket change
		If sub_index>BucketBase<T>.CAPACITY-1
			bucket =bucket.NextNode()
			sub_index = 0
		Endif
		
#If CONFIG="debug"		
		If bucket=Null Then Error "BucketDeque error!"
#Endif
		
		Local v:T = bucket.Value().data[sub_index]
		
		Return v
		
	End

Private

	Field stack:BucketDeque<T>
	Field bucket:list.Node<BucketBase<T>>
	Field index:Int, sub_index:Int, offset:int
	
End

Sammy

(Posted 2013) [#2]

What coding scenarios do you see using data structure be advantageous Adam?

AdamRedwoods

(Posted 2013) [#3]

Any time you have a stack or deque where the object type is rather large, and resizing the array takes a lot of time.

Sammy

(Posted 2013) [#4]

Ok, thank a Adam, no harm in having another weapon at our disposal! ;)