#ifndef _TILING_H___
#define _TILING_H___

#include "tbb/pipeline.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/tick_count.h"
#include <iomanip>
#include <cstdio>

static double wall_mseconds()
{
  struct timeval t;
  gettimeofday(&t, NULL);

  return (double) t.tv_sec*1000 + (double) t.tv_usec * 1E-3;
}

// next_row
// gap_min
// curr_pos
// gap_width to zero


#define FILL_GAP                                  \
  while (gap_width > 0) {		          \
    if (curr_pos == gap_.limit_pos_) {		  \
      break;                                      \
    }                                             \
    segment.first = (*iseq_ptr)[curr_pos];        \
    segment.second = curr_gap_min+segment.first;  \
    next_row.push_back(segment);                  \
                                                  \
    if (segment.second < gap_min)                 \
      gap_min = segment.second;                   \
                                                  \
    ++curr_pos;                                   \
                                                  \
    gap_width -= segment.first;                   \
  }                                               \
  if (gap_width != 0) {                           \
    curr_pos = 0;                                 \
    return (int *)(-1);                           \
  }


// output_filter
//   start pointer from input buffer in memory
//   argument: number of items
//   - start pointer get updated each time by the
//     number of items

// input_filter
//   current_row and related params
//   return value: number of items
//   - current row are updated each time
//

class SegmentFilter: public tbb::filter {
public:
  SegmentFilter(Gap& gap);
  ~SegmentFilter();
private:
  Gap& gap_;
  segment_vector_t curr_row;
  segment_vector_t next_row;
  uint curr_gap_min;
  uint curr_pos;
  int gap_width;
  uint gap_min;
  iseq_t *iseq_ptr;
  
  /*override*/ void *operator()(void *);
};

SegmentFilter::SegmentFilter(Gap& gap) : 
  filter(serial_in_order),
  gap_(gap),
  curr_pos(0xffffffff)
{
  iseq_ptr = gap.problem_def_.range_iseq;
}

SegmentFilter::~SegmentFilter() {
  curr_row.clear();
}
 
void *SegmentFilter::operator()(void*) {
  gap_width = 0;
  gap_min = 0xffffffff;

  if (curr_pos == 0)
    return NULL;

  if (curr_pos == gap_.limit_pos_) {
    curr_pos = 0;

    segment_vector_t::iterator it;
    uint width=0;
    uint height=(*curr_row.begin()).second;
    for(it=curr_row.begin(); it!=curr_row.end(); ++it) {
      if ((*it).second != height) {
	return (int *)(-1);
      }
      width += (*it).first;
    }

    if (width*height != gap_.problem_def_.value) {
      return (int *)(-1);
    }
    
    return (int *)(-2);
  }

  if (curr_row.size() == 0) {
    for(uint idx = gap_.start_pos_; idx<gap_.end_pos_; ++idx) {
      uint side = (*gap_.problem_def_.range_iseq)[idx];
      segment_t segment;
      segment.first = side;
      segment.second = side;
      curr_row.push_back(segment);
    }
    curr_gap_min = gap_.min_;
    curr_pos = gap_.end_pos_;

    return (int *) gap_.end_pos_;
  } else {
    segment_t segment;
    segment_vector_t::iterator it;
    for(it=curr_row.begin(); it!=curr_row.end(); ++it) {
      if((*it).second > curr_gap_min) {
	FILL_GAP;
	next_row.push_back(*it);
	if((*it).second < gap_min)
	  gap_min = (*it).second;
      } else { // height == gap_min
	gap_width += (*it).first;
      }
    } // for
    FILL_GAP;

    curr_row.swap(next_row);
    next_row.clear();
    curr_gap_min = gap_min;
    
    return (int *)curr_pos;
  }
}
    

class OutputBufferFilter: public tbb::filter {
public:
  OutputBufferFilter(const char *in_region_begin,
		     const char *in_region_end,
		     uint in_num_input,
		     uint width,
		     uint height);
  ~OutputBufferFilter();
private:
  const char *in_region_begin_;
  const char *in_region_end_;
  const char *in_region_cur_;
  uint in_num_input_;
  uint in_region_input_idx_;
  vector<char> *out;
  uint width_;
  uint height_;
  /*override*/ void *operator()(void*);
};

OutputBufferFilter::OutputBufferFilter(const char *in_region_begin,
				       const char *in_region_end,
				       uint in_num_input,
				       uint width,
				       uint height) :
  filter(serial_in_order),
  in_region_begin_(in_region_begin),
  in_region_end_(in_region_end),
  in_num_input_(in_num_input),
  in_region_cur_(in_region_begin),
  in_region_input_idx_(0),
  width_(width),
  height_(height)
{
  out = new vector<char>;

  char dimensions[128];
  sprintf(dimensions, "\n  dimensions: %d x %d\n ", height, width);
  uint len;
  for (len=0; dimensions[len]!='\0'; ++len)
    ;

  out->insert(out->begin(), dimensions, dimensions+len);
}

OutputBufferFilter::~OutputBufferFilter() {
}

void *OutputBufferFilter::operator()(void* n) {

  if ((long)(n) == (long)(-1)) {
    out->clear();
    // cout << "not a solution!; out size=" << out->size() << endl;
    return out;
  }

  if ((long)(n) == (long)(-2)) {
    out->push_back('\n');
    return out;
  }

  uint i=(long)(n);

  for (uint cnt=in_region_input_idx_; cnt<i; ++cnt) {

    if (in_region_cur_ >= in_region_end_)
      break;

    if(cnt == in_region_input_idx_) {
      out->push_back(' ');
      out->push_back('(');
    }

    while(*in_region_cur_ == '\n' ||
	  *in_region_cur_ == '\t' ||
	  *in_region_cur_ == ' ')
      ++in_region_cur_;
    while(*in_region_cur_ >= '0' &&
	  *in_region_cur_ <= '9') {
      out->push_back(*in_region_cur_++);
    }

    if (cnt == (i-1)) {
      out->push_back(')');
    } else {
      out->push_back(' ');
    }
  }

  in_region_input_idx_ = i;

  return NULL;
}

class OutputFilter: public tbb::filter {
public:
  OutputFilter(FILE *output_file);
  // ~OutputFilter();
private:
  FILE *output_file_;
  /*override*/ void *operator() (void *);
};

OutputFilter::OutputFilter(FILE *output_file) :
  filter(serial_in_order),
  output_file_(output_file)
{
}

//OutputFilter::~OutputFilter() {
//}

void *OutputFilter::operator()(void *item) {
  if (item != NULL) {
    vector<char> & out = *static_cast< vector<char>*>(item);

    if (out.size() == 0) {
      ;
    } else {
#if 0
      double start = 0;
      start = wall_mseconds();
#endif

      size_t n = fwrite(&out[0], 1, out.size(), output_file_);

#if 0
      double stop;
      double elapsed;
      stop = wall_mseconds();
      elapsed = stop - start;
      cout << "stop= " << setprecision(20) << stop << endl;
      cout << "elapsed time (microseconds)=" << elapsed << endl;
#endif

      fflush(output_file_);

      if( n!=out.size() ) {
	fprintf(stderr,"Can't write into file '%s' n=%d, size=%d\n", 
		"XXX", n, out.size());
	exit(1);
      }
    }
  }
  return NULL;
}

class Tiling {
  FILE *output_file_;
  segment_marker_t& output_;

public:

  int operator() (Gap gap) const {

    tbb::task_scheduler_init init_parallel;

    tbb::pipeline pipeline;

    SegmentFilter segment_filter(gap);
    pipeline.add_filter(segment_filter);

    uint width = gap.width_;
    uint height = gap.problem_def_.value / width;
    OutputBufferFilter output_buffer_filter(gap.problem_def_.in_region_begin,
					    gap.problem_def_.in_region_end,
					    gap.problem_def_.range_iseq->size(),
					    width, height);
    pipeline.add_filter(output_buffer_filter);

    OutputFilter output_filter(output_file_);
    pipeline.add_filter(output_filter);

    pipeline.run(init_parallel.default_num_threads()*4);

  } // function
  typedef Gap argument_type;

  Tiling(FILE *output_file, segment_marker_t& output) : 
    output_file_(output_file),
    output_(output) {}
};

#endif /* _TILING_H___ */