- Joined
- Jul 10, 2007
- Messages
- 6,306
Before you comment on how remarkably useless this is, I found a need for it in AI. I am working on creating BehaviorTree and the traditional approach requires this.
JASS:
library ArrayList /* v1.0.0.0
*************************************************************************************
*
* Used for creating cicrularly linked lists that can be of any size and that have extra functionality.
* These lists are not built for speed but rather for functionality.
*
* Any operation having to do with indexes will be O(n), so avoid them. Any other
* operation, including value counts and excluding destruction, clear, removeAll, and toString, is O(1).
*
* Destroying a list is O(2*n)
*
* This struct was modeled after the Java Vector class.
*
* Any node may be used with any method except for delete. Only non head nodes may be used with delete.
*
* next/prev pointers are hashtable reads, so this is not recommended for speed.
* The list pointer contains no data.
*
*************************************************************************************
*
* */uses/*
*
* */ Table /* hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/
*
*************************************************************************************
*
* struct ArrayList extends array
*
* integer value
* readonly integer size
* readonly thistype first
* readonly thistype last
* readonly thistype next
* readonly thistype prev
* readonly boolean isEmpty
* method operator [] takes integer index returns integer
* method operator []= takes integer index, integer value returns nothing
*
* static method create takes nothing returns thistype
* method destroy takes nothing returns nothing
*
* method add takes thistype value returns nothing
* - adds after current node (push when list is used)
* method addLast takes thistype value returns nothing
* - adds before head (enqueue)
*
* method clear takes nothing returns nothing
* method remove takes integer value returns nothing
* method removeIndexes takes integer indexStart, integer indexEnd returns nothing
* method removeAll takes integer value returns nothing
* method contains takes integer value returns boolean
*
* method getIndexOf takes integer value, integer startIndex returns integer
* method getFirstIndexOf takes integer value returns integer
* method getLastIndexOf takes integer value returns integer
*
* method getValueCount takes integer value returns integer
*
* method toString takes nothing returns string
*
* method delete takes nothing returns nothing
* - deletes node
* - list.next.delete()
*
*************************************************************************************/
struct ArrayList extends array
private static integer hashInstanceCount = 0
private static integer array hashRecycler
private static integer instanceCount = 0
private static Table hash_p
private static Table recycler
private Table next_p
private Table prev_p
private Table lookup_p
private static Table value_p
private static Table head_p
private static Table size_p
private static Table tied_p
private static Table tied_p2
private static method allocateHash takes nothing returns integer
local integer i = hashRecycler[0]
if (0 == i) then
set i = hashInstanceCount + 1
set hashInstanceCount = i
else
set hashRecycler[0] = hashRecycler[i]
endif
return i
endmethod
private static method deallocateHash takes integer hash returns nothing
set hashRecycler[hash] = hashRecycler[0]
set hashRecycler[0] = hash
endmethod
method operator value takes nothing returns integer
return value_p[this]
endmethod
private method operator head takes nothing returns thistype
return head_p[this]
endmethod
private method operator head= takes thistype head returns nothing
set head_p[this] = head
endmethod
private method operator hash takes nothing returns thistype
return hash_p[head]
endmethod
private method operator hash= takes integer value returns nothing
set hash_p[head] = value
endmethod
method operator size takes nothing returns integer
return size_p[head]
endmethod
private method operator size= takes integer value returns nothing
set size_p[head] = value
endmethod
private static method operator [] takes integer index returns thistype
return recycler[index]
endmethod
private static method operator []= takes integer index, integer value returns nothing
set recycler[index] = value
endmethod
private method operator lookup2node takes nothing returns thistype
return tied_p[this]
endmethod
private method operator node2lookup takes nothing returns thistype
return tied_p2[this]
endmethod
private method operator tied= takes thistype node returns nothing
set tied_p[this] = node
set tied_p2[node] = this
endmethod
private method clearTies takes nothing returns nothing
local thistype node = lookup2node
set tied_p[this] = 0
set tied_p2[node] = 0
endmethod
method operator next takes nothing returns thistype
return hash.next_p[this]
endmethod
method operator prev takes nothing returns thistype
return hash.prev_p[this]
endmethod
private method operator next= takes thistype i returns nothing
set hash.next_p[this] = i
endmethod
private method operator prev= takes thistype i returns nothing
set hash.prev_p[this] = i
endmethod
private method getLookup takes integer value returns thistype
return hash.lookup_p[value]
endmethod
private method setLookup takes integer value, thistype list returns nothing
set hash.lookup_p[value] = list
endmethod
method operator first takes nothing returns thistype
return head.next
endmethod
method operator last takes nothing returns thistype
return head.prev
endmethod
private method createLookup takes nothing returns nothing
set hash.lookup_p = Table.create()
endmethod
private method destroyLookup takes nothing returns nothing
call hash.lookup_p.destroy()
endmethod
method operator [] takes integer index returns integer
set this = head
loop
set this = next
exitwhen 0 == index
set index = index - 1
endloop
return value
endmethod
method operator []= takes integer index, integer value returns nothing
set this = head
loop
set this = next
exitwhen 0 == index
set index = index - 1
endloop
set this.value = value
endmethod
method getFirstIndexOf takes integer value returns integer
local integer index = 0
set this = head
if (0 != getLookup(value)) then
loop
set this = next
exitwhen this.value == value
set index = index + 1
endloop
return index
endif
return -1
endmethod
method getLastIndexOf takes integer value returns integer
local integer index
set this = head
set index = size
if (0 != getLookup(value)) then
loop
set this = prev
set index = index - 1
exitwhen this.value == value
endloop
return index
endif
return -1
endmethod
method getIndexOf takes integer value, integer startIndex returns integer
local integer index = 0
set this = head
if (0 == getLookup(value) or startIndex >= size) then
return -1
endif
loop
set this = next
exitwhen this == head or (this.value == value and index >= startIndex)
set index = index + 1
endloop
if (this == head) then
return -1
endif
return index
endmethod
method operator isEmpty takes nothing returns boolean
return 0 == size
endmethod
private static method allocate takes nothing returns thistype
local thistype this = thistype[0]
if (0 == this) then
set this = instanceCount + 1
set instanceCount = this
else
set thistype[0] = thistype[this]
endif
return this
endmethod
private method deallocate takes nothing returns nothing
set thistype[this] = thistype[0]
set thistype[0] = this
endmethod
private method initialize takes nothing returns nothing
set head = this
set hash = allocateHash()
set hash.next_p = Table.create()
set hash.prev_p = Table.create()
set next = this
set prev = this
endmethod
static method create takes nothing returns thistype
local thistype this = allocate()
call initialize()
call createLookup()
return this
endmethod
private method push takes thistype node returns nothing
set node.head = head
set head.size = head.size + 1
set this.next.prev = node
set node.next = this.next
set node.prev = this
set this.next = node
endmethod
private method pop takes nothing returns nothing
set head.size = head.size - 1
set prev.next = next
set next.prev = prev
endmethod
method contains takes integer value returns boolean
return 0 != getLookup(value)
endmethod
private static method clearLookupNode takes thistype lookupNode returns nothing
local thistype lookupList = lookupNode.head
local thistype this = lookupNode.lookup2node
call lookupNode.clearTies()
call lookupNode.pop()
if (lookupList.next == lookupList) then
call lookupList.deallocate()
call setLookup(value, 0)
call deallocateHash(lookupList.hash)
call lookupList.hash.next_p.destroy()
call lookupList.hash.prev_p.destroy()
endif
call lookupNode.deallocate()
endmethod
private method clearValue takes nothing returns nothing
call clearLookupNode(getLookup(value).next)
endmethod
method operator value= takes integer value returns nothing
local thistype lookupList
local thistype lookupNode
set lookupNode = node2lookup
if (0 != lookupNode) then
call clearLookupNode(lookupNode)
endif
set lookupList = getLookup(value)
set lookupNode = allocate()
if (0 == lookupList) then
set lookupList = allocate()
set lookupList.hash = allocateHash()
call lookupList.initialize()
call setLookup(value, lookupList)
endif
set value_p[this] = value
set value_p[lookupNode] = value
set lookupNode.tied = this
call lookupList.prev.push(lookupNode)
endmethod
method addLast takes thistype value returns nothing
local thistype node = allocate()
call head.prev.push(node)
set node.value = value
endmethod
method add takes thistype value returns nothing
local thistype node = allocate()
call push(node)
set node.value = value
endmethod
method delete takes nothing returns nothing
if (this != head) then
call clearValue()
call pop()
call deallocate()
endif
endmethod
method remove takes integer value returns nothing
local thistype lookupList = getLookup(value)
local thistype node = lookupList.next.lookup2node
if (0 == lookupList) then
return
endif
call node.delete()
endmethod
method removeAll takes integer value returns nothing
local thistype lookupList = getLookup(value)
local thistype lookupnode = lookupList
local integer size = lookupList.size
if (0 == lookupList) then
return
endif
loop
exitwhen 0 == size
set size = size - 1
call lookupnode.lookup2node.delete()
endloop
endmethod
method getValueCount takes integer value returns integer
return getLookup(value).size
endmethod
method removeIndex takes integer indexToRemove returns nothing
local integer index = 0
set this = head
if (indexToRemove >= size) then
return
endif
loop
set this = next
exitwhen index == indexToRemove
set index = index + 1
endloop
call delete()
endmethod
method removeIndexes takes integer indexStart, integer indexEnd returns nothing
local integer index = 0
set this = head
if (indexStart >= size or indexEnd < indexStart or indexEnd >= size) then
return
endif
loop
set this = next
exitwhen index == indexStart
set index = index + 1
endloop
loop
call delete()
exitwhen index == indexEnd
set this = next
set index = index + 1
endloop
endmethod
method clear takes nothing returns nothing
set this = head
loop
exitwhen 0 == size
call next.delete()
endloop
endmethod
method destroy takes nothing returns nothing
set this = head
call clear()
call deallocate()
call destroyLookup()
call hash.next_p.destroy()
call hash.prev_p.destroy()
call deallocateHash(hash)
endmethod
method toString takes nothing returns string
local string str = ""
set this = head.next
if (this == head) then
return null
endif
set str = I2S(value)
loop
set this = next
exitwhen this == head
set str = str + ", " + I2S(value)
endloop
return str
endmethod
private static method onInit takes nothing returns nothing
set recycler = Table.create()
set size_p = Table.create()
set value_p = Table.create()
set head_p = Table.create()
set tied_p = Table.create()
set tied_p2 = Table.create()
set hash_p = Table.create()
endmethod
endstruct
endlibrary
