<commit_before>//A triangulation routine based on Tipper's convex hull algorithm
//Computers and geoscience vol17 no 5 pp 597-632,1991
//Scaling is nlogn for random datasets
//<NAME> 31/08/01

// <NAME>. Q2 2002. 
// Debugging and extension of the algorithm.
// Binding to CHILD data structures.

#include <math.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define DEBUG_PRINT 1
#include "TipperTriangulator.h"

#define TIMING 1

// vector product (or cross product) of p0p1,p0p2
static
double vecprod(int p0,int p1,int p2,const point *p){
  return
    (p[p1].x-p[p0].x)*(p[p2].y-p[p0].y)
    -(p[p1].y-p[p0].y)*(p[p2].x-p[p0].x);
}

const point &point::operator=( const point &p ) {
  if ( &p != this ) {
    x=p.x; y=p.y; id=p.id;
  }
  return *this;
}

// we sort according x *and* y (if x are equal) so that
// vertically aligned point are ordered.
int point::operator < (const point& p) const {
  if (x == p.x)
    return y<p.y;
  return x<p.x;
}

#if defined(DEBUG_PRINT)
void point::print () const {cout << x << ' '<< y <<endl;}
#endif
void point::write(ofstream& f) const {f<<x<<' '<<y<<endl;}


#if defined(DEBUG_PRINT)
void edge::print(const point p[]) const {p[from].print();p[to].print();}
#endif
void edge::write(ofstream& f,const point p[]) const {p[from].write(f);p[to].write(f);}
bool edge::visible(const point p[],int i) const {
  //test whether an edge on the hull is visible from a point
  //rely on the fact that a) hull is anticlockwise oriented
  //b)data is positive x ordered

  // that is if angle(from-to,from-i) < 0 
  const double v = vecprod(from,to,i, p);
  if (v>=0)
    return false;
  return true;
}

static
bool needswap(int i1, int i2, int i3, int i4, const point p[]){
  const point 
    p1(p[i1]-p[i4]), p2(p[i1]-p[i3]), 
    p3(p[i2]-p[i4]), p4(p[i2]-p[i3]);
  double dt1=p1.dot(p2); double dt2=p3.dot(p4);
  //only do the square roots if we really need to - saves a bit of time
  if (dt1<0 || dt2<0){
    dt1 /= sqrt(p1.dot(p1)*p2.dot(p2));
    dt2 /= sqrt(p3.dot(p3)*p4.dot(p4));
    if ((dt1+dt2)<0)
      return true;
  }
  return false;
}

static
int tt_swap(int tint, edge e[], const point p[]){
  
  int& to = e[tint].to;
  int& from = e[tint].from;
  int& ret = e[tint].ret;
  int& ref = e[tint].ref;
  int& let = e[tint].let;
  int& lef = e[tint].lef;

  //edge swapping routine - each edge has four neighbour edges
  //left and attached to from node (lef) right attached to to node (ret) etc.
  //these edges may be oriented so that their from node is that of 
  // the current edge, or not
  //this routine takes the lions share of the CPU - hull construction by comparison
  //takes much less (by about a factor of ten!)
  if (ref==-1 || lef==-1 || let==-1 || ret==-1)return 0;
  //test orientation of left and right edges - store the indices of
  //points that are not part of the current edge
  const int leftp  = (e[lef].from==from) ? e[lef].to : e[lef].from;
  const int rightp = (e[ref].from==from) ? e[ref].to : e[ref].from;
  if (needswap(leftp, rightp, to, from, p)){
    //now swap the left and right edges of neighbouring edges
    //taking into account orientation
    if (e[ref].from == from){
      e[ref].lef=lef;
      e[ref].let=tint;
    }else{
      e[ref].ref=tint;
      e[ref].ret=lef;
    }
    if (e[lef].from==from){
      e[lef].ref=ref;
      e[lef].ret=tint;
    }else{
      e[lef].lef=tint;
      e[lef].let=ref;
    }
    if (e[ret].to==to){
      e[ret].lef=tint;
      e[ret].let=let;
    }else{
      e[ret].ref=let;
      e[ret].ret=tint;
    }
    if (e[let].to==to){
      e[let].ref=tint;
      e[let].ret=ret;
    }else{
      e[let].lef=ret;
      e[let].let=tint;
    }
    //change the end-points for the current edge
    to=rightp;
    from=leftp;
    //re-jig the edges
    int rf=ref;
    ref=lef;
    int rt=ret;
    ret=rf;
    int lt=let;
    let=rt;
    lef=lt;
    //examine the neighbouring edges for delauniness recursively - this is
    //a lot more efficient than trying to swap all edges right at the end.
    tt_swap(lef,e,p);
    tt_swap(let,e,p);
    tt_swap(ref,e,p);
    tt_swap(ret,e,p);
    return 1;
  }
  return 0;
}

class cyclist{
  //a fixed size linked cyclical list using arrays
  //the code here is not yet robust necessarily to list shrinking to zero
  //number of elements
  const cyclist &operator=( const cyclist & );  // assignment operator
  cyclist( const cyclist & );
  void delNext(int list_pos);
  void add(int ej);
  void invariant() const;
  void checkRange(int) const;
public:
  cyclist(int s);
  ~cyclist();
  int getEdge(int list_pos) const {
    checkRange(list_pos);<commit_msg>new cline and renka s flip test<commit_after>//A triangulation routine based on Tipper's convex hull algorithm
//Computers and geoscience vol17 no 5 pp 597-632,1991
//Scaling is nlogn for random datasets
//<NAME> 31/08/01

// <NAME>. Q2 2002. 
// Debugging and extension of the algorithm.
// Binding to CHILD data structures.

#include <math.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define DEBUG_PRINT 1
#include "TipperTriangulator.h"

#define TIMING 1

// vector product (or cross product) of p0p1,p0p2
static
double vecprod(int p0,int p1,int p2,const point *p){
  return
    (p[p1].x-p[p0].x)*(p[p2].y-p[p0].y)
    -(p[p1].y-p[p0].y)*(p[p2].x-p[p0].x);
}

const point &point::operator=( const point &p ) {
  if ( &p != this ) {
    x=p.x; y=p.y; id=p.id;
  }
  return *this;
}

// we sort according x *and* y (if x are equal) so that
// vertically aligned point are ordered.
int point::operator < (const point& p) const {
  if (x == p.x)
    return y<p.y;
  return x<p.x;
}

#if defined(DEBUG_PRINT)
void point::print () const {cout << x << ' '<< y <<endl;}
#endif
void point::write(ofstream& f) const {f<<x<<' '<<y<<endl;}


#if defined(DEBUG_PRINT)
void edge::print(const point p[]) const {p[from].print();p[to].print();}
#endif
void edge::write(ofstream& f,const point p[]) const {p[from].write(f);p[to].write(f);}
bool edge::visible(const point p[],int i) const {
  //test whether an edge on the hull is visible from a point
  //rely on the fact that a) hull is anticlockwise oriented
  //b)data is positive x ordered

  // that is if angle(from-to,from-i) < 0 
  const double v = vecprod(from,to,i, p);
  if (v>=0)
    return false;
  return true;
}

static
bool needswap(int i1, int i2, int i3, int i4, const point p[]){
  // i3 - i4 currently joined by diagonal.
  // i1 - i4 - i2 - i3 anti-clockwise
  // check if i1 lies inside the circumcircle for the triangle
  // i4-i2-i3 using the algorithm of Cline and Renka for roundoff
  // error.
  
  // t1=angle(i2,i3,i4), t2=angle(i1i4,i1i3), 
  // a swap is needed if t1+t2 > pi
  // Since t1+t2 < 2pi, this is equivalent to sin(t1+t2) < 0
  // This leads to: cos(t1)*cos(t2)+sin(t1)*sin(t2) < 0
  //
  // see discussion in:
  // Sloan, S.W. "A fast algorihtm for constructing Delaunay 
  // triangulations in the plane", Adv. Eng, Software,
  // 1987, 9(1)
  // <NAME>., <NAME>., "A Storage efficient method for 
  // construction of a Thiessen triangulation", Rocky Mountain 
  // Journal of Mathemetics, 1984, 14(119)

  const point 
    p1(p[i3]-p[i2]), p2(p[i4]-p[i2]),
    p3(p[i4]-p[i1]), p4(p[i3]-p[i1]); 
  const double cost1=p1.dot(p2), cost2=p3.dot(p4);

  if (cost1>=0 && cost2>=0)
    return false;
  if (cost1<0 && cost2<0)
    return true;
  const double sint1=vecprod(i2,i3,i4,p), sint2=vecprod(i1,i4,i3,p),
    sint1t2 = sint1*cost2+sint2*cost1;
  if (sint1t2 < 0)
    return true;
  return false;
}

static
int tt_swap(int tint, edge e[], const point p[]){
  
  int& to = e[tint].to;
  int& from = e[tint].from;
  int& ret = e[tint].ret;
  int& ref = e[tint].ref;
  int& let = e[tint].let;
  int& lef = e[tint].lef;

  //edge swapping routine - each edge has four neighbour edges
  //left and attached to from node (lef) right attached to to node (ret) etc.
  //these edges may be oriented so that their from node is that of 
  // the current edge, or not
  //this routine takes the lions share of the CPU - hull construction by comparison
  //takes much less (by about a factor of ten!)
  if (ref==-1 || lef==-1 || let==-1 || ret==-1)return 0;
  //test orientation of left and right edges - store the indices of
  //points that are not part of the current edge
  const int leftp  = (e[lef].from==from) ? e[lef].to : e[lef].from;
  const int rightp = (e[ref].from==from) ? e[ref].to : e[ref].from;

  if (needswap(leftp, rightp, to, from, p)){
    //now swap the left and right edges of neighbouring edges
    //taking into account orientation
    if (e[ref].from == from){
      e[ref].lef=lef;
      e[ref].let=tint;
    }else{
      e[ref].ref=tint;
      e[ref].ret=lef;
    }
    if (e[lef].from==from){
      e[lef].ref=ref;
      e[lef].ret=tint;
    }else{
      e[lef].lef=tint;
      e[lef].let=ref;
    }
    if (e[ret].to==to){
      e[ret].lef=tint;
      e[ret].let=let;
    }else{
      e[ret].ref=let;
      e[ret].ret=tint;
    }
    if (e[let].to==to){
      e[let].ref=tint;
      e[let].ret=ret;
    }else{
      e[let].lef=ret;
      e[let].let=tint;
    }
    //change the end-points for the current edge
    to=rightp;
    from=leftp;
    //re-jig the edges
    const int rf=ref;
    ref=lef;
    int rt=ret;
    ret=rf;
    const int lt=let;
    let=rt;
    lef=lt;
    //examine the neighbouring edges for delauniness recursively - this is
    //a lot more efficient than trying to swap all edges right at the end.
    tt_swap(lef,e,p);
    tt_swap(let,e,p);
    tt_swap(ref,e,p);
    tt_swap(ret,e,p);
    return 1;
  }
  return 0;
}

class cyclist{
  //a fixed size linked cyclical list using arrays
  //the code here is not yet robust necessarily to list shrinking to zero
  //number of elements
  const cyclist &operator=( const cyclist & );  // assignment operator
  cyclist( const cyclist & );
  void delNext(int list_pos);
  void add(int ej);
  void invariant() const;
  void checkRange(int) const;
public:
  cyclist(int s);
  ~cyclist();
  int getEdge(int list_pos) const {
    checkRange(list_pos);
{'fraction_non_alphanumeric': 0.1576603325415677, 'fraction_numerical': 0.02306017418844022, 'mean_word_length': 2.9767807949626133, 'pattern_counts': {'":': 0, '<': 68, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '396820', 'n_tokens_mistral': 4055, 'n_tokens_neox': 3906, 'n_words': 1172}