head     1.7;
branch   ;
access   ;
symbols  ;
locks    ; strict;
comment  @// @;


1.7
date     92.08.20.11.12.27;  author thoth;  state Exp;
branches ;
next     1.6;

1.6
date     92.08.14.15.44.49;  author thoth;  state Exp;
branches ;
next     1.5;

1.5
date     92.07.30.16.37.13;  author jnw;  state Exp;
branches ;
next     1.4;

1.4
date     92.07.26.16.46.17;  author thoth;  state Exp;
branches ;
next     1.3;

1.3
date     92.07.26.16.31.49;  author thoth;  state Exp;
branches ;
next     1.2;

1.2
date     92.07.21.11.28.39;  author thoth;  state Exp;
branches ;
next     1.1;

1.1
date     92.07.16.11.57.31;  author thoth;  state Exp;
branches ;
next     ;


desc
@implementation of the Yoder IntPointSet object.
@


1.7
log
@New constructor to make IntPointSets from arrays of Points
BaseIPS now requires the dimension upon construction
Binary operations are now much less monolithic
Canonicalization idiom improved
More boolean operations between IntPointSets, intersection,
symmetric+asymmetric difference.
@
text
@// Emacs: -*- C++ -*-
static char rcsid[] = "$Id: YoderIPS.cc,v 1.6 92/08/14 15:44:49 thoth Exp $";

// 
// $Log:	YoderIPS.cc,v $
// Revision 1.6  92/08/14  15:44:49  thoth
// Added an index(IntPoint) function to the IntPointSet
// 
// Revision 1.5  92/07/30  16:37:13  jnw
// Added intersection member function
// 
// Revision 1.4  92/07/26  16:46:17  thoth
// overlooked the fact that WhiteHoles and BlackHoles
// don't define the max and min methods.
// 
// Revision 1.3  92/07/26  16:31:49  thoth
// fixed a bug in the handling of the boxy predicate method.  also optimized
// to take advantage of invariants.
// switched the union operation to overload the bitwise operator.
// 
// Revision 1.2  92/07/21  11:28:39  thoth
// Actually wrote some code
// 
// Revision 1.1  92/07/16  11:57:31  thoth
// Initial revision
// 
// 

#include "ia.h"
#include "YoderIPS.h"
#pragma implementation

YoderIPS::YoderIPS(const BoxyIPS& bps)
: BaseIPS(bps.dim())
{
    this->slices = new interval[this->nslices=1];
    this->lastbefore = bps.min()[0]-1;

    this->slices[0].last = bps.max()[0];
    this->slices[0].count_last = bps.card();
    if (bps.dim()>1) {
	this->slices[0].shadow = IntPointSet(bps.shadow());
    } else {
	this->slices[0].shadow = WhiteHole;
    }
}



// aip must be a pointer to the beginning of an array of length len of
// IntPoints.  All IntPoints must have the same dimension.
// aip must be sorted into lexicographical order.
// aip may contain duplicates.
// len must be greater than 0
YoderIPS::YoderIPS(const IntPoint *aip, unsigned len, unsigned offset=0)
: BaseIPS( (len>0) ? aip[0].dimensions()-offset : 0 )
{
  // cout << "constructing Yoder from " << len << " points "
    // << "of dimen "<<dimen<<'\n' << flush;
  nslices=0;
  if (len==0) {
    slices = 0;
    lastbefore = 0;
    //cout << "maybe not\n" << flush;
    return;
  }
#if 0
  {
    for (unsigned i=0; i<len; i++)
      cout << cdr(aip[i],offset) << ' ';
    cout << '\n' << flush;
  }
#endif
  unsigned estimate = 1 + aip[len-1][offset] - aip[0][offset];
  if (estimate> len*2)
    estimate = len*2+1;
  // cout << "allocating "<< estimate <<" intervals\n";
  slices = new interval[estimate];
  lastbefore = aip[0][offset] - 1;

  unsigned i=0, j;

  if (dimen>1) {
    while (i<len) {
      j=i;
      register int	coord=aip[j][offset];
      for (; i<len && aip[i][offset]==coord; i++)
	;
      slices[nslices].last = coord;
      slices[nslices].shadow = YoderIPS(aip+j, i-j, offset+1);
      nslices++;
      if (i<len && aip[i][offset] > coord+1) {
	slices[nslices].last = aip[i][offset]-1;
	slices[nslices].shadow = BlackHole(dimen-1);
	// cout << "Black hole dimen " << dimen-1;
	// slices[nslices].shadow.output(cout);
	nslices++;
      }
    }
    this->canonicalize();
  } else {
    while (i<len) {
      j=i;
      for (; i+1<len && aip[i+1][offset] <= aip[i][offset]+1; i++)
	;
      // cout << '['<<j<<','<<i<<']' << flush;

      slices[nslices].last = aip[i][offset];
      slices[nslices].shadow = WhiteHole;
      nslices++;
      if (i+1<len) {
	slices[nslices].last = aip[i+1][offset] - 1;
	slices[nslices].shadow = BlackHole(0);
	nslices++;
      }
      i++;
    }
    this->compute_count_last();
  }
  // cout << "done\n" << flush;
}



YoderIPS::~YoderIPS()
{
    if (this->slices)
	delete[] this->slices;
}



YoderIPS::YoderIPS(const YoderIPS& ips)
:BaseIPS(ips.dimen)
{
    this->lastbefore = ips.lastbefore;
    this->nslices = ips.nslices;

    if (this->nslices)
	this->slices = new interval[this->nslices];
    else
	this->slices = 0;

    for (unsigned i=0; i<this->nslices; i++) {
	this->slices[i].last       = ips.slices[i].last;
	this->slices[i].count_last = ips.slices[i].count_last;
	this->slices[i].shadow     = ips.slices[i].shadow;
    }
}



YoderIPS& YoderIPS::operator=(const YoderIPS &ips)
{
    if (this->nslices != ips.nslices) {
	delete[] this->slices;
	this->nslices = ips.nslices;
	if (this->nslices)
	    this->slices = new interval[this->nslices];
	else
	    this->slices = 0;
    }
    for (unsigned i=0; i<this->nslices; i++) {
	this->slices[i] = ips.slices[i];
    }
    this->dimen = ips.dimen;
    this->lastbefore = ips.lastbefore;

    return *this;
}


//
//
//


int YoderIPS:: equal(BaseIPS* ips) const
{
    return ips->type() == YODER &&
	*this == *(YoderIPS*)ips;
}

int YoderIPS:: hash_self(int modulus) const
{
    unsigned sigma = this->dimen;
    sigma += this->lastbefore;
    for (unsigned i=0; i<this->nslices; i++) {
	sigma += this->slices[i].last;
	sigma += this->slices[i].shadow.hash_self(modulus);
    }
    return sigma%modulus;
}

int YoderIPS::operator==(const YoderIPS& ips) const
{
    if (this->dimen != ips.dimen ||
	this->lastbefore != ips.lastbefore ||
	this->nslices != ips.nslices)
	return 0;

    for (unsigned i=0; i < this->nslices; i++) {
	if (this->slices[i].last != ips.slices[i].last ||
	    this->slices[i].count_last != ips.slices[i].count_last ||
	    this->slices[i].shadow != ips.slices[i].shadow)
	    return 0;
    }
    return 1;
}

//
//

unsigned YoderIPS::cylinder_index(int coord) const
{
    if (this->nslices<1)
	return ~0;
    if (coord<=this->lastbefore ||
	coord>this->slices[this->nslices-1].last)
	return ~0;
 
    unsigned bottom, middle, top;
    bottom = 0;
    top = this->nslices -1;

    while (bottom<top) {
	middle = (bottom+top)/2;
	if (coord <= this->slices[middle].last) {
	    top = middle;
	} else {
	    bottom = middle+1;
	}
    }

    return bottom;
}

int YoderIPS::contains(IntPoint ip) const
{
    if (this->nslices<1)
	return 0;
    if (ip[0]<=this->lastbefore ||
	ip[0]>this->slices[this->nslices-1].last)
	return 0;

    return this->slices[cylinder_index(ip[0])].shadow.contains(cdr(ip));
    // return 0;
}

unsigned YoderIPS::index(const IntPoint &ip) const
{
    if (!this->contains(ip)) {
	if (IntPointSet::throw_on_index_uncontained)
	    throw(IA::INVALID_OPERATION, __FILE__,__LINE__);
	return IntPointSet::index_of_uncontained;
    }

    unsigned i = cylinder_index(ip[0]);

    unsigned before = i ? slices[i-1].count_last : 0;
    unsigned within = slices[i].shadow.card()
	* (ip[0] - (1+(i ? slices[i-1].last : lastbefore)));
    unsigned recurse = (dimen>1) ? slices[i].shadow.index(cdr(ip)) : 0;

    return before + within + recurse;
}

//
//

IntPoint YoderIPS::min() const
{
#if 0
    // we need IntPoint::concat(IntPoint)

    int	*vec;
    vec = new int[this->dimen];
    vec[0] = this->lastbefore +1;
    IntPoint	shadowmin = this->slices[0].shadow.min();
    for (unsigned i=0; i<shadowmin.dimensions(); i++)
	vec[i+1] = shadowmin[i];
    return IntPoint(vec, this->dimen, 1);
#else
    if (this->dimen>1)
	return concat(this->lastbefore+1 , this->slices[0].shadow.min());
    else
	return IntPoint(this->lastbefore+1);
#endif
}

IntPoint YoderIPS::max() const
{
#if 0
    int	*vec;
    vec = new int[this->dimen];
    vec[0] = this->slices[this->nslices -1].last;
    IntPoint	shadowmax = this->slices[this->nslices-1].shadow.max();
    for (unsigned i=0; i<shadowmax.dimensions(); i++)
	vec[i+1] = shadowmax[i];
    return IntPoint(vec, this->dimen, 1);
#else
    if (this->dimen>1)
	return concat(this->slices[this->nslices -1].last,
		      this->slices[this->nslices -1].shadow.max());
    else
	return IntPoint(this->slices[this->nslices -1].last);
#endif
}

int YoderIPS::empty() const
{
    for (unsigned i=0; i<this->nslices; i++) {
	if (!this->slices[i].shadow.empty())
	    return 0;
    }

    return 1;
}

int YoderIPS::isboxy() const
{
    if (this->nslices>1)
	return 0;
    if (this->nslices<1)
	return 1;
    switch (this->slices[0].shadow.type()) {
    case BOXY:
	// fall through
    case WHITE:
	return 1;
    default:
	return 0;
    }
}

//
//

void YoderIPS::compress_duplicates()
{
    unsigned low=0, high=0, scan;
    
    ////////////////
    // compress duplicates
    while (high<this->nslices && this->slices[high].shadow.empty() )
	high++;
    if (high>0)
	this->lastbefore = this->slices[high-1].last;

    while (high<this->nslices) {
	for (scan=high+1;
	     scan<this->nslices &&
	     this->slices[high].shadow == this->slices[scan].shadow;
	     scan++)
	    ;
	if (low<high) {
	    this->slices[low].shadow = this->slices[high].shadow;
	}
	this->slices[low].last = this->slices[scan-1].last;
	//
	low++;
	high = scan;
    }

    while (low>0 && this->slices[low-1].shadow.empty())
	low--;

    this->nslices = low;
}

void YoderIPS::compute_count_last()
{
  unsigned	total=0;
  ////////////////
  // scan through and set the count_last fields
      
  total = slices[0].count_last =
    (slices[0].last - lastbefore) *
      slices[0].shadow.card();
  
  for (unsigned i=1; i<nslices; i++) {
    total += (slices[i].last - slices[i-1].last) *
      slices[i].shadow.card();
    slices[i].count_last = total;
  }
}

void YoderIPS::canonicalize()
{
  compress_duplicates();
  compute_count_last();
}

void YoderIPS::interval_BlT(interval *source, interval*dest, unsigned count)
{
    for (unsigned i=0; i<count; i++) {
	dest[i].last = source[i].last;
	dest[i].shadow = source[i].shadow;
    }
}


//
//
//


void YoderIPS::union_nonoverlapping(
    const YoderIPS &first, const YoderIPS &second, YoderIPS &dest)

{
    dest.lastbefore = first.lastbefore;
    
    interval_BlT(first.slices, dest.slices, first.nslices);
    dest.nslices = first.nslices;
    
    if (dest.slices[dest.nslices-1].last < second.lastbefore) {
	// there is a gab between the two
	dest.slices[dest.nslices].last = second.lastbefore;
	dest.slices[dest.nslices].shadow = BlackHole(second.dimen -1);
	dest.nslices++;
    }
    
    interval_BlT(second.slices, dest.slices+dest.nslices, second.nslices);
    
    dest.nslices += second.nslices;
}

void YoderIPS:: copy_nonoverlapping_leader(
    const YoderIPS &first, unsigned *f_idx, const YoderIPS &second,
    YoderIPS &dest)
{
    dest.lastbefore = first.lastbefore;
    while (first.slices[*f_idx].last <= second.lastbefore) {
	dest.slices[dest.nslices] = first.slices[*f_idx];
	dest.nslices++;
	(*f_idx)++;
    }
    if (first.slices[*f_idx-1].last != second.lastbefore) {
	dest.slices[dest.nslices].last = second.lastbefore;
	dest.slices[dest.nslices].shadow =
	    first.slices[*f_idx].shadow;
	dest.nslices++;
    }
}

void YoderIPS:: copy_nonoverlapping_trailer(
    const YoderIPS &source, unsigned *s_idx, YoderIPS &dest)
{
    while (*s_idx < source.nslices) {
	dest.slices[dest.nslices].last = source.slices[*s_idx].last;
	dest.slices[dest.nslices].shadow =
	    source.slices[*s_idx].shadow;
	(*s_idx)++;
	dest.nslices++;
    }
}

void YoderIPS:: burn_nonoverlapping_leader(
    const YoderIPS &first, unsigned *f_idx, const YoderIPS &second,
    YoderIPS &dest)
{
    dest.lastbefore = second.lastbefore;
    while (first.slices[*f_idx].last <= second.lastbefore) {
	(*f_idx)++;
    }
}

void YoderIPS:: merge_overlapping_cylinders
  (const YoderIPS &first, unsigned *f_idx,
   const YoderIPS &second, unsigned *s_idx,
   YoderIPS &dest, IntPointSet(*f)(const IntPointSet&,const IntPointSet&))
{
  while ( *f_idx < first.nslices && *s_idx < second.nslices ) {
    dest.slices[dest.nslices].shadow =
      f(first.slices[*f_idx].shadow, second.slices[*s_idx].shadow);
    
    if (first.slices[*f_idx].last > second.slices[*s_idx].last) {
      dest.slices[dest.nslices].last = second.slices[*s_idx].last;
      (*s_idx)++;
    } else if (first.slices[*f_idx].last < second.slices[*s_idx].last) {
      dest.slices[dest.nslices].last = first.slices[*f_idx].last;
      (*f_idx)++;
    } else { /* == */
      dest.slices[dest.nslices].last = second.slices[*s_idx].last;
      (*s_idx)++; (*f_idx)++;
    }
    
    dest.nslices++;
  }
}

//

static IntPointSet tmp_or(const IntPointSet &lhs, const IntPointSet &rhs)
{
  return lhs | rhs;
}

YoderIPS YoderIPS::operator|(const YoderIPS &that) const
{
    YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	// need better error type
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return rval;
    }

    // this size is an upper bound.  It may be too loose by 1.
    rval.slices = new interval[ this->nslices+that.nslices+1 ];
    // rval.nslices is already 0

    if (this->slices[this->nslices-1].last <= that.lastbefore) {
      // *this does not overlap that at all
	union_nonoverlapping(*this, that, rval);
    } else if (that.slices[that.nslices-1].last <= this->lastbefore) {
      // *this does not overlap that at all
	union_nonoverlapping(that, *this, rval);
      
    } else {
      unsigned lidx=0, ridx=0;
      
      ////////////////
      // union the two Yoder PointSets
	  
      if (this->lastbefore < that.lastbefore) {
	copy_nonoverlapping_leader(*this, &lidx, that, rval);
      } else if (this->lastbefore > that.lastbefore) {
	copy_nonoverlapping_leader(that, &ridx, *this, rval);
      } else /* == */
	rval.lastbefore = that.lastbefore;
      
      merge_overlapping_cylinders (*this,&lidx, that,&ridx, rval, tmp_or);
      
      copy_nonoverlapping_trailer(*this, &lidx, rval);
      copy_nonoverlapping_trailer(that, &ridx, rval);
    }

    rval.canonicalize();

    return rval;
}

static IntPointSet tmp_and(const IntPointSet &lhs, const IntPointSet &rhs)
{
  return lhs & rhs;
}

YoderIPS YoderIPS::operator&(const YoderIPS &that) const
{
    YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	// need better error type
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return rval;
    }

    // this size is an upper bound.  It may be too loose by 1.
    rval.slices = new interval[ this->nslices+that.nslices+1 ];
    // rval.nslices is already 0

    if (this->slices[this->nslices-1].last <= that.lastbefore ||
	that.slices[that.nslices-1].last <= this->lastbefore) {
	return rval;
    } else {
      unsigned lidx=0, ridx=0;
      
      ////////////////
      // intersect the two Yoder PointSets
	  
      if (this->lastbefore < that.lastbefore) {
	burn_nonoverlapping_leader(*this, &lidx, that, rval);
      } else if (this->lastbefore > that.lastbefore) {
	burn_nonoverlapping_leader(that, &ridx, *this, rval);
      } else /* == */
	rval.lastbefore = that.lastbefore;
      
      merge_overlapping_cylinders (*this,&lidx, that,&ridx, rval, tmp_and);
      
    }

    rval.canonicalize();

    return rval;
}

//

static IntPointSet tmp_xor(const IntPointSet &lhs, const IntPointSet &rhs)
{
  return lhs ^ rhs;
}

YoderIPS YoderIPS::operator^(const YoderIPS &that) const
{
    YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	// need better error type
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return rval;
    }

    // this size is an upper bound.  It may be too loose by 1.
    rval.slices = new interval[ this->nslices+that.nslices+1 ];
    // rval.nslices is already 0

    if (this->slices[this->nslices-1].last <= that.lastbefore) {
      // *this does not overlap that at all
	union_nonoverlapping(*this, that, rval);
    } else if (that.slices[that.nslices-1].last <= this->lastbefore) {
      // *this does not overlap that at all
	union_nonoverlapping(that, *this, rval);
      
    } else {
      unsigned lidx=0, ridx=0;
      
      ////////////////
      // union the two Yoder PointSets
	  
      if (this->lastbefore < that.lastbefore) {
	copy_nonoverlapping_leader(*this, &lidx, that, rval);
      } else if (this->lastbefore > that.lastbefore) {
	copy_nonoverlapping_leader(that, &ridx, *this, rval);
      } else /* == */
	rval.lastbefore = that.lastbefore;
      
      merge_overlapping_cylinders (*this,&lidx, that,&ridx, rval, tmp_xor);
      
      copy_nonoverlapping_trailer(*this, &lidx, rval);
      copy_nonoverlapping_trailer(that, &ridx, rval);
    }

    rval.canonicalize();

    return rval;
}

static IntPointSet tmp_minus(const IntPointSet &lhs, const IntPointSet &rhs)
{
  return lhs - rhs;
}

YoderIPS YoderIPS::operator-(const YoderIPS &that) const
{
    YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	// need better error type
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return rval;
    }

    // this size is an upper bound.  It may be too loose by 1.
    rval.slices = new interval[ this->nslices+that.nslices+1 ];
    // rval.nslices is already 0

    if (this->slices[this->nslices-1].last <= that.lastbefore ||
	that.slices[that.nslices-1].last <= this->lastbefore) {
      return *this;
    } else {
      unsigned lidx=0, ridx=0;
      
      ////////////////
      // union the two Yoder PointSets
	  
      if (this->lastbefore < that.lastbefore) {
	copy_nonoverlapping_leader(*this, &lidx, that, rval);
      } else if (this->lastbefore > that.lastbefore) {
	burn_nonoverlapping_leader(that, &ridx, *this, rval);
      } else /* == */
	rval.lastbefore = that.lastbefore;
      
      merge_overlapping_cylinders (*this,&lidx, that,&ridx, rval, tmp_minus);
      
      copy_nonoverlapping_trailer(*this, &lidx, rval);
    }

    rval.canonicalize();

    return rval;
}


#if 0
void swap(const YoderIPS *p, const YoderIPS *q)
{
    const YoderIPS    *r;
    r = q;
    q = p;
    p = r;
}

YoderIPS YoderIPS::operator&(const YoderIPS &that) const
{
    YoderIPS  rval;
    const YoderIPS    *ps1, *ps2;
    
    if (this->dimen != that.dimen) {
	// need better error type
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return rval;
    }
    
    rval.dimen = this->dimen;
    ps1 = this;
    ps2 = &that;
    
    rval.slices = new interval[ (this->nslices+that.nslices+1) ];
    // rval.nslices is already 0
    
    // Get pointset with lowest coordinate slices into ps1
    if (ps1->lastbefore > ps2->lastbefore) {
	swap(ps1, ps2);
    }
    
    ////////////////
    // intersect the two Yoder PointSets
    
    unsigned lidx=0, ridx=0;
    
    if (ps1->slices[this->nslices-1].last >= ps2->lastbefore){
	
	// These PointSets overlap, thus we have something to do
	// Find the first overlapping slice
	
	if (ps1->slices[lidx].last < ps2->lastbefore) {
	    // The first slice doesn't overlap.
	    // Go looking for the first overlapping one.

	    while (ps1->slices[lidx].last <= ps2->lastbefore) {
		lidx++;
	    }
	    
	    // Set lastbefore to higher coordinate of overlapping slices
	    if ( ps1->slices[lidx - 1].last < ps2->lastbefore){
		rval.lastbefore = ps2->lastbefore;
	    } else {
		rval.lastbefore = ps1->slices[lidx -1].last +1;
	    }
	} else {
	    // First slices already overlap

	    // Set lastbefore to higher coord of already overlapping slices
	    if (ps1->lastbefore < ps2->lastbefore) {
		rval.lastbefore = ps2->lastbefore;
	    } else {
		rval.lastbefore = ps1->lastbefore;
	    }
	}

	while ( lidx < ps1->nslices && ridx < ps2->nslices) {
	    // As long as there are some overlapping slices
	    // intersect the left and right slices and store in rval
	    
	    rval.slices[rval.nslices].shadow = ps1->slices[lidx].shadow &
		ps2->slices[ridx].shadow;
	    
	    // Update lidx and ridx appropriately
	    
	    if ( ps1->slices[lidx].last > ps2->slices[ridx].last ) {
		rval.slices[rval.nslices].last = ps2->slices[ridx].last;
		
		ridx++;
	    } else if ( ps1->slices[lidx].last < ps2->slices[ridx].last ) {
		rval.slices[rval.nslices].last = ps1->slices[lidx].last;
		lidx++;
	    } else {
		rval.slices[rval.nslices].last = ps2->slices[ridx].last;
		lidx++; ridx++;
	    }
	    rval.nslices++;
	}
    }

    rval.canonicalize();

    return rval;
}
#endif


//
//

void YoderIPS::output(ostream &o, unsigned indent) const
{
  for (unsigned i=0; i<indent; i++)
    o << ' ';
  o << lastbefore << '\n';
  for (i=0; i<nslices; i++) {
    slices[i].shadow.output(o,indent+2);
    for (unsigned j=0; j<indent; j++)
      o << ' ';
    o << slices[i].last << '\n';
  }
}
@


1.6
log
@Added an index(IntPoint) function to the IntPointSet
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.cc,v 1.5 92/07/30 16:37:13 jnw Exp Locker: thoth $";
d6 3
a32 19
YoderIPS::YoderIPS(int begin, int end, const IntPointSet& shadow)
// this needs to die
{
    if (begin>end) {
	int	temp;
	temp = begin;
	begin = end;
	end = temp;
    }

    this->dimen = 1 + shadow.dim();
    this->slices = new interval[this->nslices = 1];
    this->lastbefore = begin-1;

    this->slices[0].last = end;
    this->slices[0].count_last = (end-begin+1) * shadow.card();
    this->slices[0].shadow = shadow;
}

d34 1
a35 1
    this->dimen = bps.dim();
d48 77
d131 2
d134 1
a135 1
    this->dimen = ips.dimen;
d151 2
d172 6
d211 3
d268 3
d336 2
a337 7
void YoderIPS::interval_BlT(interval *source, interval*dest, unsigned count)
{
    for (unsigned i=0; i<count; i++) {
	dest[i].last = source[i].last;
	dest[i].shadow = source[i].shadow;
    }
}
d339 1
a339 1
void YoderIPS::canonicalize()
d371 129
d502 1
a502 1
    YoderIPS	rval;
d510 2
a511 5
    rval.dimen = this->dimen;

    // this size is a VERY rough guess.
    // I'll analyze the loops below to figure out an upper bound.
    rval.slices = new interval[ (this->nslices+that.nslices+1) * 4 ];
d514 25
a538 1
    {
d540 1
a540 2
	if (this->slices[this->nslices-1].last <= that.lastbefore) {
	    // *this does not overlap that at all
d542 2
a543 1
	    rval.lastbefore = this->lastbefore;
d545 4
a548 2
	    interval_BlT(this->slices, rval.slices, this->nslices);
	    rval.nslices = this->nslices;
d550 3
a552 6
	    if (rval.slices[rval.nslices-1].last < that.lastbefore) {
		// there is a gab between the two
		rval.slices[rval.nslices].last = that.lastbefore;
		rval.slices[rval.nslices].shadow = BlackHole(that.dimen -1);
		rval.nslices++;
	    }
d554 5
a558 1
	    interval_BlT(that.slices, rval.slices+rval.nslices, that.nslices);
d560 3
a562 1
	    rval.nslices += that.nslices;
d564 19
a582 2
	} else if (that.slices[that.nslices-1].last <= this->lastbefore) {
	    // *this does not overlap that at all
d584 1
a584 1
	    rval.lastbefore = that.lastbefore;
d586 2
a587 9
	    interval_BlT(that.slices, rval.slices, that.nslices);
	    rval.nslices = that.nslices;
	    
	    if (that.slices[that.nslices-1].last < this->lastbefore) {
		// there is a gab between the two
		rval.slices[rval.nslices].last = this->lastbefore;
		rval.slices[rval.nslices].shadow = BlackHole(this->dimen -1);
		rval.nslices++;
	    }
d589 1
a589 2
	    interval_BlT(this->slices,rval.slices+rval.nslices,this->nslices);
	    rval.nslices += this->nslices;
d591 4
a594 1
	    // we need real code here.
d596 3
a598 42
	} else {
	    unsigned lidx=0, ridx=0;
	    
	    ////////////////
	    // union the two Yoder PointSets
	    
	    if (this->lastbefore < that.lastbefore) {
		rval.lastbefore = this->lastbefore;
		while (this->slices[lidx].last <= that.lastbefore) {
		    rval.slices[rval.nslices] = this->slices[lidx];
		    rval.nslices++;
		    lidx++;
		}
		if (this->slices[lidx-1].last != that.lastbefore) {
		    rval.slices[rval.nslices].last = that.lastbefore;
		    rval.slices[rval.nslices].shadow =
			this->slices[lidx].shadow;
		    rval.nslices++;
		} /* else
		    lidx++; // erroneous
		    */
	    } else if (this->lastbefore > that.lastbefore) {
		rval.lastbefore = that.lastbefore;
		while (that.slices[ridx].last <= this->lastbefore) {
		    rval.slices[rval.nslices] = that.slices[ridx];
		    rval.nslices++;
		    ridx++;
		}
		if (that.slices[ridx-1].last != this->lastbefore) {
		    rval.slices[rval.nslices].last = this->lastbefore;
		    rval.slices[rval.nslices].shadow =
			that.slices[ridx].shadow;
		    rval.nslices++;
		} /* else
		    ridx++;  // erroneous
		    */
	    } else /* == */
		rval.lastbefore = that.lastbefore;
	    
	    while ( lidx < this->nslices && ridx < that.nslices ) {
		rval.slices[rval.nslices].shadow =
		    this->slices[lidx].shadow | that.slices[ridx].shadow;
d600 4
a603 31
		if (this->slices[lidx].last > that.slices[ridx].last) {
		    rval.slices[rval.nslices].last = that.slices[ridx].last;
		    ridx++;
		} else if (this->slices[lidx].last < that.slices[ridx].last) {
		    rval.slices[rval.nslices].last = this->slices[lidx].last;
		    lidx++;
		} else { /* == */
		    rval.slices[rval.nslices].last = that.slices[ridx].last;
		    ridx++; lidx++;
		}
		
		rval.nslices++;
	    }
	    
	    if (lidx < this->nslices) {
		while (lidx < this->nslices) {
		    rval.slices[rval.nslices].last = this->slices[lidx].last;
		    rval.slices[rval.nslices].shadow =
			this->slices[lidx].shadow;
		    lidx++;
		    rval.nslices++;
		}
	    }
	    
	    while (ridx < that.nslices) {
		rval.slices[rval.nslices].last = that.slices[ridx].last;
		rval.slices[rval.nslices].shadow = that.slices[ridx].shadow;
		ridx++;
		rval.nslices++;
	    }
	}
d606 30
d638 2
a639 4
    {
	unsigned	total=0;
	////////////////
	// scan through and set the count_last fields
d641 4
a644 3
	total = rval.slices[0].count_last =
	    (rval.slices[0].last - rval.lastbefore) *
		rval.slices[0].shadow.card();
d646 8
a653 5
	for (unsigned i=1; i<rval.nslices; i++) {
	    total += (rval.slices[i].last - rval.slices[i-1].last) *
		rval.slices[i].shadow.card();
	    rval.slices[i].count_last = total;
	}
d656 27
d687 1
d780 3
a782 4
    {
	unsigned	total=0;
	////////////////
	// scan through and set the count_last fields
a783 3
	total = rval.slices[0].count_last =
	    (rval.slices[0].last - rval.lastbefore) *
		rval.slices[0].shadow.card();
d785 2
a786 6
	for (unsigned i=1; i<rval.nslices; i++) {
	    total += (rval.slices[i].last - rval.slices[i-1].last) *
		rval.slices[i].shadow.card();
	    rval.slices[i].count_last = total;
	}
    }
d788 11
a798 1
    return rval;
a799 1

@


1.5
log
@Added intersection member function
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.cc,v 1.4 92/07/26 16:46:17 thoth Exp Locker: jnw $";
d6 3
d140 1
a140 1
int YoderIPS::contains(IntPoint ip) const
d143 5
a147 5
	return 0;
    if (ip[0]<=this->lastbefore ||
	ip[0]>this->slices[this->nslices-1].last)
	return 0;

d154 1
a154 1
	if (ip[0] <= this->slices[middle].last) {
d161 12
a172 1
    return this->slices[bottom].shadow.contains(cdr(ip));
d174 18
@


1.4
log
@overlooked the fact that WhiteHoles and BlackHoles
don't define the max and min methods.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.cc,v 1.3 92/07/26 16:31:49 thoth Exp Locker: thoth $";
d6 4
d421 113
@


1.3
log
@fixed a bug in the handling of the boxy predicate method.  also optimized
to take advantage of invariants.
switched the union operation to overload the bitwise operator.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.cc,v 1.2 92/07/21 11:28:39 thoth Exp Locker: thoth $";
d6 5
d171 4
a174 1
    return concat(this->lastbefore+1 , this->slices[0].shadow.min());
d189 5
a193 2
    return concat(this->slices[this->nslices -1].last,
		  this->slices[this->nslices -1].shadow.max());
@


1.2
log
@Actually wrote some code
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.cc,v 1.1 92/07/16 11:57:31 thoth Exp Locker: thoth $";
d6 3
d19 1
d198 11
a208 5
    for (unsigned i=0; i<this->nslices; i++) {
	if (this->slices[i].shadow.type() == BOXY)
	    break;
	else if (!this->slices[i].shadow.empty())
	    return 0;
a209 4
    for ( i++; i<this->nslices; i++)
	if (!this->slices[i].shadow.empty())
	    return 0;
    return 1;
d252 1
a252 1
YoderIPS YoderIPS::operator||(const YoderIPS &that) const
d351 1
a351 1
		    this->slices[lidx].shadow || that.slices[ridx].shadow;
@


1.1
log
@Initial revision
@
text
@d2 1
a2 1
static char rcsid[] = "$Id$";
d5 3
a7 1
// $Log$
d9 391
@
