• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Linked List Question

Status
Not open for further replies.
Level 15
Joined
Nov 30, 2007
Messages
1,202
Lets say I'm indexing shit 0, 1, 2, 4, 5 ... but when I reach a cap I want to keep the order intact but remove the first one added... How do I accomplish this with out reshuffling everything?

Some of you will say linked list. Yes. But I don't only need to loop from start to finish. I also need to have a function that allows me to print a string stored in list(X) [Xth position from "start"]. After stuff have been added and removed by the FIFO principle.

Basically I want the LIST to continue adding stuff even after OP LIMIT is reached by removing the first elements. But retaining the order and all that. Without having to reshuffle it every time...

---
- Store 5 strings in a struct. (5 is a arbitrary number for testing purposes)
- When you add a string they are stored in order, 0, 1 2, 3, 4, when you reach 5, [0] is removed and 5 is added to it's place.
- Must be able to loop from array [1] to array [0] in this above state in the order they were added. (1, 2, 3, 4, 5 "[0]")
- Must be able to retrieve the current index X from last added.
 
Last edited:

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,180
to continue adding stuff even after OP LIMIT is reached by removing the first elements
Not possible because once op limit is reached the thread crashes. (no further execution occurs). Of course if your data is persistent you could always start a new thread and continue processing the data however you should rather safely terminate threads than let the op limit do so since it can result in unpredictable state.

- Store 5 strings in a struct. (5 is a arbitrary number for testing purposes)
- When you add a string they are stored in order, 0, 1 2, 3, 4, when you reach 5, [0] is removed and 5 is added to it's place.
- Must be able to loop from array [1] to array [0] in this above state in the order they were added. (1, 2, 3, 4, 5 "[0]")
- Must be able to retrieve the current index X from last added.
What you want is a Circular Buffer, not a linked list (although one could be used to back the circular buffer but there is no need). These are quite easy to implement using the integer modulo operation (to do the wrapping around) as well as two variables to keep track of head and tail.
 
I still don't understand your question.

If you need to iterate and reorder/pop front etc. then a list is a good option. If you need random access, you can combine it with a hashtable (or if your self-imposed "cap" is small enough, then you can feel free to just loop until you hit that index).

Could you run through an extensive example? Maybe we can offer a more worthwhile solution.
 
Level 15
Joined
Nov 30, 2007
Messages
1,202
The idea was that the getString should adjuct for the new head position. So when head = X
and Index = 0 it should print the head (the head is the last added string). Also if i enter getString(CAPACITY-1) it should return the last string added. No matter if it is in array[0] or array [CAPACITY-1].

But instead my debug return the following msg: "a, b, c, "d, b, c, " and "e, c, d"
if it was working it would keep printing the messages in order: "a, b, c, " "b, c, d, " and "c, d, e, "


JASS:
scope Test initializer Init
    
    globals
        constant integer CAPACITY = 3
        CircularBuffer cb
    endglobals
    
    struct CircularBuffer
        private string array s[CAPACITY]
        private integer head = 0
        private integer tail = -1
        private boolean full = false
        
        static method create takes nothing returns CircularBuffer
            return .allocate()
        endmethod
        
        method add takes string str returns nothing
            set .tail = .tail + 1
            if .full then 
                set .head = .head + 1
            endif
            if .head >= CAPACITY then 
                set .head = 0
            endif
            if .tail >= CAPACITY then
                set .tail = 0
                if not .full then
                    set .head = 1
                    set .full = true
                endif
            endifa
            set .s[.tail] = str
        endmethod
        
        method getString takes integer index returns string
            local integer a = .head + index
            if a < CAPACITY then
                return .s[a]
            elseif index < CAPACITY then
                return .s[a - CAPACITY]
            endif
            return ""
        endmethod
    endstruct
    
    private function Main takes nothing returns nothing
        local integer i = 0
        local string s = ""
        call cb.add(GetEventPlayerChatString())
        // Prints the CircleBuffer from first to last.
        loop
            set s = s + cb.getString(i) + ", "
            set i = i + 1
            exitwhen i == CAPACITY
        endloop
        call BJDebugMsg(s)
    endfunction
    
    private function Init takes nothing returns nothing
        local trigger t = CreateTrigger()
        call TriggerRegisterPlayerChatEvent(t, Player(0), "", false )
        call TriggerAddAction(t, function Main)
        set cb = CircularBuffer.create()
        call cb.add("a")
        call cb.add("b")
        call BJDebugMsg(cb.getString(0))            // head or the first entry still stored. = a
        call BJDebugMsg(cb.getString(1))            // == b
        call BJDebugMsg(cb.getString(CAPACITY - 1)) // if filled this would be the last entry (tail). Otherwise it will return null
        call cb.add("c")
        call BJDebugMsg(cb.getString(CAPACITY - 1))
        call BJDebugMsg(cb.getString(CAPACITY))     // The return null as it is outside bounds.
    endfunction
endscope
 
Last edited:
Level 21
Joined
Mar 27, 2012
Messages
3,232
If you want it to work as a tight(no gaps) ordered list, then a linked list is not enough. You'll need a binary tree and you'll need to sort it.
With a binary tree you could technically allocate subsequent positions in an array and keep them ordered in a way that allows cheap random access.
Well, this is assuming that you want random removal as well.

If you only ever need to remove the first member, then you can just do some kind of circular solution where you keep track of what the first member is and how many there are.
Then for lookup you add FirstPosition to the array index that you want to look at. If the array index becomes greater than whatever your limit is, then you subtract the size of your array(8190, probably).
 
Level 15
Joined
Nov 30, 2007
Messages
1,202
but how do i write the getString method?

I did that Xonok, but it doesn't work as I had intended... if it worked it would always print the strings orderly from the example above. With the head in the first position of the loop and the tail in the last.

Found the bug. Updated the code above.
 
Last edited:
Status
Not open for further replies.
Top