Tutorial Programming with the Collections Framework

[Nestharus]

http://www.thehelper.net/forums/showthread.php?t=137848

The collections framework deals with common collections and ways of allocating memory.

As of 8.0-
Malloc
Stacks
Dequeues

9.0 Will introduce a variety of trees and the queue data structure

It will also introduce some circular data structures.

The purpose of this guide is to give an understanding of how the collections framework can be used rather than packaged systems. For a deeper understanding of the API in the collections framework, please look into the collections framework header.


Malloc
------------------------------------------------------------
Malloc is the primary means of data allocation. This retrieves an instance for you to attach data to, like an index for an array. This method is used by structs.

Malloc uses an integer array and 2 integers for its allocation-

integer array freed
integer free = 0
integer memory = 1

memory refers to memory's current index, free refers to how much free memory there is, and freed stores the memory. Memory typically starts at 1 as 0 is used for null or default values.

Allocation

local thistype this
if free > 0 then
    set free = free - 1
    set this = freed[free]
    //do get freed code
else
    set this = memory
    set memory = memory + 1
    //do get new code
endif
//do always code

Deallocation

set freed[free] = this
set free = free + 1

Rather than writing this out constantly, structs are typically used (allocate and deallocated).

The collections framework uses macros to set up memory spaces, allocate, and free memory.

//! textmacro DYNAMIC_MEMORY takes NAMESPACE
//! textmacro DYNAMIC_MEMORY_GET_FREED takes NAMESPACE, TO_MEMORY
//! textmacro DYNAMIC_MEMORY_GET_NEW takes NAMESPACE, TO_MEMORY
//! textmacro DYNAMIC_MEMORY_FREE takes NAMESPACE, FROM_MEMORY

The namespace is similar to the concept of a vjass scope-

scope Hi
endscope

It allows multiple memory spaces within a given struct. The default memory spaces used by the framework's modules is "", so don't use that.

//! textmacro DYNAMIC_MEMORY takes NAMESPACE

sets up the variables

//! textmacro DYNAMIC_MEMORY_GET_FREED takes NAMESPACE, TO_MEMORY

Attempts to get freed memory

//! textmacro DYNAMIC_MEMORY_GET_NEW takes NAMESPACE, TO_MEMORY

Otherwise gets new

Remember the if statement in the allocation? The if statement still exists and is automatically started with GET_FREED. It is not continued at all with GET_NEW, so our usage looks like this-

struct MyStruct extends array
//! runtextmacro DYNAMIC_MEMORY("test") //test is the namespace

public static method allocate takes nothing returns thistype
    local thistype this
    //! runtextmacro DYNAMIC_MEMORY_GET_FREED("test", "this")
        //do get freed code
    else
        //! runtextmacro DYNAMIC_MEMORY_GET_NEW("test", "this")
        //do get new code
    endif
    //do always code
endmethod

/*
//! textmacro DYNAMIC_MEMORY_FREE takes NAMESPACE, FROM_MEMORY
will pass var value into freed space
*/

public method deallocate takes nothing returns nothing
    //! runtextmacro DYNAMIC_MEMORY_FREE("test", "this")
    //do freed code
endmethod

endstruct

So these macros do the exact same thing as an efficient allocation method, but they save you code. The macro names are DYNAMIC_MEMORY as of 8.0, but they will change to MALLOC to be more standardized.


If you don't need the crazy power of these macros, there are also 2 different implementations of modules-

module DynamicMemoryStruct //first implementation, all in one

    //second, like macros but thistype this is auto defined and namespace is ""
    module DynamicMemory
    module DynamicMemoryGet
    module DynamicMemoryGetFreed
    module DynamicMemoryGetNew

Stack
------------------------------------------------------------
Stacks are normally written as so-

struct Stack extends array
    public thistype head //multi instanced
    public thistype next

    implement DynamicMemoryStruct
endstruct

And node operations are generally singular

The stacks in collections work differently and only have range operations as range and singular in it have exact same overhead.

//! textmacro STACK takes NAMESPACE

variables

//! textmacro STACK_TEMP takes NAMESPACE, NODE_FIRST, NODE_LAST

temporary copy to global range vars

//! textmacro STACK_MOVE takes NAMESPACE, NODE_FIRST, NODE_LAST, TO_NODE_FIRST, TO_NODE_LAST

move range

//! textmacro STACK_REMOVE takes NAMESPACE, NODE_FIRST, NODE_LAST

remove range

As you can see, memory allocation is not actually defined as that is completely up to you. Normally, malloc style is used, but sometimes a queue style memory allocation (like a buffer), list style (sub memory pools), or indexed style (unordered memory where only iteration through all elements matters).

What this means is that the stack only defines the stack and nothing else. Many collections come package with memory allocation, typically malloc as that can apply to anything.

When dealing with a stack, you are only ever supposed to be manipulating the first element, but with this implementation, it allows you to manipulate a range of elements if you really want to. Because a stack only points to the next element, you can only ever manipulate the element in front of the current element, so for example, move will move curNode.next through lastNode to in between targetNode and targetLastNode or


head->1->2->3->4->5

head->6->7->8->9->10

So, you are current on the first stack at 2. You want to move 2, but you can't. Why? You can't change where 1 points to.

To remove 2, you'd have to do this-

1 -> 3

And since you aren't currently pointing to 1, you can't. You can only move 3 through 5. You decide to move 3 and 4 to in between 6 and 7 on next list.

head->1->2->3->4->5
head->6->3->4->7->8->9

Uh oh, 3 and 4 are still in the first stack!! So how do you get them out of there so they aren't in two spots at once? With Remove. Each operation only does what it says it does, move only moves (like a copy) and remove only removes. They don't allocate, deallocate, or do anything extra.

So removing 3 and 4 from first stack results in this
head->1->2->5
head->6->3->4->7->8->9

Operation complete.

While this may seem harder than a typical move method in a packaged collection, it actually gives you more flexibility. Another operation would be swap, which is where you want move to act like it does. In fact, with swap, you never even have to remove values as the move operation replaces the pointers of where it goes in between.

Example-
4, 5, 6
7, 8, 9, 10, 11, 12

If you wanted to move 5 to in between 9 and 12, you'd get this

4, 5, 6
7, 8, 9, 5, 12

9 now points to 5 and 5 points to 12

Now what do you do with 10 and 11? You could either deallocate them and remove 5 from first stack or move them in between 4 and 6 (5's old position)

4, 10, 11, 6
7, 8, 9, 5, 12

Successful swap! : D

To keep the positions of the first swap intact, temporary variables have to be set. The actual operation (direct code from StackSwap module) looks like this:

module StackSwap
    //! runtextmacro STACK_TEMP("", "nodeFirst1", "nodeLast2")
    //! runtextmacro STACK_MOVE("", "nodeFirst2.Next", "nodeLast2", "nodeFirst1", "nodeLast1.Next")
    //! runtextmacro STACK_MOVE("", "thistype.tempPrevious", "nodeLast1", "nodeFirst2", "thistype.tempNext")
endmodule

And that is all there really is to a stack.


Dequeue
------------------------------------------------------------
A dequeue is much easier to work with than a stack, but it uses double pointers, previous and next. It also has a head and tail rather than just a head. This means that it is quite literally double the memory for initial creation and double the operations. While it may be double, the operations are still very low, especially compared to standard dequeue modules that you may find in other collection implementations in the wc3 community. A movement of 100 nodes is 306 operations in standard implementation whereas collections framework is only 4.

So really, you should be getting the macro patterns at this point

//! textmacro DEQUEUE takes NAMESPACE
//! textmacro DEQUEUE_TEMP takes NAMESPACE, NODE_FIRST, NODE_LAST
//! textmacro DEQUEUE_MOVE takes NAMESPACE, NODE_FIRST, NODE_LAST, TO_NODE_FIRST, TO_NODE_LAST
//! textmacro DEQUEUE_REMOVE takes NAMESPACE, NODE_FIRST, NODE_LAST

The move and remove apply to current node through last node rather than the current node's next because a dequeue has access to it's current's previous node.

0<-head<->1<->2<->3<->tail->0

However, because there is a head and a tail, it requires two nodes to form it up. Stack only needed one node, so no special operation was needed, you could really do w/e you wanted. With this, head and tail have their own operation.

//! textmacro DEQUEUE_FORM takes NAMESPACE, HEAD, TAIL

Which just does this-

0<-head<->tail->0
--------------------------------------------------------------------


So, where can you use MALLOC, STACK, and DEQUEUE?
Virtually anywhere! Dequeues for projectile systems with Malloc for memory allocation, stacks for things like simplistic spawns or targets for a spell.

How do operations compare with stacks, dequeues, and queues?
stack- 2
queue- 3
dequeue- 4

extra memory?
stack- 1
queue- 2
dequeue- 2

So hopefully by this point, you can see that operation wise, this saves a massive amount on ranges and saves some extra operations on singles. Also, it has much more flexibility, and based on what you need you can go for a super simple API (all in one module), default API (one namespace/implementation), or macro API (w/e you want). I hope you can also see that writing this all out from scratch isn't fun and that the macros/modules are huge time saves. Yes, a struct may be a time saver on malloc memory allocation (given you don't want to be able to inject into on freed/on new and you want extra stuff, which is why you should at least use the malloc all in one module), and an all in one standard package in wc3 community might be super simple (but look at operations and look at how simple this is... this is actually simpler or as simple as all of them... it only has 2 operations!!), but I believe that this framework is the way to go in all scenarios no matter what your needs are. It beats out the competition hands down.


If there is anything else you think should be added to this guide on covering the current Collections Framework, let me know.

9.0 plans (this guide will be updated)-
queue
a billion trees (a billion)
circular stacks, queues, and dequeues

Why not indexed memory? Indexed memory is so simple that'd it'd actually be harder using macros than writing it from scratch ><.

 

[kingkingyyk3]

This is more likely a linked list tutorial and no practical usage for it.
You can post some usage of it like creating KT2, T32...

 

[Romek]

I'd rather detailed instructions on how to use systems and the sort were included in the actual thread of the system.

> You can post some usage of it like creating KT2, T32...
Wut?

 

[Nestharus]

>I'd rather detailed instructions on how to use systems and the sort were included in the actual thread of the system.

This isn't a guide for a system though, but a framework =).

 

[GetTriggerUnit-]

Are stacks a kind of unidirectional linked list?

>> A Jass linked list tutorial would be pretty awesome. <3.

 

[Romek]

> >> A Jass linked list tutorial would be pretty awesome. .
It's on it's way.

My current free time (or however little of it there is) is going towards my Board Game Submission. Once that's finished, I'll finish up my linked list tutorial.

 

[GetTriggerUnit-]

<3 you.

 

[Nestharus]

GetTriggerUnit, here's a picture of what a stack typically is-
http://en.wikipedia.org/wiki/File:Data_stack.svg

Queue-
http://en.wikipedia.org/wiki/Queue_(data_structure)

Dequeue-
Double ended queue ; D


So... how should I better focus this guide? Keep the theory in there or work solely on the operations?

Oh and Romek, I hope your guide will go over smart design on these collections. A lot of the collections make each node point to the head or the head+tail, which is killer overhead ;D. Furthermore, many of them have only one thingie that acts as both a head and a tail >.<, which causes all sorts of other problems.

Smart design is the best design I always say ^_^.