00001 /**********************************************************/ 00002 /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/ 00003 /* 00004 Copyright: 1996 - Grupo de Voz (DAET) ETSII/IT-Bilbao 00005 00006 Nombre fuente................ LISTT.CPP 00007 Nombre paquete............... - 00008 Lenguaje fuente.............. C++ 00009 Estado....................... Completado 00010 Dependencia Hard/OS.......... - 00011 Codigo condicional........... - 00012 00013 Codificacion................. Borja Etxebarria 00014 00015 Version dd/mm/aa Autor Comentario 00016 ------- -------- -------- ---------- 00017 1.1.0 07/05/99 Borja modif ??_mv() $$$$ doc. sin actualizar!! 00018 1.0.1 30/08/98 Borja split varios modulos listt_?.cpp 00019 1.0.0 26/03/98 Borja recodificado, templates mas sencillas. 00020 0.0.2 26/08/97 Borja uso LIINT (INT o LONG) en vez de INT 00021 0.0.1 26/08/97 Borja documentacion anyadir sin indicar elemento 00022 0.0.0 06/05/96 Borja Codificacion inicial. 00023 00024 ======================== Contenido ======================== 00025 <DOC> 00026 Manejo de listas (doblemente encadenadas) y variantes: 00027 00028 ListT template para lista 00029 SetListT template para lista set o conjunto (elementos no repetidos) 00030 KeyValListT template para lista clave K, valor V (K no repetida) 00031 00032 Nota: 00033 Si LIST_PTRVERIFY esta definido, se hace un chequeo bastante completo 00034 de inconsistencias a la hora de manejar las listas. Es un poco lento 00035 pero mas seguro. Si LIST_PTRVERIFY no esta definido, no se efectuan 00036 chequeos, y puede ser peligroso. Para chequear algunos problemas, 00037 utilizando OK() se puede comprobar que la lista sigue siendo valida. 00038 00039 Por ejemplo, si haces un exchange() entre elementos de listas 00040 diferentes, utilizas un Lix invalido, etc, o si anyades un elemento 00041 duplicado a un SetListT la lista deja de ser consistente. 00042 00043 ATENCION ATENCION ATENCION!!!!!!!!!!! 00044 Las plantillas SetListT y KeyValListT solo se puede aplicar sobre 00045 clases que tengan definido el operador de comparacion igual (==) (para 00046 el tipo clave K en la plantilla KeyValListT). Si la clase no lo tiene 00047 implementado, la plantilla provocara un error de compilacion! 00048 Un ejemplo de dicho operador para una clase MiTipo 00049 friend int operator==(const MiTipo &a,const MiTiop &b) 00050 { 00051 return a.i == b.i; // por poner algo... 00052 }; 00053 00054 ########################################################### 00055 Muchos metodos pueden recibir una referencia a un elemento de la lista 00056 bien a traves de un pseudo-indice de lista (Lix) {p} o bien a traves 00057 de un numero entero {i} que indica el numero de orden dentro de la lista. 00058 Trabajar con {i} es mucho mas lento y no es recomendable. En cualquier 00059 caso cuando se use {i} debe ser un valor valido dentro del rango de 00060 elementos de la lista (empezando en 0 para el primer elemento). 00061 00062 *** Los constructores no reciben parametros. Para inicializar o copiar 00063 una lista a partir de otra, se utilizan los metodos create() o el 00064 operador de asignacion (=). Los SetList o KeyValList inicializados 00065 con create() no copian elementos duplicados. 00066 *** l1=l2 : copia los elementos de la lista {l2} en la lista {l1} (primero 00067 se vacia {l1}). Los SetList o KeyValList no copian elementos duplicados. 00068 *** OK() : {devuelve} TRUE si la lista esta bien, o FALSE si esta mal 00069 (por ejemplo si esta corrupta o si se detectan elementos duplicados en 00070 un Set o una lista KeyVal). 00071 *** empty() : {devuelve} TRUE si la lista esta vacia 00072 *** length() : {devuelve} el numero de elementos de la lista 00073 *** clear() : borra todos los elementos de la lista 00074 00075 Las siguientes mejor no usarlas con Set y KeyVal. Estos metodos pueden 00076 funcionar con indices de lista (Lix) o con indices enteros (cuando sea 00077 aplicable). En el caso de KeyVal en vez de enviar un unico valor {x} 00078 se envian dos valores, la clave {k} y el valor {v}, por lo demas igual. 00079 El elemento/lista recibido se copia usa para inicializar el elemento de 00080 la lista (cuidado, puede tener efectos secundarios sutiles si los 00081 elementos contienen punteros a arrays, etc, pues se copia la 00082 referencia-puntero, no el array, a no ser que el operador = este 00083 adecuadamente definido). Tambien hay versiones que no reciben elemento 00084 inicial, y utilizan el constructor por defecto del elemento para 00085 inicializar el contenido del elemento en la lista. 00086 Para el caso de que se envie una lista, tambien hay versiones ???_mv 00087 (p.ej. append_mv()) que anyaden una lista completa de elementos, 00088 pero no copiando sino moviendo los elementos de la lista enviada 00089 (que queda vacia). 00090 *** prepend() : anyade un elemento al principio de la lista. {devuelve} 00091 indice Lix al primer elemento (link de {x}). 00092 *** append() : anyade elemento al final de la lista. {devuelve} indice Lix 00093 al ultimo elemento (link de {x}) 00094 *** insbefore() : anyade {x} antes del apuntado por {p}, y {devuelve} 00095 el link de {x}. Si {p} es null, anyade al final. 00096 *** insafter() : anyade {x} despues del apuntado por {p}, y {devuelve} 00097 el link de {x}. Si {p} es null, anyade al principio 00098 00099 Metodos para listas KeyVal, y algunas tambien para Sets. Cuando 00100 intervienen listas KeyVal con listas normales o sets, solo se utiliza 00101 el campo clave Key (en busquedas, eliminaciones, etc): 00102 *** add() : anyade un elemento {x} (Sets) o pareja {k}{v} (KeyVal) 00103 a la lista, salvo que ya exista. En el caso de KeyVal, si {k} ya existe, 00104 se actualiza con el nuevo valor {v} (salvo si se especifica {rewr}=FALSE). 00105 Se {devuelve} el link al elemento. Existen variantes para anyadir 00106 otra lista/set/keyval completo. Por ejemplo t.add(t2) anyade todos 00107 los elementos de la lista-KeyVal {t2} a la lista-KeyVal {t}, los 00108 elementos {k} que ya existieran en {t} se actualiza con los nuevos 00109 valores {v} de la lista {t2}, salvo si {rewr} se envia a FALSE. 00110 Tambien hay version add_mv() que mueve la lista enviada en vez de 00111 copiarla (si algun elemento no se debe mover, queda en la lista 00112 enviada, los demas desaparecen de la lista enviada). 00113 *** val() : {devuelve} el valor (Val) para una clave {k}. Si {k} no existe 00114 se produce error, salvo que se especifique un valor por defecto {vdef}. 00115 *** seek() : busca un elemento (o clave {k}) y {devuelve} su link {p}, o 00116 {devuelve} null si no esta en la lista. 00117 *** contains() : {devuelve} TRUE si la lista contiene al elemento {x} 00118 (o clave {k}). Hay versiones para comprobar si una lista contiene 00119 todos los elementos de otra lista (o lista de claves). 00120 *** equals() : {devuelve} TRUE si las dos listas son iguales (en el caso 00121 de listas KeyVal, solo se comprueba la clave Key). Cuando se compare 00122 un set o lista KeyVal con una lista normal, hay un segundo parametro 00123 {allowrep} que si es TRUE ignora elementos repetidos en la lista normal 00124 a efectos de comparacion. 00125 *** erase() : elimina el elemento indicado si existe (y se {devuelve} TRUE. 00126 Si no, no hace nada (y {devuelve} FALSE). Hay versiones para eliminar 00127 todos los elementos indicados en una lista. 00128 *** keep() : Mantiene solo los elementos que esten en otra lista indicada. 00129 00130 Metodos para borrar elementos (tambien hay versiones con indices Lix {p} 00131 y con indices enteros {i} para algunas de ellas): 00132 *** delfirst() : quita el primer elemento de la lista, error si no hay 00133 elementos 00134 *** dellast() : quita el ultimo elemento de la lista, error si no hay 00135 elementos 00136 *** del() quita el indicado en {p} y {devuelve} puntero al 00137 siguiente (dir>=0) o anterior (dir<0), error si {p} es null. 00138 *** delnext() : quita el siguiente al indicado en {p}, error si 00139 no existe ese siguiente. Si {p} es null, quita al principio. 00140 *** delprev() : quita el anterior al indicado en {p}, error si no 00141 existe ese anterior. Si {p} es null, quita al final. 00142 00143 Estas sirven para moverse por la lista con punteros Lix {p} o enteros {i} 00144 y demas funciones relacionadas: 00145 *** first() : {devuelve} el link al primer elemento, null cuando no hay 00146 ninguno. 00147 *** last() : {devuelve} el link al ultimo elemento, null cuando no hay 00148 ninguno. 00149 *** prev() : {devuelve} el link del elemento anterior a {p}, null cuando 00150 ya no hay mas. 00151 *** next() : {devuelve} el link del siguiente elemento a {p}, null cuando 00152 ya no hay mas. 00153 *** owns() : {devuelve} TRUE si la lista contiene el link {p} 00154 *** index() : {devuelve} el numero de orden en la lista para el link {p}, 00155 o -1 si no esta en la lista. 00156 *** lix() : {devuelve} el link correspondiente al elemento {i}esimo 00157 de la lista, o null si no existe dicho elemento. 00158 00159 00160 Lectura/escritura de elementos ya existentes. {devueven} una referencia 00161 asi que se pueden usar tanto para leer como para modificar el elemento. 00162 En el caso de Sets tener cuidado, pues al modificar el elemento 00163 (la clave en el caso de listas KeyVal) la lista puede ser inconsistente 00164 si aparecen elementos duplicados. En listas KeyVal se debe utilizar 00165 itemkey() en vez de item(). Hay versiones con Lix {p} o con enteros {i}: 00166 *** item_first() : {devuelve} el primer elemento, error si no hay 00167 *** item_last() : {devuelve} el ultimo elemento, error si no hay 00168 *** item(p) : {devuelve} el elemento del link {p}, error si no hay 00169 *** operador () : {devuelve} el elemento del link {p} (idem a item()), o 00170 error si no hay. Se usa por ejemplo asi: q=l(p). No hay version para 00171 left-hand (no se puee hacer l(p)=q). 00172 00173 00174 Estas son similares a las anteriores, pero especificas para listas KeyVal. 00175 Tambien permiten leer o escribir, aunque modificar asi los campos Key 00176 es peligroso pues se pueden duplicar elementos... 00177 *** itemkey() 00178 *** itemkey_first() 00179 *** itemkey_last() 00180 *** itemval() 00181 *** itemval_first() 00182 *** itemval_last() 00183 00184 00185 Metodos varios: 00186 *** exchange() : intercambia los links {p1} y {p2} dentro de la lista. error 00187 si alguno es null. (hay version con indices {i}). Se intercambian 00188 contenidos, por lo que los indices Lix siguen siendo validos, pero 00189 los contenidos estan intercambiados. 00190 *** reverse() : invierte el orden de la lista (cabeza <-> cola). 00191 *** sortf() : ordena la lista siguiendo el criterio de la funcion de 00192 comparacion enviada como parametro (ver qsort() en stdlib para saber 00193 como funciona la funcion de comparacion). En listas KeyVal, los 00194 parametros comparados son las claves {k}. 00195 00196 ########################################################### 00197 Ejemplos de uso. 00198 00199 Ejemplo de uso de la plantilla ListT 00200 00201 int x, y; 00202 ListT<int> l; 00203 Lix p; 00204 00205 for (x=0; x<100; x++) // metemos unos cuantos elementos 00206 l.append(x); 00207 00208 y=0; 00209 for (p=l.first(); p!=0; p=l.next(p)) // recorremos la lista 00210 y += l(p); // vamos sumando en {y} los elementos de la lista. 00211 00212 Para la plantilla SetListT usar add(x) para anyadir elementos. Para 00213 la plantilla KeyValListT usar add(k,v). Si no se hace asi la lista 00214 puede tener inconsistencias. KeyVal y Set tienen metodos de busqueda 00215 (seek) y comprobacion de que existe un elemento (contains) entre otros. 00216 KeyVal tiene posibilidad de localizar un Val a partir de una Key (val(k)) 00217 entre otros. 00218 00219 ########################################################### 00220 Tabla de metodos definidos en cada template: 00221 00222 Dadas estas variables: 00223 00224 MiTipo x; // dato del usuario, del tipo que sea (ej. MiTipo) 00225 MiClave k; // dato de tipo clave 00226 MiValor v; // dato de tipo valor; 00227 ListT<MiTipo> l; // lista (double-linked) de datos del tipo MiTipo 00228 SetListT<MiTipo> s; // set-lista (double-linked) de datos del tipo MiTipo 00229 KeyValListT<MiClave,MiValor> t; // conjunto clave-valor para dos tipos dados 00230 Lix p; // "List index", link a la lista, "indice" para recorrerla 00231 LIINT i; // numero entero (INT o LONG) (indice entero para recorrer listas) 00232 LIINT n; // numero entero (INT o LONG) 00233 BOOL b; // valor booleano 00234 00235 Estas son las operaciones que se pueden hacer con cada template (las 00236 que tienen una admiracion (!) detras es porque se deben usar con 00237 cuidado, pues pueden producir inconsistencia en los datos de la lista, 00238 no deben usarse salvo sabiendo exactamente lo que se hace y el nombre 00239 del metodo va precedido por un underscore (_) aunque aqui no aparezca 00240 (vamos, que en vez de t.append() realmente el nombre del metodo que 00241 se debe usar es t._append() ). 00242 00243 00244 ListT SetListT KeyValListT 00245 -------------------------------------------------------------------------- 00246 ListT<tipo> l; SetListT<tipo> s KeyValListT<tk,tv> t 00247 00248 l.create(l2) s.create(s2) t.create(t2) 00249 l.create(s) s.create(l) - 00250 00251 l=l2; s=s2 t=t2 00252 l=s s=l - 00253 00254 b=l.OK() b=s.OK() b=t.OK() 00255 00256 b=l.empty() b=s.empty() b=t.empty() 00257 n=l.length() n=s.length() n=t.length() 00258 l.clear() s.clear() t.clear() 00259 00260 p=l.prepend() p=s.prepend()! p=t.prepend()! 00261 p=l.prepend(x) p=s.prepend(x)! p=t.prepend(k,v)! 00262 p=l.prepend(l2) p=s.prepend(s2)! p=t.prepend(t2)! 00263 p=l.prepend(s) p=s.prepend(l)! - 00264 p=l.prepend_mv(l2) p=s.prepend_mv(s2)! p=t.prepend_mv(t2)! 00265 p=l.prepend_mv(s) p=s.prepend_mv(l)! - 00266 00267 p=l.append() p=s.append()! p=t.append()! 00268 p=l.append(x) p=s.append(x)! p=t.append(k,v)! 00269 p=l.append(l2) p=s.append(s2)! p=t.append(t2)! 00270 p=l.append(s) p=s.append(l)! - 00271 p=l.append_mv(l2) p=s.append_mv(s2)! p=t.append_mv(t2)! 00272 p=l.append_mv(s) p=s.append_mv(l)! - 00273 00274 p=l.insbefore(p) p=s.insbefore(p)! p=t.insbefore(p)! 00275 p=l.insbefore(p,x) p=s.insbefore(p,x)! p=t.insbefore(p,k,v)! 00276 p=l.insbefore(p,l2) p=s.insbefore(p,s2)! p=t.insbefore(p,t2)! 00277 p=l.insbefore(s) p=s.insbefore(l)! - 00278 p=l.insbefore_mv(l2) p=s.insbefore_mv(s2)! p=t.insbefore_mv(t2)! 00279 p=l.insbefore_mv(s) p=s.insbefore_mv(l)! - 00280 00281 p=l.insafter(p) p=s.insafter(p)! p=t.insafter(p)! 00282 p=l.insafter(p,x) p=s.insafter(p,x)! p=t.insafter(p,k,v)! 00283 p=l.insafter(p,l2) p=s.insafter(p,s2)! p=t.insafter(p,t2)! 00284 p=l.insafter(s) p=s.insafter(l)! - 00285 p=l.insafter_mv(l2) p=s.insafter_mv(s2)! p=t.insafter_mv(t2)! 00286 p=l.insafter_mv(s) p=s.insafter_mv(l)! - 00287 00288 - p=s.add(x) p=t.add(k,v,rewr) 00289 - s.add(s2) t.add(t2,rewr) 00290 - s.add(l) - 00291 - s.add_mv(s2,rewr) t.add_mv(t2,rewr) 00292 00293 - - v=t.val(k) 00294 - - v=t.val(k,vdef) 00295 00296 - p=s.seek(x) p=t.seek(k) 00297 00298 - b=s.contains(x) b=t.contains(k) 00299 - b=s.contains(s2) b=t.contains(t2) 00300 - b=s.contains(l) b=t.contains(l) 00301 - - b=t.contains(s) 00302 00303 - b=s.equals(s,allowrep) b=t.equals(t2,allowrep) 00304 - b=s.equals(l,allowrep) b=t.equals(l,allowrep) 00305 - - b=t.equals(s,allowrep) 00306 00307 - b=s.erase(x) b=t.erase(k) 00308 - b=s.erase(s2) b=t.erase(t2) 00309 - b=s.erase(l) b=t.erase(l) 00310 - b=t.erase(s) 00311 00312 - s.keep(s2) t.keep(t2) 00313 - s.keep(l) t.keep(l) 00314 - - t.keep(s) 00315 00316 p=l.del(p,dir=1) p=s.del(p,dir=1) p=t.del(p,dir=1) 00317 l.delprev(p) s.delprev(p) t.delprev(p) 00318 l.delnext(p) s.delnext(p) t.delnext(p) 00319 p=l.delfirst() p=s.delfirst() p=t.delfirst() 00320 p=l.dellast() p=s.dellast() p=t.dellast() 00321 00322 p=l.first() p=s.first() p=t.first() 00323 p=l.last() p=s.last() p=t.last() 00324 p=l.next(p) p=s.next(p) p=t.next(p) 00325 p=l.prev(p) p=s.prev(p) p=t.prev(p) 00326 b=l.owns(p) b=s.owns(p) b=t.owns(p) 00327 i=l.index(p) i=s.index(p) i=t.index(p) 00328 p=l.lix(i) p=s.lix(i) p=t.lix(i) 00329 00330 x=l.item(p)=x x=s.item(p)=x! - 00331 x=l(p) x=s(p) - 00332 x=l.item_first()=x x=s.item_first()=x! - 00333 x=l.item_last()=x x=s.item_last()=x! - 00334 00335 - - k=t.itemkey(p)=k! 00336 - - k=t.itemkey_first()=k! 00337 - - k=t.itemkey_last()=k! 00338 - - v=t.itemval(p)=v! 00339 - - v=t.itemval_first(p)=v! 00340 - - v=t.itemval_last(p)=v! 00341 00342 l.exchange(p1,p2) s.exchange(p1,p2) t.exchange(p1,p2) 00343 l.reverse() s.reverse() t.reverse() 00344 l.sortf(cmpfunc) s.sortf(cmpfunc) t.sortf(kcmpfunc) 00345 00346 00347 Las funciones anteriores que reciben pseudoindices (p, p1, p2) tambien 00348 pueden trabajar con indices enteros. 00349 </DOC> 00350 =========================================================== 00351 */ 00352 /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/ 00353 /**********************************************************/ 00354 00355 #include "listt_i.hpp" 00356 00357 /**********************************************************/ 00358 00359 #ifdef LIST_PTRVERIFY 00360 Lix _PList::__lix_safe( LIINT i, CHAR*func, BOOL allow0) const 00361 { 00362 Lix p=lix(i); 00363 if ((p==0)&&(!allow0 || i)) { 00364 LISTERROR(func," invalid index"); 00365 } 00366 return p; 00367 } 00368 #endif 00369 00370 /**********************************************************/ 00371 00372 _PListNode *_PList::__newNode_d( const VOID *data ) 00373 { 00374 VOID * t = _newData(data); 00375 if (!t) 00376 LISTERROR("__newNode_d","can't create data object (null new)"); 00377 return __newNode_p(t); 00378 } 00379 00380 /**********************************************************/ 00381 00382 _PListNode *_PList::__newNode_p( VOID *data ) 00383 { 00384 _PListNode * t = new _PListNode(data); 00385 if (!t) 00386 LISTERROR("__newNode_p","can't create node object (null new)"); 00387 return t; 00388 } 00389 00390 /**********************************************************/ 00391 00392 _PListNode *_PList::__newNode_d( const _PListNode *node ) 00393 { 00394 return __newNode_d(node->dp); 00395 } 00396 00397 /**********************************************************/ 00398 00399 _PListNode *_PList::__newNode_p( _PListNode *node ) 00400 { 00401 return __newNode_p(node->dp); 00402 } 00403 00404 /**********************************************************/ 00405 00406 VOID _PList::__deleteNode_d( _PListNode *p ) 00407 { 00408 _deleteData(p->dp); 00409 delete p; 00410 } 00411 00412 /**********************************************************/ 00413 00414 Lix _PList::__prepend(_PListNode *t) 00415 { 00416 if (h == 0) t->f = t->b = h = t; 00417 else { 00418 t->f = h; 00419 t->b = h->b; 00420 h->b->f = t; 00421 h->b = t; 00422 h = t; 00423 } 00424 return Lix(t); 00425 } 00426 00427 /**********************************************************/ 00428 00429 Lix _PList::__append(_PListNode *t) 00430 { 00431 if (h == 0) t->f = t->b = h = t; 00432 else { 00433 t->b = h->b; 00434 t->b->f = t; 00435 t->f = h; 00436 h->b = t; 00437 } 00438 return Lix(t); 00439 } 00440 00441 /**********************************************************/ 00442 00443 Lix _PList::__insbefore(Lix p, _PListNode *t) 00444 { 00445 if (p == 0) return __append(t); 00446 LISTVERIFY(p,"__insbefore"); 00447 _PListNode* u = (_PListNode*) p; 00448 t->b = u->b; 00449 t->f = u; 00450 u->b->f = t; 00451 u->b = t; 00452 if (u == h) h = t; 00453 return Lix(t); 00454 } 00455 00456 /**********************************************************/ 00457 00458 Lix _PList::__insafter(Lix p, _PListNode *t) 00459 { 00460 if (p == 0) return __prepend(t); 00461 LISTVERIFY(p,"__insafter"); 00462 _PListNode* u = (_PListNode*) p; 00463 t->b = u; 00464 t->f = u->f; 00465 u->f->b = t; 00466 u->f = t; 00467 return Lix(t); 00468 } 00469 00470 /**********************************************************/ 00471 00472 Lix _PList::__del(Lix p, INT dir) 00473 { 00474 if (p == 0) { LISTNONULL(p,"__del"); } 00475 else { 00476 LISTVERIFY(p,"__del"); 00477 _PListNode* t = (_PListNode*) p; 00478 if (t->f == t) { h = 0; p = 0; } 00479 else { 00480 if (dir < 0) { if (t == h) p = 0; else p = Lix(t->b); } 00481 else { if (t == h->b) p = 0; else p = Lix(t->f); } 00482 t->b->f = t->f; 00483 t->f->b = t->b; 00484 if (t == h) h = t->f; 00485 } 00486 } 00487 return p; 00488 } 00489 00490 /**********************************************************/ 00491 00492 VOID _PList::__clear( BOOL cdata ) 00493 { 00494 if (h == 0) return; 00495 _PListNode* p = h->f; 00496 h->f = 0; 00497 h = 0; 00498 while (p != 0) { 00499 _PListNode* nxt = p->f; 00500 if (cdata) __deleteNode_d(p); 00501 else __deleteNode_p(p); 00502 p = nxt; 00503 } 00504 } 00505 00506 /**********************************************************/
1.5.6