#ifndef CS235_ALGORITHM_H #define CS235_ALGORITHM_H /** LIBRARY Samples 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.
  • I - iterator type, or something that can behave like an iterator.
  • T - value type, this is what you get when you dereference the iterator.
  • F - function type, a function object a pointer to a function.
  • 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 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 void Copy(I1 start, I1 end, I2 dest) { while (start != end) *dest++ = *start++; } /** This is a simple implementation of the STL find function Returns
  • end if the item is not found in the list
  • 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 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 bool. 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 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 */ template T Accumulate(I start, I end, T value) { while (start != end) value = value + *start++; return value; } /** CLASS Add KEYWORDS BinaryFunction DESCRIPTION The object adds two objects of type T and returns their sum. Assumes T has operator+ overloaded. Parameters [in] x Constant references to the values to be added [in] y */ template struct Add : public BinaryFunction { T operator()(const T& x, const T& y) const { return x + y; } }; /** CLASS Multiply KEYWORDS BinaryFunction DESCRIPTION Mulitplies two objects of type T and returns their product. Assumes T has operator * overloaded. Parameters [in] x Constant references to the values to be multiplied [in] y */ template struct Multiply : public BinaryFunction { T operator()(const T& x, const T& y) const { return x * y; } }; /** Clone of the STL accumulate function. Applies the function fn to each value in the range [start, end). Parameters [in] start First value to be included in the accumulation [in] end First value not included in the accumulation [in] init Initial value [in] fn Function to be applied while accumulating */ template 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 to cout. 
        Author  :   Keith Suderman
    Date    :   01/20/2001
    */ template struct Outputer { protected: char fDelimiter; // Character to print after each output 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. [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) for each i in the range [start, end). Parameters [in] start First value fn() will be applied to [in] end First value fn() will not be applied to [in] fn The function to be applied */ template void ForEach(I start, I end, F fn) { while (start != end) fn(*start++); } /** Takes two references are parameters and swaps their values */ template void Swap(T& X, T& Y) { T temp = X; X = Y; Y = temp; } /** Bubble sorts the values in the range [start, end). Sorts with operator < */ template 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 fn to compare values. */ template 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