-
-
Notifications
You must be signed in to change notification settings - Fork 1
/
NodoTrieS.hpp
209 lines (181 loc) · 8.67 KB
/
NodoTrieS.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
/** @file NodoTrieS.hpp
*
* Trie especial en RAM.
* Apropiado para mantener posiciones de palabras en textos
* en español con codificación ISO-8859-1
* Basado en http://www.pasosdejesus.org/vtamara/estinf2006-1/proy-s/index.html
*
* @package Mt77
* @author Vladimir Támara Patiño. vtamara@pasosdejesus.org
* Dominio público. 2008. Sin garantías
* http://creativecommons.org/licenses/publicdomain/
* @version $Id: NodoTrieS.hpp,v 1.18 2011/03/29 23:07:26 vtamara Exp $
*/
#include <set>
#include <string>
#include <vector>
#include <stdint.h>
#if !defined(NodoTrieS_hpp)
#define NodoTrieS_hpp
using namespace std;
#include "Pos.hpp"
/**
* Un nodo de un TrieS con apuntador a hermano menor e hijo mayor.
*
* Invariante: Arbol n-ario, hermanos ordenados lexicográficamente
* de menor a mayor.
* En lista de hermanos no hay 2 con prefijo común (i.e
* todos comienzan por letra diferente)
*/
class NodoTrieS
{
private:
string cad;
NodoTrieS *hermano_mayor; //< Lista de hijos
NodoTrieS *hijo_menor; //< Lista de hijos
set<Pos> cpos; //< Referencia a posiciones de esta palabra
friend NodoTrieS *mezcla(NodoTrieS *a1, NodoTrieS *a2);
friend uint32_t precalcula_escribe_actual(NodoTrieS *n);
friend uint32_t precalcula_escribe_con_hermanos(NodoTrieS *n);
friend uint32_t precalcula_escribe(NodoTrieS *n);
friend void escribePlanoStream (NodoTrieS *n,
iostream &os,
uint32_t desp /*= 0*/);
friend class TrieSDiscoCasoPrueba;
friend uint32_t escribeCopiaNodoRam(iostream &os, NodoTrieS *a,
NodoTrieS **phijo,
vector<int64_t>* renum);
friend uint32_t escribeCopiaSubarbolRam(iostream &os, NodoTrieS *a,
int saltacad,
bool conHermanos,
vector<int64_t>* renum);
friend uint32_t mezclaDiscoRam(istream &is1, NodoTrieS *a2,
int saltacad,
iostream &os, bool conHermanos1,
bool conHermanos2,
vector<int64_t> *renum1,
vector<int64_t> *renum2);
friend uint32_t escribeCopiaNodoRam(iostream &os, NodoTrieS *a,
int saltacad,
NodoTrieS **phijo,
vector<int64_t>* renum);
public:
/** Constructora.
* Responsabilidad de liberar hijo_menor y hermano_mayor pasa a
* este nodo, esperando más eficiencia en mezclas.
* @param cad Cadena
* @param hijo_menor Apuntador a Hijo menor
* @param hermano_mayor Apuntador a hermano mayor
* @param cpos conjunto de posiciones donde está la palabra
**/
NodoTrieS(string cad = "", NodoTrieS *hijo_menor=NULL,
NodoTrieS *hermano_mayor = NULL,
set<Pos> cpos = set<Pos>());
/** Constructora que recibe una posición.
* Responsabilidad de liberar hijo_menor y hermano_mayor pasa a
* este nodo, esperando más eficiencia en mezclas.
* Inicializa conjunto de posiciones con una posición i.e. p.
* @param cad Cadena
* @param hijo_menor Apuntador a Hijo menor
* @param hermano_mayor Apuntador a hermano mayor
* @param p posición inicial
**/
NodoTrieS(string cad, NodoTrieS *hijo_menor,
NodoTrieS *hermano_mayor, Pos p);
/** Destructora.
* Libera recursivamente hijo_menor y hermano_mayor
*/
~NodoTrieS();
/**
* Retorna copia de posiciones en palabra para depuración
*/
set<Pos> depuracpos()
{
return cpos;
}
/** Busca la palabra pal. Retorna lista de posiciones en las que
* aparece.
* @param pal Palabra por buscar
* @return NULL en caso de que la palabra no este.
*/
set<Pos> busca(string pal);
/** Inserta una ocurrencia mas de la palabra pal, reportandola en
* posicion p.
* @param pal Palabra por insertar
* @param p Posición donde aparece
* @return Nueva raiz.
* @exception Memoria si la memoria se agota al insertar. En ese
* caso se garantiza que el arbol queda en un estado consistente.
*/
void inserta(string pal, Pos p);
/**
* Inserta una palabra normalizandola antes si normaliza es true
* @param pal Palabra por insertar
* @param numdoc Numero de documento en el que insertará
* @param pini Posición inicial donde insertará
* @param normaliza Indica si debe o no normalizar
* @param latin Indica si pal está en codificación LATIN1
*/
void insertaNormalizando(string pal, uint32_t numdoc,
uint32_t p, bool normalizaPal,
bool latin1 = false);
/** Inserta más ocurrencias de la palabra pal, reportandolas en
* posiciones npos.
* @param pal Palabra por insertar
* @param npos Posiciones donde aparece
* @return Nueva raiz.
* @exception Memoria si la memoria se agota al insertar. En ese
* caso se garantiza que el arbol queda en un estado consistente.
*/
void
inserta(string pal, set<Pos> *npos);
/**
* Escribe representacion de TrieS como
* árbol en el formato de dotty.
* @param os Flujo donde escribirá
* @param pref Prefijo para indentación
* @param primero Si es el primer nodo
* @param mayor Si es el mayor de los hermanos del nivel
*/
void aDotty(ostream &os, string pref = "",
bool primero = true, bool mayor = true) noexcept(false);
/* Arbol mas simple en formato dot */
void aDotty2(ostream &os, string pref = "", bool primero = true);
/* Arbol mas simple en formato dot en salida estándar*/
void aDotty2();
/**
* Con propósitos de depuración, retorna cadena con
* árbol en preorden.
*/
string preorden();
/** Renumera documentos referenciados en posiciones de trieS de
* acuerdo a vector renum. Una posición cuyo documento sea el
* número p (>=1) pasará a ser el número renum[p-1] (>=1).
* @param renum Vector para renumerar
*/
void renumeraDocs(vector<int64_t> renum);
/**
* Divide la cadena c en palabras e inserta cada una con
* la etiqueta dada en el árbol, referenciando el documento
* numdoc desde la posición inicial posini.
* @param c Cadena con palabras por insertar
* @param etiqueta Por agregar a cada palabra
* @param numdoc Número de documento del cual provienen
* @param pini Posición inicial en documento de la cadena c
* @param latin1 Lo que se agregara está en LATIN1
*/
void insertaConEtiqueta(string c, string etiqueta,
uint32_t numdoc,
uint32_t pini,
bool latin1 = false);
};
/** Construye un trieS a partir de un texto plano
* @param na Archivo
* @param ndoc Número de documento
* @param t Donde se leera trieS
* @param normalizaPal Si debe o no normalizar cada palabra leida
* @param latin1 Si el texto está en codificación LATIN1 dlc es UTF-8
**/
void leeTexto(const char *na, uint32_t ndoc, NodoTrieS &t,
bool normalizaPal = true, bool latin1 = false);
#endif