lexico.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

  Ejercicio tomado en el 1er parcial 16/04/02.
  Dadas dos listas de enteros L1 y L2, escribir una
  function LEXICORD (L1, L2: lista): boolean, que retorna
  true si la lista L1 es mayor que la L2 en sentido
  lexicogr\'afico, y false en caso contrario. El orden
  lexicogr\'afico es el orden alfab\'etico y puede
  definirse de la siguiente manera:

  1) si las dos listas son vacias, entonces son iguales
     (valor de retorno false);

  2) si L1 es vacia y L2 no lo es, entonces L1 < L2 es falso;
  3) si L2 es vacia y L1 no lo es, entonces L1 < L2 es true; 

  4) Si las dos listas no son vacias, y los primeros
     elementos son diferentes (digamos a_1 y b_1),
     entonces el valor de retorno es a_1 > b_1.
     Si los dos primeros elementos fueran iguales,
     entonces el valor de retorno ser\'a el
     correspondiente a las listas que se obtienen
     eliminando los primeros elementos.

  Asi, por ejemplo,

  a) Si L1 = [1 3 2 4 6] y L2 = [1 3 2 5], entonces L2 > L1
     y LEXICORD (L1, L2) retorna false;

  b) Si L1 = [1 3 3 4 5] y L2 = [1 3 3], entonces L1 > L2 y
     LEXICORD (L1, L2) retorna true;

  c) Si L1 = [1 3 3 4] y L2 = [1 3 3 4], entonces L1 = L2 y
     LEXICORD (L1, L2) retorna false.
  keywords: lista

FIN DE DESCRIPCION}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id:lexicord_p.pas 2002/04/12 00:17 mstorti Exp jdelia  $}
program lexicord_p;
uses u_lispif;
type
  lista = lispif;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function LEXICORD (L1, L2 : lista) : boolean;
var
  p, q : posicion;
begin
  { Posiciones sobre los elementos a comparar }
  p := L1.PRIMERO;
  q := L2.PRIMERO;
  while (p <> L1.FIN) and (q <> L2.FIN) do begin
    { Si los primeros elementos son diferentes}
    { entonces ya se pueden comparar          }
    if L1.RECUPERA (p) <> L2.RECUPERA (q) then begin
      LEXICORD := L1.RECUPERA (p) > L2.RECUPERA (q);
      exit ; end
    else begin { Si son iguales, avanzar posiciones }
      p := L1.SIGUIENTE (p);
      q := L2.SIGUIENTE (q);
    end ; {if}
  end; {while}
  { Se termino alguna de las listas. L1 es la mayor }
  { si contiene elementos }
  LEXICORD := p <> L1.FIN;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  L1, L2 : lista;
  n, i   : integer;
begin
  randomize ;
  for i := 1 to 20 do begin
    writeln ;
    writeln ('caso test ; i = ', i); 
    L1.ANULA;
    L2.ANULA;
  { Primero inserta una serie de numeros iguales}
    while random (4)<> 0 do begin
      n := random (10);
      L1.INSERTA (n, L1.FIN);
      L2.INSERTA (n, L2.FIN);
    end; {while}
  { inserta una cierta cantidad de numeros random en L1 }
    while random (2) <> 0 do begin
      n := random (10);
      L1.INSERTA (n, L1.FIN);
    end; {while}
  { inserta una cierta cantidad de numeros random en L2 }
    while random (2) <> 0 do begin
      n := random (10);
      L2.INSERTA (n, L2.FIN);
    end; {while}

  { Imprime listas }
    L1.IMPRIME ('L1: ');
    L2.IMPRIME ('L2: ');

  { Reporta la relacion entre L1 y L2} 
    if      LEXICORD (L1, L2) then
      writeln ('L1 > L2')
    else if LEXICORD (L2, L1) then
      writeln ('L1 < L2')
    else begin
      writeln ('L1 = L2')
    end ; {if}
    readln ;
  end; {i}
  writeln ;
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}