kingkingyyk3
Visitor (Welcome to the Jungle, Baby!)
- Reaction score
- 216
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.
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.
So the code is here.
JASS:
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.