// 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.11 1994/11/10 19:53:56 ljr Exp $";
#endif

// 
// $Log: SetStructure.c,v $
// 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_INLINE_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);
		    frag.bar = concat(0,orig.bar) + bar;
		    frag.plate = concat(0,orig.plate);
		}
	    } else {
		IA_decomp_frag	&frag = fragments.after_last();
		frag.bar = bar;
		frag.plate = concat(0,shadow);
		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(Pointset_RequireExtensive_Exception(__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);
}
