#ifndef _INCLUDE_STOPTIFU_SMAP_H_
#define _INCLUDE_STOPTIFU_SMAP_H_

// This file should be included from AC.h.

class rwmap_element;
class smap_element;

template <class T, class U> static inline bool must_be_same_array(T x, U y);
template <class T, class U> static inline bool might_be_same_array(T x, U y);

/* A smap_element represents one of three things in a loop:
   1. A write to an array element, a[R(p)] = e, where
      at the end of the iteration the value of a[R(p)] is still
      what it was just after the write.
   2a. A read from an array element, x = a[R(p)], where
       the value of a[R(p)] at the start of the iteration is
       the same as the value that will be read.
   2b. A read from an array element, x = a[R(p)], where
       at the end of the iteration the value of a[R(p)] is still
       what it was just after the read.
   (2a and 2b may both hold, or one may, or neither may.)
   Each smap_element is executed on every iteration of the loop.
   In all cases, |R(p)| must be one for all values of p.
*/
class smap_element {
 public:
  smap_element(int access, bool case2a, bool case2b, int array,
	       Relation R) :
    access(access), case2a(case2a), case2b(case2b), array(array), R(R) {}

  /* Arbitrary way to keep track of which array access is which. */
  int access;
  /* Which case? */
  bool case2a, case2b;
  inline bool is_read() const { return case2a || case2b; }
  inline bool is_write() const { return !is_read(); }
  /* Arbitrary way to keep track of which array is which. */
  /* A value of 0 means "I don't know." */
  int array;
  /* Maps iteration space point to array indices. */
  Relation R;

  inline bool must_be_same_array(const smap_element *x) const {
    return ::must_be_same_array(this, x);
  }
  inline bool might_be_same_array(const smap_element *x) const {
    return ::might_be_same_array(this, x);
  }
  inline bool must_be_same_array(const rwmap_element *x) const {
    return ::must_be_same_array(this, x);
  }
  inline bool might_be_same_array(const rwmap_element *x) const {
    return ::might_be_same_array(this, x);
  }

  inline string to_string() const {
    return string("<") + (is_read() ? 'r' : 'w') + ' ' +
      i2s(access) + ", V=" + i2s(array) + ", " +
      ((array == 0) ? string("unknown") : relation_to_str((Relation) R)) + ">";
  }
};

class Foreach;

typedef map<Foreach *, llist<smap_element *> *> smap;

/* A rwmap_element can represent any reads or writes to an array in a loop. */
class rwmap_element {
 public:
  rwmap_element(int access, int array, bool is_read, Relation R,
		bool every_iter = false) :
    access(access), array(array), R(R), every_iter(every_iter),
    _is_read(is_read) {}

  /* Arbitrary way to keep track of which array access is which. */
  int access;
  /* Arbitrary way to keep track of which array is which. */
  /* A value of 0 means "I don't know." */
  int array;
  /* Maps iteration space point to array indices that may be used. */
  /* If array is 0 then R is meaningless. */
  Relation R;
  bool every_iter;

 private:
  bool _is_read;
 public:
  inline bool is_read() const { return _is_read; }
  inline bool is_write() const { return !_is_read; }

  inline bool must_be_same_array(const smap_element *x) const {
    return ::must_be_same_array(this, x);
  }
  inline bool might_be_same_array(const smap_element *x) const {
    return ::might_be_same_array(this, x);
  }
  inline bool must_be_same_array(const rwmap_element *x) const {
    return ::must_be_same_array(this, x);
  }
  inline bool might_be_same_array(const rwmap_element *x) const {
    return ::might_be_same_array(this, x);
  }

  inline string to_string() const {
    return string("<") + (is_read() ? 'r' : 'w') + ' ' +
      i2s(access) + ", V=" + i2s(array) + ", " +
      relation_to_str((Relation) R) + ">";
  }
};

typedef map<Foreach *, llist<rwmap_element *> *> rwmap;

template <class T, class U> static inline bool must_be_same_array(T x, U y) {
  return y->array != 0 && y->array == x->array;
}
template <class T, class U> static inline bool might_be_same_array(T x, U y) {
  return y->array == 0 || x->array == 0 || y->array == x->array;
}

/* In a megatile the same rwmap_element can be execute by different steps.
   Hence, a "touch" indicates the step number along with the rwmap_element. */
typedef pair<int, rwmap_element *> touch;

static inline bool touch_is_read(const touch &t) {
  return t.second->is_read();
}
static inline bool touch_is_write(const touch &t) {
  return t.second->is_write();
}

/* From storage.cc */
extern Relation
relation_from_tilespace_to_arrayindex(Relation x, const Foreach *f,
				      const intvector *v);

typedef pair<int, smap_element *> smap_at_k;

#endif