UserList - lato C++
Implementare il codice C++ di supporto alla gestione di una userList dinamica è un obiettivo complesso.
Quanto segue è riferito al codice, non ancora raffinato, collocato nel branch dinamicUserList e, in particolare, nei file AutoCompletion.h, | AutoCompletion.cpp e Main.qml.
Quest'ultimo, in particolare, è ad un punto di sviluppo del tutto primordiale, utile solamente a verificare la funzionalità dell'algoritmo lato C++.
Passo 1: adeguare la struttura del trie
Il primo aspetto da sottolineare è la necessità di mettere in interazione due strutture di dati indipendenti.
La grafica delle userList, infatti, è gestita, in Qt, da un vettore lineare chiamato QList. Ciascun elemento della QList è un puntatore a una classe USER, che contiene le informazioni essenziali proprie dell'utente (username, realname, uid, gid e via dicendo), corrispondente a un parsing del comando getpwent.
La ricerca per il completamento, invece, si sviluppa intorno ad un albero trie, essenziale per la gestione dell'algoritmo.
Gli elementi di un trie sono foglie, contenenti una lettera, due puntatori e un marcatore per la gestione delle ricerche in profondità (dfs).
typedef struct letter {
char character;
int mark { 0 };
letter* right { NULL };
letter* down { NULL };
} letter;
Per gestire gli effetti grafici, dopo ogni ricerca condotta lungo l'albero trie, è necessario individuare la classe USER corrispondente all'utente corrente. Procedere linearmente significherebbe vanificare del tutto (!!!) il vantaggio di avere usato il trie.
Cosa possiamo fare?
Forse, una buona soluzione può essere quella di rendere disponibile, alla fine di ogni ricerca lungo il trie, un campo contenente il puntatore alla classe USER corrispondente. Tecnicamente, questo si realizza modificando la foglia nel modo seguente:
typedef struct letter {
char character;
int mark { 0 };
letter* right { NULL };
letter* down { NULL };
UserPtr user { nullptr };
} letter;
Cosa è cambiato?
Per ogni singola lettera, viene inserito un campo specifico per un puntatore a un elemento della QList degli utenti.
Normalmente, si tratta di un puntatore vuoto, ma le ultime lettere di ogni parola verranno aggiornate con un collegamento esplicito all'elemento corrispondente della QList.
Passo 2: inizializzare la QList degli utenti
L'inizializzazione dei dati è gestita, nella versione attuale, dal metodo initAutoCompletion, che si sviluppa in tre passi successivi:
- creazione di un nuovo puntatore ad un albero trie.
- ciclo ricorsivo di lettura degli utenti con:
- popolamento del trie;
- costruzione della QList, tramite una ricerca in profondità.
ed ecco le parti essenziali del codice:
int AutoCompletion::initAutoCompletion() {
makeTrie(&root);
...
while ((current_pw = getpwent()) != nullptr) {
...
addStringToTrie(&root,current_pw->pw_name);
}
...
return 0;
}
