Discussion N-Dimensional Arrays, Useful?

[Jesus4Lyf]

Jesus, this worked for me

It works about as well as

globals
    private integer StoredValue
endglobals
function StoreInHashtable takes integer key, integer value returns nothing
    set StoredValue=value
endfunction
function ReadFromHashtable takes integer key returns integer
    return StoredValue
endfunction

Try something like this:

function test takes nothing returns nothing
        set MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][5][-200][90000]=2
        set MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][6][-200][90000]=3
        call BJDebugMsg(I2S(MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][5][-200][90000]))
        call BJDebugMsg(I2S(MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][6][-200][90000]))
    endfunction

Haven't tried it. I expect it would fail.

 

[Sevion]

The 90000 fails because this has a 8192 limit :-/

Though, if I change the 90000 to 8191, it works fine <3

Though, I've been playing around with it trying to get it to work with data retrieval and storage in any of the dimensions... Until I got sidetracked into playing some Halo on XBL ;3

 

[Jesus4Lyf]

The 90000 fails because this has a 8192 limit :-/

Though, if I change the 90000 to 8191, it works fine <3

library MDA    
    //! textmacro NEWARRAY takes DIMENSION, NEXTDIMENSION, END
        struct array$DIMENSION$ extends array
            integer data
            static if $END$ then
                method operator [] takes integer index returns thistype
                    return thistype(index).data
                endmethod
            else
                method operator [] takes integer index returns array$NEXTDIMENSION$
                    return index
                endmethod
            endif
            method operator []= takes integer index, integer data returns nothing
                set thistype(index).data = data
            endmethod
        endstruct
    //! endtextmacro
    
    //! runtextmacro NEWARRAY("4", "0", "true")
    //! runtextmacro NEWARRAY("3", "4", "false")
    //! runtextmacro NEWARRAY("2", "3", "false")
    
    struct MDA_array extends array
        integer data
        static method operator [] takes integer index returns array2
            return index
        endmethod
        method operator []= takes integer index, integer data returns nothing
            set thistype(index).data = data
        endmethod
    endstruct
endlibrary

scope Test initializer test
    function test takes nothing returns nothing
        set MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][5][-200][8191]=2
        set MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][6][-200][8191]=3
        call BJDebugMsg(I2S(MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][5][-200][8191]))
        call BJDebugMsg(I2S(MDA_array[GetHandleId(CreateTimer())][GetHandleId(GetTriggerUnit())][6][-200][8191]))
    endfunction
endscope

No, Sevion. No, it does not work fine. As I said, it does not even come close to working at all.

It displays 3 twice, instead of two. And indeed, as long as the last index is the same, it will overwrite, making every previous index redundant. It is actually really blatant in your code:

method operator [] takes integer index returns array$NEXTDIMENSION$
                    return index
                endmethod

That method makes no use of "this" whatsoever, which means what's returned is irrelevant to the current array you are on.

In fact, even your own test shouldn't work if your implementation is correct:

// 'i' will change with each index you write. Obviously.
        set i = GetHandleId(CreateTimer())
        set MDA_array<i>[5][-200][8191]=2
        set i = GetHandleId(CreateTimer())
        set MDA_array<i>[5][-199][1531]=3
        set i = GetHandleId(CreateTimer())
        set MDA_array<i>[5][-198][8116]=4
        set i = GetHandleId(CreateTimer())
        set MDA_array<i>[5][-197][3457]=5
        set i = GetHandleId(CreateTimer())
        set MDA_array<i>[5][-200][14]=6
        // yet here you read from the &#039;i&#039; for the last one every time.
        call BJDebugMsg(&quot;Value: &quot; + I2S(MDA_array<i>[5][-200][8191]))
        call BJDebugMsg(&quot;Value: &quot; + I2S(MDA_array<i>[5][-199][1531]))
        call BJDebugMsg(&quot;Value: &quot; + I2S(MDA_array<i>[5][-198][8116]))
        call BJDebugMsg(&quot;Value: &quot; + I2S(MDA_array<i>[5][-197][3457]))
        call BJDebugMsg(&quot;Value: &quot; + I2S(MDA_array<i>[5][-200][14]))
        // therefore, obviously at least the first index is irrelevant.</i></i></i></i></i></i></i></i></i></i>

I would refer you back to my implementation of this.

library NArray
    globals
        private hashtable Store=InitHashtable()
    endglobals
    struct NArray
        method operator[] takes integer index returns thistype
            if not HaveSavedInteger(Store,this,index) then
                call SaveInteger(Store,this,index,thistype.create())
            endif
            return thistype(LoadInteger(Store,this,index))
        endmethod
        method operator []= takes integer index, integer value returns nothing
            call SaveInteger(Store,this,index,value)
        endmethod
    endstruct
endlibrary

Here is the correct implementation. The only limitation is you must only read where you know you have written a value, and do not write to where you intend to read as an array.

This does not include flushing, and hence leaks on destroy.

Anyone want to admire how useless it is? It's basically table on crack...

Edit: Here is what seems to be the perfect implementation.

library NArray // Jesus4Lyf's NArray demonstration.
    struct NArray
        private static hashtable Store=InitHashtable()
        
        private thistype next
        private thistype prev
        
        private static thistype new
        method operator[] takes integer index returns thistype
            if not HaveSavedInteger(Store,this,index) then
                set thistype.new=thistype.allocate()
                set this.prev.next=thistype.new
                set thistype.new.prev=this.prev
                set thistype.new.next=this
                set this.prev=thistype.new
                call SaveInteger(thistype.Store,this,index,thistype.new)
                return thistype.new
            endif
            return thistype(LoadInteger(thistype.Store,this,index))
        endmethod
        method operator []= takes integer index, integer value returns nothing
            call SaveInteger(thistype.Store,this,index,value)
        endmethod
        static method create takes nothing returns thistype
            local thistype this=thistype.allocate()
            set this.next=this
            set this.prev=this
            return this
        endmethod
        method destroy takes nothing returns nothing
            local thistype node=this.next
            loop
                exitwhen node==this
                call node.destroy()
                set node=node.next
            endloop
            call FlushChildHashtable(thistype.Store,this)
            set this.next.prev=this.prev
            set this.prev.next=this.next
            call this.deallocate()
        endmethod
    endstruct
endlibrary

scope Test initializer test
    function test takes nothing returns nothing
        local timer t=CreateTimer()
        
        local NArray arr=NArray.create()
        set arr[90000][-90000][GetHandleId(t)]=577
        set arr[90000][-90000][2][9][GetHandleId(t)][GetUnitTypeId(GetTriggerUnit())][8][7][6][5][4][3][2][1][19029532890]=209348
        call BJDebugMsg(I2S(arr[90000][-90000][GetHandleId(t)]))
        call BJDebugMsg(I2S(arr[90000][-90000][2][9][GetHandleId(t)][GetUnitTypeId(GetTriggerUnit())][8][7][6][5][4][3][2][1][19029532890]))
        call arr.destroy()
        
        call DestroyTimer(t)
        set t=null
    endfunction
endscope

The NArray. May no one ever find a valid use for it...
It's actually efficient, solid data storage, of infinite dimension (but can only store globally 8191 integers, totally).
It will automatically clean itself, when you destroy.

 

[Jesus4Lyf]

The only limitation is you must only read where you know you have written a value, and do not write to where you intend to read as an array.

...

Edit: Here is what seems to be the perfect implementation.

library NArray // Jesus4Lyf's NArray demonstration.
    struct NArray
        private static hashtable Store=InitHashtable()
        
        private thistype next
        private thistype prev
        
        private static thistype new
        method operator[] takes integer index returns thistype
            if not HaveSavedInteger(Store,this,index) then
                set thistype.new=thistype.allocate()
                set this.prev.next=thistype.new
                set thistype.new.prev=this.prev
                set thistype.new.next=this
                set this.prev=thistype.new
                call SaveInteger(thistype.Store,this,index,thistype.new)
                return thistype.new
            endif
            return thistype(LoadInteger(thistype.Store,this,index))
        endmethod
        method operator []= takes integer index, integer value returns nothing
            call SaveInteger(thistype.Store,this,index,value)
        endmethod
        static method create takes nothing returns thistype
            local thistype this=thistype.allocate()
            set this.next=this
            set this.prev=this
            return this
        endmethod
        method destroy takes nothing returns nothing
            local thistype node=this.next
            loop
                exitwhen node==this
                call node.destroy()
                set node=node.next
            endloop
            call FlushChildHashtable(thistype.Store,this)
            set this.next.prev=this.prev
            set this.prev.next=this.next
            call this.deallocate()
        endmethod
    endstruct
endlibrary

scope Test initializer test
    function test takes nothing returns nothing
        local timer t=CreateTimer()
        
        local NArray arr=NArray.create()
        set arr[90000][-90000][GetHandleId(t)]=577
        set arr[90000][-90000][2][9][GetHandleId(t)][GetUnitTypeId(GetTriggerUnit())][8][7][6][5][4][3][2][1][19029532890]=209348
        call BJDebugMsg(I2S(arr[90000][-90000][GetHandleId(t)]))
        call BJDebugMsg(I2S(arr[90000][-90000][2][9][GetHandleId(t)][GetUnitTypeId(GetTriggerUnit())][8][7][6][5][4][3][2][1][19029532890]))
        call arr.destroy()
        
        call DestroyTimer(t)
        set t=null
    endfunction
endscope

The NArray. May no one ever find a valid use for it...
It's actually efficient, solid data storage, of infinite dimension (but can only store globally 8191 integers, totally).
It will automatically clean itself, when you destroy.

Bump for comment.

 

[the Immortal]

Really cool as a concept (and realization) but really can't seem to find a use for it anywhere.

Also, at its current state .destroy() doesn't work - stops the thread. Though I'm not quite sure if I understand your recycling mechanism, I suppose it comes from the .allocate() instead of .create() when making the child structs (you need to init the linked list for each of them, too, in order to free the indexes, don't you?); simply replacing it doesn't seem to work but gonna try to debug it (if you don't do it before me, that is).

Also the integer limit can be fixed by saving in the hashtable the .next and .prev (that would mean excessive calling to Save/LoadInteger, though). Hmm, but that means allocators will have to be rewritten as well, and may (depending on impelementation / restrictions) need a hashtable abuse, as well.

Apart from that, I find it (completely) useless. I haven't seen much cases (and none in war3) where an N array would be needed. Generally you always know whether you need a 1, 2, 3 or.. even 4-dimensional one. And then a simple 1-line hashtable wrapper could do the same work.

EDIT: Wrong understanding of recycling. Whited out

EDIT 2: in the destroy method should replace [ljass]call node.destroy()[/ljass] with [ljass]call node.deallocate()[/ljass] to recycle properly.

 

[Sevion]

Well, I suppose you are correct Jesus. I can't think of any way using my method to completely recreate what you've done. Oh, well.

 

[Jesus4Lyf]

Also, at its current state .destroy() doesn't work - stops the thread.
...
EDIT 2: in the destroy method should replace [ljass]call node.destroy()[/ljass] with [ljass]call node.deallocate()[/ljass] to recycle properly.

That's not recursive - it will leak. I can't see why, at a glance, it would thread terminate, but perhaps I can look into it..

I don't "recycle" at all.

... Ah. I see now. I need to break up my linked list into two.
Requires a significant rework of my node tracking to fix.

Edit: I lie. Here's the fix (freehanded):

library NArray // Jesus4Lyf's NArray demonstration.
    struct NArray
        private static hashtable Store=InitHashtable()
        
        private thistype next
        private thistype prev
        
        private static thistype new
        method operator[] takes integer index returns thistype
            if not HaveSavedInteger(Store,this,index) then
                set thistype.new=thistype.allocate()
                set this.prev.next=thistype.new
                set thistype.new.prev=this.prev
                set thistype.new.next=this
                set this.prev=thistype.new
                call SaveInteger(thistype.Store,this,index,thistype.new)
                return thistype.new
            endif
            return thistype(LoadInteger(thistype.Store,this,index))
        endmethod
        method operator []= takes integer index, integer value returns nothing
            call SaveInteger(thistype.Store,this,index,value)
        endmethod
        static method create takes nothing returns thistype
            local thistype this=thistype.allocate()
            set this.next=this
            set this.prev=this
            return this
        endmethod
        method destroy takes nothing returns nothing
            local thistype node=this.next
            loop
                call FlushChildHashtable(thistype.Store,node)
                call node.deallocate()
                exitwhen node==this
                set node=node.next
            endloop
        endmethod
    endstruct
endlibrary

scope Test initializer test
    function test takes nothing returns nothing
        local timer t=CreateTimer()
        
        local NArray arr=NArray.create()
        set arr[90000][-90000][GetHandleId(t)]=577
        set arr[90000][-90000][2][9][GetHandleId(t)][GetUnitTypeId(GetTriggerUnit())][8][7][6][5][4][3][2][1][19029532890]=209348
        call BJDebugMsg(I2S(arr[90000][-90000][GetHandleId(t)]))
        call BJDebugMsg(I2S(arr[90000][-90000][2][9][GetHandleId(t)][GetUnitTypeId(GetTriggerUnit())][8][7][6][5][4][3][2][1][19029532890]))
        call arr.destroy()
        
        call DestroyTimer(t)
        set t=null
    endfunction
endscope

Immortal was right, but I needed to also flush the child hashtable for the node. I accidentally wrote something better than I intended to, and mistook it for what I intended it to be instead. XD

 

[the Immortal]

Wait, if I got it properly, you have the main object, with a linked list on it; then every child node of that object gets added to the list.
So if you write arr[1][2][3] then the 1 is attached to the main list, 2 is attached as 'next' of 1 i.e. in the same list and so on.

Then you save into hashtable using (this, index) meaning in destroy (where you have to simply release (or "recycle" as I said) all indexes and flush the table) you should just loop through all objects in the linked list, [ljass].deallocate()[/ljass] them, and flush the hashtable from all members with their key. Which, I think, should clean it completely.

In other words shouldn't the destructor be something like this:

        method destroy takes nothing returns nothing
            local thistype node=this.next
            loop
                exitwhen node==this
                call node.deallocate()
                call FlushChildHashtable(thistype.Store,node)
                set node=node.next
            endloop
            call this.deallocate()
        endmethod

Isn't this how it works? With the change I suggested there's no recursion -and- it releases all indexes from the testmap and cleans the hashtable. Haven't done any further tests but I don't see any logical problems with it.


Also, as I'm not really good with these things, I would love understanding what's wrong with it / how it should work.. if you have the time to explain, so..

PS. At first I thought each new 'level' keeps a new linked list (i.e. when creating 'child' members in [] operator use .create() and then build up a new linked list for their childs, recursively using .destroy() when deallocating main object) but compared to this, it is generally an unneeded complication.

PPS. BLAAAARGH, Gotta refresh pages more often. So it works! Whee

 

[Jesus4Lyf]

PS. At first I thought each new 'level' keeps a new linked list (i.e. when creating 'child' members in [] operator use .create() and then build up a new linked list for their childs, recursively using .destroy() when deallocating main object) but compared to this, it is generally an unneeded complication.

That's what I'd thought I'd done with the linked lists. Then I realised the way I'd written it, I must have arbitrarily overwritten next/prev pointers, because each node would need to be part of a parent linked list and and child linked list, but I used the same set of pointers for both. Then I realised the way I'd written it, it would actually construct one giant linked list. Hence I realised you were actually right. I accidentally wrote a better/simpler solution than I meant to..

But yea, I agree I can't think of a good use for this. Although, I don't see why you'd need to make use of the "n" dimensions factor - I'd use this even if it was 5d or something. But I can't see myself needing 5d data storage in a hurry. It's just cool, that it's possible..

 

[SerraAvenger]

any reason we can't just use a hashtable with the known and appreciatied x*k other than multiplication being so slow?

 

[Sevion]

It's just a fun experiment

 

[Hatebreeder]

Bump for comment.

I've actually found use for this
I tried attaching structs to units. With the N Dimensional Array, I could even detect Stacks(instances).
Though it can be done in another way I assume

 

[Jesus4Lyf]

any reason we can't just use a hashtable with the known and appreciatied x*k other than multiplication being so slow?

x*k == k*x and therefore fails.
It would mean myArr[x][k] stores to the same slot as myArr[k][x]. Else I'd have used it in my implementation.

>With the N Dimensional Array, I could even detect Stacks(instances).
Do tell?

Actually, if people have a use for it, I can submit...
Just because it does actually work. Lol.

 

[Sevion]

'

So the answer to this thread be Yes. >=D

 

[SerraAvenger]

x*k == k*x and therefore fails.

It doesn't.

myArray [k1][k2][k3]int

puts myArray[x1][x2][x3]

<=>

myArray[k1*k2*k3]
puts myArray[ x1 + k1*x2 + k1*k2*x3]

If it doesn't work for you, you did something wrong. And it is actually pretty easy to compile such that k1*k2 is a constant, and if you don't want to precompile it it's still fast _enough_.

EDIT:
btw, the sole purpose for an n-dimensional array I have found so far is multilayered board games. Eg n instances of chess runing at the same time in the same environment, or SET.

 

[Sevion]

What he means is:

set myArr[10][11] = 1
set myArr[11][10] = 2

Using the x*k method, myArr[10][11] == myArr[11][10]

Because, myArr[10][11] is really myArr[10*11]

Thus, myArr[11][10] is myArr[11*10]

myArr[110]==myArr[110]

 

[Bribe]

Not if you are extending the arrays.

type Array1 extends integer array [80]
type Array2 extends Array1 array [80]
type Array3 extends Array2 array [80]

As KingPin stated.

 

[SerraAvenger]

myArray [k1][k2][k3]int
puts myArray[x1][x2][x3]

<=>

myArray[k1*k2*k3]
puts myArray[ x1 + k1*x2 + k1*k2*x3]

Try it out.

myArray [10][10]int
puts myArray[2][3]
puts myArray[3][2]

<=>

myArray[10*10] // 100
puts myArray[ 2 + 10*3] // 32
puts myArray[ 3 + 10*2] // 23

and no, 32 != 23, just in case you were wondering.

EDIT: What kinky states is nonsensical and hard to instanciate.
IIRC, all members are zero value initialized.

what you would want to do is something like this

package array
type ThreeDArray interface {
    Get( x1, x2, x3 int ) interface{}
    Set( x1, x2, x3 int, val interface{} )
}

An example struct that implements the interface and a main package to test it

package samplearray

import "array"

type sampleThreeDArray struct {
    k_2, k_3 int // no k_1 because it is always 1
    table [8192]interface{}
}

func New(k1, k2, k3 int) array.ThreeDArray {
    return sampleThreeDArray{
        k1,
        k1 * k2,
        make([]interface{}, k1 * k2 * k3 ),
    }    
}

func (a sampleThreeDArray) Get(x1, x2, x3 int) interface{} {
    return a.table[ x1 + x2 * a.k_2 + x3 * a.k_3 ]
}
func (a sampleThreeDArray) Set( x1, x2, x3 int, val interface{} ) {
    a.table[ x1 + x2 * a.k_2 + x3 * a.k_3 ] = val
}

// ...

package main

import "samplearray"

func main () {
  var := samplearray.New( 20, 25, 15 )
  var.Set( 19, 24, 14, "hi!" )  
}

I haven't compiled/gofmted those though. And yes they have no bounds checks. And yes golang comes with arrays of arrays already so this is not needed.

EDIT2:
Yes this has constant lookup and constant write. Yes this has the maximum array size of wc3 jass. Yes this supports any number of 3d arrays.

 

[Jesus4Lyf]

Serra is talking about the way vJass does multi-dimensional arrays. Not the multiplication thing mentioned earlier.

If it is possible to use it, by all means, do. But it requires restrictions around what values you can use in an index.

Indeed, it's the approach I try to take in all my systems.

Good luck using a handle id as an index, for example.

So the answer to this thread be Yes. >=D

Not really... I still agree with Serra instead. They're just theoretically useful.

 

[SerraAvenger]

Good luck using a handle id as an index, for example.

Well if you don't want to use a JASS native hashtable there, I still have my old hashich system and my doublehashing algorithms lying around = )