AlliedModders - [INC] CellTravTrie

AlliedModders (https://forums.alliedmods.net/index.php)

- Code Snippets/Tutorials (https://forums.alliedmods.net/forumdisplay.php?f=83)

- - [INC] CellTravTrie (https://forums.alliedmods.net/showthread.php?t=74753)

[INC] CellTravTrie

This is a set of stocks me and Twilight_Suzuka (but mostly her) wrote in order to reproduce the functionality of ArrayX using core AMXX functions. It requires CellTrie (included in AMXX 1.8.0 r3711) and CellArray (included in AMXX 1.8.0).

Here is an example plugin that I used to test it:

Code:

 #include <amxmodx>
#include <amxmisc>
#include <celltravtrie>

public plugin_init()
{
    register_plugin("TravTrie Test","1.0","Hawk552")
    
    new TravTrie:CurTrie = TravTrieCreate(),Temp,Results[4]
    server_print("TravTrie: %d",CurTrie)
    
    TravTrieSetCellEx(CurTrie,0,99)
    Results[0] = TravTrieGetCellEx(CurTrie,0,Temp)
    
    TravTrieSetCellEx(CurTrie,1,3)
    TravTrieSetStringEx(CurTrie,2,"ham")
    
    new Cell,String[33],Non
    Results[1] = TravTrieGetCellEx(CurTrie,1,Cell)
    Results[2] = TravTrieGetStringEx(CurTrie,2,String,32)
    Results[3] = TravTrieGetCellEx(CurTrie,31,Non)
    server_print("Cell: %d / Temp: %d / String: %s / Non: %d / Results: %d %d %d %d",Cell,Temp,String,Non,Results[0],Results[1],Results[2],Results[3])
    
    new travTrieIter:Iter = GetTravTrieIterator(CurTrie),Value
    while(MoreTravTrie(Iter))
    {
        ReadTravTrieCell(Iter,Value)
        server_print("Value: %d",Value)
    }
    DestroyTravTrieIterator(Iter)
    
    TravTrieNth(CurTrie,1,String,32)
    TravTrieGetCell(CurTrie,String,Cell)
    
    server_print("Nth: %d",Cell)
}

A couple of notes:

This isn't a perfect replacement for ArrayX. It's designed to act as a keytable (it's a trie, after all) and the stocks I added to allow you to pass a cell as the key are much slower than the ArrayX equivalents.
TrieSetArray and TrieGetArray are broken and, as such, the stocks added basically mirror the functionality of TrieSetString/TrieGetString.

Some things you should know about tries:

Insertion (adding data) is relatively slow, but retrieving it is extremely fast.
I've had problems using this as a heterogeneous container (i.e. containing more than one data type in a single trie), so you should avoid it.

Have fun.

Re: [INC] CellTravTrie

Why do you have checks to see if the strings begin with the newline character? Won't you meant the null character?

Other thing: there is a recurrent "problem" in her coding (it also happens in ArrayX):

This:

PHP Code:


		
			
stock bool:TravTrieSetCell(TravTrie:trie, const key[], any:value)
{
    if(key[0] == '^n') return false;
    
    new any:val;
    if(!TravTrieGetCell(trie, key, val) )
    {
        new Array:iter;
        if(!TrieGetCell(Trie:trie,"",any:iter)) return false;
    
        ArrayPushString(Array:iter,key);
    }
    if(key[0] == '^n') return false;
    
    TrieSetCell(Trie:trie,key,value);
    return true;
}

should be:

PHP Code:


		
			
stock bool:TravTrieSetCell(TravTrie:trie, const key[], any:value)
{
    if(key[0] == '^n') return false;
    
    new any:val;
    if(!TravTrieGetCell(trie, key, val) )
    {
        new Array:iter;
        if(!TrieGetCell(Trie:trie,"",any:iter)) return false;
    
        ArrayPushString(Array:iter,key);

        if(key[0] == '^n') return false;
    }
    
    TrieSetCell(Trie:trie,key,value);
    return true;
}

In keytable_natives.cpp she has

PHP Code:


		
			
if(a == end) a = handle->lower_bound(start);
if(a == end) a = handle->upper_bound(start);
if(a == end) return 0;
else len--;

It should be:

PHP Code:


		
			
if(a == end) 
{
    a = handle->lower_bound(start)
        
    if(a == end)
        a = handle->upper_bound(start);
}

if(a == end)
    return 0
else
    len--

Not that it matter that much to performance but i thought that she has extremely rigorous at coding. It seems that she prefers to compact the code instead of making it more accurate

Re: [INC] CellTravTrie

I don't think it can store a "^n" as the key. Also, you're right about the problem. It's a trivial optimization, though.

Re: [INC] CellTravTrie

Quote:

Originally Posted by Hawk552 (Post 782454)

I don't think it can store a "^n" as the key. Also, you're right about the problem. It's a trivial optimization, though.

I don't believe in that. The character '^n' is, for the programming language, the same as any other, except the 0. And, the code just checks if it starts by '^n' so, it can have ^n's thereafter. So, i think it was meant to be a 0.

Re: [INC] CellTravTrie

I never tested it because I assumed that Suzuka knew what it was doing. You're probably right, though.

Re: [INC] CellTravTrie

Quote:

Originally Posted by Hawk552 (Post 782464)

I never tested it because I assumed that Suzuka knew what it was doing. You're probably right, though.

Please enlight me over this:

What does this include makes you able to do, that you can't do without it?

Re: [INC] CellTravTrie

It allows you to traverse a trie. Without this header, you can't traverse it.

Re: [INC] CellTravTrie

Quote:

Originally Posted by Hawk552 (Post 782472)

It allows you to traverse a trie. Without this header, you can't traverse it.

Ok. Thanks. Sorry for bothering.

Re: [INC] CellTravTrie

TravTrieClear() is broken, if you use it on your travtrie you lose you object.

Here is a fix :

Code:

stock TravTrieClear(TravTrie:trie, keylength = 64, startsize = 32)

{

        new Array:iter;

        if(!TrieGetCell(Trie:trie,"",any:iter)) { TrieClear(Trie:trie); return; }



        ArrayDestroy(iter);

        TrieClear(Trie:trie);

        TrieSetCell(Trie:trie, "", _:ArrayCreate(keylength, startsize));

}