compbtree.cpp

//__INSERT_LICENSE__
// $Id$

#include <list>
#include <cstdio>
#include "./btree.h"
#include "./btreetools.h"
#include "./util.h"

using namespace aed;
using namespace std;

/* COMIENZO DE DESCRIPCION 

   __USE_WIKI__
   Se define una relaci\'on de orden
   entre \'arboles binarios de enteros de la siguiente forma: 
   #A<B# si #a<b#, o bien ({\tt a=b} y {\tt Ai < Bi}), o 
   bien ({\tt a=b} y #Ai=Bi# y {\tt Ad<Bd}), donde 
   #a#, #b# son las ra\'{\i}ces y #Ai#, #Ad#, #Bi#, #Bd# 
   son los sub\'arboles izquierdos y derechos de #A# y #B#. 
   Consigna: Escribir una funci\'on 
   #bool es_menor(tree<int> &A,tree<int> &B)# que retorna
   verdadero si #A < B#. 
   [Tomado en el 2do parcial 26/5/2005]. 
   keywords: arbol binario

   FIN DE DESCRIPCION */

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
bool es_menor(btree<int> &T1,btree<int>::iterator n1,
	      btree<int> &T2,btree<int>::iterator n2) {
  // Si los dos estan vacios, entonces no cae en
  // ninguno de los casos especificados y debe
  // retornar false. 
  if (n1==T1.end() && n2==T2.end()) return false;
  // Si `n1==end()' y `n2!=end()' entonces
  // `*n1<*n2' y debe retornar `true'. 
  if (n1==T1.end()) return true;
  // Si `n1!=end()' y `n2==end()' entonces
  // `*n1>*n2' y no entra en ninguno de los casos,
  // por lo tanto debe retornar `false'. 
  if (n2==T2.end()) return false;
  // Las dos raices son dereferenciables.
  // Si son distintas ya puede retornar un valor. 
  if (*n1 < *n2) return true;
  if (*n1 > *n2) return false;

  // Si llega aqui, las dos raices son dereferenciables
  // e iguales. Hay que comparar los arboles de los hijos. 

  // Si `Ai' y `Bi' son diferentes retornar un valor...
  if (es_menor(T1,n1.left(),T2,n2.left()))
    return true;
  if (es_menor(T2,n2.left(),T1,n1.left()))
    return false;
  // ... finalmente retorna el valor de comparacion
  // de los hijos derechos. 
  return es_menor(T1,n1.right(),T2,n2.right());
}

// `wrapper'
bool es_menor(btree<int> &T1,btree<int> &T2) {
  return es_menor(T1,T1.begin(),T2, T2.begin());
}

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
// Cuando se define una relacion de orden vimos que basta
// con definir <, >, <= o >=.  Una alternativa es una
// funcion `comp(a,b)' que retorna -1 si T1<T2, 0 si T1==T2,
// +1 si T1>T2. (En Perl es el operador `<=>').
// Esta funcion seria el operador `comp' para
// arboles binarios. Ademas, esta implementacion
// permite pasar una funcion de comparacion
// (programacion funcional)
int comp_btree(btree<int> &T1,btree<int>::iterator n1,
	    btree<int> &T2,btree<int>::iterator n2,
	    int (*comp)(int x,int y)) {
  // Si son Lambda => son iguales. 
  if (n1==T1.end() && n2==T2.end()) return 0;
  // Si `n1==end()' y `n2!=end()'
  // entonces `*n1<*n2'. 
  // debe retornar -1. 
  if (n1==T1.end()) return -1;
  // Si `n1!=end()' y `n2==end()'
  // entonces `*n1>*n2'. 
  if (n2==T2.end()) return +1;
  // Si `comp(*n1,*n2)!=0' entonces debe
  // retornar el valor de `comp'
  int v = comp(*n1,*n2);
  if (v) return v;
  // Si `comp_btree(Ai,Bi) != 0' entonces debe
  // retornar el valor.
  v = comp_btree(T1,n1.left(),T2,n2.left(),comp);
  if (v) return v;
  // Retorna el valor `comp_btree(Ai,Bi) != 0'
  return comp_btree(T1,n1.right(),T2,n2.right(),comp);
}

// `wrapper'
int comp_btree(btree<int> &T1, btree<int> &T2,
	    int (*comp)(int x,int y)) {
  comp_btree(T1,T1.begin(),T2,T2.begin(),comp);
}

// Funcion de comparacion para enteros. 
int comp(int x,int y) {
  return (y<x) - (x<y);
}

// Funcion de comparacion para enteros,
// correspondiente a la relacion de orden (debil)
// |a|<|b|
int comp_abs(int x,int y) {
  int yy = abs(y);
  int xx = abs(x);
  return (yy<xx) - (xx<yy);
}

int M=5;

int f(int x) { return x-M/2; }

bool equalp(btree<int> &A, btree<int>::iterator a, 
	    btree<int> &B, btree<int>::iterator b, 
	    bool (*eq)(int x,int y)) {
  if ((a == A.end()) != (b == B.end())) return false;
  if (a == A.end()) return true;
  if (!eq(*a,*b)) return false;
  return equalp(A,a.left(),B,b.left(),eq) &&
    equalp(A,a.right(),B,b.right(),eq);
}

bool equalp(btree<int> &A, btree<int> &B, 
	    bool (*eq)(int x,int y)) {
  return equalp(A,A.begin(),B,B.begin(),eq);
}

bool odd(int x) { return x %2; }
bool equal(int x,int y) { return x==y; }

int main() {
#if 1
  const int N=10000;
  typedef btree<int> tree_t;
  typedef tree_t::iterator node_t;
  typedef list<tree_t> list_t;
  typedef list_t::iterator iter_t;
  list_t L;
  tree_t A;
  // Genera una lista de `N' arboles.
  // La lista esta ordenada de aceuerdo
  // a `es_menor'
  for (int j=0; j<N; j++) {
    A.clear();
    double p=0.2;
    make_random_btree(A,M,p);
    apply(A,f);
    iter_t Q = L.begin();
    while (Q!=L.end() && !es_menor(A,*Q)) {
      // Se chequea consistencia entre `es_menor'
      // y `comp_btree'.
      assert(comp_btree(*Q,A,comp) == 
	     (es_menor(A,*Q)-es_menor(*Q,A)));
      Q++;
    }
    // Aqui se hace una copia 
    L.insert(Q,A);
  }
  
  // Imprime todos los arboles en forma ordenada
  iter_t Q = L.begin();
  while (Q!=L.end()) {
    Q->lisp_print();
    printf("\n");
    Q++;
  }

  // Verifica transitividad. 
  // Si `es_menor' y `comp_btree' representan
  // relaciones de orden, entonces se puede comparar
  // cualquier par de arboles Q,R tal que Q esta antes
  // que R en la lista y debe
  // ser Q <= R
  Q = L.begin();
  while (Q!=L.end()) {
    iter_t R = Q;
    R++;
    while (R!=L.end()) {

      if (es_menor(*R,*Q)) {
	printf("error!!!: Q>R segun es_menor()!! Q: ");
	Q->lisp_print();
	printf("\nQ: ");
	R->lisp_print();
	printf("\n");
      }

      if (comp_btree(*Q,*R,comp)>0) {
	printf("error!! Q>R segun comp_btree()!! Q: ");
	Q->lisp_print();
	printf("\nQ: ");
	R->lisp_print();
	printf("\n");
      }
      R++;
    }
    Q++;
  }

#else
  const int N=10;
  btree<int> A,B;
  for (int j=0; j<N; j++) {
    A.clear();
    B.clear();
    double p=0.2;
    make_random_btree(A,M,p);
    apply(A,f);
    make_random_btree(B,M,p);
    apply(B,f);
    printf("-----------------\nA, B: \n");
    A.lisp_print();
    printf("\n");
    B.lisp_print();
    printf("\n");
    printf("A==B? %d\n",equalp(A,B,equal));
  }
#endif
}