head	1.15;
access;
symbols
	r2_1:1.9
	r2_0:1.9
	r1_1_beta:1.9
	r1_1_alpha:1.8
	r1_0:1.8
	r0_11:1.7
	r0_10:1.7
	r0_9:1.7
	Eglin_alpha_1:1.7;
locks; strict;
comment	@// @;


1.15
date	94.12.08.18.08.48;	author ljr;	state Exp;
branches;
next	1.14;

1.14
date	94.12.07.20.12.14;	author ljr;	state Exp;
branches;
next	1.13;

1.13
date	94.12.03.04.17.43;	author fjsoria;	state Exp;
branches;
next	1.12;

1.12
date	94.12.01.16.04.02;	author fjsoria;	state Exp;
branches;
next	1.11;

1.11
date	94.11.10.19.53.56;	author ljr;	state Exp;
branches;
next	1.10;

1.10
date	94.11.01.19.18.36;	author fjsoria;	state Exp;
branches;
next	1.9;

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

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

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

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

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

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

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

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

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


desc
@a structure describing the derivation of a binary set operation
@


1.15
log
@added IA_BCPP_CONCAT_OVERLOAD_RESOLUTION guard for workarounds
resolving amibiguity with concat calls for BC++.
@
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: SetStructure.c,v 1.14 1994/12/07 20:12:14 ljr Exp ljr $";
#endif

// 
// $Log: SetStructure.c,v $
// Revision 1.14  1994/12/07  20:12:14  ljr
// added (const IA_Set<IA_Point<int> >&) casts to three concat calls
// to resolve ambiguities for BC++
//
// Revision 1.13  1994/12/03  04:17:43  fjsoria
//  changed pointset_erros.h to pset_errors.h
//
// Revision 1.12  1994/12/01  16:04:02  fjsoria
// __NO_OUTLINE_DESTRUCTORS
// changed from __NO_INLINE_DESTRUCTORS
//
// Revision 1.11  1994/11/10  19:53:56  ljr
// Added IA_NO_RCS_STATIC_DATA guard.
//
// Revision 1.10  1994/11/01  19:18:36  fjsoria
// non-inlined destructor fixed for g++
//
// Revision 1.9  1994/07/25  17:00:05  thoth
// Name sanitization.
//
// Revision 1.8  1994/05/08  19:37:14  thoth
// New intpointset decomposition capability.
//
// Revision 1.7  1993/05/26  16:57:50  thoth
// Copyright Notices
//
// Revision 1.6  92/12/16  14:48:19  thoth
// conversion to IA_ mostly complete
// 
// Revision 1.5  92/11/15  15:57:50  thoth
// expect a slight performance increase with preallocation.
// 
// Revision 1.4  92/11/11  12:17:14  thoth
// incremental optimization of SetStructures.
// 
// Revision 1.3  92/11/04  11:59:37  thoth
// stylistic improvements.
// 
// Revision 1.2  92/10/25  20:55:25  thoth
// made recursion termination constants have sensible names.
// 
// Revision 1.1  92/10/21  14:58:12  thoth
// Initial revision
// 
//

#include "SetStructure.h"
#include "BoxyIPS.h"
#include "YoderIPS.h"
#include "MondoPS.h"
#include "pset_errors.h"


static IA_real_ss	alpha(1.0), beta(1.0), gamma(1.0);
const IA_SetStructure IA_SetStructure::FIRST_ONLY  (&alpha);
const IA_SetStructure IA_SetStructure::SECOND_ONLY (&beta);
const IA_SetStructure IA_SetStructure::BOTH   (&gamma);

void IA_SetStructure::copy_on_write()
{
    if (!val) {
	val = new IA_real_ss;
	return;
    }
    if (val->refcount<2)
	return;
    IA_real_ss *temp=new IA_real_ss(*val);
    val->refcount--;
    val = temp;
}

IA_SetStructure::IA_SetStructure(IA_real_ss *val_)
{
    val = val_;
    if (val)
	val->refcount++;
}

IA_SetStructure::IA_SetStructure()
{
    val = 0;
}

IA_SetStructure::IA_SetStructure(const IA_SetStructure &ss)
{
    val = ss.val;
    if (val)
	val->refcount++;
}

#ifndef __NO_OUTLINE_DESTRUCTORS
IA_SetStructure::~IA_SetStructure()
{
    if (val)
	if (0>=--val->refcount)
	    delete val;
    val=0;
}
#else
void IA_SetStructure::DestroySetStructure()
{
    if (val)
	if (0>=--val->refcount)
	    delete val;
    val=0;
}
#endif


IA_SetStructure& IA_SetStructure::operator=(const IA_SetStructure& rhs)
{
    if (rhs.val)
	rhs.val->refcount++;
    if (val) {
	if (0 >= --val->refcount)
	    delete val;
    }
    val = rhs.val;
    return *this;
}

void IA_SetStructure::add_interval(unsigned count, IA_SetStructure sub)
{
    if (sub.val==0 || sub.val->ivls.len()==0)
	// if the substructure is empty, why add it?
	return;

    copy_on_write();

    if (val->ivls.len()>0 && val->ivls.last().substructure == sub) {
	val->ivls.last().count += count;
	return;
    }

    IA_ss_interval 	&ivl = val->ivls.after_last();

    if (sub.val->ivls.len()==1) {
	ivl.count = count * sub.val->ivls[0].count;
	ivl.substructure = sub.val->ivls[0].substructure;
    } else {
	ivl.count = count;
	ivl.substructure = sub;
    }
}

IA_ss_interval IA_SetStructure::retrieve_interval(unsigned idx) const
{
    if (val)
	return val->ivls[idx];
    else
	return IA_ss_interval();
}

unsigned IA_SetStructure::nintervals() const
{
    if (val)
	return val->ivls.len();
    else
	return 0;
}

void IA_SetStructure::ensure_space(unsigned howmuch)
{
    copy_on_write();

    unsigned	len=val->ivls.len();
    val->ivls.lengthen(len+howmuch);
    val->ivls.shorten(len);
}

//
//
//

IA_PointSetDecomposition:: IA_PointSetDecomposition(const IA_Set<IA_Point<int> > &ps)
{
    if (ps.type() == IA_BoxyIPS::s_type()) {
	IA_decomp_frag	&frag = fragments[0];
	if (ps.card()==1) {
	    // condition 2
	    frag.bar = ps;
	    frag.plate = extend_to_point(0, ps.dim());
	} else {
	    IA_Point<int>	inf_(ps.inf());
	    IA_Point<int>	sup_(ps.sup());
	    for	(int i=0; i<ps.dim(); i++) {
		if (inf_[i] != sup_[i]) {
		    IA_Point<int>	inf2(inf_), sup2(sup_);
		    sup2[i] = inf2[i] = 0; 
		    if (inf2==sup2) {
			// condition 1
			frag.bar = ps;
			frag.plate = extend_to_point(0, ps.dim());
		    } else {
			// both bits are meaty
			frag.plate = IA_boxy_pset(inf2, sup2);
			sup2 = inf2 = extend_to_point(0, ps.dim());
			inf2[i] = inf_[i];
			sup2[i] = sup_[i];
			frag.bar = IA_boxy_pset(inf2, sup2);
		    }
		    break;
		} else {
		    // condition 2
		}
	    }
	    // the loop will never terminate normally.
	    // It will always break because ps.card()!=1
	}
    } else if (ps.type() == IA_YoderIPS::s_type()) {
	const IA_YoderIPS	&yips = *(IA_YoderIPS*)ps.ps;
	char	*already = new char[yips.nslices];
	int	i, j;
	for (i=0; i<yips.nslices; i++)
	    already[i] = 0;
	for (i=0; i<yips.nslices; i++) {
	    if (already[i])
		continue;	// this had the same shadow as an earlier slice
	    IA_Set<IA_Point<int> >	bar = IA_empty_ipset(ps.dim());
	    IA_Set<IA_Point<int> >	shadow = yips.slices[i].shadow;
	    for (j=i; j<yips.nslices; j++) {
		if (yips.slices[j].shadow==shadow) {
		    already[j] = 1;
		    IA_Point<int>	inf_, sup_;
		    inf_ = sup_ = extend_to_point(0, ps.dim());
		    inf_[0] = yips.last_before(j)+1;
		    sup_[0] = yips.slices[j].last;
		    bar |= IA_boxy_pset(inf_, sup_);
		}
	    }
	    if (shadow.empty())
		continue;	// we don't really need to talk about this one

	    if (bar.card()==1) {
		// Condition 2
		IA_PointSetDecomposition	pds(shadow);
		for (int k=0; k<pds.fragments.len(); k++) {
		    IA_decomp_frag	&frag = fragments.after_last();
		    IA_decomp_frag	orig = pds.fragments(k);

#ifdef IA_BCPP_CONCAT_OVERLOAD_RESOLUTION
		    frag.bar = concat(0,(const IA_Set<IA_Point<int> >&)orig.bar) + bar;
		    frag.plate = concat(0,(const IA_Set<IA_Point<int> >&)orig.plate);
#else
		    frag.bar = concat(0,orig.bar) + bar;
		    frag.plate = concat(0,orig.plate);
#endif
		}
	    } else {
		IA_decomp_frag	&frag = fragments.after_last();
		frag.bar = bar;

#ifdef IA_BCPP_CONCAT_OVERLOAD_RESOLUTION
		frag.plate = concat(0,(const IA_Set<IA_Point<int> >&)shadow);
#else
		frag.plate = concat(0,shadow);
#endif
		if (frag.plate.card()==1) {
		    // condition 1
		    frag.bar += frag.plate;
		    frag.plate = extend_to_point(0, ps.dim());
		}
	    }
	}

	for (i=0; i<fragments.len(); i++)
	    already[i] = 0;
	int	k=0;
	for (i=0; i < fragments.len(); i++) {
	    if (already[i])
		continue;
	    already[i]=1;
	    if (k!=i)
		fragments[k] = fragments[i];
	    for (j=i+1; j<fragments.len(); j++) {
		if (!already[j] &&
		    fragments(j).plate==fragments(i).plate) {
		    fragments[k].bar |= fragments(j).bar;
		    already[j] = 1;
		}
	    }
	    k++;
	}
	fragments.shorten(k);

	delete[] already;

    } else if (ps.type() == IA_WhiteHole_<IA_Point<int> >::s_type()
	       && ps.dim()==0) {
	IA::not_yet_implemented(__FILE__, __LINE__);
    } else {
	ia_throw(IA::PSET_REQUIRE_EXTENSIVE, __FILE__, __LINE__);
    }
}


IA_decomp_frag IA_PointSetDecomposition::get_frag(int idx)
{
    if (idx<0 || idx>=fragments.len()) {
	ia_throw(Pointset_DecompFragBounds_Exception(__FILE__, __LINE__));
	return IA_decomp_frag();
    } else
	return fragments(idx);
}
@


1.14
log
@added (const IA_Set<IA_Point<int> >&) casts to three concat calls
to resolve ambiguities for BC++
@
text
@d11 1
a11 1
static char rcsid[] = "$Id: SetStructure.c,v 1.13 1994/12/03 04:17:43 fjsoria Exp ljr $";
d16 4
d255 2
d259 4
d267 2
d270 3
@


1.13
log
@ changed pointset_erros.h to pset_errors.h
@
text
@d11 1
a11 1
static char rcsid[] = "$Id: SetStructure.c,v 1.12 1994/12/01 16:04:02 fjsoria Exp fjsoria $";
d16 3
d251 2
a252 2
		    frag.bar = concat(0,orig.bar) + bar;
		    frag.plate = concat(0,orig.plate);
d257 1
a257 1
		frag.plate = concat(0,shadow);
@


1.12
log
@__NO_OUTLINE_DESTRUCTORS
changed from __NO_INLINE_DESTRUCTORS
@
text
@d11 1
a11 1
static char rcsid[] = "$Id: SetStructure.c,v 1.11 1994/11/10 19:53:56 ljr Exp fjsoria $";
d16 4
d59 1
a59 1
#include "pointset_errors.h"
@


1.11
log
@Added IA_NO_RCS_STATIC_DATA guard.
@
text
@d11 1
a11 1
static char rcsid[] = "$Id: SetStructure.c,v 1.10 1994/11/01 19:18:36 fjsoria Exp ljr $";
d16 3
d95 1
a95 1
#ifndef __NO_INLINE_DESTRUCTORS
@


1.10
log
@non-inlined destructor fixed for g++
@
text
@d8 1
d11 2
a12 1
static char rcsid[] = "$Id: SetStructure.c,v 1.9 1994/07/25 17:00:05 thoth Exp fjsoria $";
d16 3
@


1.9
log
@Name sanitization.
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: SetStructure.c,v 1.8 1994/05/08 19:37:14 thoth Exp thoth $";
d14 3
d87 1
d95 10
@


1.8
log
@New intpointset decomposition capability.
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: SetStructure.c,v 1.7 1993/05/26 16:57:50 thoth Exp thoth $";
d14 3
d46 5
a50 8
typedef IA_real_ss	real_ss;
typedef IA_ss_interval	ss_interval;
typedef IA_SetStructure	SetStructure;

static real_ss	alpha(1.0), beta(1.0), gamma(1.0);
const SetStructure SetStructure::FIRST_ONLY  (&alpha);
const SetStructure SetStructure::SECOND_ONLY (&beta);
const SetStructure SetStructure::BOTH   (&gamma);
d52 1
a52 1
void SetStructure::copy_on_write()
d55 1
a55 1
	val = new real_ss;
d60 1
a60 1
    real_ss *temp=new real_ss(*val);
d65 1
a65 1
SetStructure::IA_SetStructure(real_ss *val_)
d72 1
a72 1
SetStructure::IA_SetStructure()
d77 1
a77 1
SetStructure::IA_SetStructure(const SetStructure &ss)
d84 1
a84 1
SetStructure::~IA_SetStructure()
d92 1
a92 1
SetStructure& SetStructure::operator=(const SetStructure& rhs)
d104 1
a104 1
void SetStructure::add_interval(unsigned count, SetStructure sub)
d117 1
a117 1
    ss_interval 	&ivl = val->ivls.after_last();
d128 1
a128 1
ss_interval SetStructure::retrieve_interval(unsigned idx) const
d133 1
a133 1
	return ss_interval();
d136 1
a136 1
unsigned SetStructure::nintervals() const
d144 1
a144 1
void SetStructure::ensure_space(unsigned howmuch)
d157 1
a157 1
IA_PointSetDecomposition:: IA_PointSetDecomposition(const IA_IntPointSet &ps)
d166 2
a167 2
	    IA_IntPoint	inf_(ps.inf());
	    IA_IntPoint	sup_(ps.sup());
d170 1
a170 1
		    IA_IntPoint	inf2(inf_), sup2(sup_);
d201 2
a202 2
	    IA_IntPointSet	bar = IA_empty_ipset(ps.dim());
	    IA_IntPointSet	shadow = yips.slices[i].shadow;
d206 1
a206 1
		    IA_IntPoint	inf_, sup_;
@


1.7
log
@Copyright Notices
@
text
@d10 1
a10 1
static char rcsid[] = "$Id: SetStructure.c,v 1.6 92/12/16 14:48:19 thoth Exp Locker: thoth $";
d13 4
a16 1
// $Log:	SetStructure.c,v $
d38 4
d151 124
@


1.6
log
@conversion to IA_ mostly complete
@
text
@a1 1
static char rcsid[] = "$Id: SetStructure.c,v 1.5 92/11/15 15:57:50 thoth Exp Locker: thoth $";
d3 9
d14 3
@


1.5
log
@expect a slight performance increase with preallocation.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: SetStructure.c,v 1.4 92/11/11 12:17:14 thoth Exp Locker: thoth $";
d6 3
d25 4
d47 1
a47 1
SetStructure::SetStructure(real_ss *val_)
d54 1
a54 1
SetStructure::SetStructure()
d59 1
a59 1
SetStructure::SetStructure(const SetStructure &ss)
d66 1
a66 1
SetStructure::~SetStructure()
@


1.4
log
@incremental optimization of SetStructures.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: SetStructure.c,v 1.3 92/11/04 11:59:37 thoth Exp Locker: thoth $";
d6 3
d117 9
@


1.3
log
@stylistic improvements.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: SetStructure.c,v 1.2 92/10/25 20:55:25 thoth Exp Locker: thoth $";
d6 3
d83 15
a97 3
    ss_interval 	&ivl = val->ivls[val->ivls.len()];
    ivl.count = count;
    ivl.substructure = sub;
@


1.2
log
@made recursion termination constants have sensible names.
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: SetStructure.c,v 1.1 92/10/21 14:58:12 thoth Exp Locker: thoth $";
d6 3
d16 1
a16 1
static real_ss	alpha, beta, gamma;
@


1.1
log
@Initial revision
@
text
@d2 1
a2 1
static char rcsid[] = "$Id: YoderIPS.c,v 1.9 92/09/30 10:39:31 thoth Exp Locker: thoth $";
d5 4
a8 1
// $Log:	YoderIPS.c,v $
d13 4
a16 5
real_ss	alpha, beta, gamma, delta;
const SetStructure SetStructure::NEITHER(&alpha);
const SetStructure SetStructure::FIRST  (&beta);
const SetStructure SetStructure::SECOND (&gamma);
const SetStructure SetStructure::BOTH   (&delta);
d18 1
a18 1
void SetStructure::cow()
d20 9
a28 9
  if (!val) {
    val = new real_ss;
    return;
  }
  if (val->refcount<2)
    return;
  real_ss *temp=new real_ss(*val);
  val->refcount--;
  val = temp;
d33 3
a35 4
  dimensions = 0;
  val = val_;
  if (val)
    val->refcount++;
d38 1
a38 1
SetStructure::SetStructure(unsigned dim)
d40 1
a40 6
  dimensions = dim;
#if 0
  val = new real_ss;
#else
  val = 0;
#endif
d45 3
a47 4
  dimensions = ss.dimensions;
  val = ss.val;
  if (val)
    val->refcount++;
d52 4
a55 4
  if (val)
    if (0>=--val->refcount)
      delete val;
  val=0;
d60 8
a67 9
  if (rhs.val)
    rhs.val->refcount++;
  if (val) {
    if (0 >= --val->refcount)
      delete val;
  }
  val = rhs.val;
  dimensions = rhs.dimensions;
  return *this;
d72 8
a79 4
  cow();
  ss_interval 	&ivl = val->ivls[val->ivls.len()];
  ivl.count = count;
  ivl.substructure = sub;
d84 4
a87 4
  if (val)
    return val->ivls[idx];
  else
    return ss_interval();
d92 4
a95 4
  if (val)
    return val->ivls.len();
  else
    return 0;
@
