#ifndef __OOP_ALGOS_HPP__
#define __OOP_ALGOS_HPP__

namespace cs427_527
{
  /**
   * Folds all values between the given delimiter in the given range
   * and outputs them through the given iterator.
   *
   * @param IIter an input iterator type
   * @param OIter an output iterator type
   * @param T the type of the delimiter
   * @param Op a type callable with U and the iterators' value type
   * @param U the type of the value to fold
   * @param start an iterator at the beginning of the range
   * @param end an iterator past the end of the range
   * @param out an output iteratoe
   * @param delimiter the delimiter
   * @param f the fold function
   * @param init the initial value for the fold function
   */
  template<typename IIter, typename OIter, typename T, typename Op, typename U>
  void split(IIter start, IIter end, OIter out, const T& delimiter, Op f, const U& init)
  {
    if (start == end)
      {
	return;
      }

    // initial value for fold
    auto curr = init;
    for (auto i = start; i != end; i++)
      {
	if (*i == delimiter)
	  {
	    // see a delimiter -- output previous value and start new one
	    *out = curr;
	    out++;
	    curr = init;
	  }
	else
	  {
	    // fold current value in
	    f(curr, *i);
	  }
      }
    // output last value
    *out = curr;
  }

  /**
   * Outputs all the indices in the given range where the given key is found.
   *
   * @param IIter a random-access input iterator type
   * @param OIter an output iterator type
   * @param T a type that supports equality comparison
   * @param start an iterator at the beginning of the range to search
   * @param end an iterator past the end of the range to search
   * @param out an output iterator
   * @param key the value to search for matches of
   */
  template<typename IIter, typename OIter, typename T>
  void find_indices(IIter start, IIter end, OIter out, const T& key)
  {
    for (auto i = start; i != end; i++)
      {
	if (*i == key)
	  {
	    // found a match -- output it (this is where we need random access)
	    *out = i - start;
	    out++;
	  }
      }
  }

}

#endif