[STL] adt_* (travtrie, deque, queue, stack)

Twilight Suzuka · **Author**

A few useful stocks until official versions are added. These follow the same format as adt_array and adt_trie (even when I dislike it) just to maintain compatibility.

Deque:
Meets all deque requirements for speed, at the sacrifice of space
Space grows linearly, but quicker than it could
Worst case for space is queue (unfortunately)

Queue:
Based on deque (soon to be based on circular buffer)
Meets all queue requirements for speed

Stack:
Based on adt_array
Meets all stack requirements for speed

TravTrie:
Based on adt_trie and adt_array
Retrieve has no slow down
insert has O(1) slow down
delete has O(logn) or O(n) slow down
constant iteration provided through Plugin Iterator like mechanism
iteration occurs in O(n) unsorted, O(nlogn) sorted

TravTrie Tripups:
1. Getting the string key (not the value) will not increment the iterator
2. A function is provided to sort the travtrie if wanted

Note: These functions have been compile tested and moderately runtime tested, but not stress tested (except for queue and travtrie). Tell me if an error occurs.
Please tell me how if you like it!

Nican · 03-23-2008 , 11:58 Re: [STL] adt_* (travtrie, deque, queue, stack)

Good job.

Could you show some examples?

sfPlayer · *Last edited by sfPlayer; 03-23-2008 at 15:03.*

(partial) adt_queue implementation based upon my C++ implementation

The SourceMod version is 150-200 times slower than the C++ one (benchmark: (push_back 2k, pop_front 1k, push_back 1k, pop_front 2k)*1k).

Twilight Suzuka · 03-23-2008 , 23:46 Re: [STL] adt_* (travtrie, deque, queue, stack)

Got any comparisons of mine and yours? I assume yours will beat mine, but my circular buffer one should beat both.

sfPlayer · *Last edited by sfPlayer; 03-24-2008 at 11:15.*

yours "crashes"

Code:

L 03/24/2008 - 16:08:24: [SM] Native "SetArrayCell" reported: Invalid index 4224 (count: 1280)
L 03/24/2008 - 16:08:24: [SM] Displaying call stack trace for plugin "adt_queue_test.smx":
L 03/24/2008 - 16:08:24: [SM]   [0]  Line 358, adt_deque.inc::PushBackDequeCell()
L 03/24/2008 - 16:08:24: [SM]   [1]  Line 18, adt_queue.inc::PushQueueCell()

The performance is primarily limited by the very poor performance of adt_array/datapacks as a replacement for object members / a struct on the heap

sfPlayer · 03-24-2008 , 11:12 Re: [STL] adt_* (travtrie, deque, queue, stack)

benchmark:

Code:

public OnPluginStart() {
    new Handle:queue = CreateQueue();
    new Float:startTime = GetEngineTime();
    for (new j=0; j<1000; j++) {
        for (new i=0; i<2000; i++) {
            PushQueueCell(queue, 123);
        }
        for (new i=0; i<1000; i++) {
            new test = FrontQueueCell(queue);
            if (test != 123) {
                PrintToServer("error at %d", GetQueueSize(queue));
                break;
            }
            PopQueue(queue);
        }
        for (new i=0; i<1000; i++) {
            PushQueueCell(queue, 123);
        }
        for (new i=0; i<2000; i++) {
            new test = FrontQueueCell(queue);
            if (test != 123) {
                PrintToServer("error at %d", GetQueueSize(queue));
                break;
            }
            PopQueue(queue);
        }
    }
    PrintToServer("queue test ok");
    PrintToServer("time: %fs", GetEngineTime()-startTime);
}

Twilight Suzuka · 03-24-2008 , 20:03 Re: [STL] adt_* (travtrie, deque, queue, stack)

sweet googly moogly! Have to look into that.

The cost of the native overhead to just access the members in our fake structs is rather high. Wonder if I could pack the members somehow...