text:
// Copyright (c) 2017, 2020, Oracle and/or its affiliates.
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, version 2.0,
// as published by the Free Software Foundation.
//
// This program is also distributed with certain software (including
// but not limited to OpenSSL) that is licensed under separate terms,
// as designated in a particular file or component or in included license
// documentation.  The authors of MySQL hereby grant you an additional
// permission to link the program and your derivative works with the
// separately licensed software that they have included with MySQL.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License, version 2.0, for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA.

/// @file
///
/// This file implements the within functor and function.

#include <cmath>  // std::isfinite
#include <limits>
#include <memory>  // std::unique_ptr

#include <boost/geometry.hpp>

#include "sql/dd/types/spatial_reference_system.h"  // dd::Spatial_reference_system
#include "sql/gis/box.h"
#include "sql/gis/box_traits.h"
#include "sql/gis/difference_functor.h"
#include "sql/gis/equals_functor.h"
#include "sql/gis/gc_utils.h"
#include "sql/gis/geometries.h"
#include "sql/gis/geometries_traits.h"
#include "sql/gis/intersects_functor.h"
#include "sql/gis/mbr_utils.h"
#include "sql/gis/relops.h"
#include "sql/gis/within_functor.h"
#include "sql/sql_exception_handler.h"  // handle_gis_exception
#include "template_utils.h"             // down_cast

namespace bg = boost::geometry;

namespace gis {

Within::Within(double semi_major, double semi_minor)
    : m_semi_major(semi_major),
      m_semi_minor(semi_minor),
      m_geographic_pl_pa_strategy(
          bg::srs::spheroid<double>(semi_major, semi_minor)),
      m_geographic_ll_la_aa_strategy(
          bg::srs::spheroid<double>(semi_major, semi_minor)) {}

bool Within::operator()(const Geometry *g1, const Geometry *g2) const {
  return apply(*this, g1, g2);
}

bool Within::operator()(const Box *b1, const Box *b2) const {
  DBUG_ASSERT(b1->coordinate_system() == b2->coordinate_system());
  switch (b1->coordinate_system()) {
    case Coordinate_system::kCartesian:
      return eval(down_cast<const Cartesian_box *>(b1),
                  down_cast<const Cartesian_box *>(b2));
    case Coordinate_system::kGeographic:
      return eval(down_cast<const Geographic_box *>(b1),
                  down_cast<const Geographic_box *>(b2));
  }

  DBUG_ASSERT(false);
  return false;
}

bool Within::eval(const Geometry *g1, const Geometry *g2) const {
  // All parameter type combinations have been implemented.
  DBUG_ASSERT(false);
  throw not_implemented_exception::for_non_projected(*g1, *g2);
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_point, *)

bool Within::eval(const Cartesian_point *g1, const Cartesian_point *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_point *g1,
                  const Cartesian_linestring *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_point *g1,
                  const Cartesian_polygon *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_point *g1,
                  const Cartesian_geometrycollection *g2) const {
  // g1 must be within one of the elements of g2.
  for (auto g : *g2)
    if ((*this)(g1, g)) return true;
  return false;
}

bool Within::eval(const Cartesian_point *g1,
                  const Cartesian_multipoint *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_point *g1,
                  const Cartesian_multilinestring *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_point *g1,
                  const Cartesian_multipolygon *g2) const {
  return bg::within(*g1, *g2);
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_linestring, *)

bool Within::eval(const Cartesian_linestring *, const Cartesian_point *) const {
  // A linestring can never be within a point.
  return false;
}

bool Within::eval(const Cartesian_linestring *g1,
                  const Cartesian_linestring *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_linestring *g1,
                  const Cartesian_polygon *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_linestring *g1,
                  const Cartesian_geometrycollection *g2) const {
  // For g1 to be within g2, no point of g1 may be in the exterior of g2 and at
  // least one point of the interior of g1 has to be within the interior of g2.

  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);

  Difference difference(m_semi_major, m_semi_minor);
  std::unique_ptr<Multilinestring> g1_diff_g2(new Cartesian_multilinestring());
  g1_diff_g2.reset(down_cast<Cartesian_multilinestring *>(
      difference(g1, down_cast<Cartesian_multilinestring *>(g2_mls.get()))));
  g1_diff_g2.reset(down_cast<Cartesian_multilinestring *>(
      difference(down_cast<Cartesian_multilinestring *>(g1_diff_g2.get()),
                 down_cast<Cartesian_multipolygon *>(g2_mpy.get()))));

  boost::geometry::de9im::mask mask("T********");
  return g1_diff_g2->empty() &&
         (bg::relate(*g1, *down_cast<Cartesian_multilinestring *>(g2_mls.get()),
                     mask) ||
          bg::relate(*g1, *down_cast<Cartesian_multipolygon *>(g2_mpy.get()),
                     mask));
}

bool Within::eval(const Cartesian_linestring *,
                  const Cartesian_multipoint *) const {
  // A linestring can never be within a multipoint.
  return false;
}

bool Within::eval(const Cartesian_linestring *g1,
                  const Cartesian_multilinestring *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_linestring *g1,
                  const Cartesian_multipolygon *g2) const {
  return bg::within(*g1, *g2);
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_polygon, *)

bool Within::eval(const Cartesian_polygon *, const Cartesian_point *) const {
  // A polygon can never be within a point.
  return false;
}

bool Within::eval(const Cartesian_polygon *,
                  const Cartesian_linestring *) const {
  // A polygon can never be within a linestring.
  return false;
}

bool Within::eval(const Cartesian_polygon *g1,
                  const Cartesian_polygon *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_polygon *g1,
                  const Cartesian_geometrycollection *g2) const {
  // Polygons can only be within other polygons or multipolygons, so we can
  // ignore points and linestrings. g1 is within g2 if g1 is within the union
  // multipolygon of g2.
  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);
  return eval(g1, down_cast<Cartesian_multipolygon *>(g2_mpy.get()));
}

bool Within::eval(const Cartesian_polygon *,
                  const Cartesian_multipoint *) const {
  // A polygon can never be within a multipoint.
  return false;
}

bool Within::eval(const Cartesian_polygon *,
                  const Cartesian_multilinestring *) const {
  // A polygon can never be within a multilinestring.
  return false;
}

bool Within::eval(const Cartesian_polygon *g1,
                  const Cartesian_multipolygon *g2) const {
  return bg::within(*g1, *g2);
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_geometrycollection, *)

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_point *g2) const {
  Equals equals(m_semi_major, m_semi_minor);
  return equals(g1, g2);
}

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_linestring *g2) const {
  // g1 is within g2 if g1 contains only points and linestrings. One of the
  // elements of g1 must be within g2, the rest must be covered by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (!g1_mpy->empty()) return false;

  if (eval(down_cast<Cartesian_multipoint *>(g1_mpt.get()), g2))
    return g1_mls->empty() ||
           bg::covered_by(*down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                          *g2);
  if (eval(down_cast<Cartesian_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Cartesian_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2)) return false;
    return true;
  }
  return false;
}

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_polygon *g2) const {
  // At least one element of g1 has to be within g2. The rest have to be covered
  // by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (eval(down_cast<Cartesian_multipoint *>(g1_mpt.get()), g2)) {
    return (g1_mls->empty() ||
            bg::covered_by(
                *down_cast<Cartesian_multilinestring *>(g1_mls.get()), *g2)) &&
           (g1_mpy->empty() ||
            bg::covered_by(*down_cast<Cartesian_multipolygon *>(g1_mpy.get()),
                           *g2));
  }
  if (eval(down_cast<Cartesian_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Cartesian_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2)) return false;
    return g1_mpy->empty() ||
           bg::covered_by(*down_cast<Cartesian_multipolygon *>(g1_mpy.get()),
                          *g2);
  }
  if (eval(down_cast<Cartesian_multipolygon *>(g1_mpy.get()), g2)) {
    for (auto &pt : *down_cast<Cartesian_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2)) return false;
    return g1_mls->empty() ||
           bg::covered_by(*down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                          *g2);
  }
  return false;
}

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_geometrycollection *g2) const {
  // At least one element of g1 has to be within g2. The rest have to be covered
  // by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);

  // Check that no part of g1 is in the exterior of g2.
  Difference difference(m_semi_major, m_semi_minor);
  std::unique_ptr<Cartesian_multipoint> g1_mpt_diff_g2(
      new Cartesian_multipoint());
  g1_mpt_diff_g2.reset(down_cast<Cartesian_multipoint *>(
      difference(down_cast<Cartesian_multipoint *>(g1_mpt.get()),
                 down_cast<Cartesian_multipoint *>(g2_mpt.get()))));
  g1_mpt_diff_g2.reset(down_cast<Cartesian_multipoint *>(
      difference(g1_mpt_diff_g2.get(),
                 down_cast<Cartesian_multilinestring *>(g2_mls.get()))));
  g1_mpt_diff_g2.reset(down_cast<Cartesian_multipoint *>(
      difference(g1_mpt_diff_g2.get(),
                 down_cast<Cartesian_multipolygon *>(g2_mpy.get()))));
  if (!g1_mpt_diff_g2->empty()) return false;

  std::unique_ptr<Cartesian_multilinestring> g1_mls_diff_g2(
      new Cartesian_multilinestring());
  g1_mls_diff_g2.reset(down_cast<Cartesian_multilinestring *>(
      difference(down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                 down_cast<Cartesian_multilinestring *>(g2_mls.get()))));
  g1_mls_diff_g2.reset(down_cast<Cartesian_multilinestring *>(
      difference(g1_mls_diff_g2.get(),
                 down_cast<Cartesian_multipolygon *>(g2_mpy.get()))));
  if (!g1_mls_diff_g2->empty()) return false;

  std::unique_ptr<Cartesian_multipolygon> g1_mpy_diff_g2(
      new Cartesian_multipolygon());
  g1_mpy_diff_g2.reset(down_cast<Cartesian_multipolygon *>(
      difference(down_cast<Cartesian_multipolygon *>(g1_mpy.get()),
                 down_cast<Cartesian_multipolygon *>(g2_mpy.get()))));
  if (!g1_mpy_diff_g2->empty()) return false;

  // Check that the interiors of g1 and g2 have at least one point in common.
  boost::geometry::de9im::mask mask("T********");
  return eval(down_cast<Cartesian_multipoint *>(g1_mpt.get()), g2) ||
         bg::relate(*down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                    *down_cast<Cartesian_multilinestring *>(g2_mls.get()),
                    mask) ||
         bg::relate(*down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                    *down_cast<Cartesian_multipolygon *>(g2_mpy.get()), mask) ||
         bg::relate(*down_cast<Cartesian_multipolygon *>(g1_mpy.get()),
                    *down_cast<Cartesian_multipolygon *>(g2_mpy.get()), mask);
}

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_multipoint *g2) const {
  // g1 is within g2 if g1 contains only points and those points are within g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);
  return g1_mls->empty() && g1_mpy->empty() &&
         eval(down_cast<Cartesian_multipoint *>(g1_mpt.get()), g2);
}

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_multilinestring *g2) const {
  // g1 is within g2 if g1 contains only points and linestrings. One of the
  // elements of g1 must be within g2, the rest must be covered by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (!g1_mpy->empty()) return false;

  if (eval(down_cast<Cartesian_multipoint *>(g1_mpt.get()), g2))
    return g1_mls->empty() ||
           bg::covered_by(*down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                          *g2);
  if (eval(down_cast<Cartesian_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Cartesian_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2)) return false;
    return true;
  }
  return false;
}

bool Within::eval(const Cartesian_geometrycollection *g1,
                  const Cartesian_multipolygon *g2) const {
  // At least one element of g1 has to be within g2. The rest have to be covered
  // by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (eval(down_cast<Cartesian_multipoint *>(g1_mpt.get()), g2)) {
    return (g1_mls->empty() ||
            bg::covered_by(
                *down_cast<Cartesian_multilinestring *>(g1_mls.get()), *g2)) &&
           (g1_mpy->empty() ||
            bg::covered_by(*down_cast<Cartesian_multipolygon *>(g1_mpy.get()),
                           *g2));
  }
  if (eval(down_cast<Cartesian_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Cartesian_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2)) return false;
    return g1_mpy->empty() ||
           bg::covered_by(*down_cast<Cartesian_multipolygon *>(g1_mpy.get()),
                          *g2);
  }
  if (eval(down_cast<Cartesian_multipolygon *>(g1_mpy.get()), g2)) {
    for (auto &pt : *down_cast<Cartesian_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2)) return false;
    return g1_mls->empty() ||
           bg::covered_by(*down_cast<Cartesian_multilinestring *>(g1_mls.get()),
                          *g2);
  }
  return false;
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_multipoint, *)

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_point *g2) const {
  Equals equals(m_semi_major, m_semi_minor);
  return equals(g1, g2);
}

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_linestring *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2);
      if (!within)
        intersects = bg::intersects(pt, *g2);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_polygon *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2);
      if (!within)
        intersects = bg::intersects(pt, *g2);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_geometrycollection *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  Intersects intersects_func(m_semi_major, m_semi_minor);
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = eval(&pt, g2);
      if (!within)
        intersects = intersects_func(&pt, g2);
      else
        intersects = true;
    } else {
      intersects = intersects_func(&pt, g2);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_multipoint *g2) const {
  for (auto &pt : *g1)
    if (!bg::within(pt, *g2)) return false;
  return true;
}

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_multilinestring *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2);
      if (!within)
        intersects = bg::intersects(pt, *g2);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Cartesian_multipoint *g1,
                  const Cartesian_multipolygon *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2);
      if (!within)
        intersects = bg::intersects(pt, *g2);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_multilinestring, *)

bool Within::eval(const Cartesian_multilinestring *,
                  const Cartesian_point *) const {
  // A multilinestring can never be within a point.
  return false;
}

bool Within::eval(const Cartesian_multilinestring *g1,
                  const Cartesian_linestring *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_multilinestring *g1,
                  const Cartesian_polygon *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_multilinestring *g1,
                  const Cartesian_geometrycollection *g2) const {
  // For g1 to be within g2, no point of g1 may be in the exterior of g2 and at
  // least one point of the interior of g1 has to be within the interior of g2.

  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);

  Difference difference(m_semi_major, m_semi_minor);
  std::unique_ptr<Cartesian_multilinestring> g1_diff_g2(
      new Cartesian_multilinestring());
  g1_diff_g2.reset(down_cast<Cartesian_multilinestring *>(
      difference(g1, down_cast<Cartesian_multilinestring *>(g2_mls.get()))));
  g1_diff_g2.reset(down_cast<Cartesian_multilinestring *>(difference(
      g1_diff_g2.get(), down_cast<Cartesian_multipolygon *>(g2_mpy.get()))));

  boost::geometry::de9im::mask mask("T********");
  return g1_diff_g2->empty() &&
         (bg::relate(*g1, *down_cast<Cartesian_multilinestring *>(g2_mls.get()),
                     mask) ||
          bg::relate(*g1, *down_cast<Cartesian_multipolygon *>(g2_mpy.get()),
                     mask));
}

bool Within::eval(const Cartesian_multilinestring *,
                  const Cartesian_multipoint *) const {
  // A multilinestring can never be within a multipoint.
  return false;
}

bool Within::eval(const Cartesian_multilinestring *g1,
                  const Cartesian_multilinestring *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_multilinestring *g1,
                  const Cartesian_multipolygon *g2) const {
  return bg::within(*g1, *g2);
}

//////////////////////////////////////////////////////////////////////////////

// within(Cartesian_multipolygon, *)

bool Within::eval(const Cartesian_multipolygon *,
                  const Cartesian_point *) const {
  // A multipolygon can never be within a point.
  return false;
}

bool Within::eval(const Cartesian_multipolygon *,
                  const Cartesian_linestring *) const {
  // A multipolygon can never be within a linestring.
  return false;
}

bool Within::eval(const Cartesian_multipolygon *g1,
                  const Cartesian_polygon *g2) const {
  return bg::within(*g1, *g2);
}

bool Within::eval(const Cartesian_multipolygon *g1,
                  const Cartesian_geometrycollection *g2) const {
  // A multipolygon may not be within the points and linestrings of g2, so the
  // only way a multipolygon is within a geometrycollectin, is if it's within
  // the union multipolygon of the geometrycollection.
  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);
  return eval(g1, down_cast<Cartesian_multipolygon *>(g2_mpy.get()));
}

bool Within::eval(const Cartesian_multipolygon *,
                  const Cartesian_multipoint *) const {
  // A multipolygon can never be within a multipoint.
  return false;
}

bool Within::eval(const Cartesian_multipolygon *,
                  const Cartesian_multilinestring *) const {
  // A multipolygon can never be within a multilinestring.
  return false;
}

bool Within::eval(const Cartesian_multipolygon *g1,
                  const Cartesian_multipolygon *g2) const {
  return bg::within(*g1, *g2);
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_point, *)

bool Within::eval(const Geographic_point *g1,
                  const Geographic_point *g2) const {
  // Default strategy is OK. P/P computations do not depend on shape of
  // ellipsoid.
  return bg::within(*g1, *g2);
}

bool Within::eval(const Geographic_point *g1,
                  const Geographic_linestring *g2) const {
  return bg::within(*g1, *g2, m_geographic_pl_pa_strategy);
}

bool Within::eval(const Geographic_point *g1,
                  const Geographic_polygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_pl_pa_strategy);
}

bool Within::eval(const Geographic_point *g1,
                  const Geographic_geometrycollection *g2) const {
  // g1 must be within one of the elements of g2.
  for (auto g : *g2)
    if ((*this)(g1, g)) return true;
  return false;
}

bool Within::eval(const Geographic_point *g1,
                  const Geographic_multipoint *g2) const {
  // Default strategy is OK. P/P computations do not depend on shape of
  // ellipsoid.
  return bg::within(*g1, *g2);
}

bool Within::eval(const Geographic_point *g1,
                  const Geographic_multilinestring *g2) const {
  return bg::within(*g1, *g2, m_geographic_pl_pa_strategy);
}

bool Within::eval(const Geographic_point *g1,
                  const Geographic_multipolygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_pl_pa_strategy);
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_linestring, *)

bool Within::eval(const Geographic_linestring *,
                  const Geographic_point *) const {
  // A linestring can never be within a point.
  return false;
}

bool Within::eval(const Geographic_linestring *g1,
                  const Geographic_linestring *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_linestring *g1,
                  const Geographic_polygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_linestring *g1,
                  const Geographic_geometrycollection *g2) const {
  // For g1 to be within g2, no point of g1 may be in the exterior of g2 and at
  // least one point of the interior of g1 has to be within the interior of g2.

  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);

  Difference difference(m_semi_major, m_semi_minor);
  std::unique_ptr<Multilinestring> g1_diff_g2(new Geographic_multilinestring());
  g1_diff_g2.reset(down_cast<Geographic_multilinestring *>(
      difference(g1, down_cast<Geographic_multilinestring *>(g2_mls.get()))));
  g1_diff_g2.reset(down_cast<Geographic_multilinestring *>(
      difference(down_cast<Geographic_multilinestring *>(g1_diff_g2.get()),
                 down_cast<Geographic_multipolygon *>(g2_mpy.get()))));

  boost::geometry::de9im::mask mask("T********");
  return g1_diff_g2->empty() &&
         (bg::relate(*g1,
                     *down_cast<Geographic_multilinestring *>(g2_mls.get()),
                     mask, m_geographic_ll_la_aa_strategy) ||
          bg::relate(*g1, *down_cast<Geographic_multipolygon *>(g2_mpy.get()),
                     mask, m_geographic_ll_la_aa_strategy));
}

bool Within::eval(const Geographic_linestring *,
                  const Geographic_multipoint *) const {
  // A linestring can never be within a multipoint.
  return false;
}

bool Within::eval(const Geographic_linestring *g1,
                  const Geographic_multilinestring *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_linestring *g1,
                  const Geographic_multipolygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_polygon, *)

bool Within::eval(const Geographic_polygon *, const Geographic_point *) const {
  // A polygon can never be within a point.
  return false;
}

bool Within::eval(const Geographic_polygon *,
                  const Geographic_linestring *) const {
  // A polygon can never be within a linestring.
  return false;
}

bool Within::eval(const Geographic_polygon *g1,
                  const Geographic_polygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_polygon *g1,
                  const Geographic_geometrycollection *g2) const {
  // Polygons can only be within other polygons or multipolygons, so we can
  // ignore points and linestrings. g1 is within g2 if g1 is within the union
  // multipolygon of g2.
  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);
  return eval(g1, down_cast<Geographic_multipolygon *>(g2_mpy.get()));
}

bool Within::eval(const Geographic_polygon *,
                  const Geographic_multipoint *) const {
  // A polygon can never be within a multipoint.
  return false;
}

bool Within::eval(const Geographic_polygon *,
                  const Geographic_multilinestring *) const {
  // A polygon can never be within a multilinestring.
  return false;
}

bool Within::eval(const Geographic_polygon *g1,
                  const Geographic_multipolygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_geometrycollection, *)

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_point *g2) const {
  Equals equals(m_semi_major, m_semi_minor);
  return equals(g1, g2);
}

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_linestring *g2) const {
  // g1 is within g2 if g1 contains only points and linestrings. One of the
  // elements of g1 must be within g2, the rest must be covered by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (!g1_mpy->empty()) return false;

  if (eval(down_cast<Geographic_multipoint *>(g1_mpt.get()), g2))
    return g1_mls->empty() ||
           bg::covered_by(
               *down_cast<Geographic_multilinestring *>(g1_mls.get()), *g2,
               m_geographic_ll_la_aa_strategy);
  if (eval(down_cast<Geographic_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Geographic_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2, m_geographic_pl_pa_strategy)) return false;
    return true;
  }
  return false;
}

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_polygon *g2) const {
  // At least one element of g1 has to be within g2. The rest have to be covered
  // by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (eval(down_cast<Geographic_multipoint *>(g1_mpt.get()), g2)) {
    return (g1_mls->empty() ||
            bg::covered_by(
                *down_cast<Geographic_multilinestring *>(g1_mls.get()), *g2,
                m_geographic_ll_la_aa_strategy)) &&
           (g1_mpy->empty() ||
            bg::covered_by(*down_cast<Geographic_multipolygon *>(g1_mpy.get()),
                           *g2, m_geographic_ll_la_aa_strategy));
  }
  if (eval(down_cast<Geographic_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Geographic_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2, m_geographic_pl_pa_strategy)) return false;
    return g1_mpy->empty() ||
           bg::covered_by(*down_cast<Geographic_multipolygon *>(g1_mpy.get()),
                          *g2, m_geographic_ll_la_aa_strategy);
  }
  if (eval(down_cast<Geographic_multipolygon *>(g1_mpy.get()), g2)) {
    for (auto &pt : *down_cast<Geographic_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2, m_geographic_pl_pa_strategy)) return false;
    return g1_mls->empty() ||
           bg::covered_by(
               *down_cast<Geographic_multilinestring *>(g1_mls.get()), *g2,
               m_geographic_ll_la_aa_strategy);
  }
  return false;
}

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_geometrycollection *g2) const {
  // At least one element of g1 has to be within g2. The rest have to be covered
  // by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);

  // Check that no part of g1 is in the exterior of g2.
  Difference difference(m_semi_major, m_semi_minor);
  std::unique_ptr<Geographic_multipoint> g1_mpt_diff_g2(
      new Geographic_multipoint());
  g1_mpt_diff_g2.reset(down_cast<Geographic_multipoint *>(
      difference(down_cast<Geographic_multipoint *>(g1_mpt.get()),
                 down_cast<Geographic_multipoint *>(g2_mpt.get()))));
  g1_mpt_diff_g2.reset(down_cast<Geographic_multipoint *>(
      difference(g1_mpt_diff_g2.get(),
                 down_cast<Geographic_multilinestring *>(g2_mls.get()))));
  g1_mpt_diff_g2.reset(down_cast<Geographic_multipoint *>(
      difference(g1_mpt_diff_g2.get(),
                 down_cast<Geographic_multipolygon *>(g2_mpy.get()))));
  if (!g1_mpt_diff_g2->empty()) return false;

  std::unique_ptr<Geographic_multilinestring> g1_mls_diff_g2(
      new Geographic_multilinestring());
  g1_mls_diff_g2.reset(down_cast<Geographic_multilinestring *>(
      difference(down_cast<Geographic_multilinestring *>(g1_mls.get()),
                 down_cast<Geographic_multilinestring *>(g2_mls.get()))));
  g1_mls_diff_g2.reset(down_cast<Geographic_multilinestring *>(
      difference(g1_mls_diff_g2.get(),
                 down_cast<Geographic_multipolygon *>(g2_mpy.get()))));
  if (!g1_mls_diff_g2->empty()) return false;

  std::unique_ptr<Geographic_multipolygon> g1_mpy_diff_g2(
      new Geographic_multipolygon());
  g1_mpy_diff_g2.reset(down_cast<Geographic_multipolygon *>(
      difference(down_cast<Geographic_multipolygon *>(g1_mpy.get()),
                 down_cast<Geographic_multipolygon *>(g2_mpy.get()))));
  if (!g1_mpy_diff_g2->empty()) return false;

  // Check that the interiors of g1 and g2 have at least one point in common.
  boost::geometry::de9im::mask mask("T********");
  return eval(down_cast<Geographic_multipoint *>(g1_mpt.get()), g2) ||
         bg::relate(*down_cast<Geographic_multilinestring *>(g1_mls.get()),
                    *down_cast<Geographic_multilinestring *>(g2_mls.get()),
                    mask, m_geographic_ll_la_aa_strategy) ||
         bg::relate(*down_cast<Geographic_multilinestring *>(g1_mls.get()),
                    *down_cast<Geographic_multipolygon *>(g2_mpy.get()), mask,
                    m_geographic_ll_la_aa_strategy) ||
         bg::relate(*down_cast<Geographic_multipolygon *>(g1_mpy.get()),
                    *down_cast<Geographic_multipolygon *>(g2_mpy.get()), mask,
                    m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_multipoint *g2) const {
  // g1 is within g2 if g1 contains only points and those points are within g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);
  return g1_mls->empty() && g1_mpy->empty() &&
         eval(down_cast<Geographic_multipoint *>(g1_mpt.get()), g2);
}

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_multilinestring *g2) const {
  // g1 is within g2 if g1 contains only points and linestrings. One of the
  // elements of g1 must be within g2, the rest must be covered by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (!g1_mpy->empty()) return false;

  if (eval(down_cast<Geographic_multipoint *>(g1_mpt.get()), g2))
    return g1_mls->empty() ||
           bg::covered_by(
               *down_cast<Geographic_multilinestring *>(g1_mls.get()), *g2,
               m_geographic_ll_la_aa_strategy);
  if (eval(down_cast<Geographic_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Geographic_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2, m_geographic_pl_pa_strategy)) return false;
    return true;
  }
  return false;
}

bool Within::eval(const Geographic_geometrycollection *g1,
                  const Geographic_multipolygon *g2) const {
  // At least one element of g1 has to be within g2. The rest have to be covered
  // by g2.
  std::unique_ptr<Multipoint> g1_mpt;
  std::unique_ptr<Multilinestring> g1_mls;
  std::unique_ptr<Multipolygon> g1_mpy;
  split_gc(g1, &g1_mpt, &g1_mls, &g1_mpy);
  gc_union(m_semi_major, m_semi_minor, &g1_mpt, &g1_mls, &g1_mpy);

  if (eval(down_cast<Geographic_multipoint *>(g1_mpt.get()), g2)) {
    return (g1_mls->empty() ||
            bg::covered_by(
                *down_cast<Geographic_multilinestring *>(g1_mls.get()), *g2,
                m_geographic_ll_la_aa_strategy)) &&
           (g1_mpy->empty() ||
            bg::covered_by(*down_cast<Geographic_multipolygon *>(g1_mpy.get()),
                           *g2, m_geographic_ll_la_aa_strategy));
  }
  if (eval(down_cast<Geographic_multilinestring *>(g1_mls.get()), g2)) {
    for (auto &pt : *down_cast<Geographic_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2, m_geographic_pl_pa_strategy)) return false;
    return g1_mpy->empty() ||
           bg::covered_by(*down_cast<Geographic_multipolygon *>(g1_mpy.get()),
                          *g2, m_geographic_ll_la_aa_strategy);
  }
  if (eval(down_cast<Geographic_multipolygon *>(g1_mpy.get()), g2)) {
    for (auto &pt : *down_cast<Geographic_multipoint *>(g1_mpt.get()))
      if (!bg::covered_by(pt, *g2, m_geographic_pl_pa_strategy)) return false;
    return g1_mls->empty() ||
           bg::covered_by(
               *down_cast<Geographic_multilinestring *>(g1_mls.get()), *g2,
               m_geographic_ll_la_aa_strategy);
  }
  return false;
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_multipoint, *)

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_point *g2) const {
  Equals equals(m_semi_major, m_semi_minor);
  return equals(g1, g2);
}

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_linestring *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2, m_geographic_pl_pa_strategy);
      if (!within)
        intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_polygon *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2, m_geographic_pl_pa_strategy);
      if (!within)
        intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_geometrycollection *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  Intersects intersects_func(m_semi_major, m_semi_minor);
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = eval(&pt, g2);
      if (!within)
        intersects = intersects_func(&pt, g2);
      else
        intersects = true;
    } else {
      intersects = intersects_func(&pt, g2);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_multipoint *g2) const {
  // Default strategy is OK. P/P computations do not depend on shape of
  // ellipsoid.
  for (auto &pt : *g1)
    if (!bg::within(pt, *g2)) return false;
  return true;
}

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_multilinestring *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2, m_geographic_pl_pa_strategy);
      if (!within)
        intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

bool Within::eval(const Geographic_multipoint *g1,
                  const Geographic_multipolygon *g2) const {
  // At least one point in g1 must be within g2. The rest has to intersect g2.
  bool within = false;
  bool intersects = false;
  for (auto &pt : *g1) {
    if (!within) {
      within = bg::within(pt, *g2, m_geographic_pl_pa_strategy);
      if (!within)
        intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
      else
        intersects = true;
    } else {
      intersects = bg::intersects(pt, *g2, m_geographic_pl_pa_strategy);
    }
    if (!intersects) break;
  }
  return (within && intersects);
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_multilinestring, *)

bool Within::eval(const Geographic_multilinestring *,
                  const Geographic_point *) const {
  // A multilinestring can never be within a point.
  return false;
}

bool Within::eval(const Geographic_multilinestring *g1,
                  const Geographic_linestring *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_multilinestring *g1,
                  const Geographic_polygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_multilinestring *g1,
                  const Geographic_geometrycollection *g2) const {
  // For g1 to be within g2, no point of g1 may be in the exterior of g2 and at
  // least one point of the interior of g1 has to be within the interior of g2.

  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);

  Difference difference(m_semi_major, m_semi_minor);
  std::unique_ptr<Geographic_multilinestring> g1_diff_g2(
      new Geographic_multilinestring());
  g1_diff_g2.reset(down_cast<Geographic_multilinestring *>(
      difference(g1, down_cast<Geographic_multilinestring *>(g2_mls.get()))));
  g1_diff_g2.reset(down_cast<Geographic_multilinestring *>(difference(
      g1_diff_g2.get(), down_cast<Geographic_multipolygon *>(g2_mpy.get()))));

  boost::geometry::de9im::mask mask("T********");
  return g1_diff_g2->empty() &&
         (bg::relate(*g1,
                     *down_cast<Geographic_multilinestring *>(g2_mls.get()),
                     mask, m_geographic_ll_la_aa_strategy) ||
          bg::relate(*g1, *down_cast<Geographic_multipolygon *>(g2_mpy.get()),
                     mask, m_geographic_ll_la_aa_strategy));
}

bool Within::eval(const Geographic_multilinestring *,
                  const Geographic_multipoint *) const {
  // A multilinestring can never be within a multipoint.
  return false;
}

bool Within::eval(const Geographic_multilinestring *g1,
                  const Geographic_multilinestring *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_multilinestring *g1,
                  const Geographic_multipolygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

//////////////////////////////////////////////////////////////////////////////

// within(Geographic_multipolygon, *)

bool Within::eval(const Geographic_multipolygon *,
                  const Geographic_point *) const {
  // A multipolygon can never be within a point.
  return false;
}

bool Within::eval(const Geographic_multipolygon *,
                  const Geographic_linestring *) const {
  // A multipolygon can never be within a linestring.
  return false;
}

bool Within::eval(const Geographic_multipolygon *g1,
                  const Geographic_polygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

bool Within::eval(const Geographic_multipolygon *g1,
                  const Geographic_geometrycollection *g2) const {
  // A multipolygon may not be within the points and linestrings of g2, so the
  // only way a multipolygon is within a geometrycollectin, is if it's within
  // the union multipolygon of the geometrycollection.
  std::unique_ptr<Multipoint> g2_mpt;
  std::unique_ptr<Multilinestring> g2_mls;
  std::unique_ptr<Multipolygon> g2_mpy;
  split_gc(g2, &g2_mpt, &g2_mls, &g2_mpy);
  gc_union(m_semi_major, m_semi_minor, &g2_mpt, &g2_mls, &g2_mpy);
  return eval(g1, down_cast<Geographic_multipolygon *>(g2_mpy.get()));
}

bool Within::eval(const Geographic_multipolygon *,
                  const Geographic_multipoint *) const {
  // A multipolygon can never be within a multipoint.
  return false;
}

bool Within::eval(const Geographic_multipolygon *,
                  const Geographic_multilinestring *) const {
  // A multipolygon can never be within a multilinestring.
  return false;
}

bool Within::eval(const Geographic_multipolygon *g1,
                  const Geographic_multipolygon *g2) const {
  return bg::within(*g1, *g2, m_geographic_ll_la_aa_strategy);
}

//////////////////////////////////////////////////////////////////////////////

// within(Box, Box)

bool Within::eval(const Cartesian_box *b1, const Cartesian_box *b2) const {
  if (mbrs_are_equal(*b1, *b2)) return true;

  // Work around bugs in BG for boxes that have zero height and/or width.
  if (mbr_is_point(*b1)) {
    Cartesian_point pt(b1->min_corner().x(), b1->min_corner().y());

    if (mbr_is_line(*b2)) {
      Cartesian_point b2_ls_start(b2->min_corner().x(), b2->min_corner().y());
      Cartesian_point b2_ls_end(b2->max_corner().x(), b2->max_corner().y());
      Cartesian_linestring b2_ls;
      b2_ls.push_back(b2_ls_start);
      b2_ls.push_back(b2_ls_end);

      return bg::within(pt, b2_ls);
    }

    return bg::within(pt, *b2);
  }

  if (mbr_is_line(*b1)) {
    Cartesian_point b1_ls_start(b1->min_corner().x(), b1->min_corner().y());
    Cartesian_point b1_ls_end(b1->max_corner().x(), b1->max_corner().y());
    Cartesian_linestring b1_ls;
    b1_ls.push_back(b1_ls_start);
    b1_ls.push_back(b1_ls_end);

    if (mbr_is_line(*b2)) {
      Cartesian_point b2_ls_start(b2->min_corner().x(), b2->min_corner().y());
      Cartesian_point b2_ls_end(b2->max_corner().x(), b2->max_corner().y());
      Cartesian_linestring b2_ls;
      b2_ls.push_back(b2_ls_start);
      b2_ls.push_back(b2_ls_end);

      return bg::within(b1_ls, b2_ls);
    }

    Cartesian_point b2_pt1(b2->min_corner().x(), b2->min_corner().y());
    Cartesian_point b2_pt2(b2->max_corner().x(), b2->min_corner().y());
    Cartesian_point b2_pt3(b2->max_corner().x(), b2->max_corner().y());
    Cartesian_point b2_pt4(b2->min_corner().x(), b2->max_corner().y());
    Cartesian_point b2_pt5(b2->min_corner().x(), b2->min_corner().y());
    Cartesian_linearring b2_lr;
    b2_lr.push_back(b2_pt1);
    b2_lr.push_back(b2_pt2);
    b2_lr.push_back(b2_pt3);
    b2_lr.push_back(b2_pt4);
    b2_lr.push_back(b2_pt5);
    Cartesian_polygon b2_py;
    b2_py.push_back(b2_lr);

    return bg::within(b1_ls, b2_py);
  }

  return bg::within(*b1, *b2);
}

bool Within::eval(const Geographic_box *b1, const Geographic_box *b2) const {
  if (mbrs_are_equal(*b1, *b2)) return true;

  // Work around bugs in BG for boxes that have zero height and/or width.
  if (mbr_is_point(*b1)) {
    Geographic_point pt(b1->min_corner().x(), b1->min_corner().y());

    if (mbr_is_line(*b2)) {
      Geographic_point b2_ls_start(b2->min_corner().x(), b2->min_corner().y());
      Geographic_point b2_ls_end(b2->max_corner().x(), b2->max_corner().y());
      Geographic_linestring b2_ls;
      b2_ls.push_back(b2_ls_start);
      b2_ls.push_back(b2_ls_end);

      return bg::within(pt, b2_ls);
    }

    return bg::within(pt, *b2);
  }

  if (mbr_is_line(*b1)) {
    Geographic_point b1_ls_start(b1->min_corner().x(), b1->min_corner().y());
    Geographic_point b1_ls_end(b1->max_corner().x(), b1->max_corner().y());
    Geographic_linestring b1_ls;
    b1_ls.push_back(b1_ls_start);
    b1_ls.push_back(b1_ls_end);

    if (mbr_is_line(*b2)) {
      Geographic_point b2_ls_start(b2->min_corner().x(), b2->min_corner().y());
      Geographic_point b2_ls_end(b2->max_corner().x(), b2->max_corner().y());
      Geographic_linestring b2_ls;
      b2_ls.push_back(b2_ls_start);
      b2_ls.push_back(b2_ls_end);

      return bg::within(b1_ls, b2_ls);
    }

    // If b1 is a line along the border of b2, it's not within b2.
    if (((b1_ls_start.x() == b1_ls_end.x()) &&
         (b1_ls_start.x() == b2->min_corner().x() ||
          b1_ls_start.x() == b2->max_corner().x())) ||
        ((b1_ls_start.y() == b1_ls_end.y()) &&
         (b1_ls_start.y() == b2->min_corner().y() ||
          b1_ls_start.y() == b2->max_corner().y())))
      return false;

    return bg::covered_by(b1_ls_start, *b2) && bg::covered_by(b1_ls_end, *b2);
  }

  return bg::within(*b1, *b2);
}

//////////////////////////////////////////////////////////////////////////////

bool within(const dd::Spatial_reference_system *srs, const Geometry *g1,
            const Geometry *g2, const char *func_name, bool *within,
            bool *null) noexcept {
  try {
    DBUG_ASSERT(g1->coordinate_system() == g2->coordinate_system());
    DBUG_ASSERT(srs == nullptr ||
                ((srs->is_cartesian() &&
                  g1->coordinate_system() == Coordinate_system::kCartesian) ||
                 (srs->is_geographic() &&
                  g1->coordinate_system() == Coordinate_system::kGeographic)));

    if ((*null = (g1->is_empty() || g2->is_empty()))) return false;

    Within within_func(srs ? srs->semi_major_axis() : 0.0,
                       srs ? srs->semi_minor_axis() : 0.0);
    *within = within_func(g1, g2);
  } catch (...) {
    handle_gis_exception(func_name);
    return true;
  }

  return false;
}

bool mbr_within(const dd::Spatial_reference_system *srs, const Geometry *g1,
                const Geometry *g2, const char *func_name, bool *within,
                bool *null) noexcept {
  try {
    DBUG_ASSERT(g1->coordinate_system() == g2->coordinate_system());
    DBUG_ASSERT(srs == nullptr ||
                ((srs->is_cartesian() &&
                  g1->coordinate_system() == Coordinate_system::kCartesian) ||
                 (srs->is_geographic() &&
                  g1->coordinate_system() == Coordinate_system::kGeographic)));

    if ((*null = (g1->is_empty() || g2->is_empty()))) return false;

    Within within_func(srs ? srs->semi_major_axis() : 0.0,
                       srs ? srs->semi_minor_axis() : 0.0);

    switch (g1->coordinate_system()) {
      case Coordinate_system::kCartesian: {
        Cartesian_box mbr1;
        box_envelope(g1, srs, &mbr1);
        Cartesian_box mbr2;
        box_envelope(g2, srs, &mbr2);

        *within = within_func(&mbr1, &mbr2);
        break;
      }
      case Coordinate_system::kGeographic: {
        Geographic_box mbr1;
        box_envelope(g1, srs, &mbr1);
        Geographic_box mbr2;
        box_envelope(g2, srs, &mbr2);

        *within = within_func(&mbr1, &mbr2);
        break;
      }
    }
  } catch (...) {
    handle_gis_exception(func_name);
    return true;
  }

  return false;
}

}  // namespace gis

ext: cc


text:
//
// Copyright 2017 Pixar
//
// Licensed under the Apache License, Version 2.0 (the "Apache License")
// with the following modification; you may not use this file except in
// compliance with the Apache License and the following modification to it:
// Section 6. Trademarks. is deleted and replaced with:
//
// 6. Trademarks. This License does not grant permission to use the trade
//    names, trademarks, service marks, or product names of the Licensor
//    and its affiliates, except as required to comply with Section 4(c) of
//    the License and to reproduce the content of the NOTICE file.
//
// You may obtain a copy of the Apache License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the Apache License with the above modification is
// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the Apache License for the specific
// language governing permissions and limitations under the Apache License.
//
#include "pxr/base/arch/pragmas.h"

ARCH_PRAGMA_PUSH
ARCH_PRAGMA_PLACEMENT_NEW  // because of pyFunction.h and boost::function

#include <boost/python/def.hpp>
#include <boost/python/tuple.hpp>

#include "pxr/base/tf/pyFunction.h"
#include "pxr/base/tf/pyUtils.h"

#include "pxr/pxr.h"
#include "pxr/usd/sdf/copyUtils.h"

#include "pxr/usd/sdf/layer.h"
#include "pxr/usd/sdf/path.h"

#include "pxr/base/vt/value.h"

#include <functional>

using namespace boost::python;

PXR_NAMESPACE_USING_DIRECTIVE

namespace
{

VtValue
_GetValueForField(
    const SdfLayerHandle& layer, const TfToken& field,
    const boost::python::object& obj)
{
    // Need to disambiguate certain types from Python.
    //
    // XXX: See also wrapSpec.cpp. Perhaps this logic should live in
    // pyUtils.h?
    const VtValue& fallback = layer->GetSchema().GetFallback(field);
    if (fallback.IsHolding<TfTokenVector>()) {
        return VtValue(extract<TfTokenVector>(obj)());
    }

    VtValue v = extract<VtValue>(obj)();
    if (!fallback.IsEmpty()) {
        v.CastToTypeOf(fallback);
    }
    return v;
}

using Py_SdfShouldCopyValueSig =
    boost::python::object(
        SdfSpecType, const TfToken&,
        const SdfLayerHandle&, const SdfPath&, bool,
        const SdfLayerHandle&, const SdfPath&, bool);

using Py_SdfShouldCopyValueFn = std::function<Py_SdfShouldCopyValueSig>;

using Py_SdfShouldCopyChildrenSig =
    boost::python::object(
        const TfToken&,
        const SdfLayerHandle&, const SdfPath&, bool,
        const SdfLayerHandle&, const SdfPath&, bool);

using Py_SdfShouldCopyChildrenFn = std::function<Py_SdfShouldCopyChildrenSig>;

bool
_ShouldCopyValue(
    const Py_SdfShouldCopyValueFn& pyFunc,
    SdfSpecType specType, const TfToken& field,
    const SdfLayerHandle& srcLayer, const SdfPath& srcPath, bool fieldInSrc,
    const SdfLayerHandle& dstLayer, const SdfPath& dstPath, bool fieldInDst,
    boost::optional<VtValue>* value)
{
    object result = pyFunc(
        specType, field,
        srcLayer, srcPath, fieldInSrc, dstLayer, dstPath, fieldInDst);

    if (PyBool_Check(result.ptr())) {
        return extract<bool>(result)();
    }

    extract<tuple> getTuple(result);
    if (getTuple.check()) {
        if (PyBool_Check(object(result[0]).ptr())) {
            const bool status = extract<bool>(result[0])();
            *value = _GetValueForField(srcLayer, field, result[1]);
            return status;
        }
    }

    TfPyThrowTypeError(
        "Expected shouldCopyValueFn to return bool or (bool, value)");
    return true;
}

bool
_ShouldCopyChildren(
    const Py_SdfShouldCopyChildrenFn& pyFunc,
    const TfToken& field,
    const SdfLayerHandle& srcLayer, const SdfPath& srcPath, bool fieldInSrc,
    const SdfLayerHandle& dstLayer, const SdfPath& dstPath, bool fieldInDst,
    boost::optional<VtValue>* srcChildren,
    boost::optional<VtValue>* dstChildren)
{
    object result = pyFunc(
        field, srcLayer, srcPath, fieldInSrc, dstLayer, dstPath, fieldInDst);

    if (PyBool_Check(result.ptr())) {
        return extract<bool>(result)();
    }

    extract<tuple> getTuple(result);
    if (getTuple.check()) {
        if (PyBool_Check(object(result[0]).ptr())) {
            const bool status = extract<bool>(result[0])();
            *srcChildren = _GetValueForField(srcLayer, field, result[1]);
            *dstChildren = _GetValueForField(srcLayer, field, result[2]);
            return status;
        }
    }

    TfPyThrowTypeError(
        "Expected shouldCopyChildrenFn to return bool or (bool, value, value)");
    return true;
}

bool
Py_SdfCopySpec(
    const SdfLayerHandle& srcLayer, const SdfPath& srcPath,
    const SdfLayerHandle& dstLayer, const SdfPath& dstPath,
    const Py_SdfShouldCopyValueFn& shouldCopyValueFn,
    const Py_SdfShouldCopyChildrenFn& shouldCopyChildrenFn)
{
    namespace ph = std::placeholders;

    return SdfCopySpec(
        srcLayer, srcPath, dstLayer, dstPath,
        /* shouldCopyValueFn = */ std::bind(
            _ShouldCopyValue, std::cref(shouldCopyValueFn),
            ph::_1, ph::_2, ph::_3, ph::_4, ph::_5, ph::_6, ph::_7, ph::_8,
            ph::_9),
        /* shouldCopyChildrenFn = */ std::bind(
            _ShouldCopyChildren, std::cref(shouldCopyChildrenFn),
            ph::_1, ph::_2, ph::_3, ph::_4, ph::_5, ph::_6, ph::_7, ph::_8,
            ph::_9)
        );
}

}

void
wrapCopyUtils()
{
    def("CopySpec",
        (bool(*)(const SdfLayerHandle&, const SdfPath&,
                 const SdfLayerHandle&, const SdfPath&))
        &SdfCopySpec,
        (arg("srcLayer"), arg("srcPath"), arg("dstLayer"), arg("dstPath")));

    TfPyFunctionFromPython<Py_SdfShouldCopyChildrenSig>();
    TfPyFunctionFromPython<Py_SdfShouldCopyValueSig>();
    def("CopySpec", &Py_SdfCopySpec,
        (arg("srcLayer"), arg("srcPath"), arg("dstLayer"), arg("dstPath"),
         arg("shouldCopyValueFn"), arg("shouldCopyChildrenFn")));
}

ARCH_PRAGMA_POP

ext: cpp

max_stars_repo_name: YuqiaoZhang/USD

max_issues_repo_name: YuqiaoZhang/USD

max_forks_repo_name: YuqiaoZhang/USD


text:
/*
 * fs/mime_types.cc
 * -------------------------------------------------------------------------
 * MIME type lookup implementation.
 * -------------------------------------------------------------------------
 *
 * Copyright (c) 2013, Tarick Bedeir.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <fstream>
#include <map>
#include <vector>
#include <boost/algorithm/string/case_conv.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/split.hpp>

#include "base/paths.h"
#include "fs/mime_types.h"

using boost::is_any_of;
using boost::token_compress_on;
using boost::algorithm::to_lower;
using std::ifstream;
using std::map;
using std::string;
using std::vector;

using s3::base::paths;
using s3::fs::mime_types;

namespace
{
  typedef map<string, string> type_map;

  const char *MAP_FILES[] = {
    "/etc/httpd/mime.types",
    "/private/etc/apache2/mime.types", // this just happens to be where I found the mime map on my OS X system
    "/etc/mime.types",
    "~/.mime.types" };

  const size_t MAP_FILE_COUNT = sizeof(MAP_FILES) / sizeof(MAP_FILES[0]);

  type_map s_map;

  void load_from_file(const string &path)
  {
    string line;
    vector<string> fields;
    ifstream f(paths::transform(path).c_str(), ifstream::in);

    while (f.good()) {
      size_t pos;

      getline(f, line);

      pos = line.find('#');

      if (pos == 0)
        continue;
      else if (pos != string::npos)
        line = line.substr(0, pos);

      split(fields, line, is_any_of(string(" \t")), token_compress_on);

      for (size_t i = 1; i < fields.size(); i++)
        s_map[fields[i]] = fields[0];
    }
  }
}

void mime_types::init()
{
  for (size_t i = 0; i < MAP_FILE_COUNT; i++)
    load_from_file(MAP_FILES[i]);
}

string mime_types::get_type_by_extension(string ext)
{
  to_lower(ext);

  const type_map::const_iterator &iter = s_map.find(ext);
  return (iter == s_map.end()) ? "" : iter->second;
}


text:
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#include "util/os-util.h"

#include <unistd.h>
#include <fstream>
#include <sstream>
#include <boost/filesystem.hpp>
#include <boost/algorithm/string.hpp>
#include <gutil/strings/substitute.h>

#include "util/error-util.h"
#include "util/string-parser.h"

#include "common/names.h"

using boost::filesystem::exists;
using boost::algorithm::is_any_of;
using boost::algorithm::token_compress_on;
using boost::algorithm::split;
using boost::algorithm::trim_right;
using namespace impala;
using namespace strings;

// Ensure that Impala compiles on earlier kernels. If the target kernel does not support
// _SC_CLK_TCK, sysconf(_SC_CLK_TCK) will return -1.
#ifndef _SC_CLK_TCK
#define _SC_CLK_TCK 2
#endif

static const int64_t TICKS_PER_SEC = sysconf(_SC_CLK_TCK);

// Offsets into the ../stat file array of per-thread statistics
static const int64_t USER_TICKS = 13;
static const int64_t KERNEL_TICKS = 14;
static const int64_t IO_WAIT = 41;

// Largest offset we are interested in, to check we get a well formed stat file.
static const int64_t MAX_OFFSET = IO_WAIT;

Status impala::GetThreadStats(int64_t tid, ThreadStats* stats) {
  DCHECK(stats != NULL);
  if (TICKS_PER_SEC <= 0) return Status("ThreadStats not supported");

  stringstream proc_path;
  proc_path << "/proc/self/task/" << tid << "/stat";
  if (!exists(proc_path.str())) return Status("Thread path does not exist");

  ifstream proc_file(proc_path.str().c_str());
  if (!proc_file.is_open()) return Status("Could not open ifstream");

  string buffer((std::istreambuf_iterator<char>(proc_file)),
      std::istreambuf_iterator<char>());

  vector<string> splits;
  split(splits, buffer, is_any_of(" "), token_compress_on);
  if (splits.size() < MAX_OFFSET) return Status("Unrecognised /proc format");

  StringParser::ParseResult parse_result;
  int64_t tmp = StringParser::StringToInt<int64_t>(splits[USER_TICKS].c_str(),
      splits[USER_TICKS].size(), &parse_result);
  if (parse_result == StringParser::PARSE_SUCCESS) {
    stats->user_ns = tmp * (1e9 / TICKS_PER_SEC);
  }

  tmp = StringParser::StringToInt<int64_t>(splits[KERNEL_TICKS].c_str(),
      splits[KERNEL_TICKS].size(), &parse_result);
  if (parse_result == StringParser::PARSE_SUCCESS) {
    stats->kernel_ns = tmp * (1e9 / TICKS_PER_SEC);
  }

  tmp = StringParser::StringToInt<int64_t>(splits[IO_WAIT].c_str(),
      splits[IO_WAIT].size(), &parse_result);
  if (parse_result == StringParser::PARSE_SUCCESS) {
    stats->iowait_ns = tmp * (1e9 / TICKS_PER_SEC);
  }

  return Status::OK();
}

bool impala::RunShellProcess(const string& cmd, string* msg, bool do_trim) {
  DCHECK(msg != NULL);
  FILE* fp = popen(cmd.c_str(), "r");
  if (fp == NULL) {
    *msg = Substitute("Failed to execute shell cmd: '$0', error was: $1", cmd,
        GetStrErrMsg());
    return false;
  }
  // Read the first 1024 bytes of any output before pclose() so we have some idea of what
  // happened on failure.
  char buf[1024];
  size_t len = fread(buf, 1, 1024, fp);
  string output;
  output.assign(buf, len);

  // pclose() returns an encoded form of the sub-process' exit code.
  int status = pclose(fp);
  if (WIFEXITED(status) && WEXITSTATUS(status) == 0) {
    *msg = output;
    if (do_trim) trim_right(*msg);
    return true;
  }

  // pclose() doesn't set errno. We could redirect the cmd to get the stderr output as
  // well, but that might interfere with correct executions that happen to produce output
  // on stderr.
  *msg = Substitute("Shell cmd: '$0' exited with error status: '$1'. Stdout was: '$2'",
      cmd, WEXITSTATUS(status), output);
  return false;
}

max_stars_repo_name: suifengzhuliu/impala

max_issues_repo_name: suifengzhuliu/impala

max_forks_repo_name: suifengzhuliu/impala


text:
// Copyright (c) 2016 by SN Systems Ltd., Sony Interactive Entertainment Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

#ifndef SCANLIB_CONSUMER_HPP
#define SCANLIB_CONSUMER_HPP

// Standard library includes
#include <string>

// 3rd party includes
#include <boost/filesystem.hpp>
#include <boost/lockfree/queue.hpp>

// The job queue
struct queue_member {
    boost::filesystem::path real_path;
    std::string member_name;
    boost::filesystem::path user_path;
};
using queue_type = boost::lockfree::queue<queue_member const *>;

class comdat_scanner;
struct output_flags;
struct state_flags;
class updater;
void consumer (queue_type & queue, comdat_scanner * const scanner, output_flags const & ofl,
               state_flags * const state, updater & progress);

#endif // SCANLIB_CONSUMER_HPP
// eof scanlib/consumer.hpp

ext: hpp

max_stars_repo_name: SNSystems/Program-repository

max_issues_repo_name: SNSystems/Program-repository

max_forks_repo_name: SNSystems/Program-repository


text:
//
// Copyright (c) 2016-2019 Vinnie Falco (vinnie dot falco at gmail dot com)
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// Official repository: https://github.com/boostorg/beast
//

#ifndef BOOST_BEAST_HTTP_IMPL_RFC7230_HPP
#define BOOST_BEAST_HTTP_IMPL_RFC7230_HPP

#include <boost/beast/http/detail/rfc7230.hpp>
#include <iterator>

namespace boost {
namespace beast {
namespace http {

class param_list::const_iterator
{
    using iter_type = string_view::const_iterator;

    std::string s_;
    detail::param_iter pi_;

public:
    using value_type = param_list::value_type;
    using pointer = value_type const*;
    using reference = value_type const&;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::input_iterator_tag;

    const_iterator() = default;

    bool
    operator==(const_iterator const& other) const
    {
        return
            other.pi_.it == pi_.it &&
            other.pi_.last == pi_.last &&
            other.pi_.first == pi_.first;
    }

    bool
    operator!=(const_iterator const& other) const
    {
        return !(*this == other);
    }

    reference
    operator*() const
    {
        return pi_.v;
    }

    pointer
    operator->() const
    {
        return &*(*this);
    }

    const_iterator&
    operator++()
    {
        increment();
        return *this;
    }

    const_iterator
    operator++(int)
    {
        auto temp = *this;
        ++(*this);
        return temp;
    }

private:
    friend class param_list;

    const_iterator(iter_type first, iter_type last)
    {
        pi_.it = first;
        pi_.first = first;
        pi_.last = last;
        increment();
    }

    BOOST_BEAST_DECL
    static
    std::string
    unquote(string_view sr);

    BOOST_BEAST_DECL
    void
    increment();
};

inline
auto
param_list::
begin() const ->
    const_iterator
{
    return const_iterator{s_.begin(), s_.end()};
}

inline
auto
param_list::
end() const ->
    const_iterator
{
    return const_iterator{s_.end(), s_.end()};
}

inline
auto
param_list::
cbegin() const ->
    const_iterator
{
    return const_iterator{s_.begin(), s_.end()};
}

inline
auto
param_list::
cend() const ->
    const_iterator
{
    return const_iterator{s_.end(), s_.end()};
}

//------------------------------------------------------------------------------

class ext_list::const_iterator
{
    ext_list::value_type v_;
    iter_type it_;
    iter_type first_;
    iter_type last_;

public:
    using value_type = ext_list::value_type;
    using pointer = value_type const*;
    using reference = value_type const&;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    const_iterator() = default;

    bool
    operator==(const_iterator const& other) const
    {
        return
            other.it_ == it_ &&
            other.first_ == first_ &&
            other.last_ == last_;
    }

    bool
    operator!=(const_iterator const& other) const
    {
        return !(*this == other);
    }

    reference
    operator*() const
    {
        return v_;
    }

    pointer
    operator->() const
    {
        return &*(*this);
    }

    const_iterator&
    operator++()
    {
        increment();
        return *this;
    }

    const_iterator
    operator++(int)
    {
        auto temp = *this;
        ++(*this);
        return temp;
    }

private:
    friend class ext_list;

    const_iterator(iter_type begin, iter_type end)
    {
        it_ = begin;
        first_ = begin;
        last_ = end;
        increment();
    }

    BOOST_BEAST_DECL
    void
    increment();
};

inline
auto
ext_list::
begin() const ->
    const_iterator
{
    return const_iterator{s_.begin(), s_.end()};
}

inline
auto
ext_list::
end() const ->
    const_iterator
{
    return const_iterator{s_.end(), s_.end()};
}

inline
auto
ext_list::
cbegin() const ->
    const_iterator
{
    return const_iterator{s_.begin(), s_.end()};
}

inline
auto
ext_list::
cend() const ->
    const_iterator
{
    return const_iterator{s_.end(), s_.end()};
}

//------------------------------------------------------------------------------

class token_list::const_iterator
{
    token_list::value_type v_;
    iter_type it_;
    iter_type first_;
    iter_type last_;

public:
    using value_type = token_list::value_type;
    using pointer = value_type const*;
    using reference = value_type const&;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::forward_iterator_tag;

    const_iterator() = default;

    bool
    operator==(const_iterator const& other) const
    {
        return
            other.it_ == it_ &&
            other.first_ == first_ &&
            other.last_ == last_;
    }

    bool
    operator!=(const_iterator const& other) const
    {
        return !(*this == other);
    }

    reference
    operator*() const
    {
        return v_;
    }

    pointer
    operator->() const
    {
        return &*(*this);
    }

    const_iterator&
    operator++()
    {
        increment();
        return *this;
    }

    const_iterator
    operator++(int)
    {
        auto temp = *this;
        ++(*this);
        return temp;
    }

private:
    friend class token_list;

    const_iterator(iter_type begin, iter_type end)
    {
        it_ = begin;
        first_ = begin;
        last_ = end;
        increment();
    }

    BOOST_BEAST_DECL
    void
    increment();
};

inline
auto
token_list::
begin() const ->
    const_iterator
{
    return const_iterator{s_.begin(), s_.end()};
}

inline
auto
token_list::
end() const ->
    const_iterator
{
    return const_iterator{s_.end(), s_.end()};
}

inline
auto
token_list::
cbegin() const ->
    const_iterator
{
    return const_iterator{s_.begin(), s_.end()};
}

inline
auto
token_list::
cend() const ->
    const_iterator
{
    return const_iterator{s_.end(), s_.end()};
}

template<class Policy>
bool
validate_list(detail::basic_parsed_list<
    Policy> const& list)
{
    auto const last = list.end();
    auto it = list.begin();
    if(it.error())
        return false;
    while(it != last)
    {
        ++it;
        if(it.error())
            return false;
        if(it == last)
            break;
    }
    return true;
}

} // http
} // beast
} // boost

#ifdef BOOST_BEAST_HEADER_ONLY
#include <boost/beast/http/impl/rfc7230.ipp>
#endif

#endif


text:
// Copyright 2008 Willow Garage, Inc.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//    * Redistributions of source code must retain the above copyright
//      notice, this list of conditions and the following disclaimer.
//
//    * Redistributions in binary form must reproduce the above copyright
//      notice, this list of conditions and the following disclaimer in the
//      documentation and/or other materials provided with the distribution.
//
//    * Neither the name of the Willow Garage, Inc. nor the names of its
//      contributors may be used to endorse or promote products derived from
//      this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

/** \Author Ioan Sucan */

#include <geometric_shapes/bodies.h>
#include <geometric_shapes/shape_operations.h>
#include <geometric_shapes/body_operations.h>
#include <boost/filesystem.hpp>
#include <gtest/gtest.h>
#include "resources/config.h"

// We expect surface points are counted inside.
#define EXPECT_SURF EXPECT_TRUE

// split length into the largest number elem, such that sqrt(elem^2 + elem^2) <= length
double largestComponentForLength2D(const double length)
{
  // HACK: sqrt(2) / 2 is a problem due to rounding errors since the distance
  //       is computed as 1.0000000000000002 . In such case we subtract an
  //       epsilon.

  double sq2 = sqrt(length / 2);
  while (sq2 * sq2 + sq2 * sq2 > length)
    sq2 -= std::numeric_limits<double>::epsilon();
  return sq2;
}

Eigen::Isometry3d getRandomPose(random_numbers::RandomNumberGenerator& g)
{
  const Eigen::Vector3d t(g.uniformReal(-100, 100), g.uniformReal(-100, 100), g.uniformReal(-100, 100));

  double quat[4];
  g.quaternion(quat);
  const Eigen::Quaterniond r({ quat[3], quat[0], quat[1], quat[2] });

  return Eigen::Isometry3d::TranslationType(t) * r;
}

TEST(SpherePointContainment, Basic)
{
  shapes::Sphere shape(1.0);
  bodies::Sphere sphere(&shape);

  // clang-format off
  // zero
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.00, 0.00, 0.00)));
  // general point outside
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(1.00, 1.00, 1.00)));

  // near single-axis maximum
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.99, 0.00, 0.00)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(1.00, 0.00, 0.00)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(1.01, 0.00, 0.00)));
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.00, 0.99, 0.00)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(0.00, 1.00, 0.00)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.00, 1.01, 0.00)));
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.00, 0.00, 0.99)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(0.00, 0.00, 1.00)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.00, 0.00, 1.01)));

  // near two-axis maximum
  const double sq2e = largestComponentForLength2D(1.0);
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.70, 0.70, 0.00)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(sq2e, sq2e, 0.00)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.71, 0.71, 0.00)));
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.70, 0.00, 0.70)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(sq2e, 0.00, sq2e)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.71, 0.00, 0.71)));
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.00, 0.70, 0.70)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(0.00, sq2e, sq2e)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.00, 0.71, 0.71)));

  // near three-axis maximum
  const double sq3 = sqrt(3) / 3;
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.57, 0.57, 0.57)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(sq3 , sq3 , sq3 )));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.58, 0.58, 0.58)));

  // near three-axis maximum with translation
  Eigen::Isometry3d pose;
  pose.setIdentity();
  pose.translation() = Eigen::Vector3d(1.0, 0.0, 0.0);
  sphere.setPose(pose);

  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(1.57, 0.57, 0.57)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(1+sq3,sq3 , sq3 )));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(1.58, 0.58, 0.58)));

  pose.translation() = Eigen::Vector3d(0.0, 1.0, 0.0);
  sphere.setPose(pose);
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.57, 1.57, 0.57)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(sq3 ,1+sq3, sq3 )));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.58, 1.58, 0.58)));

  pose.translation() = Eigen::Vector3d(0.0, 0.0, 1.0);
  sphere.setPose(pose);
  EXPECT_TRUE( sphere.containsPoint(Eigen::Vector3d(0.57, 0.57, 1.57)));
  EXPECT_SURF( sphere.containsPoint(Eigen::Vector3d(sq3 , sq3, 1+sq3)));
  EXPECT_FALSE(sphere.containsPoint(Eigen::Vector3d(0.58, 0.58, 1.58)));
  // clang-format on
}

TEST(SpherePointContainment, SimpleInside)
{
  shapes::Sphere shape(1.0);
  bodies::Body* sphere = new bodies::Sphere(&shape);
  sphere->setScale(1.05);
  EXPECT_TRUE(sphere->containsPoint(0, 0, 1.0));

  random_numbers::RandomNumberGenerator r(0);
  Eigen::Vector3d p;
  for (int i = 0; i < 1000; ++i)
  {
    const Eigen::Isometry3d pos = getRandomPose(r);
    sphere->setPose(pos);
    sphere->setScale(r.uniformReal(0.1, 100.0));
    sphere->setPadding(r.uniformReal(-0.001, 10.0));

    EXPECT_TRUE(sphere->samplePointInside(r, 100, p));
    EXPECT_TRUE(sphere->containsPoint(p));
  }
  delete sphere;
}

TEST(SpherePointContainment, SimpleOutside)
{
  shapes::Sphere shape(1.0);
  bodies::Body* sphere = new bodies::Sphere(&shape);
  sphere->setScale(0.95);
  bool contains = sphere->containsPoint(0, 0, 1.0);
  delete sphere;
  EXPECT_FALSE(contains);
}

TEST(SpherePointContainment, ComplexInside)
{
  shapes::Sphere shape(1.0);
  bodies::Body* sphere = new bodies::Sphere(&shape);
  sphere->setScale(0.95);
  Eigen::Isometry3d pose;
  pose.setIdentity();
  pose.translation() = Eigen::Vector3d(1.0, 1.0, 1.0);
  sphere->setPose(pose);
  bool contains = sphere->containsPoint(0.5, 1, 1.0);
  delete sphere;
  EXPECT_TRUE(contains);
}

TEST(SpherePointContainment, ComplexOutside)
{
  shapes::Sphere shape(1.0);
  bodies::Body* sphere = new bodies::Sphere(&shape);
  sphere->setScale(0.95);
  Eigen::Isometry3d pose;
  pose.setIdentity();
  pose.translation() = Eigen::Vector3d(1.0, 1.0, 1.0);
  sphere->setPose(pose);
  bool contains = sphere->containsPoint(0.5, 0.0, 0.0);
  delete sphere;
  EXPECT_FALSE(contains);
}

TEST(BoxPointContainment, Basic)
{
  shapes::Box shape(2.0, 2.0, 2.0);
  bodies::Box box(&shape);

  // clang-format off
  // zero
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.00, 0.00, 0.00)));
  // general point outside
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(2.00, 2.00, 2.00)));

  // near single-axis maximum
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.99, 0.00, 0.00)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(1.00, 0.00, 0.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(1.01, 0.00, 0.00)));
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.00, 0.99, 0.00)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(0.00, 1.00, 0.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(0.00, 1.01, 0.00)));
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.00, 0.00, 0.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(0.00, 0.00, 1.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(0.00, 0.00, 1.01)));

  // near two-axis maximum
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.99, 0.99, 0.00)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(1.00, 1.00, 0.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(1.01, 1.01, 0.00)));
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.99, 0.00, 0.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(1.00, 0.00, 1.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(1.01, 0.00, 1.01)));
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.00, 0.99, 0.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(0.00, 1.00, 1.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(0.00, 1.01, 1.01)));

  // near three-axis maximum
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.99, 0.99, 0.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(1.00, 1.00, 1.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(1.01, 1.01, 1.01)));

  // near three-axis maximum with translation
  Eigen::Isometry3d pose;
  pose.setIdentity();
  pose.translation() = Eigen::Vector3d(1.0, 0.0, 0.0);
  box.setPose(pose);

  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(1.99, 0.99, 0.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(2.00, 1.00, 1.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(2.01, 1.01, 1.01)));

  pose.translation() = Eigen::Vector3d(0.0, 1.0, 0.0);
  box.setPose(pose);
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.99, 1.99, 0.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(1.00, 2.00, 1.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(1.01, 2.01, 1.01)));

  pose.translation() = Eigen::Vector3d(0.0, 0.0, 1.0);
  box.setPose(pose);
  EXPECT_TRUE( box.containsPoint(Eigen::Vector3d(0.99, 0.99, 1.99)));
  EXPECT_SURF( box.containsPoint(Eigen::Vector3d(1.00, 1.00, 2.00)));
  EXPECT_FALSE(box.containsPoint(Eigen::Vector3d(1.01, 1.01, 2.01)));
  // clang-format on
}

TEST(BoxPointContainment, SimpleInside)
{
  shapes::Box shape(1.0, 2.0, 3.0);
  bodies::Body* box = new bodies::Box(&shape);
  box->setScale(0.95);
  bool contains = box->containsPoint(0, 0, 1.0);
  EXPECT_TRUE(contains);

  random_numbers::RandomNumberGenerator r;
  Eigen::Vector3d p;
  EXPECT_TRUE(box->samplePointInside(r, 100, p));
  EXPECT_TRUE(box->containsPoint(p));

  delete box;
}

TEST(BoxPointContainment, SimpleOutside)
{
  shapes::Box shape(1.0, 2.0, 3.0);
  bodies::Body* box = new bodies::Box(&shape);
  box->setScale(0.95);
  bool contains = box->containsPoint(0, 0, 3.0);
  delete box;
  EXPECT_FALSE(contains);
}

TEST(BoxPointContainment, ComplexInside)
{
  shapes::Box shape(1.0, 1.0, 1.0);
  bodies::Body* box = new bodies::Box(&shape);
  box->setScale(1.01);
  Eigen::Isometry3d pose(Eigen::AngleAxisd(M_PI / 3.0, Eigen::Vector3d::UnitX()));
  pose.translation() = Eigen::Vector3d(1.0, 1.0, 1.0);
  box->setPose(pose);

  bool contains = box->containsPoint(1.5, 1.0, 1.5);
  EXPECT_TRUE(contains);

  delete box;
}

TEST(BoxPointContainment, Sampled)
{
  shapes::Box shape(1.0, 2.0, 3.0);
  bodies::Box box(&shape);

  random_numbers::RandomNumberGenerator r(0);
  Eigen::Vector3d p;
  for (int i = 0; i < 1000; ++i)
  {
    const Eigen::Isometry3d pos = getRandomPose(r);
    box.setPose(pos);
    box.setScale(r.uniformReal(0.1, 100.0));
    box.setPadding(r.uniformReal(-0.001, 10.0));

    EXPECT_TRUE(box.samplePointInside(r, 100, p));
    EXPECT_TRUE(box.containsPoint(p));
  }
}

TEST(BoxPointContainment, ComplexOutside)
{
  shapes::Box shape(1.0, 1.0, 1.0);
  bodies::Body* box = new bodies::Box(&shape);
  box->setScale(1.01);
  Eigen::Isometry3d pose(Eigen::AngleAxisd(M_PI / 3.0, Eigen::Vector3d::UnitX()));
  pose.translation() = Eigen::Vector3d(1.0, 1.0, 1.0);
  box->setPose(pose);

  bool contains = box->containsPoint(1.5, 1.5, 1.5);
  delete box;
  EXPECT_FALSE(contains);
}

TEST(CylinderPointContainment, Basic)
{
  shapes::Cylinder shape(1.0, 4.0);
  bodies::Cylinder cylinder(&shape);

  // clang-format off
  // zero
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.00, 0.00, 0.00)));
  // general point outside
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(1.00, 1.00, 4.00)));

  // near single-axis maximum
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.99, 0.00, 0.00)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(1.00, 0.00, 0.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(1.01, 0.00, 0.00)));
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.00, 0.99, 0.00)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(0.00, 1.00, 0.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.00, 1.01, 0.00)));
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.00, 0.00, 1.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(0.00, 0.00, 2.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.00, 0.00, 2.01)));

  // near two-axis maximum
  const double sq2 = sqrt(2) / 2;
  const double sq2e = largestComponentForLength2D(1);

  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.70, 0.70, 0.00)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(sq2e, sq2e, 0.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.71, 0.71, 0.00)));
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.99, 0.00, 1.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(1.00, 0.00, 2.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(1.01, 0.00, 2.01)));
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.00, 0.99, 1.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(0.00, 1.00, 2.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.00, 1.01, 2.01)));

  // near three-axis maximum
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.70, 0.70, 1.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(sq2e, sq2e, 2.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.71, 0.71, 2.01)));

  // near three-axis maximum with translation
  Eigen::Isometry3d pose;
  pose.setIdentity();
  pose.translation() = Eigen::Vector3d(1.0, 0.0, 0.0);
  cylinder.setPose(pose);

  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(1.70, 0.70, 1.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(1+sq2,sq2 , 2.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(1.71, 0.71, 2.01)));

  pose.translation() = Eigen::Vector3d(0.0, 1.0, 0.0);
  cylinder.setPose(pose);
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.70, 1.70, 1.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(sq2 ,1+sq2, 2.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.71, 1.71, 2.01)));

  pose.translation() = Eigen::Vector3d(0.0, 0.0, 1.0);
  cylinder.setPose(pose);
  EXPECT_TRUE( cylinder.containsPoint(Eigen::Vector3d(0.70, 0.70, 2.99)));
  EXPECT_SURF( cylinder.containsPoint(Eigen::Vector3d(sq2e, sq2e, 3.00)));
  EXPECT_FALSE(cylinder.containsPoint(Eigen::Vector3d(0.71, 0.71, 3.01)));
  // clang-format on
}

TEST(CylinderPointContainment, SimpleInside)
{
  shapes::Cylinder shape(1.0, 4.0);
  bodies::Body* cylinder = new bodies::Cylinder(&shape);
  cylinder->setScale(1.05);
  bool contains = cylinder->containsPoint(0, 0, 2.0);
  delete cylinder;
  EXPECT_TRUE(contains);
}

TEST(CylinderPointContainment, SimpleOutside)
{
  shapes::Cylinder shape(1.0, 4.0);
  bodies::Body* cylinder = new bodies::Cylinder(&shape);
  cylinder->setScale(0.95);
  bool contains = cylinder->containsPoint(0, 0, 2.0);
  delete cylinder;
  EXPECT_FALSE(contains);
}

TEST(CylinderPointContainment, CylinderPadding)
{
  shapes::Cylinder shape(1.0, 4.0);
  bodies::Body* cylinder = new bodies::Cylinder(&shape);
  bool contains = cylinder->containsPoint(0, 1.01, 0);
  EXPECT_FALSE(contains);
  cylinder->setPadding(.02);
  contains = cylinder->containsPoint(0, 1.01, 0);
  EXPECT_TRUE(contains);
  cylinder->setPadding(0.0);
  bodies::BoundingSphere bsphere;
  cylinder->computeBoundingSphere(bsphere);
  EXPECT_TRUE(bsphere.radius > 2.0);

  delete cylinder;
}

TEST(CylinderPointContainment, Sampled)
{
  shapes::Cylinder shape(1.0, 4.0);
  bodies::Cylinder cylinder(&shape);

  random_numbers::RandomNumberGenerator r(0);
  Eigen::Vector3d p;
  for (int i = 0; i < 1000; ++i)
  {
    const Eigen::Isometry3d pos = getRandomPose(r);
    cylinder.setPose(pos);
    cylinder.setScale(r.uniformReal(0.1, 100.0));
    cylinder.setPadding(r.uniformReal(-0.001, 10.0));

    EXPECT_TRUE(cylinder.samplePointInside(r, 100, p));
    EXPECT_TRUE(cylinder.containsPoint(p));
  }
}

TEST(MeshPointContainment, Basic)
{
  // clang-format off
  shapes::Mesh *ms = shapes::createMeshFromResource("file://" +
    (boost::filesystem::path(TEST_RESOURCES_DIR) / "/box.dae").string());
  ASSERT_TRUE(ms != nullptr);
  bodies::ConvexMesh cubeMesh(ms);
  cubeMesh.setScale(1.5);
  cubeMesh.setPadding(0.5 * sqrt(3));

  // zero
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 0.00, 0.00)));
  // general point outside
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(3.00, 3.00, 3.00)));

  // near single-axis maximum
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(1.99, 0.00, 0.00)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(2.00, 0.00, 0.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(2.01, 0.00, 0.00)));
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 1.99, 0.00)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 2.00, 0.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(0.00, 2.01, 0.00)));
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 0.00, 1.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 0.00, 2.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(0.00, 0.00, 2.01)));

  // near two-axis maximum
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(1.99, 1.99, 0.00)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(2.00, 2.00, 0.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(2.01, 2.01, 0.00)));
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(1.99, 0.00, 1.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(2.00, 0.00, 2.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(2.01, 0.00, 2.01)));
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 1.99, 1.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(0.00, 2.00, 2.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(0.00, 2.01, 2.01)));

  // near three-axis maximum
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(1.99, 1.99, 1.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(2.00, 2.00, 2.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(2.01, 2.01, 2.01)));

  // near three-axis maximum with translation
  Eigen::Isometry3d pose;
  pose.setIdentity();
  pose.translation() = Eigen::Vector3d(1.0, 0.0, 0.0);
  cubeMesh.setPose(pose);

  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(2.99, 1.99, 1.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(3.00, 2.00, 2.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(3.01, 2.01, 2.01)));

  pose.translation() = Eigen::Vector3d(0.0, 1.0, 0.0);
  cubeMesh.setPose(pose);
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(1.99, 2.99, 1.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(2.00, 3.00, 2.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(2.01, 3.01, 2.01)));

  pose.translation() = Eigen::Vector3d(0.0, 0.0, 1.0);
  cubeMesh.setPose(pose);
  EXPECT_TRUE( cubeMesh.containsPoint(Eigen::Vector3d(1.99, 1.99, 2.99)));
  EXPECT_SURF( cubeMesh.containsPoint(Eigen::Vector3d(2.00, 2.00, 3.00)));
  EXPECT_FALSE(cubeMesh.containsPoint(Eigen::Vector3d(2.01, 2.01, 3.01)));
  // clang-format on

  delete ms;
}

TEST(MeshPointContainment, Pr2Forearm)
{
  shapes::Mesh* ms = shapes::createMeshFromResource(
      "file://" + (boost::filesystem::path(TEST_RESOURCES_DIR) / "/forearm_roll.stl").string());
  ASSERT_TRUE(ms != nullptr);
  bodies::Body* m = new bodies::ConvexMesh(ms);
  ASSERT_TRUE(m != nullptr);
  Eigen::Isometry3d t(Eigen::Isometry3d::Identity());
  t.translation().x() = 1.0;
  EXPECT_FALSE(m->cloneAt(t)->containsPoint(-1.0, 0.0, 0.0));

  random_numbers::RandomNumberGenerator r(0);
  Eigen::Vector3d p;
  bool found = true;
  for (int i = 0; i < 10; ++i)
  {
    if (m->samplePointInside(r, 10000, p))
    {
      found = true;
      EXPECT_TRUE(m->containsPoint(p));
    }
  }
  EXPECT_TRUE(found);

  delete m;
  delete ms;
}

TEST(MergeBoundingSpheres, MergeTwoSpheres)
{
  std::vector<bodies::BoundingSphere> spheres;

  bodies::BoundingSphere s1;
  s1.center = Eigen::Vector3d(5.0, 0.0, 0.0);
  s1.radius = 1.0;

  bodies::BoundingSphere s2;
  s2.center = Eigen::Vector3d(-5.1, 0.0, 0.0);
  s2.radius = 1.0;

  spheres.push_back(s1);
  spheres.push_back(s2);

  bodies::BoundingSphere merged_sphere;
  bodies::mergeBoundingSpheres(spheres, merged_sphere);

  EXPECT_NEAR(merged_sphere.center[0], -.05, .00001);
  EXPECT_EQ(merged_sphere.radius, 6.05);
}

int main(int argc, char** argv)
{
  testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}