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

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

/**

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

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

/**

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::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;

	}

/** 

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

*/

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

*/

void TFoldedCanonicalIterator::Next(const TUnicodeDataSet* aCharDataSet)

	{

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

	if (!iSorted.AtEnd())

		{

		iSorted.Next();

		return;

		}

	iBase.Next();

    if(!iBase.AtEnd())

        {

	    iBase.EnterFoldedSequence();

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

           {

		    iSorted.Set(iBase);

            }

        }

	}

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

// Folding - Global functions and structures

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

/** 

@internalComponent

*/

struct TEndTester 

    { 

    typedef enum {EGenuine, EWildcard} TType;

    inline TEndTester(TType aType) :

        iType(aType)

        {

        }

    inline TBool operator()(const TFoldedDecompIterator& a) const

        {

        return iType == EGenuine ? a.AtEnd() : a.AtEndOrWildcard();

        } 

private:

    TType iType;

    };

/**

Consumes as much of aCandidate as matches aSearchTerm up to the next '?' or

'*' wildcard or the end of aSearchTerm.

It is assumed that the search term begins with a base character.

Returns true if and only if the whole search term was matched

with a whole number of UTF16s in the candidate string.

On return of ETrue the candidate string iterator will have consumed the

matching characters the search term will have had all its matching characters

consumed.

@internalComponent

*/

TBool ConsumeFoldedMatch(TUTF32Iterator& aCandidateString, TUTF32Iterator& aSearchTerm,

                         const TEndTester& aEndTester)

	{

	TBool assumeBase = ETrue;

	TFoldedDecompIterator st(aSearchTerm);

	TFoldedDecompIterator cs(aCandidateString);

	while (!aEndTester(st))

		{

		if (cs.AtEnd())

			return EFalse;

		if (st.Match(cs))

			{

			assumeBase = EFalse;

			if (aEndTester(st))

				{

                // We have a match...

                if (cs.IsInFoldedSequence())

                    // but it was against only part of a character

                    // in the original string, so we fail.

                    return EFalse;

				aCandidateString = cs.BaseIterator();

				aSearchTerm = st.BaseIterator();

				return ETrue;

				}

			continue;

			}

		// did not match. We need to re-order canonically.

		if (assumeBase)

			// The first characters did not match.. do not bother

			// to re-order.

			return EFalse;

		TFoldedSortedDecompIterator csc;

		TInt cscLength = csc.Set(cs);

		if (cscLength < 2)

			// If there are less than two characters to be reordered,

			// there is no hope of getting a match by re-ordering

			return EFalse;

		TFoldedSortedDecompIterator stc;

		if (cscLength != stc.Set(st))

			// if the strings have differing numbers of characters,

			// there can be no match

			return EFalse;

		while (!stc.AtEnd())