1. Updated Resource Submission Rules: All model & skin resource submissions must now include an in-game screenshot. This is to help speed up the moderation process and to show how the model and/or texture looks like from the in-game camera.
    Dismiss Notice
  2. DID YOU KNOW - That you can unlock new rank icons by posting on the forums or winning contests? Click here to customize your rank or read our User Rank Policy to see a list of ranks that you can unlock. Have you won a contest and still havn't received your rank award? Then please contact the administration.
    Dismiss Notice
  3. Don’t forget to sign up for the Hive Cup. There’s a 555 EUR prize pool. Sign up now!
    Dismiss Notice
  4. The Hive Workshop Cup contest results have been announced! See the maps that'll be featured in the Hive Workshop Cup tournament!
    Dismiss Notice
  5. The results are out! Check them out.
    Dismiss Notice
  6. The poll for Hive's 12th Concept Art Contest is up! Go cast your vote for your favourite genie!
    Dismiss Notice
  7. The raddest synthwave tracks were chosen - Check out our Music Contest #12 - Results and congratulate the winners!
    Dismiss Notice
  8. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

[Containers] List<T>

Discussion in 'JASS Resources' started by Bannar, Mar 4, 2014.

  1. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    Updated. Update tries to achieve most of the goals listed in posts above.
    Code has been greatly reduced, contains only neccessary features. Most of the functions are inline friendly - especially the child item structs which are basically structs with just one method.
    Added few debug messages, improved API and documentation. Fixed demo to reflect the changes. AllocT in the end wasn't even required.

    Edit: Fixed issue with delegates inside <NAME>Item structs (DEFINE_STRUCT_LIST macro). These are now solely based on Table instances.

    Edit2: Fixed debug calls. Removed create() and destroy() methods from <NAME>Item structs and moved them directly into list struct effectively disallowing user to perform silly actions with these.
    Added ownership safety to list to prevent unintentional behaviour when dealing with foreign nodes.
     
    Last edited: Sep 20, 2015
  2. edo494

    edo494

    Joined:
    Apr 16, 2012
    Messages:
    3,855
    Resources:
    5
    Spells:
    1
    JASS:
    4
    Resources:
    5
    hmm...I think this looks good enough, yes it still has the problem of running out of instances, but that is inherit to any non Hashtable based struct, even tho when you are using each node as list itself, it gets a bit costy.

    On the API front, there is nothing "lacking" from my point, it supports the most obvious push/pop and it also has neat shift/unshift as well as find.

    I think this is good to go for approval, and since Bribe agreed back in 2015, I think I will go ahead and do it right now.

    It would be good however, if you linked to Table in the documentation, so that people dont have to go around looking for it, but have the link served to them(Alloc cant since it can use whatever, even tho recommendation for Sevions[since it is approved] could be made too)
     
  3. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    You can only run out of instances for list-class instances itself, for nodes (and those are usually the problem) the limit is raised to the limit hashtable storage.
    It's highly unlikely you will ever create more than 8191 (in the past), and now you can create four times as many before hitting array-index limit. If this would be the real issue, 100% of current lists would be bound to failure and none other but Table-based implementations needed to be used.
    My implementation is a mix: nodes are Table-based yet lists remain array-based. With VectorT, ListT and Table it's basically done deal when speaking about Containers for War3 vJass. You need nothing else, maybe apart from LinkedListModule. Those are as close to Wurst data packages are one can get in vJass :)

    Updated to 2.1.2.0.

    Added removeElem method for ListT due to frequrency of remove and find method invocations.
    Added erase method, which deprecates remove method.
    Improved documentation and readability.
    Reduced size of push and unshift methods slightly.
    Validated to be Wurst friendly.

    Introduction of removeElem and erase starts 3-6 months period of depreciation. Plan is to have 'remove ' renamed to 'erase' (which is iterator based in c++) and have 'removeElem' renamed to 'remove' (which is value based in c++).
     
    Last edited: May 7, 2018
  4. Spellbound

    Spellbound

    Joined:
    Jan 9, 2005
    Messages:
    1,953
    Resources:
    15
    Skins:
    5
    Spells:
    9
    JASS:
    1
    Resources:
    15
    Hmm, would it be possible to have something like myList.getRandom() which returns a random node from a list? And if so, how hard would it be to pass it through a boolexpr filter?
     
  5. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    ListT core should be left as simple as possible. If jasshelper properly eliminated constants and unused methods then it would have been an entirely different case. And btw, I don't care about optimizer, this job should be done on compiler level.

    Back to the topic. getRandom implementation for jass is rather straightforward:
    Code (vJASS):
    function GetRandomListItem takes IntegerList list returns integer
        local integer rand = GetRandomInt(0, list.size())
        local IntegerListItem iter = list.first

        loop
            exitwhen rand == 0
            set rand = rand - 1
            set iter = iter.next
        endloop
        return iter.data
    endfunction

    Elaborate on the boolexpr filter case.
     
  6. Spellbound

    Spellbound

    Joined:
    Jan 9, 2005
    Messages:
    1,953
    Resources:
    15
    Skins:
    5
    Spells:
    9
    JASS:
    1
    Resources:
    15
    Hmm, I see. Sounds good.

    For the boolexpr filter, similar to how you can use one with
    native GroupEnumUnitsInRange takes group whichGroup, real x, real y, real radius, boolexpr filter returns nothing
    , I was wondering how hard/feasible/useful it would be to have the ability to pick a random unit in a list depending on a filter. Like, let's say you have 3 footmen, 2 knights and 4 sorceresses in a list and you want to pick one of the 4 sorceresses.
     
  7. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    Why doesn't the pop() method return the element just popped. It doesn't make sense to me that a struct method returns the struct that just executed the method. But perhaps I'm missing something?

    Code (vJASS):

                loop
                    exitwhen i == max
                    set unitType = .unitTypes.back()
                    call .unitTypes.pop()
                    call BJDebugMsg("id: " + I2S(unitType))
                    set i = i + 1
                endloop


    The back() method here shouldn't be needed.

    Perhaps separate pop() from say removeBack() being two different things (or not). But i really think pop should return the value. :)

    Rather than being able to chain pop.
    list.pop().pop().pop()
    I see no point with this functionality.

    You should add examples of how to iterate through the list and how to iterate through the list and remove an element. Useful if you want to remove a struct based on one of it's data members.
     
    Last edited: Jul 30, 2018
  8. IcemanBo

    IcemanBo

    Joined:
    Sep 6, 2013
    Messages:
    6,181
    Resources:
    22
    Maps:
    3
    Spells:
    11
    Template:
    1
    Tutorials:
    4
    JASS:
    3
    Resources:
    22
    Could:
    Code (vJASS):

    call BJDebugMsg("id: " + I2S(.unitTypes.back()))
    call .unitTypes.pop()


    In his example is a loop:
    Code (vJASS):

        local IntegerListItem node = list.first
        local string s = ""
        loop
            exitwhen node == 0
            set s = s + " " + I2S(node.data)
            set node = node.next
        endloop

    but if an element should be removed I would go something like:
    Code (vJASS):

        local IntegerListItem node = list.first
        local IntegerListItem temp
        local string s = ""
        loop
            exitwhen node == 0
            set temp = node.next
            set s = s + " " + I2S(node.data)
            if node.data == 12345 then
                call list.erase(node)
            endif
            set node = temp
        endloop


    .. about return value instead of object, maybe it's preference. I somehow find it neat to make multiple operations in a row.
     
  9. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    Thanks @IcemanBo for providing the examples!

    I made that mistake in the past, should have added different method for pop/pop-cascade. Didn't remove it for compatibility reasons.

    I could start deprecation process now, like I did for several methods in multiple libs, although..
    ..in JASS world, it turned out that in most cases I did not need the ret of pop and [this] came in handy.
     
  10. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    What about these methods:
    list.exists(Value), list.indexOf(Value) and list.get(Value). Iceman your motivations be damned! D:
     
  11. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    exists: find(...) != 0
    get: find(...)
    no indexOf per se.

    You see, the initial version had dozens of methods much like its c++ inspiration. However, after brainstorming for a bit and reading some feedback from my jass bros, I've decided to strip container libs (both, vec and list) from most of their initial functionality and include only the core, elementary methods.
    If you need indexOf, just create simple extension method within your map's code. Again, this is just jass. In 99% cases you don't need a cherry on top, the cake alone will do just fine. I think I've struck the right balance.
    What's more, quite often, most experienced mappers modify certain elements of imported sources to suit their needs. It's not possible to satisfy everyone. Diplomacy comes in handy here.

    ```
    If you want the cherry, magic, hokus pokus, meet me on the linux kernel battlefields.
     
  12. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    Fine, you win this time... :) But could you help explain to me why setNamesAsUsed doesn't work whilst getRandomName does? It doesn't seem to be able to find FullName for some reason.

    problematic
    Code (vJASS):

    method setNameAsUsed takes FullName name, boolean used returns nothing
                call BJDebugMsg("This is called...")
                if (used) then
                    if (.unusedNames.erase(name)) then
                        call .usedNames.push(name)
                        call BJDebugMsg("added to uused names list")
                    endif
                else
                    if (.usedNames.erase(name)) then
                        call .unusedNames.push(name)
                        call BJDebugMsg("Added to unused names list")
                    endif
                endif
            endmethod
       
            method getRandomName takes nothing returns FullName
                local integer unusedSize = .unusedNames.size()
                local integer random
                local IntegerListItem node
                local FullName name = 0
                if (unusedSize > 0) then
                    set node = .unusedNames.first
                    set random = GetRandomInt(0, unusedSize)
                    loop
                        exitwhen random == 0
                        set random = random - 1
                        set node = node.next
                    endloop
                    call BJDebugMsg("A")
                    return node.data
                endif
                set node = .usedNames.first
                set random = GetRandomInt(0, usedNames.size())
                loop
                    exitwhen random == 0
                    set random = random - 1
                    set node = node.next
                endloop
                call BJDebugMsg("B")
                return node.data
            endmethod
    They are used like this:
    Code (vJASS):

            set name = pool.getRandomName()
            call pool.setNameAsUsed(name, true)

     
    Last edited: Aug 5, 2018
  13. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    .erase expects argument of $TYPE$Item type. Your example compiles only because vJass is not type safe.
    I've added .removeElem method for conveniency some time ago. It will be renamed to .remove in nearest future - deprecation period slowly comes to an end.
     
  14. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    Ah I see thanks. A problem that arises with that though is that removeElem returns thistype and not true or false? This List is like a magic box when it comes to how some API functions work some times. The convenience of cascade methods again haunt me sir. I suggest you change it to return boolean.
     
    Last edited: Aug 5, 2018
  15. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    You better get used to it or switch to wurst where 'both returns' are available due to cascade operator.
     
  16. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    My listed suggestions:


    method getNode takes integer index returns Node

    method findNode takes $TYPE$ value returns Node 

    method removeNode takes Node nodeToRemove returns nothing
    (All delete logic here)
    method addNode takes integer index, Node nodeToAdd, $TYPE$ value returns boolean
    (All add logic here)
    method add takes integer index, $TYPE$ value returns boolean
    (must have)
    method addFirst takes $TYPE$ value returns nothing 
    (useful wrapper)
    method addLast takes $TYPE$ value returns nothing
    (useful wrapper)
    method contains takes $TYPE$ value returns boolean
    (very useful wrapper)
    method copyRange takes integer start, integer end returns thistype

    method define takes integer index, $TYPE$ value returns boolean
    (must have)
    method defineFirst takes $TYPE$ value returns boolean
    (useful wrapper)
    method defineLast takes $TYPE$ value returns boolean
    (useful wrapper
    method get takes integer index returns $TYPE$
    (must have)
    method getFirst takes nothing returns $TYPE$
    (useful wrapper)
    method getLast takes nothing returns $TYPE$
    (useful wrapper)
    method indexOf takes $TYPE$ value returns integer 
    (very useful wrapper)
    method iterator takes nothing returns Iterator 
    (useful wrapper, special mention)
    method remove takes integer index returns $TYPE$
    (must have)
    method removeFirst takes nothing returns $TYPE$
    (replaces pop)
    method removeLast takes nothing returns $TYPE$

    method removeElement takes $TYPE$ value returns boolean

    method sort takes nothing returns nothing
    (optional, but dont see why not)

    replace every if-statement that has empty() in it with count == 0

    example of iterator improves code readability and usage (maybe) D:
    Code (vJASS):

    struct Iterator extends array
            private Node curNode
            private Node nextNode
            private Node prevNode
            private LinkedList list
     
            implement Alloc
     
            static method create takes LinkedList list, Node head returns thistype
                local thistype this = .allocate()
                set .nextNode = head
                set .curNode = 0
                set .prevNode = 0
                set .list = list
                return this
            endmethod
     
            method hasNext takes nothing returns boolean
                return nextNode != 0
            endmethod
     
            method next takes nothing returns integer
                set .prevNode = .curNode
                set .curNode = .nextNode
                set .nextNode = .nextNode.next
                return .curNode.value
            endmethod
     
             method remove takes nothing returns boolean
                if (.curNode == 0) then
                    call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, ITR + ".remove:" + NULL_PTR)
                    return false
                endif
                call .list.removeNode(.curNode)
                set .curNode = 0
                return true
            endmethod
        endstruct
    Usage
    Code (vJASS):

    call list.add(0, 3)
            call list.add(0, 4)
            call list.add(0, 5)
            call list.add(1, 7)
            set list2 = list.copyRange(0, 1)
            call list.remove(0)
            set itr = list.iterator()
            loop
                exitwhen not itr.hasNext()
                set value = itr.next()
                call BJDebugMsg("Value: " + I2S(value))
                call itr.remove()
                // call itr.remove() <-- Illegal action double remove without next!
            endloop



    AddFirst and addLast can implement cascade logic (it makes the most sense to have it in setup)
     
    Last edited: Aug 6, 2018
  17. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    I'd suggest these being implemented in some kind of extension/ plugin lib. Afterwards, static-if could be added for List<T> that would implement code of such plugin lib.
     
  18. Pinzu

    Pinzu

    Joined:
    Nov 30, 2007
    Messages:
    1,177
    Resources:
    3
    Spells:
    2
    Tutorials:
    1
    Resources:
    3
    why though? If you change your configuration addNode, removeNode and findNode most of these methods become wrappers. Maybe your current configuration can do it already though, don't know. Perhaps getNode(index) is the one that most of them build upon. So if you only want node manipulation you should change for example:

    Code (vJASS):

        method push takes $TYPE$ value returns thistype
            local $NAME$Item node = createNode(value)
            if not empty() then
                set last.next = node
                set node.prev = last
            else
                set first = node
                set node.prev = 0
            endif
            set last = node
            set node.next = 0
            set count = count + 1
            return this
        endmethod
     


    Into something that can do more things, example:
    Code (vJASS):

     method addNode takes integer index, $NAME$ nodeToAdd, $TYPE$ value returns boolean
            if (index > .count or index < 0) then
                call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60, LIST + ".add:" + OUT_BOUNDS)
                return false
            endif
            if (nodeToAdd == 0) then
                set nodeToAdd = createNode(value) // if nodeToAdd is 0 we create a new one with the value
            endif
            if (index == 0) then
                call .addFirst(value)
            elseif (index == .count) then
                call .addLast(value)
            else // insertion
                set oldNode = getNode(index) // <---- needed for extended features
                set oldNode.prev.next = nodeToAdd
                set nodeToAdd.prev = oldNode.prev
                set nodeToAdd.next = oldNode
                set oldNode.prev = nodeToAdd
                set .count = .count + 1
            endif
            return true
        endmethod

            method addFirst takes integer value returns nothing
                local Node nodeToAdd = Node.create(value)
                if (.head == 0) then
                    set .head = nodeToAdd
                    set .tail = .head
                else
                   set .head.prev = nodeToAdd
                   set nodeToAdd.next = .head
                   set .head = nodeToAdd
                endif
                set .length = .length + 1
            endmethod
           
            method addLast takes integer value returns nothing
                local Node nodeToAdd = Node.create(value)
                set nodeToAdd.prev = tail
                set .tail.next = nodeToAdd
                set .tail = nodeToAdd
                set .length = .length + 1
            endmethod
     
    See my lab post for more examples.
     
    Last edited: Aug 6, 2018
  19. Bannar

    Bannar

    Joined:
    Mar 19, 2008
    Messages:
    3,087
    Resources:
    20
    Spells:
    5
    Tutorials:
    1
    JASS:
    14
    Resources:
    20
    List<T> already defines front/ back and first/ last.

    "Mandatory" is a very subjective term. History shows that successful jass collection snippets were small. Range of utility functions you've posted out there won't be used by 98% users.
    Professional approach is to wrap such utilities within plugin library and add adequate static-if construct into parent lib.

    There is an another option - fix jass compiler so unused methods are not generated at all, much like wurst one. And yes, I know about optimizer tool, and yes, I do not care. Such "optimization" should be done on compiler level.