[Snippet] Stack

[Magtheridon96]

You have no idea how many times I have to repeat writing this snippet of code:

/***********************************************
*
*   Stack
*   v1.0.0.0
*   By Magtheridon96
*
*   - Light stack object.
*   - Similar to indexed array.
*
*   API:
*   ----
*
*       - struct Stack extends array
*
*           - static method create takes nothing returns thistype
*               - Creates a new stack.
*           - method destroy takes nothing returns nothing
*               - Destroys a stack.
*           - method push takes integer value returns nothing
*               - Adds a value to the top of a stack.
*           - method pop takes nothing returns integer
*               - Removes the top of a stack and returns the value.
*           - method get takes integer index returns integer
*               - Gets a value from the stack given the index (Zero being the first).
*           - method set takes integer index, integer value returns nothing
*               - Sets a value in the stack given the index.
*           - method has takes integer value returns boolean
*               - Determines if a value is present in the stack.
*           - method operator top takes nothing returns integer
*               - Returns the value at the top of a stack.
*           - method operator first takes nothing returns integer
*               - Returns the value at the bottom of a stack.
*           - method operator size takes nothing returns integer
*               - Returns the size of the stack.
*
***********************************************/
library Stack requires Table
    
    struct Stack extends array
        private static integer ic = 0
        private static integer ir = 0
        private static integer array rn
        
        private static integer array count
        private static Table array list
        private static Table array bool
        
        method push takes integer i returns nothing
            set list[this][count[this]] = i
            set bool[this][i] = bool[this][i] + 1
            set count[this] = count[this] + 1
        endmethod
        
        method pop takes nothing returns integer
            local integer i = list[this][count[this]-1]
            
            set bool[this][i] = bool[this][i] - 1
            set count[this] = count[this] - 1
            
            return i
        endmethod
        
        method operator size takes nothing returns integer
            return count[this]
        endmethod
        
        method operator first takes nothing returns integer
            return list[this][0]
        endmethod
        
        method operator top takes nothing returns integer
            return list[this][count[this]-1]
        endmethod
        
        method get takes integer index returns integer
            return list[this][index]
        endmethod
        
        method set takes integer index, integer value returns nothing
            set bool[this][list[this][index]] = bool[this][list[this][index]] - 1
            set list[this][index] = value
            set bool[this][value] = bool[this][value] + 1
        endmethod
        
        method has takes integer value returns boolean
            return bool[this][value] > 0
        endmethod
        
        method destroy takes nothing returns nothing
            call list[this].flush()
            call bool[this].flush()
            
            set count[this] = 0
            
            set rn[this] = ir
            set ir = this
        endmethod
        
        static method create takes nothing returns thistype
            local thistype this = ir
            
            if this == 0 then
                set ic = ic + 1
                set this = ic
            else
                set ir = rn[this]
            endif
            
            if list[this] == 0 then
                set list[this] = Table.create()
                set bool[this] = Table.create()
            endif
            
            return this
        endmethod
        
    endstruct
    
endlibrary

It's a light stack object.
Iteration is done with the method get.
You'd iterate through the stack as if you were iterating through any other indexed array.

Feel free to comment.

 

[Nestharus]

Uh... wth

module Stack
	private static integer ic = 0		//instance count
	readonly thistype next

	static method allocate takes nothing returns thistype
		local thistype this = thistype(0).next
		if (0 == this) then
			set this = ic + 1
			set ic = this
		else
			set thistype(0).next = next
		endif

		set next = 0

		return this
	endmethod
	method deallocate takes nothing returns nothing
		set next = thistype(0).next
		set thistype(0).next = this
	endmethod

	method push takes thistype node returns nothing
		set node.next = next
		set next = node
	endmethod

	method pop takes nothing returns nothing
		set next = next.next
	endmethod

	method clear takes nothing returns nothing
		local thistype end = this
		if (0 != next) then
			loop
				exitwhen 0 == end.next
				set end = end.next
			endloop
			set end.next = thistype(0).next
			set thistype(0).next = next
		endif
	endmethod

	method destroy takes nothing returns nothing
		local thistype end = this
		loop
			exitwhen 0 == end.next
			set end = end.next
		endloop
		set end.next = thistype(0).next
		set thistype(0).next = this
	endmethod
endmodule

This one almost makes me laugh ; P

module StaticStack
	private static integer c = 0		//count

	static method operator first takes nothing returns thistype
		return c
	endmethod

	method next takes nothing returns thistype
		return this-1
	endmethod
	
	static method push takes nothing returns thistype
		set c = c + 1
		return c
	endmethod

	static method pop takes takes nothing returns nothing
		set c = c - 1
	endmethod
endmodule

Yes, a static stack is extremely easy to do : ).


I'd almost add in the last thing for queues to a stack for fast clear and destroy ;o.

 

[Magtheridon96]

Not quite as useless as you made it look Nes.
I'm using a stack per item id for my recipe system (Going to update).

I'm also going to need this stack library when I update Rising_Dusk's SoundUtils library

 

[Bribe]

Magtheridon, the stack you coded is like the LinkedList I coded, and no one could even find a practical use for mine.

The LinkedList module by Dirac (well, once the overhead methods are scraped off) really poops all over these hash structures because in reality you won't hit 8190. And if you did hit that value please explain the situation to me, post the code you have, and I can un-graveyard my LinkedList.

 

[Magtheridon96]

Omg.
I just realized that this is EXACTLY like your linked list T_T

I guess it would be ok to graveyard it :/
I'll just inline this struct into my code ;p

Basically, what I was doing was creating a stack struct per item id
that is registered in the CreateRecipe function and adding Recipe
instances into each item stack. (Wherever that item appears)

Using a single doubly linked list for that would have a lot of
overhead :/

edit

        method requires takes integer id, integer charges returns thistype
        
            // Recipe Data
            set itemId[6 * this + count[this]] = id
            set charge[6 * this + count[this]] = charges
            
            // Item Stack Add
            if Stack[id] == 0 then
                // If Stack Is Null, Create and Add
                call Stack.create(id)
                call Stack[id].push(this)
            elseif not Stack[id].has(this) then
                // Else, If Instance Is Not Present, Add
                call Stack[id].push(this)
            endif
            
            // Increase Count
            set count[this] = count[this] + 1
            
            return this
        endmethod
        
        static method create takes integer result, integer charges returns thistype
            local thistype this = stack
            local integer i = 0
            
            // Increase stack
            set stack = stack + 1
            
            // This Makes Iteration Faster (Helps Avoid A Few Checks)
            loop
                set itemId[6 * this + i] = NULL
                exitwhen i == 5
                set i = i + 1
            endloop
            
            // Recipe Data
            set output[this] = result
            set outputCharge[this] = charges
            
            return this
        endmethod

The stack I used for this had a static method operator that returned an
instance based on the item id. I was going to replace that with a Table instance specific to
the Recipe struct, but I guess since I'm going to be inlining this code, I'll keep the operator.

 

[Bribe]

Grave-yarded. If you disagree, send me a PM.