/*    deadzones: A program for identifying genomic deadzones
 *    Copyright (C) 2009 University of Southern California and
 *                       Andrew D. Smith
 *
 *    Authors: Andrew D. Smith
 *
 *    This program is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program.  If not, see .
 */

#include "smithlab_utils.hpp"
#include "GenomicRegion.hpp"
#include "OptionParser.hpp"

#include 
#include 

#if defined(_OPENMP)
  #include 
#else
  #include 
#endif

#include 
using std::tr1::unordered_map;

using std::string;
using std::vector;
using std::cout;
using std::endl;
using std::cerr;

class IndexLess {
public:
  IndexLess(const size_t k, const string &s) :
    kmer(k), itr(s.begin()) {}
  bool operator()(size_t a, size_t b) const {
    const string::const_iterator lim(itr + a + kmer);
    string::const_iterator a_itr(itr + a), b_itr(itr + b);
    while (a_itr < lim && *(a_itr) == *(b_itr)) {
      ++a_itr; ++b_itr;
    }
    return (*a_itr < *b_itr && a_itr < lim);
  }
private:
  size_t kmer;
  const string::const_iterator itr;
};

template  bool
lexico_equal(In first, In last, In first2) {
  while (first != last)
    if (*first++ != *first2++) return false;
  return true;
}

static void
sort_index(const bool VERBOSE, const size_t kmer, const string &prefix,
           const string &seq, vector &ambigs,
           const unordered_map &invalid_pool) {

  if (VERBOSE) cerr