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 12-05-2008, 03:07 AM   #1
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default LinkedList

LinkedList
by Ammorth
Collapse JASS:
//==============================================================================
//  LinkedList script by Ammorth - Version 1.2b - February 2, 2010
//==============================================================================
//
//  Purpose:
//      - Adds linked list functionality to vJass.
//
//  about:
//      - Stores data in a doubly-linked list, allowing one to add and remove 
//      data easily anywhere within the list.
//       
//  Usage:
//      - Create a new empty list with List.create()
//      - Add new data to the front of the list with Link.create(list, data)
//      - Add new data to the back of the list with Link.createLast(list, data)
//      - Insert new data before a link with link.insertBefore(data)
//      - Insert new data after a link with link.insert(data)
//      - Get the next and previous links with link.next and link.prev
//      - Get the list a link belongs to with link.parent
//      - Get the first or last link in a list with list.first or list.last
//      - Get the size of a list with list.size
//      - Get the link which contains data with list.Search(data)
//      - Remove a link with link.destroy()
//      - Destroy the entire list (including links) with list.destroy()      
//
//  Notes:
//      - If you find you are creating large lists, or that you are using them
//      to store long-term data, you can increase the number of links avaliable,
//      with a slight hit to performance (default is 8190).
//      - The number of lists avaliable is set at 8190.  If you need more, you
//      need a better approach at managing data.
//      - Except for the data, all variables are read-only (don't try and use 
//      the 'x' versions).
//
//  Requirements:
//      - JassHelper version 0.9.E.0 or newer (older versions may still work).
//
//  Installation:
//      - Create a new trigger called LinkedList.
//      - Convert it to custom text and replace all the code with this code.
//
//  Special Thanks:
//      - Rising_Dusk: helping me with the 1.1 code and idea
//      - Vexorian: giving me some hints about JassHelper
//      - Anitarf: convincing me that simpler is better
//
//==============================================================================
library LinkedList
globals
//==============================================================================
// Change this value here to increase the number of avaliable links (see notes).
    private constant integer LINK_SIZE = 8190 // defualt 8190
//==============================================================================
endglobals
private keyword xnext
private keyword xprev
private keyword xparent
private keyword xfirst
private keyword xlast

struct Link[LINK_SIZE]
    integer data
    Link xnext
    Link xprev
    List xparent
    
    method operator next takes nothing returns Link
        return this.xnext
    endmethod
    method operator prev takes nothing returns Link
        return this.xprev
    endmethod
    method operator parent takes nothing returns List
        return this.xparent
    endmethod
    
    private static method createEmpty takes List parent, integer data returns Link
        local Link new = Link.allocate()
        set new.data = data
        set new.xparent = parent
        return new
    endmethod
    
    method insert takes integer data returns Link
        local Link new = Link.createEmpty(this.xparent, data)
        set new.xprev = this
        set new.xnext = this.xnext
        if this.xnext == 0 then
            set this.xparent.xlast = new
        else
            set this.xnext.xprev = new
        endif
        set this.xnext = new
        return new
    endmethod

     method insertBefore takes integer data returns Link
        local Link new = Link.createEmpty(this.xparent, data)
        set new.xprev = this.xprev
        set new.xnext = this
        if this.xprev == 0 then
            set this.xparent.xfirst = new
        else
            set this.xprev.xnext = new
        endif
        set this.xprev = new
        return new
    endmethod
    
    static method create takes List l, integer data returns Link
        local Link new
        if l == 0 then
            debug call BJDebugMsg("Error: Cannot create Link for null List in Link.create()")
            return 0
        endif
        if l.xfirst == 0 then
            set new = Link.createEmpty(l, data)
            set l.xfirst = new
            set l.xlast = new
            set new.xnext = 0
            set new.xprev = 0
            return new
        else
            return l.xfirst.insertBefore(data)
        endif
    endmethod
    
    static method createLast takes List l, integer data returns Link
        if l == 0 then
            debug call BJDebugMsg("Error: Cannot create Link for null List in Link.createLast()")
            return 0
        endif
        if l.xlast == 0 then
            return Link.create(l, data)
        else
            return l.xlast.insert(data)
        endif
    endmethod
    
    method onDestroy takes nothing returns nothing
        if this.xparent == 0 then
            if this.xnext != 0 then
                set this.xnext.xparent = 0
                call this.xnext.destroy()
            endif
        else
            if this.xprev == 0 then
                set this.xparent.xfirst = this.xnext
            else
                set this.xprev.xnext = this.xnext
            endif
            if this.xnext == 0 then
                set this.xparent.xlast = this.xprev
            else
                set this.xnext.xprev = this.xprev
            endif
        endif
        set this.xnext = 0
        set this.xprev = 0
        set this.data = 0
    endmethod
endstruct

struct List
    Link xfirst
    Link xlast
    
    static method create takes nothing returns List
        local List new = List.allocate()
        set new.xfirst = 0
        set new.xlast = 0
        return new
    endmethod
    
    method operator first takes nothing returns Link
        return this.xfirst
    endmethod
    method operator last takes nothing returns Link
        return this.xlast
    endmethod
    method operator size takes nothing returns integer
        local Link n = this.xfirst
        local integer out = 0
        loop
            exitwhen n == 0
            set n = n.xnext
            set out = out + 1
        endloop
        return out
    endmethod
    
    method onDestroy takes nothing returns nothing
        if this.xfirst != 0 then
            set this.xfirst.xparent = 0
            call this.xfirst.destroy()
        endif
        set this.xfirst = 0
        set this.xlast = 0
    endmethod
    
    method search takes integer data returns Link
        local Link temp = this.xfirst
        loop
            exitwhen temp == 0
            if temp.data == data then
                return temp
            endif
            set temp = temp.xnext
        endloop
        return 0
    endmethod
endstruct

endlibrary
//==============================================================================
//  End of LinkedList script
//==============================================================================

Changelog

  • 1.2b
    Removed duplicate code found by Anitarf
  • 1.2a:
    Changed List.Search to List.search
    Changed Link.insertAfter to Link.insert
  • 1.2:
    Re-wrote from scratch, keeping simplicity in mind
  • 1.1:
    Never released publicly
  • 1.0:
    First public release



Wrote for my upcoming update to PAS, so I thought I may as well post it as it will be a requirement.

I am aware that a linked list library already exists in the database, but ever since the evolution of vJass, it has become out-dated. One of the ways to speed up PAS was to speed up and reduce the use of LinkedLists, hence why I wrote this.
Attached Images
File Type: jpg linkedlist.jpg (88.0 KB, 68 views)
__________________

Last edited by Ammorth : 02-03-2010 at 03:07 AM.
Ammorth is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 12-05-2008, 03:28 AM   #2
Pyrogasm
Lackadaisically Absent.
 
Pyrogasm's Avatar


Respected User
 
Join Date: Sep 2006
Posts: 4,520

Submissions (9)

Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)

Hero Contest - Fourth place

Send a message via ICQ to Pyrogasm Send a message via AIM to Pyrogasm Send a message via MSN to Pyrogasm Send a message via Yahoo to Pyrogasm
Default

Nice and useful!

However, you should mention that indexes start with 0 (or so I assume from your comments), and this line is incorrect:
Collapse JASS:
//      call list[3] // returns 5
Should be:
//      call list[2] // returns 5
Can you explain the SearchList function, please? If I use SEARCH_TYPE_GREATER, will it return the index of the first number than 5, which in this case would be 0?
__________________
Quote:
Originally posted by Rising_Dusk
Your spells are mostly ignored because they are not very cool so we aren't very excited to review/approve them, but you are incredibly persistent and won't give us an excuse to graveyard it. That is generally what results in a resource being ignored for a long time.

The Spell Request Thread Done for, unless someone else wants to revive it...
It lasted a damn long time.

Please; Ask for Help Appropriately














Quote:
Originally posted by Kyrbi0
Huh. Almost makes me wish I had a girlfriend, to take advantage of today (wait, no, that's not what I meant... I mean, take advantage of the fact that it is international women's day... gah, never mind).
Quote:
Originally posted by Pyrogasm
Rome may not have been built in a day, but the Romans sure as hell didn't say "look at this great city we built guys!" when they had nothing more than a bit of stone and some cottages.

Last edited by Pyrogasm : 12-05-2008 at 03:30 AM.
Pyrogasm is offline   Reply With Quote
Old 12-05-2008, 03:57 AM   #3
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by Pyrogasm
Nice and useful!

However, you should mention that indexes start with 0 (or so I assume from your comments), and this line is incorrect:
Collapse JASS:
//      call list[3] // returns 5
Should be:
//      call list[2] // returns 5

Thanks

Quote:
Originally Posted by Pyrogasm
Can you explain the SearchList function, please? If I use SEARCH_TYPE_GREATER, will it return the index of the first number than 5, which in this case would be 0?

Correct. It will return the index of the first element that meets the conditions. If nothing matches, it will return -1.
__________________
Ammorth is offline   Reply With Quote
Old 12-05-2008, 12:21 PM   #4
Anitarf
Procrastination Incarnate


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

Submissions (19)

Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)

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

Default

I was going to write something just like this so excuse me if I nitpick at your implementation a bit:

...ok, I really don't have that much to say, it's pretty neat. There's just a bit many methods, I don't particularly like all those that treat the list as an array by either taking or returning indexes, if you think they're justified that raises the question why doesn't your stack resource submission have them as well. Also, I think you should ditch the getElement method, users shouldn't be able to get a random element from the list like that because all they can do with it is break stuff, since all methods are pretty much meant to be called only on first elements, so getting another list element isn't only dangerous but pretty useless.

call list.AddToListBackOf(9, 2) // List contains: 8, 2, 5, 9, -3 Wouldn't 9 be added two spots after the end of the list, not one?

You could add the less-or-equal and greater-or-equal search types. Also, that stuff should have a public keyword; either that, or make it a static integer in the struct.

There's too much duplication of code in the search function, you could have just a single loop and then an if/elseif statement inside it.

A sort method would be nice to have.
__________________
Anitarf is offline   Reply With Quote
Old 12-05-2008, 03:26 PM   #5
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by Anitarf
...ok, I really don't have that much to say, it's pretty neat. There's just a bit many methods, I don't particularly like all those that treat the list as an array by either taking or returning indexes, if you think they're justified that raises the question why doesn't your stack resource submission have them as well. Also, I think you should ditch the getElement method, users shouldn't be able to get a random element from the list like that because all they can do with it is break stuff, since all methods are pretty much meant to be called only on first elements, so getting another list element isn't only dangerous but pretty useless.

Originally, everything was private and the user was only able to access information from the header node. Although this is great for keeping everything from being tampered with, when it came time to use it, I found I was wanting to loop through the list on my own and do some comparisons and such. The problem with that is doing:

Collapse JASS:
local integer i = 0
loop
    exitwhen i >= list.size
    doSomethingWith( list[i] )
    ...
    set i = i + 1
endloop

would have huge performance issues (due to starting at the front for each access), vs:

Collapse JASS:
local integer i = 0
local LinkedList temp = list.next // first slot
loop
    exitwhen i >= list.size
    doSomethingWith( temp )
    ...
    set temp = temp.next
    set i = i + 1
endloop

here, one can traverse the list with O(n) time vs O(n*n!). Maybe ill make it readonly... I'll take a look at it when I get a chance (currently running).

I'll also address the rest of your comments later (I don't mind being nit-picked, anything to make it better).
__________________

Last edited by Ammorth : 12-05-2008 at 03:26 PM.
Ammorth is offline   Reply With Quote
Old 12-05-2008, 03:57 PM   #6
Anitarf
Procrastination Incarnate


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

Submissions (19)

Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)Anitarf has a brilliant future (903)

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

Default

If that's the issue, then you should have simply added a loopThroughList method that calls a user function (via a function interface or something) for each item on the list. Users shouldn't have to code their own low-level loops.
__________________
Anitarf is offline   Reply With Quote
Old 12-05-2008, 04:06 PM   #7
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by Anitarf
If that's the issue, then you should have simply added a loopThroughList method that calls a user function (via a function interface or something) for each item on the list. Users shouldn't have to code their own low-level loops.

I never thought of that before. I'll go and add it then.

Quote:
Originally Posted by Anitarf
call list.AddToListBackOf(9, 2) // List contains: 8, 2, 5, 9, -3 Wouldn't 9 be added two spots after the end of the list, not one?
No, it adds the value after the 3rd element (index = 2). Since 5 is the 3rd element, it is added after 5.

Quote:
Originally Posted by Anitarf
You could add the less-or-equal and greater-or-equal search types. Also, that stuff should have a public keyword; either that, or make it a static integer in the struct.

There's too much duplication of code in the search function, you could have just a single loop and then an if/elseif statement inside it.

I'll revise it before the next update

Quote:
Originally Posted by Anitarf
A sort method would be nice to have.

Alright, will do. I'll hopefully implement merge-sort.

edit: at school so when I get home tonight, ill update.

edit2: alright, I have most of the code written, but its going to take awhile to write the handbook that goes with it. Expect an update sometime tomorrow (today, but after I get some sleep).
__________________

Last edited by Ammorth : 12-06-2008 at 09:36 AM.
Ammorth is offline   Reply With Quote
Old 12-06-2008, 12:26 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

Is there a maximum of elements per LinkedList ?
akolyt0r is offline   Reply With Quote
Old 12-06-2008, 10:47 PM   #9
Pyrogasm
Lackadaisically Absent.
 
Pyrogasm's Avatar


Respected User
 
Join Date: Sep 2006
Posts: 4,520

Submissions (9)

Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)Pyrogasm is a splendid one to behold (638)

Hero Contest - Fourth place

Send a message via ICQ to Pyrogasm Send a message via AIM to Pyrogasm Send a message via MSN to Pyrogasm Send a message via Yahoo to Pyrogasm
Default

8191, unless I'm mistaken.
__________________
Quote:
Originally posted by Rising_Dusk
Your spells are mostly ignored because they are not very cool so we aren't very excited to review/approve them, but you are incredibly persistent and won't give us an excuse to graveyard it. That is generally what results in a resource being ignored for a long time.

The Spell Request Thread Done for, unless someone else wants to revive it...
It lasted a damn long time.

Please; Ask for Help Appropriately














Quote:
Originally posted by Kyrbi0
Huh. Almost makes me wish I had a girlfriend, to take advantage of today (wait, no, that's not what I meant... I mean, take advantage of the fact that it is international women's day... gah, never mind).
Quote:
Originally posted by Pyrogasm
Rome may not have been built in a day, but the Romans sure as hell didn't say "look at this great city we built guys!" when they had nothing more than a bit of stone and some cottages.
Pyrogasm is offline   Reply With Quote
Old 12-07-2008, 03:25 PM   #10
Kwah
Christmassy.
 
Kwah's Avatar
 
Join Date: Jun 2008
Posts: 644

Submissions (4)

Kwah will become famous soon enough (43)Kwah will become famous soon enough (43)

Default

Quote:
Collapse JASS:
private constant integer LINKEDLIST_SIZE = 8191 //default 8191

I would say so.
Kwah is offline   Reply With Quote
Old 12-07-2008, 04:31 PM   #11
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

This is getting a face-lift once I finish coding. I had a long talk with Anitarf and we came to a bunch of conclusions about Linked-Lists and how they should operate.
__________________
Ammorth is offline   Reply With Quote
Old 12-07-2008, 04:37 PM   #12
Kwah
Christmassy.
 
Kwah's Avatar
 
Join Date: Jun 2008
Posts: 644

Submissions (4)

Kwah will become famous soon enough (43)Kwah will become famous soon enough (43)

Default

This is actually very convenient. I was looking for tuples the other day.
Kwah is offline   Reply With Quote
Old 12-08-2008, 02:57 AM   #13
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Updated. Lots has changed so backwards compatibility is lost.
__________________
Ammorth is offline   Reply With Quote
Old 12-08-2008, 07:36 PM   #14
C2H3NaO2
User
 
Join Date: May 2008
Posts: 80

C2H3NaO2 is on a distinguished road (17)

Default

I like that thing! Is looks pretty clean and easy.
But there are a few things, that I would implement different.

I would put it all into a textmacro. This would give you (and other users you don't know) the ability to create different Lists with different types.
In most cases only having integer lists is enough, but sometimes you have to create a own structs only for storing a string or something like that.

In my opinion there also belongs pushfront, pushback, popfront and popback (yeah i like the c++ names) methods in the main list struct that ALWAYS works.

btw: In my opinion you should save the size in a integer in the struct List. It would be much faster.

P.s. Excuse my English; if I did some really BIG mistakes, please tell me. I try to correct my English skills.
C2H3NaO2 is offline   Reply With Quote
Old 12-08-2008, 11:55 PM   #15
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by C2H3NaO2
I would put it all into a textmacro. This would give you (and other users you don't know) the ability to create different Lists with different types.
In most cases only having integer lists is enough, but sometimes you have to create a own structs only for storing a string or something like that.

I would have to argue against you here, and say that the majority (if not all) of the time, structs will be stored in the lists. Even if someone wants to store arbitrary values in a list, it makes no sense to duplicate this system for every new type when one can just create a struct which requires less lines and when it is in-lined (vex's map optimizer), provides the same efficiency.

Quote:
Originally Posted by C2H3NaO2
In my opinion there also belongs pushfront, pushback, popfront and popback (yeah i like the c++ names) methods in the main list struct that ALWAYS works.
pushFront == Link.create()
pushBack == Link.createLast()
popFront == set data = list.front.data ; call list.front.destroy()
popBack == set data = list.last.data ; call list.last.destroy()

Quote:
Originally Posted by C2H3NaO2
btw: In my opinion you should save the size in a integer in the struct List. It would be much faster.
This was probably one of the ideas I was contemplating the most. I thought about it but decided to scrap it. My reasons are:
  1. Then I need to add 1 and subtract 1 every time the list is changed (over-time, becomes slow especially if you want to sort the list)
  2. How many times do you really need list.size? It makes no sense to do so, other than for personal enjoyment. If you need to loop through the list, it's much easier and efficient to do.
    Collapse JASS:
    set tempLink = list.first
    loop
        exitwhen tempLink == 0
        call DoStuffWithLink(tempLink)
        set tempLink = tempLink.next
    endloop
Same principle to check if the list is empty: if list.first == 0 then //empty It was just a feature that I felt would not be used enough to compensate for the slow-downs caused by adding and removing links.

I do thank you for your criticism though; and your english was fine.

edit: Another update. Changed names of methods; that is all.
__________________

Last edited by Ammorth : 12-09-2008 at 03:14 AM.
Ammorth 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 01:31 PM.


Affiliates
The Hubb The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

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