Linked List

[Eleandor]

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.
//! 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

List methods

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

Example

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

Linked List Library

// 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...

 

[Dynasti]

This can be used for what?

 

[Akolyt0r]

Would be interresting which system is faster ....yours or Ammorth's ...
blah i hate to read textmacroized code ....so i wont :/

Good thing about this one is, that you can have LinkedLists for other types than integer aswell ...
However most of the time integer should be sufficient ...but well its a bonus.

This can be used for what?

this is a generic system .. linked lists can be used for pretty many things ...
e.g. spells ...or other systems ...

Most of the time linked lists might be slower than other implementations, but there are some cases in which, linked lists make the code faster and/or much cleaner ..

 

[Element of Water]

How would you use them in hash tables to avoid value collision? That's what I want to know...

 

[Eleandor]

Normally, this is how your hashtable works (more or less):

Your object has (example):
handle your_handle // the handle you wish to store (or anything you wish to store)
integer key

Your object is stored at:
set Table[hash(key)] = your_handle
with hash a function that takes an integer and returns an integer. The hashing function.
In other words: your table is a handle array.

To avoid collision with separate chaining (linked lists), you don't have a handle array table, but you have:
List array Table
The table is not an array of handles, but an array of Lists. Those lists, in turn, will contain your handles.

To initialize your table, you do:
for each array index i in Table, do:
set Table = List.create()

To add elements to your table, you do:
local List tmp = Table[hash(element)]
call tmp.push_back(element)

To remove or retrieve elements from your table, you do:
local List tmp = Table[hash(element)]
local ListIterator iterator = ListIterator.create(tmp.begin)
loop
---exitwhen iterator.done
---if iterator.obj == element then
------ remove or return element
---endif
---iterator.inc()
endloop

Something more sofisticated than that should work

 

[Element of Water]

Ah ok, thanks!