quad_node.hpp

// SPDX-FileCopyrightText: 2010 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT
 
#pragma once
 
#include "mdds/global.hpp"
 
#include <cassert>
 
#include <boost/intrusive_ptr.hpp>
 
namespace mdds {
 
#ifdef MDDS_DEBUG_NODE_BASE
size_t node_instance_count = 0;
inline size_t get_node_instance_count()
{
    return node_instance_count;
}
#endif

enum node_quadrant_t
{
    quad_northeast,
    quad_northwest,
    quad_southeast,
    quad_southwest,
    quad_unspecified
};

enum search_region_space_t
{
    region_northwest,
    region_north,
    region_northeast,
    region_east,
    region_southeast,
    region_south,
    region_southwest,
    region_west,
    region_center
};

enum direction_t
{
    dir_north,
    dir_west,
    dir_south,
    dir_east
};
 
inline node_quadrant_t opposite(node_quadrant_t quad)
{
    switch (quad)
    {
        case quad_northeast:
            return quad_southwest;
        case quad_northwest:
            return quad_southeast;
        case quad_southeast:
            return quad_northwest;
        case quad_southwest:
            return quad_northeast;
        case quad_unspecified:
        default:;
    }
    return quad_unspecified;
}
 
template<typename _NodePtr, typename _NodeType, typename _Key>
struct quad_node_base
{
    typedef _Key key_type;
    typedef _NodePtr node_ptr;
    typedef _NodeType node_type;
 
    size_t refcount;
 
    node_ptr parent;
    node_ptr northeast;
    node_ptr northwest;
    node_ptr southeast;
    node_ptr southwest;
 
    key_type x;
    key_type y;
 
    quad_node_base(key_type _x, key_type _y)
        : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
          x(_x), y(_y)
    {
#ifdef MDDS_DEBUG_NODE_BASE
        ++node_instance_count;
#endif
    }

    quad_node_base(const quad_node_base& r)
        : refcount(0), parent(nullptr), northeast(nullptr), northwest(nullptr), southeast(nullptr), southwest(nullptr),
          x(r.x), y(r.y)
    {
#ifdef MDDS_DEBUG_NODE_BASE
        ++node_instance_count;
#endif
    }
 
    bool leaf() const
    {
        return !northeast && !northwest && !southeast && !southwest;
    }
 
    bool operator==(const quad_node_base& r) const
    {
        return x == r.x && y == r.y;
    }

    quad_node_base& operator=(const quad_node_base& r)
    {
        if (this == &r)
            // assignment to self.
            return *this;
 
        x = r.x;
        y = r.y;
        return *this;
    }
 
    ~quad_node_base()
    {
#ifdef MDDS_DEBUG_NODE_BASE
        --node_instance_count;
#endif
        static_cast<node_type*>(this)->dispose();
    }

    node_quadrant_t get_quadrant(key_type other_x, key_type other_y) const
    {
        if (other_x < x)
            // west
            return other_y < y ? quad_northwest : quad_southwest;
 
        // east
        return other_y < y ? quad_northeast : quad_southeast;
    }
 
    bool has_quadrant_node(node_quadrant_t quad) const
    {
        switch (quad)
        {
            case quad_northeast:
                return northeast.get() != nullptr;
            case quad_northwest:
                return northwest.get() != nullptr;
            case quad_southeast:
                return southeast.get() != nullptr;
            case quad_southwest:
                return southwest.get() != nullptr;
            default:
                throw general_error("unknown quadrant type");
        }
        return false;
    }
 
    node_ptr get_quadrant_node(node_quadrant_t quad) const
    {
        node_ptr ret;
        switch (quad)
        {
            case quad_northeast:
                ret = northeast;
                break;
            case quad_northwest:
                ret = northwest;
                break;
            case quad_southeast:
                ret = southeast;
                break;
            case quad_southwest:
                ret = southwest;
                break;
            default:
                throw general_error("unknown quadrant type");
        }
        return ret;
    }
};
 
template<typename _NodePtr, typename _NodeType, typename _Key>
inline void intrusive_ptr_add_ref(::mdds::quad_node_base<_NodePtr, _NodeType, _Key>* p)
{
    ++p->refcount;
}
 
template<typename _NodePtr, typename _NodeType, typename _Key>
inline void intrusive_ptr_release(::mdds::quad_node_base<_NodePtr, _NodeType, _Key>* p)
{
    --p->refcount;
    if (!p->refcount)
        delete p;
}
 
template<typename _NodePtr>
void disconnect_node_from_parent(_NodePtr p)
{
    if (!p || !p->parent)
        // Nothing to do.
        return;
 
    _NodePtr& parent = p->parent;
    if (parent->northeast && parent->northeast == p)
    {
        parent->northeast.reset();
    }
    else if (parent->northwest && parent->northwest == p)
    {
        parent->northwest.reset();
    }
    else if (parent->southwest && parent->southwest == p)
    {
        parent->southwest.reset();
    }
    else if (parent->southeast && parent->southeast == p)
    {
        parent->southeast.reset();
    }
    else
        throw general_error("parent node doesn't lead to the deleted node.");
}
 
template<typename _NodePtr>
void disconnect_all_nodes(_NodePtr p)
{
    if (!p)
        return;
 
    if (p->northeast)
    {
        disconnect_all_nodes(p->northeast);
        p->northeast.reset();
    }
 
    if (p->northwest)
    {
        disconnect_all_nodes(p->northwest);
        p->northwest.reset();
    }
 
    if (p->southeast)
    {
        disconnect_all_nodes(p->southeast);
        p->southeast.reset();
    }
 
    if (p->southwest)
    {
        disconnect_all_nodes(p->southwest);
        p->southwest.reset();
    }
 
    p->parent.reset();
}
 
template<typename _NodeType, typename _Key>
search_region_space_t get_search_region_space(_NodeType* p, _Key x1, _Key y1, _Key x2, _Key y2)
{
    typedef _Key key_type;
 
    key_type x = p->x, y = p->y;
    if (x < x1)
    {
        // western region
        if (y < y1)
        {
            return region_northwest;
        }
        else if (y1 <= y && y <= y2)
        {
            return region_west;
        }
 
        assert(y2 < y);
        return region_southwest;
    }
    else if (x1 <= x && x <= x2)
    {
        // central region
        if (y < y1)
        {
            return region_north;
        }
        else if (y1 <= y && y <= y2)
        {
            return region_center;
        }
 
        assert(y2 < y);
        return region_south;
    }
 
    // eastern region
    assert(x2 < x);
    if (y < y1)
    {
        return region_northeast;
    }
    else if (y1 <= y && y <= y2)
    {
        return region_east;
    }
 
    assert(y2 < y);
    return region_southeast;
}
 
} // namespace mdds