SearchAlgorithms.h

Go to the documentation of this file.

#ifndef MMANN_SEARCH_ALGORITHMS_H
#define MMANN_SEARCH_ALGORITHMS_H


#include "CompareAlgorithms.h"

template <class Datatype>
Datatype* BSearch(Datatype* Key, Datatype* Base, int Size, ACompareNodesAlgorithm<Datatype, void>* Compare)
{
    if (Size == 0)
        return NULL;

    int Middle = Size/2;
    int CompareValue = Compare->Compare(Key, &Base[Middle], NULL);
    if (CompareValue == 0)
    {
        return &Base[Middle];
    }
    else if (CompareValue < 0)
    {
        return BSearch<Datatype>(Key, Base, Middle, Compare);
    }
    else if (CompareValue > 0)
    {
        Datatype* NewBase = &(Base[Middle+1]);
        return BSearch<Datatype>(Key, NewBase, (Size-1)/2, Compare);
    }

    return NULL;
}

template <class Datatype>
Datatype* FreecellSolverBSearch(Datatype* Key, Datatype* Array, int Length, 
                                ACompareNodesAlgorithm<Datatype, void>* Compare, bool* Found)
{
    int Low = 0,
        High = Length - 1,
        Mid,
        Result;

    while (Low <= High)
    {
        Mid = ((Low+High)>>1);
        Result = Compare->Compare(Key, &Array[Mid], NULL);

        if (Result < 0)
        {
            High = Mid-1;
        }
        else if (Result > 0)
        {
            Low = Mid+1;
        }
        else
        {
            *Found = true;
            return (&Array[Mid]);
        }
    }

    *Found = false;
    return (&Array[High+1]);
}

template <class Datatype>
void SFOMergeLargeAndSmallSortedArrays(Datatype* BigArray, int BigArraySize, 
                                       Datatype* SmallArray, int SmallArraySize,
                                       ACompareNodesAlgorithm<Datatype, void>* Compare)
{
    int NumberOfBigItemsMoved = 0,
        Position,
        StartOffset,
        EndOffset;
    Datatype* PositionPtr;
    bool Found;

    for (int ItemToMove = SmallArraySize-1 ; ItemToMove >= 0; ItemToMove--)
    {
        PositionPtr = FreecellSolverBSearch<Datatype>(&SmallArray[ItemToMove],
                                    BigArray, BigArraySize-NumberOfBigItemsMoved,
                                    Compare, &Found);

        Position = PositionPtr-BigArray;
        //This expression was simplified from the original
        EndOffset = BigArraySize - NumberOfBigItemsMoved + ItemToMove + 1;
        StartOffset = EndOffset + Position - (BigArraySize - NumberOfBigItemsMoved);

        memmove(&BigArray[StartOffset], &BigArray[Position], (EndOffset - StartOffset)*sizeof(Datatype));
        memcpy(&BigArray[StartOffset-1], &SmallArray[ItemToMove], sizeof(Datatype));
        NumberOfBigItemsMoved += (EndOffset - StartOffset);
    }
}

#endif

---