/* This is our implementation of complete traversals by means of two
 * generic functions, namely:
 *
 *     o complete_unique_traversal
 *     o complete_multiple_traversal
 *
 * The first one takes a unique sorted associative container (SAC)
 * (i.e. a set or a map), and an object function. The second one takes a
 * multiple SAC (i.e. a multiset or a multimap), and an object function.
 * Both generic functions iterate on their SAC argument applying
 * the function, in such a way that elements which are possibly
 * inserted by it are also treated.
 * In both cases the object function (to be provided by the user), must have
 * its operator () defined in such a way that it takes a value_type
 * argument (defined below) and a SAC. Additionally, the object function
 * must mantain a public data member, named Q, which is an STL queue
 * for keeping those elements to be inserted into the SAC which are
 * generated by each object function evaluation. The function should
 * therefore not insert the elements into the SAC.
 *
 * Details can be found in:
 *
 * E. Gamess, D. R. Musser, A. J. Sanchez-Ruiz. "Complete Traversals
 * and their Implementation Using the Standard Template Library". Available
 * from http://anubis.ciens.ucv.ve/~asanchez/autoolab.html.
 *
 *
 *            By:   Eric Gamess (*, %), 
 *                  David Musser(+), 
 *                  and Arturo J. Sanchez-Ruiz (*)
 *
 *              (*)Automatic Tools Construction Lab (AuTooLab)
 *                 Software Engineering and Systems Center (ISYS)
 *                 Faculty of Science -- Central University of Venezuela (UCV)
 *                 http://anubis.ciens.ucv.ve/~asanchez/autoolab.html
 *
 *              (%)Computer Science Department
 *                 Universidad del Valle
 *                 Cali, Colombia
 *
 *              (+)Computer Science Department
 *                 Rensselaer Polytechnic Institute
 *                 http://www.cs.rpi.edu/~musser
 *
 *                              (May, 1999)
 */

#ifndef COMPLETE_TRAVERSAL_H
#define COMPLETE_TRAVERSAL_H

template <class UniqueSortedAssociativeContainer, class Function>
void complete_unique_traversal(UniqueSortedAssociativeContainer& container, 
                               Function f) 
{
  typename UniqueSortedAssociativeContainer::value_type v;
  typename UniqueSortedAssociativeContainer::iterator i;
  typedef typename UniqueSortedAssociativeContainer::iterator iterator;
  for (i = container.begin(); i != container.end(); ++i) {
    f(*i, container);
    while (!f.Q.empty()) {
      v = f.Q.front();
      f.Q.pop();
      pair<iterator, bool> p = container.insert(v);
      // Check whether we need to process v now with f
      if (p.second && container.value_comp()(v, *i))
        // v has been inserted in container (it wasn't already there)
        // and it occurs before the current traversal 
        // position, i, so process it now with f:
        f(v, container);
      // Otherwise, it was already present or it will be processed later
    }
  }
}

template <class MultipleSortedAssociativeContainer, class Function>
void complete_multiple_traversal(MultipleSortedAssociativeContainer& container, 
                                 Function f) 
{
  typename MultipleSortedAssociativeContainer::value_type v;
  typename MultipleSortedAssociativeContainer::iterator i, j, k;
  for (i = container.begin(); i != container.end(); ++i) {
    f(*i, container);
    while (!f.Q.empty()) {
      v = f.Q.front();
      f.Q.pop();
      j = container.insert(v);
      // If v's position, j, in container is before the current
      // traversal position, i, then process v now with f
      if (container.value_comp()(v, *i)) 
        f(v, container);
      else if (!container.value_comp()(*i, v)) {
        // *i and v are equivalent, so we must search forward from 
        // v's position, j, through all of the following equivalent 
        // elements, if any, looking for position i:
        for (k = ++j; k != container.end() && 
               !container.value_comp()(v, *k); ++k)
          if (k == i)  {        // v was inserted before position i,
            f(v, container);    // so we process v now with f
            break;
          }
      }
    }
  }
}

#endif