/* Loci on dyadic grids */
/* Last edited on 2004-08-17 23:04:08 by stolfi */

#ifndef dglocus_H
#define dglocus_H

#include <dgbasic.h>
#include <dgtree.h>
#include <vec.h>
#include <js.h>

  
/*
  VALID LOCUS
  
  A locus {E} of a dyadic grid {G} is /valid/ if all the cells
  of its star {K(E)} are cells of {G}. Note that each item of {G}
  may be associated to zero or more valid loci.
  
  MINIMAL VALID LOCUS
  
  A locus {E} of a dyadic grid {G} is /minimal valid/ if it is valid
  and there is no other valid locus {E'} of {G}, with the same item
  as {E}, whose star {K(E')} is smaller than {K(E)} (i.e., whose rank 
  is greater than that of {E}). It can be seen that {E} is minimal valid if and only if
  it is valid, and at least one of the cells in {K(E)} is a leaf of
  {G}.
  
  MAXIMAL VALID LOCUS
  
  Similarly, a locus {E} of a dyadic grid {G} is /maximal valid/ if it
  is valid and there is no other valid locus {E'} of {G}, with the
  same item as {E}, whose star {K(E')} is greater than {K(E)} (i.e.,
  whose rank is less than that of {E}). It can be seen that {E} is
  maximal valid if and only if it is valid, and its rank is that of
  the first layer where that item appears.
  
  ENUMERATION OF MINIMAL AND MAXIMAL LOCI
  
  In what follows, {E} is a locus in some given dyadic greid {G},
  {NE} is the node star {N(E,T)} of {E} in the given grid, and 
  {dtE} is an arbitrary client data record associated with {E}. */

typedef void dg_LocusData;
  /* An arbitrary client data record associated with a locus. */
  
typedef void dg_LocusVisitProc
  ( dg_Locus E, 
    dg_Rank r, 
    dg_NodeStar *NE,
    dg_LocusData *dtE, 
    bool maxE
  );
  /* A procedure used by {dg_enum_critical_locus} to report a locus {E}
    of rank {r} that is maximal valid (if {maxE=TRUE}) or minimal
    valid (if {maxE=FALSE}). */

typedef dg_LocusData *dg_RootLocusDataProc(dg_Locus E, dg_Node *root);
  /* A procedure used by {dg_enum_critical_locus} to create an
    initial client data record for a locus {E} of rank 0. */
    
typedef dg_LocusData *dg_ShrinkLocusDataProc
  ( dg_Locus E, 
    dg_Rank r, 
    dg_Axis splax,
    dg_NodeStar *NE,
    dg_LocusData *dtE
  );
  /* A procedure used by {dg_enum_critical_locus} to create a new
    client data record for the child {E'} of a non-leaf valid locus
    {E} of rank {r} whose item {B} also exists in level {r+1}. Each
    each cell of the star of {E} gets split in perpendicular to axis
    {splax}. */

typedef dg_LocusData *dg_SplitLocusDataProc
  ( dg_Locus E, 
    dg_Rank r, 
    dg_Axis splax,
    dg_NodeStar *NE,
    dg_LocusData *dtE,
    dg_LocusData **dtLO, 
    dg_LocusData **dtHI, 
    dg_LocusData **dtMD
  );
  /* A procedure used by {dg_enum_critical_locus} to create new client
    data records {dtLO,dtHI,dtMD} for the children {ELO,EHI,EMD} of a
    non-leaf valid locus {E} of rank {r} which gets split in level
    {r+1}. Children {ELO} and {EHI} are the low and high halves of
    {E}, and {EMD} is their shared facet. The cut is perpendicular to
    axis {splax}. */
    
typedef void dg_FreeLocusDataProc
  ( dg_Locus E, 
    dg_Rank r, 
    dg_NodeStar *NE, 
    dg_LocusData *dtE
  );
  /* A procedure used by {dg_enum_critical_locus} to reclaim the
    space used by the client data record {dtE}, created by 
    one of the calls above. */

void dg_enum_critical_loci
  ( dg_Dim d, 
    dg_Node *root,
    dg_LocusVisitProc *visit, 
    dg_RootLocusDataProc *root_data,
    dg_ShrinkLocusDataProc *shrink_data,
    dg_SplitLocusDataProc *split_data,
    dg_FreeLocusDataProc *free_data
  );
  /* Enumerates all maximal and minimal loci of the finite {d}-dimensional
    multigrid {G} represented by the tree rooted at {t}. 
    
    The procedure calls {visit(E, r, dtE, TRUE)} is for each maximal
    valid locus, and {visit(E, r, dtE, FALSE)} for each minimal valid
    locus. The argument {r} given to {visit} is the rank of {E}.
    
    The argument {dtE} is some arbitrary client data record associated
    with {E}. Such records are created by {root_data}, {shrink_data},
    and {split_data} and eventually recovered by {free_data}. */
  
dg_Locus_vec_t dg_find_critical_loci(dg_Dim d, dg_Node *t, bool vtxOnly, bool maximal);
  /* Returns a list of all maximal (if {maximal=TRUE}) or minimal
    ({maximal=FALSE}) valid loci of the finite {d}-dimensional
    multigrid {G} represented by the tree rooted at {t}. If {vtxOnly},
    returns only vertex loci. */

#endif