Discussion Working TableX

[kingkingyyk3]

I was wondering around and suddenly TableX came into my mind. So I quickly rush to the computer and try to make it work. So.. it is working! :thup: It follows the concept of TableX - does not use array.

So the code is here.

library Table
    
    //! textmacro Table__make takes name, type, key
    struct $name$
        private integer value
        private thistype next
        private thistype prev
        private integer data
        private boolean haveValue
        
        static method create takes nothing returns thistype
            local thistype this = .allocate()
            set .next = this
            set .prev = this
            set .haveValue = false
            return this
        endmethod
        
        method operator []= takes $type$ key, integer data returns nothing
            local thistype id = this
            local integer target = $key$
            
            loop
                set id = id.next
            exitwhen id.value == target or id == this
            endloop
            
            if id == this then
                set id = .allocate()
                set .next.prev = id
                set id.next = .next
                set .next = id
                set id.prev = this
                
                set id.value = target
                set id.haveValue = true
            endif
            set id.data = data
        endmethod
        
        method operator [] takes $type$ key returns integer
            local thistype id = this
            local integer target = $key$
            
            loop
                set id = id.next
                if id.value == target then
                    return id.data
                endif
            exitwhen id == this
            endloop
            return 0
        endmethod
        
        method flush takes $type$ key returns nothing
            local thistype id  = this
            local integer target = $key$
            
            loop
                set id = id.next
            exitwhen id.value == target or id == this
            endloop
            
            if id.value == target then
                set id.next.prev = id.prev
                set id.prev.next = id.next
                
                set id.next = 0
                set id.prev = 0
                set id.value = 0
                set id.data = 0
                set id.haveValue = false
                
                call id.deallocate()
            endif
            
        endmethod
        
        method exists takes $type$ key returns boolean
            local thistype id  = this
            local integer target = $key$
            
            loop
                set id = id.next
            exitwhen id.value == target or id == this
            endloop
            
            return id.haveValue
        endmethod
        
    endstruct
    //! endtextmacro

    //! runtextmacro Table__make("Table","integer","key" )
    //! runtextmacro Table__make("StringTable","string", "StringHash(key)" )
    //! runtextmacro Table__make("HandleTable","handle","GetHandleId(key)" )
    
endlibrary

Personal Criticism : It simulates hashtable. However, I reckon it is slower because it used O(n) searching. :banghead: The more the data stored on it, the slower the speed it is. You need to use flush to maintain the speed of it. I believe there is no other way to achieve O(1) complexity with this concept.
Concept behind of this is a doubly linked list. Table object is a head of linked list. Every "array value" is stored inside a node. When a data is stored inside it, it will search whole list for the "array value". If there is no "array value", a node is create and linked to it. If the "array value" is present, it will simply overwrite the stored data with new one. When getting data, it will literate through all the node, checking for "array value". If the array value is present, return the data, else return 0. When flush is called, it will find whether the "array value" is present or not. If the "array value" is present, it will discard the node from the list, hence making the list faster.

 

[quraji]

So, a linked list with [ljass][][/ljass] and [ljass][]=[/ljass] operators?

Why would I prefer this over O(1) add/remove/search?

 

[kingkingyyk3]

This is only a demo. It is not recommended.
Anyway, the advantage of this is hashtables-less. I can't find any advantage other than this.

 

[BlackRose]

Can't resist. Table seX.

 

[quraji]

Anyway, the advantage of this is hashtables-less. I can't find any advantage other than this.

What's the advantage of that?

 

[Romek]

This is horrible.

 

[Jesus4Lyf]

The fastest implementation I wrote back in the day was 10% faster than gamecache. That's a big hint that this is not practical or useful.

The cool thing about it is if you can write a proper implementation of it, it inspires you to write really nice data structures. This is not, in any way, a proper implementation of it since it uses no hashing (it's all just O(n), which was not the point of TableX - TableX was actually very fast).

Actually, all kingking has written here is a linked list wrapper, and has little to nothing to do with TableX, which used a 2d linked list to achieve a faster implementation than the alternative. See below:

library Table
//***************************************************************
//***    Jesus4Lyf's    **    TABLE-X   **    Version 1.03    ***
//***************************************************************
//* Table object
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for key 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   t.exists(32)         - Was key 32 assigned? Notice
//*                          that flush() unassigns values.
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*   If you use HandleTable instead of Table, it is the same
//* but it uses handles as keys, the same with StringTable.
//*
//***************************************************************
//* This version of Table does not use GameCache.
//* Please note that all data attaching is messed up if you load
//*  a saved game. Use normal Table if you need to load games.

    ///////////////
    // Constants //
//===============================================================
    globals
        private constant integer MAX_INSTANCES=8100 //400000
        private constant integer MAX_ATTACHMENTS=8190
        // MAX_ATTACHMENTS is the maximum number of things being
        // attached to in total + the number of tables in
        // existance + 1, at any one time.
        // If it is any higher than 8190, it is slower than normal Table.

    ///////////////////////////
    // System Implementation //
//===============================================================
        private constant integer MAX_STRINGID=MAX_ATTACHMENTS-1
        private integer RandomData=MAX_ATTACHMENTS
    endglobals
    
    private keyword GTable
    
    //////////////////////////////////////////////////////
    // 2D DOUBLY LINKED-LIST HASHING TABLE SYNTAX CANDY //
    /////////////////////////////////////////////////////////////
    // Sounds fun? Think again. Use (for my own reference):
    // d.delete()
    // d.chainDelete()
    // Data.getPointer() --> Data
    // Data.getForRead(stringid) --> Data or 0
    // Data.getForWrite(trackingPointer, stringid) --> Data
    private struct Data[MAX_ATTACHMENTS] // Not really a struct, just syntax candy.
        integer stringid
        integer value
        Data prev
        Data next
        Data drill // down
        Data roll // counter-down (for unlinking)
        /////////////
        // GENERAL //
        /////////////////////////////////////////////////////////
        method wipe takes nothing returns nothing
            set this.stringid=0
            set this.value=0
            set this.prev=0
            set this.next=0
            set this.drill=0
            set this.roll=0
        endmethod
        method move takes Data targ returns Data
            // Copy
            set targ.stringid=this.stringid
            set targ.value=this.value
            set targ.prev=this.prev
            set targ.next=this.next
            set targ.drill=this.drill
            set targ.roll=this.roll
            // Fix pointers
            set this.next.prev=targ
            set this.prev.next=targ
            set this.drill.roll=targ
            set this.roll.drill=targ
            // Clean up
            call this.wipe()
            // Done
            return targ // Probably unneeded.
        endmethod
        method init takes Data prev, integer stringid returns nothing
            set this.stringid=stringid
            set prev.next.prev=this
            set this.next=prev.next
            set prev.next=this
            set this.prev=prev
        endmethod
        static method getRandom takes nothing returns Data
            local integer oldrandom=RandomData
            set RandomData=RandomData-1
            loop
                if RandomData<1 then
                    set RandomData=MAX_ATTACHMENTS-1
                endif
                exitwhen Data(RandomData).stringid==0
                if RandomData==oldrandom then
                    call BJDebugMsg("Table-X out of space. Increase MAX_ATTACHMENTS constant.")
                endif
                set RandomData=RandomData-1
            endloop
            return RandomData
        endmethod
        method delete takes nothing returns nothing
            set this.next.prev=this.prev
            set this.prev.next=this.next
            set this.drill.roll=this.roll
            set this.roll.drill=this.drill
            if this.roll==0 and this.drill!=0 then
                call this.drill.move(this)
            else
                call this.wipe()
            endif
        endmethod
        method chainDelete takes nothing returns nothing
            if this==0 then
                return
            endif
            call this.next.chainDelete()
            if this.roll==0 and this.drill!=0 then
                call this.drill.move(this)
            else
                call this.wipe()
            endif
        endmethod
        static method getPointer takes nothing returns Data
            local Data d=Data.getRandom()
            set d.stringid=-1
            return d
        endmethod
        
        //////////////////////////
        // STACKING ABSTRACTION //
        /////////////////////////////////////////////////////////
        method stack takes Data nextDown returns Data
            set this.drill.roll=nextDown
            set nextDown.drill=this.drill
            set this.drill=nextDown
            set nextDown.roll=this
            return nextDown
        endmethod
        static method get takes integer stringid returns Data
            local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
            loop
                if d.stringid==stringid then
                    return d // d.stringid=stringid
                endif
                exitwhen d.drill==0
                set d=d.drill
            endloop
            return d // may be empty or not, but is not the stringid's data, so stack or init here.
        endmethod
        static method getForRead takes integer stringid returns Data
            local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
            loop
                if d.stringid==stringid then
                    return d // d.stringid=stringid
                endif
                exitwhen d.drill==0
                set d=d.drill
            endloop
            return 0
        endmethod
        static method getForWrite takes Data flushList, integer stringid returns Data
            local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
            loop
                if d.stringid==stringid then
                    return d // d.stringid=stringid
                endif
                exitwhen d.drill==0
                set d=d.drill
            endloop
            if d.stringid!=0 then
                set d=d.stack(Data.getRandom()) // Get one stacked onto returned one.
                // d has become the result of getRandom here.
            endif
            call d.init(flushList,stringid)
            return d
        endmethod
    endstruct
    
    private struct GTable[MAX_INSTANCES]
        // A "protected" keyword would've been really nice here.
        // Don't play with "trackingPointer" or "base" in your map.
        // Looking for ideas on how to protect them, still.
        Data trackingPointer
        string base
        
        method reset takes nothing returns nothing
            call this.trackingPointer.chainDelete()
            set this.trackingPointer=Data.getPointer()
            //call FlushStoredMission(gc,I2S(this))
        endmethod
        
        private method onDestroy takes nothing returns nothing
            call this.trackingPointer.chainDelete()
            //call FlushStoredMission(gc,I2S(this))
        endmethod
    endstruct
    
    globals//locals
        private integer sid
        private Data dat
    endglobals
    
    //Hey: Don't instanciate other people's textmacros that you are not supposed to, thanks.
    //! textmacro Table__make takes name, type, key
    struct $name$ extends GTable
        static method create takes nothing returns $name$
            local $name$ d=$name$.allocate()
            set d.trackingPointer=Data.getPointer()
            set d.base=I2S(d)+"x"
            return d
        endmethod
        
        method operator [] takes $type$ key returns integer
            set sid=StringHash(this.base+$key$)
            set dat=sid-(sid/MAX_STRINGID)*MAX_STRINGID+1
            loop
                if dat.stringid==sid then
                    return dat.value // d.stringid=stringid
                endif
                exitwhen dat.drill==0
                set dat=dat.drill
            endloop
            return 0
        endmethod
        
        method operator []= takes $type$ key, integer value returns nothing
            set sid=StringHash(this.base+$key$)
            set dat=sid-(sid/MAX_STRINGID)*MAX_STRINGID+1
            loop
                exitwhen dat.stringid==sid
                if dat.drill==0 then
                    if dat.stringid!=0 then
                        set dat=dat.stack(Data.getRandom()) // Get one stacked onto returned one.
                        // d has become the result of getRandom here.
                    endif
                    call dat.init(this.trackingPointer,sid)
                    return
                endif
                set dat=dat.drill
            endloop
            set dat.value=value
        endmethod
        
        method flush takes $type$ key returns nothing
            local Data d=Data.getForRead(StringHash(this.base+$key$))
            if d!=0 then
                call d.delete()
            endif
        endmethod
        
        method exists takes $type$ key returns boolean
            return Data.getForRead(StringHash(this.base+$key$))!=0
        endmethod
    endstruct
    //! endtextmacro
    
    //! runtextmacro Table__make("Table","integer","I2S(key)")
    //! runtextmacro Table__make("StringTable","string","key")
    //! runtextmacro Table__make("HandleTable","handle","I2S(GetHandleId(key))")
endlibrary

A much better version. :thup:
(Still probably not as fast as hashtables.)

 

[kingkingyyk3]

This is horrible.
Exactly.

 

[Romek]

> Exactly.
Why did you post it then? It doesn't even serve as a 'demo', and it just makes J4L's code (which you claim this is similar to) look bad.

I need to finish my Linked List tutorial.

 

[Lyerae]

> I need to finish my Linked List tutorial.

DO IT!
Please?