OCCT

// Created on: 2002-03-29
// Created by: Alexander GRIGORIEV
// Copyright (c) 2002-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

// Purpose:   Implementation of the BaseSequence class

#include <NCollection_BaseSequence.hxx>
#include <Standard_NoSuchObject.hxx>
#include <Standard_OutOfRange.hxx>
#include <Standard_DomainError.hxx>

//=======================================================================
// function : clearSeq
// purpose  : removes all items from the current sequence
//=======================================================================

void NCollection_BaseSequence::clearSeq(NCollection_DelSeqNode fDel)
{
  NCollection_SeqNode* p = myFirstItem;
  while (p)
  {
    NCollection_SeqNode* q = p;
    p                      = p->Next();
    fDel(q, myAllocator);
  }
  nullify();
}

//=================================================================================================

void NCollection_BaseSequence::pAppend(NCollection_SeqNode* theItem)
{
  if (mySize == 0)
  {
    myFirstItem = myLastItem = myCurrentItem = theItem;
    myCurrentIndex = mySize = 1;
  }
  else
  {
    myLastItem->SetNext(theItem);
    theItem->SetPrevious(myLastItem);
    theItem->SetNext(nullptr);
    myLastItem = theItem;
    ++mySize;
  }
}

//=======================================================================
// function : pAppend
// purpose  : push a sequence at the end of the sequence
//=======================================================================

void NCollection_BaseSequence::pAppend(NCollection_BaseSequence& Other)
{
  if (Other.mySize == 0)
  {
    return;
  }
  if (mySize == 0)
  {
    mySize         = Other.mySize;
    myFirstItem    = Other.myFirstItem;
    myLastItem     = Other.myLastItem;
    myCurrentItem  = myFirstItem;
    myCurrentIndex = 1;
  }
  else
  {
    mySize += Other.mySize;
    myLastItem->SetNext(Other.myFirstItem);
    if (Other.myFirstItem)
    {
      Other.myFirstItem->SetPrevious(myLastItem);
      myLastItem = Other.myLastItem;
    }
  }
  Other.nullify();
}

//=================================================================================================

void NCollection_BaseSequence::pPrepend(NCollection_SeqNode* theItem)
{
  if (mySize == 0)
  {
    myFirstItem = myLastItem = myCurrentItem = theItem;
    myCurrentIndex = mySize = 1;
  }
  else
  {
    myFirstItem->SetPrevious(theItem);
    theItem->SetNext(myFirstItem);
    theItem->SetPrevious(nullptr);
    theItem->SetNext(myFirstItem);
    myFirstItem = theItem;
    ++mySize;
    ++myCurrentIndex;
  }
}

//=======================================================================
// function : pPrepend
// purpose  : push a sequence in the beginning of the sequence
//=======================================================================

void NCollection_BaseSequence::pPrepend(NCollection_BaseSequence& Other)
{
  if (Other.mySize == 0)
  {
    return;
  }
  if (mySize == 0)
  {
    mySize         = Other.mySize;
    myFirstItem    = Other.myFirstItem;
    myLastItem     = Other.myLastItem;
    myCurrentIndex = 1;
    myCurrentItem  = myFirstItem;
  }
  else
  {
    mySize += Other.mySize;
    if (Other.myLastItem)
    {
      Other.myLastItem->SetNext(myFirstItem);
    }
    myFirstItem->SetPrevious(Other.myLastItem);
    myFirstItem = Other.myFirstItem;
    myCurrentIndex += Other.mySize;
  }
  Other.nullify();
}

//=======================================================================
// function : pReverse
// purpose  : reverse the order of a given sequence
//=======================================================================

void NCollection_BaseSequence::pReverse() noexcept
{
  NCollection_SeqNode* p = myFirstItem;
  while (p)
  {
    NCollection_SeqNode* tmp = p->Next();
    p->SetNext(p->Previous());
    p->SetPrevious(tmp);
    p = tmp;
  }
  NCollection_SeqNode* tmp = myFirstItem;
  myFirstItem              = myLastItem;
  myLastItem               = tmp;
  if (mySize != 0)
  {
    myCurrentIndex = mySize + 1 - myCurrentIndex;
  }
}

//=================================================================================================

void NCollection_BaseSequence::pInsertAfter(NCollection_BaseSequence::Iterator& thePosition,
                                            NCollection_SeqNode*                theItem)
{
  NCollection_SeqNode* aPos = thePosition.myCurrent;
  if (aPos == nullptr)
  {
    pPrepend(theItem);
  }
  else
  {
    theItem->SetNext(aPos->Next());
    theItem->SetPrevious(aPos);
    if (aPos->Next() == nullptr)
    {
      myLastItem = theItem;
    }
    else
    {
      aPos->Next()->SetPrevious(theItem);
    }
    aPos->SetNext(theItem);
    ++mySize;
    myCurrentItem  = myFirstItem;
    myCurrentIndex = 1;
  }
}

//=================================================================================================

void NCollection_BaseSequence::pInsertAfter(const size_t theIndex, NCollection_SeqNode* theItem)
{
  if (theIndex == 0)
  {
    pPrepend(theItem);
  }
  else
  {
    NCollection_SeqNode* p = find(theIndex);
    theItem->SetNext(p->Next());
    theItem->SetPrevious(p);
    if (theIndex == mySize)
    {
      myLastItem = theItem;
    }
    else
    {
      p->Next()->SetPrevious(theItem);
    }
    p->SetNext(theItem);
    ++mySize;
    if (theIndex < myCurrentIndex)
    {
      ++myCurrentIndex;
    }
  }
}

//=======================================================================
// function : pInsertAfter
// purpose  : insert a sequence after a given index in the sequence
//=======================================================================

void NCollection_BaseSequence::pInsertAfter(const size_t theIndex, NCollection_BaseSequence& Other)
{
  if (theIndex > mySize)
  {
    throw Standard_OutOfRange();
  }
  if (Other.mySize != 0)
  {
    if (theIndex == 0)
    {
      pPrepend(Other);
    }
    else
    {
      NCollection_SeqNode* p = find(theIndex);
      Other.myFirstItem->SetPrevious(p);
      Other.myLastItem->SetNext(p->Next());
      if (theIndex == mySize)
      {
        myLastItem = Other.myLastItem;
      }
      else
      {
        p->Next()->SetPrevious(Other.myLastItem);
      }
      p->SetNext(Other.myFirstItem);
      mySize += Other.mySize;
      if (theIndex < myCurrentIndex)
      {
        myCurrentIndex += Other.mySize;
      }
      Other.nullify();
    }
  }
}

//=======================================================================
// function : pExchange
// purpose  : exchange two elements in the sequence
//=======================================================================

void NCollection_BaseSequence::pExchange(const size_t I, const size_t J)
{
  Standard_OutOfRange_Raise_if(I == 0 || J == 0 || I > mySize || J > mySize, "");

  // Assume I < J
  if (J < I)
  {
    pExchange(J, I);
  }
  else if (I < J)
  {
    NCollection_SeqNode* pi = find(I);
    NCollection_SeqNode* pj = find(J);

    // update the node before I
    if (pi->Previous())
    {
      pi->Previous()->SetNext(pj);
    }
    else
    {
      myFirstItem = pj;
    }

    // update the node after J
    if (pj->Next())
    {
      pj->Next()->SetPrevious(pi);
    }
    else
    {
      myLastItem = pi;
    }

    if (pi->Next() == pj)
    { // I and J are consecutives, update them
      pj->SetPrevious(pi->Previous());
      pi->SetPrevious(pj);
      pi->SetNext(pj->Next());
      pj->SetNext(pi);
    }
    else
    { // I and J are not consecutive
      // update the node after I
      pi->Next()->SetPrevious(pj);
      // update the node before J
      pj->Previous()->SetNext(pi);
      // update nodes I and J
      NCollection_SeqNode* tmp = pi->Next();
      pi->SetNext(pj->Next());
      pj->SetNext(tmp);
      tmp = pi->Previous();
      pi->SetPrevious(pj->Previous());
      pj->SetPrevious(tmp);
    }

    if (myCurrentIndex == I)
    {
      myCurrentItem = pj;
    }
    else if (myCurrentIndex == J)
    {
      myCurrentItem = pi;
    }
  }
}

//=================================================================================================

void NCollection_BaseSequence::pSplit(const size_t theIndex, NCollection_BaseSequence& Sub)
{
  Standard_OutOfRange_Raise_if(theIndex == 0 || theIndex > mySize, "");
  Standard_DomainError_Raise_if(this == &Sub, "No Split on myself!!");

  NCollection_SeqNode* p = find(theIndex);

  Sub.myLastItem = myLastItem;
  Sub.mySize     = mySize - theIndex + 1;

  myLastItem = p->Previous();
  if (myLastItem)
  {
    myLastItem->SetNext(nullptr);
    mySize = theIndex - 1;
    if (myCurrentIndex >= theIndex)
    {
      myCurrentIndex = 1;
      myCurrentItem  = myFirstItem;
    }
  }
  else
  {
    myFirstItem = myCurrentItem = nullptr;
    mySize = myCurrentIndex = 0;
  }

  Sub.myFirstItem = Sub.myCurrentItem = p;
  p->SetPrevious(nullptr);
  Sub.myCurrentIndex = 1;
}

//=================================================================================================

void NCollection_BaseSequence::removeSeq(NCollection_BaseSequence::Iterator& thePosition,
                                         NCollection_DelSeqNode              fDel)
{
  NCollection_SeqNode* aPos = thePosition.myCurrent;
  if (aPos == nullptr)
  {
    return;
  }
  thePosition.myCurrent = aPos->Next();

  if (aPos->Previous())
  {
    aPos->Previous()->SetNext(aPos->Next());
  }
  else
  {
    myFirstItem = aPos->Next();
  }

  if (aPos->Next())
  {
    aPos->Next()->SetPrevious(aPos->Previous());
  }
  else
  {
    myLastItem = aPos->Previous();
  }

  --mySize;
  myCurrentItem  = myLastItem;
  myCurrentIndex = mySize;

  fDel(aPos, myAllocator);
}

//=================================================================================================

void NCollection_BaseSequence::removeSeq(const size_t theIndex, NCollection_DelSeqNode fDel)
{
  Standard_OutOfRange_Raise_if(theIndex == 0 || theIndex > mySize,
                               "NCollection_BaseSequence::removeSeq() - index is out of range");

  NCollection_SeqNode* p = find(theIndex);
  if (p->Previous())
  {
    p->Previous()->SetNext(p->Next());
  }
  else
  {
    myFirstItem = p->Next();
  }
  if (p->Next())
  {
    p->Next()->SetPrevious(p->Previous());
  }
  else
  {
    myLastItem = p->Previous();
  }

  --mySize;
  if (myCurrentIndex > theIndex)
  {
    --myCurrentIndex;
  }
  else if (myCurrentIndex == theIndex)
  {
    if (p->Next())
    {
      myCurrentItem = p->Next();
    }
    else
    {
      myCurrentItem  = myLastItem;
      myCurrentIndex = mySize;
    }
  }
  fDel(p, myAllocator);
}

//=================================================================================================

void NCollection_BaseSequence::removeSeq(const size_t           From,
                                         const size_t           To,
                                         NCollection_DelSeqNode fDel)
{
  Standard_OutOfRange_Raise_if(From == 0 || To > mySize || From > To,
                               "NCollection_BaseSequence::removeSeq() - invalid input range");

  NCollection_SeqNode* pfrom = find(From);
  NCollection_SeqNode* pto   = find(To);

  if (pfrom->Previous())
  {
    pfrom->Previous()->SetNext(pto->Next());
  }
  else
  {
    myFirstItem = pto->Next();
  }
  if (pto->Next())
  {
    pto->Next()->SetPrevious(pfrom->Previous());
  }
  else
  {
    myLastItem = pfrom->Previous();
  }

  mySize -= To - From + 1;
  if (myCurrentIndex > To)
  {
    myCurrentIndex -= To - From + 1;
  }
  else if (myCurrentIndex >= From)
  {
    if (pto->Next())
    {
      myCurrentItem  = pto->Next();
      myCurrentIndex = From; // AGV fix 24.05.01
    }
    else
    {
      myCurrentItem  = myLastItem;
      myCurrentIndex = mySize;
    }
  }

  for (size_t i = From; i <= To; ++i)
  {
    NCollection_SeqNode* tmp = pfrom;
    pfrom                    = pfrom->Next();
    fDel(tmp, myAllocator);
  }
}

//=================================================================================================

NCollection_SeqNode* NCollection_BaseSequence::find(const size_t theIndex) const noexcept
{
  size_t               i;
  NCollection_SeqNode* p;
  if (theIndex <= myCurrentIndex)
  {
    if (theIndex < myCurrentIndex / 2)
    {
      p = myFirstItem;
      for (i = 1; i < theIndex; ++i)
      {
        p = p->Next();
      }
    }
    else
    {
      p = myCurrentItem;
      for (i = myCurrentIndex; i > theIndex; --i)
      {
        p = p->Previous();
      }
    }
  }
  else
  {
    if (theIndex < (myCurrentIndex + mySize) / 2)
    {
      p = myCurrentItem;
      for (i = myCurrentIndex; i < theIndex; ++i)
      {
        p = p->Next();
      }
    }
    else
    {
      p = myLastItem;
      for (i = mySize; i > theIndex; --i)
      {
        p = p->Previous();
      }
    }
  }
  return p;
}