//
// ========================
// Multi Rect Domain Type A
// ========================
//
// This represents a domain that is a list of Rect Domains.  It
// is optimized for a fast "foreach" at the expense of set comparisons
// and operations.
//

#include "domains.h"

#define ASSERTREPOKON(mrad) ASSERTMSG(((mrad).repOK()==null),(mrad).repOK()+" at line "+__LINE__)
#define ASSERTREPOK()       ASSERTREPOKON(this)

#ifdef TI_DOMAINS_INTERNALCHECK
  #define DO_DEBUG(action) do { action; } while (false)
#else
  #define DO_DEBUG(action)
#endif

//The initializations of hashcache and bboxcache are redundant thanks to auto-init
#define INITCACHES() do {\
sizecache=-1; \
/*hashCache=0; */\
/*bBoxcache=new tiRectDomain();*/ \
} while(false)


// cannot use tiDomains.region for our temps, because they may outlast the user-provided region
// use GC region for now, possibly experiment with a library-created PrivateRegion later
#define TEMPS_REGION null

#if 1
  #define EMPTY_MRAD() emptyDomain()
#else
  #define EMPTY_MRAD() (new (tiDomains.region) tiMultiRectADomain())
#endif

#if 1
  #define MAKE_MRAD(region, arrayLength) makeDomain((region), (arrayLength))
#else
  #define MAKE_MRAD(region, arrayLength) \
     (new (region) tiMultiRectADomain(new (region) tiRectDomain[arrayLength]))
#endif

#if 1
  #define RD_TO_MRAD(RD) toDomain(RD)
#else
  #define RD_TO_MRAD(RD) (new (tiDomains.region) tiMultiRectADomain(RD))
#endif

/* Append an rd onto an rd[] using a doubling strategy if we run off the end
 * Also, autoincrement the index variable given
 */

#define appendrd(array,rd,idx) do { \
if (idx >= array.length) { \
tiRectDomain[] local temp=new (array.regionOf()) tiRectDomain[array.length*2]; \
System.arraycopy(array,0,temp,0,array.length); \
array=temp; \
} \
array[idx++]=rd; \
} while(false)

/* Acquire temporary array #tempnum, storing its pointer into target
 * If that array is null (unallocated), allocate it with length size
 * If the array has length<size, reallocate it with length size
 * Actually, reallocate with max(size,length*2)
 */

#define acquireTemp(tempnum,target,size) do { \
int localsize=size; \
target = myTmpArr##tempnum; \
DO_DEBUG(myTmpArr##tempnum = null); \
 if ((target == null) || (target.length < localsize)) \
   target = new (TEMPS_REGION) tiRectDomain[(target==null)?localsize:Math.max(localsize,target.length*2)]; \
} while(false)

/* Release temporary array number tempnum, whose pointer is currently held in variable target
 */

#define releaseTemp(tempnum,target) do { \
ASSERT(myTmpArr##tempnum == null); \
myTmpArr##tempnum = target; \
} while(false)

public final class tiMultiRectADomain extends tiDomain {

  /* --------------------------------------------------------------------- */
  /* native code implemented in compiler-generated domains.h */
  public static native tiDomain local emptyDomain();
     // return an empty Domain<N>
     // called directly by compiler codegen

  static native tiMultiRectADomain local makeDomain(Region r, int arrayLen);
     // construct and return a fresh Domain<N> with a rects array 
     // containing arrayLen rectangles. The object is fully initialized,
     // with the exception of the rect array elements, which need to be filled in
  /* --------------------------------------------------------------------- */

  public static inline tiDomain local toDomain(tiRectDomain rd) {
    // convert rd to a Domain
    // called directly by compiler codegen
    if (rd.isEmpty()) return emptyDomain();
    else {
        tiMultiRectADomain local result = makeDomain(tiDomains.region, 1);
        result.rects[0] = rd;
        ASSERTREPOKON(result);
        return result;
    }
  }

  // Constructors
  tiMultiRectADomain() {
    // this constructor is called at startup to create empty domains which are cached
    // and returned by subsequent calls to emptyDomain()
    rects = null;
    INITCACHES();
    //CHECK((repOK()==null),repOK()+" at line "+__LINE__);
    ASSERTREPOK();
  }

  tiMultiRectADomain(tiRectDomain[] rectList)
  {
    if (rectList == null || rectList.length==0) { // empty MRAD
      rects = null;
    } else if (rectList.isLocal() && rectList.regionOf() == this.regionOf()) {
      rects=(tiRectDomain[] local)rectList;
    } else {
      rects=new (this.regionOf()) tiRectDomain[rectList.length];
      System.arraycopy(rectList,0,rects,0,rects.length);
    }
    INITCACHES();
    //    CHECK((repOK()==null),repOK()+" at line "+__LINE__);
    ASSERTREPOK();
  }
     
  tiMultiRectADomain(tiMultiRectADomain copy) {
    // copy constructor
    
    rects = copy.getRectsJArray(this.regionOf()); //localizes for us
    // Copy over the caches if cheap
    if (copy.isLocal()) {
      sizecache=copy.sizecache; bBoxcache=copy.bBoxcache; hashCache=copy.hashCache;
    } else {
      INITCACHES();
    }
    // Do we even need to do a copy if we're duplicating a local Domain?
    
    //CHECK((repOK()==null),repOK()+" at line "+__LINE__);
    ASSERTREPOK();
  }

  tiMultiRectADomain(tiRectDomain rd) {

    if (!rd.isEmpty())
      {
	//System.out.println("Called tiMRAD("+rd+")");
	rects = new (this.regionOf()) tiRectDomain[1];
	rects[0] = rd;
	//System.out.println("\tResulting in"+this);
      }
    else
      rects=null;
    INITCACHES();
    //    CHECK((repOK()==null),repOK()+" at line "+__LINE__);
    ASSERTREPOK();
  }

  public tiMultiRectADomain(tiRectDomain [1d] rda) {
    // unchecked: assert that RectDomain's in rda are disjoint
    //    rects = new (this.regionOf()) tiRectDomainList();
    if (rda.domain().isEmpty()) { //empty Domain
      rects=null;
    } else {
      rects = new (this.regionOf()) tiRectDomain[rda.domain().size()];
      int idx=0;
      foreach (p in rda.domain()) {
	if (!rda[p].isEmpty())
	  rects[idx++]=rda[p];
      }
      if (idx==0) //We added no rectdomains - they were all empty
	rects=null;
      //Maybe we should scan the array first, and allocate later?
    }
    INITCACHES();
    //CHECK((repOK()==null),repOK()+" at line "+__LINE__);
    ASSERTREPOK();
  }
  public tiMultiRectADomain(Point<ARITY> [1d] pa) {
    // unchecked: assert that Point's in pa are disjoint
    if (pa.domain().isEmpty()) {
      rects=null;
    } else {
      rects = new (this.regionOf()) tiRectDomain[pa.domain().size()];
      int idx=0;
      foreach (p in pa.domain()) {
	rects[idx++]=new tiRectDomain(pa[p],pa[p]+ONES_POINT,true);
      }
    }
    INITCACHES();
    //CHECK((repOK()==null),repOK()+" at line "+__LINE__);
    ASSERTREPOK();
  }

  // Internal set relations routines
  // rectsToAddD == dlD || rectsToAddD == null
  // If testEmpty==false, calculates (tiDomains.region)(this-dlD+rectsToAddD)
  //                      if that would be empty, return null
  // If testEmpty==true, returns nonnull iff this-dlD is nonempty
  private tiDomain newSubtract(tiMultiRectADomain dlD,boolean testEmpty,tiMultiRectADomain rectsToAddD) {
     
    ASSERTMSG(dlD != null && (rectsToAddD == dlD || rectsToAddD==null),"Failed parameter invariant in tiMRAD.newSubtract");

    //System.out.println("\tEntered newSub subtracting "+new tiMultiRectADomain(dl)+" and adding "+new tiMultiRectADomain(rectsToAdd));
    // If this is empty, then this-anything is empty
    // This code will get screwed if a rect Domain can be stored in its bb
    if (rects==null) return (rectsToAddD != null ? rectsToAddD : this);
    // Subtracting nothing is rather pointless...
    if (dlD.rects==null) return this;

    //Localize the list of rectangles to subtract to lump together communication
    //This might suck for small subtractions, given alloc/copy overhead
    tiRectDomain[] local localdl = dlD.getRectsJArray();
    //TODO: could change append to if checkempty, return nonnull, else append

    // Initialize our inbox to the list of rectangles, using temp array 1
    // Also acquire our outbox, with the same length as the inbox
    // And get a count of valid elements in each array
    tiRectDomain[] local result,saved_result;
    int resultlength=rects.length, savreslength=0;
    acquireTemp(1,result,rects.length);
    acquireTemp(2,saved_result,rects.length);
    System.arraycopy(rects,0,result,0,rects.length);

    for (int dlidx=0; dlidx < localdl.length; dlidx++) {

      //Swap the inbox and outbox and replace validity lengths
      tiRectDomain[] local rdswap=saved_result;
      saved_result=result;
      result=rdswap;
      savreslength=resultlength; resultlength=0;
      
      tiRectDomain curdl=localdl[dlidx];

      for (int sridx=0; sridx < savreslength; sridx++) {
	
	tiRectDomain sr_sridx=saved_result[sridx];
	tiRectDomain id = sr_sridx * curdl;

	if (id.isEmpty()) {
	  appendrd(result,sr_sridx,resultlength);
	} else if (id == sr_sridx) {
	  // do nothing
	} else {
	  tiRectDomain rd = sr_sridx;
	  Point<ARITY> p0 = rd.min();
	  Point<ARITY> p1 = rd.upb();
	  Point<ARITY> stride = rd.getStride();

	  // slice
	  for (int i = 0; i < ARITY; i++) {
	    int rd_p0 = p0.get(i);
	    int rd_p1 = p1.get(i);
	    int id_p0 = id.min().get(i);
	    int id_p1 = id.upb().get(i);

	    if (rd_p0 < id_p0) {
	      appendrd(result,new tiRectDomain(p0,p1.set(i,id_p0),stride),resultlength);
	      p0 = p0.set(i, id_p0);
	    }
	    if (rd_p1 > id_p1) {
	      appendrd(result,new tiRectDomain(p0.set(i,(id_p1-1+stride.get(i))),
					       p1,stride),resultlength);
	      p1 = p1.set(i, id_p1);
	    }
	  }

	  // handle interior of overlap
	  Point<ARITY> id_stride=id.getStride();
	  for (int i = 0; i < ARITY; i++) {
	    if (stride.get(i) < id_stride.get(i)) {
	      for (int set_p0 = p0.get(i);
		   set_p0 < (p1.get(i) -
			     id_stride.get(i));
		   set_p0 += id_stride.get(i)) {
		appendrd(result,new tiRectDomain(p0.set(i,(set_p0 + stride.get(i))),
						 p1.set(i,(set_p0 + id_stride.get(i))),
						 stride),resultlength);
	      }
	      stride = stride.set(i,
				  id_stride.get(i));
	    }
	  }
	}
      }
    }
    
    if (testEmpty) {
      //System.out.println("\tReturning out of testEmpty check");
      tiMultiRectADomain realresult = null;
      if (resultlength != 0) realresult=this;
      releaseTemp(1,result);
      releaseTemp(2,saved_result);
      return realresult;
    } else {
      int totallen = resultlength;
      if (rectsToAddD != null) totallen += localdl.length; // use guarantee that rectsToAddD == dlD
      if (totallen == 0) {
	//System.out.println("\tReturning out of resultlen=0 and rectstoadd=null");
	releaseTemp(1,result);
	releaseTemp(2,saved_result);
	return EMPTY_MRAD();
      }
	
      // Dump result into tiDomains.region since that's what op+/op- want
      tiMultiRectADomain local realresult = MAKE_MRAD(tiDomains.region, totallen);
      if (resultlength > 0) System.arraycopy(result,0,realresult.rects,0,resultlength);
      if (totallen > resultlength) System.arraycopy(localdl,0,realresult.rects,resultlength,localdl.length);
      releaseTemp(1,result);
      releaseTemp(2,saved_result);
      return realresult;
    }
  }

  // Set Relations
  public tiDomain op+(tiDomain d) {
    //System.out.println("Calling newSub on "+this+" subtracting "+d);
    return newSubtract((tiMultiRectADomain)d,false,(tiMultiRectADomain)d);
  }
  public tiDomain op-(tiDomain d) {
    return newSubtract((tiMultiRectADomain)d,false,null);
  }
  public tiDomain op*(tiDomain d) {
    // this * d
    tiRectDomain[] local result;
    int resultsize=0;
    //already localized
    tiRectDomain[] local other = d.getRectsJArray();

    if ((rects==null) || (other==null)) { //Isct anything with empty is empty
      return EMPTY_MRAD();
    }

    if ((rects.length==1) && (other.length==1)) { //Intersecting rectangles!
      tiRectDomain res=rects[0] * other[0];
      if (res.isEmpty()) {
	return EMPTY_MRAD();
      } else {
	tiMultiRectADomain local retval = MAKE_MRAD(tiDomains.region,1);
	retval.rects[0]=res;
	return retval;	
      }
    }

    acquireTemp(1,result,2);
    for (int myidx=0; myidx < rects.length; myidx++) {
      tiRectDomain myRD = rects[myidx];
      for (int d_idx=0; d_idx < other.length; d_idx++) {

	tiRectDomain partial = myRD * other[d_idx];

	if (!partial.isEmpty()) {
	  appendrd(result,partial,resultsize);
	}
      }
    }
    if (resultsize != 0) {
      tiMultiRectADomain local retval = MAKE_MRAD(tiDomains.region, resultsize);
      System.arraycopy(result,0,retval.rects,0,resultsize);
      releaseTemp(1,result);
      
      return retval;
    } else {
      releaseTemp(1,result);
      return EMPTY_MRAD();
    }
  }
  /* op-assign operators */
  // DOB: Because tiDomain is implemented using mutables, 
  // it may be more efficient (reduce memory churn, etc) to implement these directly
  // (and perhaps implement the non-assign versions in terms of these)
  public inline tiDomain op+=(tiDomain d) { return this + d; }
  public inline tiDomain op-=(tiDomain d) { return this - d; }
  public inline tiDomain op*=(tiDomain d) { return this * d; }
  //DEPRECATED - use isEmpty
  public inline boolean isNull() {
    // this is the empty set
    return rects==null;
  }
  //DEPRECATED - use isNotEmpty
  public inline boolean isNotNull() {
    return !isNull();
  }
  public inline boolean isEmpty() {
    // this is the empty set
    return rects==null;
  }
  public inline boolean isNotEmpty() {
    return !isEmpty();
  }
  public boolean isADR() {
    if (rects==null)
      return true;
    for (int idx=0; idx < rects.length; idx++) {
      if (!rects[idx].isADR())
	return false;
    }
    return true;
  }
  
  public inline boolean equals(tiDomain d) {
    // this == d
    if (size()!=d.size()) return false;
    if (boundingBox()!=d.boundingBox()) return false;
    return (this-d).isEmpty();
  }
  public boolean op<=(tiDomain d) { // isSubset
    // this <= d
    return newSubtract((tiMultiRectADomain)d,true,null)==null;
  }
  public boolean op<(tiDomain d) { // isStrictSubset
    // this < d
    return (this <= d) && !(d <= this);
  }
  public boolean op>=(tiDomain d) { // isSuperset
    return d <= this;
  }
  public boolean op>(tiDomain d) { // isStrictSuperset
    return d < this;
  }

  // Object relations
  public boolean equals(Object d) {
    return ((d instanceof tiDomain) && (this.equals((tiDomain)d)));
  }

  // RectDomain Relations
  public tiDomain op+(tiRectDomain rd) {
    return this + (RD_TO_MRAD(rd));
  }
  public tiDomain op-(tiRectDomain rd) {
    return this - (RD_TO_MRAD(rd));
  }
  public tiDomain op*(tiRectDomain rd) {
    return this * (RD_TO_MRAD(rd));
  }
  public tiDomain op+=(tiRectDomain rd) {
    return this + (RD_TO_MRAD(rd));
  }
  public tiDomain op-=(tiRectDomain rd) {
    return this - (RD_TO_MRAD(rd));
  }
  public tiDomain op*=(tiRectDomain rd) {
    return this * (RD_TO_MRAD(rd));
  }

  // TODO: these could be optimized further by first checking rd against boundingBox
  public inline boolean equals(tiRectDomain rd) {
    return this.equals(RD_TO_MRAD(rd));
  }
  public boolean op<=(tiRectDomain rd) { // isSubset
    return this <= (RD_TO_MRAD(rd));
  }
  public boolean op<(tiRectDomain rd) { // isStrictSubset
    return this < (RD_TO_MRAD(rd));
  }
  public boolean op>=(tiRectDomain rd) { // isSuperset
    return this >= (RD_TO_MRAD(rd));
  }
  public boolean op>(tiRectDomain rd) { // isStrictSuperset
    return this > (RD_TO_MRAD(rd));
  }

  // Point Relations
  public tiDomain op+(Point<ARITY> p) {
    // this + p

    if (rects==null)
      return EMPTY_MRAD();
   
    tiMultiRectADomain local retval = MAKE_MRAD(tiDomains.region, rects.length);
    tiRectDomain[] local result = retval.rects;
 
    for (int ctr=0; ctr < rects.length; ctr++) {
      result[ctr]=rects[ctr]+p;
    }

    ASSERTREPOKON(retval);
    return retval;
  }
  public tiDomain op-(Point<ARITY> p) {
    // this - p
    if (rects==null)
      return EMPTY_MRAD();

    tiMultiRectADomain local retval = MAKE_MRAD(tiDomains.region, rects.length);
    tiRectDomain[] local result = retval.rects;

    for (int ctr=0; ctr < rects.length; ctr++)
      result[ctr]=rects[ctr]-p;

    ASSERTREPOKON(retval);
    return retval;
  }
  public tiDomain op/(Point<ARITY> p) {
    // this / p
    tiDomain result = EMPTY_MRAD();

    if (rects==null)
      return result;

    for (int ctr=0; ctr < rects.length; ctr++) {
      // Call the add function to remove any overlaps generated by rounding
      // effects during the divide.
      result = result + (rects[ctr] / p);
    }

    return result;
  }
  public tiDomain op*(Point<ARITY> p) {
    // this * p
    if (rects==null)
      return EMPTY_MRAD();

    tiMultiRectADomain local retval = MAKE_MRAD(tiDomains.region, rects.length);
    tiRectDomain[] local result = retval.rects;

    for (int ctr=0; ctr < rects.length; ctr++)
      result[ctr]=rects[ctr]*p;

    ASSERTREPOKON(retval);
    return retval;
  }
  /* op-assign operators */
  // DOB: Because tiDomain is implemented using mutables, 
  // it may be more efficient (reduce memory churn, etc) to implement these directly
  // (and perhaps implement the non-assign versions above in terms of these)
  public inline tiDomain op+=(Point<ARITY> p) { return this + p; }
  public inline tiDomain op-=(Point<ARITY> p) { return this - p; }
  public inline tiDomain op*=(Point<ARITY> p) { return this * p; }
  public inline tiDomain op/=(Point<ARITY> p) { return this / p; }

  public tiDomain permute(Point<ARITY> p) {
    if (rects==null)
      return EMPTY_MRAD();
    
    tiMultiRectADomain local retval = MAKE_MRAD(tiDomains.region, rects.length);
    tiRectDomain[] local result = retval.rects;

    for (int ctr=0; ctr < rects.length; ctr++)
      result[ctr]=rects[ctr].permute(p);
    
    ASSERTREPOKON(retval);
    return retval;
  }

  // Shape Information
  public boolean contains(Point<ARITY> p) {
    // this contains p
  
    if (rects==null) return false;
    if (! boundingBox().contains(p)) return false;
    for (int ctr=0; ctr < rects.length; ctr++) {
      if (rects[ctr].contains(p)) {
	return true;
      }
    }
    return false;
  }
  //If this.isEmpty, returns null
  //Else, returns null if !isRectangular, otherwise returns a tiRectDomain[] with exactly one item - a tiRD rd such that rd==this
  //If this.isRectangular and this.isLocal, modifies this.rects so that it contains only one item, as specified above
  // Remember to disambiguate a null result by checking isEmpty
  tiRectDomain[] isRectangularEx() {
    //if we're empty or a single rd, then clearly we're rectangular
    //if ((rects.getNumItems()==0)||(rects.getNumItems()==1))
    if ((rects==null) || (rects.length==1))
      return rects;
        
    int size=0;
    tiRectDomain bb=boundingBox();
    Point<ARITY> min=bb.min();
    Point<ARITY> base_upb=min;
    Point<ARITY> upb=bb.upb();
    int base_size[]=new (TEMPS_REGION) int[ARITY]; //Depending on the default initialization to zero
    Point<ARITY> theStride=ONES_POINT;
    
    //Calculate the base-row lengths, base-row maxes, and this.size()
    //For details on the algorithm, see PR677

    for (int ctr=0; ctr < rects.length; ctr++) {
      tiRectDomain rd=rects[ctr];
      size+=rd.size();

      for (int varyingdim=0;varyingdim<ARITY;varyingdim++) {
	boolean rowpresent=true;
	
	for (int ar=0;ar < ARITY && rowpresent; ar++) {
	  if (ar==varyingdim) continue; //We're varying this coord
	  if (rd.min().get(ar) > min.get(ar)) //If the rd is based above the min we won't have a row to examine
	    rowpresent=false;
	}
	if (rowpresent) {
	  //We know that every other coordinate is fixed, so we just want the variation possible in
	  //varyingdim. This will be bounded by the max and min, divided by the stride in that dimension
	  int len=((rd.upb().get(varyingdim) - 1 - rd.min().get(varyingdim))/rd.stride().get(varyingdim))+1;
	  base_upb=base_upb.set(varyingdim,tiDomainUtils.max(base_upb.get(varyingdim),rd.upb().get(varyingdim)));
	  //	  System.out.println("Found row of length "+len+" varying dimension "+varyingdim+" in "+rd);
	  base_size[varyingdim]+=len;
	}
      }
    }
    
    //Make sure the maxes are compatible
    if (base_upb != upb) return null;
    //Calculate the base stride
    for (int dim=0;dim < ARITY; dim++) {
      int bbsize=upb.get(dim) - min.get(dim);
      if (bbsize != 1) { //if bbsize==1, s[i]=1, which it's initialized to anyway
	if ((bbsize - 1) % (base_size[dim] - 1) != 0) return null;
	theStride.set(dim,(bbsize - 1)/(base_size[dim] - 1));
      }
    }
    
    tiRectDomain rectResult=new tiRectDomain(min,upb,theStride);
    //Check that we have the right number of points
    if (rectResult.size() != size) return null;

    //Verify that each rectangle is compatible with the putative rectResult
    for (int ctr=0; ctr < rects.length; ctr++)
      if (!(rects[ctr]<=rectResult)) return null;
    
    tiRectDomain[] local result= new (this.isLocal()?this.regionOf():tiDomains.region) tiRectDomain[1];
    result[0]=rectResult;
    
    if (this.isLocal()) {
      ((tiMultiRectADomain local)this).rects=result; 
      ASSERTREPOK();
    }    

    return result;
  }
  //If this.isRectangularEx!=null and this.isLocal, modifies this as specified in interface to isRectangularEx
  public inline boolean isRectangular() {
    //if we're empty or a single rd, then clearly we're rectangular
    //isRectEx now returns null on empty, too
     return (isEmpty() || (isRectangularEx()!=null));
  }    

  public int size() {
    if (sizecache == -1) {//Check for a cached value
      int result = 0;
      if (rects!=null) {
	for (int ctr=0; ctr < rects.length; ctr++) {
	  result += rects[ctr].size();
	}
      }
      sizecache=result;
    }
    return sizecache;
  }
  public Point<ARITY> min() {
    return boundingBox().min();
  }
  public Point<ARITY> lwb() {
    return min();
  }
  public Point<ARITY> upb() {
    return boundingBox().upb();
  }
  public Point<ARITY> max() {
    return upb() - (ONES_POINT);
  }

  public tiRectDomain boundingBox() {
    if (bBoxcache.isEmpty() && (!isEmpty())) { //BB is not cached
      Point<ARITY> min,upb;
      //Expand min() and upb() inline so that we don't loop over rectangles twice
	upb=rects[0].upb();
	min=rects[0].min();
	for (int ctr=1; ctr < rects.length; ctr++) {
	  upb=upb.upperBound(rects[ctr].upb());
	  min=min.lowerBound(rects[ctr].min());
	}
	bBoxcache=new tiRectDomain(min,upb,true);
      }

    return bBoxcache;
  }    

  //As getRectsJArray() (below), but the returned array will be in Region r
  inline private tiRectDomain[] local getRectsJArray(Region r) {
    if (rects==null) return null;
    if (this.isLocal() && this.regionOf() == r) return (tiRectDomain[] local) rects;
    tiRectDomain[] result=new (r) tiRectDomain[rects.length];
    System.arraycopy(rects,0,result,0,rects.length);
    return (tiRectDomain[] local) result;
  }
  // return a non-empty local Java array containing a set of disjoint RectDomains covering the area
  // if the Domain is empty, return NULL (*never* an empty array)
  //if this.islocal, return rects, otherwise copy
  inline public tiRectDomain[] local getRectsJArray() {
    return getRectsJArray(this.regionOf());
  }
  public tiRectDomain [1d] RectDomainList() {
    return (tiRectDomain [1d])RectDomainListLocal();
  }
  public tiRectDomain [1d] local RectDomainListLocal() { // private interface also used by code-grid.cc
    int numRectangles = (rects==null)?0:rects.length;
    tiRectDomain [1d] local result =
      new (tiDomains.region) tiRectDomain [[1 : numRectangles : 1]];
    if (rects!=null) {    
      for (int ctr=0; ctr < rects.length; ctr++) {
	result[[ctr+1]] = rects[ctr];
      }
    // assert (numRectsAdded == numRectangles);
    }
    return result;
  }
  public Point<ARITY> [1d] PointList() {
    return (Point<ARITY> [1d])PointListLocal();
  }
  public Point<ARITY> [1d] local PointListLocal() { // private interface also used by code-grid.cc
    int numPoints = size();
    Point<ARITY> [1d] local result =
      new (tiDomains.region) Point<ARITY> [[1 : numPoints : 1]];
    int numPointsAdded = 0;

    if (rects!=null) {
      for (int ctr=0; ctr < rects.length; ctr++) {
	//rep invar is such that we'll never call this on an empty rd...
	RectDomain<ARITY> rd=[rects[ctr].min() : rects[ctr].max() : rects[ctr].stride()];
      foreach (p in rd) {
	numPointsAdded++;
	result[[numPointsAdded]] = p;
      }
    }
    }
    // assert (numPointsAdded == numPoints);
    return result;
  }

  // Internal dynamic optimization routines
  private void joinRectangles() {

    if (!(isLocal()) || (rects==null) || (rects.length==1)) return;

    boolean changes_made;
    tiRectDomain[] local currList,newList;
    acquireTemp(1,currList,rects.length);
    System.arraycopy(rects,0,currList,0,rects.length);
    acquireTemp(2,newList,rects.length);
    boolean ignore[] = new (TEMPS_REGION) boolean[rects.length];
    int currListLen=rects.length, newListLen=0;
    
    do {
      changes_made = false;
      newListLen=0;
      for (int i=0; i < currListLen; i++) {
	ignore[i] = false;
      }

      int searchIndexInit = 0;
      for (int curidx=0; curidx < currListLen; curidx++) {
	if (!ignore[searchIndexInit]) {
	  int searchIndex = searchIndexInit + 1;
	  boolean matchFound = false;
	  for (int compidx=1; ((compidx < currListLen) && (!matchFound)); compidx++) {
	    if (!ignore[searchIndex]) {
	      tiDomain result = currList[curidx] + currList[compidx];
	      tiRectDomain[] local rdl = result.getRectsJArray();
	      if (rdl.length==1) { //rdl should never be null here - never get empty RDs
		appendrd(newList,rdl[0],newListLen);
		changes_made = true;
		matchFound = true;
		ignore[searchIndex] = true;
	      }
	    }
	    searchIndex++;
	  }
	  if (!matchFound) {
	    appendrd(newList,currList[curidx],newListLen);
	  }
	}
	searchIndexInit++;
      }
      tiRectDomain[] local rdswap=currList;
      currList = newList;
      newList=rdswap;
      //No need to swap lengths - newListLen gets clobbered at the top of the loop anyway
      currListLen=newListLen;
    } while (changes_made);
    if (currListLen < rects.length) {
      tiRectDomain[] local newrects=new (rects.regionOf()) tiRectDomain[currListLen];
      System.arraycopy(currList,0,newrects,0,currListLen);
      ((tiMultiRectADomain local)this).rects = newrects;
    }

    // these may be inverted here, but that's ok
    releaseTemp(1,currList);
    releaseTemp(2,newList);
 
    ASSERTREPOK();
  }

  // Dynamic optimizations
  // IsRectangularEx already does a join if the Domain is rectangular
  public tiDomain demote() {
    if (!isEmpty() && (isRectangularEx()==null))
      joinRectangles();

    return this;
  }
  public void optimize() {
    demote();
  }

  // Object overrides

  // Convert to a string
  public String toString() {
    String result;
    boolean isFirst;

    isFirst = true;
    result = "";
    if (rects!=null) {
      for (int ctr=0; ctr < rects.length; ctr++) {
	tiRectDomain dom=rects[ctr];
	if (!dom.isEmpty()) {
	  if (!isFirst) {
	      result = result + " + ";
	    }
	    result = result + dom.toString();
	    isFirst = false;
	}
      }
    }
    if (isFirst) //if this is an empty Domain
	return (new tiRectDomain()).toString();
    else
	return result;
  }

  public int hashCode() { 
    if (hashCache == 0) {
      int retval = 0;
      Point<ARITY> min = min();
      Point<ARITY> upb = upb();
      for (int i = 0; i < ARITY; i++) {
	retval ^= (min.get(i) << 16) | upb.get(i);
      }
      retval ^= size();
      hashCache = (retval == 0)?1:retval;
    }
    return hashCache;
  }

  // Debugging
  /*
  public void print(String desc) {
    int count = 0;
    for (tiRectDomainListIterator d_iter = rects.newIterator();
	 !d_iter.isEnd();
	 d_iter.advance()) {
      count++;
      tiRectDomain rd = d_iter.dereference();
      Point<ARITY> p = rd.min();
      System.out.print(desc);
      System.out.print("(");
      System.out.print(count);
      System.out.print(") [[");
      for (int i = 0; i < p.arity(); i++) {
	if (i != 0) System.out.print(",");
	System.out.print(p.get(i));
      }
      System.out.print("] : ");
      Point<ARITY> p2 = rd.upb();
      System.out.print("[");
      for (int i = 0; i < p2.arity(); i++) {
	if (i != 0) System.out.print(",");
	System.out.print(p2.get(i));
      }
      System.out.print("] : ");
      Point<ARITY> p3 = rd.getStride();
      System.out.print("[");
      for (int i = 0; i < p3.arity(); i++) {
	if (i != 0) System.out.print(",");
	System.out.print(p3.get(i));
      }
      System.out.println("]]");
    }
  }
  */
  //returns null on invariant ok, otherwise an error string
  private String repOK() {
    if (rects==null) {
      if (!(sizecache==-1 || sizecache==0))
	return "size cached incorrectly for an empty Domain";
      if (!bBoxcache.isEmpty())
	return "bounding box cached incorrectly for an empty Domain";
      return null;
    }
    else {
      if (this.regionOf() != rects.regionOf() ||
	  this.creator() != rects.creator())
	return "representational region invariant violated"; 
      if (rects.length==0)
	return "rects is a zero-length array";
      for (int idx=0;idx<rects.length;idx++) {
	if (rects[idx].isEmpty())
	  return "found empty RD in the rects list";
      }
      return null;
    }
  }
  // State
  private tiRectDomain[] local rects;
    // array of nonempty disjoint RD's which cover the domain
    // always has the same locality as "this" and therefore stored as local ptr
    // if the MRAD is empty, then (list == null),
    //  (ie NEVER an empty array or array with all empty entries)
    // every RD in the list is part of the Domain
  
  private int sizecache;
    // cached .size() for the Domain, or -1 if never been computed
  
  private int hashCache;
    // cached .hashCode(), or 0 if never been computed (implies that the hashCode of a domain is never 0)

  private tiRectDomain bBoxcache;
    // cached unit-stride bounding box of the Domain, or emptyRD if never computed

  private static tiRectDomain [] local myTmpArr1;
    // Temporary thread-local buffer used in various MRAD ops. Should only be used with the acquireTemp and releaseTemp macros
  private static tiRectDomain [] local myTmpArr2;
    // Temporary thread-local buffer used in various MRAD ops. Should only be used with the acquireTemp and releaseTemp macros
}