• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[Snippet] Stack

This is my Stack library, full of features.
For the purpose of this library, requirements, changelog, api and more check the script header!

As always, I am happy about any feedback I get.

JASS:
// --------------------------------------------------------------------------------------------------------------------
//  
//  Stack
//  =====
// 
// 	Version:	1.7.0
// 	Author:		Anachron
// 
// 	Requirements:
// 		(New) Table [by Bribe] (v. 3.1) [url]http://www.hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/[/url]
// 
// 	Description:
// 		Stack is a list that includes basic features.
// 		It can be easily extended so it will provide advanced functionality.
//  
// 	History:
// 		1.0.0: Initial Release
// 		1.1.0: Add of split, switch and merge
//      1.2.0: A lot of bug fixes, added iterator, printing of debug msg
//      1.3.0: Added sorting and rand to get random element
//      1.4.0: Added first, last and onDestroy cleanup, replaced while with loop
//      1.5.0: Rearranged delete to not need a fix func
//      1.6.0: Swappred create with createEx, renamed functions to give a better clue what they do, 
//             fixed random method (thanks to Magtheridon96), used destroy instead of onDestroy
//      1.7.0: Replaced FunctionInterface with TriggerEvaluate, added full and empty methods
//
//  API:
//      ------------------------------------------------------------------------------------------------
//          Basics
//      ------------------------------------------------------------------------------------------------
//      has(int x)              --> Check if value is in stack
//      index(int value)        --> Get the index of value
//      add(int x)              --> Add a new value to the stack
//      clear()                 --> Remove all values from the stack
//      count                   --> Return how many elements are in stack
//      delete(int x)           --> Delete a value from the stack
//      full                    --> Boolean whether Stack is full or not
//      empty                   --> Boolean whether Stack is empty or not
//
//      ------------------------------------------------------------------------------------------------
//          Utilities
//      ------------------------------------------------------------------------------------------------
//      each(code x)            --> Execute this function for each value in stack
//      max[= x]                --> Get/Set maximum amount of elements in stack
//      merge(Stack x)          --> Merge other stack into current stack
//      split(Stack x, int y)   --> Split this stack with elements after y into the new stack
//      switch(int x, int y)    --> Switch indexes for value x and y
//      sort(bool asc)          --> Sort Stack ascend or descending
//
//      ------------------------------------------------------------------------------------------------
//          Iteration
//      ------------------------------------------------------------------------------------------------
//      cursor                  --> Get current cursor index location
//      direction               --> Get boolean, whether iterating is forward (true) or backward (false)
//      hasNext()               --> Boolean, whether cur is at end or not
//      hasPrev()               --> Boolean, whether cur is at start or not
//      getNext()               --> Increases cur by 1 and returns the current element
//      getPrev()               --> Decreases cur by 1 and returns the current element
//      reset()                 --> Sets cur to -1 (start)
//      end()                   --> Sets cur to count
//
//      ------------------------------------------------------------------------------------------------
//          Getters
//      ------------------------------------------------------------------------------------------------
//      get(int x)              --> Get value on index x
//      getFirst()              --> Returns first element of stack
//      getLast()               --> Returns the last element of stack
//      random()                --> Return any random value of the stack
//
//      ------------------------------------------------------------------------------------------------
//          Each Static Members
//      ------------------------------------------------------------------------------------------------
//      thistype.eachStack      --> Current instance of stack
//      thistype.eachValue      --> Current value
//      thistype.eachIndex      --> Current index
// 
// --------------------------------------------------------------------------------------------------------------------------
library Stack requires Table

	globals
		constant integer STACK_INFINITIVE = -1
		constant integer STACK_INVALID = -1
        constant boolean STACK_FIXED_MAX = true
        debug constant string STACK_COLOR = "|cffffcc00"
        debug string STACK_MSG = ""
        constant trigger STACK_EXECUTOR = CreateTrigger()
	endglobals

	module IsStack
		private Table	IndexData	= 0
		private Table	ValueData	= 0
		private integer	Count		= 0
		private integer Max			= STACK_INFINITIVE
        private integer Cur         = -1
        private boolean Dir         = true
        
        public static thistype eachStack = 0
        public static integer eachValue = 0
        public static integer eachIndex = 0
        
        debug public boolean print  = false
        
        public static method createEx takes integer max returns thistype
			local thistype this = thistype.allocate()
			set .max = max
            set .IndexData = Table.create()
            set .ValueData = Table.create()
			return this
		endmethod
        
        public static method create takes nothing returns thistype
            return thistype.createEx(STACK_INFINITIVE)
        endmethod
        
        public method operator empty takes nothing returns boolean
            return .Count == 0
        endmethod
        
        public method operator full takes nothing returns boolean
            return .Max != STACK_INFINITIVE and .Count > .Max
        endmethod
        
        public method get takes integer index returns integer
			if not .IndexData.has(index) then
				return STACK_INVALID
			endif
			
			return .IndexData[index]
		endmethod
		
		public method has takes integer value returns boolean
			return .ValueData.has(value)
		endmethod
        
        public method random takes nothing returns integer
            if .Count == 0 then
                return STACK_INVALID
            endif
            
            return .IndexData[GetRandomInt(0, .Count -1)]
        endmethod
		
		public method index takes integer value returns integer
			if not .ValueData.has(value) then
				return STACK_INVALID
			endif
			
			return .ValueData[value]
		endmethod
		
		public method add takes integer value returns boolean
			if .has(value) then
				return false
			endif
			
			if .Max != STACK_INFINITIVE and .Count >= .Max then
				return false
			endif
			
			set .IndexData[.Count] = value
			set .ValueData[value] = .Count
			set .Count = .Count +1
            
            debug if .print then
                debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                debug set STACK_MSG = STACK_MSG + "Added " + STACK_COLOR + I2S(value) + "|r" + " at [" + STACK_COLOR + I2S(.Count -1) + "|r]"
                debug call BJDebugMsg(STACK_MSG)
            debug endif
            
            return true
		endmethod
		
		method operator count takes nothing returns integer
			return .Count
		endmethod
		
		public method delete takes integer value returns boolean
            local integer index = .index(value)
			local integer lastIndex = .Count -1
			local integer lastValue = .get(lastIndex)
		
			if not .has(value) then
				return false
			endif
            
			call .ValueData.remove(value)
            if index < lastIndex then
                set .IndexData[index] = lastValue
                set .ValueData[lastValue] = index
                debug if .print then
                    debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                    debug set STACK_MSG = STACK_MSG + "Pushed " + STACK_COLOR + I2S(value) + "|r" + " from [" + STACK_COLOR + I2S(lastIndex) + "|r] " 
                    debug set STACK_MSG = STACK_MSG + "to [" + STACK_COLOR + I2S(index) + "|r]"
                    debug call BJDebugMsg(STACK_MSG)
                debug endif
            else
                call .IndexData.remove(index)
                debug if .print then
                    debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                    debug set STACK_MSG = STACK_MSG + "Deleted [" + STACK_COLOR + I2S(index) + "|r] = " + STACK_COLOR + I2S(value) + "|r"
                    debug call BJDebugMsg(STACK_MSG)
                debug endif
            endif
			set .Count = .Count -1
            
            if .Cur == index then
                if .Dir and .hasPrev() then
                    set .Cur = .Cur -1
                    debug if .print then
                        debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                        debug set STACK_MSG = STACK_MSG + "Decreased cursor to [" + STACK_COLOR + I2S(.Cur) + "|r]"
                        debug call BJDebugMsg(STACK_MSG)
                    debug endif
                elseif not .Dir and .hasNext() then
                    set .Cur = .Cur +1
                    debug if .print then
                        debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                        debug set STACK_MSG = STACK_MSG + "Increased cursor to [" + STACK_COLOR + I2S(.Cur) + "|r]"
                        debug call BJDebugMsg(STACK_MSG)
                    debug endif
                endif
            endif
            
            return true
		endmethod
        
        public method clear takes nothing returns integer
			local integer amount = .Count
		
			loop
				exitwhen .Count == 0
				call .delete(.IndexData[.Count])
			endloop
			
			return amount
		endmethod
		
		public method each takes code forEach returns integer
			local integer index = 1
			local integer iterated = 0
			local integer value = 0
			local boolean success = true
            local boolexpr forEachWrapper = Filter(forEach)
            local triggercondition forEachCondition = TriggerAddCondition(STACK_EXECUTOR, forEachWrapper)
			
            set thistype.eachStack = this
			loop
				exitwhen index > .Count
                set thistype.eachIndex = index
				
				set value = .IndexData[index]
                set thistype.eachValue = value
                
				set success = TriggerEvaluate(STACK_EXECUTOR)
				
				if .has(value) then
					set index = index +1
				endif
				
				if success then
					set iterated = iterated +1
				endif
			endloop
            
            set thistype.eachStack = 0
            set thistype.eachValue = 0
            set thistype.eachIndex = 0
			
            call TriggerRemoveCondition(STACK_EXECUTOR, forEachCondition)
            call DestroyBoolExpr(forEachWrapper)
            set forEachWrapper = null
            set forEachCondition = null
            
			return iterated
		endmethod
		
		method operator max takes nothing returns integer
			return .Max
		endmethod
        
        method operator max= takes integer max returns boolean
            if not STACK_FIXED_MAX then
                set .Max = max
                return true
            endif
            return false
        endmethod
        
        public method merge takes thistype mergeStack returns nothing
        	local integer tmpValue = 0
        	loop
        		exitwhen mergeStack.count <= 0
        		
        		set tmpValue = mergeStack.get(mergeStack.count -1)
        		call .add(tmpValue)
        		call mergeStack.delete(tmpValue)
        	endloop
        endmethod
        
        public method split takes thistype new, integer pos returns nothing
        	local integer index = .Count -1
        	
        	loop
        		exitwhen index < pos
        		
        		call new.add(.ValueData[index])
        		call .delete(.ValueData[index])
        		
        		set index = index -1
        	endloop
        endmethod
        
        public method switch takes integer left, integer right returns boolean
        	local integer leftIndex = .ValueData[left]
        	local integer rightIndex = .ValueData[right]
        	
        	if not .ValueData.has(left) or not .ValueData.has(right) then
        		return false
        	endif
        	
        	set .IndexData[leftIndex] = right
        	set .ValueData[right] = leftIndex
        	set .IndexData[rightIndex] = left
        	set .ValueData[left] = rightIndex
            
            debug if .print then
                debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                debug set STACK_MSG = STACK_MSG + "Switched [" + STACK_COLOR + I2S(leftIndex) + "|r] = " + STACK_COLOR + I2S(left)
                debug set STACK_MSG = STACK_MSG + "|r with [" + STACK_COLOR + I2S(rightIndex) + "|r] = " + STACK_COLOR + I2S(right) + "|r"
                debug call BJDebugMsg(STACK_MSG)
            debug endif
        	
        	return true
        endmethod
        
        public method sort takes boolean asc returns nothing
            local integer out = -1
            local integer ins = -1
            local integer outVal = -1
            local integer insVal = -1
            debug local boolean print = .print
        
            debug set .print = false
            
            set out = 0
            set ins = out +1
            set outVal = .get(out)
            set insVal = .get(ins)
            loop
                exitwhen out >= .Count
                
                if (insVal < outVal and asc) or (insVal > outVal and not asc) then
                    call .switch(insVal, outVal)
                    debug if .print then
                        debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
                        debug set STACK_MSG = STACK_MSG + "Replaced " + STACK_COLOR + I2S(outVal) + "|r "
                        debug set STACK_MSG = STACK_MSG + "with " + STACK_COLOR + I2S(insVal) + "|r"
                        debug call BJDebugMsg(STACK_MSG)
                    debug endif
                endif
                set ins = ins +1
                
                if ins >= .Count then
                    set out = out +1
                    set ins = out +1
                endif
                
                set insVal = .get(ins)
                set outVal = .get(out)
            endloop
            
            debug set .print = print
        endmethod
        
        method operator cursor takes nothing returns integer
            return .Cur
        endmethod
        
        method operator direction takes nothing returns boolean
            return .Dir
        endmethod
        
        public method hasNext takes nothing returns boolean
            return .Cur +1 < .Count
        endmethod
        
        public method getNext takes nothing returns integer
            if .hasNext() then
                set .Cur = .Cur +1
                set .Dir = true
                return .get(.Cur)
            endif
            return STACK_INVALID
        endmethod
        
        public method hasPrev takes nothing returns boolean
            return .Cur > 0
        endmethod
        
        public method getPrev takes nothing returns integer
            if .hasPrev() then
                set .Cur = .Cur -1
                set .Dir = false
                return .get(.Cur)
            endif
            return STACK_INVALID
        endmethod
        
        public method reset takes nothing returns nothing
            set .Cur = -1
        endmethod
        
        public method end takes nothing returns nothing
            set .Cur = .Count
        endmethod
        
        public method getFirst takes nothing returns integer
            if .Count > 0 then
                return .get(0)
            endif
            return STACK_INVALID
        endmethod
        
        public method getLast takes nothing returns integer
            if .Count > 0 then
                return .get(.Count -1)
            endif
            return STACK_INVALID
        endmethod
        
        public method destroy takes nothing returns nothing
            // tables will flush themselves on destroy
            call .IndexData.destroy()
            call .ValueData.destroy()
        endmethod
	endmodule
	
	struct Stack
		implement IsStack
	endstruct

endlibrary

Example
JASS:
private function testStack takes nothing returns nothing
        local Stack myStack = Stack.create() // create a new stack
        local integer val = 0
        
        debug set myStack.print = true
        
        // fill our stack with data
        loop
            // as long as there are less then 10 values
            exitwhen myStack.count == 10
            // add a new value 
            call myStack.add(myStack.count +1)
        endloop
        
        call BJDebugMsg("==========================================")
        
        // try to switch values, 1 with 2
        call myStack.switch(1, 2)
        
        call BJDebugMsg("==========================================")
        
        // reset the pointer, if used before
        call myStack.reset()
        // exit only when we don't have any more values
        loop
            exitwhen not myStack.hasNext()
            set val = myStack.getNext()
            // print the current value to the user
            call BJDebugMsg("Pos: " + I2S(myStack.cursor) + " - Value: " + I2S(val))
        endloop
        
        call BJDebugMsg("==========================================")
        
        // manipulate the stack
        call myStack.reset()
        // exit only when we don't have any more values
        loop
            exitwhen not myStack.hasNext()
            // delete if module leaves a rest of 1
            set val = myStack.getNext()
            if ModuloInteger(val, 3) == 1 then
                //call BJDebugMsg("Removed " + I2S(val))
                call myStack.delete(val)
            endif
        endloop
        
        call BJDebugMsg("==========================================")
        
        call myStack.sort(true)
        
        // we can also iterate other way
        call myStack.end()
        // exit only when we don't have any more values
        loop
            exitwhen not myStack.hasPrev()
            // print the current value to the user
            call BJDebugMsg("Value: " + I2S(myStack.getPrev()))
        endloop
        
        call BJDebugMsg("==========================================")
    endfunction
 
Last edited:
Level 7
Joined
Apr 30, 2011
Messages
359
  • use static ifs for those protections
  • make it extends array
  • use your own allocator + deallocator
  • use a hashtable is better than Table in this case, due to the huge amount of Table instances, use its first key for the struct id, second key used for the value if it is in positive sign (contains the value's key), or the value's key if it is in negative sign (contains the value)
  • remove that iterator thing :(
  • rename it to something else, this isn't exactly a stack (2DMap or just Map looks fine, you could make it to do nD-Map, each value relates to each other, the user can get any of the value from the other values. ex: (x, y, z), the user can get y and/or z from x)
  • make max public
 
use static ifs for those protections
Sorry but why?

make it extends array
Okay, could you explain me why that's a big deal? Didn't code for a longer time.

use your own allocator + deallocator
Back a few years ago when I was in active coding that was bad practice...

use a hashtable is better than Table in this case, due to the huge amount of Table instances, use its first key for the struct id, second key used for the value if it is in positive sign (contains the value's key), or the value's key if it is in negative sign (contains the value)
I wanna use the features of Table that I don't need to create a hashtable for my system...

remove that iterator thing :(
Really? Why? I like it. With that you can do anything. Count, filter, even remove entries of the stack in the called function.

rename it to something else, this isn't exactly a stack (2DMap or just Map looks fine, you could make it to do nD-Map, each value relates to each other, the user can get any of the value from the other values. ex: (x, y, z), the user can get y and/or z from x)
Okay I see. I just thought of anything and named it like that.

make max public
Not yet, I wanna build a construct that will do some checking. But yeah, for now it's useless.
 
Stack Library:

  • I don't think you need a create method. You can keep createEx, but you already make it so that Max = STACK_INFINITIVE so that means it should set it to that value upon creation.
  • In the method delete you can just inline lastIndex since you only use it once.
  • In the method delete you refer to .has which is below your method. You should either inline it or place the has method above the delete method. Else it will use up a trigger to evaluate it.
  • In the method each you have:
    JASS:
    if .has(value) then
        set index = index +1
    endif
    If .has(value) returns false, it won't increment the index. That would lead to an infinite loop, no?

I'll check the other one out later.

EDIT:
overcold_ice said:
use static ifs for those protections

Sorry but why?
I think he means use the debug keyword. static ifs wouldn't work in that case. It is a pretty minor deal so it is up to you whether you want protection only in debug mode.
 
Level 7
Joined
Apr 30, 2011
Messages
359
@purge: i mean debug, thanks

@anachron:
  • a struct that doesn't extends array generates double free protections and more silly codes, ask nes for more info
  • it's now preferred to use extends array and custom allocator and deallocator, ask nes too D:
  • Table has a limited instance :3 (around 8190)
  • don't use interfaces, use boolexprs + TriggerEvaluate !!!
  • good luck :D
 
I don't think you need a create method. You can keep createEx, but you already make it so that Max = STACK_INFINITIVE so that means it should set it to that value upon creation.
Thanks, fixed :)

In the method delete you can just inline lastIndex since you only use it once.
Thanks, will check about it.

[*] In the method delete you refer to .has which is below your method. You should either inline it or place the has method above the delete method. Else it will use up a trigger to evaluate it.
Good catch, I will rearrange it.

In the method each you have:
JASS:
if .has(value) then
    set index = index +1
endif
If .has(value) returns false, it won't increment the index. That would lead to an infinite loop, no?
[/LIST]
No. I was using it so you can remove elements in the callback function. Then the current slot is used for last element, so it should be iterated.

I'll check the other one out later.
Okay, thanks.

I think he means use the debug keyword. static ifs wouldn't work in that case. It is a pretty minor deal so it is up to you whether you want protection only in debug mode.
Okay, I will think about it. Any pro/con you could think of?

@Adiktus: Right now two times the same value is not supported.
I will rewrite the IdStack so its supported soon.

Edit:
a struct that doesn't extends array generates double free protections and more silly codes, ask nes for more info
Honestly, I like double free error ... It leads to better coding.

it's now preferred to use extends array and custom allocator and deallocator, ask nes too D:
Because? I don't see how Vexorians well thought routines for creating better code is in any way harmful?

Table has a limited instance :3 (around 8190)
Except you increase the instance count to any number you want to use ...

don't use interfaces, use boolexprs + TriggerEvaluate !!!
AFAIK interfaces are boolexpr + TriggerEvaluate?

good luck :D
Thanks!
 
Last edited:
Level 16
Joined
Aug 7, 2009
Messages
1,403
AFAIK interfaces are boolexpr + TriggerEvaluate?

They tend to duplicate functions, though (I still use them in one of my snippets, simply because I was lazy to go through the entire spell section and change all the buff application/removal code)

In this particular case, there's no need to use an array struct. It surely wouldn't hurt either to do the allocation manually, but the snippet doesn't use "onCreate/onDestroy" methods, or any other BS that would make it slow as hell. I personally like using array structs, but in my opinion they're overrated and using them became a quite annoying custom here, on THW, in the JASS/vJASS section.
 
I updated to Stack 1.2.0:
A lot of bug fixes, added iterator, printing of debug msg
Also I rearranged the methods.

A little test can be done like this:

JASS:
library Examples initializer init requires Stack, IndexStack

    private function init takes nothing returns nothing
        local Stack myStack = Stack.create() // create a new stack
        local integer val = 0
        
        debug set myStack.print = true
        
        // fill our stack with data
        loop
            // as long as there are less then 10 values
            exitwhen myStack.count == 10
            // add a new value 
            call myStack.add(myStack.count +1)
        endloop
        
        call BJDebugMsg("==========================================")
        
        // try to switch values, 1 with 2
        call myStack.switch(1, 2)
        
        call BJDebugMsg("==========================================")
        
        // reset the pointer, if used before
        call myStack.reset()
        // exit only when we don't have any more values
        while myStack.hasNext()
            set val = myStack.next()
            // print the current value to the user
            call BJDebugMsg("Pos: " + I2S(myStack.cur) + " - Value: " + I2S(val))
        endloop
        
        call BJDebugMsg("==========================================")
        
        // manipulate the stack
        call myStack.reset()
        // exit only when we don't have any more values
        while myStack.hasNext()
            // delete if module leaves a rest of 1
            set val = myStack.next()
            if ModuloInteger(val, 3) == 1 then
                //call BJDebugMsg("Removed " + I2S(val))
                call myStack.delete(val)
            endif
        endloop
        
        call BJDebugMsg("==========================================")
        
        // we can also iterate other way
        call myStack.end()
        // exit only when we don't have any more values
        while myStack.hasPrev()
            // print the current value to the user
            call BJDebugMsg("Value: " + I2S(myStack.prev()))
        endloop
        
        call BJDebugMsg("==========================================")
    endfunction

endlibrary

I hope you enjoy the update!
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
But it's less intuitive and it makes the code harder to read/edit.
The time won to avoid to type some letters is ridiculous comparing to the time of thinking the structure of the code or even reading.

We are not computers.

In "real" programming languages, short names were always because of the parser (or whatever else) limitations, now even C allows "long" names with the "new" language standard C99.
 
Last edited:
Level 17
Joined
Apr 27, 2008
Messages
2,455
My best advice about it :

Don't follow Nestharus, don't make a resource just because you can, but because you need it.
Ofc it's fine if you enjoy making them but don't be disappointed if there is a lack of interest from others, especially these days, and ofc it will be more and more true in the future.

And if you don't have a concrete use of it, then it's more likely that you will add extra useless stuff, or even wrong stuff.
Not to mention that you can't affirm it will work without bugs (because the code is not used).
 
Then you don't have to ask about usefulness if you know that you will use it.
Of course, but the question is: Do the others need it?

Also, have you read about Stack on wc3c.net ? (i know that exists)
You mean this?
Yeah, but it is not up to date and is missing a lot of features of my Stack lib.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Personnaly i just used UnitLL for units if needed.
But many times a simple stack is enough, it's even quite easy to write one basic from scratch.

But it's me, i don't know about other peoples.
Now, if you have a use, go for it, but again don't really expect comments about the features.
 

Update:
Added sorting (ascending, descending).
Added IndexStack (use your own indexes).
Added random function to get random value with rand().

Also added tests to the first post!


Update:
Added HandleStack.
HandleStack uses IndexStack and provides a few more utilities. (Easy setter + getter)

This will act like a wrapper for a specific handle type.
One specific handle can only have one object.
If you create the object again it will load the old one instead.

I've also updated the examples to show how easy it is to use it.
 
Updated.

Stack:
Added first(), last(), Added onDestroy cleanup, created API groups for easier navigation.

IndexStack:
Nothing

HandleStack:
Completely rewritten, acts the same as Stack, but returns handles instead of integers (ids).

Examples:
Added new HandleStack test and added a testmap.

General:
Replaced whiles with loops.

I hope you enjoy :)

Edit:
Quickfix for HandleStack: Added missing clear method
 
Couple of quick things:

- Since you're calling the .delete method above it's declaration, you're causing JassHelper to replace all calls with TriggerEvaluations. You should switch the ordering of the methods in the struct in order to avoid this.

- A user can legally declare more than one instance of a HandleStack struct :/
You should probably encourage users to declare their handleStack structs in one library called HandleStackStructs in which you would declare a couple of example structs by running the textmacro (Comment them out of course :p)
Then you would just explain in the documentation that the user should only declare them here. (It would be more of a dummy lib, like a repository)
 
Okay, I will rearrange the .delete method.
About the HandleStack stuff:
Thanks for your feedback, actually that is what the example is for, so they see how to use it...

Maybe I should describe that in the library head instead?
I would never do something like HandleStackStruct, since that is kind of ugly. (And useless)

Edit:
Added TimedStack
Added test cases for TimedStack
Rearranged methods in Stack to not need a fix func for calling.
 
Last edited:
JASS:
// --------------------------------------------------------------------------------------------------------------------
//
//  Stack
//  =====
//
//     Version:    1.5.0
//     Author:        Anachron
//
//     Requirements:
//         (New) Table [by Bribe] (v. 3.1) [url]http://www.hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/[/url]
//
//     Description:
//         Stack is a list that includes basic features.
//         It can be easily extended so it will provide advanced functionality.
//
//     History:
//         1.0.0: Initial Release
//         1.1.0: Add of split, switch and merge
//      1.2.0: A lot of bug fixes, added iterator, printing of debug msg
//      1.3.0: Added sorting and rand to get random element
//      1.4.0: Added first, last and onDestroy cleanup, replaced while with loop
//      1.5.0: Rearranged delete to not need a fix func

Well, good job here. You have the resource's name, the version number, the author's name, the required libraries with links and even a changelog.

JASS:
//  API:
//      ------------------------------------------------------------------------------------------------
//          Basics
//      ------------------------------------------------------------------------------------------------
//      has(int x)              --> Check if value is in stack
//      index(int value)        --> Get the index of value
//      add(int x)              --> Add a new value to the stack
//      clear()                 --> Remove all values from the stack
//      count                   --> Return how many elements are in stack
//      delete(int x)           --> Delete a value from the stack
//
//      ------------------------------------------------------------------------------------------------
//          Utilities
//      ------------------------------------------------------------------------------------------------
//      each(EachFunc x)        --> Execute this function for each value in stack
//      max[= x]                --> Get/Set maximum amount of elements in stack
//      merge(Stack x)          --> Merge other stack into current stack
//      split(Stack x, int y)   --> Split this stack with elements after y into the new stack
//      switch(int x, int y)    --> Switch indexes for value x and y
//      sort(bool asc)          --> Sort Stack ascend or descending
//
//      ------------------------------------------------------------------------------------------------
//          Iteration
//      ------------------------------------------------------------------------------------------------
//      cur                     --> Get current cursor index location
//      dir                     --> Get boolean, whether iterating is forward (true) or backward (false)
//      hasNext()               --> Boolean, whether cur is at end or not
//      hasPrev()               --> Boolean, whether cur is at start or not
//      next()                  --> Increases cur by 1 and returns the current element
//      prev()                  --> Decreases cur by 1 and returns the current element
//      reset()                 --> Sets cur to -1 (start)
//      end()                   --> Sets cur to count
//
//      ------------------------------------------------------------------------------------------------
//          Getters
//      ------------------------------------------------------------------------------------------------
//      get(int x)              --> Get value on index x
//      first()                 --> Returns first element of stack
//      last()                  --> Returns the last element of stack
//      rand()                  --> Return any random value of the stack

Cool, you have an incredibly rich API. Usually, we wouldn't consider that as an advantage because modularity is always better, but since we can't really approve any simple datastructure libraries anymore,
this gives you an advantage. I like how you can merge stacks, split them, sort them and even iterate over them, but what I don't like is HOW you iterate over them. The best way to implement an "each method"
is like so: method forEach takes code c returns nothing. And along with that, you would have static methods that return the current stack being iterated over (getCurrentStack())
and even the current value (getCurrentValue()). Still, I would like you to discourage the use of this method because it does a trigger evaluation inside a loop, which is pretty much a speed
killer. Also, your index method isn't well named, because it doesn't really give the user a message of what it does exactly. It should be called something like getIndex to make more sense. As for the
iteration methods, I have to admit, I'm not a fan of names like cur, dir, hasPrev and prev. It's much better to use full names like current, direction, hasPrevious and previous because it's
easier for a user to type out .current than to remember whether he has to type out .curr or .cur. Also, 'dir' isn't exactly a name that screams out "DIRECTION". This is another reason why using full names in
your API is always better :/. Now, for the getters: first() and last() may as well be method operators, because if they are to be methods, than the proper names would've been "getFirst()" and "getLast()"
respectively. As for "rand" and "get", I think getValue() and getRandomValue() would be better names because they explain exactly what the methods do (get is too general, and although rand makes sense, it
would be less intuitive after all the API changes because you'd have full names everywhere and this one short one.)

JASS:
globals
    constant integer STACK_INFINITIVE = -1
    constant integer STACK_INVALID = -1
    constant boolean STACK_FIXED_MAX = true
    debug constant string STACK_COLOR = "|cffffcc00"
    debug string STACK_MSG = ""
endglobals

So far so good.

JASS:
private Table    IndexData    = 0
private Table    ValueData    = 0
private integer    Count        = 0
private integer Max            = STACK_INFINITIVE
private integer Cur         = -1
private boolean Dir         = true

debug public boolean print  = false

Heavens no, this would make your module only function for structs that do not extend arrays. Without the default values defined, you can make this module work for any struct. All you would need to do is add
a few lines to your createEx method.

JASS:
public static method create takes nothing returns thistype
    return thistype.createEx(STACK_INFINITIVE)
endmethod

public static method createEx takes integer max returns thistype
    local thistype this = thistype.allocate()
    set .max = max
    set .IndexData = Table.create()
    set .ValueData = Table.create()
    return this
endmethod

You should switch the order of these functions because currently, this is generating a TriggerEvaluate call, which is unneeded. I mean, you already have enough TriggerEvaluate calls in there, no need to have
more, am I right? :L

JASS:
public method get takes integer index returns integer
    if not .IndexData.has(index) then
        return STACK_INVALID
    endif
    
    return .IndexData[index]
endmethod

You can optimize this by replacing the first if block with something that compares the index to (count). If the index is greater than or equal to count, return STACK_INVALID.

JASS:
public method rand takes nothing returns integer
    if .Count == 0 then
        return STACK_INVALID
    endif
            
    return .IndexData[GetRandomInt(0, .Count)]
endmethod

This function does not function correctly. If I have a count equal to 1, I would have only 1 element in my stack, but GetRandomInt(0, 1) would either return 0 or 1, meaning there would be a chance of getting
an invalid element from the stack. It should be GetRandomInt(0, .Count - 1).

JASS:
public method has takes integer value returns boolean
    return .ValueData.has(value)
endmethod

Sweet.

JASS:
public method index takes integer value returns integer
    if not .ValueData.has(value) then
        return STACK_INVALID
    endif
    
    return .ValueData[value]
endmethod

O(1) ftw. No problems here, except for the name as mentioned before.

JASS:
public method add takes integer value returns boolean
    if .has(value) then
        return false
    endif

    if .Max != STACK_INFINITIVE and .Count >= .Max then
        return false
    endif

    set .IndexData[.Count] = value
    set .ValueData[value] = .Count
    set .Count = .Count +1

    debug if .print then
        debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
        debug set STACK_MSG = STACK_MSG + "Added " + STACK_COLOR + I2S(value) + "|r" + " at [" + STACK_COLOR + I2S(.Count -1) + "|r]"
        debug call BJDebugMsg(STACK_MSG)
    debug endif
    
    return true
endmethod

Good job with the debugging here :D

JASS:
public method sort takes boolean asc returns nothing
    local integer out = -1
    local integer ins = -1
    local integer outVal = -1
    local integer insVal = -1
    debug local boolean print = .print

    debug set .print = false
    set out = 0
    set ins = out +1
    set outVal = .get(out)
    set insVal = .get(ins)
    loop
        exitwhen out >= .Count
	
        if (insVal < outVal and asc) or (insVal > outVal and not asc) then
            call .switch(insVal, outVal)
            debug if .print then
        	debug set STACK_MSG = STACK_COLOR + "Stack|r[" + STACK_COLOR+ I2S(this) + "|r]: "
        	debug set STACK_MSG = STACK_MSG + "Replaced " + STACK_COLOR + I2S(outVal) + "|r "
        	debug set STACK_MSG = STACK_MSG + "with " + STACK_COLOR + I2S(insVal) + "|r"
        	debug call BJDebugMsg(STACK_MSG)
            debug endif
        endif
        set ins = ins +1
        
        if ins >= .Count then
            set out = out +1
            set ins = out +1
        endif
        
        set insVal = .get(ins)
        set outVal = .get(out)
    endloop
    
    debug set .print = print
endmethod

I'd recommend using a MergeSort or QuickSort algorithm here to speed this up. Dirac wrote a snippet that does Merge sort: http://www.hiveworkshop.com/forums/jass-resources-412/snippet-mergesort-206213/
This could help you out.

JASS:
public method first takes nothing returns integer
    if .Count > 0 then
	return .get(0)
    else
	return STACK_INVALID
    endif
endmethod

public method last takes nothing returns integer
    if .Count > 0 then
	return .get(.Count -1)
    else
	return STACK_INVALID
    endif
endmethod

These can be optimized. Since a return statement ends the function's execution, you can change them to follow the form:
JASS:
if condition then
    return something
endif
return somethingElse


JASS:
private method onDestroy takes nothing returns nothing
    // tables will flush themselves on destroy
    call .IndexData.destroy()
    call .ValueData.destroy()
endmethod

Might as well use destroy here. onDestroy is a shit.
 
Thank you so much for the review, most of the stuff you said is more than just correct.
Heavens no, this would make your module only function for structs that do not extend arrays. Without the default values defined, you can make this module work for any struct. All you would need to do is add
a few lines to your createEx method.
Yeah, I don't know whether I should do it or not ... :)
I guess I will think about it.

a solution is to use the library_once keyword
encapsulate the struct within a library_once line of code, so whenever two scripts are generating the same handle stack struct,
only one of them will be generated
Amazing idea! Thanks! I will think about it :)
 
Level 7
Joined
Apr 30, 2011
Messages
359
  • IndexStack: what it does ??? what's the difference between the normal Stack and this
  • HandleStack: please do the textmacros
  • TimedStack: no, just no!!!
 
Level 7
Joined
Apr 30, 2011
Messages
359
timed stack is useful, yes . .
but better not to include that, since it doesn't worth it . . .
its appearance in the code is low, and its efficiency is somewhat lesser than those that the users' manually do
 
Hey Anachron, could you submit these as different resources and call them [Plugin] or [Addon] or [Extension]? :p
This way, you would be getting feedback from users on very specific parts of your Stack system, and you'd be able to know exactly how to improve each one if needed :D

(Yeah, this was your idea a couple of days ago and I'm just restating it because it's a good one)
 
Top