Tries
#1
original:https://forums.alliedmods.net/showthread.php?t=201872

autor: guipatinador

traductor: roccoxx



Antes de empezar, este tutorial es para todo el mundo que no sabe cómo utilizar las Tries .Voy a suponer que usted sabe lo basico sobre pawn Sonrisa



Básicamente, las Tries permiten almacenar los datos asociados a una clave (string). Los datos por lo general son números enteros(integer) o un string.



Algunas consideraciones sobre este tutorial:

- No voy a hacer comparaciones entre tries y arrays (https://forums.alliedmods.net/showthread.php?t=88396) (esta en ingles)

- Todos los ejemplos son generalmente simples. Sólo voy a mostrar como usar las tries



Por lo tanto, para el primer ejemplo voy a demostrar cómo detectar si un jugador tiene un Steam ID en la lista negra(ban).



Código PHP:
#include < amxmodx >



new Trie:g_tAuthIdBlackList // g significa global; t significa trie



public plugin_init( )

{

    
register_plugin"trie example""1.0.1""guipatinador" )

    

    
g_tAuthIdBlackList TrieCreate( ) // Creamos la trie...

    

    
TrieSetCellg_tAuthIdBlackList"STEAM_2:3:123456")

    
TrieSetCellg_tAuthIdBlackList"STEAM_2:3:654321")

    
TrieSetCellg_tAuthIdBlackList"STEAM_2:3:123654")

    
TrieSetCellg_tAuthIdBlackList"STEAM_2:3:456123")

    

    
// primer parametro = nombre de la trie

    // segundo parametro = string con el Steam ID baneado (debe ser único)

    // Tercer parametro = es un integer(numero entero), no lo vamos a usar

}



public 
plugin_end( )

{

    
TrieDestroyg_tAuthIdBlackList // Destruimos la trie cuando cambiamos de map o se cae el sv :P

}



public 
client_putinserverid )

{

    new 
szAuthID32 ]; get_user_authididszAuthIDcharsmaxszAuthID ) )

    

    if( 
TrieKeyExistsg_tAuthIdBlackListszAuthID ) )

    {

        
// El Steam ID existe en la trie

        
server_cmd"kick #%i ^"Tu Steam ID esta baneado^""get_user_useridid ) )

    }

    

    else

    {

        
// El Steam ID no está en la trie

        // No vamos a hacer nada porque el Steam ID no esta baneado

    
}





Para el segundo ejemplo, vamos a asociar un Steam ID con un integer, y comprobamos/chekiamos si el jugador es un MOD, ADMIN, o VIP.



Código PHP:
#include < amxmodx >



new Trie:g_tAuthIdOfPeople



#define LOGFILE "steamidsofpeople.log"



// Sólo para ser más fácil ...

#define ADMIN 1

#define MOD 2

#define VIP 3



public plugin_init( )

{

    
register_plugin"trie example""1.0.2""guipatinador" )

    

    
g_tAuthIdOfPeople TrieCreate( )

    

    
TrieSetCellg_tAuthIdOfPeople"STEAM_2:3:123456"ADMIN // admin es 1

    
TrieSetCellg_tAuthIdOfPeople"STEAM_2:3:654321"ADMIN )

    
TrieSetCellg_tAuthIdOfPeople"STEAM_2:3:123654"MOD // mod es 2

    
TrieSetCellg_tAuthIdOfPeople"STEAM_2:3:456123"VIP // vip es 3

}



public 
plugin_end( )

{

    
TrieDestroyg_tAuthIdOfPeople )

}



public 
client_authorizedid )

{

    new 
szAuthID32 ]; get_user_authididszAuthIDcharsmaxszAuthID ) )

    

    new 
iNum

    

    
// esto almacena nuestro integer (ADMIN, MOD or VIP) en iNum, si el Steam ID está en la trie

    
if( TrieGetCellg_tAuthIdOfPeopleszAuthIDiNum ) )

    {

        switch( 
iNum )

        {

            case 
ADMIN:

                
log_to_fileLOGFILE"Un Admin entro en el server" )

            

            case 
MOD:

                
log_to_fileLOGFILE"Un Mod entro en el server" )

            

            case 
VIP:

                
log_to_fileLOGFILE"Un Vip entro en el server" )

        }

    }

    

    else 
// el Steam ID no esta en la trie

    
{

        
log_to_fileLOGFILE"Un user normal entro en el server" )

    }





Si entendemos esto, sabemos cómo trabajar con TrieCreate, TrieDestroy, TrieGetCell, TrieSetCell y TrieKeyExists Lengua.



Ahora vamos a trabajar con algunas natives más.Crab



En el tercer ejemplo, vamos a utilizar los comandos de administrador para bloquear algunos nicks(nombres).



Código PHP:
#include < amxmodx >

#include < amxmisc >



new Trie:g_tNicks



#define ADMIN_FLAG ADMIN_RCON



public plugin_init( )

{

    
register_plugin"trie example""1.0.3""guipatinador" )

    

    
register_concmd"amx_blocknick""BlockNickCmd"ADMIN_FLAG"<nombre a bloquear >" )

    
register_concmd"amx_unblocknick""UnBlockNickCmd"ADMIN_FLAG"<nombre a desbloquear>" )

    
register_concmd"amx_removenicks""RemoveNicksCmd"ADMIN_FLAG )

    

    
g_tNicks TrieCreate( )

}



public 
plugin_end( )

{

    
TrieDestroyg_tNicks )

}



public 
BlockNickCmdidlevelcid )

{

    if( !
cmd_accessidlevelcid) )

        return 
PLUGIN_HANDLED

    

    
new szName32 ]    

    
read_argv1szNamecharsmaxszName ) )

    

    
// Primero vamos a comprobar si el nombre de usuario está en el trie

    // Si está, no vamos a hacer nada

    // Si no está, vamos a añadir el nick.

    

    // Voy a mostrar dos métodos

    

    // método uno

    
if( TrieKeyExistsg_tNicksszName ) )

    {

        
client_printidprint_console"el Nombre de usuario ya se agrego antes" )    

    }

    

    else

    {

        
TrieSetCellg_tNicksszName)

        
client_printidprint_console"el Nombre de usuario se agrego con exito" // :P

    
}

    

    
/*

    // método dos

    

    new iNum

    new bool:bNameAlreadyAdded = TrieGetCell( g_tNicks, szName, iNum )

    

    if( bNameAlreadyAdded )

    {

        client_print( id, print_console, "el Nombre de usuario ya se agrego antes" )    

    }

    

    else

    {

        TrieSetCell( g_tNicks, szName, 1 )

        client_print( id, print_console, "el Nombre de usuario se agrego con exito" )

    }

    */

    

    
return PLUGIN_HANDLED

}



public 
UnBlockNickCmdidlevelcid )

{

    if( !
cmd_accessidlevelcid) )

        return 
PLUGIN_HANDLED

    

    
new szName32 ]    

    
read_argv1szNamecharsmaxszName ) )

    

    if( 
TrieDeleteKeyg_tNicksszName ) )

    {

        
client_printidprint_console"Nombre de usuario eliminado con exito" )

    }

    

    else

    {

        
client_printidprint_console"el Nombre de usuario ya se elimino antes" )

    }



    
/*

    // Si queremos borrar el nombre de usuario sin mostrar los fuckings prints hacemos esto:

    TrieDeleteKey( g_tNicks, szName )

    */

    

    
return PLUGIN_HANDLED

}



public 
RemoveNicksCmdidlevelcid )

{

    if( !
cmd_accessidlevelcid) )

        return 
PLUGIN_HANDLED

    

    TrieClear
g_tNicks // Ésto borra todos los nicks de la trie y los datos

    
client_printidprint_console"todos los nicks bloqueados  fueron eliminados" )

    

    return 
PLUGIN_HANDLED

}



public 
client_putinserverid )

{

    new 
szName32 ]; get_user_nameidszNamecharsmaxszName ) )

    

    if( 
TrieKeyExistsg_tNicksszName ) )

    {

        
server_cmd"kick #%i ^"Tu nick esta bloqueado^""get_user_useridid ) )

    }

    

    
/*

    // Tenga en cuenta que esto también funciona

    new iNum

    if( TrieGetCell( g_tNicks, szName, iNum ) )

    {

        server_cmd( "kick #%i ^"Tu nick esta bloqueado^"", get_user_userid( id ) )

    }

    */





Para el TrieGetString y TrieSetString vamos a asociar algunas fechas VIP a los Steam IDs.

Código PHP:
#include < amxmodx >

#include < amxmisc >



new Trie:g_tVipDate



new const VIPDATE[ ][ ][ ] = {

    { 
"STEAM_2:3:123456""01-04-2013" },

    { 
"STEAM_2:3:654321""25-02-2013" },

    { 
"STEAM_2:3:123654""13-03-2013" },

    { 
"STEAM_2:3:456123""09-01-2013" }

}



public 
plugin_init( )

{

    
register_plugin"trie example""1.0.4""guipatinador" )

    

    
register_clcmd"say /vipdate""VipDate" )

    

    
g_tVipDate TrieCreate( )

    

    new 
i

    
for( 0sizeof VIPDATEi++ )

    {

        
TrieSetStringg_tVipDateVIPDATE][ ], VIPDATE][ ] )

        
// primer parametro = nombre de la trie

        // segundo parametro = Steam ID

        // Tercer parametro = fecha cuando el vip termina (string)

    
}

}



public 
plugin_end( )

{

    
TrieDestroyg_tVipDate )

}



public 
VipDateid )

{

    new 
szAuthID32 ]; get_user_authididszAuthIDcharsmaxszAuthID ) )

    

    
// Primero vamos a comprobar si el Steam ID del jugador está en la trie

    
new szVipDate12 ]

    if( 
TrieGetStringg_tVipDateszAuthIDszVipDatecharsmaxszVipDate ) ) )

    {

        
// El usuario es vip porque el Steam ID esta en la trie

        
client_printidprint_chat"Tu privilegio VIP vence el: %s"szVipDate )

    }

    

    else

    {

        
// el pibe no es vip

        
client_printidprint_chat"Vos no sos VIP" )

    }





Y por último ... vamos a trabajar con TrieSetArray y TrieGetArray.

Este plugin lee las estadísticas de un archivo y lo guarda por Steam ID.



Código PHP:
#include < amxmodx >

#include < amxmisc >



new Trie:g_StatsOfPlayers



new g_szAuthID33 ][ 35 // Esto guarda el Steam ID of de cualquier jugador



enum _:Stats {

    
SteamID32 ],

    
Kills,

    
Deaths,

    
KillsKnife,

    
KillsHE

}

//Estas son las estadísticas que deseamos guardar. Tengamos en cuenta que el Steam ID es un string, el resto son números enteros(integers)



public plugin_init( )

{

    
register_plugin"trie example""1.0.5""guipatinador" )

    

    
register_clcmd"say /mystats""PrintStats" // Vamos a utilizar este comando para ver las estadísticas :P

    

    
g_StatsOfPlayers TrieCreate( )

    
ReadStatsFromFile( ) // Lee las estadísticas del archivo cuando se inicia el sv o se cambia de map  

}



public 
plugin_end( )

{

    
TrieDestroyg_StatsOfPlayers )

}



public 
ReadStatsFromFile( )

{

    new 
szFilePath128 ]

    
get_configsdirszFilePathcharsmaxszFilePath ) )

    
addszFilePathcharsmaxszFilePath ), "/stats_of_players.ini" // Archivo donde se guardan las estadísticas

    

    
new fopenszFilePath"rt" )

    

    if( !
)

    {

        new 
szMessage256 ]

        
formatexszMessagecharsmaxszMessage ), "No se puede abrir: %s"szFilePath )

        
set_fail_stateszMessage )

    }

    

    new 
szDataFromFile128 ]

    new 
DataStats ]

    new 
szKills]

    new 
szDeaths]

    new 
szKnife]

    new 
szHE]

    

    while( !
feof) ) // Abrimos el archivo

    
{

        
fgetsfszDataFromFilecharsmaxszDataFromFile ) )

        

        if( !
szDataFromFile] || szDataFromFile] == ';' || szDataFromFile] == '/' && szDataFromFile] == '/' )

            continue

        

        
trimszDataFromFile )

        
parseszDataFromFile,

        
DataSteamID ], charsmaxDataSteamID ] )

        
szKillscharsmaxszKills ),

        
szDeathscharsmaxszDeaths ),

        
szKnifecharsmaxszKnife ),

        
szHEcharsmaxszHE ) )

        

        
// Todas esas cosas son strings. Las Vamos a convertir en integers

        
DataKills ] = str_to_numszKills )

        
DataDeaths ] = str_to_numszDeaths )

        
DataKillsKnife ] = str_to_numszKnife )

        
DataKillsHE ] = str_to_numszHE )

        

        
// Esto guarda el Steam ID y las estadísticas en la trie

        
TrieSetArrayg_StatsOfPlayersDataSteamID ], Datasizeof Data )

        
// primer parametro = nombre de la trie

        // segundo parametro = string ( en este caso el Steam ID)

        // Tercer parametro = array que contiene las estadísticas

        // Cuarto parametro = tamaño del array (usar que 'sizeof Data - 1' no funciona)

    
}

    

    
fclose// Cierra el archivo

}



public 
client_authorizedid )

{

    
get_user_authididg_szAuthIDid ], charsmaxg_szAuthID[ ] ) )

}



public 
PrintStatsid )

{

    new 
DataStats ]

    

    if( 
TrieGetArrayg_StatsOfPlayersg_szAuthIDid ], Datasizeof Data ) )

    {

        
// Los parametros son iguales a TrieSetString

        // primero = nombre del array

        // segundo = g_szAuthID[ id ] contiene el Steam ID del jugador que tipea(escribe) /mystats

        // tercero = array para recuperar los datos

        // cuarto = tamaño

        

        
client_printidprint_chat"Steam ID: %s | Kills: %i | Deaths: %i | Knife: %i | HE: %i"DataSteamID ], DataKills ], DataDeaths ], DataKillsKnife ], DataKillsHE ] )

    }

    

    
//  Si el ID de Steam no existe en el archivo:

    
else

    {

        
client_printidprint_chat"Tu Steam ID no tiene estadisticas guardadas" )

    }





Eso es todo chicas.



*Nota: google traductor traducía cualquier chota o las cosas por la mitad (casi siempre) y bueno tuve que poner aun mas de voluntad para ver que quede bien y se entienda y traducir yo tmb Sonrisa.



me fui a dormir bye
Responder
#2
Vale destacar que una de las utilidades de los tries son usados para evitar la creación de variables con una cantidad de celdas exageradas.

Por ejemplo:

Código PHP:
new gArray[50

Ni te molestes en enviarme un mensaje privado para pedirme ayuda porque NO lo voy a contestar.
Gracias por su atención.
Responder
#3
(08/10/2013, 02:13 PM)alan_el_more escribió: Vale destacar que una de las utilidades de los tries son usados para evitar la creación de variables con una cantidad de celdas exageradas.

Por ejemplo:

Código PHP:
new gArray[50

Mmm no estoy de acuerdo, por qué evitaría crear celdas?
Responder
#4
Los tries básicamente son arrays con celdas dinamicas.

Es preferible crear un trie que se adapta a los datos ingresados que crear un array con demasiadas celdas para no quedarse corto.



Espero ser claro y que se entienda lo que quiero decir.

Ni te molestes en enviarme un mensaje privado para pedirme ayuda porque NO lo voy a contestar.
Gracias por su atención.
Responder
#5
(08/10/2013, 02:30 PM)alan_el_more escribió: Los tries básicamente son arrays con celdas dinamicas.

Es preferible crear un trie que se adapta a los datos ingresados que crear un array con demasiadas celdas para no quedarse corto.



Espero ser claro y que se entienda lo que quiero decir.

Entiendo la función de las tries, pero a mi entender no tiene nada que ver con la cantidad de celdas. La única diferencia con los arrays es que permite usar cadenas como claves... y eso te abre un abanico de posibilidades a la hora de programar...
Responder
#6
(08/10/2013, 02:37 PM)Neeeeeeeeeel.- escribió:
(08/10/2013, 02:30 PM)alan_el_more escribió: Los tries básicamente son arrays con celdas dinamicas.

Es preferible crear un trie que se adapta a los datos ingresados que crear un array con demasiadas celdas para no quedarse corto.



Espero ser claro y que se entienda lo que quiero decir.

Entiendo la función de las tries, pero a mi entender no tiene nada que ver con la cantidad de celdas. La única diferencia con los arrays es que permite usar cadenas como claves... y eso te abre un abanico de posibilidades a la hora de programar...



Tenes razón, retiro lo dicho

Ni te molestes en enviarme un mensaje privado para pedirme ayuda porque NO lo voy a contestar.
Gracias por su atención.
Responder
#7
Un trie es una estructura de Arbol que posee dos caminos (Izquierda y Derecha) por el cual recorre los datos. No es una estructura lineal a menos que todos los elementos se encuentren a la izquierda o todos a la derecha. No puede ser comparado con un array, lo más cercano sería un Heap Gran sonrisa

Y uno de sus pro por el cual se puede usar Strings como claves es por el método de búsqueda que tiene.

#Roccoxx
Si es una traducción por lo visto. Eres capaz de darle soporte si a alguien el surge alguna duda?
Búsqueda de la ecuación perfecta.
Responder
#8
Si gladius, aunque siempre hay alguno que sabe y me gana de mano o responde de mejor forma.
Responder
#9
nunca me interesaron mucho las tries...



entonces mejor tries que arrays, cierto?
(17/04/2015, 03:36 PM)Neeeeeeeeeel.- escribió: No se va a volver a conectar a internet en toda su puta vida... nadie sube porno a mi foro y vive para contarlo.
Responder
#10
(10/10/2013, 05:12 PM)RauliTop escribió: nunca me interesaron mucho las tries...



entonces mejor tries que arrays, cierto?



No, depende de tus necesidades.
Búsqueda de la ecuación perfecta.
Responder
#11
(10/10/2013, 05:12 PM)RauliTop escribió: nunca me interesaron mucho las tries...



entonces mejor tries que arrays, cierto?

Trie = claves con cadenas de caracteres + distintos algoritmos de inserción y búsqueda a los arrays

Arrays = claves con números
Responder
#12
un array también puede ser carácteres
(17/04/2015, 03:36 PM)Neeeeeeeeeel.- escribió: No se va a volver a conectar a internet en toda su puta vida... nadie sube porno a mi foro y vive para contarlo.
Responder
#13
(10/10/2013, 06:14 PM)RauliTop escribió: un array también puede ser carácteres
Las claves de los arrays son numéricas únicamente.
Responder
#14
Te referis a que una clave de una trie puede ser un texto (string) y que los arrays solo números?



Por ejemplo, lo siguiente no se podría hacer con arrays:



Código PHP:
#define CLAVE_TRIE "Soy una clave"

TrieSetCell(g_tTrieCLAVE_TRIE123

Ni te molestes en enviarme un mensaje privado para pedirme ayuda porque NO lo voy a contestar.
Gracias por su atención.
Responder
#15
Exacto.
Responder
#16
La clave en sí no es un string es solo 1 caracter.

Se le dice "clave" erroneamente en el sentido que no lee el string de una, si no que va leyendo clave por clave (carácter por carácter) hasta formar la palabra (Realiza una combinación de claves), luego de encontrar la palabra pregunta ese último carácter si es el final de la "clave que nosotros pusimos".

Hice algo básico en C/C++ para que entiendan como funciona un Trie internamente. No sé si es tal cual el del amx, claro que es muy básico y se puede adaptar a cualquier tipo de dato. El código en sí en "claves" almacena números.

Código PHP:
#include <iostream>
using namespace std;

#define MaxClaves 128 // ASCII

class Node
{
    private:
        
int datofinal;
        
Nodeclaves[MaxClaves];
        
bool clavefinal;

    public:
        
Node()
        {
            
clavefinal false;

            for(
int i 0;MaxClaves;++i)
            {
                
claves[i] = NULL;
            }
        }
        ~
Node()
        {
            for(
int i 0;MaxClaves;++i)
            {
                if(
claves[i])
                {
                    
delete claves[i];
                }
            }
        }
        
NodegetClave(char c)
        {
            return 
claves[c];
        }
        
void setClave(Node *clavechar c)
        {
            
claves[c] = clave;
        }
        
bool getFinal()
        {
            return 
clavefinal;
        }
        
void setFinal(bool final, int dato)
        {
            
clavefinal = final;
            
datofinal dato;
        }
        
int getDato()
        {
            return 
datofinal;
        }
        
void setDato(int dato)
        {
            
datofinal dato;
        }
};

class 
Trie
{
    private:
        
Noderoot;

    public:
        
Trie()
        {
            
root = new Node();
        }
        ~
Trie()
        {
            
delete root;
        }
        
void add(string claveint dato)
        {
            
Node *curr root;
            for(
int i 0clave.size(); i++)
            {
                
charclave[i];
                if(!
curr->getClave(c))
                {
                    
curr->setClave(new Node(), c);
                }
                
curr curr->getClave(c);
            }
            
curr->setFinal(truedato);
        }
        
Node *search(string clave)
        {
            
Nodecurr root;
            for(
int i 0clave.size(); i++)
            {
                
charclave[i];
                if(!
curr->getClave(c))
                {
                    return 
NULL;
                }
                
curr curr->getClave(c);
            }
            if(
curr->getFinal())
            {
                return 
curr;
            }
            else
            {
                return 
NULL;
            }
        }
        
void cambiar(string claveint newdato)
        {
            
Nodecurr root;
            for(
int i 0clave.size(); i++)
            {
                
charclave[i];
                if(!
curr->getClave(c))
                {
                    return;
                }
                
curr curr->getClave(c);
            }
            if(
curr->getFinal())
            {
                
curr->setDato(newdato);
            }
        }
};

main()
{
    
Trie trie;
    
Node *buscar;

    
trie.add("Hola1000"999);
    
buscar trie.search("Hola25");
    if(
buscar)
    {
        
cout << "1. "<< buscar->getDato() << endl;
    }

    
trie.add("Hola0"25);
    
trie.add("Ho!!la3*00"3);

    
buscar trie.search("Hola0");
    if(
buscar)
    {
        
cout << "2. "<< buscar->getDato() << endl;
    }

    
buscar trie.search("Ho!!la3*00");
    if(
buscar)
    {
        
cout << "3. "<< buscar->getDato() << endl;
    }

    
buscar trie.search("Hola0");
    if(
buscar)
    {
        
trie.cambiar("Holaasd0", -9999);
        
cout << "4. "<< buscar->getDato() << endl;
    }


Fíjense bien en la class Trie.
Búsqueda de la ecuación perfecta.
Responder
#17
gladius de donde aprendiste C++?
Responder
#18
Aprendí después de Pawn y fue porque estaba buscando nuevos métodos para mejorar mis códigos en los plugins y ahí encontré C y luego C++.
Búsqueda de la ecuación perfecta.
Responder
#19
si pero de alguna pagina?
Responder
#20
No, google y listo jajaja, de todas maneras yo no soy de leer mucho soy más de ir a lo práctico en Pawn nunca he leído una guía de como hacer algo me oriento con ciertas cosas pero no leo guías es raro. Y en C me pasa algo similar a veces cuando estoy aprendiendo cosas nuevas leo un par de líneas o pseucódigos de tutoriales y listo.
Búsqueda de la ecuación perfecta.
Responder
#21
Una pregunta, para el primer ejemplo solo se puede guardar steamid ? osea solo se puede guardar un dato? si quiero guardar el nombre y el steam ?
Responder
#22
guiate por el ejemplo de los vips y la fecha de vencimiento o el de las estadísticas creo que es el ultimo que puse.
Ingeniero agrónomo y desarrollador de Software.

tutoriales-allied
buscas un zp?

"La imitación es la forma más sincera de admiración con la que puede pagar la mediocridad a la grandeza"

Merci Alliedmodders pour m'introduire dans la programmation.
Responder


Salto de foro:


Usuarios navegando en este tema: 1 invitado(s)