/**************************************************************
 *
 * 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"

#define _TOOLS_TABLE_CXX

// -----------------------------------------------------------------------
#include <tools/debug.hxx>
#include <impcont.hxx>
#include <tools/table.hxx>

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

sal_uIntPtr Table::ImplGetIndex( sal_uIntPtr nKey, sal_uIntPtr* pIndex ) const
{
	// Abpruefen, ob der erste Key groesser als der Vergleichskey ist
	if ( !nCount || (nKey < (sal_uIntPtr)Container::ImpGetObject(0)) )
		return TABLE_ENTRY_NOTFOUND;

	sal_uIntPtr	nLow;
	sal_uIntPtr	nHigh;
	sal_uIntPtr	nMid;
	sal_uIntPtr	nCompareKey;
	void**	pNodes = Container::ImpGetOnlyNodes();

	// Binaeres Suchen
	nLow  = 0;
	nHigh = nCount-1;
	if ( pNodes )
	{
		do
		{
			nMid = (nLow + nHigh) / 2;
			nCompareKey = (sal_uIntPtr)pNodes[nMid*2];
			if ( nKey < nCompareKey )
				nHigh = nMid-1;
			else
			{
				if ( nKey > nCompareKey )
					nLow = nMid + 1;
				else
					return nMid*2;
			}
		}
		while ( nLow <= nHigh );
	}
	else
	{
		do
		{
			nMid = (nLow + nHigh) / 2;
			nCompareKey = (sal_uIntPtr)Container::ImpGetObject( nMid*2 );
			if ( nKey < nCompareKey )
				nHigh = nMid-1;
			else
			{
				if ( nKey > nCompareKey )
					nLow = nMid + 1;
				else
					return nMid*2;
			}
		}
		while ( nLow <= nHigh );
	}

	if ( pIndex )
	{
		if ( nKey > nCompareKey )
			*pIndex = (nMid+1)*2;
		else
			*pIndex = nMid*2;
	}

	return TABLE_ENTRY_NOTFOUND;
}

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

Table::Table( sal_uInt16 _nInitSize, sal_uInt16 _nReSize ) :
		   Container( CONTAINER_MAXBLOCKSIZE, _nInitSize*2, _nReSize*2 )
{
	DBG_ASSERT( _nInitSize <= 32767, "Table::Table(): InitSize > 32767" );
	DBG_ASSERT( _nReSize <= 32767, "Table::Table(): ReSize > 32767" );
	nCount = 0;
}

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

sal_Bool Table::Insert( sal_uIntPtr nKey, void* p )
{
	// Tabellenelement einsortieren
	sal_uIntPtr i;
	if ( nCount )
	{
		if ( nCount <= 24 )
		{
			sal_uInt16 n = 0;
			sal_uInt16 nTempCount = (sal_uInt16)nCount * 2;
			//<!--Modified by PengYunQuan for resolving a NULL pointer access

			if( void** pNodes = Container::ImpGetOnlyNodes() )
			{
				sal_uIntPtr  nCompareKey = (sal_uIntPtr)(*pNodes);
				while ( nKey > nCompareKey )
				{
					n += 2;
					pNodes += 2;
					if ( n < nTempCount )
						nCompareKey = (sal_uIntPtr)(*pNodes);
					else
					{
						nCompareKey = 0;
						break;
					}
				}

				// Testen, ob sich der Key schon in der Tabelle befindet
				if ( nKey == nCompareKey )
					return sal_False;

				i = n;
			}
			else
			{
				i = 0;
				if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND )
					return sal_False;
			}
			//-->Modified by PengYunQuan for resolving a NULL pointer access
		}
		else
		{
			i = 0;
			if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND )
				return sal_False;
		}
	}
	else
		i = 0;

	// Eintrag einfuegen (Key vor Pointer)
	Container::Insert( (void*)nKey, i );
	Container::Insert( p, i+1 );

	// Ein neuer Eintrag
	nCount++;

	return sal_True;
}

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

void* Table::Remove( sal_uIntPtr nKey )
{
	// Index besorgen
	sal_uIntPtr nIndex = ImplGetIndex( nKey );

	// Testen, ob sich der Key in der Tabelle befindet
	if ( nIndex == TABLE_ENTRY_NOTFOUND )
		return NULL;

	// Itemanzahl erniedrigen
	nCount--;

	// Key entfernen
	Container::Remove( nIndex );

	// Pointer entfernen und zurueckgeben
	return Container::Remove( nIndex );
}

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

void* Table::Replace( sal_uIntPtr nKey, void* p )
{
	// Index abfragen
	sal_uIntPtr nIndex = ImplGetIndex( nKey );

	// Existiert kein Eintrag mit dem Schluessel
	if ( nIndex == TABLE_ENTRY_NOTFOUND )
		return NULL;
	else
		return Container::Replace( p, nIndex+1 );
}

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

void* Table::Get( sal_uIntPtr nKey ) const
{
	// Index besorgen
	sal_uIntPtr nIndex = ImplGetIndex( nKey );

	// Testen, ob sich der Key in der Tabelle befindet
	if ( nIndex == TABLE_ENTRY_NOTFOUND )
		return NULL;
	else
		return Container::ImpGetObject( nIndex+1 );
}

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

void* Table::GetCurObject() const
{
	return Container::ImpGetObject( Container::GetCurPos()+1 );
}

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

sal_uIntPtr Table::GetKey( const void* p ) const
{
	sal_uIntPtr nIndex = 0;

	// Solange noch Eintraege Vorhanden sind
	while ( nIndex < nCount )
	{
		// Stimmt der Pointer ueberein, wird der Key zurueckgegeben
		if ( p == Container::ImpGetObject( (nIndex*2)+1 ) )
			return (sal_uIntPtr)Container::ImpGetObject( nIndex*2 );

		nIndex++;
	}

	return TABLE_ENTRY_NOTFOUND;
}

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

sal_Bool Table::IsKeyValid( sal_uIntPtr nKey ) const
{
	return (ImplGetIndex( nKey ) != TABLE_ENTRY_NOTFOUND) ? sal_True : sal_False;
}

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

sal_uIntPtr Table::GetUniqueKey( sal_uIntPtr nStartKey ) const
{
	DBG_ASSERT( (nStartKey > 1) && (nStartKey < 0xFFFFFFFF),
				"Table::GetUniqueKey() - nStartKey == 0 or nStartKey >= 0xFFFFFFFF" );

	if ( !nCount )
		return nStartKey;

	sal_uIntPtr nLastKey = (sal_uIntPtr)Container::GetObject( (nCount*2)-2 );
	if ( nLastKey < nStartKey )
		return nStartKey;
	else
	{
		if ( nLastKey < 0xFFFFFFFE )
			return nLastKey+1;
		else
		{
			sal_uIntPtr nPos;
			sal_uIntPtr nTempPos = ImplGetIndex( nStartKey, &nPos );
			if ( nTempPos != TABLE_ENTRY_NOTFOUND )
				nPos = nTempPos;
			nLastKey = (sal_uIntPtr)Container::GetObject( nPos );
			if ( nStartKey < nLastKey )
				return nStartKey;
			while ( nLastKey < 0xFFFFFFFE )
			{
				nPos += 2;
				nLastKey++;
				if ( nLastKey != (sal_uIntPtr)Container::GetObject( nPos ) )
					return nLastKey;
			}
		}
	}

	return 0;
}

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

sal_uIntPtr Table::SearchKey( sal_uIntPtr nKey, sal_uIntPtr* pPos ) const
{
	*pPos = 0;
	sal_uIntPtr nPos = ImplGetIndex( nKey, pPos );
	if ( nPos != TABLE_ENTRY_NOTFOUND )
	{
		nPos /= 2;
		*pPos = nPos;
	}
	else
		*pPos /= 2;
	return nPos;
}

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

void* Table::Seek( sal_uIntPtr nKey )
{
	// Testen, ob ein Eintrag vorhanden ist
	if ( nCount )
	{
		sal_uIntPtr nIndex = ImplGetIndex( nKey );

		// Ist Key nicht enthalten
		if ( nIndex == TABLE_ENTRY_NOTFOUND )
			return NULL;
		else
		{
			// Index setzen
			Container::Seek( nIndex );

			// Pointer zurueckgeben
			return Container::ImpGetObject( Container::GetCurPos() + 1 );
		}
	}
	else
		return NULL;
}

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

void* Table::Seek( void* p )
{
	sal_uIntPtr nKey = GetKey( p );

	// Ist Key vorhanden, dann als aktuellen Eintrag setzen
	if ( nKey != TABLE_ENTRY_NOTFOUND )
		return Seek( nKey );
	else
		return NULL;
}

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

void* Table::First()
{
	// Testen, ob ein Eintrag vorhanden ist
	if ( nCount )
	{
		// Auf ersten Eintag setzen
		Container::First();

		// Pointer zurueckgeben
		return Container::ImpGetObject( 1 );
	}
	else
		return NULL;
}

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

void* Table::Last()
{
	// Testen, ob ein Eintrag vorhanden ist
	if ( nCount )
	{
		// Last auf letzten Eintrag setzen
		void* p = Container::Last();
		Container::Prev();

		// Pointer zurueckgeben
		return p;
	}
	else
		return NULL;
}

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

void* Table::Next()
{
	// Ueber den Pointer weiterschalten
	Container::Next();

	// Nachsten Eintag
	Container::Next();

	// Pointer vom naechsten Key zurueckgeben
	return Container::ImpGetObject( Container::GetCurPos() + 1 );
}

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

void* Table::Prev()
{
	// Ueber den Pointer weiterschalten
	void* p = Container::Prev();

	// Nachsten Eintag
	Container::Prev();

	// Pointer vom vorherigen Key zurueckgeben
	return p;
}