#ifndef CS235_ALGORITHM_H
#define CS235_ALGORITHM_H

/*
LIBRARY
    Samples

THE LIBRARY SECTION
    For each <i>library</i> (collection of header files) you are
    allowed to define one <i>LIBRARY</i> section in one of the
    header files. Use this section to discuss the classes,
    datatypes, and algorithms in the entire library.  This documentation
    will appear on the root page to the html files for the library.

    You can only define one LIBRARY section and the library name
    must match the libary name used in the config file or on the
    command line.
    
DESCRIPTION
    Simple algorithms, all of which can be found in the STL.  The first
    letter of each function, struct/class name has been capatalized to
    prevent naming conflicts with the STL functions.

NAMING CONVENTIONS
    In template classes the following abbreviations are used.

    <li>I - iterator type, or something that can behave like an iterator.
    <li>T - value type, this is what you get when you dereference
            the iterator.
    <li>F - function type, a function object a pointer to a function.
    <li>P - predicate type, a function object or a pointer to a function
            that takes two parameters of type T and returns a bool.
	    See functional.h

    If a template function or class requires more that one iterator, value,
    or function type the digits are appended. i.e.

        template<class I1, class I2> void Copy(I1 start, I1 end, I2 dest);

    Here 'start', and 'end' and of iterator type "I1" and 'dest' is of
    iterator type "I2". I1 and I2 may, or may not, be the same types of
    iterators.
*/

#include "functional.h"

/** Copies the objects pointed to by the iterators to dest.
    Objects in the range [start,end) are copied.

    Parameters
    [in]    start   Position to start copying from
    [in]    end     First element not to include in copying
    [in]    dest    Position to copy to 
*/ 
template <class I1, class I2> void Copy(I1 start, I1 end, I2 dest)
{
    while (start != end)
        *dest++ = *start++;
}

/** This is a simple implementation of the STL find function

    Returns
        <li> <b><i>end</i></b> if the item is not found in the list
        <li> else an iterator of type I that can be used to reference the
             desired item.
        
    Parameters
    [in]    start   Position to start searching from
    [in]    end     First element not included in the search
    [in]    value   The value we are searching for
*/
template <class I, class T> I Find(I start, I end, T value)
{
    while (start != end)
    {
        if (*start == value)
            return start;
        ++start;
    }
    return start;
}

/** A predicate version of the STL find

    The parameter class P is a predicate that is expected to take to
    parameters of type T and return a <i>bool</i>.

    Parameters
    [in]    start   Position to start searching from
    [in]    end     First element not included in the search
    [in]    value   The value we are searching for
    [in]    fn      The predicate fuction to be applied to determine if
                    an element has been "found"
*/
template <class I, class T, class P> I Find(I start, I end, T value, P fn)
{
    while (start != end)
    {
        if ( fn(*start, value))
            return start;
        ++start;
    }
    return start;
}

/** STL accumulate function.  Calculates the sum of all the values in the
    sequence [start,end). Assumes that operator+ has been defined
    for the type T.

    Parameters
    [in]    start   First element in the sequence to include in the sum.
    [in]    end     The first element not included in the sum such
                    that *(end-1) is included in the sum.
    [in] value      Used to pass in the initial value (in case we
                    don't want to start at 0)
*/
template <class I, class T> T Accumulate(I start, I end, T value)
{
    while (start != end)
        value = value + *start++;
    return value;
}

/*
CLASS
    Add

KEYWORDS
    BinaryFunction
 
DESCRIPTION
    The Add class inherits from the BinaryFunction class and overloads
    the function call operator. Assumes that objects of type T have
    <i>operator+</i> overloaded.
*/
template <class T> struct Add : public BinaryFunction<T,T,T>
{
      /** The overloaded function operator.  Adds the two values
	  and returns the result.

	  Parameters
	  [in]     x     Constant references to the values to be added
	  [in]     y     
      */
      T operator()(const T& x, const T& y) const  { return x + y; }
};

/*
CLASS
   Multiply

KEYWORDS
   BinaryFunction

DESCRIPTION
    The Multiply class inherits from BinaryFunction and provides an
    overloaded function call operator that calculates the product of
    two objects.  Assumes that the objects of type T have
    <i>operator*</i> defined.
*/
template <class T> struct Multiply : public BinaryFunction<T,T,T>
{
      /** Calculate the product of x and y and return the result.
	  Parameters
	  [in]     x     Constant references to the values to be multiplied
	  [in]     y
      */
      T operator()(const T& x, const T& y) const  { return x * y; }
};

/** A more general version of the accumulate function.  The function
    applies the predicate <i>fn</i> to the values in the range [start,end)
    and accumlates the result.  That is it calculates:
    <pre>
        init = fn(init, *i)
    </pre>
    
    for all i in the range [start,end).  For example,
    <pre>
        Multiply<int> multiplyer;
	int a[] = {1,2,3,4,5,6};
	int product = 1;     // identity value for multiplication
	Accumulate(a, a+7, product, multiplier);
	assert(product == 720);
    </pre>

    Parameters
    [in]      start       First value to be included in the accumulation
    [in]      end         First value <b>not</b> included in the accumulation
    [in]      init        Initial value
    [in]      fn          Function to be applied while accumulating
*/
template <class I, class T, class F> T Accumulate(I start, const I end, T init, F fn)
{
    while (start != end)
        init = fn(init, *start++);
    return init;
}

/*
CLASS
    Outputer

DESCRIPTION
    A function object used to print objects of type T to cout.

    The class provides a parameterized constructor that accepts
    a single character.  This character will be used as the delimiting
    character between the objects of type T.  That is for each
    output operation the class essentially performs:
    EXAMPLE
        cout << T << delimiter;
    END
    If the delimiting character is not defined the output is not
    delimited.

    The Outputer class is useful printing sequences of things. For
    example given a 10 element array of interger and an STL list of
    strings we could do the following:

    EXAMPLE
        extern int ints[];
        extern list<string> strings;
        Outputer<int> print_with_spaces(' ');
	Outputer<string> print_one_per_line('\n');

	ForEach(ints, ints+10, print_with_spaces);
	ForEach(strings.begin(), strings.end(), print_one_per_line);
    END
    
    <pre>
    Author  :   Keith Suderman
    Date    :   01/20/2001
    </pre>
*/
template <class T> struct Outputer
{
   protected:
      /** Character to print after each output operation. If
	  fDelimiter is the NULL character then the delimiter
	  is not printed.
       */
    char fDelimiter;
public:
    /** Default constructor set fDelimiter to 0. Output will
        not be delimited.
    */
    Outputer() : fDelimiter(0)  { }

   /** Copy constructor.  Makes a copy of the delimiting character. 
   */
   Outputer(const Outputer& o) : fDelimiter(o.fDelimiter) { }
    

    /** Parameterized constructor.  Set the delimiting character when
        the Ouputer is constructed.

        Parameters
        [in]     ch    Character to be printed after each ouput operation.
    */
    Outputer(char ch) : fDelimiter(ch) { }


    /** Overload of the function call operator. If the delimiter has been
	defined then the operator performs
	<pre>
	    cout << value << fDelimiter;
	</pre>
	otherwise it performs
	<pre>
	    cout << value;
	</pre>
	
        Parameters
        [in]    value : the value to be printed to cout.
    */
    void operator()(T value)
    {
        cout << value;
        if (fDelimiter != 0)
            cout << fDelimiter;
    }
};

/** Applies the function fn(*i) to each <b>i</b> in the range
    [start, end). The parameter <i>fn</i> should be a function
    object or a pointer to a function.

    Parameters
    [in]     start       First value fn() will be applied to
    [in]     end         First value fn() will <b>not</b> be applied to
    [in]     fn          The function to be applied
*/
template <class I, class F> void ForEach(I start, I end, F fn)
{
    while (start != end)
        fn(*start++);
}

/** Takes two references are parameters and swaps their values.
*/
template <class T> void Swap(T& X, T& Y)
{
    T temp = X;
    X = Y;
    Y = temp;
}

/** Bubble sorts the values in the range [start, end).  Sorts with
    <b>operator < </b>.
*/
template <class I> void Sort(I start, I end)
{
    while (start != end)
    {
        I i = start;
        I j = i + 1;
        while (j != end)
        {
            if (*i < *j)
                Swap(*i, *j);
            ++i;
            j = i + 1;
        }
        --end;
    }
}

/** Predicate version of BubbleSort.  Uses the Predicate function
    <b>fn</b> to compare values. For example, given an STL
    vector of integers:

    <pre>
        extern vector<int> ints;
	Outputer
	Sort(ints.begin(), ints.end(), Greater<int>());
	ForEach(ints.begin(), ints.end(), Outputer<int>(' '));

	Sort(int.begin(), ints.end(), Less<int>());
	ForEach(ints.begin(), ints.end(), Outputer<int>
    </pre>
 */
template <class I, class P> void Sort(I start, I end, P fn)
{
    while (start != end)
    {
        I i = start;
        I j = i + 1;
        while (j != end)
        {
            if ( fn(*i,*j) )
                Swap(*i, *j);
            ++i;
            j = i + 1;
        }
        --end;
    }
}

#endif