[occt.git] / src / NCollection / NCollection_BaseSequence.cxx

// Created on: 2002-03-29
// Created by: Alexander GRIGORIEV
// Copyright (c) 2002-2012 OPEN CASCADE SAS
//
// The content of this file is subject to the Open CASCADE Technology Public
// License Version 6.5 (the "License"). You may not use the content of this file
// except in compliance with the License. Please obtain a copy of the License
// at http://www.opencascade.org and read it completely before using this file.
//
// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
//
// The Original Code and all software distributed under the License is
// distributed on an "AS IS" basis, without warranty of any kind, and the
// Initial Developer hereby disclaims all such warranties, including without
// limitation, any warranties of merchantability, fitness for a particular
// purpose or non-infringement. Please see the License for the specific terms
// and conditions governing the rights and limitations under the License.

// 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, Handle(NCollection_BaseAllocator)& theAl)
{
  const NCollection_SeqNode * p = myFirstItem;
  NCollection_SeqNode * q;
  while (p) {
    q = (NCollection_SeqNode *) p;
    p = p->Next();
    fDel (q, theAl);
  }
  Nullify();
}

//=======================================================================
//function : PAppend
//purpose  : append an item to sequence
//=======================================================================

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

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

void NCollection_BaseSequence::PAppend(NCollection_BaseSequence& Other)
{
  if (mySize == 0) {
    mySize         = Other.mySize;
    myFirstItem    = Other.myFirstItem;
    myLastItem     = Other.myLastItem;
    myCurrentItem  = myFirstItem;
    myCurrentIndex = 1;
  } else {
    mySize += Other.mySize;
    ((NCollection_SeqNode *) myLastItem)->SetNext(Other.myFirstItem);
    if (Other.myFirstItem) {
      ((NCollection_SeqNode *) Other.myFirstItem)->SetPrevious(myLastItem);
      myLastItem = Other.myLastItem;
    }
  }
  Other.Nullify();
}

//=======================================================================
//function : PPrepend
//purpose  : prepend an item to sequence
//=======================================================================

void NCollection_BaseSequence::PPrepend (NCollection_SeqNode * theItem)
{
  if (mySize == 0) {
    myFirstItem = myLastItem = myCurrentItem = theItem;
    myCurrentIndex = mySize = 1;
  } else {
    ((NCollection_SeqNode *) myFirstItem)->SetPrevious (theItem);
    ((NCollection_SeqNode *) theItem)->SetNext (myFirstItem); 
    theItem->SetPrevious(NULL);
    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 (mySize == 0) {
    mySize         = Other.mySize;
    myFirstItem    = Other.myFirstItem;
    myLastItem     = Other.myLastItem;
    myCurrentIndex = 1;
    myCurrentItem  = myFirstItem;
  } else {
    mySize += Other.mySize;
    if (Other.myLastItem)
      ((NCollection_SeqNode *) Other.myLastItem)->SetNext (myFirstItem);
    ((NCollection_SeqNode *) 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()
{
  const NCollection_SeqNode * p = myFirstItem;
  const NCollection_SeqNode * tmp;
  while (p) {
    tmp = p->Next();
    ((NCollection_SeqNode *) p)->SetNext (p->Previous());
    ((NCollection_SeqNode *) p)->SetPrevious (tmp);
    p = tmp;
  }
  tmp = myFirstItem;
  myFirstItem = myLastItem;
  myLastItem = tmp;
  if (mySize != 0) myCurrentIndex = mySize + 1 - myCurrentIndex;
}


//=======================================================================
//function : PInsertAfter
//purpose  : 
//=======================================================================

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

//=======================================================================
//function : PInsertAfter
//purpose  : 
//=======================================================================

void NCollection_BaseSequence::PInsertAfter(const Standard_Integer theIndex,
                                            NCollection_SeqNode * theItem)
{
  if (theIndex == 0)
    PPrepend (theItem);
  else {
    const NCollection_SeqNode * p = Find (theIndex);
    theItem->SetNext(p->Next());
    theItem->SetPrevious(p);
    if (theIndex == mySize) myLastItem = theItem;
    else ((NCollection_SeqNode *) p->Next())->SetPrevious(theItem);
    ((NCollection_SeqNode *) 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 Standard_Integer theIndex,
                                             NCollection_BaseSequence& Other)
{
  if (theIndex < 0 || theIndex > mySize)
    Standard_OutOfRange::Raise();
  if (Other.mySize != 0) {
    if (theIndex == 0) 
      PPrepend (Other);
    else {
      const NCollection_SeqNode * p = Find (theIndex);
      ((NCollection_SeqNode *) Other.myFirstItem)->SetPrevious (p);
      ((NCollection_SeqNode *) Other.myLastItem)->SetNext (p->Next());
      if (theIndex == mySize)
        myLastItem = Other.myLastItem;
      else
        ((NCollection_SeqNode *) p->Next())->SetPrevious (Other.myLastItem);
      ((NCollection_SeqNode *) 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 Standard_Integer I,
                                          const Standard_Integer 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) {
    const NCollection_SeqNode * pi = Find(I);
    const NCollection_SeqNode * pj = Find(J);

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

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

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

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

//=======================================================================
//function : PSplit
//purpose  : 
//=======================================================================

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

  const NCollection_SeqNode * p = Find (theIndex);

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

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

  Sub.myFirstItem = Sub.myCurrentItem = p;
  ((NCollection_SeqNode *) p)->SetPrevious (NULL);
  Sub.myCurrentIndex = 1;
}

//=======================================================================
//function : Remove
//purpose  : 
//=======================================================================

void NCollection_BaseSequence::RemoveSeq 
                              (NCollection_BaseSequence::Iterator& thePosition,
                               NCollection_DelSeqNode              fDel, 
                               Handle(NCollection_BaseAllocator)&  theAl)
{
  NCollection_SeqNode * aPos = thePosition.myCurrent;
  if (aPos == NULL)
    return;
  thePosition.myCurrent = (NCollection_SeqNode *) aPos -> Next();

  if (aPos->Previous())
    ((NCollection_SeqNode *) aPos->Previous())->SetNext (aPos->Next());
  else
    myFirstItem = aPos->Next();

  if (aPos->Next())
    ((NCollection_SeqNode *) aPos->Next())->SetPrevious (aPos->Previous());
  else
    myLastItem = aPos->Previous();

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

  fDel (aPos, theAl);
}

//=======================================================================
//function : Remove
//purpose  : 
//=======================================================================

void NCollection_BaseSequence::RemoveSeq 
                              (const Standard_Integer theIndex,
                               NCollection_DelSeqNode fDel, 
                               Handle(NCollection_BaseAllocator)& theAl)
{
  Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize, "");
  
  const NCollection_SeqNode * p = Find (theIndex);
  if (p->Previous())
    ((NCollection_SeqNode *) p->Previous())->SetNext (p->Next());
  else
    myFirstItem = p->Next();
  if (p->Next())
    ((NCollection_SeqNode *) 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 ((NCollection_SeqNode *) p, theAl);
}

//=======================================================================
//function : Remove
//purpose  : remove a set of items
//=======================================================================

void NCollection_BaseSequence::RemoveSeq 
                              (const Standard_Integer From,
                               const Standard_Integer To, 
                               NCollection_DelSeqNode fDel,
                               Handle(NCollection_BaseAllocator)& theAl)
{
  Standard_OutOfRange_Raise_if (From <= 0 || To > mySize || From > To, "");

  const NCollection_SeqNode * pfrom = Find(From);
  const NCollection_SeqNode * pto   = Find(To);
  
  if (pfrom->Previous())
    ((NCollection_SeqNode *) pfrom->Previous())->SetNext (pto->Next());
  else
    myFirstItem = pto->Next();
  if (pto->Next())
    ((NCollection_SeqNode *) 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 (Standard_Integer i = From; i <= To; i++) {
    NCollection_SeqNode * tmp = (NCollection_SeqNode *)pfrom;
    pfrom = pfrom->Next();
    fDel (tmp, theAl);
  }
}

//=======================================================================
//function : Find
//purpose  : 
//=======================================================================

const NCollection_SeqNode * NCollection_BaseSequence::Find
                                        (const Standard_Integer theIndex) const 
{
  Standard_Integer i;
  const 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;
}
Commit	Line	Data
b311480e	1	// Created on: 2002-03-29
	2	// Created by: Alexander GRIGORIEV
	3	// Copyright (c) 2002-2012 OPEN CASCADE SAS
	4	//
	5	// The content of this file is subject to the Open CASCADE Technology Public
	6	// License Version 6.5 (the "License"). You may not use the content of this file
	7	// except in compliance with the License. Please obtain a copy of the License
	8	// at http://www.opencascade.org and read it completely before using this file.
	9	//
	10	// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
	11	// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
	12	//
	13	// The Original Code and all software distributed under the License is
	14	// distributed on an "AS IS" basis, without warranty of any kind, and the
	15	// Initial Developer hereby disclaims all such warranties, including without
	16	// limitation, any warranties of merchantability, fitness for a particular
	17	// purpose or non-infringement. Please see the License for the specific terms
	18	// and conditions governing the rights and limitations under the License.
	19
7fd59977	20	// Purpose: Implementation of the BaseSequence class
	21
	22	#include <NCollection_BaseSequence.hxx>
	23	#include <Standard_NoSuchObject.hxx>
	24	#include <Standard_OutOfRange.hxx>
	25	#include <Standard_DomainError.hxx>
	26
	27	//=======================================================================
	28	//function : ClearSeq
	29	//purpose : removes all items from the current sequence
	30	//=======================================================================
	31
	32	void NCollection_BaseSequence::ClearSeq
	33	(NCollection_DelSeqNode fDel, Handle(NCollection_BaseAllocator)& theAl)
	34	{
	35	const NCollection_SeqNode * p = myFirstItem;
	36	NCollection_SeqNode * q;
	37	while (p) {
	38	q = (NCollection_SeqNode *) p;
	39	p = p->Next();
	40	fDel (q, theAl);
	41	}
	42	Nullify();
	43	}
	44
	45	//=======================================================================
	46	//function : PAppend
	47	//purpose : append an item to sequence
	48	//=======================================================================
	49
	50	void NCollection_BaseSequence::PAppend (NCollection_SeqNode * theItem)
	51	{
	52	if (mySize == 0) {
	53	myFirstItem = myLastItem = myCurrentItem = theItem;
	54	myCurrentIndex = mySize = 1;
	55	} else {
	56	((NCollection_SeqNode *) myLastItem)->SetNext(theItem);
	57	theItem->SetPrevious(myLastItem);
	58	theItem->SetNext(NULL);
	59	myLastItem = theItem;
	60	++ mySize;
	61	}
	62	}
	63
	64	//=======================================================================
	65	//function : PAppend
	66	//purpose : push a sequence at the end of the sequence
	67	//=======================================================================
	68
	69	void NCollection_BaseSequence::PAppend(NCollection_BaseSequence& Other)
	70	{
	71	if (mySize == 0) {
	72	mySize = Other.mySize;
	73	myFirstItem = Other.myFirstItem;
	74	myLastItem = Other.myLastItem;
	75	myCurrentItem = myFirstItem;
	76	myCurrentIndex = 1;
	77	} else {
	78	mySize += Other.mySize;
	79	((NCollection_SeqNode *) myLastItem)->SetNext(Other.myFirstItem);
	80	if (Other.myFirstItem) {
	81	((NCollection_SeqNode *) Other.myFirstItem)->SetPrevious(myLastItem);
	82	myLastItem = Other.myLastItem;
	83	}
84	}
85	Other.Nullify();
86	}
87
88	//=======================================================================
89	//function : PPrepend
90	//purpose : prepend an item to sequence
91	//=======================================================================
92
93	void NCollection_BaseSequence::PPrepend (NCollection_SeqNode * theItem)
94	{
95	if (mySize == 0) {
96	myFirstItem = myLastItem = myCurrentItem = theItem;
97	myCurrentIndex = mySize = 1;
98	} else {
99	((NCollection_SeqNode *) myFirstItem)->SetPrevious (theItem);
100	((NCollection_SeqNode *) theItem)->SetNext (myFirstItem);
101	theItem->SetPrevious(NULL);
102	theItem->SetNext(myFirstItem);
103	myFirstItem = theItem;
104	++ mySize;
105	++ myCurrentIndex;
106	}
107	}
108
109	//=======================================================================
110	//function : PPrepend
111	//purpose : push a sequence in the beginning of the sequence
112	//=======================================================================
113
114	void NCollection_BaseSequence::PPrepend (NCollection_BaseSequence& Other)
115	{
116	if (mySize == 0) {
117	mySize = Other.mySize;
118	myFirstItem = Other.myFirstItem;
119	myLastItem = Other.myLastItem;
120	myCurrentIndex = 1;
121	myCurrentItem = myFirstItem;
122	} else {
123	mySize += Other.mySize;
124	if (Other.myLastItem)
125	((NCollection_SeqNode *) Other.myLastItem)->SetNext (myFirstItem);
126	((NCollection_SeqNode *) myFirstItem)->SetPrevious(Other.myLastItem);
127	myFirstItem = Other.myFirstItem;
128	myCurrentIndex += Other.mySize;
129	}
130	Other.Nullify();
131	}
132
133	//=======================================================================
134	//function : PReverse
135	//purpose : reverse the order of a given sequence
136	//=======================================================================
137
138	void NCollection_BaseSequence::PReverse()
139	{
140	const NCollection_SeqNode * p = myFirstItem;
141	const NCollection_SeqNode * tmp;
142	while (p) {
143	tmp = p->Next();
144	((NCollection_SeqNode *) p)->SetNext (p->Previous());
145	((NCollection_SeqNode *) p)->SetPrevious (tmp);
146	p = tmp;
147	}
148	tmp = myFirstItem;
149	myFirstItem = myLastItem;
150	myLastItem = tmp;
151	if (mySize != 0) myCurrentIndex = mySize + 1 - myCurrentIndex;
152	}
153
154
155	//=======================================================================
156	//function : PInsertAfter
157	//purpose :
158	//=======================================================================
159
160	void NCollection_BaseSequence::PInsertAfter
161	(NCollection_BaseSequence::Iterator& thePosition,
162	NCollection_SeqNode * theItem)
163	{
164	NCollection_SeqNode * aPos = thePosition.myCurrent;
165	if (aPos == NULL)
166	PPrepend (theItem);
167	else {
168	theItem->SetNext (aPos->Next());
169	theItem->SetPrevious (aPos);
170	if (aPos->Next() == NULL) myLastItem = theItem;
171	else ((NCollection_SeqNode *) aPos->Next())->SetPrevious(theItem);
172	aPos->SetNext(theItem);
173	++ mySize;
174	myCurrentItem = myFirstItem;
175	myCurrentIndex = 1;
176	}
177	}
178
179	//=======================================================================
180	//function : PInsertAfter
181	//purpose :
182	//=======================================================================
183
184	void NCollection_BaseSequence::PInsertAfter(const Standard_Integer theIndex,
185	NCollection_SeqNode * theItem)
186	{
187	if (theIndex == 0)
188	PPrepend (theItem);
189	else {
190	const NCollection_SeqNode * p = Find (theIndex);
191	theItem->SetNext(p->Next());
192	theItem->SetPrevious(p);
193	if (theIndex == mySize) myLastItem = theItem;
194	else ((NCollection_SeqNode *) p->Next())->SetPrevious(theItem);
195	((NCollection_SeqNode *) p)->SetNext(theItem);
196	++ mySize;
197	if (theIndex < myCurrentIndex)
198	++ myCurrentIndex;
199	}
200	}
201
202	//=======================================================================
203	//function : PInsertAfter
204	//purpose : insert a sequence after a given index in the sequence
205	//=======================================================================
206
207	void NCollection_BaseSequence::PInsertAfter (const Standard_Integer theIndex,
208	NCollection_BaseSequence& Other)
209	{
210	if (theIndex < 0 \|\| theIndex > mySize)
211	Standard_OutOfRange::Raise();
eafb234b	212	if (Other.mySize != 0) {
7fd59977	213	if (theIndex == 0)
	214	PPrepend (Other);
	215	else {
	216	const NCollection_SeqNode * p = Find (theIndex);
	217	((NCollection_SeqNode *) Other.myFirstItem)->SetPrevious (p);
	218	((NCollection_SeqNode *) Other.myLastItem)->SetNext (p->Next());
	219	if (theIndex == mySize)
	220	myLastItem = Other.myLastItem;
	221	else
	222	((NCollection_SeqNode *) p->Next())->SetPrevious (Other.myLastItem);
	223	((NCollection_SeqNode *) p)->SetNext (Other.myFirstItem);
	224	mySize += Other.mySize;
	225	if (theIndex < myCurrentIndex)
	226	myCurrentIndex += Other.mySize;
	227	Other.Nullify();
	228	}
eafb234b	229	}
7fd59977	230	}
	231
	232	//=======================================================================
	233	//function : PExchange
	234	//purpose : exchange two elements in the sequence
	235	//=======================================================================
	236
	237	void NCollection_BaseSequence::PExchange (const Standard_Integer I,
	238	const Standard_Integer J)
	239	{
	240	Standard_OutOfRange_Raise_if (I <= 0 \|\| J <= 0 \|\| I > mySize \|\| J > mySize,
	241	"" );
	242
	243	// Assume I < J
	244	if (J < I)
	245	PExchange(J,I);
	246	else if (I < J) {
	247	const NCollection_SeqNode * pi = Find(I);
	248	const NCollection_SeqNode * pj = Find(J);
	249
	250	// update the node before I
	251	if (pi->Previous())
	252	((NCollection_SeqNode *) pi->Previous())->SetNext (pj);
	253	else
	254	myFirstItem = pj;
	255
	256	// update the node after J
	257	if (pj->Next())
	258	((NCollection_SeqNode *) pj->Next())->SetPrevious(pi);
	259	else
	260	myLastItem = pi;
	261
	262	if (pi->Next() == pj) { // I and J are consecutives, update them
	263	((NCollection_SeqNode *) pj)->SetPrevious (pi->Previous());
	264	((NCollection_SeqNode *) pi)->SetPrevious (pj);
	265	((NCollection_SeqNode *) pi)->SetNext (pj->Next());
	266	((NCollection_SeqNode *) pj)->SetNext (pi);
	267	}
	268	else { // I and J are not consecutive
	269	// update the node after I
	270	((NCollection_SeqNode *) pi->Next())->SetPrevious (pj);
	271	// update the node before J
	272	((NCollection_SeqNode *) pj->Previous())->SetNext (pi);
	273	// update nodes I and J
	274	const NCollection_SeqNode* tmp = pi->Next();
	275	((NCollection_SeqNode *) pi)->SetNext (pj->Next());
	276	((NCollection_SeqNode *) pj)->SetNext (tmp);
	277	tmp = pi->Previous();
	278	((NCollection_SeqNode *) pi)->SetPrevious (pj->Previous());
	279	((NCollection_SeqNode *) pj)->SetPrevious (tmp);
	280	}
	281
	282	if (myCurrentIndex == I) myCurrentItem = pj;
	283	else if (myCurrentIndex == J) myCurrentItem = pi;
	284	}
	285	}
	286
	287	//=======================================================================
	288	//function : PSplit
	289	//purpose :
	290	//=======================================================================
	291
	292	void NCollection_BaseSequence::PSplit (const Standard_Integer theIndex,
	293	NCollection_BaseSequence& Sub)
294	{
295	Standard_OutOfRange_Raise_if (theIndex <= 0 \|\| theIndex > mySize,"" );
296	Standard_DomainError_Raise_if (this == &Sub, "No Split on myself!!");
297
298	const NCollection_SeqNode * p = Find (theIndex);
299
300	Sub.myLastItem = myLastItem;
301	Sub.mySize = mySize - theIndex + 1;
302
303	myLastItem = p->Previous();
304	if (myLastItem) {
305	((NCollection_SeqNode *) myLastItem)->SetNext(NULL);
306	mySize = theIndex - 1;
307	if (myCurrentIndex >= theIndex) {
308	myCurrentIndex = 1;
309	myCurrentItem = myFirstItem;
310	}
311	} else {
312	myFirstItem = myCurrentItem = NULL;
313	mySize = myCurrentIndex = 0;
314	}
315
316	Sub.myFirstItem = Sub.myCurrentItem = p;
317	((NCollection_SeqNode *) p)->SetPrevious (NULL);
318	Sub.myCurrentIndex = 1;
319	}
320
321	//=======================================================================
322	//function : Remove
323	//purpose :
324	//=======================================================================
325
326	void NCollection_BaseSequence::RemoveSeq
327	(NCollection_BaseSequence::Iterator& thePosition,
328	NCollection_DelSeqNode fDel,
329	Handle(NCollection_BaseAllocator)& theAl)
330	{
331	NCollection_SeqNode * aPos = thePosition.myCurrent;
332	if (aPos == NULL)
333	return;
334	thePosition.myCurrent = (NCollection_SeqNode *) aPos -> Next();
335
336	if (aPos->Previous())
337	((NCollection_SeqNode *) aPos->Previous())->SetNext (aPos->Next());
338	else
339	myFirstItem = aPos->Next();
340
341	if (aPos->Next())
342	((NCollection_SeqNode *) aPos->Next())->SetPrevious (aPos->Previous());
343	else
344	myLastItem = aPos->Previous();
345
346	-- mySize;
347	myCurrentItem = myLastItem;
348	myCurrentIndex = mySize;
349
350	fDel (aPos, theAl);
351	}
352
353	//=======================================================================
354	//function : Remove
355	//purpose :
356	//=======================================================================
357
358	void NCollection_BaseSequence::RemoveSeq
359	(const Standard_Integer theIndex,
360	NCollection_DelSeqNode fDel,
361	Handle(NCollection_BaseAllocator)& theAl)
362	{
363	Standard_OutOfRange_Raise_if (theIndex <= 0 \|\| theIndex > mySize, "");
364
365	const NCollection_SeqNode * p = Find (theIndex);
366	if (p->Previous())
367	((NCollection_SeqNode *) p->Previous())->SetNext (p->Next());
368	else
369	myFirstItem = p->Next();
370	if (p->Next())
371	((NCollection_SeqNode *) p->Next())->SetPrevious (p->Previous());
372	else
373	myLastItem = p->Previous();
374
375	-- mySize;
376	if (myCurrentIndex > theIndex) -- myCurrentIndex;
377	else if (myCurrentIndex == theIndex) {
378	if (p->Next())
379	myCurrentItem = p->Next();
380	else {
381	myCurrentItem = myLastItem;
382	myCurrentIndex = mySize;
383	}
384	}
385	fDel ((NCollection_SeqNode *) p, theAl);
386	}
387
388	//=======================================================================
389	//function : Remove
390	//purpose : remove a set of items
391	//=======================================================================
392
393	void NCollection_BaseSequence::RemoveSeq
394	(const Standard_Integer From,
395	const Standard_Integer To,
396	NCollection_DelSeqNode fDel,
397	Handle(NCollection_BaseAllocator)& theAl)
398	{
399	Standard_OutOfRange_Raise_if (From <= 0 \|\| To > mySize \|\| From > To, "");
400
401	const NCollection_SeqNode * pfrom = Find(From);
402	const NCollection_SeqNode * pto = Find(To);
403
404	if (pfrom->Previous())
405	((NCollection_SeqNode *) pfrom->Previous())->SetNext (pto->Next());
406	else
407	myFirstItem = pto->Next();
408	if (pto->Next())
409	((NCollection_SeqNode *) pto->Next())->SetPrevious (pfrom->Previous());
410	else
411	myLastItem = pfrom->Previous();
412
413	mySize -= To - From + 1;
414	if (myCurrentIndex > To)
415	myCurrentIndex -= To - From + 1;
416	else if (myCurrentIndex >= From) {
417	if (pto->Next()) {
418	myCurrentItem = pto->Next();
419	myCurrentIndex = From; // AGV fix 24.05.01
420	} else {
421	myCurrentItem = myLastItem;
422	myCurrentIndex = mySize;
423	}
424	}
425
426	for (Standard_Integer i = From; i <= To; i++) {
427	NCollection_SeqNode * tmp = (NCollection_SeqNode *)pfrom;
428	pfrom = pfrom->Next();
429	fDel (tmp, theAl);
430	}
431	}
432
433	//=======================================================================
434	//function : Find
435	//purpose :
436	//=======================================================================
437
438	const NCollection_SeqNode * NCollection_BaseSequence::Find
439	(const Standard_Integer theIndex) const
440	{
441	Standard_Integer i;
442	const NCollection_SeqNode * p;
443	if (theIndex <= myCurrentIndex) {
444	if (theIndex < myCurrentIndex / 2) {
445	p = myFirstItem;
446	for (i = 1; i < theIndex; i++) p = p->Next();
447	} else {
448	p = myCurrentItem;
449	for (i = myCurrentIndex; i > theIndex; i--) p = p->Previous();
450	}
451	} else {
452	if (theIndex < (myCurrentIndex + mySize) / 2) {
453	p = myCurrentItem;
454	for (i = myCurrentIndex; i < theIndex; i++) p = p->Next();
455	} else {
456	p = myLastItem;
457	for (i = mySize; i > theIndex; i--) p = p->Previous();
458	}
459	}
460	return p;
461	}