// Emacs: -*- C++ -*-

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


// 
// $Log: YoderIPS.h,v $
// Revision 1.31  1994/09/13  19:14:05  ljr
// made IA_YoderIPS::interval class definition public to appease BC++
//
// Revision 1.30  1994/08/18  23:39:28  thoth
// DOS-inspired filename rework
//
// Revision 1.29  1994/07/25  16:58:52  thoth
// \Name sanitization
//
// Revision 1.28  1994/05/08  19:35:40  thoth
// New pointset concatenation capability.
// New intpointset decomposition capability.
//
// Revision 1.27  1993/11/17  18:02:03  thoth
// extensivep() is now extensive()
//
// Revision 1.26  1993/08/08  13:21:39  thoth
// new IA_Set template specialization architecture.
//
// Revision 1.25  93/07/15  11:35:28  thoth
// Add support for iterator virtual method.
// 
// Revision 1.24  93/05/26  16:51:48  thoth
// Copyright Notices
// 
// Revision 1.23  93/05/19  14:46:01  thoth
// LatticeRelation is now in IA::
// 
// Revision 1.22  93/04/19  23:27:50  thoth
// Convert BaseIPS to IA_BasePS<IA_IntPoint>
// 
// Revision 1.21  93/02/12  16:28:04  thoth
// more IA_ prefixes.
// 
// Revision 1.20  93/01/20  11:38:56  thoth
// Yoder hash code is now cached.
// 
// Revision 1.19  92/12/16  14:48:26  thoth
// conversion to IA_ mostly complete
// 
// Revision 1.18  92/12/07  12:05:16  thoth
// new IntPoint index(unsigned) operation for use with "other" iterators.
// 
// Revision 1.17  92/11/11  12:12:03  thoth
// added another restriction utility.
// 
// Revision 1.16  92/11/04  12:02:26  thoth
// new image extension support routines.
// 
// Revision 1.15  92/10/25  20:54:13  thoth
// changed argument passing on set restriction routines.
// 
// Revision 1.14  92/10/22  15:13:21  thoth
// pointset restriction utilities.
// 
// Revision 1.13  92/09/30  10:41:19  thoth
// type() system now based on address of static data member.
// infimum & supremum virtuals now inf & sup.
// contains now accepts const Point<>&.
// 
// Revision 1.12  92/09/20  17:37:49  thoth
// fixed spelling error
// 
// Revision 1.11  92/09/20  14:08:07  thoth
// new infimum and supremum methods for point sets.
// 
// Revision 1.10  92/09/03  13:31:13  thoth
// hash_self now deals with unsigneds
// 
// Revision 1.9  92/08/26  14:52:03  thoth
// mo' better comments
// 
// Revision 1.8  92/08/25  15:34:07  thoth
// new offsetted virtual functions for set translation
// set difference is operator/, not -
// lattice relationship is determinable on Yoders using compare() friend
// 
// Revision 1.7  92/08/23  13:30:19  thoth
// CFrontified version
// 
// 

#ifndef YoderIPS_h_
#define YoderIPS_h_

#ifdef IA_PRII
#pragma interface
#endif

#include "IntPoint.h"
#include "IntPS.h"
#include "BasePS.h"
#include "BoxyIPS.h"
#include "SetStructure.h"

class IA_YoderIPSIter;

class IA_YoderIPS: public IA_BasePS<IA_Point<int> > {
private:
    static char	type_;
public:
    /* A shadow cylinder is a set of points that are identical except for
       their first coordinate, and for each value of the first coordinate,
       every shadow is represented by a point in the set.
       */
    class interval {
    public:
	// The last coordinate of this shadow cylinder
	int	last;
	// The index (relative to the point set) of the point after
	// the last point in this shadow cylinder.
	unsigned	count_last;
	// The shape of the shadow.  One special IntPointSets:
	// WhiteHole represents a 0-dimensional IntPointSet that contains
	// the 0-dimensional IntPoint.
	IA_Set<IA_Point<int> >	shadow;
    };
protected:
    // the last coordinate before the shadow cylinders begin.
    int	lastbefore;

    // a vector of shadow cylinders
    // adjacent shadows must not be equal
    interval *slices;
    unsigned	nslices;

    static void interval_BlT(interval *source, interval *dest, unsigned count);
    unsigned cylinder_index(int coord) const;
    int last_before(unsigned idx) const { return idx?
					  slices[idx-1].last:
					  lastbefore; }

    void compress_duplicates();
    void compute_count_last();
    void compute_hash_cache();
    void canonicalize();

    // the following are subfunctions of the binary set operations |,^,&,/

    static void union_nonoverlapping
	(const IA_YoderIPS &first, const IA_YoderIPS &second, IA_YoderIPS &dest);
    static void copy_nonoverlapping_leader
	(const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
	 IA_YoderIPS &dest);
    static void copy_nonoverlapping_trailer
	(const IA_YoderIPS &source, unsigned *s_idx, IA_YoderIPS &dest);
    static void burn_nonoverlapping_leader
	(const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
	 IA_YoderIPS &dest);
    static void 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> >&));

    static void copy_nonoverlapping_leader
    (const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
     IA_YoderIPS &dest, IA_SetStructure *ss_result, IA_SetStructure sub);
    static void burn_nonoverlapping_leader
    (const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &second,
     IA_YoderIPS &dest, IA_SetStructure *ss_result, IA_SetStructure sub);
    static void 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*));
    static void copy_nonoverlapping_trailer
    (const IA_YoderIPS &first, unsigned *f_idx,
     IA_YoderIPS &dest, IA_SetStructure *, IA_SetStructure sub);
    static void burn_nonoverlapping_trailer
    (const IA_YoderIPS &first, unsigned *f_idx, const IA_YoderIPS &dest,
     IA_SetStructure *ss_result, IA_SetStructure sub);


    // protected constructor to create a blank Yoder.  It is used by the
    // binary set operations
    IA_YoderIPS(unsigned dim) :IA_BasePS<IA_Point<int> >(dim) { nslices=0; slices=0; lastbefore=0; }
private:
    // private constructor that takes a sorted array of IntPoints of
    // length len and constructs a Yoder from them.  It is private because
    // it has many preconditions that make it "unsafe" for the general public.
    IA_YoderIPS(const IA_Point<int> *, unsigned len, unsigned offset=0);

    // private constructor that increases the dimension of a pointset
    // by one by extending the input pointset into a cylinder
    IA_YoderIPS(int b1, int b2, const IA_Set<IA_Point<int> > &);

public:

    IA_YoderIPS(const IA_BoxyIPS&);
    ~IA_YoderIPS();
    IA_YoderIPS(const IA_YoderIPS&);
    IA_YoderIPS& operator=(const IA_YoderIPS&);

    int equal(IA_BasePS<IA_Point<int> >*) const;
    unsigned hash_self(unsigned) const;
private:
    unsigned hash_cache;
public:
    int operator==(const IA_YoderIPS&) const;

    static IA::Type s_type() { return &type_; }
    IA::Type type() const { return &type_; }

    int contains(const IA_Point<int>&) const;
    unsigned index(const IA_Point<int>&) const;
    IA_Point<int> index(unsigned) const;

    IA_Point<int> min() const;
    IA_Point<int> max() const;
    IA_Point<int> inf() const;
    IA_Point<int> sup() const;
    IA_Point<int> choice() const {return index(IA::rand_mod(card()));}

    unsigned card() const { return nslices ? slices[nslices-1].count_last :0; }
    int empty() const;
    IA_BasePS<IA_Point<int> > *offsetted(const IA_Point<int>&) const;
    IA_BasePS<IA_Point<int> > *reflect_through_origin() const;
    int extensive() const { return 1; }
    IA_BasePSIter<IA_Point<int> > *iterator() const;

    void output (ostream&, unsigned =0) const;

    // extra functions
    int isboxy() const;

    // binary set operations
    IA_YoderIPS operator|(const IA_YoderIPS&) const;
    IA_YoderIPS operator&(const IA_YoderIPS&) const;
    IA_YoderIPS operator^(const IA_YoderIPS&) const;
    IA_YoderIPS operator/(const IA_YoderIPS&) const;

    IA_YoderIPS intersect_with_structure(const IA_YoderIPS&, IA_SetStructure*) const;
    IA_YoderIPS intersect_with_dualstruct(const IA_YoderIPS&, IA_SetStructure*) const;
    IA_YoderIPS union_with_structure(const IA_YoderIPS&, IA_SetStructure*) const;

    IA_YoderIPS concat_with(IA_Set<IA_Point<int> >) const;

    // This function can return
    // NO_REL, P_SUBSET, P_SUPERSET, or EQUAL
    // It will abort if internal inconsistencies would cause it
    // to return otherwise.
    friend IA::LatticeRelation
	compare(const IA_YoderIPS&, const IA_YoderIPS&);

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

    friend class IA_Set<IA_Point<int> >;
    friend class IA_YoderIPSIter;
    friend class IA_PointSetDecomposition;
};

#endif
