Import inicial despuƩs del "/var incident". :(
[z.facultad/75.41/parcial.git] / t_colord_a2.pas
1 { algoritmos y programacion II - Catedra Carolo - PRACTICA }\r\r
2 { PARCIAL 1 1ra Op CUAT 1 2000 }\r\r
3 \r\r
4 unit T_COLORD_A2;\r\r
5 \r\r
6 {\r\r
7         IMPLEMENTACION : cola ordenada (cola de prioridades)\r\r
8         ALMACENAMIENTO : CURSORES\r\r
9         CARACTERISTICAS: sacar ordenado\r\r
10         \r\r
11 }\r\r
12 \r\r
13 { ACLARACIONES : implementamos tambien aca los cursores porque son para estos nodos en particular }\r\r
14 interface\r\r
15 \r\r
16 { usa las funciones generales de TDAs }\r\r
17 uses tda_gral;\r\r
18 \r\r
19 { maximo tamano del cursor }\r\r
20 const COLAORD_MAX_CURSOR = 100;\r\r
21 \r\r
22 { tipos propios de la lista para definir el cursor }\r\r
23 TYPE\r\r
24         COLAORD_puntero = integer;\r\r
25 \r\r
26 const\r\r
27    COLAORD_nulo : COLAORD_puntero = 0;\r\r
28 \r\r
29 type\r\r
30 \r\r
31         COLAORD_nodo = RECORD\r\r
32                 Elem : Tipo_Elem;\r\r
33                 Sig : COLAORD_puntero;\r\r
34         END;\r\r
35 \r\r
36 \r\r
37    { ahora le toca definir el cursor }\r\r
38    COLAORD_Almac = record\r\r
39       almacenamiento : array [ 1 .. COLAORD_MAX_CURSOR ] of COLAORD_Nodo;\r\r
40       disponibles    : array [ 1 .. COLAORD_MAX_CURSOR ] of COLAORD_Puntero;\r\r
41       primero_dispo  : COLAORD_Puntero;\r\r
42    end;\r\r
43 \r\r
44         \r\r
45    COLAORD_Cola = RECORD\r\r
46                 almac : COLAORD_Almac;\r\r
47                 primero: COLAORD_puntero;\r\r
48         END;\r\r
49 \r\r
50 \r\r
51 { ========= }\r\r
52 { INTERFASE }\r\r
53 \r\r
54 \r\r
55 PROCEDURE COLAORD_Inicializar ( VAR l: COLAORD_Cola );\r\r
56 FUNCTION  COLAORD_vacia( l: COLAORD_Cola): BOOLEAN;\r\r
57 FUNCTION  COLAORD_llena( l: COLAORD_Cola): BOOLEAN;\r\r
58 \r\r
59 PROCEDURE COLAORD_poner ( VAR l: COLAORD_Cola; e: Tipo_Elem; VAR error: boolean);\r\r
60 PROCEDURE COLAORD_sacar ( VAR l: COLAORD_Cola; VAR e: Tipo_Elem);\r\r
61 PROCEDURE COLAORD_vaciar ( VAR l: COLAORD_Cola );\r\r
62 PROCEDURE COLAORD_copiar ( a: COLAORD_Cola; VAR b: COLAORD_Cola );\r\r
63 \r\r
64 implementation\r\r
65 \r\r
66 { CURSORES DE ESTA IMPLEMENTACION }\r\r
67 { ========================================================================== }\r\r
68 {  inicializar el almacenamiento }\r\r
69 { PRE : 'almac' no esta inicializado  }\r\r
70 { POST: 'almac' esta inicializado y vacio }\r\r
71 procedure COLAORD_Almac_Inicializar( VAR almac : COLAORD_Almac );\r\r
72 var i : COLAORD_Puntero;\r\r
73 begin\r\r
74    almac.primero_dispo := 1;\r\r
75    for i := 1 to COLAORD_MAX_CURSOR - 1 do\r\r
76    begin\r\r
77       almac.disponibles[i] := i + 1;\r\r
78    end;\r\r
79    almac.disponibles[COLAORD_MAX_CURSOR] := COLAORD_Nulo;\r\r
80 end;\r\r
81 \r\r
82 { ========================================================================== }\r\r
83 {  saber si hay lugar para reservar un nuevo elemento en el almacenamiento }\r\r
84 { PRE : 'almac' esta inicializado  }\r\r
85 { POST: si hay lugar en 'almac' para un nuevo elemento,\r\r
86             entonces retorna TRUE y sino FALSE }\r\r
87 function COLAORD_Almac_HayLugar( almac : COLAORD_Almac ): boolean;\r\r
88 begin\r\r
89    COLAORD_Almac_HayLugar := almac.primero_dispo <> COLAORD_Nulo;\r\r
90 end;\r\r
91 \r\r
92 { ========================================================================== }\r\r
93 {  el pedido de un nuevo elemento al almacenamiento }\r\r
94 { PRE : 'almac' esta inicializado  }\r\r
95 { POST: si hay lugar en 'almac' para un nuevo elemento,\r\r
96             entonces 'puntero' tiene una referencia a un nuevo elemento del almacenamiento\r\r
97             sino 'puntero' tiene el valor TTDA_Nulo }\r\r
98 procedure COLAORD_Almac_Reservar( VAR almac : COLAORD_Almac; VAR puntero : COLAORD_Puntero );\r\r
99 begin\r\r
100    if not COLAORD_Almac_HayLugar( almac )\r\r
101    then\r\r
102       puntero := COLAORD_Nulo\r\r
103    else begin\r\r
104       puntero := almac.primero_dispo;\r\r
105       almac.primero_dispo := almac.disponibles[ puntero ];\r\r
106    end;\r\r
107 end;\r\r
108 \r\r
109 { ========================================================================== }\r\r
110 {  liberar un elemento del almacenamiento }\r\r
111 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento  }\r\r
112 { POST: 'almac' libero el nodo apuntado por 'puntero' y 'puntero' vale TTDA_Nulo }\r\r
113 procedure COLAORD_Almac_Liberar( VAR almac : COLAORD_Almac; VAR puntero : COLAORD_Puntero );\r\r
114 begin\r\r
115    almac.disponibles[ puntero ] := almac.primero_dispo;\r\r
116    almac.primero_dispo := puntero;\r\r
117    puntero := COLAORD_Nulo;\r\r
118 end;\r\r
119 \r\r
120 { ========================================================================== }\r\r
121 {  acceder al elemento del almacenamiento apuntado por un puntero }\r\r
122 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento  }\r\r
123 { POST: 'elemento' tiene una copia del elemento apuntado por 'puntero' }\r\r
124 procedure COLAORD_Almac_Acceder( almac : COLAORD_Almac; puntero : COLAORD_Puntero; VAR elemento : COLAORD_Nodo );\r\r
125 begin\r\r
126    elemento := almac.almacenamiento[ puntero ];\r\r
127 end;\r\r
128 \r\r
129 { ========================================================================== }\r\r
130 {  modificar el elemento del almacenamiento apuntado por un puntero }\r\r
131 { PRE : 'almac' esta inicializado y 'puntero' fue pedido al almacenamiento }\r\r
132 { POST: el elemento de 'almac' apuntado por 'puntero' tiene una copia de 'elemento' }\r\r
133 procedure COLAORD_Almac_Modificar( VAR almac : COLAORD_Almac; puntero : COLAORD_Puntero; elemento : COLAORD_Nodo );\r\r
134 begin\r\r
135    almac.almacenamiento[ puntero ] := elemento;\r\r
136 end;\r\r
137 \r\r
138 \r\r
139 \r\r
140 { Estas son los dos procedimientos principales de la aplicaciĆ³n }\r\r
141 \r\r
142 PROCEDURE COLAORD_Inicializar ( VAR l: COLAORD_Cola );\r\r
143 BEGIN\r\r
144    COLAORD_Almac_Inicializar( l.almac );\r\r
145    l.primero := COLAORD_Nulo;\r\r
146 END;\r\r
147 \r\r
148 FUNCTION COLAORD_vacia( l: COLAORD_Cola): BOOLEAN;\r\r
149 BEGIN\r\r
150         COLAORD_vacia := ( l.Primero = COLAORD_Nulo);\r\r
151 END;\r\r
152 \r\r
153 FUNCTION COLAORD_llena( l: COLAORD_Cola): BOOLEAN;\r\r
154 BEGIN\r\r
155         COLAORD_llena := not COLAORD_Almac_HayLugar( l.almac );\r\r
156 END;\r\r
157 \r\r
158 PROCEDURE COLAORD_poner ( VAR l: COLAORD_Cola; e: Tipo_Elem;  VAR error: boolean);\r\r
159 VAR\r\r
160    n : COLAORD_Nodo;\r\r
161    np: COLAORD_Puntero;\r\r
162    m : COLAORD_Nodo;\r\r
163    mp : COLAORD_Puntero;\r\r
164 BEGIN\r\r
165         error := false;\r\r
166         np := l.primero;\r\r
167         WHILE ( np <> COLAORD_Nulo ) AND ( not error )\r\r
168         DO BEGIN\r\r
169                 COLAORD_Almac_Acceder( l.almac, np, n );\r\r
170                 error := devolver_clave_elem( n.elem ) = devolver_clave_elem( e );\r\r
171                 \r\r
172                 { cambio los punteros }\r\r
173                 np := n.sig;\r\r
174                 END;\r\r
175 \r\r
176         IF not error\r\r
177         THEN BEGIN\r\r
178                 { inserto como en una pila, adelante }  \r\r
179                 m.Elem := e;\r\r
180                 m.sig := l.primero;\r\r
181                 COLAORD_Almac_Reservar( l.almac, mp );\r\r
182                 COLAORD_Almac_Modificar( l.almac, mp, m );\r\r
183                 \r\r
184                 l.primero := mp;\r\r
185                 END;\r\r
186 END;\r\r
187 \r\r
188 { pre: no esta vacia }\r\r
189 PROCEDURE COLAORD_sacar ( VAR l: COLAORD_Cola; VAR e: Tipo_Elem);\r\r
190 VAR\r\r
191         n,m  : COLAORD_Nodo;\r\r
192         np, mp, ap, amp: COLAORD_Puntero;\r\r
193 BEGIN\r\r
194         mp := l.primero;\r\r
195         COLAORD_Almac_Acceder( l.almac, mp, m ); { este es el primer menor }\r\r
196         amp := COLAORD_Nulo;\r\r
197         np := m.sig; { y salto al siguiente para no hacer la comparacion dos veces }\r\r
198         ap := mp;\r\r
199 \r\r
200         { busco el menor }\r\r
201         WHILE np <> COLAORD_Nulo\r\r
202         DO BEGIN\r\r
203                 COLAORD_Almac_Acceder( l.almac, np, n );\r\r
204                 IF devolver_clave_elem( n.elem ) < devolver_clave_elem( m.elem )\r\r
205                 THEN BEGIN\r\r
206                         m := n;\r\r
207                         mp := np;\r\r
208                         amp :=  ap;\r\r
209                         END;\r\r
210                 \r\r
211                 { cambio los punteros }\r\r
212                 ap := np;\r\r
213                 np := n.sig;\r\r
214                 END;\r\r
215 \r\r
216         IF l.primero = mp THEN BEGIN\r\r
217                 { como estoy tocando el primero el primero es su siguiente }\r\r
218                 l.primero := m.sig;\r\r
219                 END\r\r
220         ELSE BEGIN\r\r
221                 COLAORD_Almac_Acceder( l.almac, amp, n );\r\r
222       n.sig := m.sig;\r\r
223                 COLAORD_Almac_Modificar( l.almac, amp, n );\r\r
224                 END;\r\r
225 \r\r
226         { libero el nodo del menor }\r\r
227         COLAORD_Almac_Liberar( l.almac, mp );\r\r
228 \r\r
229    { y se lo asigno al parametro }\r\r
230    e := m.Elem;\r\r
231 END;\r\r
232 \r\r
233 PROCEDURE COLAORD_vaciar ( VAR l: COLAORD_Cola );\r\r
234 VAR np : COLAORD_Puntero;\r\r
235     n : COLAORD_Nodo;\r\r
236 BEGIN\r\r
237    np := l.primero;\r\r
238    while( np <> COLAORD_Nulo ) do begin\r\r
239       COLAORD_Almac_Acceder( l.almac, np, n );\r\r
240       COLAORD_Almac_Liberar( l.almac, np );\r\r
241       np := n.sig;\r\r
242       end;\r\r
243    l.primero := COLAORD_Nulo;\r\r
244 END;\r\r
245 \r\r
246 { pre: 'a' y 'b' estan creadas y 'b' esta vacia }\r\r
247 { POST: 'b' tiene una copia de los elementos de 'a' y el corriente esta en el primero }\r\r
248 PROCEDURE COLAORD_copiar ( a : COLAORD_Cola; VAR b : COLAORD_Cola );\r\r
249 VAR np, mp, tmpp : COLAORD_Puntero;\r\r
250     n, m : COLAORD_Nodo;\r\r
251 BEGIN\r\r
252    if a.primero = COLAORD_Nulo then exit;\r\r
253    np := a.primero;\r\r
254    COLAORD_Almac_Acceder( a.almac, np, n );\r\r
255 \r\r
256    COLAORD_Almac_Reservar( b.almac, mp );\r\r
257    b.primero := mp;\r\r
258    m.elem := n.elem;\r\r
259 \r\r
260    while( n.sig <> COLAORD_Nulo ) do begin\r\r
261 \r\r
262       COLAORD_Almac_Reservar( b.almac, tmpp );\r\r
263       m.sig := tmpp;\r\r
264       COLAORD_Almac_Modificar( b.almac, mp, m );\r\r
265 \r\r
266       np := n.sig;\r\r
267       COLAORD_Almac_Acceder( a.almac, np, n );\r\r
268 \r\r
269       mp := tmpp;\r\r
270       m.elem := n.elem;\r\r
271 \r\r
272       end;\r\r
273    m.sig := COLAORD_Nulo;\r\r
274    COLAORD_Almac_Modificar( b.almac, mp, m );\r\r
275 END;\r\r
276 \r\r
277 end.\r\r
278 \r\r