Wc3C.net Stack
 Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar

06-20-2009, 11:22 PM   #1
Anitarf
Procrastination Incarnate

Development Director

Join Date: Feb 2004
Posts: 8,189

Submissions (19)

Stack

This is an alternative, simpler, more encapsulated implementation of Ammorth's LinkedList. A lot of credit for Lists should go to Ammorth since the library is based on his work, as he made his library more powerful and more complex I was working in the other direction to create a slightly more limited, but simpler library. I think both approaches have their merits, so I am now finally submitting my version as well.

Originally, this submission was split up into two data structures, stacks and lists, however they were similar enough that I ended up merging them into one script that can function as either of the two.

Stack:
library Stack

//*****************************************************************
//*  STACK
//*
//*  written by: Anitarf
//*
//*  This is an efficient implementation of a stack in vJass. Since
//*  it is based on a linked list, I decided to add common list
//*  methods to the data structure so it can function both as
//*  a stack and a simple linked list.
//*
//*  As a linked list, it has less functionality than Ammorth's
//*  LinkedList, but is considerably faster. Note only that most of
//*  the list methods have O(n) time complexity so they may not be
//*  suitable for operations on very large lists, however due to
//*  their simplicity the list would need to be really large for
//*  this to become a problem.
//*
//*  All stack methods are of course O(1) and as fast as possible.
//*  If you just need a stack, this is definitely the best choice.
//*
//*   set s=Stack.create()  - Instanceates a new Stack object.
//*   call s.destroy()      - Destroys the Stack.
//*
//*  Stack syntax:
//*   call s.push(123)      - Pushes the value 123 on the stack.
//*                           A stack may contain multiple
//*                           instances of the same value.
//*   set i=s.peek()        - Reads the top value of the stack
//*                           and stores it to the variable i.
//*   set i=s.pop()         - Removes the top value from the stack
//*                           and stores it to the variable i.
//*   s.peek()==Stack.EMPTY - Checks if the stack is empty.
//*
//*  List syntax:
//*                           A list may contain multiple
//*                           instances of the same value.
//*   s.size                - The total number of values on the list.
//*   s.contains(123)       - Checks if the value 123 is on the list.
//*   set n=s.count(123)    - Stores the number of times the value
//*                           123 is on the list to the variable n.
//*   call s.remove(123)    - Removes one instance of the value 123
//*                           from the list. Returns false if
//*   call s.purge(123)     - Removes all instances of the value 123
//*                           from the list. Returns the number of
//*                           values that were removed.
//*   set i=s.first         - Reads the first value from the list
//*                           and stores it to the variable i.
//*   set i=s.random        - Reads a random value from the list
//*                           and stores it to the variable i.
//*   set s2=s.copy()       - Makes a copy of the list and stores
//*                           it to the variable s2.
//*   call s.enum(Func,b)   - Calls function Func for all values
//*                           on the list. The function must follow
//*                           the Enum function interface.
//*                           b is a boolean value, if it is true
//*                           then the values will be enumerated
//*                           top to bottom, if false then bottom
//*                           to top.
//*****************************************************************

public function interface Enum takes integer value returns nothing

struct Stack
// Use a totally random number here, the more improbable someone uses it, the better.
// This is the value that is returned by .pop and .peek methods and .first and .random operators when called on an empty stack.
public static constant integer EMPTY=0x28829022

// End of calibration.

private integer top = 0
private static integer free = 1
private static integer array next
private static integer array value

method push takes integer i returns nothing
// Get an index from the list of free indexes.
local integer n=Stack.free
set Stack.free=Stack.next[n]
// Extend the list of free indexes if needed.
if Stack.free==0 then
set Stack.free=n+1
endif
// Store the value to the index.
set Stack.value[n]=i
// Add index to the top of the stack.
set Stack.next[n]=.top
set .top=n
set .size=.size+1
endmethod
method pop takes nothing returns integer
// Get the top index of stack.
local integer n=.top
// Safety check in case a user pops an empty stack.
if n==0 then
debug call BJDebugMsg("stack warning: .pop called on an empty stack!")
return Stack.EMPTY
endif
// Remove the top index from stack.
set .top=Stack.next[n]
set .size=.size-1
// Add the index to the list of free indexes.
set Stack.next[n]=Stack.free
set Stack.free=n
// Return the value.
return Stack.value[n]
endmethod
method peek takes nothing returns integer
// Read the value of the top index.
return Stack.value[.top]
endmethod

method add takes integer value returns nothing
call .push(value)
endmethod
method contains takes integer value returns boolean
// Get the first index of the list.
local integer i=.top
// Search through the list.
loop
// Stop the search when the end of the list is reached.
exitwhen i==0
// Stop the search if the value is found.
if Stack.value[i]==value then
return true
endif
// Get the next index of the list.
set i=Stack.next[i]
endloop
return false
endmethod
method count takes integer value returns integer
local integer count=0
// Get the first index of the list.
local integer i=.top
// Search through the list.
loop
// Stop the search when the end of the list is reached.
exitwhen i==0
// Increase the count if the value is found.
if Stack.value[i]==value then
set count=count+1
endif
// Get the next index of the list.
set i=Stack.next[i]
endloop
return count
endmethod
method operator first takes nothing returns integer
return .peek()
endmethod
method operator random takes nothing returns integer
local integer r=GetRandomInt(1,.size)
// Get the first index of the list.
local integer i=.top
// Loop through the list.
loop
// Stop the loop after a random amount of repeats.
set r=r-1
exitwhen r==0 or i==0
// Get the next index of the list.
set i=Stack.next[i]
endloop
return Stack.value[i]
endmethod
method remove takes integer value returns boolean
// Get the first index of the list.
local integer i1=.top
local integer i2
// Check if the first index holds the value.
if Stack.value[i1]==value then
call .pop()
return true
endif
// Search through the rest of the list.
loop
set i2=Stack.next[i1]
// Stop the search when the end of the list is reached.
exitwhen i2==0
// Check if the next index holds the value.
if Stack.value[i2]==value then
// Remove the index from the stack.
set Stack.next[i1]=Stack.next[i2]
// Add the removed index to the list of free indexes.
set Stack.next[i2]=Stack.free
set Stack.free=i2
set .size=.size-1
return true
endif
set i1=i2
endloop
return false
endmethod
method purge takes integer value returns integer
local integer count=0
local integer i1
local integer i2
// If the first index holds the value, pop it.
loop
// If the list is empty, return.
if .top==0 then
return count
endif
// Repeat until the first index doesn't hold the value.
exitwhen Stack.value[.top]!=value
call .pop()
set count=count+1
endloop
// Get the first index of the list.
set i1=.top
// Search through the rest of the list.
loop
set i2=Stack.next[i1]
// Stop the search when the end of the list is reached.
exitwhen i2==0
// Check if the next index holds the value.
if Stack.value[i2]==value then
// Remove the index from the stack.
set Stack.next[i1]=Stack.next[i2]
// Add the removed index to the list of free indexes.
set Stack.next[i2]=Stack.free
set Stack.free=i2
set .size=.size-1
set count=count+1
else
set i1=i2
endif
endloop
return count
endmethod
method enum takes Enum f, boolean top2bottom returns nothing
local integer array value
// Get the first index of the list.
local integer i1=.top
local integer i2=0
// Populate the array.
loop
exitwhen i1==0
set value[i2]=Stack.value[i1]
set i2=i2+1
set i1=Stack.next[i1]
endloop
// Call the Enum function for each value in the array.
set i1=i2-1
loop
exitwhen i2==0
set i2=i2-1
// Enumerate in which direction?
if top2bottom then
call f.evaluate(value[i1-i2])
else
call f.evaluate(value[i2])
endif
endloop
endmethod
method copy takes nothing returns Stack
local Stack that=Stack.create()
// Get the first index of the list.
local integer i1=.top
local integer i2
// Add a dummy index to the top of the new list.
call that.push(0)
set i2=that.top
loop
exitwhen i1==0
// Get an index from the list of free indexes and add it at the end of the list.
set Stack.next[i2]=Stack.free
set i2=Stack.next[i2]
set Stack.free=Stack.next[i2]
// Extend the list of free indexes if needed.
if Stack.free==0 then
set Stack.free=i2+1
endif
// Copy the value to the new index.
set Stack.value[i2]=Stack.value[i1]
set i1=Stack.next[i1]
endloop
// End the new list correctly.
set Stack.next[i2]=0
// Remove the dummy index.
call that.pop()
// Copy the size value to the new list.
set that.size=this.size
return that
endmethod

method onDestroy takes nothing returns nothing
local integer n
// Remove all remaining indexes from the stack.
loop
// Get the top index.
set n=.top
exitwhen n==0
// Remove it from the stack.
set .top=Stack.next[n]
// Add it to the list of free indexes.
set Stack.next[n]=Stack.free
set Stack.free=n
endloop
endmethod
static method onInit takes nothing returns nothing
// Store the EMPTY value to index 0 to make .peek inline friendly.
set Stack.value[0]=Stack.EMPTY
endmethod
endstruct
endlibrary
__________________
 Cinema Workshop released! Let's make some cinematics! Editor's version of the winner of the Blizzard's Cinematic Contest: The Spirit of Vengeance

Last edited by Anitarf : 08-11-2009 at 01:27 AM.

 06-21-2009, 03:17 PM #2 Toadcop BuranX     Join Date: Jul 2006 Posts: 1,886 Submissions (4) it allows to store only integers ? or what. i don't get this shit code... __________________
06-21-2009, 04:01 PM   #3
Anitarf
Procrastination Incarnate

Development Director

Join Date: Feb 2004
Posts: 8,189

Submissions (19)

Quote:
 Originally Posted by Toadcop it allows to store only integers ?
Why would you need to store anything other than integers?
__________________
 Cinema Workshop released! Let's make some cinematics! Editor's version of the winner of the Blizzard's Cinematic Contest: The Spirit of Vengeance

06-21-2009, 04:09 PM   #4
Vexorian
Free Software Terrorist

Technical Director

Join Date: Apr 2003
Posts: 14,898

Submissions (37)

Quote:
 Originally Posted by Toadcop it allows to store only integers ? or what. i don't get this shit code...
Only explanation for not being to understand this code would that you are low on sugar...
__________________
 Wc3 map optimizer 5.0 Someone should fix .wav sound in this thing. JassHelper 0.A.2.A Turns your simple code into something that is complicated enough to work.
 Wc3 map optimizer 5.0 JassHelper 0.A.2.A Xye 0.12.1 | Editor/Levels xe0.9 CS16.0 My spells jEdit modes for vJass&Zinc (v9) WarCiTy 0.2.0
Faster != more useful

06-21-2009, 09:28 PM   #5
BuranX

Join Date: Jul 2006
Posts: 1,886

Submissions (4)

Quote:
 Why would you need to store anything other than integers?
i don't but i am not the potential user of this =)
i don't see any sense to make "store systems" not as textmacro.
or you wrote this for your own use and decided to post it here ?
__________________

 06-21-2009, 09:40 PM #6 Rising_Dusk Obscurity, the Art Projects DirectorProject Leader: OD   Join Date: Feb 2006 Posts: 9,729 Submissions (27) Well, TimerUtils is widely used and it can only store integers as well. I don't see the problem with that. __________________
06-21-2009, 10:16 PM   #7
Vexorian
Free Software Terrorist

Technical Director

Join Date: Apr 2003
Posts: 14,898

Submissions (37)

Quote:
 i don't see any sense to make "store systems" not as textmacro.
I don't see any sense to make any system as textmacro.
__________________
 Wc3 map optimizer 5.0 Someone should fix .wav sound in this thing. JassHelper 0.A.2.A Turns your simple code into something that is complicated enough to work.
 Wc3 map optimizer 5.0 JassHelper 0.A.2.A Xye 0.12.1 | Editor/Levels xe0.9 CS16.0 My spells jEdit modes for vJass&Zinc (v9) WarCiTy 0.2.0
Faster != more useful

 06-22-2009, 04:05 PM #8 akolyt0r In Flames     Join Date: Jan 2006 Posts: 1,154 Submissions (3) Table ? ... Well integer really should be sufficient for this one... especially with the new hashtables... __________________
 06-22-2009, 04:20 PM #9 Here-b-Trollz Corkscrew Chainsaw!!!   Join Date: Jun 2006 Posts: 711 Ehh?: // Add a value to the list. method add takes integer value returns nothing local list l = list.create() set l.next=.next set .next=l set .data=.data+1 //? endmethod __________________ By reading this signature, you agree that I cannot be held accountable for anything that I might say or do.
06-22-2009, 05:01 PM   #10
Anitarf
Procrastination Incarnate

Development Director

Join Date: Feb 2004
Posts: 8,189

Submissions (19)

Quote:
 Originally Posted by Here-b-Trollz Ehh?: // Add a value to the list. method add takes integer value returns nothing local list l = list.create() set l.next=.next set .next=l set .data=.data+1 //? endmethod
Aah.:
method operator size takes nothing returns integer
return .data
endmethod
__________________
 Cinema Workshop released! Let's make some cinematics! Editor's version of the winner of the Blizzard's Cinematic Contest: The Spirit of Vengeance

06-23-2009, 02:57 AM   #11
Here-b-Trollz
Corkscrew Chainsaw!!!

Join Date: Jun 2006
Posts: 711

Quote:
 Originally Posted by Anitarf Aah.: method operator size takes nothing returns integer return .data endmethod
I suppose I figured it was necessary to store 'value' somewhere, in order for this to be useful in any way at all. Maybe I'm wrong.
__________________
By reading this signature, you agree that I cannot be held accountable for anything that I might say or do.

06-23-2009, 05:47 AM   #12
Anitarf
Procrastination Incarnate

Development Director

Join Date: Feb 2004
Posts: 8,189

Submissions (19)

I see. Weird, I was sure that I tested it. Must have mixed it up with Stacks. Anyway, yeah, the value assigment is missing. Didn't realize that was what you were refering to. Fixed.
__________________
 Cinema Workshop released! Let's make some cinematics! Editor's version of the winner of the Blizzard's Cinematic Contest: The Spirit of Vengeance

 06-23-2009, 05:49 AM #13 Here-b-Trollz Corkscrew Chainsaw!!!   Join Date: Jun 2006 Posts: 711 okay but you are still using .data as the counter, so... EDIT: Oh, I see now. The first link in the list is the handler link, got it. __________________ By reading this signature, you agree that I cannot be held accountable for anything that I might say or do. Last edited by Here-b-Trollz : 06-29-2009 at 08:52 PM.
 06-29-2009, 08:34 PM #14 Blubb-Tec Full Metal Mapping!     Join Date: Nov 2006 Posts: 270 Submissions (1) just a quick suggestion, add .size also to the stack, main reason being that adding it is simply easy, lol. __________________ P A R T Y "In a way, we're all troubled adolescent girls... deep inside."
 07-02-2009, 10:26 PM #15 0zyx0 Perfectionist noob     Join Date: Mar 2009 Posts: 255 I would consider the lack of .size a feature. __________________ My new signature - Now easier to understand than ever!