#ifndef _BOUNDINGBOX_H_
#define _BOUNDINGBOX_H_

#include "BoxIter.h"

class BoundingBox {
 public:
  BoundingBox() : lo(NULL), hi(NULL) {}
  BoundingBox(intvector *x) : lo(NULL), hi(NULL) { insert(x); }
  BoundingBox(intvector *x, intvector *y) : lo(NULL), hi(NULL) {
    insert(x);
    insert(y);
  }

  void insert(intvector *x) {
    if (lo == NULL) {
      assert(hi == NULL);
      lo = x->copy();
      hi = x->copy();
      n = x->size();
    } else {
      assert(n == x->size() &&
	     "Inserting vector of wrong size in BoundingBox");
      for (int i = (int) n; --i >= 0; ) {
	(*lo)[i] = std::min((*lo)[i], (*x)[i]);
	(*hi)[i] = std::max((*hi)[i], (*x)[i]);
      }
    }
    /*
    cout << "Inserted " << x->to_string() << "; box is " << lo->to_string() <<
      " up to " << hi->to_string() << endl;
    */
  }

  inline intvector *& lwb() { return lo; }
  inline intvector *& upb() { return hi; }

  /* In the i'th dimension, how many different values can the coordinate be? */
  inline int girth(int i) const {
    return (*hi)[i] - (*lo)[i] + 1;
  }

  int volume() const {
    if (lo == NULL || hi == NULL)
      return 0;
    int result = girth(0);
    for (int i = (int) n; --i >= 1; )
      result *= girth(i);
    return result;
  }

  /* Cut this roughly in half, into two boxes, that together cover the
     same space as this did upon entry.  Set this to one of them, and
     return the other.  If this has volume 0 or 1 then return NULL and
     do not modify this. */
  BoundingBox *calve() {
    if (volume() < 2)
      return NULL;
    int max, max_index, i;
    for (max = girth(0), max_index = 0, i = (int) n; --i >= 1; )
      if (girth(i) > max) 
	max = girth(max_index = i);
    assert(max >= 2);
    int split = (*lo)[max_index] + max / 2;
    BoundingBox *result = new BoundingBox(lo, hi);
    (*hi)[max_index] = split - 1;
    (*result->lwb())[max_index] = split;
    return result;
  }

  BoxIter start() const { return BoxIter(lo, hi); }

  string to_string() const {
    return string("{") + lo->to_string() + " to " + hi->to_string() + "}";
  }

 private:
  intvector *lo, *hi;
  size_t n;
};

#endif // _BOUNDINGBOX_H_