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

        {

	    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())

			{

			ASSERT(!csc.AtEnd());

			if (stc.Current() != csc.Current())

				// well, we tried.

				return EFalse;

			stc.Next();

			csc.Next();

			}

		}

	// If the candidate string is in a folded sequence, then

	// we should not accept the match, as we require all matches

	// to be for a whole number of characters in the original string.

	if (cs.IsInFoldedSequence())

		return EFalse;

	aCandidateString = cs.BaseIterator();

	aSearchTerm = st.BaseIterator();

	return ETrue;

	}

/** 

@internalComponent

*/

TBool ConsumeFoldedMatchWholeGraphemes(TUTF32Iterator& aCandidateString, TUTF32Iterator& aSearchTerm, 

                                       const TEndTester& aEndTester)

	{

    if (!::ConsumeFoldedMatch(aCandidateString, aSearchTerm, aEndTester))

		return EFalse;

    return aCandidateString.AtEnd() || ::IsBaseCharacter(aCandidateString.Current());

	}

/** 

@internalComponent

*/

static TBool ConsumeGrapheme(TUTF32Iterator& a)

	{

	if (a.AtEnd())

		return EFalse;

	a.Next();

    while (!a.AtEnd() && !::IsBaseCharacter(a.Current()))

		a.Next();

	return ETrue;

	}

/** 

@internalComponent

*/

TBool MatchSectionFolded(TUTF32Iterator& aCandidateString, TUTF32Iterator& aSearchTerm)

	{

    TEndTester endTester(TEndTester::EWildcard);

    while(::ConsumeFoldedMatchWholeGraphemes(aCandidateString, aSearchTerm, endTester))

		{

		if (aSearchTerm.AtEnd() || aSearchTerm.Current() == '*')

			return ETrue;

		ASSERT(aSearchTerm.Current() == '?');

		aSearchTerm.Next();

        if (!::ConsumeGrapheme(aCandidateString))

			return EFalse;

		}

	return EFalse;

	}

/** 

@internalComponent

*/

TBool FindMatchSectionFolded(TUTF32Iterator& aCandidateString, TUTF32Iterator& aSearchTerm)

	{

	// match as many graphemes as there are leading ?s

	while (!aSearchTerm.AtEnd()

		&& aSearchTerm.Current() != '*' && aSearchTerm.Current() == '?')

		{

        if (!::ConsumeGrapheme(aCandidateString))

			return EFalse;

		aSearchTerm.Next();

		}

	if (aSearchTerm.AtEnd() || aSearchTerm.Current() == '*')

		return ETrue;

    TChar firstCharOfSearchTerm = ::GetFirstFoldedChar(aSearchTerm.Current());

	TUTF32Iterator savedST(aSearchTerm);

	while (aCandidateString.LocateFoldedBaseCharacter(firstCharOfSearchTerm))

		{

		TUTF32Iterator savedCS = aCandidateString;

		if (::MatchSectionFolded(aCandidateString, aSearchTerm))

			return ETrue;

		aSearchTerm = savedST;

		aCandidateString = savedCS;

		aCandidateString.Next();

		}

	return EFalse;

	}

/** 

@internalComponent

*/

TBool MatchStringFolded(const TText16* aCandidateStringStart, const TText16* aCandidateStringEnd,

                        const TText16* aSearchTermStart, const TText16* aSearchTermEnd)

	{

	TUTF32Iterator candidate(aCandidateStringStart, aCandidateStringEnd);

	TUTF32Iterator searchTerm(aSearchTermStart, aSearchTermEnd);

	// First section of search term must match exactly at the start of the

	// candidate string.

	if (!::MatchSectionFolded(candidate, searchTerm))

		return EFalse;

	// If there was only one section, it must match the whole candidate string.

	if (searchTerm.AtEnd())

		return candidate.AtEnd();

	while (!searchTerm.AtEnd())

		{

		searchTerm.Next();

		if (!::FindMatchSectionFolded(candidate, searchTerm))

			return EFalse;

		}

	// The last section must match exactly at the end of the candidate string.

	if (candidate.AtEnd())	// shortcut

		return ETrue;

	const TText16* searchTermLastSection = aSearchTermEnd;

	while (searchTermLastSection != aSearchTermStart

		&& searchTermLastSection[-1] != '*')

		--searchTermLastSection;

	if (searchTermLastSection == aSearchTermEnd)

		// last section is null, so trivially matches

		return ETrue;

	// Count graphemes by counting the number of base characters.

	// The first one is assumed to start a grapheme.

	TInt graphemeCount = 1;

	for (const TText16* s = searchTermLastSection + 1; s != aSearchTermEnd; ++s)

		{

        if (::IsBaseCharacter(*s))

			++graphemeCount;

		}

	// Count this many graphemes back in the candidate string

	const TText16* candidateLastSection = aCandidateStringEnd;

	while (graphemeCount != 0

		&& candidateLastSection != aCandidateStringStart)

		{

        if (::IsBaseCharacter(*--candidateLastSection))

			--graphemeCount;

		}

	TUTF32Iterator last(candidateLastSection, aCandidateStringEnd);

	TUTF32Iterator st(searchTermLastSection, aSearchTermEnd);

	return ::MatchSectionFolded(last, st);

	}

/** 

Implementation of MatchF

(slow if there is a match: MatchStringFolded is better, but does not return

the position of the match)

@internalComponent

*/

TInt LocateMatchStringFolded(const TText16* aCandidateStringStart, const TText16* aCandidateStringEnd,

                             const TText16* aSearchTermStart, const TText16* aSearchTermEnd)

	{

	// Quick shortcut for simple non-match

	if (aSearchTermStart != aSearchTermEnd && *aSearchTermStart != '*')

		{

		if (aCandidateStringStart == aCandidateStringEnd)

			return KErrNotFound;

		// We won't bother with non-characters and surrogate pairs.

		if (*aSearchTermStart != '?'

			&& *aSearchTermStart < 0xD800

			&& *aCandidateStringStart < 0xD800

            && ::GetFirstFoldedChar(*aSearchTermStart) != ::GetFirstFoldedChar(*aCandidateStringStart))

			return KErrNotFound;

		}

    if (!::MatchStringFolded(aCandidateStringStart, aCandidateStringEnd,

		aSearchTermStart, aSearchTermEnd))

		return KErrNotFound;

	// find where it matches

	while (aSearchTermStart != aSearchTermEnd && *aSearchTermStart == '*')

		++aSearchTermStart;

	const TText16* end = aSearchTermStart;

	while (end != aSearchTermEnd && *end != '*')

		++end;

	// To preserve existing behaviour, a search term consisting of nothing

	// but stars is considered to match at 0.

	if (end == aSearchTermStart)

		return 0;

	for (const TText16* csSection = aCandidateStringStart;

		csSection <= aCandidateStringEnd; ++csSection)

		{

		TUTF32Iterator cs(csSection, aCandidateStringEnd);

		TUTF32Iterator st(aSearchTermStart, end);

        if (::MatchSectionFolded(cs, st))

			{

			// If this match must match exactly at the end, we must keep

			// going.

			// This could be a lot faster, with some optimizations.

			if (end == aSearchTermEnd)

				{

				if (!cs.AtEnd())

					continue;

				}

			return csSection - aCandidateStringStart;

			}

        // Because this function is using TUTF32Iterator, which means the

        // original author want to support surrogate. Take it as a defect and

        // fix it, while do not define a new LocateMatchStringFoldedSurrogate().

        if (IsSurrogate(*csSection))

        	++csSection;

		}

	// this should never happen!

	ASSERT(0);

	return KErrNotFound;

	}

/** 

Implementation of FindF

@internalComponent

*/

TInt FindFolded(TUTF32Iterator& aCandidateString, TUTF32Iterator& aSearchTerm)

	{

    //Empty aSearchTerm string? - Then return 0 - keep the new implementation functionally 

    //compatible with the old one.

    if(aSearchTerm.Length() == 0)

        {

        return 0;

        }

	const TText16* candidateStartPosition = aCandidateString.CurrentPosition();

    TChar firstCharOfSearchTerm = ::GetFirstFoldedChar(aSearchTerm.Current());

	TUTF32Iterator savedST(aSearchTerm);

	while (aCandidateString.LocateFoldedBaseCharacter(firstCharOfSearchTerm))

		{

		TUTF32Iterator savedCS = aCandidateString;

        TEndTester endTester(TEndTester::EGenuine);

        if (::ConsumeFoldedMatchWholeGraphemes(aCandidateString, aSearchTerm, endTester))

			return savedCS.CurrentPosition() - candidateStartPosition;

		aSearchTerm = savedST;

		aCandidateString = savedCS;

		aCandidateString.Next();

		}

	return KErrNotFound;

	}

/** 

Implementation of boolean CompareF

@internalComponent

*/

TBool EqualsFolded(TUTF32Iterator& aLeft, TUTF32Iterator& aRight)

	{

    TEndTester endTester(TEndTester::EGenuine);

    if (::ConsumeFoldedMatchWholeGraphemes(aLeft, aRight, endTester))

		return aLeft.AtEnd();

	return EFalse;

	}

/** 

Implementation of tri-state CompareF

@internalComponent

*/

TInt CompareFolded(const TUTF32Iterator& aLeft, const TUTF32Iterator& aRight)

	{

	TFoldedCanonicalIterator left(aLeft);

	TFoldedCanonicalIterator right(aRight);

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

	while (!left.AtEnd())

		{

		if (right.AtEnd())

			return 1;

		TChar cr = right.Current();

		TChar cl = left.Current();

		if (cr != cl)

			return cl - cr;

        right.Next(charDataSet);

        left.Next(charDataSet);

		}

	return right.AtEnd()? 0 : -1;

	}

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

// Composition/Decomposition - Global functions and structures

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

/** 

@internalComponent

*/

static TUTF32Iterator IndexToNonSingletonDecomposition(TInt aIndex)

	{

	const TText* start = KNonSingletonDecompositions + 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);

	}

/** 

Come up with a decomposition for the current value pointed at by the iterator

@internalComponent

*/

static TBool Decompose(const TUTF32Iterator& aUTF32It, TUTF32Iterator& aOutIt)

	{

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

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

	const TInt SizeOfSingletonTable = sizeof(KSingletonDecompositions)/sizeof(KSingletonDecompositions[0]);

	if(index < 0 || SizeOfSingletonTable <= singletonIndex)

        {

        aOutIt = aUTF32It.CurrentAsIterator();

		return EFalse;//There is not any valid decomposition

        }

	if(0 <= singletonIndex)

        {

        // KSingletonDecompositions contains some items that come from "ShortDecompsLongFolds".

        // "ShortDecompsLongFolds" contains some characters that have no composition, but have "long fold".

        // This basically specific to non-BMP characters with fold also outside BMP.

        // For example:

        // 10400;DESERET CAPITAL LETTER LONG I;Lu;0;L;;;;;N;;;;10428;

        // In Unicode 5.0.0, totally, there are 40 similar characters, which are U+10400-U+10427.

        if (KSingletonDecompositions[singletonIndex] == 0xFFFF)

        	return EFalse;

		aOutIt = TUTF32Iterator(KSingletonDecompositions + singletonIndex);

        }

    else

        {

        aOutIt = ::IndexToNonSingletonDecomposition(index);

        }

    return ETrue;//Valid decomposition

	}

/** 

@internalComponent

*/

static TUTF32Iterator CharToUTF32Iterator(TChar aChar, TDes16& aBuf)

	{

	aBuf.Zero();

	if (aChar < 0x10000)

		aBuf.Append(aChar);

	else

		{

		aBuf.Append((aChar >> 10) + 0xD7C0);

		aBuf.Append((aChar & 0x3FF) + 0xDC00);

		}

	const TText16* t = aBuf.Ptr();

	return TUTF32Iterator(t, t + aBuf.Length());

	}

/** 

@internalComponent

*/

TBool DecomposeChar(TChar aCh, TPtrC16& aResult)

    {

    aResult.Set(NULL, 0);

    TBuf16<2> srcBuf;

    TUTF32Iterator it = ::CharToUTF32Iterator(aCh, srcBuf);

    TBool res = ::Decompose(it, it);

    if(res)

        {

        aResult.Set(it.CurrentPosition(), it.Length());

        }

    return res;

    }

/** 

Turn an index into the hash table known to point to a non-singleton

decomposition into that decomposition.

@internalComponent

*/

static TUTF32Iterator HashIndexToDecomposition(TInt aIndex)

	{

	TUint32 v = KUnicodeToIndexHash[aIndex];

	ASSERT(v != 0);

	TInt index = static_cast<TInt>(v >> 20);

	ASSERT(index < ARRAY_LENGTH(KNonSingletonDecompositions)/2);

    return ::IndexToNonSingletonDecomposition(index);

	}

/**

Takes a start and (one past the) end index into KCompostionMapping

and a number of UTF16 characters (aLengthSoFar). All of the compositions

within the range must have their first aLengthSoFar UTF16 characters

matching.

On entry, if aStart == aEnd then there is no possibility of a match so return

immediately with EFalse. To continue, aStart must be strictly less than aEnd.