hierarchy/Stack modules

BlitzMax Forums/BlitzMax Module Tweaks/hierarchy/Stack modules

Bot Builder

(Posted 2005) [#1]

Hierarchy.bmx:

Strict

Rem
bbdoc: Hierarchy
End Rem
Module BOT.Hierarchy

ModuleInfo "Version: 1.00"
ModuleInfo "Author: Michael Sloan aka BotBuilder"
ModuleInfo "License: Blitz Shared Source Code"
ModuleInfo "Copyright: Michael Sloan"
'ModuleInfo "Modserver: BRL"

Import bot.stack
Import brl.standardio

Type Node
	Field Nxt:Node,Prv:Node
	Field Val:Object
	
	Rem
	bbdoc: Retrieves the node's position in the list
	about: 0 is the first node, 1 is the one after the first, etc
	returns: The node's index in the list
	Tested: GetIndex front, GetIndex middle, GetIndex last
	EndRem
	Method GetIndex%()
		Local cur:Node=Self,count=0
		While cur.prv<>Null
			count:+1
			cur=cur.prv
		Wend
		Return count
	End Method
End Type

Type Group Extends Node
	Field First:Node, Last:Node
	Field Enums:LIFO

	Method New()
		Enums=New LIFO
	End Method

	Rem
	bbdoc: Adds a node to the beginning of the group's linked list
	about: If given a node or a group, it'll insert that rather than creating a new node with the given object as data.
	returns: Inserted node
	Tested: From empty group, Group with other objects, Add node
	EndRem
	Method AddFirst:node(O:Object)
		Local n:Node
		If Node(O) Then			'Provide it with a node/group and it is used rather than making a new one
			n=Node(O)
		Else
			n=New Node
			n.Val=O
		EndIf
		If first=Null Then
			first=n
			last=n
		Else
			n.nxt=first
			first.prv=n		'Set up back/forth link to original first
			first=n
		EndIf
		Return n
	End Method

	Rem
	bbdoc: Adds a node To the End of the group's linked list
	about: If given a node Or a group, it'll insert that rather than creating a new node with the given object as data.
	returns: Inserted node
	Tested: Group with other objects, from empty group, Add node
	EndRem
	Method AddLast:node(O:Object)
		Local n:Node
		If Node(O) Then
			n=Node(O)
		Else
			n=New Node
			n.Val=O
		EndIf
		If first=Null Then
			first=n
			last=n
		Else
			n.prv=last
			last.nxt=n		'Set up back/forth link to original last
			last=n
		EndIf
		Return n
	End Method

	Rem
	bbdoc: A more convenient name for AddLast
	about: Can be overridden in derivative types
	EndRem
	Method Add:node(O:Object)
		Return AddLast(O)
	End Method
	
	Rem
	bbdoc: Converts the list to an array
	about: If multilevel is set to true then it will turn groups into arrays of the array, if first is value then the first element of each array (and child arrays) is the node value
	Tested: Standard array, Multilevel
	EndRem
	Method ToArray:Object[](multilevel=False, FirstIsValue=False)
		Local cnt=count()
		If FirstIsValue Then cnt:+1
		Local out:Object[]=New Object[cnt],i=0
		If FirstIsValue Then
			i=1
			out[0]=val
		EndIf
		If multilevel Then
			For Local o:Object=EachIn Self
				If Group(o) Then out[i]=Group(o).ToArray(True,FirstIsValue) Else out[i]=o
				i:+1
			Next
		Else
			For Local o:Object=EachIn Self
				out[i]=o
				i:+1
			Next
		EndIf
		Return out
	End Method
	
	Rem
	bbdoc: Creates a group from an array
	returns: The array
	about: If multilevel is true then it will convert arrays within the array
	Tested: Basic, multilevel
	EndRem
	Function FromArray:Group( Input:Object[], multilevel=False, firstisvalue=False )
		Local g:group=New group
		If firstisvalue Then g.val=Input[0]
		If firstisvalue Then firstisvalue=1 Else firstisvalue=0
		For Local i=firstisvalue Until Input.length
			If multilevel And (Object[](Input[i])) Then FromArray(Object[](Input[i]),multilevel,firstisvalue) Else g.Add(Input[i])
		Next
		Return g
	End Function
	
	Rem   I realized that these would require me to import TList...  Chances are if they are using this they wont be using tlist.
	bbdoc: Creates a list from the group
	about: noidea why you would ever want to
	method ToList:TList(multilevel=false,firstisvalue=false)
		
		For o:object=eachin self
			
		Next
	endmethod

	bbdoc: Creates a group from a list
	about: this makes a bit more sense than ToList
	Function FromList:group(l:TList, multilevel=False, firstisvalue=False)

	End Function
	EndRem
	
	Rem
	bbdoc: Creates a comma delimeted string of contents
	about: Uses each object's ToString method
	returns: The string
	Tested: Basic
	EndRem
	Method ToString$()
		Local sum$
		For Local o:Object=EachIn Self
			If String(o)<>"" Then sum$:+String(o)+","
		Next
		If sum$<>"" Then sum$=Sum$[..sum.length-1]
		Return sum
	End Method
	
	Rem
	bbdoc: Creates a group from a common delimited list
	about: To do custom string splits use the SplitString function
	Returns: The group
	Tested: Basic
	EndRem
	Function FromString:group(s$)
		Return SplitString(s$,[","," "])
	End Function
	
	Rem
	bbddoc: Splits a string into parts
	about: str$ is the string to be splitted, splitters is an array of splitters to be used on the string. At every point in the string that a splitter is detected the parts before and after (until another splitter or the limits of the string) are added to the group. Flags can be used to modify the begaviour.  They can be 0-3.  0 is not case sensitive, and splitters not included in the group. 1 is not case sensitive, and splitters included in the group. 2 is case sensitive, and splitters not included in the group. 3 is case sensitive and splitters included in the group.  The last parameter is default which allows a default to be set. 
	Returns: The group
	Tested: basic sentance
	EndRem
	Function SplitString:group(str$,splitters$[],flags[]=Null)
		Local last=0,ret:group=New group,lstr$=str.tolower()
		If flags Then
			For Local i=0 Until splitters.length
				If flags[i]=1 Or flags[i]=3 Then splitters[i]=splitters[i].tolower()
			Next
		EndIf
		For Local i=0 Until str.length
			For Local j=0 Until splitters.length
				If splitters[j].length<=(str.length-i) Then
					'test both iterative and sectioning approaches
					Local caseSensitive, KeepSplitters
					If flags Then
						caseSensitive=(flags[j]>1)
						If flags[j]=1 Or flags[j]=3 Then Keepsplitters=1
					EndIf
					If casesensitive Then
						If splitters[j]=str[i..i+splitters[j].length] Then Continue
					Else
						If splitters[j]<>lstr[i..i+splitters[j].length] Then Continue
					EndIf
					If i-last>0 Then ret.Add(str[last..i])
					If KeepSplitters Then ret.Add(splitters[j])
					last=i+splitters[j].length
					Exit
				EndIf
			Next
		Next
		If str.length-last>0 Then
			ret.Add(str[last..])
		EndIf
		Return ret
	End Function
	
	Rem
	bbdoc: Counts the number of nodes in the list
	returns: The number of nodes
	Tested: Group with contents
	End Rem
	Method Count()
		Local i=0
		For Local o:Object=EachIn Self
			i:+1
		Next
		Return i
	End Method
	
	Rem
	bbdoc: Checks If the group has child nodes
	Tested: List with contents, Empty list
	EndRem
	Method IsEmpty()
		Return First=Null				'lets hope its empty if the handle to the first is null
	End Method

	Rem
	bbdoc: Finds a Node given the value
	about: Does both a pointer comparison And data comparison using Compare Method
	Tested: First, middle, last, and nonexisting object
	EndRem
	Method FindNode:Node(O1:Object)
		For Local O2:Object=EachIn Self
			If O2=O1 Or O2.Compare(O1)=0 Then Return CurrentNode()
		Next
		Return Null
	End Method

	Rem
	bbdoc: Checks If an Object value is In the list
	about: Uses Find node, so if you are going to be using FindNode later, might as well store the result of findnode in a temp variable, and use it twice.
	Tested: First, middle, last, and nonexisting object
	EndRem
	Method Contains(O:Object)
		If FindNode(O) Then Return True Else Return False
	End Method

	Rem
	bbdoc: Current node in the top enumerator
	about: If you have nested for eachin loops of the same group that exit early you will run into problems.  This also applys to using one of the methods of the group that has an early-exiting foreach loop.  (returns count)
	Tested: First, Middle, Last Node
	EndRem
	Method CurrentNode:Node()
		Local Grenum:GroupEnum=GroupEnum(Enums.Peek())
		Return Grenum.Current()
	End Method
	
	Rem
	bbdoc: Retrieves the node at the specified index
	returns: The node value of the index - may be a group
	Tested: First, middle, last nodes
	End Rem
	Method NodeAtIndex:Node(index)
		Local cur:Node=First
		For Local i=0 Until index
			cur=cur.nxt
		Next
		Return cur
	End Method
	
	Rem
	bbdoc: Retrieves the value of the node at a specified index
	returns: The node at the specified index
	Tested: First, middle, last values
	EndRem
	Method ValueAtIndex:Object(index)
		Local cur:Node=First
		For Local i=0 Until index
			cur=cur.nxt
		Next
		Return cur.val
	End Method
	
	Rem
	bbdoc: Removes a node from a group
	about: Make sure that the node is a member of the group.  Although in most cases it does not matter, if it is the first or the last node of a different group it will mess up.  Will work for groups as a group extends a node.
	Tested: First, Middle, Last nodes
	EndRem
	Method RemoveNode(n:node)
		If n=first Then first=First.nxt
		If n=last Then last=last.prv
		If n.nxt Then n.nxt.prv=n.prv
		If n.prv Then n.prv.nxt=n.nxt
		n.nxt=Null
		n.prv=Null
	EndMethod
	
	Rem
	bbdoc: Removes a value from a group
	about: Only removes the first instance of the value
	Tested: First, middle, Last Nodes
	EndRem
	Method RemoveValue(o:Object)
		RemoveNode(FindNode(o))
	End Method
	
	Rem
	bbdoc: Debugs the group to the command line in a human readable format - the ToString method of each node's value is called.
	about: Child groups are denoted with indentation, and \_name for each group.
	Tested: Basic group, Multilevel, Null values
	EndRem
	Method Debug(indent=0)
		For Local d:Object=EachIn Self
			If group(d) Then
				Print RepeatString("  ",indent)+"\_"+String(group(d).val)
				group(d).Debug(indent+1)
			Else
				Print RepeatString("  ",indent)+String(D)
			EndIf
		Next
	End Method

	Rem
	bbdoc: Convenience function to replace a node with a group
	about: Takes the nodes current value and puts it in the groups value field
	returns: Handle to the new group
	Tested: First, Middle, Last nodes
	EndRem
	Method NodeToGroup:group(n:node)
		Local g:group=New group
		g.prv=n.prv
		g.nxt=n.nxt
		If n.prv Then n.prv.nxt=g
		If n.nxt Then n.nxt.prv=g
		g.val=n.val
		If first=n Then first=g
		If last=n Then last=g
		Return g
	End Method

	Rem
	bbdoc: Reverses the order of the group's nodes
	about: Uses a for each loop so until mark fixes the problems with enumerators, you might have problems accessing the current node after this runs.
	tested: Basic
	EndRem
	Method Reverse()
		For Local o:Object=EachIn Self
			Local t:node=CurrentNode(),t2:node
			t2=t.prv
			t.prv=t.nxt
			t.nxt=t2
		Next
		Local t:node=first
		first=last
		last=t
	End Method

	Rem
	bbdoc: Returns a duplicate of the group
	about: Elsewhere known as a deep copy.  Uses a for each loop so until mark fixes the problems with enumerators, you might have problems accessing the current node after this runs.
	tested: Basic, multilevel
	EndRem
	Method Copy:Group(multilevel=False)
		Local g:group=New group
		For Local o:Object=EachIn Self
			g.Add(o)
		Next
		g.val=val
		Return g
	End Method
	
	Rem
	bbdoc: Cleans up the group by removing null nodes
	about: If the nodes are groups it doesn't do anything. If multilevel is true then it will take null nodes out of child groups
	Tested: Basic
	EndRem
	Method RemoveNullNodes(multilevel=False)
		Local cur:node=first
		While cur
			If group(cur) Then
				group(cur).RemoveNullNodes(multilevel)
			Else
				If cur.val=Null Then RemoveNode(cur)
			EndIf
			cur=cur.nxt
		Wend
	End Method
	
	Rem
	bbdoc: Cleans up the group by removing empty child groups
	about: If multilevel is true then it will take out empty grand children, great grand children, etc groups
	Tested: Basic, Multilevel
	EndRem
	Method RemoveEmptyGroups(multilevel=False)
		For Local g:group=EachIn Self
			If g.First=Null Then RemoveNode(g)
			If multilevel Then g.RemoveEmptyGroups(True)
		Next
	End Method
	
	Rem
	bbdoc: Cleans up the group by removing null nodes and empty groups
	about: If multilevel is true it cleans up child groups too
	Tested: Basic, multilevel
	EndRem
	Method Clean(multilevel=False)
		RemoveNullNodes(multilevel)
		RemoveEmptyGroups(multilevel)
	End Method
	
	Rem
	bbdoc: Switches the places of two nodes in this group
	about: Swaps the nodes' location not data
	Tested: First, middle, last
	EndRem
	Method SwapNodes(n1:node,n2:node)
		If first=n1 Then first=n2 ElseIf first=n2 Then first=n1
		If last=n1 Then last=n2 ElseIf last=n2 Then last=n1
		If n1.nxt Then n1.nxt.prv=n2
		If n1.prv Then n1.prv.nxt=n2
		If n2.nxt Then n2.nxt.prv=n1
		If n2.prv Then n2.prv.nxt=n1
		Local t:node=n1.nxt
		n1.nxt=n2.nxt
		n2.nxt=t
		t=n1.prv
		n1.prv=n2.prv
		n2.prv=t
	End Method
	
	Rem
	bbdoc: Swaps nodes in different groups
	about: Swaps the nodes' location not data. g1 is n1's group, g2 is n2's group
	Tested: First, middle, last
	EndRem
	Function CrossSwap(n1:node,g1:group,n2:node,g2:group)
		If g1.first=n1 Then g1.first=n2 ElseIf g2.first=n2 Then g2.first=n1
		If g1.last=n1 Then g1.last=n2 ElseIf g2.last=n2 Then g2.last=n1
		If n1.nxt Then n1.nxt.prv=n2
		If n1.prv Then n1.prv.nxt=n2
		If n2.nxt Then n2.nxt.prv=n1
		If n2.prv Then n2.prv.nxt=n1
		Local t:node=n1.nxt
		n1.nxt=n2.nxt
		n2.nxt=t
		t=n1.prv
		n1.prv=n2.prv
		n2.prv=t
	End Function
	
	Rem
	bbdoc: Required for For...Each
	about: Could be used to enumerate through the group easily without using for...each.  Note that it returns a GEnum, which is different from a GroupEnum.  They would be the same, but this makes the effect of mark not tweaking the compiler not so bad.
	returns: Enumerator type
	Tested: List containing nodes
	End Rem
	Method ObjectEnumerator:GEnum()
		Local Enum:GEnum=New GEnum
		Enum.D.Nxt=First
		Enum.D.Origin=Self
		Enums.Push(Enum.D)
		Return Enum
	EndMethod
End Type

Type GroupEnum
	Field Nxt:Node
	Field Origin:Group
	
	Rem
	bbdoc: The last enumerator's node
	returns: The last enumerator's node
	about: Currently very buggy as it is the last created enumerator's handle.  I would prefer the enclosing enumerator, however mark has not implemented a very simple call to delete the enumerator on loop exit.
	Tested: First, middle, last node
	EndRem
	Method Current:Node()
		If nxt Then Return Nxt.prv Else Return origin.last
	End Method
End Type

'Private type forced upon me by mark
Type GEnum
	Field D:GroupEnum
	
	Method New()
		D=New GroupEnum
	End Method
	
	Method Delete()
		D.Origin.Enums.Pop()
	End Method

	Method HasNext()
		If D.Nxt Then 
			Return True
		Else
			D.Origin.Enums.Pop()
			Return False
		EndIf
	End Method
	
	Method NextObject:Object()
		Local t:node=D.nxt
		D.nxt=t.nxt
		If group(t) Then Return group(t) Else Return t.Val
	EndMethod
End Type

Private

'The wierd old String() function in blitz - only ever used it for one thing - the thing here. A native string method would be better though because this way initializes objects over and over again.
Function RepeatString$(s$,count)
	Local out$
	For Local i=0 Until count
		out:+s
	Next
	Return out$
End Function

stack.bmx:

Strict

'Toadd count, reverse, copy, toarray, fromarray, totlist, fromtlist, debug depending on if there's demand or not

Rem
bbdoc: Stack
End Rem
Module BOT.Stack

ModuleInfo "Version: 1.00"
ModuleInfo "Author: Michael Sloan aka BotBuilder"
ModuleInfo "License: Blitz Shared Source Code"
ModuleInfo "Copyright: Michael Sloan"
'ModuleInfo "Modserver: BRL"

Rem
bbdoc: Entry in a LIFO, or perhaps later LILO stack
EndRem
Type StackEntry
	Field Value:Object
	Field Nxt:StackEntry
End Type

Rem
bbdoc: Abstract type - both LIFO and LILO 
EndRem
Type Stack Abstract
	Field Current:StackEntry

	Method Push(Data:Object) Abstract

	Rem
	bbdoc: Pops an object off the stack
	returns:  The object
	EndRem
	Method Pop:Object()
		?debug
		If Current=Null Then Throw "None left on stack in stack routines"
		?
		Local Val:Object=Current.Value
		Current=Current.Nxt
		Return Val
	End Method
	
	Rem
	bbdoc: Checks an object on the stack's data without removing it
	about: Distance is distance back from the top - most recent items. It defaults to 0, so is like a pop that doesnt take it off.
	EndRem
	Method Peek:Object(distance=0)
		Local Res:StackEntry=Current
		For Local i=0 To distance-1
			Res=Res.Nxt
			?debug
			If Res=Null Then Throw "Attempt to peek too far back in stack routines"
			?
		Next
		Return Res.Value
	End Method
	
	Rem
	bbdoc: Doesn't actually need it like hierarchy stuff does, just utility
	EndRem
	Method Clear()
		While current
			Local tmp:StackEntry=current
			current=current.nxt
			tmp.nxt=Null
		Wend
		current=Null
	End Method
	
	Rem
	bbdoc: Checks if the stack is empty
	returns: if the stack is empty
	EndRem
	Method IsEmpty()
		Return Current=Null
	End Method
End Type

Rem
bbdoc: This is a LIFO stack of objects
about: LIFO = last in first out.  It's very handy for various computer tasks.
EndRem
Type LIFO Extends Stack
	Rem
	bbdoc: Pushes an object onto the stack
	EndRem
	Method Push(Data:Object)
		If Current=Null Then
			Current=New StackEntry
			Current.Value=Data
		Else
			Local nw:StackEntry=New StackEntry
			nw.Value=Data
			nw.Nxt=Current
			Current=nw
		EndIf
	End Method
End Type

Rem
bbdoc: This is a LILO stack of objects
about: LILO = last in last out.  It's fairly handy for various computer tasks.
EndRem
Type LILO Extends Stack
	Field First:StackEntry

	Method Pop:Object()
		Local t:Object=Super.Pop()
		If Current=Null Then First=Null
		Return t
	End Method

	Rem
	bbdoc: Pushes an object onto the stack
	EndRem
	Method Push(Data:Object)
		If First=Null Then
			First=New StackEntry
			First.Value=Data
			Current=First
		Else
			Local nw:StackEntry=New StackEntry
			nw.Value=Data
			First.nxt=nw
			First=nw
		EndIf
	End Method
End Type

Have fun, feel free to post requests. brl, maybe include these in the pub.mod on the modserver?

gellyware

(Posted 2005) [#2]

Hey bot,

The hierarchy doesnt work due to an 'end rem' without the original rem around line 160.

Change it to:

	Rem
	Function FromList:group(l:TList, multilevel=False, firstisvalue=False)

	End Function
	EndRem

and it works!

Also, did you make a commands.html help file?

Bot Builder

(Posted 2005) [#3]

Hehe, I guess nested Rem EndRems dont work. no, i didn't make a commands.html file. I'm not developing with blitz for compilers any more. All .net now. There's this cool language called Boo for .net and I'm working in C# on mono compiler stuff (Cecil, ilasm, ildasm, iloptimze).

REDi	(Posted 2005) [#4]

Very nice Bot, I think BRL should add these officially.

Bot Builder

(Posted 2005) [#5]

Thanks papa. Me too :)