/* The quad-edge data structure (oriented surface version). */
/* Last edited on 2005-08-26 10:53:09 by stolfi */

/* 
** The quad-edge data structure encodes the topology of a 
** graph drawn on an orientable compact 2-D manifold
** (i.e. a borderless surface of finite extent)
** in such a way that every face is a topological disk.
** For details, see 
**
**   "Primitives for the Manipulation of General Subdivisions 
**   and the Computation of Voronoi Diagrams"
**
**   L. Guibas, J. Stolfi, ACM Transcations on Graphics, April 1985
**
** Originally written by Jim Roth (DEC CADM Advanced Group) on May 1986.
** Modified by J. Stolfi on April 1993.
** See the copyright notice at the end of this file.
*/

#ifndef quad_H
#define quad_H

typedef int quad_arc_t;  /* A directed edge, primal or dual */

#define NULL_REF 0

typedef struct quad_edge_rec { /* Edge record (four arcs). */
    quad_arc_t next[4];  /* Topological links. */
    void *data[4];       /* Client data fields. */
    unsigned mark;       /* For internal use. */
  } quad_edge_rec;

/* Edge record from arc reference: */

#define EDGE(e) ((quad_edge_rec *)((e)&0xfffffffcu))

/* Edge orientation operators: */

#define ROT(e) (((e)&0xfffffffcu)+(((e)+1)&3u))
#define SYM(e) (((e)&0xfffffffcu)+(((e)+2)&3u))
#define TOR(e) (((e)&0xfffffffcu)+(((e)+3)&3u))

/* Vertex/face walking operators: */

#define ONEXT(e) ((quad_edge_rec *)((e)&0xfffffffcu))->next[(e)&3]
#define ROTRNEXT(e) ((quad_edge_rec *)((e)&0xfffffffcu))->next[((e)+1)&3]
#define SYMDNEXT(e) ((quad_edge_rec *)((e)&0xfffffffcu))->next[((e)+2)&3]
#define TORLNEXT(e) ((quad_edge_rec *)((e)&0xfffffffcu))->next[((e)+3)&3]

#define RNEXT(e) (TOR(ROTRNEXT(e)))
#define DNEXT(e) (SYM(SYMDNEXT(e)))
#define LNEXT(e) (ROT(TORLNEXT(e)))

#define OPREV(e) (ROT(ROTRNEXT(e)))
#define DPREV(e) (TOR(TORLNEXT(e)))
#define RPREV(e) (SYMDNEXT(e))
#define LPREV(e) (SYM(ONEXT(e)))

/* Data pointers: */

#define ODATA(e) ((quad_edge_rec *)((e)&0xfffffffcu))->data[(e)&3]
#define RDATA(e) ((quad_edge_rec *)((e)&0xfffffffcu))->data[((e)+1)&3]
#define DDATA(e) ((quad_edge_rec *)((e)&0xfffffffcu))->data[((e)+2)&3]
#define LDATA(e) ((quad_edge_rec *)((e)&0xfffffffcu))->data[((e)+3)&3]

/* Orientation bits: */

#define SYMBIT(e) (((e)&2)>>1)  
#define ROTBIT(e) ((e)&1)
#define QUADBITS(e) ((e)&3)
  /* Bits that distinguish the various flavors of the same edge:
      {SYMBIT(e)} distinguishes {e} from {SYM(e)}.
      {ROTBIT(e)} distinguishes {{e,SYM(e)}} from {{ROT(e),TOR(e)}}.
      {QUADBITS(e) = 2*SYMBIT(e) + ROTBIT(e)} distinguishes the four arcs
        {ROT^k(e)} from each other.
    Nothing can be assumed between {QUADBITS(e)} and {QUADBITS(ONEXT(e))}. */

/* Topology_changing operators: */

quad_arc_t quad_make_edge(void);

void quad_destroy_edge(quad_arc_t e);

void quad_splice(quad_arc_t a, quad_arc_t b);

/* Map traversal: */

void quad_enum(
    quad_arc_t a, 
    void visit_proc(quad_arc_t e, void *closure), 
    void *closure
  );
  /* Enumerates undirected primal edges reachable from {a}.
    
    Calls visit_proc(e, closure) for every edge {e} that can be reached from
    edge {a} by a chain of {SYM} and {ONEXT} calls; except that exactly one
    of {e} and {SYM(e)} is visited. */

#endif

/*
** Copyright notice:
**
** Copyright © 1996, 2005 Institute of Computing, Unicamp.
**
** Permission to use this software for any purpose is hereby granted,
** provided that any substantial copy or mechanically derived version
** of this file that is made available to other parties is accompanied
** by this copyright notice in full, and is distributed under these same
** terms. 
**
** DISCLAIMER: This software is provided "as is" with no explicit or
** implicit warranty of any kind.  Neither the authors nor their
** employers can be held responsible for any losses or damages
** that might be attributed to its use.
**
** End of copyright notice.
*/