#include "patternminsearcher.hh"


using namespace Gecode;


uint64_t pointless_finds = 0;
uint64_t bytes_searched = 0;


PatternMinSearcher::PatternMinSearcher (std::list<unsigned char> pattern) :
  pattern (pattern)
{
}


MinSearcherResult PatternMinSearcher::find_minimum (Space& home, DataSource& ds, int64_t& lower, int64_t upper, int64_t& maxEnd) 
{
  invalidate_dsread_cache ();

  int64_t original_lower = lower;

  int pattern_size = pattern.size ();

  bool search_complete = false;
  IntVar unavailable = ds.unavailable ();
  while (!search_complete && lower <= upper && lower + pattern_size - 1 <= maxEnd) {
    if (lower % BLOCK_SIZE == 0) {
      if (unavailable.in (lower / BLOCK_SIZE)) { 
        return PATTERN_RESULT_INDETERMINATE; 
      }
    }
    bool test_failed = false;

    int i = 0;
    for (std::list<unsigned char>::const_iterator it = pattern.begin (); !test_failed && it != pattern.end (); ++it, i++) {
      int64_t offset = lower + i;
      if (i != 0 && offset % BLOCK_SIZE == 0) {
        if (unavailable.in (offset / BLOCK_SIZE)) { 
          return PATTERN_RESULT_INDETERMINATE; 
        }
      }
      unsigned char ch = dsread (ds, offset); 
      if (ch != *it) {
        test_failed = true;
      }
      bytes_searched++;
    }

    if (test_failed) {
      lower++;
    } else {
      maxEnd = lower + pattern_size - 1;
      search_complete = true;
    }
  }
  if (search_complete) {
    if (original_lower == lower) {
      pointless_finds++;
    }
    return PATTERN_RESULT_FOUND;
  } else {
    return PATTERN_RESULT_FAILED;
  }
}


