quadnode.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  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 QUADNODE_H
# define QUADNODE_H
 
# include <htlist.H>
# include <point.H>
# include <ah-errors.H>
 
using namespace Aleph;
 
# define PARENT(p) ((p)->get_parent())
# define NW_CHILD(p) ((p)->get_nw_child())
# define NE_CHILD(p) ((p)->get_ne_child())
# define SW_CHILD(p) ((p)->get_sw_child())
# define SE_CHILD(p) ((p)->get_se_child())
# define COLOR(p) ((p)->get_color())
# define LEVEL(p) ((p)->get_level())
 
class QuadNode
{
public:
 
  enum class Color
  {
    White,  
    Gray,   
    Black,  
    Num_Colors
  };
 
  enum class Quad
  {
    NW,  
    NE,  
    SW,  
    SE,  
    Num_Quads
  };
 
  enum class Side
  {
    North,  
    South,  
    East,   
    West,   
    Num_Sides
  };
 
private:
  DynList<Point> points; 
 
  QuadNode * parent;   
  QuadNode * nw_child; 
  QuadNode * ne_child; 
  QuadNode * sw_child; 
  QuadNode * se_child; 
 
  Color color;         
  unsigned long level; 
 
  // Region boundaries
  Geom_Number min_x;   
  Geom_Number max_x;   
  Geom_Number min_y;   
  Geom_Number max_y;   
 
  static QuadNode * get_north_neighbor(QuadNode * v) noexcept
  {
    if (PARENT(v) == nullptr)
      return nullptr;
 
    if (v->is_sw_child())
      return NW_CHILD(PARENT(v));
 
    if (v->is_se_child())
      return NE_CHILD(PARENT(v));
 
    QuadNode * u = get_north_neighbor(PARENT(v));
 
    if (u == nullptr or u->is_leaf())
      return u;
    else if (v->is_nw_child())
      return SW_CHILD(u);
    else
    return SE_CHILD(u);
  }
 
  static QuadNode * get_south_neighbor(QuadNode * v) noexcept
  {
    if (PARENT(v) == nullptr)
      return nullptr;
 
    if (v->is_nw_child())
      return SW_CHILD(PARENT(v));
 
    if (v->is_ne_child())
      return SE_CHILD(PARENT(v));
 
    QuadNode * u = get_south_neighbor(PARENT(v));
 
    if (u == nullptr or u->is_leaf())
      return u;
    else if (v->is_sw_child())
      return NW_CHILD(u);
    else
      return NE_CHILD(u);
  }
 
  static QuadNode * get_east_neighbor(QuadNode * v) noexcept
  {
    if (PARENT(v) == nullptr)
      return nullptr;
 
    if (v->is_nw_child())
      return NE_CHILD(PARENT(v));
 
    if (v->is_sw_child())
      return SE_CHILD(PARENT(v));
 
    QuadNode * u = get_east_neighbor(PARENT(v));
 
    if (u == nullptr or u->is_leaf())
      return u;
    else if (v->is_ne_child())
      return NW_CHILD(u);
    else
      return SW_CHILD(u);
  }
 
  static QuadNode * get_west_neighbor(QuadNode * v) noexcept
  {
    if (PARENT(v) == nullptr)
      return nullptr;
 
    if (v->is_ne_child())
      return NW_CHILD(PARENT(v));
 
    if (v->is_se_child())
      return SW_CHILD(PARENT(v));
 
    QuadNode * u = get_west_neighbor(PARENT(v));
 
    if (u == nullptr or u->is_leaf())
      return u;
    else if (v->is_nw_child())
      return NE_CHILD(u);
    else
      return SE_CHILD(u);
  }
 
  static void get_neighbors_by_side(QuadNode * node,
                                    const Side & side,
            DynList<QuadNode *> & neighbors)
  {
    if (node == nullptr)
      return;
 
    if (node->is_leaf())
      {
        neighbors.append(node);
        return;
      }
 
    switch(side)
      {
      case Side::West:
        get_neighbors_by_side(NW_CHILD(node), side, neighbors);
        get_neighbors_by_side(SW_CHILD(node), side, neighbors);
        break;
      case Side::East:
        get_neighbors_by_side(NE_CHILD(node), side, neighbors);
        get_neighbors_by_side(SE_CHILD(node), side, neighbors);
        break;
      case Side::North:
        get_neighbors_by_side(NW_CHILD(node), side, neighbors);
        get_neighbors_by_side(NE_CHILD(node), side, neighbors);
        break;
      case Side::South:
        get_neighbors_by_side(SW_CHILD(node), side, neighbors);
        get_neighbors_by_side(SE_CHILD(node), side, neighbors);
        break;
      default:
        ah_domain_error_if(true) << "Invalid side value";
    }
}
 
static size_t count_points(QuadNode * node) noexcept
{
  if (node == nullptr)
    return 0;
 
  if (node->is_leaf())
    return node->points.size();
 
  size_t num_points = 0;
 
  num_points += count_points(NW_CHILD(node));
  num_points += count_points(NE_CHILD(node));
  num_points += count_points(SW_CHILD(node));
  num_points += count_points(SE_CHILD(node));
 
  return num_points;
}
  
public:
 
  QuadNode() noexcept
    : points(), parent(nullptr), nw_child(nullptr), ne_child(nullptr),
      sw_child(nullptr), se_child(nullptr), color(Color::White), level(0),
      min_x(0), max_x(0), min_y(0), max_y(0)
  {
    // Empty
  }
  
  QuadNode(const Geom_Number & _min_x, const Geom_Number & _max_x,
     const Geom_Number & _min_y, const Geom_Number & _max_y,
     QuadNode * _parent = nullptr)
    : points(), parent(_parent), nw_child(nullptr), ne_child(nullptr),
      sw_child(nullptr), se_child(nullptr), color(Color::White), level(0),
      min_x(_min_x), max_x(_max_x), min_y(_min_y), max_y(_max_y)
  {
    ah_domain_error_if(min_x >= max_x or min_y >= max_y)
      << "QuadNode bounds must define a non-empty region";
  }
 
  QuadNode(const QuadNode &) = delete;
 
  void set_region(const Geom_Number & _min_x,
      const Geom_Number & _max_x,
                  const Geom_Number & _min_y,
                  const Geom_Number & _max_y)
  {
    ah_domain_error_if(_min_x >= _max_x or _min_y >= _max_y)
      << "QuadNode bounds must define a non-empty region";
 
    min_x = _min_x;
    max_x = _max_x;
    min_y = _min_y;
    max_y = _max_y;
  }
 
  [[nodiscard]] QuadNode *& get_parent() noexcept { return parent; }
 
  [[nodiscard]] QuadNode *& get_nw_child() noexcept { return nw_child; }
 
  [[nodiscard]] QuadNode *& get_ne_child() noexcept { return ne_child; }
 
  [[nodiscard]] QuadNode *& get_sw_child() noexcept { return sw_child; }
 
  [[nodiscard]] QuadNode *& get_se_child() noexcept { return se_child; }
 
  [[nodiscard]] Color & get_color() noexcept { return color; }
 
  [[nodiscard]] unsigned long & get_level() noexcept { return level; }
 
  [[nodiscard]] bool is_leaf() const noexcept { return color != Color::Gray; }
 
  [[nodiscard]] bool is_nw_child() const noexcept
  {
    if (parent == nullptr)
      return false;
    return NW_CHILD(parent) == this;
  }
 
  [[nodiscard]] bool is_ne_child() const noexcept
  {
    if (parent == nullptr)
      return false;
    return NE_CHILD(parent) == this;
  }
 
  [[nodiscard]] bool is_sw_child() const noexcept
  {
    if (parent == nullptr)
      return false;
    return SW_CHILD(parent) == this;
  }
 
  [[nodiscard]] bool is_se_child() const noexcept
  {
    if (parent == nullptr)
      return false;
    return SE_CHILD(parent) == this;
  }
 
  [[nodiscard]] bool contains(const Point & p) const noexcept
  {
    return p.get_x() >= min_x and p.get_x() < max_x and
           p.get_y() >= min_y and p.get_y() < max_y;
  }
 
  [[nodiscard]] QuadNode * get_child_to(const Point & p) const
  {
    assert(nw_child != nullptr);
    assert(ne_child != nullptr);
    assert(sw_child != nullptr);
    assert(se_child != nullptr);
 
    ah_domain_error_if(not contains(p))
      << "This node does not contain that point";
 
    if (nw_child->contains(p))
      return nw_child;
 
    if (ne_child->contains(p))
      return ne_child;
 
    if (sw_child->contains(p))
      return sw_child;
 
    if (se_child->contains(p))
      return se_child;
 
    return nullptr; // To avoid compiler warnings
  }
 
  Point & add_point(const Point & p)
  {
    color = Color::Black;
    return points.append(p);
  }
 
  [[nodiscard]] size_t get_num_points() noexcept
  {
    return count_points(this);
  }
 
  [[nodiscard]] const Geom_Number & get_min_x() const noexcept { return min_x; }
 
  [[nodiscard]] const Geom_Number & get_max_x() const noexcept { return max_x; }
 
  [[nodiscard]] const Geom_Number & get_min_y() const noexcept { return min_y; }
 
  [[nodiscard]] const Geom_Number & get_max_y() const noexcept { return max_y; }
 
  [[nodiscard]] Geom_Number get_width() const noexcept { return max_x - min_x; }
 
  [[nodiscard]] Geom_Number get_height() const noexcept { return max_y - min_y; }
 
  [[nodiscard]] Geom_Number get_mid_x() const noexcept { return (min_x + max_x) / 2; }
 
  [[nodiscard]] Geom_Number get_mid_y() const noexcept { return (min_y + max_y) / 2; }
 
  [[nodiscard]] Point * search_point(const Point & p) noexcept
  {
    for (Point & point : points)
      {
        if (point == p)
          return &point;
      }
    return nullptr;
  }
 
  bool remove_point(const Point & p)
  {
    for (DynList<Point>::iterator it(points); it.has_curr(); it.next_ne())
      {
        const Point & curr = it.get_curr_ne();
  
        if (curr == p)
          {
            it.del();
            if (points.is_empty())
              color = Color::White;
            return true;
          }
      }
    return false;
  }
 
  void empty() noexcept
  {
    points.empty();
    color = Color::White;
  }
 
  [[nodiscard]] DynList<QuadNode *> get_neighbors()
  {
    DynList<QuadNode *> neighbors;
    
    QuadNode * north_neighbor = get_north_neighbor(this);
    get_neighbors_by_side(north_neighbor, Side::South, neighbors);
 
    QuadNode * south_neighbor = get_south_neighbor(this);
    get_neighbors_by_side(south_neighbor, Side::North, neighbors);
 
    QuadNode * east_neighbor = get_east_neighbor(this);
    get_neighbors_by_side(east_neighbor, Side::West, neighbors);
 
    QuadNode * west_neighbor = get_west_neighbor(this);
    get_neighbors_by_side(west_neighbor, Side::East, neighbors);
 
    return neighbors;
  }
 
  [[nodiscard]] DynList<Point> & get_points_set() noexcept { return points; }
 
  template <class Op>
  void for_each_point(Op & op)
  {
    for (Point & point : points)
      op(point);
  };
 
  template <class Op>
  void for_each_point(Op && op = Op())
  {
    for_each_point<Op>(op);
  }
 
  QuadNode & operator = (const QuadNode &) = delete;
};
 
# endif // QUADNODE_H