Raised This Month: $51 Target: $400
 12% 

[INC] CellTravTrie


Post New Thread Reply   
 
Thread Tools Display Modes
Author Message
Hawk552
AMX Mod X Moderator
Join Date: Aug 2005
Old 07-24-2008 , 08:28   [INC] CellTravTrie
Reply With Quote #1

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.
Attached Files
File Type: inc celltravtrie.inc (9.1 KB, 1069 views)
__________________

Last edited by Hawk552; 08-16-2009 at 19:53.
Hawk552 is offline
Send a message via AIM to Hawk552
joaquimandrade
Veteran Member
Join Date: Dec 2008
Location: Portugal
Old 03-16-2009 , 22:55   Re: [INC] CellTravTrie
Reply With Quote #2

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(triekeyval) )
    {
        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(triekeyval) )
    {
        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(== endhandle->lower_bound(start);
if(
== endhandle->upper_bound(start);
if(
== end) return 0;
else 
len--; 
It should be:

PHP Code:
if(== end
{
    
handle->lower_bound(start)
        
    if(
== end)
        
handle->upper_bound(start);
}

if(
== 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
__________________

Last edited by joaquimandrade; 03-16-2009 at 23:32.
joaquimandrade is offline
Hawk552
AMX Mod X Moderator
Join Date: Aug 2005
Old 03-16-2009 , 23:25   Re: [INC] CellTravTrie
Reply With Quote #3

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.
__________________
Hawk552 is offline
Send a message via AIM to Hawk552
joaquimandrade
Veteran Member
Join Date: Dec 2008
Location: Portugal
Old 03-16-2009 , 23:36   Re: [INC] CellTravTrie
Reply With Quote #4

Quote:
Originally Posted by Hawk552 View Post
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.
__________________

Last edited by joaquimandrade; 03-17-2009 at 01:09.
joaquimandrade is offline
Hawk552
AMX Mod X Moderator
Join Date: Aug 2005
Old 03-16-2009 , 23:45   Re: [INC] CellTravTrie
Reply With Quote #5

I never tested it because I assumed that Suzuka knew what it was doing. You're probably right, though.
__________________
Hawk552 is offline
Send a message via AIM to Hawk552
joaquimandrade
Veteran Member
Join Date: Dec 2008
Location: Portugal
Old 03-16-2009 , 23:50   Re: [INC] CellTravTrie
Reply With Quote #6

Quote:
Originally Posted by Hawk552 View Post
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?
__________________
joaquimandrade is offline
Hawk552
AMX Mod X Moderator
Join Date: Aug 2005
Old 03-16-2009 , 23:52   Re: [INC] CellTravTrie
Reply With Quote #7

It allows you to traverse a trie. Without this header, you can't traverse it.
__________________
Hawk552 is offline
Send a message via AIM to Hawk552
joaquimandrade
Veteran Member
Join Date: Dec 2008
Location: Portugal
Old 03-16-2009 , 23:57   Re: [INC] CellTravTrie
Reply With Quote #8

Quote:
Originally Posted by Hawk552 View Post
It allows you to traverse a trie. Without this header, you can't traverse it.
Ok. Thanks. Sorry for bothering.
__________________
joaquimandrade is offline
luxor
Member
Join Date: Jan 2014
Old 06-10-2016 , 11:16   Re: [INC] CellTravTrie
Reply With Quote #9

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));
}

Last edited by luxor; 06-10-2016 at 14:24.
luxor is offline
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 01:24.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode