/**************************************************************
 * 
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 * 
 *************************************************************/



// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_tools.hxx"

#ifndef _LIMITS_H
#include <limits.h>
#endif

#ifndef _STRING_H
#include <string.h>
#endif

#ifndef _STDIO_H
#include <stdio.h>
#endif
#include <tools/solar.h>
#include <impcont.hxx>
#include <tools/contnr.hxx>
#include <tools/debug.hxx>

// -----------------------------------------------------------------------

DBG_NAME( CBlock )
DBG_NAME( Container )

/*************************************************************************
|*
|*	  DbgCheckCBlock()
|*
|*	  Beschreibung		Pruefung eines CBlock fuer Debug-Utilities
|*	  Ersterstellung	MI 30.01.92
|*	  Letzte Aenderung	TH 24.01.96
|*
*************************************************************************/

#ifdef DBG_UTIL
const char* CBlock::DbgCheckCBlock( const void* pBlock )
{
	CBlock* p = (CBlock*)pBlock;

	if ( p->nCount > p->nSize )
		return "nCount > nSize";

	if ( p->nSize && !p->pNodes )
		return "nSize > 0 && pNodes == NULL";

	return NULL;
}
#endif

/*************************************************************************
|*
|*	  CBlock::CBlock()
|*
|*	  Beschreibung		Construktor des Verwaltungsblocks
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

CBlock::CBlock( sal_uInt16 nInitSize, CBlock* _pPrev, CBlock* _pNext )
{
	DBG_CTOR( CBlock, DbgCheckCBlock );

	pPrev	= _pPrev;
	pNext	= _pNext;
	nSize	= nInitSize;
	nCount	= 0;

	// Datenpuffer anlegen
	pNodes = new PVOID[nSize];
}

/*************************************************************************
|*
|*	  CBlock::CBlock()
|*
|*	  Beschreibung		Construktor des Verwaltungsblocks
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

CBlock::CBlock( sal_uInt16 _nSize, CBlock* _pPrev )
{
	DBG_CTOR( CBlock, DbgCheckCBlock );
	DBG_ASSERT( _nSize, "CBlock::CBlock(): nSize == 0" );

	pPrev	= _pPrev;
	pNext	= NULL;
	nSize	= _nSize;
	nCount	= _nSize;

	// Datenpuffer anlegen und initialisieren
	pNodes = new PVOID[nSize];
	memset( pNodes, 0, nSize*sizeof(PVOID) );
}

/*************************************************************************
|*
|*	  CBlock::CBlock()
|*
|*	  Beschreibung		Copy-Construktor des Verwaltungsblocks
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

CBlock::CBlock( const CBlock& r, CBlock* _pPrev )
{
	DBG_CTOR( CBlock, DbgCheckCBlock );
	DBG_CHKOBJ( &r, CBlock, DbgCheckCBlock );

	pPrev	= _pPrev;
	pNext	= NULL;
	nSize	= r.nSize;
	nCount	= r.nCount;

	// Datenpuffer anlegen und Daten kopieren
	pNodes = new PVOID[nSize];
	memcpy( pNodes, r.pNodes, nCount*sizeof(PVOID) );
}

/*************************************************************************
|*
|*	  CBlock::~CBlock()
|*
|*	  Beschreibung		Destruktor des Verwaltungsblocks
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

inline CBlock::~CBlock()
{
	DBG_DTOR( CBlock, DbgCheckCBlock );

	// Daten loeschen
	delete[] pNodes;
}

/*************************************************************************
|*
|*	  CBlock::Insert()
|*
|*	  Beschreibung		Fuegt einen Pointer ein
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void CBlock::Insert( void* p, sal_uInt16 nIndex, sal_uInt16 nReSize )
{
	DBG_CHKTHIS( CBlock, DbgCheckCBlock );
	DBG_ASSERT( nIndex <= nCount, "CBlock::Insert(): Index > nCount" );

	// Muss Block realokiert werden
	if ( nCount == nSize )
	{
		// Neue Daten anlegen
        nSize = nSize + nReSize;    // MSVC warns here if += is used
		void** pNewNodes = new PVOID[nSize];

		// Wird angehaengt
		if ( nCount == nIndex )
		{
			// Daten kopieren
			memcpy( pNewNodes, pNodes, nCount*sizeof(PVOID) );
		}
		else
		{
			// Daten kopieren
			memcpy( pNewNodes, pNodes, nIndex*sizeof(PVOID) );
			memcpy( pNewNodes + nIndex + 1,
					pNodes + nIndex,
					(nCount-nIndex)*sizeof(PVOID) );
		}

		// Alte Daten loeschen und neue setzen
		delete[] pNodes;
		pNodes = pNewNodes;
	}
	else
	{
		if ( nIndex < nCount )
		{
			memmove( pNodes + nIndex + 1,
					 pNodes + nIndex,
					 (nCount-nIndex)*sizeof(PVOID) );
		}
	}

	// Neuen Pointer setzen und Elementgroesse erhoehen
	pNodes[nIndex] = p;
	nCount++;
}

/*************************************************************************
|*
|*	  CBlock::Split()
|*
|*	  Beschreibung		Fuegt einen Pointer ein und splittet den Block
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

CBlock* CBlock::Split( void* p, sal_uInt16 nIndex, sal_uInt16 nReSize )
{
	DBG_CHKTHIS( CBlock, DbgCheckCBlock );

	sal_uInt16	nNewSize;
	sal_uInt16	nMiddle;
	CBlock* pNewBlock;

	nMiddle = nCount/2;

	if ( ( nIndex == nCount ) || ( nIndex == 0 ) )
		nNewSize = nReSize;
	else
	{
		// Der aktuelle Block wird in der Mitte geteilt
		nNewSize = (nCount+1) / 2;

		if ( nNewSize < nReSize )
			nNewSize = nReSize;
		else
		{
			// Neue Groesse muss ein vielfaches von Resize sein
			if ( nNewSize % nReSize )
				nNewSize += nReSize - (nNewSize % nReSize);
			else
                nNewSize = nNewSize + nReSize;  // MSVC warns here if += is used
		}
	}

	// Vor oder hinter dem aktuellem Block einfuegen?
	if ( nIndex > nMiddle )
	{
		// Neuen Split-Block anlegen und hinter dem aktuellem Block einfuegen
		pNewBlock = new CBlock( nNewSize, this, pNext );

		if ( pNext )
			pNext->pPrev = pNewBlock;
		pNext = pNewBlock;

		if ( nIndex == nCount )
		{
			// Neuen Pointer einfuegen
			pNewBlock->pNodes[0] = p;
			pNewBlock->nCount = 1;
		}
		else
		{
            nIndex = nIndex - nMiddle;  // MSVC warns here if += is used
			// Alles von Mitte bis Index kopieren
			if ( nIndex )
				memcpy( pNewBlock->pNodes, pNodes+nMiddle, nIndex*sizeof(PVOID) );

			// Neuen Pointer einfuegen
			pNewBlock->pNodes[nIndex] = p;

			// Alles von Mitte bis Ende hinter Index kopieren
			memcpy( pNewBlock->pNodes+nIndex+1,
					pNodes+nMiddle+nIndex,
					(nCount-nMiddle-nIndex) * sizeof(PVOID) );

			pNewBlock->nCount = (nCount-nMiddle+1);
			nCount = nMiddle;

			// Den aktuellen Datenbereich auch halbieren
			if ( nSize != nNewSize )
			{
				void** pNewNodes = new PVOID[nNewSize];
				memcpy( pNewNodes, pNodes, nCount*sizeof(PVOID) );
				delete[] pNodes;
				pNodes = pNewNodes;
				nSize = nNewSize;
			}
		}
	}
	else
	{
		// Neuen Split-Block anlegen und vor dem aktuellem Block einfuegen
		pNewBlock = new CBlock( nNewSize, pPrev, this );

		if ( pPrev )
			pPrev->pNext = pNewBlock;
		pPrev = pNewBlock;

		if ( nIndex == 0 )
		{
			// Neuen Pointer einfuegen
			pNewBlock->pNodes[0] = p;
			pNewBlock->nCount = 1;
		}
		else
		{
			// Alles von Anfang bis Index kopieren
			memcpy( pNewBlock->pNodes, pNodes, nIndex*sizeof(PVOID) );

			// Neuen Pointer einfuegen
			pNewBlock->pNodes[nIndex] = p;

			// Alles von Index bis Mitte hinter Index kopieren
			if ( nIndex != nMiddle )
			{
				memcpy( pNewBlock->pNodes+nIndex+1,
						pNodes+nIndex,
						(nMiddle-nIndex) * sizeof(PVOID) );
			}

			pNewBlock->nCount = nMiddle+1;
            nCount = nCount - nMiddle;  // MSVC warns here if += is used

			// Die zweite Haelfte in einen neuen Block kopieren
			if ( nSize != nNewSize )
			{
				void** pNewNodes = new PVOID[nNewSize];
				memcpy( pNewNodes, pNodes+nMiddle, nCount*sizeof(PVOID) );
				delete[] pNodes;
				pNodes = pNewNodes;
				nSize = nNewSize;
			}
			else
				memmove( pNodes, pNodes+nMiddle, nCount*sizeof(PVOID) );
		}
	}

	// Neu angelegten Block zurueckgeben, da gegebenfalls die Blockpointer
	// im Container angepast werden koennen
	return pNewBlock;
}

/*************************************************************************
|*
|*	  CBlock::Remove()
|*
|*	  Beschreibung		Entfernt einen Pointer
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* CBlock::Remove( sal_uInt16 nIndex, sal_uInt16 nReSize )
{
	DBG_CHKTHIS( CBlock, DbgCheckCBlock );

	// Alten Pointer sichern
	void* pOld = pNodes[nIndex];

	// 1 Element weniger
	nCount--;

	// Block verkleinern (wenn Reallokationsgroesse um 4 unterschritten wird)
	if ( nCount == (nSize-nReSize-4) )
	{
		// Neue Daten anlegen
        nSize = nSize - nReSize;    // MSVC warns here if += is used
		void** pNewNodes = new PVOID[nSize];

		// Wird letzter Eintrag geloescht
		if ( nIndex == nCount )
		{
			// Daten kopieren
			memcpy( pNewNodes, pNodes, nCount*sizeof(PVOID) );
		}
		else
		{
			// Daten kopieren
			memcpy( pNewNodes, pNodes, nIndex*sizeof(PVOID) );
			memcpy( pNewNodes + nIndex, pNodes + nIndex+1,
					(nCount-nIndex)*sizeof(PVOID) );
		}

		// Alte Daten loeschen und neue setzen
		delete[] pNodes;
		pNodes = pNewNodes;
	}
	else
	{
		// Wenn nicht das letzte Element, dann zusammenschieben
		if ( nIndex < nCount )
		{
			memmove( pNodes + nIndex, pNodes + nIndex + 1,
					 (nCount-nIndex)*sizeof(PVOID) );
		}
	}

	// Alten Pointer zurueckgeben
	return pOld;
}

/*************************************************************************
|*
|*	  CBlock::Replace()
|*
|*	  Beschreibung		Ersetzt einen Pointer
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

inline void* CBlock::Replace( void* p, sal_uInt16 nIndex )
{
	DBG_CHKTHIS( CBlock, DbgCheckCBlock );

	// Alten Pointer sichern, neuen setzen und alten zurueckgeben
	void* pOld = pNodes[nIndex];
	pNodes[nIndex] = p;
	return pOld;
}

/*************************************************************************
|*
|*	  CBlock::GetObjectPtr()
|*
|*	  Beschreibung		Gibt einen Pointer auf den Pointer aus dem Block
|*						zurueck
|*	  Ersterstellung	TH 26.01.93
|*	  Letzte Aenderung	TH 26.01.93
|*
*************************************************************************/

inline void** CBlock::GetObjectPtr( sal_uInt16 nIndex )
{
	DBG_CHKTHIS( CBlock, DbgCheckCBlock );

	return &(pNodes[nIndex]);
}

/*************************************************************************
|*
|*	  CBlock::SetSize()
|*
|*	  Beschreibung		Aendert die Groesse des Blocks
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void CBlock::SetSize( sal_uInt16 nNewSize )
{
	DBG_CHKTHIS( CBlock, DbgCheckCBlock );
	DBG_ASSERT( nNewSize, "CBlock::SetSize(): nNewSize == 0" );

	// Unterscheidet sich die Groesse
	if ( nNewSize != nCount )
	{
		// Array erweitern
		void** pNewNodes = new PVOID[nNewSize];

		// Alte Tabelle in die Neue kopieren
		if ( nNewSize < nCount )
			memcpy( pNewNodes, pNodes, nNewSize*sizeof(PVOID) );
		else
		{
			memcpy( pNewNodes, pNodes, nCount*sizeof(PVOID) );

			// Array mit 0 initialisieren
			memset( pNewNodes+nCount, 0, (nNewSize-nCount)*sizeof(PVOID) );
		}

		// Altes Array loeschen und neue Werte setzen
		nSize  = nNewSize;
		nCount = nSize;
		delete[] pNodes;
		pNodes = pNewNodes;
	}
}

//------------------------------------------------------------------------

/*************************************************************************
|*
|*	  DbgCheckContainer()
|*
|*	  Beschreibung		Pruefung eines Container fuer Debug-Utilities
|*	  Ersterstellung	MI 30.01.92
|*	  Letzte Aenderung	TH 24.01.96
|*
*************************************************************************/

#ifdef DBG_UTIL
const char* Container::DbgCheckContainer( const void* pCont )
{
	Container* p = (Container*)pCont;

	if ( p->nCount && (!p->pFirstBlock || !p->pLastBlock || !p->pCurBlock) )
		return "nCount > 0 but no CBlocks";

	return NULL;
}
#endif

/*************************************************************************
|*
|*	  ImpCopyContainer()
|*
|*	  Beschreibung		Kopiert alle Daten des Containers
|*	  Ersterstellung	TH 24.01.96
|*	  Letzte Aenderung	TH 24.01.96
|*
*************************************************************************/

void Container::ImpCopyContainer( const Container* pCont2 )
{
	// Werte vom uebergebenen Container uebernehmen
	nCount	   = pCont2->nCount;
	nCurIndex  = pCont2->nCurIndex;
	nInitSize  = pCont2->nInitSize;
	nReSize    = pCont2->nReSize;
	nBlockSize = pCont2->nBlockSize;

	// Alle Bloecke kopieren
	if ( pCont2->nCount )
	{
		CBlock* pBlock1;
		CBlock* pBlock2;
		CBlock* pTempBlock;

		// Erstmal ersten Block kopieren
		pBlock2 = pCont2->pFirstBlock;
		pFirstBlock = new CBlock( *pBlock2, NULL );
		// Ist erster Block der Current-Block, dann Current-Block setzen
		if ( pBlock2 == pCont2->pCurBlock )
			pCurBlock = pFirstBlock;
		pBlock1 = pFirstBlock;
		pBlock2 = pBlock2->GetNextBlock();
		while ( pBlock2 )
		{
			// Neuen Block anlegen und aus der uebergebenen Liste kopieren
			pTempBlock = new CBlock( *pBlock2, pBlock1 );
			pBlock1->SetNextBlock( pTempBlock );
			pBlock1 = pTempBlock;

			// Current-Block beruecksichtigen
			if ( pBlock2 == pCont2->pCurBlock )
				pCurBlock = pBlock1;

			// Auf naechsten Block weitersetzen
			pBlock2 = pBlock2->GetNextBlock();
		}

		// Letzten Block setzen
		pLastBlock = pBlock1;
	}
	else
	{
		pFirstBlock = NULL;
		pLastBlock	= NULL;
		pCurBlock	= NULL;
	}
}

/*************************************************************************
|*
|*	  Container::Container()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

Container::Container( sal_uInt16 _nBlockSize, sal_uInt16 _nInitSize, sal_uInt16 _nReSize )
{
	DBG_CTOR( Container, DbgCheckContainer );

	// BlockSize muss mindestens 4 sein und kleiner als 64 KB
	if ( _nBlockSize < 4 )
		nBlockSize = 4;
	else
	{
		if ( _nBlockSize < CONTAINER_MAXBLOCKSIZE )
			nBlockSize = _nBlockSize;
		else
			nBlockSize = CONTAINER_MAXBLOCKSIZE;
	}

	// ReSize muss mindestens 2 sein und kleiner als BlockSize
	if ( _nReSize >= nBlockSize )
		nReSize = nBlockSize;
	else
	{
		if ( _nReSize < 2 )
			nReSize = 2;
		else
			nReSize = _nReSize;

		// BlockSize muss ein vielfaches der Resizegroesse sein
		if ( nBlockSize % nReSize )
			nBlockSize -= nReSize - (nBlockSize % nReSize);
	}

	// InitSize muss groesser gleich ReSize sein und kleiner als BlockSize
	if ( _nInitSize <= nReSize )
		nInitSize = nReSize;
	else
	{
		if ( _nInitSize >= nBlockSize )
			nInitSize = nBlockSize;
		else
		{
			nInitSize = _nInitSize;

			// InitSize muss ein vielfaches der Resizegroesse sein
			if ( nInitSize % nReSize )
				nInitSize -= nReSize - (nInitSize % nReSize);
		}
	}

	// Werte initialisieren
	pFirstBlock = NULL;
	pLastBlock	= NULL;
	pCurBlock	= NULL;
	nCount		= 0;
	nCurIndex	= 0;
}

/*************************************************************************
|*
|*	  Container::Container()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

Container::Container( sal_uIntPtr nSize )
{
	DBG_CTOR( Container, DbgCheckContainer );

	nCount	   = nSize;
	nCurIndex  = 0;
	nBlockSize = CONTAINER_MAXBLOCKSIZE;
	nInitSize  = 1;
	nReSize    = 1;

	if ( !nSize )
	{
		pFirstBlock = NULL;
		pLastBlock	= NULL;
		pCurBlock	= NULL;
	}
	else
	{
		// Muss mehr als ein Block angelegt werden
		if ( nSize <= nBlockSize )
		{
			pFirstBlock = new CBlock( (sal_uInt16)nSize, NULL );
			pLastBlock = pFirstBlock;
		}
		else
		{
			CBlock* pBlock1;
			CBlock* pBlock2;

			pFirstBlock = new CBlock( nBlockSize, NULL );
			pBlock1 = pFirstBlock;
			nSize -= nBlockSize;

			// Solange die Blockgroesse ueberschritten wird, neue Bloecke anlegen
			while ( nSize > nBlockSize )
			{
				pBlock2 = new CBlock( nBlockSize, pBlock1 );
				pBlock1->SetNextBlock( pBlock2 );
				pBlock1 = pBlock2;
				nSize -= nBlockSize;
			}

			pLastBlock = new CBlock( (sal_uInt16)nSize, pBlock1 );
			pBlock1->SetNextBlock( pLastBlock );
		}

		pCurBlock  = pFirstBlock;
	}
}

/*************************************************************************
|*
|*	  Container::Container()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

Container::Container( const Container& r )
{
	DBG_CTOR( Container, DbgCheckContainer );

	// Daten kopieren
	ImpCopyContainer( &r );
}

/*************************************************************************
|*
|*	  Container::~Container()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

Container::~Container()
{
	DBG_DTOR( Container, DbgCheckContainer );

	// Alle Bloecke loeschen
	CBlock* pBlock = pFirstBlock;
	while ( pBlock )
	{
		CBlock* pTemp = pBlock->GetNextBlock();
		delete pBlock;
		pBlock = pTemp;
	}
}

/*************************************************************************
|*
|*	  Container::ImpInsert()
|*
|*	  Beschreibung		Interne Methode zum Einfuegen eines Pointers
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	DV 01.07.97
|*
*************************************************************************/

void Container::ImpInsert( void* p, CBlock* pBlock, sal_uInt16 nIndex )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	if ( !nCount )
	{
		if ( !pBlock )
		{
			pFirstBlock = new CBlock( nInitSize, NULL, NULL );
			pLastBlock	= pFirstBlock;
			pCurBlock	= pFirstBlock;
		}
		pFirstBlock->Insert( p, nIndex, nReSize );
	}
	else
	{
		// Ist im Block die maximale Blockgroesse erreicht,
		// dann neuen Block anlegen
		if ( pBlock->Count() == nBlockSize )
		{
			// Block auftrennen
			CBlock* pNewBlock = pBlock->Split( p, nIndex, nReSize );

			// Wurde Block dahinter angehaegnt
			if ( pBlock->pNext == pNewBlock )
			{
				// Gegebenenfalls LastBlock anpassen
				if ( pBlock == pLastBlock )
					pLastBlock = pNewBlock;

				// Current-Position nachfuehren
				if ( pBlock == pCurBlock )
				{
					if ( pBlock->nCount <= nCurIndex )
					{
						if ( nIndex <= nCurIndex )
							nCurIndex++;
						pCurBlock  = pNewBlock;
                        nCurIndex = nCurIndex - pBlock->nCount; // MSVC warns here if += is used
					}
				}
			}
			else
			{
				// Gegebenenfalls FirstBlock anpassen
				if ( pBlock == pFirstBlock )
					pFirstBlock = pNewBlock;

				// Current-Position nachfuehren
				if ( pBlock == pCurBlock )
				{
					if ( nIndex <= nCurIndex )
						nCurIndex++;
					if ( pNewBlock->nCount <= nCurIndex )
                        nCurIndex = nCurIndex - pNewBlock->nCount;  // MSVC warns here if += is used
					else
						pCurBlock = pNewBlock;
				}
			}
		}
		else
		{
			// Sonst reicht normales einfuegen in den Block
			pBlock->Insert( p, nIndex, nReSize );

			// Current-Position nachfuehren
			if ( (pBlock == pCurBlock) && (nIndex <= nCurIndex) )
				nCurIndex++;
		}
	}

	// Ein neues Item im Container
	nCount++;
}

/*************************************************************************
|*
|*	  Container::Insert()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void Container::Insert( void* p )
{
	ImpInsert( p, pCurBlock, nCurIndex );
}

/*************************************************************************
|*
|*	  Container::Insert()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void Container::Insert( void* p, sal_uIntPtr nIndex )
{
	if ( nCount <= nIndex )
	{
		if ( pLastBlock )
			ImpInsert( p, pLastBlock, pLastBlock->Count() );
		else
			ImpInsert( p, NULL, 0 );
	}
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		while ( pTemp->Count() < nIndex )
		{
			nIndex -= pTemp->Count();
			pTemp	= pTemp->GetNextBlock();
		}

		ImpInsert( p, pTemp, (sal_uInt16)nIndex );
	}
}

/*************************************************************************
|*
|*	  Container::Insert()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void Container::Insert( void* pNew, void* pOld )
{
	sal_uIntPtr nIndex = GetPos( pOld );
	if ( nIndex != CONTAINER_ENTRY_NOTFOUND )
		Insert( pNew, nIndex );
}

/*************************************************************************
|*
|*	  Container::ImpRemove()
|*
|*	  Beschreibung		Interne Methode zum Entfernen eines Pointers
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::ImpRemove( CBlock* pBlock, sal_uInt16 nIndex )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	void* pOld;

	// Ist Liste danach leer
	if ( nCount == 1 )
	{
		// Block und CurIndex zuruecksetzen
		pOld = pBlock->GetObject( nIndex );
		pBlock->Reset();
		nCurIndex = 0;
	}
	else
	{
		// Ist Block nach Remove leer
		if ( pBlock->Count() == 1 )
		{
			// dann Block entfernen und Block-Pointer umsetzen
			if ( pBlock->GetPrevBlock() )
				(pBlock->GetPrevBlock())->SetNextBlock( pBlock->GetNextBlock() );
			else
				pFirstBlock = pBlock->GetNextBlock();

			if ( pBlock->GetNextBlock() )
				(pBlock->GetNextBlock())->SetPrevBlock( pBlock->GetPrevBlock() );
			else
				pLastBlock = pBlock->GetPrevBlock();

			// Current-Position nachfuehren
			if ( pBlock == pCurBlock )
			{
				if ( pBlock->GetNextBlock() )
				{
					pCurBlock = pBlock->GetNextBlock();
					nCurIndex = 0;
				}
				else
				{
					pCurBlock = pBlock->GetPrevBlock();
					nCurIndex = pCurBlock->Count()-1;
				}
			}

			pOld = pBlock->GetObject( nIndex );
			delete pBlock;
		}
		else
		{
			// Sonst Item aus dem Block entfernen
			pOld = pBlock->Remove( nIndex, nReSize );

			// Current-Position nachfuehren
			if ( (pBlock == pCurBlock) &&
				 ((nIndex < nCurIndex) || ((nCurIndex == pBlock->Count()) && nCurIndex)) )
				nCurIndex--;
		}
	}

	// Jetzt gibt es ein Item weniger
	nCount--;

	// Und den Pointer zurueckgeben, der entfernt wurde
	return pOld;
}

/*************************************************************************
|*
|*	  Container::Remove()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Remove()
{
	// Wenn kein Item vorhanden ist, NULL zurueckgeben
	if ( !nCount )
		return NULL;
	else
		return ImpRemove( pCurBlock, nCurIndex );
}

/*************************************************************************
|*
|*	  Container::Remove()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Remove( sal_uIntPtr nIndex )
{
	// Ist Index nicht innerhalb des Containers, dann NULL zurueckgeben
	if ( nCount <= nIndex )
		return NULL;
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		while ( pTemp->Count() <= nIndex )
		{
			nIndex -= pTemp->Count();
			pTemp	= pTemp->GetNextBlock();
		}

		return ImpRemove( pTemp, (sal_uInt16)nIndex );
	}
}

/*************************************************************************
|*
|*	  Container::Replace()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Replace( void* p )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	if ( !nCount )
		return NULL;
	else
		return pCurBlock->Replace( p, nCurIndex );
}

/*************************************************************************
|*
|*	  Container::Replace()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Replace( void* p, sal_uIntPtr nIndex )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Index nicht innerhalb des Containers, dann NULL zurueckgeben
	if ( nCount <= nIndex )
		return NULL;
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		while ( pTemp->Count() <= nIndex )
		{
			nIndex -= pTemp->Count();
			pTemp	= pTemp->GetNextBlock();
		}

		return pTemp->Replace( p, (sal_uInt16)nIndex );
	}
}

/*************************************************************************
|*
|*	  Container::SetSize()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void Container::SetSize( sal_uIntPtr nNewSize )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	if ( nNewSize )
	{
		// Unterscheiden sich die Groessen
		if ( nNewSize != nCount )
		{
			CBlock* pTemp;
			sal_uIntPtr	nTemp;

			// Wird verkleinert
			if ( nNewSize < nCount )
			{
				pTemp = pFirstBlock;
				nTemp = 0;
				while ( (nTemp+pTemp->Count()) < nNewSize )
				{
					nTemp += pTemp->Count();
					pTemp  = pTemp->GetNextBlock();
				}

				// Alle folgenden Bloecke loeschen
				sal_Bool	bLast = sal_False;
				CBlock* pDelNext;
				CBlock* pDelBlock = pTemp->GetNextBlock();
				while ( pDelBlock )
				{
					// Muss CurrentBlock umgesetzt werden
					if ( pDelBlock == pCurBlock )
						bLast = sal_True;
					pDelNext = pDelBlock->GetNextBlock();
					delete pDelBlock;
					pDelBlock = pDelNext;
				}

				// Block in der Groesse anpassen, oder bei Groesse 0 loeschen
				if ( nNewSize > nTemp )
				{
					pLastBlock = pTemp;
					pTemp->SetNextBlock( NULL );
					pTemp->SetSize( (sal_uInt16)(nNewSize-nTemp) );
				}
				else
				{
					pLastBlock = pTemp->GetPrevBlock();
					pLastBlock->SetNextBlock( NULL );
					delete pTemp;
				}

				nCount = nNewSize;
				if ( bLast )
				{
					pCurBlock = pLastBlock;
					nCurIndex = pCurBlock->Count()-1;
				}
			}
			else
			{
				// Auf den letzen Puffer setzen
				pTemp = pLastBlock;
				nTemp = nNewSize - nCount;

				if ( !pTemp )
				{
					// Muss mehr als ein Block angelegt werden
					if ( nNewSize <= nBlockSize )
					{
						pFirstBlock = new CBlock( (sal_uInt16)nNewSize, NULL );
						pLastBlock = pFirstBlock;
					}
					else
					{
						CBlock* pBlock1;
						CBlock* pBlock2;

						pFirstBlock = new CBlock( nBlockSize, NULL );
						pBlock1 = pFirstBlock;
						nNewSize -= nBlockSize;

						// Solange die Blockgroesse ueberschritten wird, neue Bloecke anlegen
						while ( nNewSize > nBlockSize )
						{
							pBlock2 = new CBlock( nBlockSize, pBlock1 );
							pBlock1->SetNextBlock( pBlock2 );
							pBlock1 = pBlock2;
							nNewSize -= nBlockSize;
						}

						pLastBlock = new CBlock( (sal_uInt16)nNewSize, pBlock1 );
						pBlock1->SetNextBlock( pLastBlock );
					}

					pCurBlock  = pFirstBlock;
				}
				// Reicht es, den letzen Puffer in der Groesse anzupassen
				else if ( (nTemp+pTemp->Count()) <= nBlockSize )
					pTemp->SetSize( (sal_uInt16)(nTemp+pTemp->Count()) );
				else
				{
					// Puffer auf max. Blockgroesse setzen
					nTemp -= nBlockSize - pTemp->GetSize();
					pTemp->SetSize( nBlockSize );

					CBlock* pTemp2;
					// Solange die Blockgroesse ueberschritten wird,
					// neue Bloecke anlegen
					while ( nTemp > nBlockSize )
					{
						pTemp2 = new CBlock( nBlockSize, pTemp );
						pTemp->SetNextBlock( pTemp2 );
						pTemp = pTemp2;
						nTemp -= nBlockSize;
					}

					// Den letzten Block anlegen
					if ( nTemp )
					{
						pLastBlock = new CBlock( (sal_uInt16)nTemp, pTemp );
						pTemp->SetNextBlock( pLastBlock );
					}
					else
						pLastBlock = pTemp;
				}

				nCount = nNewSize;
			}
		}
	}
	else
		Clear();
}

/*************************************************************************
|*
|*	  Container::Clear()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void Container::Clear()
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Erst alle Bloecke loeschen
	CBlock* pBlock = pFirstBlock;
	while ( pBlock )
	{
		CBlock* pTemp = pBlock->GetNextBlock();
		delete pBlock;
		pBlock = pTemp;
	}

	// Werte zuruecksetzen
	pFirstBlock = NULL;
	pLastBlock	= NULL;
	pCurBlock	= NULL;
	nCount		= 0;
	nCurIndex	= 0;
}

/*************************************************************************
|*
|*	  Container::GetCurObject()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::GetCurObject() const
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// NULL, wenn Container leer
	if ( !nCount )
		return NULL;
	else
		return pCurBlock->GetObject( nCurIndex );
}

/*************************************************************************
|*
|*	  Container::GetCurPos()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

sal_uIntPtr Container::GetCurPos() const
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// CONTAINER_ENTRY_NOTFOUND, wenn Container leer
	if ( !nCount )
		return CONTAINER_ENTRY_NOTFOUND;
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		sal_uIntPtr	nTemp = 0;
		while ( pTemp != pCurBlock )
		{
			nTemp += pTemp->Count();
			pTemp  = pTemp->GetNextBlock();
		}

		return nTemp+nCurIndex;
	}
}

/*************************************************************************
|*
|*	  Container::GetObjectPtr()
|*
|*	  Beschreibung		Interne Methode fuer Referenz-Container
|*	  Ersterstellung	TH 26.01.93
|*	  Letzte Aenderung	TH 26.01.93
|*
*************************************************************************/

void** Container::GetObjectPtr( sal_uIntPtr nIndex )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Index nicht innerhalb des Containers, dann NULL zurueckgeben
	if ( nCount <= nIndex )
		return NULL;
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		while ( pTemp->Count() <= nIndex )
		{
			nIndex -= pTemp->Count();
			pTemp	= pTemp->GetNextBlock();
		}

		// Item innerhalb des gefundenen Blocks zurueckgeben
		return pTemp->GetObjectPtr( (sal_uInt16)nIndex );
	}
}

/*************************************************************************
|*
|*	  Container::GetObject()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::GetObject( sal_uIntPtr nIndex ) const
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Index nicht innerhalb des Containers, dann NULL zurueckgeben
	if ( nCount <= nIndex )
		return NULL;
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		while ( pTemp->Count() <= nIndex )
		{
			nIndex -= pTemp->Count();
			pTemp	= pTemp->GetNextBlock();
		}

		// Item innerhalb des gefundenen Blocks zurueckgeben
		return pTemp->GetObject( (sal_uInt16)nIndex );
	}
}

/*************************************************************************
|*
|*	  Container::GetPos()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

sal_uIntPtr Container::GetPos( const void* p ) const
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	void**	pNodes;
	CBlock* pTemp;
	sal_uIntPtr	nTemp;
	sal_uInt16	nBlockCount;
	sal_uInt16	i;

	// Block suchen
	pTemp = pFirstBlock;
	nTemp = 0;
	while ( pTemp )
	{
		pNodes = pTemp->GetNodes();
		i = 0;
		nBlockCount = pTemp->Count();
		while ( i < nBlockCount )
		{
			if ( p == *pNodes )
				return nTemp+i;
			pNodes++;
			i++;
		}
		nTemp += nBlockCount;
		pTemp  = pTemp->GetNextBlock();
	}

	return CONTAINER_ENTRY_NOTFOUND;
}

/*************************************************************************
|*
|*	  Container::GetPos()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 14.09.94
|*	  Letzte Aenderung	TH 14.09.94
|*
*************************************************************************/

sal_uIntPtr Container::GetPos( const void* p, sal_uIntPtr nStartIndex,
						 sal_Bool bForward ) const
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Index nicht innerhalb des Containers, dann NOTFOUND zurueckgeben
	if ( nCount <= nStartIndex )
		return CONTAINER_ENTRY_NOTFOUND;
	else
	{
		void**	pNodes;
		sal_uInt16	nBlockCount;
		sal_uInt16	i;

		// Block suchen
		CBlock* pTemp = pFirstBlock;
		sal_uIntPtr	nTemp = 0;
		while ( nTemp+pTemp->Count() <= nStartIndex )
		{
			nTemp += pTemp->Count();
			pTemp  = pTemp->GetNextBlock();
		}

		// Jetzt den Pointer suchen
		if ( bForward )
		{
			// Alle Bloecke durchrsuchen
			i = (sal_uInt16)(nStartIndex - nTemp);
			pNodes = pTemp->GetObjectPtr( i );
			do
			{
				nBlockCount = pTemp->Count();
				while ( i < nBlockCount )
				{
					if ( p == *pNodes )
						return nTemp+i;
					pNodes++;
					i++;
				}
				nTemp += nBlockCount;
				pTemp  = pTemp->GetNextBlock();
				if ( pTemp )
				{
					i = 0;
					pNodes = pTemp->GetNodes();
				}
				else
					break;
			}
			while ( sal_True );
		}
		else
		{
			// Alle Bloecke durchrsuchen
			i = (sal_uInt16)(nStartIndex-nTemp)+1;
			pNodes = pTemp->GetObjectPtr( i-1 );
			do
			{
				do
				{
					if ( p == *pNodes )
						return nTemp+i-1;
					pNodes--;
					i--;
				}
				while ( i );
				nTemp -= pTemp->Count();
				pTemp  = pTemp->GetPrevBlock();
				if ( pTemp )
				{
					i = pTemp->Count();
					// Leere Bloecke in der Kette darf es nicht geben. Nur
					// wenn ein Block existiert, darf dieser leer sein
					pNodes = pTemp->GetObjectPtr( i-1 );
				}
				else
					break;
			}
			while ( sal_True );
		}
	}

	return CONTAINER_ENTRY_NOTFOUND;
}

/*************************************************************************
|*
|*	  Container::Seek()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Seek( sal_uIntPtr nIndex )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist der Container leer, dann NULL zurueckgeben
	if ( nCount <= nIndex )
		return NULL;
	else
	{
		// Block suchen
		CBlock* pTemp = pFirstBlock;
		while ( pTemp->Count() <= nIndex )
		{
			nIndex -= pTemp->Count();
			pTemp	= pTemp->GetNextBlock();
		}

		// Item innerhalb des gefundenen Blocks zurueckgeben
		pCurBlock = pTemp;
		nCurIndex = (sal_uInt16)nIndex;
		return pCurBlock->GetObject( nCurIndex );
	}
}

/*************************************************************************
|*
|*	  Container::First()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::First()
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Container leer, dann NULL zurueckgeben
	if ( !nCount )
		return NULL;
	else
	{
		// Block und Index setzen und ersten Pointer zurueckgeben
		pCurBlock = pFirstBlock;
		nCurIndex = 0;
		return pCurBlock->GetObject( nCurIndex );
	}
}

/*************************************************************************
|*
|*	  Container::Last()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Last()
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Container leer, dann NULL zurueckgeben
	if ( !nCount )
		return NULL;
	else
	{
		// Block und Index setzen und ersten Pointer zurueckgeben
		pCurBlock = pLastBlock;
		nCurIndex = pCurBlock->Count()-1;
		return pCurBlock->GetObject( nCurIndex );
	}
}

/*************************************************************************
|*
|*	  Container::Next()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Next()
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Container leer, dann NULL zurueckgeben, ansonsten preufen ob
	// naechste Position noch im aktuellen Block ist. Falls nicht, dann
	// einen Block weiterschalten (geht ohne Gefahr, da leere Bloecke
	// nicht vorkommen duerfen, es sein denn, es ist der einzige).
	if ( !nCount )
		return NULL;
	else if ( (nCurIndex+1) < pCurBlock->Count() )
		return pCurBlock->GetObject( ++nCurIndex );
	else if ( pCurBlock->GetNextBlock() )
	{
		pCurBlock = pCurBlock->GetNextBlock();
		nCurIndex = 0;
		return pCurBlock->GetObject( nCurIndex );
	}
	else
		return NULL;
}

/*************************************************************************
|*
|*	  Container::Prev()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

void* Container::Prev()
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Ist Container leer, dann NULL zurueckgeben, ansonsten preufen ob
	// vorherige Position noch im aktuellen Block ist. Falls nicht, dann
	// einen Block zurueckschalten (geht ohne Gefahr, da leere Bloecke
	// nicht vorkommen duerfen, es sein denn, es ist der einzige).
	if ( !nCount )
		return NULL;
	else if ( nCurIndex )
		return pCurBlock->GetObject( --nCurIndex );
	else if ( pCurBlock->GetPrevBlock() )
	{
		pCurBlock = pCurBlock->GetPrevBlock();
		nCurIndex = pCurBlock->Count() - 1;
		return pCurBlock->GetObject( nCurIndex );
	}
	else
		return NULL;
}

/*************************************************************************
|*
|*	  Container::operator =()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

Container& Container::operator =( const Container& r )
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	// Erst alle Bloecke loeschen
	CBlock* pBlock = pFirstBlock;
	while ( pBlock )
	{
		CBlock* pTemp = pBlock->GetNextBlock();
		delete pBlock;
		pBlock = pTemp;
	}

	// Daten kopieren
	ImpCopyContainer( &r );
	return *this;
}

/*************************************************************************
|*
|*	  Container::operator ==()
|*
|*	  Beschreibung		CONTNR.SDW
|*	  Ersterstellung	TH 17.09.91
|*	  Letzte Aenderung	TH 17.09.91
|*
*************************************************************************/

sal_Bool Container::operator ==( const Container& r ) const
{
	DBG_CHKTHIS( Container, DbgCheckContainer );

	if ( nCount != r.nCount )
		return sal_False;

	sal_uIntPtr i = 0;
	while ( i < nCount )
	{
		if ( GetObject( i ) != r.GetObject( i ) )
			return sal_False;
		i++;
	}

	return sal_True;
}