#ifndef _SpatialConvex_h
#define _SpatialConvex_h
/*
//#     Filename:       SpatialConvex.h
//#
//#     Classes defined here: SpatialConvex
//#
//#
//#     Author:         Peter Z. Kunszt, based on A. Szalay's code
//#     
//#     Date:           October 16, 1998
//#
//#
//#
//# (c) Copyright The Johns Hopkins University 1998
//# All Rights Reserved
//#
//# The software and information contained herein are proprietary to The
//# Johns Hopkins University, Copyright 1998.  This software is furnished
//# pursuant to a written license agreement and may be used, copied,
//# transmitted, and stored only in accordance with the terms of such
//# license and with the inclusion of the above copyright notice.  This
//# software and information or any other copies thereof may not be
//# provided or otherwise made available to any other person.
//#
//#
*/
#include "SpatialConstraint.h"
#include "SpatialIndex.h"
#include "SpatialMarkup.h"
#include "BitList.h"

/*
//########################################################################
*/

typedef struct {
  IDTYPE *vector_;
  size_t length_;
  size_t capacity_;
} SpatialIDVec;

typedef struct {
  int32  *vector_;
  size_t capacity_;
  size_t length_;
} VarVecInt;

typedef struct {
  SpatialConstraintVec constraints_;      /* The vector of constraints */
  const SpatialIndex   *index_;		  /* A pointer to the index */
  SpatialMarkup        *markup_;	  /* A pointer to the markup */
  SpatialVectorVec     corners_;	  /* The corners of a zERO convex */
  SpatialConstraint    boundingCircle_;	  /* For zERO convexes, the bc. */
  size_t 	       addlevel_;	  /* additional levels to calculate */
  BitList 	       *full_;		  /* bitlist of full nodes */
  BitList 	       *partial_;	  /* bitlist of partial nodes */
  SpatialIDVec 	       *flist_;		  /* list of full node ids */
  SpatialIDVec 	       *plist_;		  /* list of partial node ids */
  bool bitresult_;			  /* flag which result (bit or list) */
  Sign sign_;
} SpatialConvex;

typedef struct {
  SpatialConvex *vector_;
  size_t 	length_;
  size_t        capacity_;
} SpatialConvexVec;

/* Default Constructor */
SpatialConvex * spatialConvexNew();

/* Destructor */
void spatialConvexDelete( SpatialConvex *c );

/* Constructor from a triangle */
SpatialConvex * spatialConvexNewTriangle( const SpatialVector * v1,
					  const SpatialVector * v2,
					  const SpatialVector * v3 );

/* Constructor from a rectangle */
SpatialConvex * spatialConvexNewRectangle( const SpatialVector * v1,
					   const SpatialVector * v2,
					   const SpatialVector * v3,
					   const SpatialVector * v4 );

/* Copy constructor */
SpatialConvex * spatialConvexCopy( const SpatialConvex * );

/* Assignment */
void spatialConvexAssign( SpatialConvex *, const SpatialConvex * );

/* Add a constraint */
void spatialConvexAdd( SpatialConvex *c, SpatialVector *v, float64 d );
size_t spatialConvexExtend( SpatialConvex *c );

/* Initialize the convex */
void spatialConvexInit( SpatialConvex * );

/* Simplify the convex, remove redundancies */
void spatialConvexSimplify( SpatialConvex * );

/* Intersect with index. The partial and full bitlists for the
   result have to be given. The markup accelerates the intersection
   for the index that is in memory, but is not used for the dynamically
   built triangles.
   If the conves occupies a large percent of the area of the sphere,
   bitlists are the preferred result method. */
void spatialConvexIntersectBit( SpatialConvex *, 
				const SpatialIndex * index, 
				SpatialMarkup * markup,
				BitList * partial, BitList * full );

/* Same intersection, but the result is given in a list of nodes.
   If the conves is very small, this is the preferred result method. */
void spatialConvexIntersect( SpatialConvex *, 
			     const SpatialIndex * index, 
			     SpatialMarkup * markup,
			     SpatialIDVec * partial, SpatialIDVec * full );

/* Return the number of constraints */
size_t spatialConvexNumConstraints( SpatialConvex * );

/* [] operator: give back constraint */
SpatialConstraint * spatialConvexGet( SpatialConvex *, size_t i );

/* read from stream */
void spatialConvexRead( SpatialConvex *, FILE * );

/* read from stream */
void spatialConvexReadRaDec( SpatialConvex *, FILE * );

/* write to stream */
void spatialConvexWrite( SpatialConvex *, FILE * );

/* Do the intersection (common function for overloaded intersect()) */
void spatialConvexDoIntersect( SpatialConvex * );

/* Simplification routine for zERO convexes. This is called by
   simplify() in case we have all zERO constraints. */
void spatialConvexSimplify0( SpatialConvex * );

/* This is the testsuit for the intersection.

   triangleTest: Test the nodes of the index if the convex hits it
   the argument gives the index of the nodes_ array to specify the QuadNode
 */
uint8 spatialConvexTriangleTest( SpatialConvex *, IDTYPE nodeIndex );

/* fillChildren: Mark the child nodes as markup. */
void spatialConvexFillChildren( SpatialConvex *, IDTYPE nodeIndex );

/* test each quadnode for intersections. Calls testTriangle after having
   tested the vertices using testVertex. */
uint8 spatialConvexTestNode( SpatialConvex *, 
			     const SpatialVector * v0, 
			     const SpatialVector * v1, 
			     const SpatialVector * v2 );

/* the same routine, but for a given saved node */
uint8 spatialConvexTestNodeIdx( SpatialConvex *, IDTYPE nodeIndex );

/* testTriangle: tests a triangle given by 3 vertices if
   it intersects the convex. Here the whole logic of deciding
   whether it is partial, full, swallowed or unknown is handled. */
uint8 spatialConvexTestTriangle( SpatialConvex *,
				 const SpatialVector * v0, 
				 const SpatialVector * v1, 
				 const SpatialVector * v2,
				 int vsum );

/* setfull: set the full bitlist for each node below this level. */
void spatialConvexSetfull( SpatialConvex *, IDTYPE id, size_t level );

/* test a triangle's subtriangles whether they are partial.
   If level is nonzero, recurse: subdivide the
   triangle according to our rules and test each subdivision.
   (our rules are: each subdivided triangle has to be given
   ordered counter-clockwise, 0th index starts off new 0-node,
   1st index starts off new 1-node, 2nd index starts off new 2-node
   middle triangle gives new 3-node.)
   if we are at the bottom, set this id's leafindex in partial bitlist. */
void spatialConvexTestPartial( SpatialConvex *,
			       size_t level, IDTYPE id,
			       const SpatialVector * v0, 
			       const SpatialVector * v1, 
			       const SpatialVector * v2 );

/* call full or partial depending on result of testNode. */
void spatialConvexTestSubTriangle( SpatialConvex *,
				   size_t level, IDTYPE id,
				   const SpatialVector * v0, 
				   const SpatialVector * v1, 
				   const SpatialVector * v2 );

/* Test for constraint relative position; intersect, one in the
   other, disjoint. */
int spatialConvexTestConstraints( SpatialConvex *, size_t i, size_t j );

/* Test if vertices are inside the convex for a saved node.
   makes use of the markup (this is where the speedup occurs) */
int spatialConvexTestVertexIdx( SpatialConvex *, size_t vIndex );

/* Same testVertex but for any vector v, no handling using markup */
int spatialConvexTestVertex( SpatialConvex *, const SpatialVector * v );

/* testHole : look for 'holes', i.e. negative constraints that have their
   centers inside the node with the three corners v0,v1,v2. */
bool spatialConvexTestHole( SpatialConvex *, 
			    const SpatialVector * v0, 
			    const SpatialVector * v1, 
			    const SpatialVector * v2 );

/* testEdge0: test the edges of the triangle against the edges of the
   zERO convex. The convex is stored in corners_ so that the convex
   is always on the left-hand-side of an edge corners_(i) - corners_(i+1).
   (just like the triangles). This makes testing for intersections with
   the edges easy. */
bool spatialConvexTestEdge0( SpatialConvex *,
			     const SpatialVector * v0, 
			     const SpatialVector * v1, 
			     const SpatialVector * v2 );

/* testEdge: look whether one of the constraints intersects with one of
   the edges of node with the corners v0,v1,v2. */
bool spatialConvexTestEdge( SpatialConvex *,
			    const SpatialVector * v0, 
			    const SpatialVector * v1, 
			    const SpatialVector * v2 );

/* eSolve: solve the quadratic equation for the edge v1,v2 of
   constraint[cIndex] */
bool spatialConvexESolve( SpatialConvex *,
			  const SpatialVector * v1, 
			  const SpatialVector * v2, size_t cIndex );

/* Test if bounding circle intersects with a constraint */
bool spatialConvexTestBoundingCircle( SpatialConvex *,
				      const SpatialVector * v0, 
				      const SpatialVector * v1, 
				      const SpatialVector * v2 );

  /* Test if a constraint intersects the edges */
bool spatialConvexTestEdgeConstraint( SpatialConvex *,
				      const SpatialVector * v0, 
				      const SpatialVector * v1, 
				      const SpatialVector * v2, 
				      size_t cIndex );

  /* Look for any positive constraint that does not intersect the edges */
size_t spatialConvexTestOtherPosNone( SpatialConvex *,
				      const SpatialVector * v0, 
				      const SpatialVector * v1, 
				      const SpatialVector * v2 );

  /* Test for a constraint lying inside or outside of triangle */
bool spatialConvexTestConstraintInside( SpatialConvex *,
					const SpatialVector * v0, 
					const SpatialVector * v1, 
					const SpatialVector * v2, 
					size_t cIndex );

  /* Test for a vector lying inside or outside of triangle */
bool spatialConvexTestVectorInside( SpatialConvex *,
				    const SpatialVector * v0, 
				    const SpatialVector * v1, 
				    const SpatialVector * v2, 
				    SpatialVector * v );


/* append a new element in spatialconvexvec */
size_t spatialConvexVecAppend( SpatialConvexVec *, 
			       const SpatialConvex * );

/* clear spatialconvexvec */
void spatialConvexVecClear( SpatialConvexVec *, bool );
void spatialConvexVecInit ( SpatialConvexVec * );

size_t spatialIDVecAppend( SpatialIDVec *, IDTYPE );
void spatialIDVecClear( SpatialIDVec *, bool );
void spatialIDVecInit( SpatialIDVec * );

size_t varVecIntAppend( VarVecInt *, int32 );
void varVecIntClear( VarVecInt *, bool );
void varVecIntInit( VarVecInt *v );
int varVecIntOrderDescending ( const void *a, const void *b );

#endif