void find_in_tree(const btree<T> &b, T val) {
  typename btree<T>::const_iterator iter = std::find(b.begin(), b.end(), val);
  if (iter == b.end()) 
    std::cout << val << " not found" << std::endl;
  else
    std::cout << val << " found" << std::endl;
}

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
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());
}

void  tree_union (btree<int> &A, 
	          btree<int> &B, 
	          btree<int> &C, 
	          bool (*fun) (int x,int y,int &z),int undef=0) {
  tree_union (A, A.begin(), B, B.begin(),
	      C, C.begin(), fun, undef);
} 

bool semejante_p (btree &T,iterator_t nt,
	      btree &Q,iterator_t nq) { 
  if (nt==T.end() xor nq==Q.end()) return false;
  if (nt==T.end()) return true;
  return semejante_p(T,nt.right(),Q,nq.right()) &&
    semejante_p(T,nt.left(),Q,nq.left());
}

// -------------------------------------------------------------------
int cont_nod_prof(btree<int> &A,btree<int>::iterator n,
		  int prof) {
  if (n==A.end()) return 0;
  else return (prof<=0) 
	 + cont_nod_prof (A,n.left(),prof-1) 
	 + cont_nod_prof (A,n.right(),prof-1);
}

// Esta es la funcion "wrapper" correspondiente. 
void  tree_intersection(btree<int> &A, 
               	        btree<int> &B, 
		        btree<int> &C, 
                        bool (*fun) (int x,int y,int &z)) {
  tree_intersection (A, A.begin(),
		     B, B.begin(),
		     C, C.begin(),
		     fun);
}

T reduce (btree <T> & Q,
          T (*f_asociat) (T,T),
          T   v_ini) {
    T z ;
    if (Q.begin() != Q.end())
        z = reduce (Q, Q.begin (), f_asociat, v_ini, f_iden<T>);
    else
        z = v_ini;
    return z ;
}

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);
}

static void test_dupkeys (const btree<V> & t, int k1, int k2,
                          int expected_key,
                          const V expected_value1, const V expected_value2)
{
    typename btree<V>::query_answer query_result
        = t.range_query (typename btree<V>::key_range(k1, k2));
    BOOST_CHECK_EQUAL (query_result.size(), 2);
    BOOST_CHECK_EQUAL (query_result[0].first, expected_key);
    BOOST_CHECK_EQUAL (query_result[0].second, expected_value1);
    BOOST_CHECK_EQUAL (query_result[1].first, expected_key);
    BOOST_CHECK_EQUAL (query_result[1].second, expected_value2);
}

void tareas (btree <T> & Q) {
    T     i ;
    T cero = 0 ;
    T semilla = INT_MAX ;
    bool  b ;

    cout << endl ;
    cout << "+++++++++++++++++++++++++++++++++++++++++++++++ " << endl ;
    cout << "Arbol ; Q: ";
    Q.lisp_print ();
    cout << endl;

    b = reduce (Q, and_f,  true, evenp) ;
    cout << endl ;
    cout << "todos pares   ? : " << (b ? "si" : "no") << endl;

    b = reduce (Q, and_f,  true,  oddp) ;
    cout << endl ;
    cout << "todos impares ? : " << (b ? "si" : "no") << endl;

    b = reduce (Q,  or_f, false, evenp) ;
    cout << endl ;
    cout << "alguno par    ? : " << (b ? "si" : "no") << endl;

    b = reduce (Q,  or_f, false, oddp) ;
    cout << endl ;
    cout << "alguno impar  ? : " << (b ? "si" : "no") << endl;

    i = reduce (Q, max, -semilla) ;
    cout << endl ;
    cout << "max. etiquetas  = " << i << endl;

    i = reduce (Q, min, semilla) ;
    cout << endl ;
    cout << "min. etiquetas  = " << i << endl;

    i = reduce (Q, suma, cero) ;
    cout << endl ;
    cout << "suma etiquetas  = " << i << endl;

    i = reduce (Q, root, cero) ;
    cout << endl ;
    cout << "norma L2        = " << i << endl;

    i = reduce (Q, suma, cero, square) ;
    cout << endl ;
    cout << "suma cuadrados etiquetas = " << i << endl;

}

static void test_existing (const btree<V, K> & t, const K k1, const K k2,
                           const K expected_key, const V expected_value)
{
    typename btree<V, K>::query_answer query_result
        = t.range_query (typename btree<V, K>::key_range(k1, k2));
    if (query_result.size() != 1)
    {
        std::cerr << "test_existing: expected_key = " << expected_key << '\n';
        BOOST_CHECK_EQUAL (query_result.size(), 1);
    }
    else
    {
        BOOST_CHECK_EQUAL (query_result[0].first, expected_key);
        BOOST_CHECK_EQUAL (query_result[0].second, expected_value);
    }
}

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
void packleft(btree<int> &T,btree<int>::iterator n) {
  // Si el arbol esta vacio no hay que hacer nada
  if (n==T.end()) return;
  // `l,r' son los hijos
  btree<int>::iterator l = n.left(), r = n.right();
  // Solo en el caso de que `l' es vacio y `r'
  // no, entonces hay que hacer un splice.
  // Notar que hay que refrescar `l,r'
  if (l==T.end() && r!=T.end()) l = T.splice(l,r);
  r = n.right();
  // Aplica recursivamente a `l' y `r'
  packleft(T,l);
  packleft(T,r);
}

//---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>
// 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);
}

///void foo(const btree<int> &b) {
void foo(btree<int> &b) {
  std::copy(b.begin(), b.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}

void 
huffman(const vector<double> &prob,btree<int> &T) {
  typedef list<huffman_tree> bosque_t;

  // Contiene todos los arboles
  bosque_t bosque;
  // Numero de caracteres del codigo
  int N = prob.size();
  // Crear los arboles iniciales poniendolos en
  // una lista Los elementos de la lista contienen
  // la probabilidad de cada caracter y un arbol
  // con un solo nodo. Los nodos interiores del
  // arbol tienen un -1 (es solo para
  // consistencia) y las hojas tienen el indice
  // del caracter. (entre 0 y N-1)
  for (int j=0; j<N; j++) {
    // Agrega un nuevo elemento a la lista
    bosque_t::iterator htree = 
      bosque.insert(bosque.begin(),huffman_tree());
    htree->p = prob[j];
    htree->T.insert(htree->T.begin(),j);
  }

  // Aqui empieza el algoritmo de Huffman.
  // Tmp va a contener el arbol combinado
  btree<int> Tmp;
  for (int j=0; j<N-1; j++) {
    // En la raiz de Tmp (que es un nodo interior)
    // ponemos un -1 (esto es solo para chequear).
    Tmp.insert(Tmp.begin(),-1);
    // Tmp_p es la probabilidad del arbol combinado
    // (la suma de las probabilidades de los dos subarboles)
    double Tmp_p = 0.0;
    // Para `k=0' toma el menor y lo pone en el
    // hijo izquierdo de la raiz de Tmp. Para `k=1' en el
    // hijo derecho. 
    for (int k=0; k<2; k++) {
      // recorre el `bosque' (la lista de arboles)
      //  busca el menor. `qmin' es un iterator al menor
      bosque_t::iterator q = bosque.begin(), qmin=q;
      while (q != bosque.end()) {
	if (q->p < qmin->p) qmin = q;
	q++;
      }
      // Asigna a `node' el hijo derecho o izquierdo
      // de la raiz de `Tmp' dependiendo de `k'
      btree<int>::iterator node = Tmp.begin();
      node = (k==0 ? node.left() : node.right());
      // Mueve todo el nodo que esta en `qmin'
      // al nodo correspondiente de `Tmp'
      Tmp.splice(node,qmin->T.begin());
      // Acumula las probabilidades
      Tmp_p += qmin->p;
      // Elimina el arbol correspondiente del bosque. 
      bosque.erase(qmin);
    }
    // Inserta el arbol combinado en el bosque
    bosque_t::iterator r = 
      bosque.insert(bosque.begin(),huffman_tree());
    // Mueve todo el arbol de `Tmp' al nodo
    // recien insertado
    r->T.splice(r->T.begin(),Tmp.begin());
    // Pone la probabilidad en el elemento de la
    // lista
    r->p = Tmp_p;
  }
  // Debe haber quedado 1 solo elemento en la lista
  assert(bosque.size()==1);
  // Mueve todo el arbol que quedo a `T'
  T.clear();
  T.splice(T.begin(),bosque.begin()->T.begin());
}

static void test_nonexisting (const btree<V, K> & t, const K k1, const K k2)
{
    typename btree<V, K>::query_answer query_result
        = t.range_query (typename btree<V, K>::key_range(k1, k2));
    BOOST_CHECK_EQUAL (query_result.size(), 0);
}