- Joined
- Aug 21, 2005
- Messages
- 3,699
Figured this might be useful to some...
Introduction
The Linked List is implemented as a doubly linked list.
Lists can only store 1 type of object. This type can be anything you want, if you run the right textmacro for it.
"List" is the listname.
"integer" is the datatype. Replace this with "string", "handle", etc.
"Node" is the name of the node. You won't be confronted with nodes, so you can choose any name you like, as long as it's unique
"Iterator" is the name of your listiterator. Read more on list iterators further
"ListInit" is the library initializer. You can choose any name you like, as long as it's unique.
Restrictions
Per "type" of list you can have a maximum of 8191 list instances, and you can only have 8191 objects in all lists of a type.
For instance: you can have 10 lists each storing 800 objects, but you can't have 10 lists each storing 900 objects. You can have 8191 lists with 1 object
List Methods
Example
Library
Note: it might have some bugs, I made some last minute changes but was too lazy to test...
Introduction
The Linked List is implemented as a doubly linked list.
Lists can only store 1 type of object. This type can be anything you want, if you run the right textmacro for it.
//! runtextmacro List__Make("List", "integer", "Node", "Iterator", "ListInit" )
"List" is the listname.
"integer" is the datatype. Replace this with "string", "handle", etc.
"Node" is the name of the node. You won't be confronted with nodes, so you can choose any name you like, as long as it's unique
"Iterator" is the name of your listiterator. Read more on list iterators further
"ListInit" is the library initializer. You can choose any name you like, as long as it's unique.
Restrictions
Per "type" of list you can have a maximum of 8191 list instances, and you can only have 8191 objects in all lists of a type.
For instance: you can have 10 lists each storing 800 objects, but you can't have 10 lists each storing 900 objects. You can have 8191 lists with 1 object
List Methods
JASS:
local List list = List.create() // Create a new list object.
call list.destroy() // Remove a list object.
call list.push_front(5) // Add the number "5" as first element of the list.
call list.pop_front() // Remove the first element of the list.
call list.push_back(6) // Add the number "6" as last element of the list.
call list.pop_back() // Remove the last element of the list.
call list.clear() // Clear the list, effectively removing all elements from the list
call list.insert(7, 2) // Add the number "7" at the 2nd position in the list (right after the first element) --- Return success
call list.delete(5) // Remove the first occurance of the number "5" from the list --- Return success
list.first // Return the first element of the list
list.last // Return the last element of the list
list.size // Return the size of the list
list.empty // Return true if the list is empty
list.begin // Set ListIterator to begin of list (see: ListIterator)
list.end // Set ListIterator to end of list (see: ListIterator)
local ListIterator iterator = ListIterator.create(list.begin)
// Create a new ListIterator, set it to the begin of the list
local ListIterator iterator = ListIterator.create(list.end)
// Create a new ListIterator, set it to the end of the list
call iterator.destroy() // Remove the iterator from memory
call iterator.inc() // Increase the iterator (set to next element in list)
call iterator.dec() // Decrease the iterator (set to previous element in list)
iterator.done // Return true if the iterator has completed a cycle and cannot continue iterating
iterator.obj // Return the object the iterator is at.
Example
JASS:
function TestIterator takes StringList strings returns nothing
local Iterator iterator = Iterator.create(strings.begin)
local string str
call BJDebugMsg(">> The size of the strings list is: " + I2S(strings.size))
loop
exitwhen iterator.done // Stop iterating over the list when the iterator is done
call BJDebugMsg(">> String: " + iterator.obj)
call iterator.inc()
endloop
call iterator.destroy()
endfunction
function TestList takes nothing returns nothing
local StringList strings = StringList.create()
call strings.push_back("Hi there!")
call strings.push_front("You're a noob")
call TestIterator(strings)
call strings.pop_front()
call strings.push_back("I'm Eleandor")
call strings.push_back("I made this container!")
call TestIterator(strings)
call strings.destroy()
endfunction
// The output of calling function TestList will be:
// >> The size of the strings list is: 2
// >> String: You're a noob
// >> String: Hi there!
// >> The size of the strings list is: 3
// >> String: Hi there!
// >> String: I'm Eleandor
// >> String: I made this container!
Library
JASS:
// LINKED LIST
// @author: Eleandor
// @version: 1.0
// @language: vjass
// @description: Linked List is implemented as a doubly linked list
//! textmacro List__Make takes list, type, node, iterator, initializer
library $list$ initializer $initializer$
private struct $node$
$type$ object
$node$ next
$node$ prev
static method create takes $type$ object returns $node$
local $node$ this = $node$.allocate()
set this.object = object
set this.prev = 0
set this.next = 0
return this
endmethod
endstruct
private function $initializer$ takes nothing returns nothing
local $node$ n = 0
set n.next = 0
set n.prev = 0
endfunction
struct $list$
private $node$ fFirst
private $node$ fLast
private integer fSize
static method create takes nothing returns $list$
local $list$ this = $list$.allocate()
set this.fFirst = 0
set this.fLast = 0
set this.fSize = 0
return this
endmethod
method operator first takes nothing returns $type$
return this.fFirst.object
endmethod
method operator last takes nothing returns $type$
return this.fLast.object
endmethod
method operator begin takes nothing returns $node$
return this.fFirst
endmethod
method operator end takes nothing returns $node$
return this.fLast
endmethod
method operator size takes nothing returns integer
return this.fSize
endmethod
method operator empty takes nothing returns boolean
return this.fSize == 0
endmethod
method push_front takes $type$ object returns nothing
local $node$ first = $node$.create(object)
if this.fFirst != 0 then
set first.next = this.fFirst
set this.fFirst.prev = first
else
set this.fLast = first
endif
set this.fFirst = first
set this.fSize = this.fSize + 1
endmethod
method pop_front takes nothing returns nothing
local $node$ first = this.fFirst
if this.fFirst != 0 then
set this.fFirst = first.next
if this.fFirst != 0 then
set this.fFirst.prev = 0
else
set this.fLast = 0
endif
set this.fSize = this.fSize - 1
call first.destroy()
endif
endmethod
method push_back takes $type$ object returns nothing
local $node$ last = $node$.create(object)
if this.fLast != 0 then
set this.fLast.next = last
set last.prev = this.fLast
else
set this.fFirst = last
endif
set this.fLast = last
set this.fSize = this.fSize + 1
endmethod
method pop_back takes nothing returns nothing
local $node$ last = this.fLast
if this.fLast != 0 then
set this.fLast = last.prev
if this.fLast != 0 then
set this.fLast.next = 0
else
set this.fFirst = 0
endif
set this.fSize = this.fSize - 1
call last.destroy()
endif
endmethod
method clear takes nothing returns nothing
local $node$ current = this.fFirst
local $node$ next
loop
exitwhen current == 0
set next = current.next
call current.destroy()
set current = next
endloop
endmethod
method insert takes $type$ object, integer position returns boolean
// insert element at position
local $node$ new
local $node$ prev = this.fFirst
local integer pos = 1
if position > this.fSize or position < 1 then
return false
elseif position == 1 then
call this.push_front(object)
return true
elseif position == this.fSize then
call this.push_back(object)
return true
endif
set new = $node$.create(object)
loop
exitwhen pos == position
set prev = prev.next
set pos = pos + 1
endloop
set prev.next.prev = new
set new.next = prev.next
set prev.next = new
set new.prev = prev
set this.fSize = this.fSize + 1
return true
endmethod
method delete takes $type$ object returns boolean
// delete first occurance of object
local $node$ target = this.fFirst
local $node$ prev = 0
local integer pos = 1
loop
exitwhen target.object == object
set prev = target
set target = target.next
set pos = pos + 1
if target == 0 then
return false
endif
endloop
if pos == 1 then
call this.pop_front()
elseif pos == this.fSize then
call this.pop_back()
else
set prev.next = target.next
set target.next.prev = prev
call target.destroy()
endif
return true
endmethod
method onDestroy takes nothing returns nothing
call this.clear()
endmethod
endstruct
struct $iterator$
$node$ current
static method create takes $node$ start returns $iterator$
local $iterator$ this = $iterator$.allocate()
set this.current = start
return this
endmethod
method inc takes nothing returns nothing
set this.current = this.current.next
endmethod
method dec takes nothing returns nothing
set this.current = this.current.prev
endmethod
method operator done takes nothing returns boolean
return this.current == 0
endmethod
method operator obj takes nothing returns $type$
return this.current.object
endmethod
endstruct
endlibrary
//! endtextmacro
//! runtextmacro List__Make("List", "integer", "Node", "Iterator", "ListInit" )
//! runtextmacro List__Make("HandleList", "handle", "HandleNode", "HandleIterator", "HandleListInit")
//! runtextmacro List__Make("StringList", "string", "StringNode", "StringIterator", "StringListInit" )
Note: it might have some bugs, I made some last minute changes but was too lazy to test...