//
// Copyright (C) 2000-2002 Andrey Slepuhin <pooh@msu.ru>
//
// libp++ 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.
//
// libp++ 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 libp++; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// $Source$
// $Revision$
// $Date$
// Author: Andrey Slepuhin <pooh@msu.ru>

#include "pxx_chunk_allocator_block_header.ih"
#include "pxx_common.ih"

namespace pxx
{

CABlockHeader* CABlockHeader::node_restore_left_balance (int _old_balance)
{
  if (left == null) balance += 1;
  else if ((left->balance != _old_balance) && (left->balance == 0))
    balance += 1;
  if (balance > 1) return node_balance();
  return this;
}

CABlockHeader* CABlockHeader::node_restore_right_balance (int _old_balance)
{
  if (right == null) balance -= 1;
  else if ((right->balance != _old_balance) && (right->balance == 0))
    balance -= 1;
  if (balance < -1) return node_balance();
  return this;
}

CABlockHeader* CABlockHeader::node_remove_leftmost (CABlockHeader** _leftmost)
{
  int old_balance;
  if (left == null) {
    *_leftmost = this;
    return right;
  }
  old_balance = left->balance;
  left = left->node_remove_leftmost(_leftmost);
  return node_restore_left_balance(old_balance);
}

CABlockHeader* CABlockHeader::node_remove (CABlockHeader* _key)
{
  int old_balance;
  CABlockHeader* res = this;
  CABlockHeader* new_root;
  if (_key == this) {
    if (right == null) {
      res = left;
    } else {
      old_balance = right->balance;
      right = right->node_remove_leftmost(&new_root);
      new_root->left = left;
      new_root->right = right;
      new_root->balance = balance;
      res = new_root->node_restore_right_balance(old_balance);
    }
  } else if (_key < this) {
    if (left != null) {
      old_balance = left->balance;
      left = left->node_remove(_key);
      res = node_restore_left_balance(old_balance);
    }
  } else {
    if (right != null) {
      old_balance = right->balance;
      right = right->node_remove(_key);
      res = node_restore_right_balance(old_balance);
    }
  }
  return res;
}

CABlockHeader* CABlockHeader::node_rotate_left ()
{
  CABlockHeader* rt;
  int a_bal, b_bal;

  rt = right;

  right = rt->left;
  rt->left = this;

  a_bal = balance;
  b_bal = rt->balance;

  if (b_bal <= 0) {
    if (a_bal >= 1) rt->balance = b_bal - 1;
    else rt->balance = a_bal + b_bal - 2;
    balance = a_bal - 1;
  } else {
    if (a_bal <= b_bal) rt->balance = a_bal - 2;
    else rt->balance = b_bal - 1;
    balance = a_bal - b_bal - 1;
  }

  return rt;
}

CABlockHeader* CABlockHeader::node_rotate_right ()
{
  CABlockHeader* lt;
  int a_bal, b_bal;

  lt = left;

  left = lt->right;
  lt->right = this;

  a_bal = balance;
  b_bal = lt->balance;

  if (b_bal <= 0) {
    if (b_bal > a_bal) lt->balance = b_bal + 1;
    else lt->balance = a_bal + 2;
    balance = a_bal - b_bal + 1;
  } else {
    if (a_bal <= -1) lt->balance = b_bal + 1;
    else lt->balance = a_bal + b_bal + 2;
    balance = a_bal + 1;
  }

  return lt;
}

CABlockHeader* CABlockHeader::node_balance ()
{
  CABlockHeader* res = this;
  if (balance < -1) {
    if (left->balance > 0)
      left = left->node_rotate_left();
    res = node_rotate_right();
  } else {
    if (right->balance < 0)
      right = right->node_rotate_right();
    res = node_rotate_left();
  }
  return res;
}

CABlockHeader* CABlockHeader::node_insert (CABlockHeader* _key)
{
  CABlockHeader* res = this;
  int old_balance;
  if (_key < this) {
    if (left != null) {
      old_balance = left->balance;
      left = left->node_insert(_key);
      if ((old_balance != left->balance) && (left->balance != 0))
        balance -= 1;
    } else {
      left = _key;
      balance -= 1;
    }
  } else {
    if (right != null) {
      old_balance = right->balance;
      right = right->node_insert(_key);
      if ((old_balance != right->balance) && (right->balance != 0))
        balance += 1;
    } else {
      right = _key;
      balance += 1;
    }
  }
  if ((balance < -1) || (balance > 1))
    res = node_balance();
  return res;
}

}