// DEMO: 2D-tree in C++, from last day of class
#include <cassert>
#include <cmath>

typedef enum feature_class {
    Airport,
    Arch,
    Area,
    Arroyo,
    Bar,
    Basin,
    Bay,
    Beach,
    Bench,
    Bend,
    Bridge,
    Building,
    Canal,
    Cape,
    Cemetery,
    Census,
    Channel,
    Church,
    Civil,
    Cliff,
    Crater,
    Crossing,
    Dam,
    Falls,
    Flat,
    Forest,
    Gap,
    Glacier,
    Gut,
    Harbor,
    Hospital,
    Island,
    Isthmus,
    Lake,
    Lava,
    Levee,
    Locale,
    Military,
    Mine,
    Oilfield,
    Park,
    Pillar,
    Plain,
    Populated_Place,
    Post_Office,
    Range,
    Rapids,
    Reserve,
    Reservoir,
    Ridge,
    School,
    Sea,
    Slope,
    Spring,
    Stream,
    Summit,
    Swamp,
    Tower,
    Trail,
    Tunnel,
    Unknown,
    Valley,
    Well,
    Woods
} FeatureClass;


class Mappoint {
public:
  double x, y; // (x, y) are location in map coordinates
  FeatureClass feature;
  const char *name;
};
  

class HBoundary;
class VBoundary;
class Tree2D;

class HBoundary {
public:
  Tree2D *above;
  double y;
  Tree2D *below;
};

class VBoundary {
public:
  Tree2D *left;
  double x;
  Tree2D *right;
};

typedef enum { An_HBoundary, A_VBoundary, A_Point } TreeTag;

/*
DATA DEFINITION:
  A Tree2D is one of:
    - A Mappoint
    - An HBoundary
    - A VBoundary
  as identified by the 'choice' field
*/

class Tree2D {
public:
  TreeTag choice;
  union {
    HBoundary hboundary;
    VBoundary vboundary;
    Mappoint  *point;
  };
};

Tree2D *make_h_boundary(Tree2D *t1, double hline, Tree2D *t2) {
  Tree2D *t = new Tree2D;
  t->choice = An_HBoundary;
  t->hboundary.above = t1;
  t->hboundary.y     = hline;
  t->hboundary.below = t2;
  return t;
}

double square(double x) {
  return x * x;
}

// return the Euclidean distance between the given (x, y) and the given point
double point_distance (double x, double y, Mappoint *pt) {
  return sqrt (square (pt->x - x) + square (pt->y - y));
}


// find the point in the given trees that is closest to the given (x, y),
// where all points in the far tree are at least distance delta away from (x, y)
Mappoint *near_or_far(double x, double y, double delta,
                            Tree2D *near, Tree2D *far);


// find the point in 'tree' that is closest to (x, y)
Mappoint *nearest_point(double x, double y, Tree2D *tree) {
  // N.B. Choice code is completely unsafe---you as
  // programmer must get this code right!
  switch (tree->choice) {
  case A_Point:
    return tree->point;

  case An_HBoundary:
    if (y < tree->hboundary.y)
      return near_or_far (x, y, tree->hboundary.y - y,
                          tree->hboundary.above, tree->hboundary.below);
    else
      return near_or_far (x, y, y - tree->hboundary.y,
                          tree->hboundary.below, tree->hboundary.above);

  case A_VBoundary:
    if (x < tree->vboundary.x)
      return near_or_far (x, x, tree->vboundary.x - x,
                          tree->vboundary.left, tree->vboundary.right);
    else
      return near_or_far (x, x, x - tree->vboundary.x,
                          tree->vboundary.right, tree->vboundary.left);
  }

  assert(false);
}


// return the point in the given trees that is closest to the given (x, y),
// where all points in the far tree are at least distance delta from (x, y)
Mappoint *near_or_far(double x, double y, double delta,
                      Tree2D *near, Tree2D *far)
{
  Mappoint *nearpt = nearest_point (x, y, near);
  double how_far = point_distance (x, y, nearpt);
  if (how_far <= delta)
    return nearpt;
  else {
    Mappoint *farpt = nearest_point (x, y, far);
    if (point_distance (x, y, farpt) < how_far)
      return farpt;
    else
      return nearpt;
  }
}