Algorithms for dealing with delimited strings

delimited_algos.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <utility>

using namespace std;

template <typename FwdIt1, typename FwdIt2, typename T>
std::pair<FwdIt1, FwdIt1> find_delimited(
    FwdIt1 first, FwdIt1 last,
    FwdIt2 s_first, FwdIt2 s_last, const T& delimiter)
{
  // is the pattern at the beginning?
  auto p = std::mismatch(s_first, s_last, first, last);
  if (p.first == s_last) {
    if (p.second == last || *p.second == delimiter) {
      return { first, p.second };
    }
  }

  // does the pattern occur between two delimiters?
  auto i = std::find(p.second, last, delimiter);
  while (i != last) {
    p = std::mismatch(s_first, s_last, std::next(i), last);
    if (p.first == s_last) {
      if (p.second == last || *p.second == delimiter) {
        return { i, p.second };
      }
    }
    i = std::find(p.second, last, delimiter);
  }

  // not found
  return { last, last };
}

template <typename FwdIt1, typename FwdIt2, typename T>
std::pair<FwdIt1, FwdIt1> bring_to_front_delimited(
    FwdIt1 front, FwdIt1 first, FwdIt1 last,
    FwdIt2 s_first, FwdIt2 s_last, const T& delimiter)
{
  // find the pattern
  auto p = find_delimited(first, last, s_first, s_last, delimiter);

  // do we have a delimiter at the front? if so, one rotate is sufficient
  bool b = front != last && *front == delimiter;

  // rotate it to the front
  auto r = std::rotate(front, p.first, p.second);

  // if it's preceded by a delimiter, rotate the delimiter to the end
  if (!b && front != last && *front == delimiter) {
    r = std::rotate(front, std::next(front),  r);
  }

  // return the point after it (possibly the next front) and where it came from
  // (the next first to start searching at)
  return { r, p.second };
}

int main(void)
{
  string s = "foo,alpha,bravo,charlie,foo,delta,,echo,foo,foo,foxtrot,golf,foo";
  string to_find = "foo";

  auto p = bring_to_front_delimited(s.begin(), s.begin(), s.end(),
                                    to_find.cbegin(), to_find.cend(), ',');
  while (p.second != s.end())
  {
    p = bring_to_front_delimited(p.first, p.second, s.end(),
                                 to_find.cbegin(), to_find.cend(), ',');
  }

  std::cout << s << std::endl;
}