/****
 BpmDj: Free Dj Tools
 Copyright (C) 1995-2007 Werner Van Belle

 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
****/

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "avltree.h"

#define LEFT_NODE(watte) (watte->left)
#define RIGHT_NODE(watte) (watte->right)
#define SET_LEFT_NODE(watte,to) (watte->left=to)
#define SET_RIGHT_NODE(watte,to) (watte->right=to)
#define POSITIVE_FLAG(watte) (watte->flag == 1)
#define NEGATIVE_FLAG(watte) (watte->flag == -1)
#define ZERO_FLAG(watte) (watte->flag == 0)
#define SET_ZERO_FLAG(watte) (watte->flag = 0)
#define SET_POSITIVE_FLAG(watte) (watte->flag = 1)
#define SET_NEGATIVE_FLAG(watte) (watte->flag = -1)
#define NULL_NODE Node<Key>::Null

template <class Key> Sentinel<Key> * Node<Key>::Null = new Sentinel<Key>();

//---------------------------------------------------------
//   The Sentinel
//---------------------------------------------------------
template <class Key> class Sentinel: public Node<Key>
{
public:
  virtual int compareAddData(Node<Key>*) {assert(0); return 0;};
  virtual int compareSearchData(Key)     {assert(0); return 0;};
  virtual void       print()             {assert(0); return;};
  virtual void       print(int)          { return; };
  virtual int        depth()             { return 0; };
  virtual int        count()             { return 0; };
  virtual bool       isNull()            { return true; };
  virtual bool       valid()             { return true; };
  virtual Node<Key>* search(Key)         { return this; };
  virtual Node<Key>* RotateLeft(int&)    {assert(0); return 0;};  
  virtual Node<Key>* RotateRight(int&)   {assert(0); return 0;};
  virtual Node<Key>* LeftFreedom(Node<Key>* &, int&)      {assert(0); return 0;};
  virtual Node<Key>* RightFreedom(Node<Key>* &, int&)     {assert(0); return 0;};
  virtual Node<Key>* GetLeftFreedom(Node<Key>* &, int&)   {assert(0); return 0;};
  virtual Node<Key>* GetRightFreedom(Node<Key>* &, int&)  {assert(0); return 0;};
  virtual Node<Key>* DeleteAvlNode(Key, int&)             { return this; };
  virtual Node<Key>* AddAvlNode(Node<Key>* who, int& depthchanged) { depthchanged=1; return who; };

};

//---------------------------------------------------------
//   Count calculation
//---------------------------------------------------------
template <class Key> int Node<Key>::count()
{
  return 1 + left->count() + right->count();
}

//---------------------------------------------------------
//   Depth calculation
//---------------------------------------------------------
template <class Key> int Node<Key>::depth()
{
  int l = left->depth();
  int r = right->depth();
  if (l>r) return l + 1;
  return r + 1;
}

//---------------------------------------------------------
//   Printing
//---------------------------------------------------------
template <class Key> void Node<Key>::print(int prefix)
{
  right->print(prefix + 1);
  for( int t = prefix; t > 0; t--) printf(".");
  print();
  int l = left->depth();
  int r = right->depth();
  printf(" left=%d, right=%d, count=%d ",l,r,count());
  // SANITY CHECK !!!
  if ( abs(l-r)>1
       || (l <  r  && ! flag >  0 ) 
       || (l >  r  && ! flag <  0 ) 
       || (l == r  && ! flag == 0 ) )
    printf("*********");
  printf("\n");
  left->print(prefix + 1);
}

//---------------------------------------------------------
//   Consistency validation
//---------------------------------------------------------
template <class Key> bool Node<Key>::valid()
{
  if (!left->valid()) return false;
  if (!right->valid()) return false;
  if (POSITIVE_FLAG(this))
    return left->depth() == right->depth() - 1 ;
  if (NEGATIVE_FLAG(this))
    return left->depth() == right->depth() + 1 ;
  return left->depth() == right->depth();
}


//---------------------------------------------------------
//   Search
//---------------------------------------------------------
template <class Key> Node<Key>* Node<Key>::search(Key watte)
{
  int compareResult = compareSearchData(watte);
  if (compareResult == 0 ) return this;
  if (compareResult == 1 ) return left->search(watte);
  if (compareResult == -1) return right->search(watte);
  return NULL_NODE;
}

//---------------------------------------------------------
//   Add
//---------------------------------------------------------

#define LEFT(WHO) WHO(Left,Right,LEFT_NODE,RIGHT_NODE,SET_LEFT_NODE,SET_RIGHT_NODE,\
	      NEGATIVE_FLAG,POSITIVE_FLAG,SET_NEGATIVE_FLAG,SET_POSITIVE_FLAG)
#define RIGHT(WHO) WHO(Right,Left,RIGHT_NODE,LEFT_NODE,SET_RIGHT_NODE,SET_LEFT_NODE,\
	      POSITIVE_FLAG,NEGATIVE_FLAG,SET_POSITIVE_FLAG,SET_NEGATIVE_FLAG)
#define CREATE_ROTATE(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
template <class Key> Node<Key>* Node<Key>::Rotate##lname(int& depthchanged)\
        {\
        Node<Key>* sec;\
	sec=RN(this);\
	assert(PF(this));\
	if (!(NF(sec)))\
	  {\
	     SRN(this,LN(sec));\
	     SLN(sec,this);\
	     if (PF(sec))\
	       {\
		  SET_ZERO_FLAG(this);\
		  SET_ZERO_FLAG(sec);\
		  depthchanged=1;\
		  return sec;\
	       }\
	     SPF(this);\
	     SNF(sec);\
	     return sec;\
	  }\
	  {\
	     Node<Key>* third=LN(sec);\
	     SLN(sec,RN(third));\
	     SRN(this,LN(third));\
	     SRN(third,sec);\
	     SLN(third,this);\
	     depthchanged=1;\
	     if (NF(third))\
	       {\
		  SPF(sec);\
		  SET_ZERO_FLAG(this);\
		  SET_ZERO_FLAG(third);\
		  return third;\
	       }\
	     if (ZERO_FLAG(third))\
	       {\
		  SET_ZERO_FLAG(sec);\
		  SET_ZERO_FLAG(third);\
		  SET_ZERO_FLAG(this);\
		  return third;\
	       }\
	     SET_ZERO_FLAG(sec);\
	     SNF(this);\
	     SET_ZERO_FLAG(third);\
	     return third;\
	  }\
     }

LEFT(CREATE_ROTATE);
RIGHT(CREATE_ROTATE);

#define CREATE_HANG(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF) {\
	SLN(this,LN(this)->AddAvlNode(who,heightchanged));\
	if (heightchanged) {\
	     if (ZERO_FLAG(this)) {\
		  SNF(this);\
		  depthchanged=1;\
		  return this; }\
	     if (PF(this)) {\
		  SET_ZERO_FLAG(this);\
		  return this; }\
	     heightchanged=0;\
	     Node<Key> *tmp = Rotate##rname(heightchanged);\
	     if (!heightchanged) depthchanged=1;\
	     return tmp; }\
	return this; }

template <class Key> Node<Key>* Node<Key>::AddAvlNode(Node<Key>* who, int& depthchanged)
{
  int heightchanged=0;
  int CompareResult=compareAddData(who);
  assert(CompareResult); // this means 'no duplicates'
  if (CompareResult > 0) LEFT(CREATE_HANG);
  RIGHT(CREATE_HANG);
}


//---------------------------------------------------------
//   Deletion
//---------------------------------------------------------
#define CREATE_FREEDOM(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
template <class Key> Node<Key>* Node<Key>::lname##Freedom (Node<Key>* &placetostorefreedom,int &heightchanged) {\
	if (RN(this)->isNull()) \
           {\
	     if ((LN(this))->isNull()) {\
		  placetostorefreedom=this;\
		  heightchanged=1;\
		  return NULL_NODE; }\
	     heightchanged=1;\
	     placetostorefreedom=this;\
	     return LN(this); \
           }\
           {\
	     int takverkleind=0;\
	     SRN(this, RN(this) -> lname##Freedom (placetostorefreedom,takverkleind));\
	     if (takverkleind) \
	       {\
		  if (NF(this)) return Rotate##rname (heightchanged);\
		  if (PF(this))\
		    {\
		       SET_ZERO_FLAG(this);\
		       heightchanged=1;\
		       return this;\
		    }\
		  SNF(this);\
		  return this;\
	       }\
	     return this;\
	  }\
     }\
\
template <class Key> Node<Key>* Node<Key>::Get##lname##Freedom(Node<Key>* &placetostorefreedom,int &heightchanged)\
     {\
	Node<Key>* lname;\
	assert(LN(this));\
	lname = LN(this);\
	if (RN( lname ))\
	  return lname -> lname##Freedom (placetostorefreedom, heightchanged);\
	heightchanged=1;\
	placetostorefreedom= lname;\
	return LN( lname );\
     }

LEFT(CREATE_FREEDOM)
RIGHT(CREATE_FREEDOM)

#define CREATE_ZAK(lname,rname,LN,RN,SLN,SRN,NF,PF,SNF,SPF)\
SLN(this,LN(this)->DeleteAvlNode(wie,takkleiner));\
if (takkleiner) {\
	if (NF(this)) {\
	     SET_ZERO_FLAG(this);\
	     heightchanged=1;\
	     return this; }\
	if (ZERO_FLAG(this)) {\
	     SPF(this);\
	     return this; }\
	return Rotate##lname (heightchanged); }\
return this;
	  
template <class Key> Node<Key>* Node<Key>::DeleteAvlNode(Key wie, int& heightchanged)
{
  int CompareResult,takkleiner=0;
  CompareResult=this->compareSearchData(wie);
  switch (CompareResult)
    {
    case -1: /* this<wie */ RIGHT(CREATE_ZAK);
    case 1: /* this>wie */ LEFT(CREATE_ZAK);
    case 0: /* this==wie */
      /* nu een opnderscheid maken voor welke kinderen de 
       * this heeft */
      if (LEFT_NODE(this)->isNull() && RIGHT_NODE(this)->isNull())
	{
	  heightchanged=1;
	  delete this;  // WVB !! Dangerours ???
	  return NULL_NODE;
	}
      if (LEFT_NODE(this)->isNull())
	{
	  Node<Key>* rechter;
	  rechter=RIGHT_NODE(this);
	  assert(POSITIVE_FLAG(this));
	  assert(rechter);
	  assert(LEFT_NODE(rechter)->isNull());
	  assert(RIGHT_NODE(rechter)->isNull());
	  heightchanged=1;
	  delete this; // WVB -- dangerous
	  return rechter;
	}
      if (RIGHT_NODE(this)->isNull())
	{
	  Node<Key>* linker;
	  linker=LEFT_NODE(this);
	  assert(NEGATIVE_FLAG(this));
	  assert(linker);
	  assert(LEFT_NODE(linker)->isNull());
	  assert(RIGHT_NODE(linker)->isNull());
	  heightchanged=1;
	  delete this;  // WVB -- dangerours ???
	  return linker;
	}
      if (POSITIVE_FLAG(this))
	{
	  Node<Key>* freedom;
	  SET_RIGHT_NODE(this,GetRightFreedom(freedom,heightchanged));
	  SET_LEFT_NODE(freedom,LEFT_NODE(this));
	  SET_RIGHT_NODE(freedom,RIGHT_NODE(this));
	  if (heightchanged) SET_ZERO_FLAG(freedom);
	  else SET_POSITIVE_FLAG(freedom);
	  delete this;   // WVB -- dangerous ???
	  return freedom;
	}
      if (NEGATIVE_FLAG(this))
	{
	  Node<Key>* freedom;
	  SET_LEFT_NODE(this,GetLeftFreedom(freedom,heightchanged));
	  SET_LEFT_NODE(freedom,LEFT_NODE(this));
	  SET_RIGHT_NODE(freedom,RIGHT_NODE(this));
	  if (heightchanged) SET_ZERO_FLAG(freedom);
	  else SET_NEGATIVE_FLAG(freedom);
	  delete this;  // WVB -- dangerours ??
	  return freedom;
	}
      if (ZERO_FLAG(this))
	{
	  Node<Key>* freedom;
	  int takverkleind=0;
	  SET_LEFT_NODE(this,GetLeftFreedom(freedom,takverkleind));
	  SET_LEFT_NODE(freedom,LEFT_NODE(this));
	  SET_RIGHT_NODE(freedom,RIGHT_NODE(this));
	  if (takverkleind) SET_POSITIVE_FLAG(freedom);
	  else  SET_ZERO_FLAG(freedom);
	  delete this;   // WVB -- dangerours
	  return freedom;
	}
    default: exit(57);
    }
}

//---------------------------------------------------------
//   Constructor and Wrappers
//---------------------------------------------------------

template <class Key> Node<Key>::Node()
{
  left = NULL;
  right = NULL;
}

template <class Key> AvlTree<Key>::AvlTree()
{
  init(); 
};

template <class Key> void AvlTree<Key>::init()
{
  root = Node<Key>::Null; 
};

template <class Key> void AvlTree<Key>::PurgeAll(Node<Key>* root)
{
  if (root && !root->isNull())
    {
      PurgeAll(root->left);
      PurgeAll(root->right);
      delete(root);
    }
}

template <class Key> AvlTree<Key>::~AvlTree()
{
  purge();
};

template <class Key> Node<Key>* AvlTree<Key>::AddAvlNode(Node<Key>* root, Node<Key>* who)
{
  if (who->isNull()) return root;
  who->left = NULL_NODE;
  who->right = NULL_NODE;
  who->flag = 0;
  int depthchanged=0;
  return root->AddAvlNode(who,depthchanged);
}

template <class Key> Node<Key>* AvlTree<Key>::DeleteAvlNode(Node<Key>* root, Key wie)
{
  int heightchanged=0;
  return root->DeleteAvlNode(wie,heightchanged);
}