//==============================================================================
//
//               Copyright (C) 2002  Dick van Oudheusden
//  
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this program; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2006/07/22 13:28:58 $ $Revision: 1.2 $
//
//==============================================================================

#include <stdlib.h>

#include "ofc/config.h"

#include "ofc/DText.h"
#include "ofc/DInt.h"
#include "ofc/DAvlTree.h"

#include "DInc.h"
#include "DTest.h"

//-Collections-----------------------------------------------------------------

void DAvlTree_test()
{
  DAvlTree   *tree = [DAvlTree alloc];
  DAvlTree   *copy = nil;
  
  int     i;
  int     c;  
  
  STARTTEST();
#if 0
  {
    DText  *key;
    DText  *val;
    
    [tree init :[DText class]];

    TEST([tree isEmpty]);

    key = [DText alloc]; [key init :"hello"];
    val = [DText alloc]; [val init :"test"];
    TEST([tree insert :key :val]);

    key = [DText alloc]; [key init :"bye"];
    val = [DText alloc]; [val init :"test"];
    TEST([tree insert :key :val]);

    TEST([tree length] == 2);

    key = [DText alloc]; [key init :"see you"];
    TEST(![tree has :key]);
    TEST(![tree delete   :key]);
  
    [key set :"bye"];
    TEST([tree has :key]);
    TEST([tree delete   :key]);
    TEST(![tree has :key]);

    [key set :"hello"];
    TEST([tree has :key]);

    TEST([tree length] == 1);

    [tree free];
  }
#endif
  tree = [DAvlTree alloc];

  [tree init :[DInt class]];

  {
    DInt *key = [[DInt alloc] init];
    DInt *val = nil;
    
    int ints[10000];
    
    i = 0;
    while (i < sizeof(ints) / sizeof(ints[0]))
    {
      ints[i] = rand();
      
      [key set :ints[i]];
      if (![tree has :key])
      {
        val = [key copy];

        [tree insert :key :val];
        
        i++;
      }
    }
    [key free];

    // TEST([tree check] == 0);
    
    c = 0;
    for (i = 0; i < sizeof(ints) / sizeof(ints[0]); i++)
    {
      DInt *key = [DInt alloc];

      [key init :ints[i]];
      
      if (![tree has :key])
        c++;
        
      [key free];
    }

    TEST(c == 0);
    // TEST([tree length] == [tree count]);

    
    // (Shallow) Copy the tree
    copy = [tree shallowCopy];
    
    TEST([tree length] == [copy length]);
    
    c = 0;
    for (i = 0; i < sizeof(ints) / sizeof(ints[0]); i++)
    {
      DInt *key = [DInt alloc];

      [key init :ints[i]];
    
      if ([tree get :key] != [copy get :key])
        c++;
        
      [key free];
    }

    TEST(c == 0);
    
    [copy shallowFree]; copy = nil;
    
    // Deep copy the tree
    copy = [tree copy];
    
    TEST([tree length] == [copy length]);
    
    c = 0;
    for (i = 0; i < sizeof(ints) / sizeof(ints[0]); i++)
    {
      DInt *key = [DInt alloc];

      [key init :ints[i]];
    
      if ([tree get :key] == [copy get :key]) // objects differ but ..
        c++;
      
      if ([[tree get :key] get] != [[copy get :key] get]) // contents the same
        c++;
      
      [key free];
    }

    TEST(c == 0);
    
    [copy free]; copy = nil;
  
    // test of keys and indirect the AvlIterator
    {
      DList *list         = [tree keys];
      DListIterator *iter = [DListIterator alloc];
      DInt  *key  = nil;
      DInt  *last = nil;

      TEST([list length] == [tree length]);
      
      [iter init :list];

      key = [iter first];
      while (key != nil)
      {
        if (last != nil)
          TEST([key get] > [last get]);

        last = key;          
        key = [iter next];
      }
      [iter free];
      [list free];
    }

    // test of rkeys and indirect the AvlIterator
    {
      DList *list         = [tree rkeys];
      DListIterator *iter = [DListIterator alloc];
      DInt  *key  = nil;
      DInt  *last = nil;

      TEST([list length] == [tree length]);
      
      [iter init :list];

      key = [iter first];
      while (key != nil)
      {
        if (last != nil)
          TEST([key get] < [last get]);

        last = key;          
        key = [iter next];
      }
      [iter free];
      [list free];
    }

    // test of objects and indirect the AvlIterator
    {
      DList *list         = [tree objects];
      DListIterator *iter = [DListIterator alloc];
      DInt  *obj  = nil;
      DInt  *last = nil;

      TEST([list length] == [tree length]);
      
      [iter init :list];

      obj = [iter first];
      while (obj != nil)
      {
        if (last != nil)
          TEST([obj get] > [last get]);

        last = obj;          
        obj = [iter next];
      }
      [iter free];
      [list free];
    }
    
    i = 0; c=0;
    while (i < sizeof(ints) / sizeof(ints[0]))
    {
      DInt *key = [DInt alloc];

      [key init :ints[i]];

      TEST([tree delete :key] != nil);

      [key free];

      i++;
    }    
  }
  [tree free];
  
  // TEST([tree length] == [tree count]);

  STOPTEST();
}