head	1.34;
access;
symbols
	r2_1:1.31
	r2_0:1.31
	r1_1_beta:1.30
	r1_1_alpha:1.29
	r1_0:1.29
	r0_11:1.28
	r0_10:1.28
	r0_9:1.27
	Eglin_alpha_1:1.25;
locks; strict;
comment	@// @;


1.34
date	94.11.10.19.53.56;	author ljr;	state Exp;
branches;
next	1.33;

1.33
date	94.10.06.17.39.00;	author fjsoria;	state Exp;
branches;
next	1.32;

1.32
date	94.09.13.19.12.56;	author ljr;	state Exp;
branches;
next	1.31;

1.31
date	94.08.26.15.37.08;	author thoth;	state Exp;
branches;
next	1.30;

1.30
date	94.07.25.16.58.52;	author thoth;	state Exp;
branches;
next	1.29;

1.29
date	94.05.08.19.36.58;	author thoth;	state Exp;
branches;
next	1.28;

1.28
date	94.01.31.16.39.12;	author thoth;	state Exp;
branches;
next	1.27;

1.27
date	93.09.15.12.34.20;	author thoth;	state Exp;
branches;
next	1.26;

1.26
date	93.07.15.11.35.25;	author thoth;	state Exp;
branches;
next	1.25;

1.25
date	93.05.28.15.05.31;	author thoth;	state Exp;
branches;
next	1.24;

1.24
date	93.05.26.16.57.51;	author thoth;	state Exp;
branches;
next	1.23;

1.23
date	93.05.19.14.45.45;	author thoth;	state Exp;
branches;
next	1.22;

1.22
date	93.04.29.12.52.59;	author thoth;	state Exp;
branches;
next	1.21;

1.21
date	93.04.19.23.27.48;	author thoth;	state Exp;
branches;
next	1.20;

1.20
date	93.04.17.15.19.55;	author thoth;	state Exp;
branches;
next	1.19;

1.19
date	93.04.16.15.50.25;	author thoth;	state Exp;
branches;
next	1.18;

1.18
date	93.02.12.16.28.02;	author thoth;	state Exp;
branches;
next	1.17;

1.17
date	93.01.20.11.38.30;	author thoth;	state Exp;
branches;
next	1.16;

1.16
date	92.12.16.14.48.24;	author thoth;	state Exp;
branches;
next	1.15;

1.15
date	92.12.07.12.05.13;	author thoth;	state Exp;
branches;
next	1.14;

1.14
date	92.11.15.15.58.29;	author thoth;	state Exp;
branches;
next	1.13;

1.13
date	92.11.11.12.12.00;	author thoth;	state Exp;
branches;
next	1.12;

1.12
date	92.11.04.12.02.14;	author thoth;	state Exp;
branches;
next	1.11;

1.11
date	92.10.25.20.54.08;	author thoth;	state Exp;
branches;
next	1.10;

1.10
date	92.10.22.15.13.05;	author thoth;	state Exp;
branches;
next	1.9;

1.9
date	92.09.30.10.39.31;	author thoth;	state Exp;
branches;
next	1.8;

1.8
date	92.09.20.17.37.46;	author thoth;	state Exp;
branches;
next	1.7;

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

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

1.5
date	92.09.03.13.36.21;	author thoth;	state Exp;
branches;
next	1.4;

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

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

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

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


desc
@CFrontified version
@


1.34
log
@Added IA_NO_RCS_STATIC_DATA guard.
@
text
@// Emacs: -*- C++ -*-

//
//	Copyright 1993, Center for Computer Vision and Visualization,
//	University of Florida.  All rights reserved.
//

#ifndef IA_NO_RCS_STATIC_DATA
static char copyright[] = "Copyright 1993, Center for Computer Vision and Visualization,\nUniversity of Florida.  All rights reserved.\n";

static char rcsid[] = "$Id: YoderIPS.c,v 1.33 1994/10/06 17:39:00 fjsoria Exp ljr $";
#endif

//
// $Log: YoderIPS.c,v $
// Revision 1.33  1994/10/06  17:39:00  fjsoria
// commented rscid[] line
//
// Revision 1.32  1994/09/13  19:12:56  ljr
// Added workarounds for conditional expressions that create temporaries.
//
// Revision 1.31  1994/08/26  15:37:08  thoth
// DOS-inspired name rework (internal files)
//
// Revision 1.30  1994/07/25  16:58:52  thoth
// \Name sanitization
//
// Revision 1.29  1994/05/08  19:36:58  thoth
// New pointset concatenation capability.
//
// Revision 1.28  1994/01/31  16:39:12  thoth
// We now document internal errors when they occur.
//
// Revision 1.27  1993/09/15  12:34:20  thoth
// Pointset behavior controls have moved to IA::
//
// Revision 1.26  93/07/15  11:35:25  thoth
// Add support for iterator virtual method.
//
// Revision 1.25  93/05/28  15:05:31  thoth
// removed dependency on with-ia-pointset*
//
// Revision 1.24  93/05/26  16:57:51  thoth
// Copyright Notices
//
// Revision 1.23  93/05/19  14:45:45  thoth
// LatticeRelation is now in IA::
//
// Revision 1.22  93/04/29  12:52:59  thoth
// Mondo PointSets are now templatized.
//
// Revision 1.21  93/04/19  23:27:48  thoth
// Convert BaseIPS to IA_BasePS<IA_IntPoint>
//
// Revision 1.20  93/04/17  15:19:55  thoth
// IA_IntPoint upgrades (dim, inf, sup)
//
// Revision 1.19  93/04/16  15:50:25  thoth
// use IA_IntPoint instead of IntPoint.
//
// Revision 1.18  93/02/12  16:28:02  thoth
// more IA_ prefixes.
//
// Revision 1.17  93/01/20  11:38:30  thoth
// Yoder hash code is now cached.
//
// Revision 1.16  92/12/16  14:48:24  thoth
// conversion to IA_ mostly complete
//
// Revision 1.15  92/12/07  12:05:13  thoth
// new IntPoint index(unsigned) operation for use with "other" iterators.
//
// Revision 1.14  92/11/15  15:58:29  thoth
// expect a slight performance increase with preallocation of SetStructure.
//
// Revision 1.13  92/11/11  12:12:00  thoth
// added another restriction utility.
//
// Revision 1.12  92/11/04  12:02:14  thoth
// new image extension support routines.
//
// Revision 1.11  92/10/25  20:54:08  thoth
// changed argument passing on set restriction routines.
//
// Revision 1.10  92/10/22  15:13:05  thoth
// pointset restriction utilities.
//
// Revision 1.9  92/09/30  10:39:31  thoth
// White and Black holes are now semi-public classes, unfortunately.
// type() system now based on address of static data member.
// WhiteHole is now a family of pointsets.
// contains now accepts const Point<>&.
// infimum & supremum virtuals now inf & sup.
//
// Revision 1.8  92/09/20  17:37:46  thoth
// fixed spelling error
//
// Revision 1.7  92/09/20  14:07:37  thoth
// new infimum and supremum methods for point sets.
// new instance of the "comp undefined" bug.
//
// Revision 1.6  92/09/14  21:53:35  thoth
// Fixed silly bug in comparison routines.
//
// Revision 1.5  92/09/03  13:36:21  thoth
// hash_self now deals with unsigneds
//
// Revision 1.4  92/08/26  13:52:56  thoth
// added some comments, hopefully things are a little clearer now.
// meaningful exception types
// sped up index, contains, empty.
// removed old min/max cruft.
// improved the compare operation.
//
// Revision 1.3  92/08/25  15:32:44  thoth
// new offsetted virtual functions for set translation
// set difference is operator/, not -
// lattice relationship is determinable on Yoders using compare() friend
//
// Revision 1.2  92/08/24  10:37:47  thoth
// *** empty log message ***
//
// Revision 1.1  92/08/23  13:30:17  thoth
// Initial revision
//
//

#include <stdlib.h>

#include "ia.h"
#include "YoderIPS.h"
#include "MondoPS.h" // for the declaration of class _WhiteHole
#include "SetStructure.h"
#include "YIPSIter.h"

#ifdef IA_PRII
#pragma implementation
#endif

char IA_YoderIPS::type_;

// construct a Yoder from a Boxy point set
IA_YoderIPS::IA_YoderIPS(const IA_BoxyIPS& bps)
: IA_BasePS<IA_Point<int> >(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 = IA_Set<IA_Point<int> >(bps.shadow());
    } else {
	this->slices[0].shadow = IA_WhiteHole(0);
    }
    compute_hash_cache();
}



// 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
IA_YoderIPS::IA_YoderIPS(const IA_Point<int> *aip, unsigned len, unsigned offset)
: IA_BasePS<IA_Point<int> >( (len>0) ? aip[0].dim()-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;
	compute_hash_cache();
	return;
    }

    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 = IA_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 = IA_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 = IA_WhiteHole(0);
	    nslices++;
	    if (i+1<len) {
		slices[nslices].last = aip[i+1][offset] - 1;
		slices[nslices].shadow = IA_BlackHole(0);
		nslices++;
	    }
	    i++;
	}
	this->compute_count_last();
	this->compute_hash_cache();
    }
    // cout << "done\n" << flush;
}



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



IA_YoderIPS::IA_YoderIPS(const IA_YoderIPS& ips)
:IA_BasePS<IA_Point<int> >(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;
    }
    this->hash_cache = ips.hash_cache;
}

IA_YoderIPS::IA_YoderIPS(int b1, int b2, const IA_Set<IA_Point<int> > &ps)
:IA_BasePS<IA_Point<int> >(ps.dim()+1)
{
    if (b2<b1) {
	int temp = b2;
	b2 = b1;
	b1 = temp;
    }

    this->lastbefore = b1-1;

    this->nslices = 1;
    this->slices = new interval[this->nslices];

    this->slices[0].last = b2;
    this->slices[0].shadow = ps;

    // Don't need to compress duplicates.
    compute_count_last(); // Do need this.
    compute_hash_cache(); // Also need this.
}

IA_YoderIPS& IA_YoderIPS::operator=(const IA_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;

    compute_hash_cache();
    return *this;
}


//
//
//


int IA_YoderIPS:: equal(IA_BasePS<IA_Point<int> >* ips) const
{
    return ips->type() == type() &&
	*this == *(IA_YoderIPS*)ips;
}

unsigned IA_YoderIPS:: hash_self(unsigned modulus) const
{
    return hash_cache%modulus;
}

int IA_YoderIPS::operator==(const IA_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;
}

//
//


// compute the index of the cylinder that contains the coord
unsigned IA_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 IA_YoderIPS::contains(const IA_Point<int> &ip) const
{
    unsigned	temp;
    temp = cylinder_index(ip[0]);

    return (temp != ~0) &&
	this->slices[temp].shadow.contains(cdr(ip));
}

unsigned IA_YoderIPS::index(const IA_Point<int> &ip) const
{
    unsigned i = cylinder_index(ip[0]);
    if (i==~0) {
	if (IA::throw_on_index_uncontained)
	    ia_throw(IA::PSET_INDEX_UNCONTAINED, __FILE__,__LINE__);
	return IA::index_of_uncontained;
    }

    unsigned before = i ? slices[i-1].count_last : 0;
    unsigned within = slices[i].shadow.card()
	* (ip[0] - (1+(i ? slices[i-1].last : lastbefore)));
    // The next statement will throw if the point is not contained.
    // This is exactly as it should be.

#ifdef IA_NO_TEMPS_IN_CONDITIONAL_EXPRS
    unsigned recurse;
    if (dimen>1)
        recurse = slices[i].shadow.index(cdr(ip));
    else
        recurse = 0;
#else
    unsigned recurse = (dimen>1) ? slices[i].shadow.index(cdr(ip)) : 0;
#endif

    return before + within + recurse;
}

IA_Point<int> IA_YoderIPS::index(unsigned idx) const
{
    unsigned bottom = 0;
    unsigned top = nslices-1;

    if (idx>=slices[top].count_last) {
	if (IA::throw_on_index_uncontained)
	    ia_throw(IA::PSET_INDEX_UNCONTAINED, __FILE__,__LINE__);
	// the index was outside the card
	return IA_Point<int>();
    }

    unsigned middle;

    while (bottom<top) {
	middle = (bottom+top)/2;
	// cout << bottom << ".." << top << "["<<slices[middle].count_last<<"\n";
	if (idx<slices[middle].count_last) {
	    top = middle;
	    while (top>bottom && slices[top].shadow.empty())
		top--;
	} else {
	    bottom = middle+1;
	    while (bottom < top && slices[bottom].shadow.empty())
		bottom++;
	}
    }

    idx -= (bottom>0) ? slices[bottom-1].count_last : 0;

    unsigned scard = slices[bottom].shadow.card();

    int	car = idx/scard + last_before(bottom)+1;
    unsigned frag = idx%scard;
    // cout << idx<<","<<bottom<<","<<scard <<","<<car<<","<<frag<<endl;
    return concat(car, slices[bottom].shadow.index(frag));
}

//
//

// lexically minimum point in the pointset
IA_Point<int> IA_YoderIPS::min() const
{
    if (this->nslices<1) {
	ia_throw(IA::PSET_INDEX_UNCONTAINED, __FILE__, __LINE__);
	return IA_Point<int>();
    }
    if (this->dimen>1)
	return concat(this->lastbefore+1 , this->slices[0].shadow.min());
    else
	return IA_Point<int>(this->lastbefore+1);
}

// the lexically maxmimum point in the pointset
IA_Point<int> IA_YoderIPS::max() const
{
    if (this->nslices<1) {
	ia_throw(IA::PSET_INDEX_UNCONTAINED, __FILE__, __LINE__);
	return IA_Point<int>();
    }
    if (this->dimen>1)
	return concat(this->slices[this->nslices -1].last,
		      this->slices[this->nslices -1].shadow.max());
    else
	return IA_Point<int>(this->slices[this->nslices -1].last);
}

// the infimum of a pointset, the coordinate-by-coordinate minimum
IA_Point<int> IA_YoderIPS::inf() const
{
    if (this->nslices<1) {
	ia_throw(IA::PSET_INDEX_UNCONTAINED, __FILE__, __LINE__);
	return IA_Point<int>();
    }

    if (dimen <= 1)
	return lastbefore+1;
    else {
	IA_Point<int>	temp(slices[0].shadow.inf());
	for (unsigned i=1; i<nslices; i++)
	    if (!slices[i].shadow.empty())
		temp = ::inf(temp, slices[i].shadow.inf());
	return concat(lastbefore+1, temp);
    }
}

// the supremum of a pointset, the coordinate-by-coordinate maximum
IA_Point<int> IA_YoderIPS::sup() const
{
    if (this->nslices<1) {
	ia_throw(IA::PSET_INDEX_UNCONTAINED, __FILE__, __LINE__);
	return IA_Point<int>();
    }

    if (dimen <= 1)
	return slices[nslices-1].last;
    else {
	IA_Point<int>	temp(slices[0].shadow.sup());
	for (unsigned i=1; i<nslices; i++) {
	    if (!slices[i].shadow.empty())
		temp = ::sup(temp, slices[i].shadow.sup());
	}
	return concat(slices[nslices-1].last, temp);
    }
}

// is the IA_YoderIPS empty?
int IA_YoderIPS::empty() const
{
    // consider the canonical Yoder which can't have empty pointsets
    // at the beginning or end of the cylinder array
    return this->nslices < 1;
}

int IA_YoderIPS::isboxy() const
{
    // the canonical Yoder with more than one cylinder would not be boxy
    if (this->nslices>1)
	return 0;

    // an empty Yoder is boxy
    if (this->nslices<1)
	return 1;

    // we only have one cylinder.  It must be boxy
    if  (this->slices[0].shadow.type() == IA_BoxyIPS::s_type() ||
	 this->slices[0].shadow.type() == IA_WhiteHole_<IA_Point<int> >::s_type()) {
	// white holes are boxy
	return 1;
    } else {
	// A black hole can't occur (canonical form) and
	// if the shadow is a Yoder and boxy, then IntPointSet is
	// not doing its job.
	return 0;
    }
}

IA_BasePSIter<IA_Point<int> > * IA_YoderIPS::iterator() const
{
    // cast away const
    return new IA_YoderIPSIter((IA_YoderIPS*)this);
}

//
//

// Part of canonicalization that compresses adjacent shadow cylinders
// that have the same shadow into one larger shadow cylinder.
// It also eliminates empty pointsets at the beginning and end.
void IA_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;
    // cout << "squashed " << high << "empty cylinders\n";

    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;
}

// Part of canonicalization that computes the count_last field of each
// shadow cylinder
void IA_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 IA_YoderIPS::compute_hash_cache()
{
    hash_cache = this->dimen;
    hash_cache += this->lastbefore;
    for (unsigned i=0; i<this->nslices; i++) {
	hash_cache += this->slices[i].last;
	hash_cache += this->slices[i].shadow.hash_self(~0);
    }
}

// complete canonicalization of a Yoder IPS.  This must be performed
// before a Yoder is handed to the user.
void IA_YoderIPS::canonicalize()
{
  compress_duplicates();
  compute_count_last();
  compute_hash_cache();
}

// Copy a block of intervals from one location to another
void IA_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;
    }
}

//
//

static void squirgle(IA_YoderIPS::interval* ivl, IA_Point<int> p)
{
    ivl->last += p[0];
    ivl->shadow += cdr(p);
}

// this constructs and returns a copy of the Yoder translated
// by `ip'.
IA_BasePS<IA_Point<int> > * IA_YoderIPS::offsetted(const IA_Point<int>&ip) const
{
    // this could be more efficient
    IA_YoderIPS	*rval = new IA_YoderIPS(*this);
    rval->lastbefore += ip[0];
    for (unsigned i=0; i<rval->nslices; i++) {
#if 0
	// koddam "comp undefined" bug
	squirgle(&rval->slices[i], ip);
#else
	rval->slices[i].last += ip[0];
	rval->slices[i].shadow += cdr(ip);
#endif
    }
    return rval;
}

//
//
//


// This static function unions two non-overlapping Yoder pointsets into
// dest.  It requires that first.slices[first.nslices-1].last <=
// second.lastbefore.
void IA_YoderIPS::union_nonoverlapping(
    const IA_YoderIPS &first, const IA_YoderIPS &second, IA_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 = IA_BlackHole(second.dimen -1);
	dest.nslices++;
    }
    
    interval_BlT(second.slices, dest.slices+dest.nslices, second.nslices);
    
    dest.nslices += second.nslices;
}

// Given two pointsets that don't begin at the same first coord,
// this static function copies the beginning part that only one pointset
// covers into dest.  The pointset with the "leader" portion must be
// `first' and `f_idx' is an index into the cylinder array that will be
// adjusted to point to the first cylinder of `first' that overlaps with
// `second'.
// It requires (first.lastbefore < second.lastbefore)
// dest.lastbefore is set to first.lastbefore
// `dest' must have a large enough slices array allocated before the call.
// normal usage has *f_idx==0 and dest.nslices==0
void IA_YoderIPS:: copy_nonoverlapping_leader(
    const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
    IA_YoderIPS &dest)
{
    // cout << "copying non-overlapping leader from " << first.lastbefore <<
    // " until " << second.lastbefore << "\n";
    dest.lastbefore = first.lastbefore;
    while (first.slices[*f_idx].last <= second.lastbefore) {
	dest.slices[dest.nslices] = first.slices[*f_idx];
	dest.nslices++;
	(*f_idx)++;
    }
    // cout << "ate " << *f_idx << " slices";

    // the simple *f_idx==0 case caused me the MOST difficulty
    if ( *f_idx==0 || 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++;
	// cout << " and filled a hole";
    }
    // cout << '\n';
}

// This function takes the cylinders from source.slices[*s_idx] to the
// end of the source's slices array and copies them onto the end of dest.
// *s_idx is set to source.nslices by this operation.
// This operation is usually performed after a call to
// merge_overlapping_cylinders (below).
void IA_YoderIPS:: copy_nonoverlapping_trailer(
    const IA_YoderIPS &source, unsigned *s_idx, IA_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++;
    }
}

// Given two pointsets that don't begin at the same first coord,
// this static function "burns" the nonoverlapping beginning.
// `first' must contain the nonoverlapping leader portion and f_idx
// is incremented to the first cylinder that overlaps with second.
// It requires (first.lastbefore < second.lastbefore)
// dest.lastbefore is set to second.lastbefore
// normal usage has *f_idx==0 and dest.nslices==0
void IA_YoderIPS:: burn_nonoverlapping_leader(
    const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
    IA_YoderIPS &dest)
{
    dest.lastbefore = second.lastbefore;
    while (first.slices[*f_idx].last <= second.lastbefore) {
	(*f_idx)++;
    }
}

// Given two pointsets that have overlapping portions, this function
// "merges" them into dest. *f_idx is the index of a cylinder of `first'
// that overlaps with the (*s_idx)th cylinder of `second'.  The new
// slices of dest are formed by taking the overlapping portions of the
// slices of first and second and applying `f' to their shadows to
// form the shadow of the new cylinder.  *f_idx and *s_idx are incremented
// in a sort of leapfrog until one of them reaches the end of their
// respective cylinder arrays.
// dest must have a large enough `slices' array allocated before the call.
// The new cylinders are appended to the end of any cylinders that have
// been placed in dest already (dest.nslices).
void IA_YoderIPS:: merge_overlapping_cylinders
  (const IA_YoderIPS &first, unsigned *f_idx,
   const IA_YoderIPS &second, unsigned *s_idx,
   IA_YoderIPS &dest, IA_Set<IA_Point<int> >(*f)(const IA_Set<IA_Point<int> >&,const IA_Set<IA_Point<int> >&))
{
  while ( *f_idx < first.nslices && *s_idx < second.nslices ) {
      // cout << "merging shadows... lasts:" << first.slices[*f_idx].last <<
      // ' ' << second.slices[*s_idx].last << '\n';
    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 IA_Set<IA_Point<int> > tmp_or(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs)
{
  return lhs | rhs;
}

// set union
IA_YoderIPS IA_YoderIPS::operator|(const IA_YoderIPS &that) const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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 IA_Set<IA_Point<int> > tmp_and(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs)
{
  return lhs & rhs;
}

// set intersection
IA_YoderIPS IA_YoderIPS::operator&(const IA_YoderIPS &that) const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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);

      // burn the nonoverlapping trailers by ignoring them
    }

    rval.canonicalize();

    return rval;
}



// set restriction stuff, dangerous

void IA_YoderIPS:: burn_nonoverlapping_leader(
    const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
    IA_YoderIPS &dest, IA_SetStructure *ss_result, IA_SetStructure sub)
{
    unsigned	count=0;
    dest.lastbefore = second.lastbefore;
    while (first.slices[*f_idx].last <= second.lastbefore) {
	count += (first.slices[*f_idx].last - first.last_before(*f_idx)) *
	    (first.slices[*f_idx].shadow.card());
	(*f_idx)++;
    }
    if (*f_idx==0 || first.slices[*f_idx-1].last < second.lastbefore)
	count += (second.lastbefore - first.last_before(*f_idx)) *
	    (first.slices[*f_idx].shadow.card());
    ss_result->add_interval(count, sub);
}


void IA_YoderIPS:: merge_overlapping_cylinders
  (const IA_YoderIPS &first, unsigned *f_idx,
   const IA_YoderIPS &second, unsigned *s_idx,
   IA_YoderIPS &dest, IA_SetStructure * ss_result,
   IA_Set<IA_Point<int> >(*f)(const IA_Set<IA_Point<int> >&,const IA_Set<IA_Point<int> >&, IA_SetStructure *)
   )
{
    while ( *f_idx < first.nslices && *s_idx < second.nslices ) {
	// cout << "merging shadows... lasts:" << first.slices[*f_idx].last <<
	// ' ' << second.slices[*s_idx].last << '\n';
	struct interval	&ivl=dest.slices[dest.nslices];
	IA_SetStructure	ss;
	ivl.shadow = f(first.slices[*f_idx].shadow,
		       second.slices[*s_idx].shadow, &ss);
	
	if (first.slices[*f_idx].last > second.slices[*s_idx].last) {
	    ivl.last = second.slices[*s_idx].last;
	    (*s_idx)++;
	} else if (first.slices[*f_idx].last < second.slices[*s_idx].last) {
	    ivl.last = first.slices[*f_idx].last;
	    (*f_idx)++;
	} else { /* == */
	    ivl.last = second.slices[*s_idx].last;
	    (*s_idx)++; (*f_idx)++;
	}
	
	ss_result->add_interval(ivl.last - dest.last_before(dest.nslices), ss);
	
	dest.nslices++;
    }
}

void IA_YoderIPS:: burn_nonoverlapping_trailer
(const IA_YoderIPS &first, unsigned *f_idx,
 const IA_YoderIPS &dest, IA_SetStructure *ss_result, IA_SetStructure sub)
{
    if (*f_idx>=first.nslices)
	return;

    unsigned count=0;
    count += (first.slices[*f_idx].last - dest.slices[dest.nslices-1].last) *
	first.slices[*f_idx].shadow.card();
    (*f_idx)++;
    while (*f_idx<first.nslices) {
	count += (first.slices[*f_idx].last - first.last_before(*f_idx)) *
	    first.slices[*f_idx].shadow.card();
	(*f_idx)++;
    }

    ss_result->add_interval(count, sub);
}


static IA_Set<IA_Point<int> > tmp_and1(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs,
			    IA_SetStructure *result)
{
    return intersect_with_structure(lhs, rhs, result);
}


IA_YoderIPS
IA_YoderIPS::intersect_with_structure (const IA_YoderIPS &that, IA_SetStructure *result)
    const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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) {
	result->add_interval(this->card(), IA_SetStructure::FIRST_ONLY);
	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,
				   result, IA_SetStructure::FIRST_ONLY);
      } 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,
				   result, tmp_and1);

      burn_nonoverlapping_trailer(*this, &lidx, rval,
				  result, IA_SetStructure::FIRST_ONLY);
    }

    rval.canonicalize();

    return rval;
}

static IA_Set<IA_Point<int> > tmp_and2(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs,
			    IA_SetStructure *result)
{
    return intersect_with_dualstruct(lhs, rhs, result);
}

IA_YoderIPS
IA_YoderIPS::intersect_with_dualstruct (const IA_YoderIPS &that, IA_SetStructure *result)
    const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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
    result->ensure_space( this->nslices+that.nslices+1 );

    if (this->slices[this->nslices-1].last <= that.lastbefore) {
	result->add_interval(this->card(), IA_SetStructure::FIRST_ONLY);
	result->add_interval(this->card(), IA_SetStructure::SECOND_ONLY);
    } else if ( that.slices[that.nslices-1].last <= this->lastbefore) {
	result->add_interval(this->card(), IA_SetStructure::SECOND_ONLY);
	result->add_interval(this->card(), IA_SetStructure::FIRST_ONLY);
    } else {
      unsigned lidx=0, ridx=0;
      
      ////////////////
      // intersect the two Yoder PointSets
	  
      if (this->lastbefore < that.lastbefore) {
	burn_nonoverlapping_leader(*this, &lidx, that, rval,
				   result, IA_SetStructure::FIRST_ONLY);
      } else if (this->lastbefore > that.lastbefore) {
	burn_nonoverlapping_leader(that, &ridx, *this, rval,
				   result, IA_SetStructure::SECOND_ONLY);
      } else /* == */
	rval.lastbefore = that.lastbefore;
      
      merge_overlapping_cylinders (*this,&lidx, that,&ridx, rval,
				   result, tmp_and2);

      burn_nonoverlapping_trailer(*this, &lidx, rval,
				  result, IA_SetStructure::FIRST_ONLY);
      burn_nonoverlapping_trailer(that, &ridx, rval,
				  result, IA_SetStructure::SECOND_ONLY);
    }

    rval.canonicalize();

    return rval;
}

//
//
//

void IA_YoderIPS:: copy_nonoverlapping_leader(
    const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
    IA_YoderIPS &dest, IA_SetStructure *result, IA_SetStructure sub)
{
    unsigned	count=0;
    // cout << "copying non-overlapping leader from " << first.lastbefore <<
    // " until " << second.lastbefore << "\n";
    dest.lastbefore = first.lastbefore;
    while (first.slices[*f_idx].last <= second.lastbefore) {
	dest.slices[dest.nslices] = first.slices[*f_idx];

	count += (first.last_before(*f_idx+1) - first.last_before(*f_idx)) *
	    first.slices[*f_idx].shadow.card();

	dest.nslices++;
	(*f_idx)++;
    }
    // cout << "ate " << *f_idx << " slices";

    // the simple *f_idx==0 case caused me the MOST difficulty
    if ( *f_idx==0 || 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;

	count += (dest.last_before(dest.nslices+1) - dest.last_before(dest.nslices)) * dest.slices[dest.nslices].shadow.card();

	dest.nslices++;
	// cout << " and filled a hole";
    }
    // cout << '\n';

    result->add_interval(count, sub);
}



void IA_YoderIPS:: copy_nonoverlapping_trailer(
    const IA_YoderIPS &source, unsigned *s_idx, IA_YoderIPS &dest,
    IA_SetStructure *result, IA_SetStructure sub)
{
    unsigned	count=0;

    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;

	count += (dest.last_before(dest.nslices+1) - dest.last_before(dest.nslices)) * dest.slices[dest.nslices].shadow.card();

	(*s_idx)++;
	dest.nslices++;
    }

    result->add_interval(count, sub);
}

static IA_Set<IA_Point<int> > tmp_or(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs,
			    IA_SetStructure *result)
{
    return union_with_structure(lhs, rhs, result);
}

IA_YoderIPS
IA_YoderIPS::union_with_structure (const IA_YoderIPS &that, IA_SetStructure *result)
    const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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) {
	union_nonoverlapping(*this, that, rval);
	result->add_interval(this->card(), IA_SetStructure::FIRST_ONLY);
	result->add_interval(that.card(), IA_SetStructure::SECOND_ONLY);
    } else if ( that.slices[that.nslices-1].last <= this->lastbefore) {
	union_nonoverlapping(that, *this, rval);
	result->add_interval(that.card(), IA_SetStructure::SECOND_ONLY);
	result->add_interval(this->card(), IA_SetStructure::FIRST_ONLY);
    } else {
      unsigned lidx=0, ridx=0;
      
      ////////////////
      // union the two Yoder PointSets
	  
      if (this->lastbefore < that.lastbefore) {
	copy_nonoverlapping_leader(*this, &lidx, that, rval,
				   result, IA_SetStructure::FIRST_ONLY);
      } else if (this->lastbefore > that.lastbefore) {
	copy_nonoverlapping_leader(that, &ridx, *this, rval,
				   result, IA_SetStructure::SECOND_ONLY);
      } else /* == */
	rval.lastbefore = that.lastbefore;
      
      merge_overlapping_cylinders (*this,&lidx, that,&ridx, rval,
				   result, tmp_or);

      copy_nonoverlapping_trailer(*this, &lidx, rval,
				  result, IA_SetStructure::FIRST_ONLY);
      copy_nonoverlapping_trailer(that, &ridx, rval,
				  result, IA_SetStructure::SECOND_ONLY);
    }

    rval.canonicalize();

    return rval;
}

//

static IA_Set<IA_Point<int> > tmp_xor(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs)
{
  return lhs ^ rhs;
}

// set symmetric difference
IA_YoderIPS IA_YoderIPS::operator^(const IA_YoderIPS &that) const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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
      //cout << "lastbefores : " << this->lastbefore << ' ' <<
      // that.lastbefore << '\n';
      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 IA_Set<IA_Point<int> > tmp_minus(const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs)
{
  return lhs / rhs;
}

// set asymmetric difference
IA_YoderIPS IA_YoderIPS::operator/(const IA_YoderIPS &that) const
{
    IA_YoderIPS	rval(this->dimen);

    if (this->dimen != that.dimen) {
	ia_throw(IA::PSET_DIMENSION_MISMATCH, __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;
}

//
//
//

// This function can return
// NO_REL, P_SUBSET, P_SUPERSET, or EQUAL
// It will abort if internal inconsistencies would cause it
// to return otherwise.
IA::LatticeRelation
compare(const IA_YoderIPS &lhs, const IA_YoderIPS &rhs)
{
    // the arguments must be canonical

    IA::LatticeRelation	rval=IA::EQUAL, temp;
    unsigned	lidx=0, ridx=0;

    if (lhs.lastbefore<rhs.lastbefore) {
	rval = IA::P_SUPERSET;
	while (lhs.slices[lidx].last <= rhs.lastbefore)
	    lidx++;
    } else if (lhs.lastbefore>rhs.lastbefore) {
	rval = IA::P_SUBSET;
	while (rhs.slices[ridx].last <= lhs.lastbefore)
	    ridx++;
    }

    while (lidx<lhs.nslices && ridx<rhs.nslices) {
	temp = compare(lhs.slices[lidx].shadow, rhs.slices[ridx].shadow);
	if (rval==IA::P_SUBSET) {
	    if (temp==IA::P_SUPERSET ||
		temp==IA::NO_REL)
		return IA::NO_REL;
	} else if (rval==IA::EQUAL) {
	    if (temp==IA::NO_REL)
		return temp;
	    else if (temp==IA::P_SUBSET ||
		     temp==IA::EQUAL ||
		     temp==IA::P_SUPERSET)
		rval=temp;
	    else {
		cout << "weird comparison result: " << rval;
		lhs.slices[lidx].shadow.output(cout);
		cout << " with\n";
		rhs.slices[ridx].shadow.output(cout);
		cout << ".\n";

		IA::internal_error(__FILE__,__LINE__);
	    }
	} else if (rval==IA::P_SUPERSET) {
	    if (temp==IA::P_SUBSET ||
		temp==IA::NO_REL)
		return IA::NO_REL;
	} else {
	    // rval should have been completely screened!
	    // this is impossible
	    IA::internal_error(__FILE__,__LINE__);
	}

	if (lhs.slices[lidx].last > rhs.slices[ridx].last)
	    ridx++;
	else if (lhs.slices[lidx].last < rhs.slices[ridx].last)
	    lidx++;
	else { /* == */
	    ridx++;
	    lidx++;
	}	    
    }

    switch (rval) {
    case IA::P_SUBSET:
	if (lidx < lhs.nslices)
	    return IA::NO_REL;
	else
	    return rval;
	break;
    case IA::EQUAL:
	if (lidx < lhs.nslices)
	    return IA::P_SUPERSET;
	else if (ridx < rhs.nslices)
	    return IA::P_SUBSET;
	else
	    return rval;
	// NOTREACHED
	break;
    case IA::P_SUPERSET:
	if (ridx < rhs.nslices)
	    return IA::NO_REL;
	else
	    return rval;
	break;
    default:
	IA::internal_error(__FILE__,__LINE__);
	break;
    }
}

//
//

void IA_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.33
log
@commented rscid[] line
@
text
@d8 2
a9 1
//static char copyright[] = "Copyright 1993, Center for Computer Vision and Visualization,\nUniversity of Florida.  All rights reserved.\n";
d11 2
a12 1
//static char rcsid[] = "$Id: YoderIPS.c,v 1.32 1994/09/13 19:12:56 ljr Exp fjsoria $";
d16 3
@


1.32
log
@Added workarounds for conditional expressions that create temporaries.
@
text
@d8 1
a8 1
static char copyright[] = "Copyright 1993, Center for Computer Vision and Visualization,\nUniversity of Florida.  All rights reserved.\n";
d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.31 1994/08/26 15:37:08 thoth Exp ljr $";
d14 3
@


1.31
log
@DOS-inspired name rework (internal files)
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.30 1994/07/25 16:58:52 thoth Exp thoth $";
d12 1
a12 1
// 
d14 3
d31 1
a31 1
// 
d34 1
a34 1
// 
d37 1
a37 1
// 
d40 1
a40 1
// 
d43 1
a43 1
// 
d46 1
a46 1
// 
d49 1
a49 1
// 
d52 1
a52 1
// 
d55 1
a55 1
// 
d58 1
a58 1
// 
d61 1
a61 1
// 
d64 1
a64 1
// 
d67 1
a67 1
// 
d70 1
a70 1
// 
d73 1
a73 1
// 
d76 1
a76 1
// 
d79 1
a79 1
// 
d86 1
a86 1
// 
d89 1
a89 1
// 
d93 1
a93 1
// 
d96 1
a96 1
// 
d99 1
a99 1
// 
d106 1
a106 1
// 
d111 1
a111 1
// 
d114 1
a114 1
// 
d117 2
a118 2
// 
// 
d178 1
a178 1
    
d378 8
d387 1
@


1.30
log
@\Name sanitization
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.29 1994/05/08 19:36:58 thoth Exp thoth $";
d14 3
d123 1
a123 1
#include "YoderIPSIter.h"
@


1.29
log
@New pointset concatenation capability.
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.28 1994/01/31 16:39:12 thoth Exp thoth $";
d14 3
d130 1
a130 1
: IA_BasePS<IA_IntPoint>(bps.dim())
d138 1
a138 1
	this->slices[0].shadow = IA_IntPointSet(bps.shadow());
d152 2
a153 2
IA_YoderIPS::IA_YoderIPS(const IA_IntPoint *aip, unsigned len, unsigned offset)
: IA_BasePS<IA_IntPoint>( (len>0) ? aip[0].dim()-offset : 0 )
d227 1
a227 1
:IA_BasePS<IA_IntPoint>(ips.dimen)
d246 1
a246 1
:IA_BasePS<IA_IntPoint>(ps.dim()+1)
d293 1
a293 1
int IA_YoderIPS:: equal(IA_BasePS<IA_IntPoint>* ips) const
d349 1
a349 1
int IA_YoderIPS::contains(const IA_IntPoint &ip) const
d358 1
a358 1
unsigned IA_YoderIPS::index(const IA_IntPoint &ip) const
d377 1
a377 1
IA_IntPoint IA_YoderIPS::index(unsigned idx) const
d386 1
a386 1
	return IA_IntPoint();
d419 1
a419 1
IA_IntPoint IA_YoderIPS::min() const
d423 1
a423 1
	return IA_IntPoint();
d428 1
a428 1
	return IA_IntPoint(this->lastbefore+1);
d432 1
a432 1
IA_IntPoint IA_YoderIPS::max() const
d436 1
a436 1
	return IA_IntPoint();
d442 1
a442 1
	return IA_IntPoint(this->slices[this->nslices -1].last);
d446 1
a446 1
IA_IntPoint IA_YoderIPS::inf() const
d450 1
a450 1
	return IA_IntPoint();
d456 1
a456 1
	IA_IntPoint	temp(slices[0].shadow.inf());
d465 1
a465 1
IA_IntPoint IA_YoderIPS::sup() const
d469 1
a469 1
	return IA_IntPoint();
d475 1
a475 1
	IA_IntPoint	temp(slices[0].shadow.sup());
d504 1
a504 1
	 this->slices[0].shadow.type() == IA_WhiteHole_<IA_IntPoint>::s_type()) {
d515 1
a515 1
IA_BasePSIter<IA_IntPoint> * IA_YoderIPS::iterator() const
d611 1
a611 1
static void squirgle(IA_YoderIPS::interval* ivl, IA_IntPoint p)
d619 1
a619 1
IA_BasePS<IA_IntPoint> * IA_YoderIPS::offsetted(const IA_IntPoint&ip) const
d748 1
a748 1
   IA_YoderIPS &dest, IA_IntPointSet(*f)(const IA_IntPointSet&,const IA_IntPointSet&))
d776 1
a776 1
static IA_IntPointSet tmp_or(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs)
d828 1
a828 1
static IA_IntPointSet tmp_and(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs)
d899 1
a899 1
   IA_IntPointSet(*f)(const IA_IntPointSet&,const IA_IntPointSet&, IA_SetStructure *)
d948 1
a948 1
static IA_IntPointSet tmp_and1(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs,
d1000 1
a1000 1
static IA_IntPointSet tmp_and2(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs,
d1118 1
a1118 1
static IA_IntPointSet tmp_or(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs,
d1178 1
a1178 1
static IA_IntPointSet tmp_xor(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs)
d1231 1
a1231 1
static IA_IntPointSet tmp_minus(const IA_IntPointSet &lhs, const IA_IntPointSet &rhs)
@


1.28
log
@We now document internal errors when they occur.
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.27 1993/09/15 12:34:20 thoth Exp thoth $";
d14 3
d242 10
d253 10
@


1.27
log
@Pointset behavior controls have moved to IA::
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.26 93/07/15 11:35:25 thoth Exp Locker: thoth $";
d13 4
a16 1
// $Log:	YoderIPS.c,v $
d1296 1
a1296 1
		abort(); // internal error
d1305 1
a1305 1
	    abort(); // internal error
d1341 1
a1341 1
	abort(); // internal error
@


1.26
log
@Add support for iterator virtual method.
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.25 93/05/28 15:05:31 thoth Exp Locker: thoth $";
d14 3
d333 1
a333 1
	if (IA_IntPointSet::throw_on_index_uncontained)
d335 1
a335 1
	return IA_IntPointSet::index_of_uncontained;
d354 1
a354 1
	if (IA_IntPointSet::throw_on_index_uncontained)
@


1.25
log
@removed dependency on with-ia-pointset*
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.24 93/05/26 16:57:51 thoth Exp Locker: thoth $";
d14 3
d108 1
d481 6
@


1.24
log
@Copyright Notices
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.23 93/05/19 14:45:45 thoth Exp Locker: thoth $";
d14 3
d110 1
a110 1
#include "with-ia-pointset-P.h"
a111 2
char YoderIPS::type_;

d113 1
a113 1
YoderIPS::IA_YoderIPS(const BoxyIPS& bps)
d122 1
a122 1
	this->slices[0].shadow = IntPointSet(bps.shadow());
d136 1
a136 1
YoderIPS::IA_YoderIPS(const IA_IntPoint *aip, unsigned len, unsigned offset)
d166 1
a166 1
	    slices[nslices].shadow = YoderIPS(aip+j, i-j, offset+1);
d202 1
a202 1
YoderIPS::~IA_YoderIPS()
d210 1
a210 1
YoderIPS::IA_YoderIPS(const YoderIPS& ips)
d231 1
a231 1
YoderIPS& YoderIPS::operator=(const YoderIPS &ips)
d257 1
a257 1
int YoderIPS:: equal(IA_BasePS<IA_IntPoint>* ips) const
d260 1
a260 1
	*this == *(YoderIPS*)ips;
d263 1
a263 1
unsigned YoderIPS:: hash_self(unsigned modulus) const
d268 1
a268 1
int YoderIPS::operator==(const YoderIPS& ips) const
d289 1
a289 1
unsigned YoderIPS::cylinder_index(int coord) const
d313 1
a313 1
int YoderIPS::contains(const IA_IntPoint &ip) const
d322 1
a322 1
unsigned YoderIPS::index(const IA_IntPoint &ip) const
d326 1
a326 1
	if (IntPointSet::throw_on_index_uncontained)
d328 1
a328 1
	return IntPointSet::index_of_uncontained;
d341 1
a341 1
IA_IntPoint YoderIPS::index(unsigned idx) const
d347 1
a347 1
	if (IntPointSet::throw_on_index_uncontained)
d383 1
a383 1
IA_IntPoint YoderIPS::min() const
d396 1
a396 1
IA_IntPoint YoderIPS::max() const
d410 1
a410 1
IA_IntPoint YoderIPS::inf() const
d429 1
a429 1
IA_IntPoint YoderIPS::sup() const
d448 2
a449 2
// is the YoderIPS empty?
int YoderIPS::empty() const
d456 1
a456 1
int YoderIPS::isboxy() const
d467 1
a467 1
    if  (this->slices[0].shadow.type() == BoxyIPS::s_type() ||
d485 1
a485 1
void YoderIPS::compress_duplicates()
d521 1
a521 1
void YoderIPS::compute_count_last()
d538 1
a538 1
void YoderIPS::compute_hash_cache()
d550 1
a550 1
void YoderIPS::canonicalize()
d558 1
a558 1
void YoderIPS::interval_BlT(interval *source, interval*dest, unsigned count)
d569 1
a569 1
static void squirgle(YoderIPS::interval* ivl, IA_IntPoint p)
d577 1
a577 1
IA_BasePS<IA_IntPoint> * YoderIPS::offsetted(const IA_IntPoint&ip) const
d580 1
a580 1
    YoderIPS	*rval = new YoderIPS(*this);
d602 2
a603 2
void YoderIPS::union_nonoverlapping(
    const YoderIPS &first, const YoderIPS &second, YoderIPS &dest)
d633 3
a635 3
void YoderIPS:: copy_nonoverlapping_leader(
    const YoderIPS &first, unsigned *f_idx, const YoderIPS &second,
    YoderIPS &dest)
d663 2
a664 2
void YoderIPS:: copy_nonoverlapping_trailer(
    const YoderIPS &source, unsigned *s_idx, YoderIPS &dest)
d682 3
a684 3
void YoderIPS:: burn_nonoverlapping_leader(
    const YoderIPS &first, unsigned *f_idx, const YoderIPS &second,
    YoderIPS &dest)
d703 4
a706 4
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&))
d734 1
a734 1
static IntPointSet tmp_or(const IntPointSet &lhs, const IntPointSet &rhs)
d740 1
a740 1
YoderIPS YoderIPS::operator|(const YoderIPS &that) const
d742 1
a742 1
    YoderIPS	rval(this->dimen);
d786 1
a786 1
static IntPointSet tmp_and(const IntPointSet &lhs, const IntPointSet &rhs)
d792 1
a792 1
YoderIPS YoderIPS::operator&(const YoderIPS &that) const
d794 1
a794 1
    YoderIPS	rval(this->dimen);
d835 3
a837 3
void YoderIPS:: burn_nonoverlapping_leader(
    const YoderIPS &first, unsigned *f_idx, const YoderIPS &second,
    YoderIPS &dest, SetStructure *ss_result, SetStructure sub)
d853 5
a857 5
void YoderIPS:: merge_overlapping_cylinders
  (const YoderIPS &first, unsigned *f_idx,
   const YoderIPS &second, unsigned *s_idx,
   YoderIPS &dest, SetStructure * ss_result,
   IntPointSet(*f)(const IntPointSet&,const IntPointSet&, SetStructure *)
d864 1
a864 1
	SetStructure	ss;
d885 3
a887 3
void YoderIPS:: burn_nonoverlapping_trailer
(const YoderIPS &first, unsigned *f_idx,
 const YoderIPS &dest, SetStructure *ss_result, SetStructure sub)
d906 2
a907 2
static IntPointSet tmp_and1(const IntPointSet &lhs, const IntPointSet &rhs,
			    SetStructure *result)
d913 2
a914 2
YoderIPS
YoderIPS::intersect_with_structure (const YoderIPS &that, SetStructure *result)
d917 1
a917 1
    YoderIPS	rval(this->dimen);
d930 1
a930 1
	result->add_interval(this->card(), SetStructure::FIRST_ONLY);
d940 1
a940 1
				   result, SetStructure::FIRST_ONLY);
d950 1
a950 1
				  result, SetStructure::FIRST_ONLY);
d958 2
a959 2
static IntPointSet tmp_and2(const IntPointSet &lhs, const IntPointSet &rhs,
			    SetStructure *result)
d964 2
a965 2
YoderIPS
YoderIPS::intersect_with_dualstruct (const YoderIPS &that, SetStructure *result)
d968 1
a968 1
    YoderIPS	rval(this->dimen);
d981 2
a982 2
	result->add_interval(this->card(), SetStructure::FIRST_ONLY);
	result->add_interval(this->card(), SetStructure::SECOND_ONLY);
d984 2
a985 2
	result->add_interval(this->card(), SetStructure::SECOND_ONLY);
	result->add_interval(this->card(), SetStructure::FIRST_ONLY);
d994 1
a994 1
				   result, SetStructure::FIRST_ONLY);
d997 1
a997 1
				   result, SetStructure::SECOND_ONLY);
d1005 1
a1005 1
				  result, SetStructure::FIRST_ONLY);
d1007 1
a1007 1
				  result, SetStructure::SECOND_ONLY);
d1019 3
a1021 3
void YoderIPS:: copy_nonoverlapping_leader(
    const YoderIPS &first, unsigned *f_idx, const YoderIPS &second,
    YoderIPS &dest, SetStructure *result, SetStructure sub)
d1056 3
a1058 3
void YoderIPS:: copy_nonoverlapping_trailer(
    const YoderIPS &source, unsigned *s_idx, YoderIPS &dest,
    SetStructure *result, SetStructure sub)
d1076 2
a1077 2
static IntPointSet tmp_or(const IntPointSet &lhs, const IntPointSet &rhs,
			    SetStructure *result)
d1082 2
a1083 2
YoderIPS
YoderIPS::union_with_structure (const YoderIPS &that, SetStructure *result)
d1086 1
a1086 1
    YoderIPS	rval(this->dimen);
d1099 2
a1100 2
	result->add_interval(this->card(), SetStructure::FIRST_ONLY);
	result->add_interval(that.card(), SetStructure::SECOND_ONLY);
d1103 2
a1104 2
	result->add_interval(that.card(), SetStructure::SECOND_ONLY);
	result->add_interval(this->card(), SetStructure::FIRST_ONLY);
d1113 1
a1113 1
				   result, SetStructure::FIRST_ONLY);
d1116 1
a1116 1
				   result, SetStructure::SECOND_ONLY);
d1124 1
a1124 1
				  result, SetStructure::FIRST_ONLY);
d1126 1
a1126 1
				  result, SetStructure::SECOND_ONLY);
d1136 1
a1136 1
static IntPointSet tmp_xor(const IntPointSet &lhs, const IntPointSet &rhs)
d1142 1
a1142 1
YoderIPS YoderIPS::operator^(const YoderIPS &that) const
d1144 1
a1144 1
    YoderIPS	rval(this->dimen);
d1189 1
a1189 1
static IntPointSet tmp_minus(const IntPointSet &lhs, const IntPointSet &rhs)
d1195 1
a1195 1
YoderIPS YoderIPS::operator/(const YoderIPS &that) const
d1197 1
a1197 1
    YoderIPS	rval(this->dimen);
d1243 1
a1243 1
compare(const YoderIPS &lhs, const YoderIPS &rhs)
d1333 1
a1333 1
void YoderIPS::output(ostream &o, unsigned indent) const
@


1.23
log
@LatticeRelation is now in IA::
@
text
@a1 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.22 93/04/29 12:52:59 thoth Exp Locker: thoth $";
d3 9
d14 3
@


1.22
log
@Mondo PointSets are now templatized.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.21 93/04/19 23:27:48 thoth Exp Locker: thoth $";
d6 3
d1230 1
a1230 1
IntPointSet::LatticeRelation
d1235 1
a1235 1
    IntPointSet::LatticeRelation	rval=IntPointSet::EQUAL, temp;
d1239 1
a1239 1
	rval = IntPointSet::P_SUPERSET;
d1243 1
a1243 1
	rval = IntPointSet::P_SUBSET;
d1250 6
a1255 6
	if (rval==IntPointSet::P_SUBSET) {
	    if (temp==IntPointSet::P_SUPERSET ||
		temp==IntPointSet::NO_REL)
		return IntPointSet::NO_REL;
	} else if (rval==IntPointSet::EQUAL) {
	    if (temp==IntPointSet::NO_REL)
d1257 3
a1259 3
	    else if (temp==IntPointSet::P_SUBSET ||
		     temp==IntPointSet::EQUAL ||
		     temp==IntPointSet::P_SUPERSET)
d1270 4
a1273 4
	} else if (rval==IntPointSet::P_SUPERSET) {
	    if (temp==IntPointSet::P_SUBSET ||
		temp==IntPointSet::NO_REL)
		return IntPointSet::NO_REL;
d1291 1
a1291 1
    case IntPointSet::P_SUBSET:
d1293 1
a1293 1
	    return IntPointSet::NO_REL;
d1297 1
a1297 1
    case IntPointSet::EQUAL:
d1299 1
a1299 1
	    return IntPointSet::P_SUPERSET;
d1301 1
a1301 1
	    return IntPointSet::P_SUBSET;
d1306 1
a1306 1
    case IntPointSet::P_SUPERSET:
d1308 1
a1308 1
	    return IntPointSet::NO_REL;
@


1.21
log
@Convert BaseIPS to IA_BasePS<IA_IntPoint>
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.20 93/04/17 15:19:55 thoth Exp Locker: thoth $";
d6 3
d453 1
a453 1
	 this->slices[0].shadow.type() == _WhiteHole::s_type()) {
@


1.20
log
@IA_IntPoint upgrades (dim, inf, sup)
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.19 93/04/16 15:50:25 thoth Exp Locker: thoth $";
d6 3
d96 1
a96 1
: BaseIPS(bps.dim())
d119 1
a119 1
: BaseIPS( (len>0) ? aip[0].dim()-offset : 0 )
d193 1
a193 1
:BaseIPS(ips.dimen)
d239 1
a239 1
int YoderIPS:: equal(BaseIPS* ips) const
d559 1
a559 1
BaseIPS * YoderIPS::offsetted(const IA_IntPoint&ip) const
@


1.19
log
@use IA_IntPoint instead of IntPoint.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.18 93/02/12 16:28:02 thoth Exp Locker: thoth $";
d6 3
d116 1
a116 1
: BaseIPS( (len>0) ? aip[0].dimensions()-offset : 0 )
d402 1
a402 1
		temp = ::infimum(temp, slices[i].shadow.inf());
d421 1
a421 1
		temp = ::supremum(temp, slices[i].shadow.sup());
@


1.18
log
@more IA_ prefixes.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.17 93/01/20 11:38:30 thoth Exp Locker: thoth $";
d6 3
d112 1
a112 1
YoderIPS::IA_YoderIPS(const IntPoint *aip, unsigned len, unsigned offset)
d289 1
a289 1
int YoderIPS::contains(const IntPoint &ip) const
d298 1
a298 1
unsigned YoderIPS::index(const IntPoint &ip) const
d317 1
a317 1
IntPoint YoderIPS::index(unsigned idx) const
d326 1
a326 1
	return IntPoint();
d359 1
a359 1
IntPoint YoderIPS::min() const
d363 1
a363 1
	return IntPoint();
d368 1
a368 1
	return IntPoint(this->lastbefore+1);
d372 1
a372 1
IntPoint YoderIPS::max() const
d376 1
a376 1
	return IntPoint();
d382 1
a382 1
	return IntPoint(this->slices[this->nslices -1].last);
d386 1
a386 1
IntPoint YoderIPS::inf() const
d390 1
a390 1
	return IntPoint();
d396 1
a396 1
	IntPoint	temp(slices[0].shadow.inf());
d405 1
a405 1
IntPoint YoderIPS::sup() const
d409 1
a409 1
	return IntPoint();
d415 1
a415 1
	IntPoint	temp(slices[0].shadow.sup());
d545 1
a545 1
static void squirgle(YoderIPS::interval* ivl, IntPoint p)
d553 1
a553 1
BaseIPS * YoderIPS::offsetted(const IntPoint&ip) const
@


1.17
log
@Yoder hash code is now cached.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.16 92/12/16 14:48:24 thoth Exp Locker: thoth $";
d6 3
d97 1
a97 1
	this->slices[0].shadow = WhiteHole(0);
d122 1
a122 7
#if 0
    {
	for (unsigned i=0; i<len; i++)
	    cout << cdr(aip[i],offset) << ' ';
	cout << '\n' << flush;
    }
#endif
d143 1
a143 1
		slices[nslices].shadow = BlackHole(dimen-1);
d158 1
a158 1
	    slices[nslices].shadow = WhiteHole(0);
d162 1
a162 1
		slices[nslices].shadow = BlackHole(0);
a237 1
#if 1
a238 9
#else
    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;
#endif
d474 3
a476 9
	     scan++) {
#if 0
	    cout << "(";
	    this->slices[high].shadow.output(cout);
	    cout << "==";
	    this->slices[scan].shadow.output(cout);
	    cout << ")";
#endif
	}
d556 1
a556 1
#if 1
d587 1
a587 1
	dest.slices[dest.nslices].shadow = BlackHole(second.dimen -1);
a685 9
    
#if 0
    cout << "a: ";
    first.slices[*f_idx].shadow.output(cout);
    cout << "b: ";
    second.slices[*s_idx].shadow.output(cout);
    cout << " a op b: ";
    dest.slices[dest.nslices].shadow.output(cout);
#endif
@


1.16
log
@conversion to IA_ mostly complete
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.15 92/12/07 12:05:13 thoth Exp Locker: thoth $";
d6 3
d96 1
d116 1
d171 1
d202 1
d223 1
d241 3
d251 1
d530 10
d546 1
@


1.15
log
@new IntPoint index(unsigned) operation for use with "other" iterators.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.14 92/11/15 15:58:29 thoth Exp Locker: thoth $";
d6 3
d75 2
d80 1
a80 1
YoderIPS::YoderIPS(const BoxyIPS& bps)
d102 1
a102 1
YoderIPS::YoderIPS(const IntPoint *aip, unsigned len, unsigned offset)
d172 1
a172 1
YoderIPS::~YoderIPS()
d180 1
a180 1
YoderIPS::YoderIPS(const YoderIPS& ips)
@


1.14
log
@expect a slight performance increase with preallocation of SetStructure.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.13 92/11/11 12:12:00 thoth Exp Locker: thoth $";
d6 3
d308 38
@


1.13
log
@added another restriction utility.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.12 92/11/04 12:02:14 thoth Exp Locker: thoth $";
d6 3
d910 1
@


1.12
log
@new image extension support routines.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.11 92/10/25 20:54:08 thoth Exp Locker: thoth $";
d6 3
d766 1
a766 1
    YoderIPS &dest, SetStructure *ss_result)
d778 1
a778 1
    ss_result->add_interval(count, SetStructure::FIRST_ONLY);
d816 1
a816 1
 const YoderIPS &dest, SetStructure *ss_result)
d831 1
a831 1
    ss_result->add_interval(count, SetStructure::FIRST_ONLY);
d835 1
a835 2
#if 1
static IntPointSet tmp_and(const IntPointSet &lhs, const IntPointSet &rhs,
a839 1
#endif
d841 1
d868 2
a869 1
	burn_nonoverlapping_leader(*this, &lidx, that, rval, result);
d876 1
a876 1
				   result, tmp_and);
d878 58
a935 1
      burn_nonoverlapping_trailer(*this, &lidx, rval, result);
@


1.11
log
@changed argument passing on set restriction routines.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.10 92/10/22 15:13:05 thoth Exp Locker: thoth $";
d6 3
d876 119
@


1.10
log
@pointset restriction utilities.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.9 92/09/30 10:39:31 thoth Exp Locker: thoth $";
d6 3
d772 1
a772 1
    ss_result->add_interval(count, SetStructure::NEITHER);
d780 1
a780 1
   SetStructure(*f)(const IntPointSet&,const IntPointSet&, IntPointSet *)
d787 3
a789 3
	SetStructure temp =
	    f(first.slices[*f_idx].shadow, second.slices[*s_idx].shadow,
	      &ivl.shadow);
d802 1
a802 1
	ss_result->add_interval(ivl.last - dest.last_before(dest.nslices), temp);
d825 1
a825 1
    ss_result->add_interval(count, SetStructure::NEITHER);
d830 2
a831 2
static SetStructure tmp_and(const IntPointSet &lhs, const IntPointSet &rhs,
			    IntPointSet	*result)
d837 2
a838 2
SetStructure
YoderIPS::intersect_with_structure (const YoderIPS &that, YoderIPS *result)
a841 1
    SetStructure	s_struct(this->dimen);
d845 1
a845 2
	*result = rval;
	return s_struct;
d854 2
a855 3
	*result = rval;
	s_struct.add_interval(this->card(), SetStructure::NEITHER);
	return s_struct;
d863 1
a863 1
	burn_nonoverlapping_leader(*this, &lidx, that, rval, &s_struct);
d870 1
a870 1
				   &s_struct, tmp_and);
d872 1
a872 1
      burn_nonoverlapping_trailer(*this, &lidx, rval, &s_struct);
d877 1
a877 2
    *result = rval;
    return s_struct;
@


1.9
log
@White and Black holes are now semi-public classes, unfortunately.
type() system now based on address of static data member.
WhiteHole is now a family of pointsets.
contains now accepts const Point<>&.
infimum & supremum virtuals now inf & sup.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.8 92/09/20 17:37:46 thoth Exp Locker: thoth $";
d6 7
d51 1
d749 130
@


1.8
log
@fixed spelling error
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.7 92/09/20 14:07:37 thoth Exp Locker: thoth $";
d6 3
d43 1
d49 2
d63 1
a63 1
	this->slices[0].shadow = WhiteHole;
d128 1
a128 1
	    slices[nslices].shadow = WhiteHole;
d199 1
a199 1
    return ips->type() == YODER &&
d259 1
a259 1
int YoderIPS::contains(IntPoint ip) const
d318 1
a318 1
IntPoint YoderIPS::infimum() const
d328 1
a328 1
	IntPoint	temp(slices[0].shadow.infimum());
d331 1
a331 1
		temp = ::infimum(temp, slices[i].shadow.infimum());
d337 1
a337 1
IntPoint YoderIPS::supremum() const
d347 1
a347 1
	IntPoint	temp(slices[0].shadow.supremum());
d350 1
a350 1
		temp = ::supremum(temp, slices[i].shadow.supremum());
d375 2
a376 5
    switch (this->slices[0].shadow.type()) {
    case BOXY:
	// of course
	return 1;
    case WHITE:
d379 1
a379 1
    default:
@


1.7
log
@new infemum and supremum methods for point sets.
new instance of the "comp undefined" bug.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.6 92/09/14 21:53:35 thoth Exp Locker: thoth $";
d6 4
d311 2
a312 2
// the infemum of a pointset, the coordinate-by-coordinate minimum
IntPoint YoderIPS::infemum() const
d322 1
a322 1
	IntPoint	temp(slices[0].shadow.infemum());
d325 1
a325 1
		temp = ::infimum(temp, slices[i].shadow.infemum());
@


1.6
log
@Fixed silly bug in comparison routines.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.C,v 1.5 92/09/03 13:36:21 thoth Exp Locker: thoth $";
d5 4
a8 1
// $Log:	YoderIPS.C,v $
d307 39
d465 6
d479 4
d485 1
@


1.5
log
@hash_self now deals with unsigneds
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.C,v 1.4 92/08/26 13:52:56 thoth Exp Locker: thoth $";
d6 3
d812 2
a813 1
	    if (temp==IntPointSet::P_SUPERSET)
d832 2
a833 1
	    if (temp==IntPointSet::P_SUBSET)
d875 1
@


1.4
log
@added some comments, hopefully things are a little clearer now.
meaningful exception types
sped up index, contains, empty.
removed old min/max cruft.
improved the compare operation.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.C,v 1.3 92/08/25 15:32:44 thoth Exp Locker: thoth $";
d6 7
d187 1
a187 1
int YoderIPS:: hash_self(int modulus) const
@


1.3
log
@new offsetted virtual functions for set translation
set difference is operator/, not -
lattice relationship is determinable on Yoders using compare() friend
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.C,v 1.2 92/08/24 10:37:47 thoth Exp Locker: thoth $";
d6 5
d28 1
d210 2
d238 2
a239 5
    if (this->nslices<1)
	return 0;
    if (ip[0]<=this->lastbefore ||
	ip[0]>this->slices[this->nslices-1].last)
	return 0;
d241 2
a242 2
    return this->slices[cylinder_index(ip[0])].shadow.contains(cdr(ip));
    // return 0;
d247 2
a248 1
    if (!this->contains(ip)) {
d250 1
a250 1
	    ia_throw(IA::INVALID_OPERATION, __FILE__,__LINE__);
a253 2
    unsigned i = cylinder_index(ip[0]);

d257 2
d267 1
d270 4
a273 11
#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
a277 1
#endif
d280 1
d283 4
a286 9
#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
a291 1
#endif
d294 1
d297 3
a299 6
    for (unsigned i=0; i<this->nslices; i++) {
	if (!this->slices[i].shadow.empty())
	    return 0;
    }

    return 1;
d304 1
d307 2
d311 2
d315 2
a316 1
	// fall through
d318 1
d321 3
d331 3
d344 1
d350 9
a358 2
	     scan++)
	    ;
d374 2
d393 2
d401 1
d413 2
d432 3
d456 10
d491 5
d508 7
d525 11
d573 2
d581 1
d587 1
a587 2
	// need better error type
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
d626 2
d633 1
d639 1
a639 2
	// need better error type
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
d664 2
a665 1
      
d680 1
d686 1
a686 2
	// need better error type
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
d726 2
d733 1
d739 1
a739 2
	// need better error type
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
d773 3
d777 4
d807 3
a809 1
	    else
d811 9
d824 3
a826 6
	    cout << "weird comparison result: " << rval;
	    lhs.slices[lidx].shadow.output(cout);
	    cout << " with\n";
	    rhs.slices[ridx].shadow.output(cout);
	    cout << ".\n";
	    abort();
d862 1
a862 1
	abort();
@


1.2
log
@*** empty log message ***
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.C,v 1.1 92/08/23 13:30:17 thoth Exp Locker: thoth $";
d6 3
d14 2
d392 2
d395 12
d667 1
a667 1
  return lhs - rhs;
d670 1
a670 1
YoderIPS YoderIPS::operator-(const YoderIPS &that) const
d711 2
a712 2
#if 0
void swap(const YoderIPS *p, const YoderIPS *q)
d714 1
a714 5
    const YoderIPS    *r;
    r = q;
    q = p;
    p = r;
}
d716 11
a726 9
YoderIPS YoderIPS::operator&(const YoderIPS &that) const
{
    YoderIPS  rval;
    const YoderIPS    *ps1, *ps2;
    
    if (this->dimen != that.dimen) {
	// need better error type
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return rval;
a727 26
    
    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.
d729 13
a741 10
	    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;
	    }
d743 6
a748 8
	    // 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;
	    }
d751 8
a758 22
	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++;
	}
d761 25
a785 3
    rval.canonicalize();

    return rval;
a786 2
#endif

@


1.1
log
@Initial revision
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.cc,v 1.7 92/08/20 11:12:27 thoth Exp $";
d5 3
a7 1
// $Log:	YoderIPS.cc,v $
d9 1
d81 1
a81 1
		slices[nslices].shadow.output(cout);
@
