/***************************************************************************
 *                                                                         *
 *   STEPFIND.H                                                            *
 *                                                                         *
 *   Copyright (c) 1998 Galacticomm, Inc.         All rights reserved.     *
 *                                                                         *
 *   Incremental sequence searching algorithms.                            *
 *                                                                         *
 *   These algorithms are derived from the standard C++ algorithms, and    *
 *   is loosely based on the source provided with Borland C++ 5.0.  The    *
 *   Borland source is itself derived from the Hewlett-Packard             *
 *   implementation of STL.                                                *
 *                                                                         *
 *                                           - J. Alvrus    06/17/1998     *
 *                                                                         *
 ***************************************************************************/

#ifndef __STEPFIND_H
#define __STEPFIND_H

//
// __step_find - Internal implementation of step_find, updates step
//
template <class InputIterator, class T, class Distance>
bool                               //   returns true when found
__step_find(                       // internal incremental find algorithm
InputIterator & first,             //   start of sequence (updated)
InputIterator last,                //   end of sequence
T const & target,                  //   value to find
Distance & step)                   //   max sequence items to test (updated)
{
     while (first != last && step > 0) {
          --step;
          if (*first == target) {
               return(true);
          }
          ++first;
     }
     return(false);
}

//
// step_find - Find a value within a sequence, searching a piece at a time.
//
// The function returns true when the value is found.  The start-of-
// sequence iterator is updated each time the function is called, and
// points to the desired value in the sequence when true is returned.
// The function will return false when maximum-items have been
// evaluated, and the start-of-sequence iterator will be equal to
// start-of-sequence plus maximum-items.  The function will return false
// when the end of the sequence is reached, and the start-of-sequence
// iterator will be equal to the end-of-sequence iterator.
//
template <class InputIterator, class T, class Distance>
bool                               //   returns true when found
step_find(                         // incremental find algorithm
InputIterator & first,             //   start of sequence (updated)
InputIterator last,                //   end of sequence
T const & target,                  //   value to find
Distance const & step)             //   maximum sequence items to test
{
     Distance n=step;
     return(__step_find(first,last,target,n));
}

//
// step_find_first_of - Find the first occurrence of a set of values in a
//                      sequence, searching a piece at a time.
//
// This function returns true when one of the items in the value set is
// found in the searched sequence.  The start-of-sequence iterator is
// updated each time the function is called.  When true is returned, the
// start-of-sequence iterator points to the first value set element
// found in the searched sequence.  The function will return false when
// maximum-items have been evaluated, and the start-of-sequence iterator
// will be equal to start-of-sequence plus maximum-items.  The function
// will return false when the end of the searched sequence is reached,
// and the start-of-sequence iterator will be equal to the
// end-of-sequence iterator.
//
template <class ForwardIteratorSearch, class ForwardIteratorSet, class Distance>
bool
step_find_first_of(                // find first occurrence of one of a set
ForwardIteratorSearch & SearchStart, // start of searched sequence (updated)
ForwardIteratorSearch SearchEnd,   //   end of searched sequence
ForwardIteratorSet SetStart,       //   start of value set sequence
ForwardIteratorSet SetEnd,         //   end of value set sequence
Distance const & step)             //   max number of sequence items to test
{
     Distance n=0;
     while (SearchStart != SearchEnd && n++ < step) {
          if (find(SetStart,SetEnd,*SearchStart) != SetEnd) {
               return(true);
          }
          ++SearchStart;
     }
     return(false);
}

//
// step_search - Find a sequence as a sub-sequence of another sequence,
//               searching a piece at a time.
//
// This function returns true when the sub-sequence is found in the
// searched sequence.  The start-of-sequence iterator is updated each
// time the function is called.  When true is returned, the
// start-of-sequence iterator points to the first target-sequence
// element found in the searched sequence.  The function will return
// false when maximum-items have been evaluated, and the
// start-of-sequence iterator will be equal to start-of-sequence plus
// maximum-items.  The function will return false when the end of the
// searched sequence is reached, and the start-of-sequence iterator will
// be equal to the end-of-sequence iterator.
//
template <class ForwardIteratorSearch, class ForwardIteratorTarget, class Distance>
bool                               //   returns true when found
step_search(                       // incremental search algorithm
ForwardIteratorSearch & SearchStart, // start of searched sequence (updated)
ForwardIteratorSearch SearchEnd,   //   end of searched sequence
ForwardIteratorTarget TargetStart, //   start of target sequence
ForwardIteratorTarget TargetEnd,   //   end of target sequence
Distance const & step)             //   max number of sequence items to test
{
     // try to find the first character of the target sequence
     Distance StepsLeft=step;
     while (__step_find(SearchStart,SearchEnd,*TargetStart,StepsLeft)
         && SearchStart != SearchEnd) {

          // found first character, now try rest of sequence
          ForwardIteratorSearch tmpSearch=SearchStart;
          ForwardIteratorTarget tmpTarget=TargetStart;
          do {
               ++tmpSearch;
               ++tmpTarget;
               if (tmpTarget == TargetEnd) {
                    return(true);
               }
          } while (tmpSearch != SearchEnd && *tmpSearch == *tmpTarget);
          ++SearchStart;
     }
     return(false);
}

#endif // __STEPFIND_H