#include <Standard_OutOfRange.hxx>
#include <Standard_NoSuchObject.hxx>
#include <Standard_NoMoreObject.hxx>
#include <PCollection_IsNotRoot.hxx> 
#include <PCollection_IsNullTree.hxx> 
#include <PCollection_IsContained.hxx>

// ----------------------------------------------------------------------
// Copyright: 	Matra-Datavision 1992
// File:	PCollection_HArbitraryTree.gxx
// Created:	Aug, 5 1992
// Author:      Mireille MERCIEN
// ----------------------------------------------------------------------

// -----------
// constructor :
// -----------
PCollection_HArbitraryTree::PCollection_HArbitraryTree(const Item& T) 
{
  MyItem = T;
  MyChildren = new PCollection_SeqArbitraryTree;
 } 

// -----------------------------------------------
// Children : Returns the list of children of me
// -----------------------------------------------
Handle(PCollection_SeqArbitraryTree) 
       PCollection_HArbitraryTree::Children() const 
{
   return MyChildren;
}

// ----------------------
// Child : returns a child 
// ----------------------
Handle(PCollection_HArbitraryTree) 
    PCollection_HArbitraryTree::Child(const Standard_Integer Index) const
{
   return MyChildren->Value(Index);
}  

// ----------------------------------------------
// Value : returns the value of the current tree
// ----------------------------------------------
Item PCollection_HArbitraryTree::Value() const
{
   return MyItem;
}

// ----------------------------------------------------
// NbChildren : Number of children in the current tree 
// ----------------------------------------------------
Standard_Integer PCollection_HArbitraryTree::NbChildren() const
{
      return (MyChildren->Length());
}

// -------------------------------------------------------
// IsLeaf : Returns True if the current tree has no child
// -------------------------------------------------------
Standard_Boolean PCollection_HArbitraryTree::IsLeaf() const
{
   return (MyChildren->IsEmpty());
}

// ----------------------
// Parent
// ----------------------
Handle(PCollection_HArbitraryTree) PCollection_HArbitraryTree::Parent() const
{
   return MyParent;
}

// ----------------------
// IsRoot
// ---------------------
Standard_Boolean PCollection_HArbitraryTree::IsRoot() const
{
   return (MyParent.IsNull());
}
 
// ---------------------------------------------
// Root : Returns the root of the current tree
// ---------------------------------------------
Handle(PCollection_HArbitraryTree) PCollection_HArbitraryTree::Root() const
{
   Handle(PCollection_HArbitraryTree) AParent;
   AParent = this;
   while ( !AParent->IsRoot() )  AParent = AParent->Parent();
   return AParent;
}

// ----------------------------------------------------------------
   // LeftSibling : returns the left neighbour of the current tree
// ----------------------------------------------------------------
Handle(PCollection_HArbitraryTree) PCollection_HArbitraryTree::LeftSibling() const
{
   Handle(PCollection_HArbitraryTree) MySelf,TheParent,NullTree;
   Handle(PCollection_SeqArbitraryTree) TheBrothers;
   NullTree.Nullify();
   MySelf = this;
   if (MySelf->IsRoot()) return NullTree;
   TheBrothers = (MySelf->Parent())->Children();
   Standard_Integer TheIndex = TheBrothers->Location(1,MySelf);
   if (TheIndex <= 1) 
       return NullTree; 
   else
       return (TheBrothers->Value(TheIndex-1));  
}   

// ---------------------------------------------------------------
// RightSibling : returns the right neighbour of the current tree
// ---------------------------------------------------------------
Handle(PCollection_HArbitraryTree) PCollection_HArbitraryTree::RightSibling() const
{
   Handle(PCollection_HArbitraryTree) MySelf,TheParent,NullTree;
   Handle(PCollection_SeqArbitraryTree) TheBrothers;
   NullTree.Nullify();
   MySelf = this;
    if (MySelf->IsRoot()) return NullTree;
   TheBrothers = (MySelf->Parent())->Children();
   Standard_Integer TheIndex = TheBrothers->Location(1,MySelf);
   if (TheIndex == TheBrothers->Length()) 
       return NullTree; 
   else
       return (TheBrothers->Value(TheIndex+1));  
}   

// --------------------------------------------------------------------
// Contains : checks if the tree Atree is contained by the current one
// --------------------------------------------------------------------
Standard_Boolean PCollection_HArbitraryTree::Contains
     (const Handle(PCollection_HArbitraryTree)& ATree) const
{
  if (ATree.IsNull()) PCollection_IsNullTree::Raise();
  Handle(PCollection_HArbitraryTree) MySelf = this;
  Standard_Boolean IsFound = Standard_False;
  PCollection_ATPreOrderIterator Iter(MySelf); 
  while (!IsFound && Iter.More())  {
      if (Iter.Value() == ATree)  IsFound = Standard_True;
      Iter.Next();
    }
  return IsFound;  
}

// -------------------------------------------------
// SetValue : changes the value of the current tree
// -------------------------------------------------
void PCollection_HArbitraryTree::SetValue(const Item& T) 
{
   MyItem = T;
}

// ---------------------------------------------------------
// SetParent : changes the parent value of the current tree
// ---------------------------------------------------------
void PCollection_HArbitraryTree::SetParent
       (const Handle(PCollection_HArbitraryTree)& ATree) 
{
   MyParent = ATree;
}

// ---------------------------------------------------------------------
// SwapChild : replace, in the current tree, the child at the range
//             <Index> by the tree <ATree> and conversely
// ---------------------------------------------------------------------
void PCollection_HArbitraryTree::SwapChild
       (const Standard_Integer Index,Handle(PCollection_HArbitraryTree)& ATree) 
{
   if (!ATree.IsNull() && !ATree->IsRoot()) PCollection_IsNotRoot::Raise(); 
   Handle (PCollection_HArbitraryTree) TempTree = ATree;
   Handle (PCollection_HArbitraryTree) NullTree;
   NullTree.Nullify();
// ... Update the returned tree
   ATree = Child(Index);   
   ATree->SetParent(NullTree);
// ... Update the current tree
   if (! TempTree.IsNull()) InsertChildAfter(Index,TempTree);
   MyChildren->Remove(Index);   
}

// -----------------------------------------------------------------
// SwapChildren : TradeOff between two subtrees in the current tree
// -----------------------------------------------------------------
void PCollection_HArbitraryTree::SwapChildren
          ( const Handle(PCollection_HArbitraryTree)& Subtree1,
            const Handle(PCollection_HArbitraryTree)& Subtree2    )  
{  
   if (Subtree1.IsNull()  || Subtree2.IsNull())
                                     PCollection_IsNullTree::Raise();   
   if (!Contains(Subtree1) || !Contains(Subtree2)) 
                                     Standard_NoSuchObject::Raise();
   if (Subtree1->Contains(Subtree2) || Subtree1->Contains(Subtree2))
                                     PCollection_IsContained::Raise(); 
   Handle(PCollection_HArbitraryTree) Parent1 = Subtree1->Parent(); 
   Handle(PCollection_HArbitraryTree) Parent2 = Subtree2->Parent();
   Handle(PCollection_SeqArbitraryTree) 
                                    Children1 = Parent1->Children(); 
   Handle(PCollection_SeqArbitraryTree)  
                                    Children2 = Parent2->Children(); 

// ... Searching the index of the subtrees. 
   Standard_Integer Ind1 = Children1->Location(1,Subtree1);
   Standard_Integer Ind2 = Children2->Location(1,Subtree2);
// ... Insertion of Subtree2
   Handle(PCollection_HArbitraryTree) NullTree;
   NullTree.Nullify();
   Subtree2->SetParent(NullTree);
   Parent1->InsertChildAfter(Ind1,Subtree2);
   Children1->Remove(Ind1);
// ... Insertion of Subtree1
   Subtree1->SetParent(NullTree);
   Parent2->InsertChildAfter(Ind2,Subtree1);
   Children2->Remove(Ind2);
}

// -----------------------------------------------------------------------
// AppendChild : appends the tree <Atree> as last child of the current tree
// -----------------------------------------------------------------------
void PCollection_HArbitraryTree::AppendChild
               (const Handle(PCollection_HArbitraryTree)& ATree)  
{
  if (ATree.IsNull()) PCollection_IsNullTree::Raise();
  if (!ATree->IsRoot()) PCollection_IsNotRoot::Raise();

  Handle (PCollection_HArbitraryTree) MySelf = this;
  ATree->SetParent(MySelf);
  MyChildren->Append(ATree);
}

// --------------------------------------------------------------------------
// PrependChild : appends the tree <ATree> as first child of the current tree
// --------------------------------------------------------------------------
void PCollection_HArbitraryTree::PrependChild
               (const Handle(PCollection_HArbitraryTree)& ATree)  
{
  if (ATree.IsNull()) PCollection_IsNullTree::Raise();
  if (!ATree->IsRoot()) PCollection_IsNotRoot::Raise();

  Handle (PCollection_HArbitraryTree) MySelf = this;
  ATree->SetParent(MySelf);
  MyChildren->Prepend(ATree);

}

// -----------------------------------------------------------------------
// InsertChildBefore : adds the child <ATree> at the index <Index> in the 
//                     current tree  
// -----------------------------------------------------------------------
void PCollection_HArbitraryTree::InsertChildBefore
   (const Standard_Integer Index , 
    const Handle(PCollection_HArbitraryTree)& ATree) 
{
  if (ATree.IsNull()) PCollection_IsNullTree::Raise();
  if (!ATree->IsRoot()) PCollection_IsNotRoot::Raise();

  Handle (PCollection_HArbitraryTree) MySelf = this;
  ATree->SetParent(MySelf);
  MyChildren->InsertBefore(Index,ATree);
}

// ------------------------------------------------------------------------
// InsertChildAfter : adds the child <ATree> at the index <Index+1> in the
//                    current tree
// ------------------------------------------------------------------------
void PCollection_HArbitraryTree::InsertChildAfter
      (const Standard_Integer Index , 
       const Handle(PCollection_HArbitraryTree)& ATree) 
{
  if (ATree.IsNull()) PCollection_IsNullTree::Raise();
  if (!ATree->IsRoot()) PCollection_IsNotRoot::Raise();

  Handle (PCollection_HArbitraryTree) MySelf = this;
  ATree->SetParent(MySelf);
  MyChildren->InsertAfter(Index,ATree);
}

// ---------------------------------------------------------------------
// RemoveChild : removes the child at range <Index> in the current tree
// ---------------------------------------------------------------------
void PCollection_HArbitraryTree::RemoveChild(const Standard_Integer Index)  
{
  MyChildren->Remove(Index);
}

// -------------------------------------------------------------
// RemoveAllChildren : removes all children of the current tree
// -------------------------------------------------------------
void PCollection_HArbitraryTree::RemoveAllChildren()  
{
   MyChildren->Clear();
}

// --------------------------------------------------------------------------
// RemoveChildren : removes the children in range <FromIndex,ToIndex> in the
//                  current tree 
// --------------------------------------------------------------------------
void PCollection_HArbitraryTree::RemoveChildren
       (const Standard_Integer FromIndex , const Standard_Integer ToIndex)  
{
  MyChildren->Remove(FromIndex,ToIndex);
}