- Joined
- Aug 4, 2006
- Messages
- 357
Requires
JassNewGenPack
Warcraft 3 v1.24 or above
Some Jass and vJass knowledge
What is this?
A List is basically like an array that keeps its contents stored between index 0 and the current size of the List. It is an easy way to store structs, handles, reals, and whatever the hell you want. It imitates the functionality of ArrayLists (from Java), but uses hashtables instead of arrays.
Pros:
Dates are MM/DD/YY. Times are GMT-10:00
1.0 (07/16/09, 1:49am)
Credits
List was made from scratch and I put a lot of work into it, so please give me credit; if you just copy/paste the List library directly into your map, I am happy. I just don't want you deleting the header comments that say I made it.
Example List Spell
So you still might be wondering how List could be useful for you. For that reason (and for fun), I made a Fire Wall spell. It has a main FireWall struct, that contains an IntegerList of all the Flame struct instances that make up the wall. List makes it easy to loop through all the flames to damage nearby units. List is also perfect to use here as the member of a struct. If you used an array to store the flames, you would limit how big of a wall you could make and/or how many FireWalls could be used at once. Since we use List, the only limit we need to worry about is how many Flame instances are on the map at one time, and your map would be doing something wrong if it ever had 8191 Flames burning at once. See the test map below for the spell code. You can just search for the parts that deal with the "flames" IntegerList.
JassNewGenPack
Warcraft 3 v1.24 or above
Some Jass and vJass knowledge
What is this?
A List is basically like an array that keeps its contents stored between index 0 and the current size of the List. It is an easy way to store structs, handles, reals, and whatever the hell you want. It imitates the functionality of ArrayLists (from Java), but uses hashtables instead of arrays.
Pros:
- Keeps its contents together and preserves the order in which they were added.
- Unlike arrays, Lists can be parameters of functions.
- Due to the above 2, List is easy to sort and loop through.
- Lists can always have an unlimited number of elements, whereas arrays can only have 8191 (or much less if the array is a member of a struct).
- Due to the above, List is great for using as a struct member.
- O(1) to get or set any object in the list.
- O(1) to add or remove an object from the front or back of the list
- O(N/2) worst case to add or remove an object from a random position in the list.
- Can store any form of data.
- Slower than working with arrays.
- Removing, replacing, or clearing handle objects can leak bad if not done responsibly. Oh wait, that can happen with any data storage system in wc3...
- Each List textmacro that you run will add ~2.6kb to your map size. If this actually matters to you, only run the textmacros for List types that you will actually use. If you are really desparate, you can delete any methods you won't use. However, this is not recommended since some List methods may make calls to other List methods.
- O(N) worst case to find the index of an object, but you should be keeping track of the indexes of your objects anyway.
JASS:
//---------important methods-------------
method operator size takes nothing returns integer
//purpose: returns the number of elements in the list.
method addLast takes $type$ object returns nothing
//purpose: appends the specified object to the end of the list.
// increases the size of the list by 1. does not shift the list.
//example:
local IntegerList intList = IntegerList.create()
call intList.addLast(35)
//intList is now { 35}
call intList.addLast(62)
//intList is now { 35, 62}
call intList.addLast(1)
//intList is now { 35, 62, 1}
method addFirst takes $type$ object returns nothing
//purpose: appends the specified object to the beginning of the list.
// increases the size of the list by 1.
// objects will seem to shift right, but the method does not loop.
//example (continued from above):
call intList.addFirst(92)
//intList is now { 92, 35, 62, 1}
method removeLast takes nothing returns $type$
//purpose: detaches the last object from the list and returns it.
// decreases .size by 1.
//example (continued):
intList.removeLast() //removes intList[3] and returns 1
//intList is now { 92, 35, 62}
method removeFirst takes nothing returns $type$
//purpose: detaches the first object from the list and returns it.
// decreases .size by 1.
// objects will seem to shift left, but the method does not loop.
//example (continued):
intList.removeFirst() //remove intList[0] and returns 92
//intList is now { 35, 62}
method operator [] takes integer index returns $type$
//purpose: get the object stored at the specified position
//example (continued):
intList[2] //reports an error if in debug mode, returns 0 by default
intList[1] //returns 62
method operator []= takes integer index, $type$ object returns nothing
//purpose: replace the object at the specified position with the specified object
//example (continued):
set intList[5] = 98 //reports an error if in debug mode, returns 0 by default
set intList[0] = 22 //replace 35 with 22
//intList is now { 22, 62}
method add takes integer index, $type$ object returns nothing
//purpose: inserts the specified object at the specified position.
//Any objects at or after this position will seem to shift right one position.
//Increases .size by 1
//example (continued):
call intList.add(2, 573) //adding at .size works the same as addLast
//intList is now { 22, 62, 573}
call intList.add(0, 6) //adding at 0 works the same as addFirst
//intList is now { 6, 22, 62, 573}
call intList.add(1, 59)
//intList is now { 6, 59, 22, 62, 573}
method remove takes integer index returns $type$
//purpose: removes the object at the specified index and returns it.
//Any objects after this will appear to shift left one slot.
//example (continued):
intList.remove(2) //returns 22
//intList is now { 6, 59, 62, 573}
method clear takes nothing returns nothing
//purpose: clears the entire list quickly
//example (continued):
call intList.clear()
//intList is now { }
//----------end important methods--------------
//------------------other methods-------------
method removeRange takes integer fromIndex, integer toIndex returns nothing
//purpose: removes from this List all of the elements whose index is between
// fromIndex (inclusive) and toIndex (exclusive).
method indexOf takes $type$ object returns integer
//purpose: returns the index of the first occurance of the given object.
// returns -1 if the object is not found.
method lastIndexOf takes $type$ object returns integer
//purpose: returns the index of the last occurance of the given object.
// returns -1 if the object is not found.
method swap takes integer index1, integer index2 returns nothing
//purpose: swaps the positions of two elements in the same list.
method exists takes integer index returns boolean
//purpose: returns true if there is an object stored at the specified position
method isEmpty takes nothing returns boolean
//purpose: returns true if list is empty
//--------------end other methods--------------------
JASS:
library List
//==================================================================================
// List version 1.1
//----------------------------
// Use this version in your map.
//==================================================================================
// - made by MaskedPoptart
// - imitates the functionality of ArrayLists (from Java)
// using a hashtable.
//==================================================================================
// Basic Usage:
// set arr = IntegerList.create() - instantiate a List of integers
// arr.size - get the current number of elements
// call arr.addLast(5732) - add 5732 to the end of the list,
// increase .size by 1
// arr.removeLast() - remove the last element in the list,
// decrease .size by 1, return removed element
// arr.remove(6) - remove the 6th element, decrease .size by 1,
// return removed element, shift elements down
// arr[3] - get the element at index 3
// set arr[23] = 815 - replace the value at index 23 with 815
// call arr.clear() - remove all objects from the list
// call arr.destroy() - clear list and recycle the struct index
//
// WARNING: Most attempts to work with indexes <0 or >=.size will fail and
// generate an error message in debug mode. Returns default to 0 for integers/
// reals, null for handles, false for booleans, etc.
//
// LEAK WARNING: List does no automatic garbage collection. If a List
// is the only place you store a variable, make sure the variable will not leak when
// you remove it or replace it.
//===================================================================================
// Credits:
// - Vexorian for JassHelper
// - Vexorian for Table 3.0 (which I used for reference)
// - All the other people who worked on JassNewGenPack
//===================================================================================
globals
private constant integer MAX_INSTANCES = 8190
endglobals
//! textmacro List takes type, listType, typeName
struct $listType$List [MAX_INSTANCES]
private integer min = -1
private integer max = 0
private static hashtable contents = InitHashtable()
private static $type$ tempObject
private static $type$ DEFAULT_VALUE
private static method onInit takes nothing returns nothing
set thistype.DEFAULT_VALUE = Load$typeName$(thistype.contents,0,0)
endmethod
private method getActualIndex takes integer publicIndex returns integer
return publicIndex + this.min + 1
endmethod
private method getPublicIndex takes integer actualIndex returns integer
return actualIndex - this.min - 1
endmethod
private method isValidIndex takes integer actualIndex returns boolean
return actualIndex > this.min and actualIndex < this.max
endmethod
//---------------------USER METHODS------------------------
method operator size takes nothing returns integer
return this.max-this.min-1
endmethod
method addFirst takes $type$ object returns nothing
call Save$typeName$(this.contents, integer(this), this.min, object)
set this.min = this.min - 1
endmethod
method addLast takes $type$ object returns nothing
call Save$typeName$(this.contents, integer(this), this.max, object)
set this.max = this.max + 1
endmethod
method removeFirst takes nothing returns $type$
if(this.size>0)then
set this.min = this.min + 1
return Load$typeName$(this.contents, integer(this), this.min)
endif
debug call BJDebugMsg("ERROR: $listType$List \"removeFirst\" method. Cannot remove from an empty List.")
return this.DEFAULT_VALUE
endmethod
method removeLast takes nothing returns $type$
if(this.size>0)then
set this.max = this.max - 1
return Load$typeName$(this.contents, integer(this), this.max)
endif
debug call BJDebugMsg("ERROR: $listType$List \"removeLast\" method. Cannot remove from an empty List.")
return this.DEFAULT_VALUE
endmethod
method operator [] takes integer index returns $type$
local integer actualIndex = this.getActualIndex(index)
if(this.isValidIndex(actualIndex))then
return Load$typeName$(this.contents, integer(this), actualIndex)
endif
debug call BJDebugMsg("ERROR: $listType$List \"[]\" method. Index Out of Bounds ("+I2S(index)+").")
return this.DEFAULT_VALUE
endmethod
method operator []= takes integer index, $type$ object returns nothing
local integer actualIndex = this.getActualIndex(index)
if(this.isValidIndex(actualIndex))then
call Save$typeName$(this.contents, integer(this), actualIndex, object)
debug else
debug call BJDebugMsg("ERROR: $listType$List \"[]=\" method. Index Out of Bounds ("+I2S(index)+").")
endif
endmethod
method add takes integer index, $type$ object returns nothing
local integer i
local integer actualIndex = this.getActualIndex(index)
if(actualIndex > this.min and actualIndex <= this.max)then
if(actualIndex <= 0.5*(this.min+this.max))then
set actualIndex = actualIndex - 1
set i = this.min
loop
exitwhen i >= actualIndex
call Save$typeName$(this.contents, integer(this), i, Load$typeName$(this.contents, integer(this), i+1))
set i = i + 1
endloop
set this.min = this.min - 1
else
set i = this.max
loop
exitwhen i <= actualIndex
call Save$typeName$(this.contents, integer(this), i, Load$typeName$(this.contents, integer(this), i-1))
set i = i - 1
endloop
set this.max = this.max + 1
endif
call Save$typeName$(this.contents, integer(this), actualIndex, object)
debug else
debug call BJDebugMsg("ERROR: $listType$List \"add\" method. Index Out of Bounds ("+I2S(index)+").")
endif
endmethod
method remove takes integer index returns $type$
local integer i
local integer actualIndex = this.getActualIndex(index)
if(this.isValidIndex(actualIndex))then
set this.tempObject = Load$typeName$(this.contents, integer(this), actualIndex)
set i = actualIndex
if(actualIndex <= 0.5*(this.min+this.max))then
set this.min = this.min + 1
loop
exitwhen i <= this.min
call Save$typeName$(this.contents, integer(this), i, Load$typeName$(this.contents, integer(this), i-1))
set i = i - 1
endloop
else
set this.max = this.max - 1
loop
exitwhen i >= this.max
call Save$typeName$(this.contents, integer(this), i, Load$typeName$(this.contents, integer(this), i+1))
set i = i + 1
endloop
endif
return this.tempObject
endif
debug call BJDebugMsg("ERROR: $listType$List \"remove\" method. Index Out of Bounds ("+I2S(index)+").")
return this.DEFAULT_VALUE
endmethod
method clear takes nothing returns nothing
call FlushChildHashtable(this.contents, integer(this))
set this.min = -1
set this.max = 0
endmethod
method removeRange takes integer fromIndex, integer toIndex returns nothing
local integer i
local integer actualFromIndex = this.getActualIndex(fromIndex)
local integer actualToIndex = this.getActualIndex(toIndex-1)
if(this.isValidIndex(actualFromIndex))then
if(this.isValidIndex(actualToIndex) and toIndex>fromIndex)then
if(actualFromIndex-this.min < this.max-actualToIndex)then
set i = actualFromIndex
loop
set i = i - 1
exitwhen i<=this.min
call Save$typeName$(this.contents, integer(this), i-fromIndex+toIndex, Load$typeName$(this.contents, integer(this), i))
endloop
set this.min = this.min-fromIndex+toIndex
else
set i = actualToIndex
loop
set i = i + 1
exitwhen i>=this.max
call Save$typeName$(this.contents, integer(this), i+fromIndex-toIndex, Load$typeName$(this.contents, integer(this), i))
endloop
set this.max = this.max+fromIndex-toIndex
endif
debug else
debug call BJDebugMsg("ERROR: $listType$List \"removeRange\" method. Index Out of Bounds ("+I2S(toIndex)+").")
endif
debug else
debug call BJDebugMsg("ERROR: $listType$List \"removeRange\" method. Index Out of Bounds ("+I2S(fromIndex)+").")
endif
endmethod
method indexOf takes $type$ object returns integer
local integer i = this.min
loop
set i = i + 1
exitwhen i>=this.max
if(Load$typeName$(this.contents, integer(this), i) == object)then
return this.getPublicIndex(i)
endif
endloop
return -1
endmethod
method lastIndexOf takes $type$ object returns integer
local integer i = this.max
loop
set i = i - 1
exitwhen i<=this.min
if(Load$typeName$(this.contents, integer(this), i) == object)then
return this.getPublicIndex(i)
endif
endloop
return -1
endmethod
method swap takes integer index1, integer index2 returns nothing
local integer actualIndex1 = this.getActualIndex(index1)
local integer actualIndex2 = this.getActualIndex(index2)
if(this.isValidIndex(actualIndex1))then
if(this.isValidIndex(actualIndex2))then
set this.tempObject = Load$typeName$(this.contents, integer(this), actualIndex1)
call Save$typeName$(this.contents, integer(this), actualIndex1, Load$typeName$(this.contents, integer(this), actualIndex2))
call Save$typeName$(this.contents, integer(this), actualIndex2, this.tempObject)
debug else
debug call BJDebugMsg("ERROR: $listType$List \"swap\" method. Index Out of Bounds ("+I2S(index2)+").")
endif
debug else
debug call BJDebugMsg("ERROR: $listType$List \"swap\" method. Index Out of Bounds ("+I2S(index1)+").")
endif
endmethod
method exists takes integer index returns boolean
return index >= 0 and index < this.size
endmethod
method isEmpty takes nothing returns boolean
return this.max == 0
endmethod
//------------------END USER METHODS----------------------
private method onDestroy takes nothing returns nothing
call this.clear()
endmethod
endstruct
//! endtextmacro
//runtextmacro List( "type", "listType", "typeName" )
//type = type of object to store. must be exact.
//listType = prefix to the List struct name. can be whatever you want.
//ex: Timer --> TimerList
//typeName = suffix in Save, Load hashtable functions. must be exact.
//ex: Str --> LoadStr
//! runtextmacro List( "integer", "Integer", "Integer" )
//! runtextmacro List( "string", "String", "Str" )
//! runtextmacro List( "real", "Real", "Real" )
//! runtextmacro List( "boolean", "Boolean", "Boolean" )
//! runtextmacro List( "player", "Player", "PlayerHandle" )
//! runtextmacro List( "unit", "Unit", "UnitHandle" )
//! runtextmacro List( "item", "Item", "ItemHandle" )
//! runtextmacro List( "widget", "Widget", "WidgetHandle" )
//! runtextmacro List( "timer", "Timer", "TimerHandle" )
//! runtextmacro List( "effect", "Effect", "EffectHandle" )
//! runtextmacro List( "rect", "Rect", "RectHandle" )
//! runtextmacro List( "group", "Group", "GroupHandle" )
//! runtextmacro List( "force", "Force", "ForceHandle" )
// Add as many handle list types as you want, and comment out the ones you do not use
// so they do not take up unnecessary space in your map script.
endlibraryDates are MM/DD/YY. Times are GMT-10:00
1.0 (07/16/09, 1:49am)
- initial release
- added fastRemove method.
- optimized a bunch of methods (mainly removeRange).
- some other minor changes.
- added struct indexer example to thread (07/22/09, 4:17pm).
- internal contents are now stored from "min" to "max" instead of 0 to "size".
- from user perspective, contents are still stored from 0 to size.
- internally, though, this allows for some new methods and optimizations.
- added addFirst, removeFirst instance methods.
- changed name of push to addLast, pop to removeLast.
- removed fastRemove method.
- optimized a bunch of methods, including: add, remove, removeRange.
- some other minor changes.
- updated struct indexer example, and included the slower (but simpler) way to do it. (07/30/09, 7:06pm)
- replaced struct indexer examples with a Fire Wall spell (I felt they were poor examples). Replaced method test map with Fire Wall test map. (08/11/09, 12:13am)
Credits
List was made from scratch and I put a lot of work into it, so please give me credit; if you just copy/paste the List library directly into your map, I am happy. I just don't want you deleting the header comments that say I made it.
Example List Spell
So you still might be wondering how List could be useful for you. For that reason (and for fun), I made a Fire Wall spell. It has a main FireWall struct, that contains an IntegerList of all the Flame struct instances that make up the wall. List makes it easy to loop through all the flames to damage nearby units. List is also perfect to use here as the member of a struct. If you used an array to store the flames, you would limit how big of a wall you could make and/or how many FireWalls could be used at once. Since we use List, the only limit we need to worry about is how many Flame instances are on the map at one time, and your map would be doing something wrong if it ever had 8191 Flames burning at once. See the test map below for the spell code. You can just search for the parts that deal with the "flames" IntegerList.
Last edited:
.
indexOf and lastIndexOf still require loops.
