head	1.48;
access;
symbols
	bob:1.48.1
	r2_1:1.43
	r2_0:1.43
	r1_1_beta:1.42
	r1_1_alpha:1.41
	r1_0:1.41
	r0_11:1.40
	r0_10:1.38
	r0_9:1.37
	Eglin_alpha_1:1.33;
locks
	thoth:1.48; strict;
comment	@// @;


1.48
date	94.11.10.18.50.09;	author fjsoria;	state Exp;
branches
	1.48.1.1;
next	1.47;

1.47
date	94.10.05.17.07.47;	author ljr;	state Exp;
branches
	1.47.1.1;
next	1.46;

1.46
date	94.10.04.18.16.35;	author thoth;	state Exp;
branches;
next	1.45;

1.45
date	94.09.27.20.47.09;	author fjsoria;	state Exp;
branches;
next	1.44;

1.44
date	94.09.19.16.49.11;	author ljr;	state Exp;
branches;
next	1.43;

1.43
date	94.08.18.23.38.01;	author thoth;	state Exp;
branches;
next	1.42;

1.42
date	94.07.25.16.58.52;	author thoth;	state Exp;
branches;
next	1.41;

1.41
date	94.05.08.19.35.40;	author thoth;	state Exp;
branches;
next	1.40;

1.40
date	94.04.26.18.16.19;	author thoth;	state Exp;
branches;
next	1.39;

1.39
date	94.03.30.13.44.31;	author thoth;	state Exp;
branches;
next	1.38;

1.38
date	94.01.31.16.38.04;	author thoth;	state Exp;
branches;
next	1.37;

1.37
date	93.11.17.18.04.38;	author thoth;	state Exp;
branches;
next	1.36;

1.36
date	93.10.20.15.50.54;	author thoth;	state Exp;
branches;
next	1.35;

1.35
date	93.09.15.12.36.33;	author thoth;	state Exp;
branches;
next	1.34;

1.34
date	93.08.08.13.18.35;	author thoth;	state Exp;
branches;
next	1.33;

1.33
date	93.05.26.16.51.29;	author thoth;	state Exp;
branches;
next	1.32;

1.32
date	93.05.19.14.47.57;	author thoth;	state Exp;
branches;
next	1.31;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.6
date	92.08.05.14.32.07;	author jnw;	state Exp;
branches;
next	1.5;

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

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

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

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

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

1.47.1.1
date	94.11.23.18.17.47;	author fjsoria;	state Exp;
branches;
next	;

1.48.1.1
date	94.11.21.19.40.14;	author thoth;	state Exp;
branches;
next	;


desc
@The IntPointSet container class.
@


1.48
log
@*** empty log message ***
@
text
@// Emacs: -*- C++ -*-

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


// 
// $Log: IntPS.h,v $
// Revision 1.47  1994/10/05  17:07:47  ljr
// Changed to not declare >= and > operators for IA_Set<IA_Point<int> >.
// This fixes a problem BC++ has compiling the bodies of these functions.
//
// Revision 1.46  1994/10/04  18:16:35  thoth
// comparisons don't need to be friends, but they do need to be declared.
//
// Revision 1.45  1994/09/27  20:47:09  fjsoria
// g++ v2.6 does no like n0n-inlined destructors
// added __NO_INLINE_DESTRUCTORS
//
// Revision 1.44  1994/09/19  16:49:11  ljr
// Changed to not declare <, <=, >=, > operators for IA_Set<IA_Point<int> >
// as friends.  This fixes a problem BC++ 4.02 has compiling the >= and >
// operator functions.
//
// Revision 1.43  1994/08/18  23:38:01  thoth
// DOS-inspired filename rework
//
// Revision 1.42  1994/07/25  16:58:52  thoth
// \Name sanitization
//
// Revision 1.41  1994/05/08  19:35:40  thoth
// New pointset concatenation capability.
// New intpointset decomposition capability.
//
// Revision 1.40  1994/04/26  18:16:19  thoth
// New array constructor that doesn't require dimension.
// White and Black Hole have been renamed to universal and empty _pset
//
// Revision 1.39  1994/03/30  13:44:31  thoth
// BasePSIter<IA_IntPoint> needs access to the hash table.
//
// Revision 1.38  1994/01/31  16:38:04  thoth
// Added static member functions to construct white and black holes.
// We can now transpose boxy 2D pointsets.
//
// Revision 1.37  1993/11/17  18:04:38  thoth
// extensivep() is now extensive()
// IPSIter is now PSIter<IntPoint> but bug in cfront 3.0.2 prevents typedef
//
// Revision 1.36  1993/10/20  15:50:54  thoth
// New naming scheme.  Closures are named Closure.
//
// Revision 1.35  1993/09/15  12:36:33  thoth
// Pointset behavior controls have moved to IA::
//
// Revision 1.34  93/08/08  13:18:35  thoth
// Parametrization of the pointsets on the point type using
// template specialization.
// 
// Revision 1.33  93/05/26  16:51:29  thoth
// Copyright Notices
// 
// Revision 1.32  93/05/19  14:47:57  thoth
// LatticeRelation is now in IA::
// 
// Revision 1.31  93/04/19  23:27:43  thoth
// Convert BaseIPS to IA_BasePS<IA_IntPoint>
// 
// Revision 1.30  93/04/17  14:52:42  thoth
// Use IA_IntPoint instead of IntPoint
// 
// Revision 1.29  93/02/20  15:21:47  thoth
// Added some comments on the op_with_structure operations.
// 
// Revision 1.28  93/02/12  16:24:37  thoth
// more IA_ prefixes.
// more comments.
// 
// Revision 1.27  93/01/20  11:36:37  thoth
// new PredicatePS class to allow for families of comprehensive pointsets.
// 
// Revision 1.26  92/12/16  14:48:11  thoth
// conversion to IA_ mostly complete
// 
// Revision 1.25  92/12/15  21:16:30  thoth
// added boxy predicate method.
// 
// Revision 1.24  92/12/07  12:05:09  thoth
// new IntPoint index(unsigned) operation for use with "other" iterators.
// 
// Revision 1.23  92/11/11  12:11:56  thoth
// added another restriction utility.
// 
// Revision 1.22  92/11/04  11:59:06  thoth
// New union_with_structure function for image extension.
// 
// Revision 1.21  92/10/25  20:53:47  thoth
// changed argument passing on set restriction routines.
// 
// Revision 1.20  92/10/22  15:11:51  thoth
// pointset restriction utilities.
// 
// Revision 1.19  92/10/07  23:16:03  thoth
// trim gratuitous includes from public headers.
// 
// Revision 1.18  92/09/30  10:33:07  thoth
// reference counts are protected from IntPointSet, unfortunately.
// infimum & supremum virtuals now inf & sup.
// contains now accepts const Point<>&.
// WhiteHole is now a family of pointsets.
// White and Black holes are now semi-public classes, unfortunately.
// 
// Revision 1.17  92/09/20  17:40:34  thoth
// fixed spelling error.
// Minkowski addition of point sets now supported.
// 
// Revision 1.15  92/09/20  14:05:49  thoth
// new infimum and supremum methods for point sets.
// 
// Revision 1.14  92/09/14  21:55:46  thoth
// dimension is now a parameter to the IntPoint array constructor.
// constructor for predicate IPS
// 
// Revision 1.13  92/09/07  13:23:23  thoth
// |&^/ operators are now friends.
// 
// Revision 1.12  92/09/03  13:35:49  thoth
// some lazies need to know the guts of IntPointSets
// 
// Revision 1.11  92/08/26  13:45:51  thoth
// eliminated dummy parameter to constructor (was workaround for g++).
// 
// Revision 1.10  92/08/25  15:31:04  thoth
// new converter from IntPoint to IntPointSet.
// set difference is operator/, not -
// op= for binary set operations now available.
// operator+ is set translation, using the offsetted() function of BaseIPS
// lattice operations on sets defined in terms of compare() friend
// 
// Revision 1.9  92/08/23  13:30:15  thoth
// CFrontified version
// 
// 

#ifndef IntPointSet_h_
#define IntPointSet_h_

#ifdef IA_PRII
#pragma interface
#endif

#define SUPPRESS_INCLUDE
#include "Set.h"
#undef SUPPRESS_INCLUDE

//#include "HashTable.h"
#include "IntPoint.h"
#include "BasePS.h"
// #include "SetStructure.h"

class IA_YoderIPS;
class IA_BoxyIPS;
class IA_HashTable;
class IA_SetStructure;
template <class P> struct IA_ClosurePS;
template <class P> class IA_PSIter;


class IA_Set<IA_Point<int> > {

    friend class IA_BasePSIter<IA_Point<int> >; // needs access to hash_table
    friend class IA_PointSetDecomposition;
  private:
    static IA_HashTable /* <IA_BasePS<IA_Point<int> >*,256> */	hash_table;
    
    IA_BasePS<IA_Point<int> >	*ps;
    void lookup_and_set(IA_BasePS<IA_Point<int> > *);
    void disassociate_ps();
    IA_Set(IA_BasePS<IA_Point<int> > *ips) { this->lookup_and_set(ips); }
    IA_Set(IA::Type t, unsigned dim);
  public:
    IA_Set();
    IA_Set(const IA_Point<int>& p);
    IA_Set(const IA_Point<int>& p0, const IA_Point<int>& p1);
    IA_Set(unsigned dimen, int(*f)(IA_Point<int>));
    IA_Set(unsigned dimen, int(*f)(const IA_Point<int>&));
    IA_Set(const IA_ClosurePS<IA_Point<int> >&);
    IA_Set(const IA_BoxyIPS&);
    IA_Set(const IA_YoderIPS&);
    IA_Set(unsigned dimen, const IA_Point<int> *aip, unsigned len);
    IA_Set(const IA_Point<int> *aip, unsigned len);
    IA_Set(const IA_Set<IA_Point<int> >& ips) { ps = ips.ps; ps->enref(); }
// dont now why g++ 2.6 doesn't like non-inlined destructors
#ifdef __NO_INLINE_DESTRUCTORS
    ~IA_Set() {
      if (ps==0) {
	cerr << "Internal Error: pointset destructed twice!\n";
	return;
      }
      this->disassociate_ps();
      ps = 0;
    }
#else
    ~IA_Set();
#endif
  
    IA_Set<IA_Point<int> > & operator=(const IA_Set<IA_Point<int> >&);
    inline friend int operator==(const IA_Set<IA_Point<int> >&s1,const IA_Set<IA_Point<int> >&s2 ) 
    { return s1.ps == s2.ps; }
    inline friend int operator!=(const IA_Set<IA_Point<int> >&s1,const IA_Set<IA_Point<int> >&s2 )
    { return s1.ps != s2.ps; }
    friend IA_Set<IA_Point<int> > operator|
    (const IA_Set<IA_Point<int> >&,const IA_Set<IA_Point<int> >&);
    friend IA_Set<IA_Point<int> > operator&
    (const IA_Set<IA_Point<int> >&,const IA_Set<IA_Point<int> >&);
    friend IA_Set<IA_Point<int> > operator^
    (const IA_Set<IA_Point<int> >&,const IA_Set<IA_Point<int> >&);
    friend IA_Set<IA_Point<int> > operator/
    (const IA_Set<IA_Point<int> >&,const IA_Set<IA_Point<int> >&);
    IA_Set<IA_Point<int> > operator~() const;
    IA_Set<IA_Point<int> >& operator|=(const IA_Set<IA_Point<int> >&rhs)
    { return (*this = *this | rhs); }
    IA_Set<IA_Point<int> >& operator&=(const IA_Set<IA_Point<int> >&rhs)
    { return (*this = *this & rhs); }
    IA_Set<IA_Point<int> >& operator^=(const IA_Set<IA_Point<int> >&rhs)
    { return (*this = *this ^ rhs); }
    IA_Set<IA_Point<int> >& operator/=(const IA_Set<IA_Point<int> >&rhs)
    { return (*this = *this / rhs); }
    
    friend IA_Set<IA_Point<int> > operator+(const IA_Set<IA_Point<int> >&, const IA_Point<int>&);
    friend IA_Set<IA_Point<int> > operator+(const IA_Point<int>& ip, const IA_Set<IA_Point<int> >&ips) {
	return ips+ip;	// commutative
    }
    IA_Set<IA_Point<int> >& operator+=(const IA_Point<int> &rhs)
    { return (*this = *this + rhs); }
    // Minkowski addition
    friend IA_Set<IA_Point<int> > operator+(const IA_Set<IA_Point<int> >&, const IA_Set<IA_Point<int> >&);
    IA_Set<IA_Point<int> >& operator+=(const IA_Set<IA_Point<int> > &rhs)
    { return (*this = *this + rhs); }
    
    friend IA::LatticeRelation compare(const IA_Set<IA_Point<int> >&, const IA_Set<IA_Point<int> >&);
    
    IA::Type type() const { return ps->type(); }
    unsigned dim() const { return ps->dim(); }
    
    int contains(const IA_Point<int> &ip) const { return ps->contains(ip); }
    unsigned index(const IA_Point<int> &ip) const { return ps->index(ip); }
    IA_Point<int> index(unsigned idx) const { return ps->index(idx); }
    
    IA_Point<int> min() const { return ps->min(); }
    IA_Point<int> max() const { return ps->max(); }
    IA_Point<int> inf() const { return ps->inf(); }
    IA_Point<int> sup() const { return ps->sup(); }
    IA_Point<int> choice() const { return ps->choice(); }
    
    unsigned card() const { return ps->card(); }
    int empty() const { return ps->empty(); }
    int boxy() const;
    int extensive() const { return ps->extensive(); }
    
    void output(ostream &o, unsigned indent=0) const { ps->output(o,indent); }
    
    int hash_self(int modulus) const { return ps->hash_self(modulus); }
    
    
    // Return the intersection of two IntPointSets, but also
    // return the structure of the lhs relative to the result.
    friend IA_Set<IA_Point<int> > intersect_with_structure
    (const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs,
     IA_SetStructure *s_struct);
    // Return the intersection of two IntPointSets, but also
    // return the structure of the both arguments relative to the result.
    friend IA_Set<IA_Point<int> > intersect_with_dualstruct
    (const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs, IA_SetStructure *s_struct);
    // Return the union of two IntPointSets, but also
    // return the structure of the both arguments relative to the result.
    friend IA_Set<IA_Point<int> > union_with_structure
    (const IA_Set<IA_Point<int> > &lhs, const IA_Set<IA_Point<int> > &rhs, IA_SetStructure *s_struct);
    
    // he has to know how to get at the underlying IA_BasePS<IA_Point<int> >*
    friend class IA_PSIter<IA_Point<int> >;
    
    
    friend IA_Set<IA_Point<int> > IA_boxy_pset(IA_Point<int>, IA_Point<int>);

    friend IA_Set<IA_Point<int> > concat(int, const IA_Set<IA_Point<int> >&);

    static IA_Set<IA_Point<int> > empty_pset(unsigned dim);
    static IA_Set<IA_Point<int> > universal_pset(unsigned dim);

    static IA_Set<IA_Point<int> > WhiteHole(unsigned dim) {
	return universal_pset(dim);
    }
    static IA_Set<IA_Point<int> > BlackHole(unsigned dim) {
	return empty_pset(dim);
    }
};


inline IA_Set<IA_Point<int> > IA_empty_ipset(unsigned dim) {
    return IA_Set<IA_Point<int> >::empty_pset(dim);
}
inline IA_Set<IA_Point<int> > IA_universal_ipset(unsigned dim) {
    return IA_Set<IA_Point<int> >::universal_pset(dim);
}

inline IA_Set<IA_Point<int> > IA_WhiteHole(unsigned dim) {
    return IA_universal_ipset(dim);
}
inline IA_Set<IA_Point<int> > IA_BlackHole(unsigned dim) {
    return IA_empty_ipset(dim);
}

void SortIntPointArray(IA_Point<int> *aip, unsigned len);

IA_Set<IA_Point<int> > transpose(const IA_Set<IA_Point<int> > &);

// in some cases, these operations can not tell definitively.
// In such cases, they return false (0).
// The following functions do not need to be declared friends.
int operator<(const IA_Set<IA_Point<int> > &, const IA_Set<IA_Point<int> >&);
int operator<=(const IA_Set<IA_Point<int> > &, const IA_Set<IA_Point<int> >&);

// The following declarations cause BC++ grief.  No one should need them,
// according to thoth.  If someone does, put a guard around them to keep
// BC++ from having problems compiling the bodies of these functions in
// IntPS.c.
#if 0
int operator>=(const IA_Set<IA_Point<int> > &, const IA_Set<IA_Point<int> >&);
int operator>(const IA_Set<IA_Point<int> > &, const IA_Set<IA_Point<int> >&);
#endif
  

#endif

@


1.48.1.1
log
@Added hash