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


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

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

1.4
date     92.07.30.16.37.51;  author jnw;  state Exp;
branches ;
next     1.3;

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

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

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


desc
@implementation of the IntPointSet container class.
@


1.6
log
@fixed bug in WhiteBlackHole::equal()
Reference counting is now the responsibility of IntPointSet
New constructor to make IntPointSets from arrays of Points
More boolean operations between IntPointSets, intersection,
symmetric+asymmetric difference.
@
text
@// Emacs: -*- C++ -*-
static char rcsid[] = "$Id: IntPointSet.cc,v 1.5 92/08/14 15:44:59 thoth Exp $";

// 
// $Log:	IntPointSet.cc,v $
// Revision 1.5  92/08/14  15:44:59  thoth
// Added an index(IntPoint) function to the IntPointSet
// 
// Revision 1.4  92/07/30  16:37:51  jnw
// Added intersection member function and constructor from YoderIPS
// Note code in & depends on not having an empty Yoder result (this
// is probably ok).
// 
// Revision 1.3  92/07/26  16:28:27  thoth
// switched the union operation to overload the bitwise operator
// (this avoids the implication of short-circuiting since this
// implication does not make sense for sets).
// Moved the handling of WhiteHoles to the top of the union operation.
// This simplifies the code a little and short circuits a very common
// condition.
// 
// Revision 1.2  92/07/21  11:26:55  thoth
// Support for Yoders, BlackHoles, WhiteHoles.
// using the hash table now.
// Union operation.
// 
// Revision 1.1  92/07/16  11:57:19  thoth
// Initial revision
// 
// 

#include <stdlib.h>
#include "IntPointSet.h"
#pragma implementation

#include "BaseIPS.h"
#include "BoxyIPS.h"
#include "YoderIPS.h"

HashTable IntPointSet::hash_table;
char IntPointSet::throw_on_index_uncontained =1;

// this is the class that contains all of the points of its dimensionality
class _WhiteHole: public BaseIPS {
public:
    _WhiteHole(unsigned dim) :BaseIPS(dim) { }
    // this class contains all points of a given dimensionality
    int equal(BaseIPS* ips) const { return ips->type()==WHITE &&
				      ips->dim() == this->dimen; }
    int hash_self(int) const { return 0; }
    PointSetType type() const { return WHITE; }
    int contains(IntPoint) const { return 1; }
    int extensivep() const { return 1;}
    unsigned card() const {
	if (this->dimen!=0)
	    throw(IA::INVALID_OPERATION,__FILE__,__LINE__);
	return 1;
    }
    int empty() const { return 0; }
    void output(ostream & o, unsigned indent=0) const {
      for (unsigned i=0; i<indent; i++) cout << ' ';
      o << "White"<<dimen<<'\n';
    }
};

// this is the 0-dimensional set that contains the 0-dimensional Point
IntPointSet WhiteHole(WHITE, 'b', 0);

// this is the class that contains none of the points of its dimensionality
class _BlackHole: public BaseIPS {
public:
    _BlackHole(unsigned dim) :BaseIPS(dim) { }
    ~_BlackHole() {}
    // this class contains no points of a given dimensionality
    int equal(BaseIPS* ips) const { return ips->type()==BLACK &&
				      ips->dim()==this->dimen; }
    int hash_self(int) const { return 1; }
    PointSetType type() const { return BLACK; }
    int contains(IntPoint) const { return 0; }
    int extensivep() const { return 0;}
    unsigned card() const { return 0;}
    int empty() const { return 1; }
    void output(ostream & o, unsigned indent=0) const {
      for (unsigned i=0; i<indent; i++) cout << ' ';
      o << "Black"<<dimen<<'\n';
    }
};


void IntPointSet::lookup_and_set(BaseIPS *ips)
{
    if (hash_table.reference(ips, &this->ps))
	delete ips;

    ps->refcount++;
}

void IntPointSet::disassociate_ps()
{
    if ( --ps->refcount <= 0 )
	hash_table.remove(ps);
    ps=0;
}

IntPointSet::IntPointSet()
{
    this->lookup_and_set(new _BlackHole(0));
}

IntPointSet::IntPointSet(PointSetType t, int dummy, unsigned dim)
{
    switch (t) {
    case WHITE:
	this->lookup_and_set(new _WhiteHole(dim));
	break;
    case BLACK:
	this->lookup_and_set(new _BlackHole(dim));
	break;
    default:
	abort();
    }
}

IntPointSet::IntPointSet(const IntPoint& p0, const IntPoint& p1)
{
    this->lookup_and_set(new BoxyIPS(p0, p1));
}

IntPointSet::IntPointSet(const BoxyIPS& bps)
{
    this->lookup_and_set(new BoxyIPS(bps));
}

IntPointSet::IntPointSet(const YoderIPS& yps)
{
    if (yps.isboxy()){
	if (yps.nslices<1) {
	    // We've got a black hole which is, of course, boxy
	    this->lookup_and_set(new  _BlackHole(yps.dimen));
	} else {
	    this->lookup_and_set(new BoxyIPS(yps.min(), yps.max()));
	}
    } else this->lookup_and_set(new YoderIPS(yps));
}


extern "C"
static int ipcmp(void *a, void *b)
{
  return Pointcmp(*(IntPoint*)a,*(IntPoint*)b);
}

void SortIntPointArray(IntPoint *aip, unsigned len)
{
  // We can use qsort because a swap of the bytes in
  // two IntPoints does not do any damage.
  qsort((char*)aip, len, sizeof(*aip), ipcmp);
}

IntPointSet::IntPointSet(const IntPoint *aip, unsigned len)
{
    if (len<1) {
	this->lookup_and_set(new _BlackHole(0));
	return;
    }

    unsigned dimen=aip[0].dimensions();

    for (unsigned i=0; i<len; i++) {
	if (aip[i].dimensions() != dimen) {
	    abort();
	    this->ps=0;
	    return;
	}
    }

    for (i=0; i+1<len; i++) {
	if (Pointcmp(aip[i],aip[i+1]) ==1)
	    break;
    }

    IntPoint	*newaip;
    if (i+1<len) {
	newaip = new IntPoint[len];
	for (i=0; i<len; i++)
	    newaip[i] = aip[i];
	SortIntPointArray(newaip, len);
#if 0
	cout << "sorting array\n" << flush;
	for (i=0; i<len; i++)
	    cout << newaip[i] << ' ';
	cout << '\n';
#endif
    } else
	newaip = (IntPoint*)aip;

    YoderIPS *temp = new YoderIPS(newaip, len);
    if (temp->isboxy()) {
	if (temp->nslices<1)
	    this->lookup_and_set(new _BlackHole(temp->dimen));
	else
	    this->lookup_and_set(new BoxyIPS(temp->min(), temp->max()));
	delete temp;
    } else
	this->lookup_and_set(temp);

    if (newaip!=aip)
	delete [] newaip;
}

IntPointSet::~IntPointSet()
{
#if 0
    if (ps==0 || ps==(BaseIPS*)1)
	// special PointSet types
	return;
#endif

    this->disassociate_ps();
}


IntPointSet& IntPointSet::operator=(const IntPointSet &ips)
{ 
    BaseIPS	*temp;
    temp = ips.ps;
    temp->refcount++;
    this->disassociate_ps();
    ps = temp;

    return *this;
}

IntPointSet IntPointSet::operator|(const IntPointSet &rhs) const
{
    if (this->dim() != rhs.dim()) {
	// need better message
	// cout << this->dim() << "!=" << rhs.dim() << '\n' << flush;
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return IntPointSet();
    }
#if 0
    cout << '|'<< this->dim() << "==" << rhs.dim() << '\n' << flush;
    this->output(cout);
    rhs.output(cout);
#endif

    switch (this->ps->type()) {
    case BLACK:
	return rhs;
    case WHITE:
	return *this;
    default:
	break;
    }
    switch (rhs.ps->type()) {
    case BLACK:
	return *this;
    case WHITE:
	return rhs;
    default:
	break;
    }

    if (this->ps->extensivep() && rhs.ps->extensivep()) {
#if 1
	YoderIPS	*left, *right;
	switch (this->ps->type()) {
	case BOXY:
	    left = new YoderIPS(*(BoxyIPS*)this->ps);
	    break;
	case YODER:
	    left = (YoderIPS*)this->ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	switch (rhs.ps->type()) {
	case BOXY:
	    right = new YoderIPS(*(BoxyIPS*)rhs.ps);
	    break;
	case YODER:
	    right = (YoderIPS*)rhs.ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	YoderIPS result( *left | *right );

	if (left != this->ps)
	    delete left;
	if (right != rhs.ps)
	    delete right;
#else
	YoderIPS result
	  ( ( (this->ps->type()==BOXY) ?
	     YoderIPS(*(BoxyIPS*)this->ps) :
	     *(YoderIPS*)this->ps )
	   |
	   ( (rhs.ps->type()==BOXY) ?
	    YoderIPS(*(BoxyIPS*)rhs.ps) :
	    *(YoderIPS*)rhs.ps )
	   );
#endif

	// this constructor checks for emptiness and boxiness
	return IntPointSet(result);
    }

    // no lazy point sets yet
    abort();
    return IntPointSet();
}

IntPointSet IntPointSet::operator&(const IntPointSet &rhs) const
{
    if (this->dim() != rhs.dim()) {
	// need better message
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return IntPointSet();
    }

    switch (this->ps->type()) {
    case BLACK:
	return *this;
    case WHITE:
	return rhs;
    default:
	break;
    }
    switch (rhs.ps->type()) {
    case BLACK:
	return rhs;
    case WHITE:
	return *this;
    default:
	break;
    }
    
    if (this->ps->extensivep() && rhs.ps->extensivep()) {
	YoderIPS	*left, *right;
	switch (this->ps->type()) {
	case BOXY:
	    left = new YoderIPS(*(BoxyIPS*)this->ps);
	    break;
	case YODER:
	    left = (YoderIPS*)this->ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	switch (rhs.ps->type()) {
	case BOXY:
	    right = new YoderIPS(*(BoxyIPS*)rhs.ps);
	    break;
	case YODER:
	    right = (YoderIPS*)rhs.ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	YoderIPS result( *left & *right );

	if (left != this->ps)
	    delete left;
	if (right != rhs.ps)
	    delete right;

	return IntPointSet(result);
    }

    // no lazy point sets yet
    abort();
    return IntPointSet();
}


IntPointSet IntPointSet::operator^(const IntPointSet &rhs) const
{
    if (this->dim() != rhs.dim()) {
	// need better message
	// cout << this->dim() << "!=" << rhs.dim() << '\n' << flush;
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return IntPointSet();
    }
#if 0
    cout << '^'<< this->dim() << "==" << rhs.dim() << '\n' << flush;
    this->output(cout);
    rhs.output(cout);
#endif

    switch (this->ps->type()) {
    case BLACK:
	return rhs;
    case WHITE:
	return ~rhs;
    default:
	break;
    }
    switch (rhs.ps->type()) {
    case BLACK:
	return *this;
    case WHITE:
	return ~*this;
    default:
	break;
    }

    if (this->ps->extensivep() && rhs.ps->extensivep()) {
	YoderIPS	*left, *right;
	switch (this->ps->type()) {
	case BOXY:
	    left = new YoderIPS(*(BoxyIPS*)this->ps);
	    break;
	case YODER:
	    left = (YoderIPS*)this->ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	switch (rhs.ps->type()) {
	case BOXY:
	    right = new YoderIPS(*(BoxyIPS*)rhs.ps);
	    break;
	case YODER:
	    right = (YoderIPS*)rhs.ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	YoderIPS result( *left ^ *right );

	if (left != this->ps)
	    delete left;
	if (right != rhs.ps)
	    delete right;

	return IntPointSet(result);
    }

    // no lazy point sets yet
    abort();
    return IntPointSet();
}


IntPointSet IntPointSet::operator-(const IntPointSet &rhs) const
{
    if (this->dim() != rhs.dim()) {
	// need better message
	// cout << this->dim() << "!=" << rhs.dim() << '\n' << flush;
	throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return IntPointSet();
    }
#if 0
    cout << '-'<< this->dim() << "==" << rhs.dim() << '\n' << flush;
    this->output(cout);
    rhs.output(cout);
#endif

    switch (this->ps->type()) {
    case BLACK:
	return *this;
    case WHITE:
	return ~rhs;
    default:
	break;
    }
    switch (rhs.ps->type()) {
    case BLACK:
	return *this;
    case WHITE:
	return BlackHole(this->dim());
    default:
	break;
    }

    if (this->ps->extensivep() && rhs.ps->extensivep()) {
	YoderIPS	*left, *right;
	switch (this->ps->type()) {
	case BOXY:
	    left = new YoderIPS(*(BoxyIPS*)this->ps);
	    break;
	case YODER:
	    left = (YoderIPS*)this->ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	switch (rhs.ps->type()) {
	case BOXY:
	    right = new YoderIPS(*(BoxyIPS*)rhs.ps);
	    break;
	case YODER:
	    right = (YoderIPS*)rhs.ps;
	    break;
	default:
	    // the other extensive pointsets were taken care of before.
	    abort();
	    break;
	}

	YoderIPS result( *left - *right );

	if (left != this->ps)
	    delete left;
	if (right != rhs.ps)
	    delete right;

	return IntPointSet(result);
    }

    // no lazy point sets yet
    abort();
    return IntPointSet();
}

IntPointSet IntPointSet::operator~() const
{
  switch (this->ps->type()) {
  case BLACK:
    return IntPointSet(WHITE, 'b', this->dim());
  case WHITE:
    return BlackHole(this->dim());
  default:
    abort();
    return IntPointSet();
  }
}
@


1.5
log
@Added an index(IntPoint) function to the IntPointSet
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: IntPointSet.cc,v 1.4 92/07/30 16:37:51 jnw Exp Locker: thoth $";
d6 3
d46 1
a46 1
    _WhiteHole(unsigned dim) { this->dimen = dim; }
d48 2
a49 1
    int equal(BaseIPS* ips) const { return ips->type()==WHITE; }
d60 4
d72 1
a72 1
    _BlackHole(unsigned dim) { this->dimen = dim; }
d75 2
a76 1
    int equal(BaseIPS* ips) const { return ips->type()==BLACK; }
d83 4
d94 2
d98 7
d146 65
d213 1
d217 1
d219 1
a219 1
    hash_table.unreference(ps);
d226 3
a228 2
    hash_table.reference(ips.ps, &temp);
    hash_table.unreference(ps);
d238 1
d242 5
d266 1
d300 11
d312 2
a313 5
	if (result.isboxy()) {
	    return IntPointSet(BoxyIPS(result.min(), result.max()));
	} else {
	    return IntPointSet(new YoderIPS(result));
	}
d381 2
a382 3
	// need to change this to use a constructor for IntPointSet
	// from YoderIPS that checks for empty.  This code failed
	// when result was empty.  min and max didn't work!
d384 4
a387 5
//	if (result.isboxy()) {
//	    return IntPointSet(BoxyIPS(result.min(), result.max()));
//	} else {
//	    return IntPointSet(new YoderIPS(result));
//	}
d389 67
d462 88
@


1.4
log
@Added intersection member function and constructor from YoderIPS
Note code in & depends on not having an empty Yoder result (this
is probably ok).
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: IntPointSet.cc,v 1.3 92/07/26 16:28:27 thoth Exp Locker: jnw $";
d6 5
d38 1
@


1.3
log
@switched the union operation to overload the bitwise operator
(this avoids the implication of short-circuiting since this
implication does not make sense for sets).
Moved the handling of WhiteHoles to the top of the union operation.
This simplifies the code a little and short circuits a very common
condition.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: IntPointSet.cc,v 1.2 92/07/21 11:26:55 thoth Exp Locker: thoth $";
d6 8
d106 12
d203 78
@


1.2
log
@Support for Yoders, BlackHoles, WhiteHoles.
using the hash table now.
Union operation.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: IntPointSet.cc,v 1.1 92/07/16 11:57:19 thoth Exp Locker: thoth $";
d6 5
d118 1
a118 1
IntPointSet IntPointSet::operator||(const IntPointSet &rhs) const
d126 2
a127 1
    if (this->ps->type() == BLACK)
d129 1
a129 1
    else if (rhs.ps->type() == BLACK)
d131 11
a145 4
	case WHITE:
	    // the result of a union of the WhiteHole with any other
	    // 0-dimensional PointSet (there are only 2) is the WhiteHole
	    return WhiteHole;
d153 1
a153 1
	    // there are no other extensive pointsets
a158 4
	case WHITE:
	    if (left != this->ps)
		delete left;
	    return WhiteHole;
d166 1
a166 1
	    // there are no other extensive pointsets
d171 1
a171 1
	YoderIPS result( *left || *right );
@


1.1
log
@Initial revision
@
text
@d2 1
a2 1
static char rcsid[] = "$Id$";
d5 3
a7 1
// $Log$
d9 1
d17 1
d21 17
a37 2
// this is the 0-dimensional set that contains the 0-dimensional point
IntPointSet WhiteHole(IntPointSet::WHITE, 0);
d39 2
a40 2
// this is the n-dimensional set that does not contains anything at all
IntPointSet BlackHole(IntPointSet::BLACK);
d42 13
a54 6
class WhiteHole: public BaseIPS {
    int equal(BaseIPS* ips) { return ips->type()==WHITE; }
    int hash_self(int) { return 0; }
    int type() { return WHITE; }
    int contains() const { return 1; }
    int extensivep() { return 0;}
d57 2
a58 1
IntPointSet::IntPointSet(SpecialTypes t, unsigned dim)
d60 11
d73 1
a73 1
	this->lookup_and_set(new WhiteHole);
d76 1
a76 1
	ps = 0;
d88 5
d102 12
a113 1
IntPointSet::lookup_and_set(BaseIPS *ips)
d115 64
a178 2
    if (hash_table.reference(ips, &this->ps))
	delete ips;
@
