Stack

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

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close