wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Resources > Code Resources > Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 06-20-2009, 11:22 PM   #1
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,085

Submissions (19)

Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default 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.

Collapse 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:
//*   call s.add(123)       - Adds the value 123 to the list.
//*                           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
//*                           the value was not found on the list.
//*   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.

        readonly integer size = 0
        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
__________________

Last edited by Anitarf : 08-11-2009 at 01:27 AM.
Anitarf is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 06-21-2009, 03:17 PM   #2
Toadcop
BuranX
 
Toadcop's Avatar
 
Join Date: Jul 2006
Posts: 1,887

Submissions (4)

Toadcop is just really nice (295)Toadcop is just really nice (295)

Approved Map: TcXSpell Making Session 10 Winner

Send a message via ICQ to Toadcop
Default

it allows to store only integers ? or what. i don't get this shit code...
__________________
Toadcop is offline   Reply With Quote
Old 06-21-2009, 04:01 PM   #3
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,085

Submissions (19)

Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

Quote:
Originally Posted by Toadcop
it allows to store only integers ?
Why would you need to store anything other than integers?
__________________
Anitarf is offline   Reply With Quote
Old 06-21-2009, 04:09 PM   #4
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

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...
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 06-21-2009, 09:28 PM   #5
Toadcop
BuranX
 
Toadcop's Avatar
 
Join Date: Jul 2006
Posts: 1,887

Submissions (4)

Toadcop is just really nice (295)Toadcop is just really nice (295)

Approved Map: TcXSpell Making Session 10 Winner

Send a message via ICQ to Toadcop
Default

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 ?
__________________
Toadcop is offline   Reply With Quote
Old 06-21-2009, 09:40 PM   #6
Rising_Dusk
Obscurity, the Art


Projects Director
Project Leader: OD
 
Join Date: Feb 2006
Posts: 9,727

Submissions (27)

Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)Rising_Dusk has a reputation beyond repute (1192)

Hero Contest #3 - 1st PlaceApproved Map: Desert of ExileApproved Map: Advent of the ZenithHero Contest #2 - 1st PlaceHero Contest - Third place>

Send a message via AIM to Rising_Dusk Send a message via MSN to Rising_Dusk
Default

Well, TimerUtils is widely used and it can only store integers as well. I don't see the problem with that.
__________________
Rising_Dusk is offline   Reply With Quote
Old 06-21-2009, 10:16 PM   #7
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,905

Submissions (37)

Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)Vexorian has a reputation beyond repute (1060)

Hero Contest #3 - 2nd Place

Default

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.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Old 06-22-2009, 04:05 PM   #8
akolyt0r
In Flames
 
akolyt0r's Avatar
 
Join Date: Jan 2006
Posts: 1,153

Submissions (3)

akolyt0r has a spectacular aura about (120)

Default

Table ? ...

Well integer really should be sufficient for this one... especially with the new hashtables...
__________________
akolyt0r is offline   Reply With Quote
Old 06-22-2009, 04:20 PM   #9
Here-b-Trollz
Corkscrew Chainsaw!!!
 
Join Date: Jun 2006
Posts: 711

Here-b-Trollz has a spectacular aura about (149)

Hero Contest #2 - 2nd Place

Default

Collapse 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.
Here-b-Trollz is offline   Reply With Quote
Old 06-22-2009, 05:01 PM   #10
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,085

Submissions (19)

Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

Quote:
Originally Posted by Here-b-Trollz
Collapse 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
Collapse Aah.:
        method operator size takes nothing returns integer
            return .data
        endmethod
__________________
Anitarf is offline   Reply With Quote
Old 06-23-2009, 02:57 AM   #11
Here-b-Trollz
Corkscrew Chainsaw!!!
 
Join Date: Jun 2006
Posts: 711

Here-b-Trollz has a spectacular aura about (149)

Hero Contest #2 - 2nd Place

Default

Quote:
Originally Posted by Anitarf
Collapse 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.
Here-b-Trollz is offline   Reply With Quote
Old 06-23-2009, 05:47 AM   #12
Anitarf
Procrastination Incarnate


Development Director
 
Join Date: Feb 2004
Posts: 8,085

Submissions (19)

Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)Anitarf has a brilliant future (888)

2008 Spell olympics - Fire - SilverApproved Map: Old School Alliance TacticsHero Contest #2 - 3rd PlaceSpell making session 2 winner

Default

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.
__________________
Anitarf is offline   Reply With Quote
Old 06-23-2009, 05:49 AM   #13
Here-b-Trollz
Corkscrew Chainsaw!!!
 
Join Date: Jun 2006
Posts: 711

Here-b-Trollz has a spectacular aura about (149)

Hero Contest #2 - 2nd Place

Default

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.
Here-b-Trollz is offline   Reply With Quote
Old 06-29-2009, 08:34 PM   #14
Blubb-Tec
Full Metal Mapping!
 
Blubb-Tec's Avatar
 
Join Date: Nov 2006
Posts: 270

Submissions (1)

Blubb-Tec will become famous soon enough (37)Blubb-Tec will become famous soon enough (37)

Default

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."
Blubb-Tec is offline   Reply With Quote
Old 07-02-2009, 10:26 PM   #15
0zyx0
Perfectionist noob
 
0zyx0's Avatar
 
Join Date: Mar 2009
Posts: 255

0zyx0 will become famous soon enough (38)0zyx0 will become famous soon enough (38)

Default

I would consider the lack of .size a feature.
__________________
My new signature - Now easier to understand than ever!
0zyx0 is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 03:23 AM.


Donate

Affiliates
The Hubb http://bylur.com - Warcraft, StarCraft, Diablo and DotA Blog & Forums The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2014, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services