I decided to implement – creating from scratch – a Stack collection in BlitzMax.
A stack is a ‘data structure’ – a way to collect data – and its features is to be a LIFO (Last In First Out) collection.
This means that the last thing added (push), is the first to gets pulled (pop)
BlitzMax has only Arrays, Lists and Maps as base collection structures.
My own implementation has the following methods
- Push(object) – insert an object at the ‘top’ of the stack
- Pop() – it returns the Object stored
- ToList() – it returns a list containing all the object in the stack
- ToArray() – it returns the array of objects
- Clear() – it clears the stack
- Size() – it returns the number of items in it
- Contains(object) – returns TRUE if the stack contains the object
- FindIndex(object) – returns the INDEX position in the stack of the object
- Get(ID) – returns the Object stored at the ID position in the stack
- Set(ID,Object) – set/replace the object at the ID position in the stack
- InsertAt(index,object) – inserts at index position another object
- Remove(index) – removes at index position the object
- RemoveObject(object) – removes the object from the stack
- Sort() – to sort the items in the stack
- Copy() – to create a copy of the stack
- Extract(from,to) – to extract – in a new stack – specific items
- Split(from) – to ‘split’ the original stack in 2, losing the items
- Join(stack) – to joins to 2 stack into one
Moreover it implements an Enumerator so it’s possibile to use it with the constructor FOR.. EACHIN to iterate with the collected objects.
Here the source code – I will include it in the LIB section as soon as possible.
Rem
bbdoc: Enumerator Object use by Tstack in order to implement Eachin support.
End Rem
Type TstackEnum
Field pos:Int
Field size:Int
Field _link:Object[]
Method HasNext:Int()
pos:+1
Return pos<size
End Method
Method NextObject:Object()
Local value:Object=_link[pos]
Return value
End Method
End Type
Rem
bbdoc: Stack
End Rem
Type Tstack
Field _items:Object[]
Field _count:Int
Field _enum:Int
Rem
bbdoc: Returns the size of the stack
End Rem
Method Size:Int()
Return Len(_items)
End Method
Method ObjectEnumerator:TstackEnum()
Local enum:TstackEnum=New TstackEnum
enum.pos=_enum-1
enum.size=Len(_items)
enum._link=_items
Return enum
End Method
Rem
bbdoc: Clears the content of the stack
End Rem
Method Clear:Int()
_items=_items[..0]
_count=0
_enum=0
Return 0
End Method
Rem
bbdoc: Insert an object into the stack
End Rem
Method Push:Int(ob:Object=Null)
If ob=Null Return -1
_count=Len(_items)
_items=_items[.._count+1]
_items[_count]=ob
Return 1
End Method
Rem
bbdoc: Get an object into the stack (the last inserted).
End Rem
Method Pop:Object()
If _items=Null Return Null
If _count<=0 Return Null
_count=Len(_items)
Local r:Object=_items[_count-1]
_items[_count-1]=Null
_items=_items[.._count-1] 'reducing the size of the array
_count:-1
If _count<0 _count=0
Return r
End Method
Rem
bbdoc: Returns as a Tlist the content of the stack.
End Rem
Method ToList:TList()
Local list:TList=New TList
For Local s:Object=EachIn _items
list.addlast s
Next
Return list
End Method
Rem
bbdoc: Returns as an array the content of the stack.
End Rem
Method ToArray:Object[]()
Return _items
End Method
Rem
bbdoc: Returns the object at the position @ID
End Rem
Method Get:Object(id:Int=0)
If id<0 Or id>Len(_items) Return Null
Return _items[id]
End Method
Rem
bbdoc: Sets the object at the position @ID
End Rem
Method Set:Int(id:Int=0,ob:Object=Null)
If id<0 Or id>Len(_items) Return -1
_items[id]=ob
Return 1
End Method
Rem
bbdoc: Returns the position in the stack of the object.
End Rem
Method FindIndex:Int(ob:Object)
For Local ix:Int=0 Until Len(_items)
If ob=_items[ix] Return ix
Next
Return -1
End Method
Rem
bbdoc: Returns @TRUE is the object exists in the stack.
End Rem
Method Contains:Int(ob:Object)
For Local ix:Int=0 Until Len(_items)
If ob=_items[ix] Return 1
Next
Return -1
End Method
Rem
bbdoc: Removes an object (if it exists) from the stack.
End Rem
Method RemoveObject:Int(ob:Object)
Return Remove(FindIndex(ob))
End Method
Rem
bbdoc: Removes the object at position @ID
End Rem
Method Remove:Int(ID:Int)
If id<0 Or id>Len(_items) Return -1
Local tmp:Object[]=_items[..]
Local tmp2:Object[]
tmp2=tmp[id+1..]
tmp=tmp[..id]
tmp=tmp[..Len(tmp2)+Len(tmp)]
For Local p:Int=0 Until Len(tmp2)
tmp[p+id]=tmp2[p]
Next
_items=tmp
_count:-1
Return 1
End Method
Rem
bbdoc: Insert at position @ID an object
End Rem
Method InsertAt:Int(id:Int,ob:Object)
If id<0 Or id>Len(_items) Return -1
Local tmp:Object[]=_items[..]
Local tmp2:Object[]
tmp2=tmp[id..]
tmp[id]=ob
tmp=tmp[..id+1]
tmp=tmp[..Len(tmp2)+Len(tmp)]
For Local p:Int=0 Until Len(tmp2)
tmp[p+id+1]=tmp2[p]
Next
_items=tmp[..]
_count:+1
Return 1
End Method
Rem
bbdoc: Joins to the current stack the content of another one.
End Rem
Method Join:Int(os:Tstack=Null)
If os=Null Return 0
Local p:Int=Len(_items)
_items=_items[..Len(_items)+Len(os._items)]
For Local i:Int=0 Until Len(os._items)
_items[p+i]=os._items[i]
Next
Return 1
End Method
Rem
bbdoc: Creates a copy of the stack
End Rem
Method Copy:Tstack()
Return Extract()
End Method
Rem
bbdoc: Returns a @NEW stack with items @FROM @TO
End Rem
Method Extract:Tstack(_from:Int=0,_to:Int=-1)
If _to<0 _to=Len(_items)
If _to>Len(_items) _to=Len(_items)
Local k:Tstack=New Tstack
k._items=_items[_from.._to]
Return k
End Method
Rem
bbdoc: Returns a @NEW stack containing items starting at @_FROM. The original stack losts these items.
End Rem
Method Split:Tstack(_from:Int=0)
Local _to:Int=Len(_items)
If _from<0 _from=0
Local k:Tstack=New Tstack
k._items=_items[_from.._to]
_items=_items[.._from]
Return k
End Method
Rem
bbdoc: Sort the items in the stack - it can be overriden by a method in objects
End Rem
Method Sort:Int( ascending:Int=True)
_items.sort(ascending)
Return 0
End Method
End Type
I’m thinking to add some other methods like JOIN to add another stack, and SORT.
EXAMPLE
Local s2:Tstack=New Tstack
Type Test
Field name:String,value:String
Function Create:Test(_NAME:String,v:String)
Local ss:Test=New Test
ss.name=_NAME
ss.value=v
Return ss
End Function
End Type
For Local k:Int=1 To 10
s2.Push(Test.Create("Name "+k,k))
Next
Print "Size of S2 : "+s2.size()
For Local s:Test=EachIn s2
If s
Print s.name+" "+s.value
End If
Next
s2.Pop()
Print "Size : "+s2.size()
Edit:
I’ve added new methods like JOIN, SPLIT, EXTRACT, SORT, COPY and added in source description/documentation.
On my own BlitzMax installation I’ve made a BRL.STACK module and now it’s part of the ‘standard’ command set. Here I’ve added the ‘module source code’ (just remember to create in BlitzMax/mod/BRL another folder (Stack.mod) and save the source code in it as stack.bmx.
Then compile and rebuild documentation.
SuperStrict
Rem
bbdoc: Data structures/Stack
End Rem
Module BRL.Stack
ModuleInfo "Version: 1.00"
ModuleInfo "Author: Degasperi Christian "
ModuleInfo "License: zlib/libpng"
ModuleInfo "Copyright: Blitz Research Ltd"
ModuleInfo "Modserver: BRL"
Import BRL.linkedlist
Rem
bbdoc: Enumerator Object use by Tstack in order to implement Eachin support.
End Rem
Type TstackEnum
Field pos:Int
Field size:Int
Field _link:Object[]
Method HasNext:Int()
pos:+1
Return pos<size
End Method
Method NextObject:Object()
Local value:Object=_link[pos]
Return value
End Method
End Type
Rem
bbdoc: Stack
End Rem
Type Tstack
Field _items:Object[]
Field _count:Int
Field _enum:Int
Rem
bbdoc: Returns the size of the stack
End Rem
Method Size:Int()
Return Len(_items)
End Method
Method ObjectEnumerator:TstackEnum()
Local enum:TstackEnum=New TstackEnum
enum.pos=_enum-1
enum.size=Len(_items)
enum._link=_items
Return enum
End Method
Rem
bbdoc: Clears the content of the stack
End Rem
Method Clear:Int()
_items=_items[..0]
_count=0
_enum=0
Return 0
End Method
Rem
bbdoc: Insert an object into the stack
End Rem
Method Push:Int(ob:Object=Null)
If ob=Null Return -1
_count=Len(_items)
_items=_items[.._count+1]
_items[_count]=ob
Return 1
End Method
Rem
bbdoc: Get an object into the stack (the last inserted).
End Rem
Method Pop:Object()
If _items=Null Return Null
If _count<=0 Return Null
_count=Len(_items)
Local r:Object=_items[_count-1]
_items[_count-1]=Null
_items=_items[.._count-1] 'reducing the size of the array
_count:-1
If _count<0 _count=0
Return r
End Method
Rem
bbdoc: Returns as a Tlist the content of the stack.
End Rem
Method ToList:TList()
Local list:TList=New TList
For Local s:Object=EachIn _items
list.addlast s
Next
Return list
End Method
Rem
bbdoc: Returns as an array the content of the stack.
End Rem
Method ToArray:Object[]()
Return _items
End Method
Rem
bbdoc: Returns the object at the position @ID
End Rem
Method Get:Object(id:Int=0)
If id<0 Or id>Len(_items) Return Null
Return _items[id]
End Method
Rem
bbdoc: Sets the object at the position @ID
End Rem
Method Set:Int(id:Int=0,ob:Object=Null)
If id<0 Or id>Len(_items) Return -1
_items[id]=ob
Return 1
End Method
Rem
bbdoc: Returns the position in the stack of the object.
End Rem
Method FindIndex:Int(ob:Object)
For Local ix:Int=0 Until Len(_items)
If ob=_items[ix] Return ix
Next
Return -1
End Method
Rem
bbdoc: Returns @TRUE is the object exists in the stack.
End Rem
Method Contains:Int(ob:Object)
For Local ix:Int=0 Until Len(_items)
If ob=_items[ix] Return 1
Next
Return -1
End Method
Rem
bbdoc: Removes an object (if it exists) from the stack.
End Rem
Method RemoveObject:Int(ob:Object)
Return Remove(FindIndex(ob))
End Method
Rem
bbdoc: Removes the object at position @ID
End Rem
Method Remove:Int(ID:Int)
If id<0 Or id>Len(_items) Return -1
Local tmp:Object[]=_items[..]
Local tmp2:Object[]
tmp2=tmp[id+1..]
tmp=tmp[..id]
tmp=tmp[..Len(tmp2)+Len(tmp)]
For Local p:Int=0 Until Len(tmp2)
tmp[p+id]=tmp2[p]
Next
_items=tmp
_count:-1
Return 1
End Method
Rem
bbdoc: Insert at position @ID an object
End Rem
Method InsertAt:Int(id:Int,ob:Object)
If id<0 Or id>Len(_items) Return -1
Local tmp:Object[]=_items[..]
Local tmp2:Object[]
tmp2=tmp[id..]
tmp[id]=ob
tmp=tmp[..id+1]
tmp=tmp[..Len(tmp2)+Len(tmp)]
For Local p:Int=0 Until Len(tmp2)
tmp[p+id+1]=tmp2[p]
Next
_items=tmp[..]
_count:+1
Return 1
End Method
Rem
bbdoc: Joins to the current stack the content of another one.
End Rem
Method Join:Int(os:Tstack=Null)
If os=Null Return 0
Local p:Int=Len(_items)
_items=_items[..Len(_items)+Len(os._items)]
For Local i:Int=0 Until Len(os._items)
_items[p+i]=os._items[i]
Next
Return 1
End Method
Rem
bbdoc: Creates a copy of the stack
End Rem
Method Copy:Tstack()
Return Extract()
End Method
Rem
bbdoc: Returns a @NEW stack with items @FROM @TO
End Rem
Method Extract:Tstack(_from:Int=0,_to:Int=-1)
If _to<0 _to=Len(_items)
If _to>Len(_items) _to=Len(_items)
Local k:Tstack=New Tstack
k._items=_items[_from.._to]
Return k
End Method
Rem
bbdoc: Returns a @NEW stack containing items starting at @_FROM. The original stack losts these items.
End Rem
Method Split:Tstack(_from:Int=0)
Local _to:Int=Len(_items)
If _from<0 _from=0
Local k:Tstack=New Tstack
k._items=_items[_from.._to]
_items=_items[.._from]
Return k
End Method
Rem
bbdoc: Sort the items in the stack - it can be overriden by a method in objects
End Rem
Method Sort:Int( ascending:Int=True)
_items.sort(ascending)
Return 0
End Method
End Type