/* See quad.h. */
/* Last edited on 2005-08-26 08:41:00 by stolfi */
  
/* 
** Written by J. Stolfi on april 1993, based on an original 
** implementation by Jim Roth (DEC CADM Advanced Group, May 1986).  
** See the copyright notice at the end of this file.
*/ 

#include "quad.h"
#include <memory.h>
#include <malloc.h>

#define MARK(e)  ((quad_edge_rec *)((e)&0xfffffffcu))->mark

/* Make a new edge: */

quad_arc_t quad_make_edge(void)
  {
    quad_arc_t e;

    e = (quad_arc_t) malloc(sizeof(quad_edge_rec));
    ONEXT(e) = e;
    SYMDNEXT(e) = SYM(e);
    ROTRNEXT(e) = TOR(e);
    TORLNEXT(e) = ROT(e);
    ODATA(e) = NULL;
    DDATA(e) = NULL;
    LDATA(e) = NULL;
    RDATA(e) = NULL;
    MARK(e) = 0;
    return e;
  }

/* Delete an edge: */

void quad_destroy_edge(quad_arc_t e)
  {
    quad_arc_t f = SYM(e);
    if (ONEXT(e) != e) quad_splice(e, OPREV(e));
    if (ONEXT(f) != f) quad_splice(f, OPREV(f));  
    free((char *) ((e) & 0xfffffffcu));
  }

/* Splice primitive: */

void quad_splice(quad_arc_t a, quad_arc_t b)
  {
    quad_arc_t ta, tb;
    quad_arc_t alpha = ROT(ONEXT(a));
    quad_arc_t beta = ROT(ONEXT(b));

    ta = ONEXT(a);
    tb = ONEXT(b);
    ONEXT(a) = tb;
    ONEXT(b) = ta;
    ta = ONEXT(alpha);
    tb = ONEXT(beta);
    ONEXT(alpha) = tb;
    ONEXT(beta) = ta;    
  }

/* Enumerate edge quads */

void quad_do_enum (
    quad_arc_t a, 
    void visit_proc(quad_arc_t e, void *closure), 
    void *closure,
    unsigned mark
  );

unsigned next_mark = 1;

void quad_enum(
    quad_arc_t a, 
    void visit_proc(quad_arc_t e, void *closure), 
    void *closure
  )
  {
    unsigned mark = next_mark;
    next_mark++;
    if (next_mark == 0) next_mark = 1;
    quad_do_enum(a, visit_proc, closure, mark); 
  }

void quad_do_enum (
    quad_arc_t e, 
    void visit_proc(quad_arc_t e, void *closure), 
    void *closure,
    unsigned mark
  )
  {
    while (MARK(e) != mark)
      {
        visit_proc(e, closure);
        MARK(e) = mark;
        quad_do_enum (ONEXT(SYM(e)), visit_proc, closure, mark);
        e = ONEXT(e);
      }
  }

/*
** 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. 
**
** NOTE: this copyright notice does not claim to supersede any copyrights
** that may apply to the original DEC implementation of the quad-edge
** data structure.
**
** 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.
*/