/* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
 * 
 * This software is provided 'as-is', without any express or implied
 * warranty. In no event will the authors be held liable for any damages
 * arising from the use of this software.
 * 
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 * 
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 * 
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 * 
 * 3. This notice may not be removed or altered from any source distribution.
 */

#include "dgStdafx.h"
#include "dgTree.h"

dgRedBackNode *dgRedBackNode::Minimum() const
{
  dgRedBackNode* ptr = (dgRedBackNode *) this;
  for (; ptr->m_left; ptr = ptr->m_left)
  {
  }
  return ptr;
}

dgRedBackNode *dgRedBackNode::Maximum() const
{
  dgRedBackNode* ptr = (dgRedBackNode *) this;
  for (; ptr->m_right; ptr = ptr->m_right)
  {
  }
  return ptr;
}

dgRedBackNode *dgRedBackNode::Prev() const
{
  if (m_left)
  {
    return m_left->Maximum();
  }

  dgRedBackNode* node = (dgRedBackNode *) this;
  dgRedBackNode* ptr = m_parent;
  for (; ptr && node == ptr->m_left; ptr = ptr->m_parent)
  {
    node = ptr;
  }
  return ptr;

}

dgRedBackNode *dgRedBackNode::Next() const
{

  if (m_right)
  {
    return m_right->Minimum();
  }

  dgRedBackNode* node = (dgRedBackNode *) this;
  dgRedBackNode* ptr = m_parent;
  for (; ptr && node == ptr->m_right; ptr = ptr->m_parent)
  {
    node = ptr;
  }
  return ptr;
}

// rotate node me to left 
void dgRedBackNode::RotateLeft(dgRedBackNode** const head)
{
  dgRedBackNode* const me = this;
  dgRedBackNode* const child = me->m_right;

  //establish me->m_right link 
  me->m_right = child->m_left;
  if (child->m_left != NULL)
  {
    child->m_left->m_parent = me;
  }

  // establish child->m_parent link 
  if (child != NULL)
  {
    child->m_parent = me->m_parent;
  }
  if (me->m_parent)
  {
    if (me == me->m_parent->m_left)
    {
      me->m_parent->m_left = child;
    }
    else
    {
      me->m_parent->m_right = child;
    }
  }
  else
  {
    *head = child;
  }

  // link child and me 
  child->m_left = me;
  if (me != NULL)
  {
    me->m_parent = child;
  }
}

// rotate node me to right  *
void dgRedBackNode::RotateRight(dgRedBackNode ** const head)
{
  dgRedBackNode* const me = this;
  dgRedBackNode* const child = me->m_left;

  // establish me->m_left link 
  me->m_left = child->m_right;
  if (child->m_right != NULL)
  {
    child->m_right->m_parent = me;
  }

  // establish child->m_parent link 
  if (child != NULL)
  {
    child->m_parent = me->m_parent;
  }
  if (me->m_parent)
  {
    if (me == me->m_parent->m_right)
    {
      me->m_parent->m_right = child;
    }
    else
    {
      me->m_parent->m_left = child;
    }
  }
  else
  {
    *head = child;
  }

  // link me and child 
  child->m_right = me;
  if (me != NULL)
  {
    me->m_parent = child;
  }
}

// maintain Red-Black tree balance after inserting node ptr   
void dgRedBackNode::InsertFixup(dgRedBackNode ** const head)
{
  dgRedBackNode* ptr = this;
  // check Red-Black properties 
  while ((ptr != *head) && (ptr->m_parent->GetColor() == RED))
  {
    // we have a violation 
    if (ptr->m_parent == ptr->m_parent->m_parent->m_left)
    {
      dgRedBackNode* const tmp = ptr->m_parent->m_parent->m_right;
      if (tmp && (tmp->GetColor() == RED))
      {
        // uncle is RED 
        ptr->m_parent->SetColor(BLACK);
        tmp->SetColor(BLACK);
        ptr->m_parent->m_parent->SetColor(RED);
        ptr = ptr->m_parent->m_parent;
      }
      else
      {
        // uncle is BLACK 
        if (ptr == ptr->m_parent->m_right)
        {
          // make ptr a left child 
          ptr = ptr->m_parent;
          ptr->RotateLeft(head);
        }

        ptr->m_parent->SetColor(BLACK);
        if (ptr->m_parent->m_parent)
        {
          ptr->m_parent->m_parent->SetColor(RED);
          ptr->m_parent->m_parent->RotateRight(head);
        }
      }
    }
    else
    {
      _ASSERTE(ptr->m_parent == ptr->m_parent->m_parent->m_right);
      // mirror image of above code 
      dgRedBackNode* const tmp = ptr->m_parent->m_parent->m_left;
      if (tmp && (tmp->GetColor() == RED))
      {
        //uncle is RED 
        ptr->m_parent->SetColor(BLACK);
        tmp->SetColor(BLACK);
        ptr->m_parent->m_parent->SetColor(RED);
        ptr = ptr->m_parent->m_parent;
      }
      else
      {
        // uncle is BLACK 
        if (ptr == ptr->m_parent->m_left)
        {
          ptr = ptr->m_parent;
          ptr->RotateRight(head);
        }
        ptr->m_parent->SetColor(BLACK);
        if (ptr->m_parent->m_parent->GetColor() == BLACK)
        {
          ptr->m_parent->m_parent->SetColor(RED);
          ptr->m_parent->m_parent->RotateLeft(head);
        }
      }
    }
  }
  (*head)->SetColor(BLACK);
}

//maintain Red-Black tree balance after deleting node x 
void dgRedBackNode::RemoveFixup(dgRedBackNode* const thisNode,
    dgRedBackNode ** const head)
{
  dgRedBackNode* ptr = this;
  dgRedBackNode* node = thisNode;
  while ((node != *head) && (!node || node->GetColor() == BLACK))
  {
    if (node == ptr->m_left)
    {
      if (!ptr)
      {
        return;
      }
      dgRedBackNode* tmp = ptr->m_right;
      if (!tmp)
      {
        return;
      }
      if (tmp->GetColor() == RED)
      {
        tmp->SetColor(BLACK);
        ptr->SetColor(RED);
        ptr->RotateLeft(head);
        tmp = ptr->m_right;
        if (!ptr || !tmp)
        {
          return;
        }
      }
      if ((!tmp->m_left || (tmp->m_left->GetColor() == BLACK))
          && (!tmp->m_right || (tmp->m_right->GetColor() == BLACK)))
      {
        tmp->SetColor(RED);
        node = ptr;
        ptr = ptr->m_parent;
        continue;
      }
      else if (!tmp->m_right || (tmp->m_right->GetColor() == BLACK))
      {
        tmp->m_left->SetColor(BLACK);
        tmp->SetColor(RED);
        tmp->RotateRight(head);
        tmp = ptr->m_right;
        if (!ptr || !tmp)
        {
          return;
        }
      }
      tmp->SetColor(ptr->GetColor());
      if (tmp->m_right)
      {
        tmp->m_right->SetColor(BLACK);
      }
      if (ptr)
      {
        ptr->SetColor(BLACK);
        ptr->RotateLeft(head);
      }
      node = *head;

    }
    else
    {
      if (!ptr)
      {
        return;
      }
      dgRedBackNode* tmp = ptr->m_left;
      if (!tmp)
      {
        return;
      }
      if (tmp->GetColor() == RED)
      {
        tmp->SetColor(BLACK);
        ptr->SetColor(RED);
        ptr->RotateRight(head);
        tmp = ptr->m_left;
        if (!ptr || !tmp)
        {
          return;
        }
      }

      if ((!tmp->m_right || (tmp->m_right->GetColor() == BLACK))
          && (!tmp->m_left || (tmp->m_left->GetColor() == BLACK)))
      {
        tmp->SetColor(RED);
        node = ptr;
        ptr = ptr->m_parent;
        continue;
      }
      else if (!tmp->m_left || (tmp->m_left->GetColor() == BLACK))
      {
        tmp->m_right->SetColor(BLACK);
        tmp->SetColor(RED);
        tmp->RotateLeft(head);
        tmp = ptr->m_left;
        if (!ptr || !tmp)
        {
          return;
        }
      }
      tmp->SetColor(ptr->GetColor());
      if (tmp->m_left)
      {
        tmp->m_left->SetColor(BLACK);
      }
      if (ptr)
      {
        ptr->SetColor(BLACK);
        ptr->RotateRight(head);
      }
      node = *head;
    }
  }
  if (node)
  {
    node->SetColor(BLACK);
  }
}

void dgRedBackNode::Unlink(dgRedBackNode ** const head)
{
//	dgRedBackNode *child;
//	dgRedBackNode *endNode;
//	dgRedBackNode *endNodeParent;
//	dgRedBackNode::REDBLACK_COLOR oldColor;

  dgRedBackNode* const node = this;
//	node->Kill();
  node->SetInTreeFlag(false);

  if (!node->m_left || !node->m_right)
  {
    // y has a NULL node as a child 
    dgRedBackNode* const endNode = node;

    // x is y's only child 
    dgRedBackNode* child = endNode->m_right;
    if (endNode->m_left)
    {
      child = endNode->m_left;
    }

    // remove y from the parent chain 
    if (child)
    {
      child->m_parent = endNode->m_parent;
    }

    if (endNode->m_parent)
    {
      if (endNode == endNode->m_parent->m_left)
      {
        endNode->m_parent->m_left = child;
      }
      else
      {
        endNode->m_parent->m_right = child;
      }
    }
    else
    {
      *head = child;
    }

    if (endNode->GetColor() == BLACK)
    {
      endNode->m_parent->RemoveFixup(child, head);
    }
//		endNode->Release();
//		delete endNode;

  }
  else
  {

    // find tree successor with a NULL node as a child 
    dgRedBackNode* endNode = node->m_right;
    while (endNode->m_left != NULL)
    {
      endNode = endNode->m_left;
    }

    _ASSERTE(endNode);
    _ASSERTE(endNode->m_parent);
    _ASSERTE(!endNode->m_left);

    // x is y's only child 
    dgRedBackNode* const child = endNode->m_right;

    _ASSERTE(
        (endNode != node->m_right) || !child || (child->m_parent == endNode));

    endNode->m_left = node->m_left;
    node->m_left->m_parent = endNode;

    dgRedBackNode* endNodeParent = endNode;
    if (endNode != node->m_right)
    {
      if (child)
      {
        child->m_parent = endNode->m_parent;
      }
      endNode->m_parent->m_left = child;
      endNode->m_right = node->m_right;
      node->m_right->m_parent = endNode;
      endNodeParent = endNode->m_parent;
    }

    if (node == *head)
    {
      *head = endNode;
    }
    else if (node == node->m_parent->m_left)
    {
      node->m_parent->m_left = endNode;
    }
    else
    {
      node->m_parent->m_right = endNode;
    }
    endNode->m_parent = node->m_parent;

    dgRedBackNode::REDBLACK_COLOR oldColor = endNode->GetColor();
    endNode->SetColor(node->GetColor());
    node->SetColor(oldColor);

    if (oldColor == BLACK)
    {
      endNodeParent->RemoveFixup(child, head);
    }
//		node->Release();
//		delete node;
  }
}

void dgRedBackNode::Remove(dgRedBackNode ** const head)
{
  Unlink(head);
  delete this;
}

void dgRedBackNode::RemoveAllLow()
{
  if (m_left)
  {
    m_left->RemoveAllLow();
  }
  if (m_right)
  {
    m_right->RemoveAllLow();
  }
  SetInTreeFlag(false);
//	Kill();
//	Release();
  delete this;
}

void dgRedBackNode::RemoveAll()
{
  dgRedBackNode* root = this;
  for (; root->m_parent; root = root->m_parent)
    ;
  root->RemoveAllLow();
}

