ldc.pas

   1 unit LDC;\r
   2 \r
   3 {\r
   4       IMPLEMENTACION : LISTAS DOBLES\r
   5       ALMACENAMIENTO : CURSORES\r
   6 \r
   7 }\r
   8 \r
   9 { ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular }\r
  10 interface\r
  11 \r
  12 { usa las funciones generales de TDAs }\r
  13 uses GRAL;\r
  14 \r
  15 { maximo tamano del cursor }\r
  16 const LDC_MAX_CURSOR = 100;\r
  17 \r
  18 { tipos propios de la lista para definir el cursor }\r
  19 TYPE\r
  20    LDC_puntero = integer;\r
  21 \r
  22 const\r
  23    LDC_nulo : LDC_puntero = 0;\r
  24 \r
  25 type\r
  26 \r
  27    LDC_nodo = RECORD\r
  28       Elem : T_REGISTRO;\r
  29       Sig : LDC_puntero;\r
  30       Ant : LDC_puntero;\r
  31    END;\r
  32 \r
  33 \r
  34    { ahora le toca definir el cursor }\r
  35    LDC_Almac = record\r
  36       almacenamiento : array [ 1 .. LDC_MAX_CURSOR ] of LDC_Nodo;\r
  37       siguientes     : array [ 1 .. LDC_MAX_CURSOR ] of LDC_Puntero;\r
  38     { anteriores     : array [ 1 .. LDC_MAX_CURSOR ] of LDC_Puntero;  PREGUNTAR SI ES NECESARIO }\r
  39       primero_dispo  : LDC_Puntero;\r
  40    end;\r
  41 \r
  42 \r
  43    LDC_LDC = RECORD\r
  44       almac : LDC_Almac;\r
  45       primero: LDC_puntero;\r
  46       corriente : LDC_puntero;\r
  47    END;\r
  48 \r
  49    LDC_movimiento = ( LDC_primero, LDC_siguiente, LDC_anterior );\r
  50 \r
  51 \r
  52 { ========= }\r
  53 { INTERFASE }\r
  54 \r
  55 \r
  56 PROCEDURE LDC_Inicializar( VAR l: LDC_LDC );\r
  57 FUNCTION  LDC_vacio( l: LDC_LDC): BOOLEAN;\r
  58 FUNCTION  LDC_lleno( l: LDC_LDC): BOOLEAN;\r
  59 PROCEDURE LDC_elem_cte( l: LDC_LDC; VAR r: T_REGISTRO);\r
  60 PROCEDURE LDC_modif_cte( VAR l: LDC_LDC; r: T_REGISTRO);\r
  61 PROCEDURE LDC_mover_cte( VAR l: LDC_LDC; m: LDC_movimiento; VAR error: BOOLEAN );\r
  62 PROCEDURE LDC_borrar_cte( VAR l: LDC_LDC );\r
  63 PROCEDURE LDC_insertar( VAR l: LDC_LDC; m: LDC_movimiento; r: T_REGISTRO );\r
  64 PROCEDURE LDC_vaciar( VAR l: LDC_LDC );\r
  65 PROCEDURE LDC_copiar( a: LDC_LDC; VAR b: LDC_LDC );\r
  66 \r
  67 implementation\r
  68 \r
  69 { CURSORES DE ESTA IMPLEMENTACION }\r
  70 { ========================================================================== }\r
  71 {  inicializar el almacenamiento }\r
  72 { PRE : 'almac' no esta inicializado  }\r
  73 { POST: 'almac' esta inicializado y vacio }\r
  74 procedure LDC_Almac_Inicializar( VAR almac : LDC_Almac );\r
  75 var i : LDC_Puntero;\r
  76 begin\r
  77    almac.primero_dispo := 1;\r
  78    for i := 1 to LDC_MAX_CURSOR - 1 do\r
  79    begin\r
  80       almac.siguientes[i] := i + 1;\r
  81    end;\r
  82 {  for i := 1 to LDC_CURSOR_MAX - 1 do\r
  83    begin\r
  84       almac.anteriores[i + 1] := i;                PREGUNTAR !!!!!!\r
  85    end;}\r
  86    almac.siguientes[LDC_MAX_CURSOR] := LDC_Nulo;\r
  87    {almac.anteriores[1] := LDC_Nulo;}\r
  88 end;\r
  89 \r
  90 { ========================================================================== }\r
  91 {  saber si hay lugar para reservar un nuevo elemento en el almacenamiento }\r
  92 { PRE : 'almac' esta inicializado  }\r
  93 { POST: si hay lugar en 'almac' para un nuevo elemento,\r
  94             entonces retorna TRUE y sino FALSE }\r
  95 function LDC_Almac_HayLugar( almac : LDC_Almac ): boolean;\r
  96 begin\r
  97    LDC_Almac_HayLugar := ( almac.primero_dispo <> LDC_Nulo );\r
  98 end;\r
  99 \r
 100 { ========================================================================== }\r
 101 {  el pedido de un nuevo elemento al almacenamiento }\r
 102 { PRE : 'almac' esta inicializado  }\r
 103 { POST: si hay lugar en 'almac' para un nuevo elemento,\r
 104             entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento\r
 105             sino 'puntero' tiene el valor TTDA_Nulo }\r
 106 procedure LDC_Almac_Reservar( VAR almac : LDC_Almac; VAR puntero : LDC_Puntero );\r
 107 begin\r
 108    if not LDC_Almac_HayLugar( almac ) then\r
 109       puntero := LDC_Nulo\r
 110    else begin\r
 111       puntero := almac.primero_dispo;\r
 112       almac.primero_dispo := almac.siguientes[ puntero ];\r
 113       end;\r
 114 end;\r
 115 \r
 116 { ========================================================================== }\r
 117 {  liberar un elemento del almacenamiento }\r
 118 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento  }\r
 119 { POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo }\r
 120 procedure LDC_Almac_Liberar( VAR almac : LDC_Almac; VAR puntero : LDC_Puntero );\r
 121 begin\r
 122    almac.siguientes[ puntero ] := almac.primero_dispo;\r
 123    almac.primero_dispo := puntero;\r
 124    puntero := LDC_Nulo;\r
 125 end;\r
 126 \r
 127 { ========================================================================== }\r
 128 {  acceder al elemento del almacenamiento apuntado por un puntero }\r
 129 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento  }\r
 130 { POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' }\r
 131 procedure LDC_Almac_Acceder( almac : LDC_Almac; puntero : LDC_Puntero; VAR elemento : LDC_Nodo );\r
 132 begin\r
 133    elemento := almac.almacenamiento[ puntero ];\r
 134 end;\r
 135 \r
 136 { ========================================================================== }\r
 137 {  modificar el elemento del almacenamiento apuntado por un puntero }\r
 138 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento }\r
 139 { POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' }\r
 140 procedure LDC_Almac_Modificar( VAR almac : LDC_Almac; puntero : LDC_Puntero; elemento : LDC_Nodo );\r
 141 begin\r
 142    almac.almacenamiento[ puntero ] := elemento;\r
 143 end;\r
 144 \r
 145 \r
 146 \r
 147 { Estas son los dos procedimientos principales de la aplicacion }\r
 148 \r
 149 PROCEDURE LDC_Inicializar( VAR l: LDC_LDC );\r
 150 BEGIN\r
 151    LDC_Almac_Inicializar( l.almac );\r
 152    l.primero := LDC_Nulo;\r
 153    l.corriente := LDC_Nulo;\r
 154 END;\r
 155 \r
 156 FUNCTION LDC_vacio( l: LDC_LDC): BOOLEAN;\r
 157 BEGIN\r
 158    LDC_vacio := ( l.Primero = LDC_Nulo);\r
 159 END;\r
 160 \r
 161 FUNCTION LDC_lleno( l: LDC_LDC): BOOLEAN;\r
 162 BEGIN\r
 163    LDC_lleno := not LDC_Almac_HayLugar( l.almac );\r
 164 END;\r
 165 \r
 166 PROCEDURE LDC_elem_cte( l: LDC_LDC; VAR r: T_REGISTRO);\r
 167 var n : LDC_Nodo;\r
 168 BEGIN\r
 169    { accedo al almacenamiento por el nodo corriente }\r
 170    LDC_Almac_Acceder( l.almac, l.Corriente, n );\r
 171 \r
 172    { y se lo asigno al parametro }\r
 173    r := n.Elem;\r
 174 END;\r
 175 \r
 176 PROCEDURE LDC_modif_cte( VAR l: LDC_LDC; r: T_REGISTRO);\r
 177 var n : LDC_Nodo;\r
 178 BEGIN\r
 179    { accedo al almacenamiento por el nodo corriente }\r
 180    LDC_Almac_Acceder( l.almac, l.Corriente, n );\r
 181 \r
 182    { y la asigno al parametro }\r
 183    n.Elem := r;\r
 184 \r
 185    { y modifico el almacenamiento }\r
 186    LDC_Almac_Modificar( l.almac, l.Corriente, n );\r
 187 END;\r
 188 \r
 189 PROCEDURE LDC_mover_cte( VAR l: LDC_LDC; m: LDC_movimiento; VAR error: BOOLEAN );\r
 190 VAR n : LDC_Nodo;\r
 191 BEGIN\r
 192    error := FALSE;\r
 193    CASE m OF\r
 194       LDC_primero:\r
 195          l.Corriente := l.Primero;\r
 196       LDC_siguiente: begin\r
 197          { accedo al almacenamiento por el nodo corriente }\r
 198          LDC_Almac_Acceder( l.almac, l.Corriente, n );\r
 199 \r
 200          IF ( n.Sig = LDC_Nulo ) THEN\r
 201             error := TRUE\r
 202          ELSE\r
 203             l.corriente := n.sig;\r
 204             end;\r
 205       LDC_anterior: begin\r
 206          { accedo al almacenamiento por el nodo corriente }\r
 207          LDC_Almac_Acceder( l.almac, l.Corriente, n );\r
 208 \r
 209          IF ( n.ant = LDC_Nulo ) THEN\r
 210             error := TRUE\r
 211          ELSE\r
 212             l.corriente := n.ant;\r
 213             end;\r
 214       END;\r
 215 END;\r
 216 \r
 217 PROCEDURE LDC_borrar_cte( VAR l: LDC_LDC );\r
 218 VAR nc : LDC_Nodo;         { Nodo Corriente }\r
 219     nac : LDC_Nodo;        { Nodo Anterior al Corriente }\r
 220     npc: LDC_Nodo;         { Nodo Posterior al Corriente }\r
 221     tmpp: LDC_Puntero;\r
 222 BEGIN\r
 223    if l.corriente = l.primero then begin\r
 224       LDC_Almac_Acceder( l.almac, l.primero, nc );\r
 225       l.primero := nc.Sig;\r
 226       LDC_Almac_Liberar( l.almac, l.corriente );\r
 227       l.corriente := l.primero;\r
 228       if ( l.primero <> LDC_Nulo ) then begin         { SI NO ERA EL UNICO ELEMENTO }\r
 229          LDC_Almac_Acceder( l.almac, l.primero, nc ); {--------------}\r
 230          nc.Ant := LDC_Nulo;  {--------------------------  PREGUNTAR }\r
 231          LDC_Almac_Modificar( l.almac, l.primero, nc); {-------------}\r
 232          end;\r
 233       end\r
 234    else begin\r
 235       LDC_Almac_Acceder( l.almac, l.corriente, nc );\r
 236       LDC_Almac_Acceder( l.almac, nc.Ant, nac );\r
 237       nac.Sig := nc.Sig;\r
 238       LDC_Almac_Modificar( l.almac, nc.Ant, nac );\r
 239       if ( nc.Sig <> LDC_Nulo ) then begin\r
 240          LDC_Almac_Acceder( l.almac, nc.Sig, npc );\r
 241          npc.Ant := nc.Ant;\r
 242          LDC_Almac_Modificar( l.almac, nc.Sig, npc );\r
 243          end;\r
 244       LDC_Almac_Liberar( l.almac, l.corriente );\r
 245       if ( nc.Ant <> LDC_Nulo ) then\r
 246          l.corriente := nc.Ant\r
 247       else\r
 248          l.corriente := nc.Sig;\r
 249       end;\r
 250 END;\r
 251 \r
 252 PROCEDURE LDC_insertar( VAR l: LDC_LDC; m: LDC_movimiento; r: T_REGISTRO );\r
 253 VAR\r
 254    p : LDC_puntero;\r
 255    n : LDC_Nodo;\r
 256    na: LDC_Nodo;\r
 257    ns: LDC_Nodo;\r
 258    np: LDC_Puntero;\r
 259 BEGIN\r
 260    { n.Ant := LDC_Nulo;                    { AGREGADO }\r
 261    LDC_Almac_Reservar( l.almac, np );\r
 262    n.Elem := r;\r
 263    CASE m OF\r
 264       LDC_primero: begin\r
 265          n.Sig := LDC_Nulo;\r
 266          n.Ant := LDC_Nulo;\r
 267          if ( l.primero <> LDC_Nulo ) then begin { NO ESTA VACIO EL ALMACENAMIENTO }\r
 268             LDC_Almac_Acceder( l.almac, l.primero, na );\r
 269             na.Ant := np;\r
 270             LDC_Almac_Modificar( l.almac, l.primero, na );\r
 271             n.Sig := l.primero;\r
 272             end;\r
 273          LDC_Almac_Modificar( l.almac, np, n );\r
 274          l.primero := np;\r
 275          end;\r
 276       LDC_siguiente: begin\r
 277          n.Ant := LDC_Nulo;\r
 278          n.Sig := LDC_Nulo;\r
 279          if ( l.primero <> LDC_Nulo ) then begin { NO ESTA VACIO EL ALMACENAMIENTO }\r
 280             LDC_Almac_Acceder( l.almac, l.corriente, na );\r
 281             n.Ant := l.corriente;\r
 282             n.Sig := na.Sig;\r
 283             na.Sig := np;\r
 284             LDC_Almac_Modificar( l.almac, l.corriente, na );\r
 285             end\r
 286          else\r
 287             l.primero := np;\r
 288          if ( n.Sig <> LDC_Nulo ) then begin\r
 289             LDC_Almac_Acceder( l.almac, n.Sig, ns );\r
 290             ns.Ant := np;\r
 291             LDC_Almac_Modificar( l.almac, n.Sig, ns );\r
 292             end;\r
 293          LDC_Almac_Modificar( l.almac, np, n );\r
 294          end;\r
 295       LDC_anterior: begin\r
 296          n.Ant := LDC_Nulo;\r
 297          n.Sig := LDC_Nulo;\r
 298          if ( l.primero <> LDC_Nulo ) then begin { NO ESTA VACIO EL ALMACENAMIENTO }\r
 299             LDC_Almac_Acceder( l.almac, l.corriente, ns );\r
 300             n.Sig := l.corriente;\r
 301             n.Ant := ns.Ant;\r
 302             ns.Ant := np;\r
 303             LDC_Almac_Modificar( l.almac, l.corriente, ns );\r
 304             end\r
 305          else\r
 306             l.primero := np;\r
 307          if ( n.Ant <> LDC_Nulo ) then begin\r
 308             LDC_Almac_Acceder( l.almac, n.Ant, na );\r
 309             na.Sig := np;\r
 310             LDC_Almac_Modificar( l.almac, n.Ant, na );\r
 311             end\r
 312          else { Si el Anterior es nulo, entonces estoy insertando atras del primero }\r
 313             l.primero := np;\r
 314          LDC_Almac_Modificar( l.almac, np, n );\r
 315          end;\r
 316       END; { case m of }\r
 317    l.Corriente := np;\r
 318 END;\r
 319 \r
 320 PROCEDURE LDC_vaciar( VAR l: LDC_LDC );\r
 321 VAR np : LDC_Puntero;\r
 322     n : LDC_Nodo;\r
 323 \r
 324 BEGIN\r
 325    np := l.primero;\r
 326    while( np <> LDC_Nulo ) do begin\r
 327       LDC_Almac_Acceder( l.almac, np, n );\r
 328       LDC_Almac_Liberar( l.almac, np );\r
 329       np := n.sig;\r
 330       end;\r
 331    l.primero := LDC_Nulo;\r
 332    l.corriente := LDC_Nulo;\r
 333 END;\r
 334 \r
 335 { pre: 'a' y 'b' estan creadas y 'b' esta vacia }\r
 336 { POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero }\r
 337 PROCEDURE LDC_copiar( a : LDC_LDC; VAR b : LDC_LDC );\r
 338 VAR np : LDC_Puntero;\r
 339     n  : LDC_Nodo;\r
 340     mp : LDC_Puntero;\r
 341     m  : LDC_Nodo;\r
 342     ms : LDC_Puntero;\r
 343     ma : LDC_Puntero;\r
 344 \r
 345 BEGIN\r
 346    if ( a.primero = LDC_Nulo ) then exit;\r
 347    np := a.primero;\r
 348    LDC_Almac_Acceder( a.almac, np, n );\r
 349    LDC_Almac_Reservar( b.almac, mp );\r
 350    b.primero := mp;\r
 351    b.corriente := mp;\r
 352    m.elem := n.elem;\r
 353    m.Ant := LDC_Nulo;\r
 354 \r
 355    while ( n.sig <> LDC_Nulo ) do begin\r
 356 \r
 357       LDC_Almac_Reservar( b.almac, ms );\r
 358       m.sig := ms;\r
 359       LDC_Almac_Modificar( b.almac, mp, m );\r
 360 \r
 361       np := n.sig;\r
 362       LDC_Almac_Acceder( a.almac, np, n );\r
 363 \r
 364       m.Ant := mp; { n.Ant; } \r
 365       mp := ms;\r
 366       m.elem := n.elem;\r
 367 \r
 368       end;\r
 369    m.sig := LDC_Nulo;\r
 370    LDC_Almac_Modificar( b.almac, mp, m );\r
 371 END;\r
 372 \r
 373 end.\r