// Copyright (c) 2001-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of the License "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// Folding and decomposition implementation

// 

//

#include "FoldDecomp.inl"

#include "CompareImp.h"

#include "u32std.h"

#define ARRAY_LENGTH(a) (static_cast<TInt>(sizeof(a)/sizeof(a[0])))

////////////////////////////////////////////////////////////////////////////////////////////

// Global functions

////////////////////////////////////////////////////////////////////////////////////////////

/**

@internalComponent

*/

TChar UTF16ToChar(const TText16* a)

	{

	if (0xD800 <= a[0])

		{

		if (a[0] < 0xE000)

			{

            if (a[0] < 0xDC00 && ::IsLowSurrogate(a[1]))

				{

                TChar c = ::PairSurrogates(a[0], a[1]);

				if ((c & 0xFFFE) != 0xFFFE)

					return c;

				}

			return 0xFFFF;

			}

		if (a[0] == 0xFFFE)

			return 0xFFFF;

		}

	return a[0];

	}

/**

Is a character a base character (ETrue) or a combiner (EFalse)?

For now, we will treat all control characters as base characters.

@internalComponent

*/

TBool IsBaseCharacter(TChar a)

	{

	if(a < 0x220)

        {

		// These Unicode characters are all assigned

		// and none of them is a combining character

		return ETrue;

        }

	return (a.GetCategory() & 0xFFF0) - TChar::EMarkGroup;

	}

/**

@internalComponent

*/

inline TInt GetDecompositionIndex(TChar a)

	{

    TInt i = DecompositionHashStart(a);

	TUint32 v = KUnicodeToIndexHash[i];

	if (!v)

		return -1;

	if ((v & 0xFFFFF) != a)

		{

        TInt step = DecompositionHashStep(a);

		do	{

			i = (i + step) & KDecompositionHashBitmask;

			v = KUnicodeToIndexHash[i];

			if (!v)

				return -1;

			} while ((v & 0xFFFFF) != a);

		}

// it is important that this is an unsigned shift

	return static_cast<TInt>(v >> 20);

	}

/**

Will not work if an invalid index is passed.

@internalComponent

*/

static TUTF32Iterator GetFoldedDecomposition(TInt aIndex)

	{

	TInt singletonIndex = aIndex - (sizeof(KNonSingletonFolds)/sizeof(KNonSingletonFolds[0])/2);

	if (0 <= singletonIndex)

		return TUTF32Iterator(KSingletonFolds + singletonIndex);

	const TText* start = KNonSingletonFolds + aIndex * 2;

	if (*start != KLongD)

		return TUTF32Iterator(start, start + 2,

			TUTF32Iterator::EStartsWithValidCharacter);

	TInt longDecompIndex = start[1];

	start = KLongDecompositions + (longDecompIndex & 0xFFF);

	return TUTF32Iterator(start, start + (longDecompIndex >> 12) + 3,

		TUTF32Iterator::EStartsWithValidCharacter);

	}

/**

@internalComponent

*/

static TChar GetFirstFoldedChar(TChar a)

	{

    TInt index = ::GetDecompositionIndex(a);

    return index < 0? a : ::GetFoldedDecomposition(index).Current();

	}

/**

@internalComponent

*/

static TBool FirstFoldedCodeIsNot(TInt aNonSurrogate, TInt aFoldedNonSurrogate)

	{

    TInt index = ::GetDecompositionIndex(aNonSurrogate);

	if (index < 0)

		return aNonSurrogate - aFoldedNonSurrogate;

	TInt singletonIndex = index - (sizeof(KNonSingletonFolds)/sizeof(KNonSingletonFolds[0])/2);

	if (0 < singletonIndex)

		return KSingletonFolds[singletonIndex] - aFoldedNonSurrogate;

	const TText* start = KNonSingletonFolds + index * 2;

	if (start[0] == KLongD)

		start = KLongDecompositions + (start[1] & 0xFFF);

	return *start - aFoldedNonSurrogate;

	}

/**

@internalComponent

*/

static TInt GetClass(TFoldedDecompIterator& a)

	{

	ASSERT(!a.AtEnd());

	a.EnterFoldedSequence();

	TChar ch = a.Current();

	TInt cl = ch.GetCombiningClass();

	if (cl == 0)

		// Assume starters have been folded from ypogegrammeni

		cl = 240;

	return cl;

	}

////////////////////////////////////////////////////////////////////////////////////////////

// TUTF32Iterator

////////////////////////////////////////////////////////////////////////////////////////////

/**

@internalComponent

*/

void TUTF32Iterator::Next()

	{

	ASSERT(iStart != iEnd);

	while (++iStart != iEnd)

		{

        iCurrent = ::UTF16ToChar(iStart);

		if (iCurrent != 0xFFFF)

			return;

		}

	}

/**

Locates a base character in a string using a folded comparision. Will not find combining 

characters, nor will it consider Korean combining Jamo to be equivalent to Hangul.

@internalComponent

*/

TBool TUTF32Iterator::LocateFoldedBaseCharacter(TChar aChar)

	{

	// A quick shortcut for simple rejections

	if (aChar < 0xFFFF)

		{

        while (iStart != iEnd && *iStart < 0xD800 && ::FirstFoldedCodeIsNot(*iStart, aChar))

			++iStart;

		if (iStart != iEnd)

			{

            iCurrent = ::UTF16ToChar(iStart);

			if (iCurrent == 0xFFFF)

				Next();

			}

		}

	while (!AtEnd())

		{

        TChar foldedChar = ::GetFirstFoldedChar(iCurrent);

		if (aChar == foldedChar)

			return ETrue;

		Next();

		}

	return EFalse;

	}

////////////////////////////////////////////////////////////////////////////////////////////

// TFoldedDecompIterator

////////////////////////////////////////////////////////////////////////////////////////////

/**

@internalComponent

*/

TFoldedDecompIterator::TFoldedDecompIterator(const TUTF32Iterator& a)

	{

	Set(a);

	}

/**

@internalComponent

*/

TBool TFoldedDecompIterator::AtEnd() const

	{

	return iOriginal.AtEnd();

	}

/**

@internalComponent

*/

TBool TFoldedDecompIterator::AtEndOrWildcard() const

	{

	// neither '?' nor '*' have decomposition sequences, so we can assume that

	// if we are pointing at one or the other, we don't need to check if we

	// are in a decomposition sequence or not.

	return iOriginal.AtEnd() || iOriginal.Current() == '?' || iOriginal.Current() == '*';

	}

/**

@internalComponent

*/

TBool TFoldedDecompIterator::EnterFoldedSequence()

	{

	ASSERT(!AtEnd());

	return !IsInFoldedSequence() && StrictEnterFoldedSequence();

	}

/**

Enter folded sequence, assuming that we are not already in one

@internalComponent

*/

TBool TFoldedDecompIterator::StrictEnterFoldedSequence()

	{

	ASSERT(!AtEnd());

	ASSERT(!IsInFoldedSequence());

    TInt index = ::GetDecompositionIndex(iOriginal.Current());

	if (index < 0)

		return EFalse;

	iFolded = ::GetFoldedDecomposition(index);

	return ETrue;

	}

/**

An iota might have folded from a combining ypogegrammeni.

If the current character is a base character, this function will

detect whether it was folded from a combining character (and

therefore does not constitute a grapheme boundary).

@internalComponent

*/

TBool TFoldedDecompIterator::CurrentIsBaseFoldedFromCombiner() const

	{

	if (!IsInFoldedSequence())

		return EFalse;

	// The only character that does this is Ypogerammeni, which folds to iota

	if (iFolded.Current() != 0x3B9)

		return EFalse;

	// If the unfolded character is a combiner then it cannot contain an iota,

	// so it must be an ypogegrammeni that has been folded to one.

	// This will catch 0x345, the ypogegrammeni itself.

    if (!::IsBaseCharacter(iOriginal.Current()))

		return ETrue;

	// Otherwise the base character will be at the start of the decomposition

	// sequence. We will assume that it is folded from a genuine iota if and

	// only if there is an iota at the start of the folded decomposition

	// sequence. (In theory there might be an iota with a combining

	// ypogegrammeni, but in practice this will not occur).

	TInt index = ::GetDecompositionIndex(iOriginal.Current());

	ASSERT(0 <= index);

	TUTF32Iterator folded = ::GetFoldedDecomposition(index);

	return folded.Current() != 0x3B9;

	}

/**

@internalComponent

*/

TChar TFoldedDecompIterator::Current() const

	{

	ASSERT(!AtEnd());

	return IsInFoldedSequence()? iFolded.Current() : iOriginal.Current();

	}

/** 

Move past this code if it matches unfolded or folded 

@internalComponent

*/

TBool TFoldedDecompIterator::Match(TChar aCode)

	{

	ASSERT(!AtEnd());

	if (!IsInFoldedSequence())

		{

		if (aCode == iOriginal.Current())

			{

			iOriginal.Next();

			return ETrue;

			}

		if (!StrictEnterFoldedSequence())

			return EFalse;

		}

	ASSERT(IsInFoldedSequence());

	if (aCode == iFolded.Current())

		{

		iFolded.Next();

		if (iFolded.AtEnd())

			iOriginal.Next();

		return ETrue;

		}

	return EFalse;

	}

/** 

Move this and argument past matching character. 

@internalComponent

*/

TBool TFoldedDecompIterator::Match(TFoldedDecompIterator& aThat)

	{

	ASSERT(!AtEnd());

	if (!IsInFoldedSequence())

		{

		if ( aThat.Match(iOriginal.Current()) )

			{

			iOriginal.Next();

			return ETrue;

			}

		if (!StrictEnterFoldedSequence())

			return EFalse;

		}

	ASSERT(IsInFoldedSequence());

	if ( aThat.Match(iFolded.Current()) )

		{

		iFolded.Next();

		if (iFolded.AtEnd())

			iOriginal.Next();

		return ETrue;

		}

	return EFalse;

	}

/** 

@internalComponent

*/

void TFoldedDecompIterator::Next()

	{

	ASSERT(!AtEnd());

	if (IsInFoldedSequence())

		{

		iFolded.Next();

		if (IsInFoldedSequence())

			return;

		}

	iOriginal.Next();

	}

////////////////////////////////////////////////////////////////////////////////////////////

// TFoldedSortedDecompIterator

////////////////////////////////////////////////////////////////////////////////////////////

/**

Set this iterator to iterate over the next combining characters.

Iotas in folded sequences are assumed to be character class 240

(combining ypogegrammeni). Next() must be used once before

the first call to Current(), as long as AtEnd() returns false.

@param aBase Sets the start of the iteration. This value is advanced to the

             end of the iteration.

@return The number of codes in the iteration.

@internalComponent

*/

TInt TFoldedSortedDecompIterator::Set(TFoldedDecompIterator &aBase)

	{

	iStart = aBase;

	TInt length = 0;

	iCurrentClass = 256;

	const TUnicodeDataSet* charDataSet = GetLocaleCharSet()->iCharDataSet;

	// Find the next starter (i.e. character with combining class 0).

	// We must not count iota folded from ypogegrammeni.

	// Ypogegrammeni has combining class 240.

	// Iota has combining class 0.

	// Also we will be searching for the character with the smallest

	// combining class to start at.

	while (!aBase.AtEnd())

		{

		aBase.EnterFoldedSequence();

		TChar ch = aBase.Current();

		TInt cl = TUnicode(TUint(ch)).GetCombiningClass(charDataSet);

		if (cl == 0)

			{

			if (aBase.CurrentIsBaseFoldedFromCombiner())

				cl = 240;

			else

				break;

			}

		if (cl < iCurrentClass)

			{

			iCurrentClass = cl;

			iCurrent = aBase;

			iCurrentCount = length;

			}

		++length;

		aBase.Next();

		}

	iRemaining = length;

	iLength = length;

	ASSERT(iLength == 0 || iCurrentClass < 256);

	return length;

	}

/** 

Set this iterator so that AtEnd() returns ETrue. 

@internalComponent

*/

void TFoldedSortedDecompIterator::Set()

	{

	iRemaining = 0;

	}

/** 

@internalComponent

*/

TBool TFoldedSortedDecompIterator::AtEnd() const

	{

	return iRemaining == 0;

	}

/** 

@internalComponent

*/

TChar TFoldedSortedDecompIterator::Current() const

	{

	ASSERT(!AtEnd());

	return iCurrent.Current();

	}

/** 

@internalComponent

*/

void TFoldedSortedDecompIterator::Next()

	{

	ASSERT(!AtEnd());

	--iRemaining;

	while (++iCurrentCount != iLength)

		{

		iCurrent.Next();

        if (::GetClass(iCurrent) == iCurrentClass)

			return;

		}

	// We have not found any more of the same class, so we will look

	// for the smallest one larger.

	TInt minClass = 256;

	TFoldedDecompIterator searcher(iStart);

	TInt searchCount = 0;

	while (searchCount != iLength)

		{

        TInt cl = ::GetClass(searcher);

		if (iCurrentClass < cl && cl < minClass)

			{

			minClass = cl;

			iCurrentCount = searchCount;

			iCurrent = searcher;

			}

		++searchCount;

		searcher.Next();

		}

	iCurrentClass = minClass;

	ASSERT(minClass < 256 || AtEnd());

	}

////////////////////////////////////////////////////////////////////////////////////////////

// TFoldedCanonicalIterator

////////////////////////////////////////////////////////////////////////////////////////////

/** 

@internalComponent

*/

TFoldedCanonicalIterator::TFoldedCanonicalIterator(const TUTF32Iterator& a)

	{

	iBase.Set(a);

	iSorted.Set();

    if(!iBase.AtEnd())

        {

	    iBase.EnterFoldedSequence();

	    if (iBase.Current().GetCombiningClass() != 0 || iBase.CurrentIsBaseFoldedFromCombiner())

            {

		    iSorted.Set(iBase);

            }

        }

	}

/** 

@internalComponent

*/

TBool TFoldedCanonicalIterator::AtEnd() const

	{

	return iSorted.AtEnd() && iBase.AtEnd();

	}

/** 

@internalComponent

*/

TChar TFoldedCanonicalIterator::Current() const

	{

	ASSERT(!iBase.AtEnd() || !iSorted.AtEnd());

	return iSorted.AtEnd()? iBase.Current() : iSorted.Current();

	}

/** 

@internalComponent

*/

void TFoldedCanonicalIterator::Next(const TUnicodeDataSet* aCharDataSet)

	{

	ASSERT(!iBase.AtEnd() || !iSorted.AtEnd());

	if (!iSorted.AtEnd())

		{

		iSorted.Next();

		return;

		}

	iBase.Next();

    if(!iBase.AtEnd())

        {