#include "AC.h"
#include "OrderingConstraint.h"

OrderingConstraint::OrderingConstraint(AC *from_, AC *to_, Kind k_)
{
  k = k_;
  if ((from = from_) != NULL) {
    fromseq = from->seq();
    fromseqindex = from->seqindex();
  }
  if ((to = to_) != NULL) {
    toseq = to->seq();
    toseqindex = to->seqindex();
  }
}

void print(llist<OrderingConstraint *> *l, ostream &os)
{
  while (l != NULL) {
    l->front()->print(os);
    l = l->tail();
  }
}

// Bug: prints statements to os, but R() to cout(?).
void OrderingConstraint::print(ostream &os)
{
  os << "Constraint of type ";
  print(k, os);
  os << " says this statement:" << endl;
  if (from)
    from->print(os, 1);
  else
    os << "????" << endl;
  os << "must precede this statement:" << endl;
  if (to)
    to->print(os, 1);
  else
    os << "????" << endl;
  os << (const char *) ((Relation *) R())->print_formula_to_string() << endl;
}

void Dep::normalize()
{
  
}

llist<OrderingConstraint *> *normalize(llist<OrderingConstraint *> *l)
{
  llist<OrderingConstraint *> *result = l;
  while (l != NULL) {
    l->front()->normalize();
    l = l->tail();
  }
  return result;
}

Relation needed_by(Relation const *been_done,
		   llist<OrderingConstraint *> *l, int n)
{
  Relation result = *emptyset(n);
  while (l != NULL) {
    result = Union(result, needed_by(been_done, l->front()->R()));
    DBG(printrel(result, "needed_by ..."));
    l = l->tail();
  }
  DBG(printrel(result, "Needed by ordering constraints:"));
  return result;
}

bool oc_violated(Relation *been_done, OrderingConstraint *o)
{
  return dep_violated(been_done, (Relation *) o->R());
}

bool oc_violated(OrderingConstraint *o, intvector *n)
{
  Relation *h = generic_halfspace(n);
  return oc_violated(h, o);
}

/* Return whether any OrderingConstraint on the list be violated
   by a plane with normal n.  Assumes all OrderingConstraints on the list
   refer to the vector space of interest. */
bool some_oc_violated_by_generic_plane(llist<OrderingConstraint *> *oc,
				       intvector *n)
{
  bool result = false;
  while (!result && oc != NULL)
    if (oc_violated(oc->front(), n))
      result = true;
    else
      oc = oc->tail();
  return result;
}

/* Return list of constraints in oc from f to t.  Caller should call
   free_all() on result. */
llist<OrderingConstraint *> *
filter_OrderingConstraints(llist<OrderingConstraint *> *oc, AC *f, AC *t)
{
  llist<OrderingConstraint *> *result = NULL;
  while (oc != NULL) {
    if (oc->front()->from->enclosed_by(f) && oc->front()->to->enclosed_by(t))
      result = cons(oc->front(), result);
    oc = oc->tail();
  }
  return dreverse(result);
}
							       

/* Return whether any OrderingConstraint from f to f might be violated
   by a plane with normal n. */
bool some_oc_violated_by_generic_plane(Foreach *f,
				       llist<OrderingConstraint *> *oc,
				       intvector *n)
{
  DBG(cout << "Checking if any deps violated by generic plane with normal " <<
      n->to_string() << "..." << endl);
  bool result =
    some_oc_violated_by_generic_plane(filter_OrderingConstraints(oc, f, f), n);
  if (!result)
    DBG(cout << "No deps violated by generic plane with normal " <<
	n->to_string() << endl);
  return result;
}

/* Assumes oc is a list of self-constraints for a loop, and been_done
   is a set of nodes that has been done.  Returns true iff doing p would not
   voilate any of the constraints in oc.  Does not modify its arguments. */
bool no_oc_violated(llist<OrderingConstraint *> *oc, Relation been_done,
		    intvector *p)
{
  return set_contains_intvector(compute_ready_set(been_done, oc), p);
}

/* Compute the ready set, given what has been done and a list of constraints.
   n is the arity of the iteration space.  Does not modify its arguments. */
Relation compute_ready_set(Relation been_done,
			   llist<OrderingConstraint *> *oc)
{
  int n = been_done.n_set();
  if (oc == NULL) {
    DPRINTLN2("compute_ready_set(..., NULL): whole space");
    return Relation::True(n);
  }
  DBG(printrel(been_done, "compute_ready_set(): been_done:"));
  Relation a(*wholespace(n));
  while (oc != NULL) {
    Relation const *r = oc->front()->R();
    DBG2(printrel(*r, "working on dep:"));

    Relation x = ready_wrt_dep(been_done, *r);
    DBG2(printrel(x, "ready wrt dep is:"));

    a = Intersection(a, x);
    a.simplify();
    DBG2(printrel(a, "a has now been cut down to:"));

    oc = oc->tail();
  }
  return a;
}

/* Destructively modifies x. */
Relation remove_nodes_that_violate_self_deps(Relation x,
					     llist<OrderingConstraint *> *oc)
{
  return Intersection(x, compute_ready_set(x, oc));
}