spatial_node.hpp

// -*- C++ -*-
//
// Copyright Sylvain Bougerel 2009 - 2013.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file COPYING or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef SPATIAL_NODE_HPP
#define SPATIAL_NODE_HPP

#include <iterator> // std::bidirectional_iterator_tag and
                    // std::forward_iterator_tag
#include "../spatial.hpp"
#include "spatial_assert.hpp"
#include "spatial_mutate.hpp"

namespace spatial
{
  namespace details
  {
    template <typename Link>
    struct Node
    {
      typedef Link              link_type;

      Node* parent;

      Node* left;

      Node* right;
    };

    template <typename Link>
    inline bool header(const Node<Link>* x)
    { return (x->left == x); }

    template <typename Link>
    inline Node<Link>* minimum(Node<Link>* x)
    {
      SPATIAL_ASSERT_CHECK(!header(x));
      while (x->left != 0) x = x->left; return x;
    }

    template <typename Link>
    inline const Node<Link>* minimum(const Node<Link>* x)
    {
      SPATIAL_ASSERT_CHECK(!header(x));
      while (x->left != 0) x = x->left; return x;
    }

    template <typename Link>
    inline Node<Link>* maximum(Node<Link>* x)
    {
      SPATIAL_ASSERT_CHECK(!header(x));
      while (x->right != 0) x = x->right; return x;
    }

    template <typename Link>
    inline const Node<Link>* maximum(const Node<Link>* x)
    {
      SPATIAL_ASSERT_CHECK(!header(x));
      while (x->right != 0) x = x->right; return x;
    }

    template <typename Link> Node<Link>*
    increment(Node<Link>* x);

    template <typename Link>
    inline const Node<Link>*
    increment(const Node<Link>* x)
    { return increment(const_cast<Node<Link>*>(x)); }

    template <typename Link>
    Node<Link>*
    decrement(Node<Link>* x);

    template <typename Link>
    inline const Node<Link>*
    decrement(const Node<Link>* x)
    { return decrement(const_cast<Node<Link>*>(x)); }

    template <typename Link> const Node<Link>*
    preorder_increment(const Node<Link>* x);

    struct relaxed_invariant_tag { };
    struct strict_invariant_tag { };

    template <typename Link>
    inline typename Link::invariant_category
    invariant_category(const Node<Link>*)
    { return typename Link::invariant_category(); }

    template<typename Key, typename Value>
    struct Kdtree_link : Node<Kdtree_link<Key, Value> >
    {
      typedef Key                                  key_type;
      typedef Value                                value_type;
      typedef Kdtree_link<Key, Value>              link_type;
      typedef link_type*                           link_ptr;
      typedef const link_type*                     const_link_ptr;
      typedef Node<link_type>*                     node_ptr;
      typedef const Node<link_type>*               const_node_ptr;
      typedef strict_invariant_tag                 invariant_category;

      Kdtree_link() : value() { }

      Value value;

    private:
      Kdtree_link<Key, Value>&
      operator= (const Kdtree_link<Key, Value>&);
    };

    template<typename Key, typename Value>
    struct Relaxed_kdtree_link : Node<Relaxed_kdtree_link<Key, Value> >
    {
      typedef Key                                 key_type;
      typedef Value                               value_type;
      typedef Relaxed_kdtree_link<Key, Value>     link_type;
      typedef link_type*                          link_ptr;
      typedef const link_type*                    const_link_ptr;
      typedef Node<link_type>*                    node_ptr;
      typedef const Node<link_type>*              const_node_ptr;
      typedef relaxed_invariant_tag               invariant_category;

      Relaxed_kdtree_link() { }

      Value value;

      weight_type weight;

    private:
      Relaxed_kdtree_link<Key, Value>&
      operator= (const Relaxed_kdtree_link<Key, Value>&);
    };

    template <typename Key, typename Value>
    inline Kdtree_link<Key, Value>*
    link(Node<Kdtree_link<Key, Value> >* node)
    {
      return static_cast<Kdtree_link<Key, Value>*>(node);
    }

    template <typename Key, typename Value>
    inline const Kdtree_link<Key, Value>*
    const_link(const Node<Kdtree_link<Key, Value> >* node)
    {
      return static_cast<const Kdtree_link<Key, Value>*>(node);
    }

    template <typename Value>
    inline const typename Kdtree_link<Value, Value>::key_type&
    const_key(const Node<Kdtree_link<Value, Value> >* node)
    {
      return static_cast<const Kdtree_link<Value, Value>*>(node)->value;
    }

    template <typename Key, typename Value>
    inline const typename Kdtree_link<Key, Value>::key_type&
    const_key(const Node<Kdtree_link<Key, Value> >* node)
    {
      return static_cast<const Kdtree_link<Key, Value>*>(node)->value.first;
    }

    template <typename Key, typename Value>
    inline typename Kdtree_link<Key, Value>::value_type&
    value(Node<Kdtree_link<Key, Value> >* node)
    {
      return static_cast<Kdtree_link<Key, Value>*>(node)->value;
    }

    template <typename Key, typename Value>
    inline const typename Kdtree_link<Key, Value>::value_type&
    const_value(const Node<Kdtree_link<Key, Value> >* node)
    {
      return static_cast<const Kdtree_link<Key, Value>*>(node)->value;
    }

    template <typename Key, typename Value>
    inline Relaxed_kdtree_link<Key, Value>*
    link(Node<Relaxed_kdtree_link<Key, Value> >* node)
    {
      return static_cast<Relaxed_kdtree_link<Key, Value>*>(node);
    }

    template <typename Key, typename Value>
    inline const Relaxed_kdtree_link<Key, Value>*
    const_link(const Node<Relaxed_kdtree_link<Key, Value> >* node)
    {
      return static_cast<const Relaxed_kdtree_link<Key, Value>*>(node);
    }

    template <typename Value>
    inline const typename Relaxed_kdtree_link<Value, Value>::key_type&
    const_key(const Node<Relaxed_kdtree_link<Value, Value> >* node)
    {
      return static_cast
        <const Relaxed_kdtree_link<Value, Value>*>(node)->value;
    }

    template <typename Key, typename Value>
    inline const typename Relaxed_kdtree_link<Key, Value>::key_type&
    const_key(const Node<Relaxed_kdtree_link<Key, Value> >* node)
    {
      return static_cast<const Relaxed_kdtree_link<Key, Value>*>
        (node)->value.first;
    }

    template <typename Key, typename Value>
    inline typename Relaxed_kdtree_link<Key, Value>::value_type&
    value(Node<Relaxed_kdtree_link<Key, Value> >* node)
    {
      return static_cast<Relaxed_kdtree_link<Key, Value>*>(node)->value;
    }

    template <typename Key, typename Value>
    inline const typename Relaxed_kdtree_link<Key, Value>::value_type&
    const_value(const Node<Relaxed_kdtree_link<Key, Value> >* node)
    {
      return static_cast<const Relaxed_kdtree_link<Key, Value>*>(node)->value;
    }

    template <typename Link>
    void swap_node_aux(Node<Link>* a, Node<Link>* b);

    template<typename Key, typename Value>
    inline void swap_node(Node<Kdtree_link<Key, Value> >*& a,
                          Node<Kdtree_link<Key, Value> >*& b)
    { swap_node_aux(a, b); std::swap(a, b); }

    template<typename Key, typename Value>
    inline void swap_node(Node<Relaxed_kdtree_link<Key, Value> >*& a,
                          Node<Relaxed_kdtree_link<Key, Value> >*& b)
    {
      swap_node_aux(a, b);
      std::swap(link(a)->weight, link(b)->weight);
      std::swap(a, b);
    }

    template<typename Link>
    class Node_iterator
    {
    public:
      typedef typename mutate<typename Link::value_type>::type value_type;
      typedef typename Link::value_type&         reference;
      typedef typename Link::value_type*         pointer;
      typedef std::ptrdiff_t                     difference_type;
      typedef std::bidirectional_iterator_tag    iterator_category;
      typedef typename Link::node_ptr            node_ptr;

    private:
      typedef Node_iterator<Link>                Self;

    public:
      Node_iterator() : node() { }

      explicit Node_iterator(node_ptr x) : node(x) { }

      reference operator*()
      { return value(node); }

      pointer operator->()
      { return &value(node); }

      Self& operator++()
      { node = increment(node); return *this; }

      Self operator++(int)
      { Self tmp = *this; node = increment(node); return tmp; }

      Self& operator--()
      { node = decrement(node); return *this; }

      Self operator--(int)
      { Self tmp = *this; node = decrement(node); return tmp; }

      bool operator==(const Self& x) const
      { return node == x.node; }

      bool operator!=(const Self& x) const
      { return node != x.node; }

      node_ptr node;
    };

    template<typename Link>
    class Const_node_iterator
    {
    public:
      typedef typename mutate<typename Link::value_type>::type value_type;
      typedef const typename Link::value_type&   reference;
      typedef const typename Link::value_type*   pointer;
      typedef std::ptrdiff_t                     difference_type;
      typedef std::bidirectional_iterator_tag    iterator_category;
      typedef typename Link::const_node_ptr      node_ptr;

    private:
      typedef Const_node_iterator<Link>          Self;
      typedef Node_iterator<Link>                iterator;

    public:
      Const_node_iterator() : node() { }

      explicit
      Const_node_iterator(node_ptr x) : node(x) { }

      Const_node_iterator(const iterator& it) : node(it.node) { }

      reference operator*()
      { return const_value(node); }

      pointer operator->()
      { return &const_value(node); }

      Self& operator++()
      { node = increment(node); return *this; }

      Self operator++(int)
      { Self tmp = *this; node = increment(node); return tmp; }

      Self& operator--()
      { node = decrement(node); return *this; }

      Self operator--(int)
      { Self tmp = *this; node = decrement(node); return tmp; }

      bool operator==(const Self& x) const
      { return node == x.node; }

      bool operator!=(const Self& x) const
      { return node != x.node; }

      node_ptr node;
    };

    template<typename Link>
    struct Preorder_node_iterator
    {
      typedef typename mutate<typename Link::value_type>::type value_type;
      typedef const typename Link::value_type&  reference;
      typedef const typename Link::value_type*  pointer;
      typedef std::ptrdiff_t                    difference_type;
      typedef std::forward_iterator_tag         iterator_category;
      typedef typename Link::const_node_ptr     node_ptr;

    private:
      typedef Preorder_node_iterator<Link>      Self;

    public:
      Preorder_node_iterator() : node() { }

      explicit
      Preorder_node_iterator(node_ptr x) : node(x) { }

      reference operator*()
      { return const_value(node); }

      pointer operator->()
      { return &const_value(node); }

      Self& operator++()
      { node = preorder_increment(node); return *this; }

      Self operator++(int)
      { Self tmp = *this; node = preorder_increment(node); return tmp; }

      bool operator==(const Self& x) const
      { return node == x.node; }

      bool operator!=(const Self& x) const
      { return node != x.node; }

      node_ptr node;
    };

    template <typename Link> inline Node<Link>* increment(Node<Link>* x)
    {
      SPATIAL_ASSERT_CHECK(!header(x));
      if (x->right != 0)
        {
          x = x->right;
          while (x->left != 0) { x = x->left; }
        }
      else
        {
          Node<Link>* p = x->parent;
          while (!header(p) && x == p->right)
            { x = p; p = x->parent; }
          x = p;
        }
      return x;
    }

    template <typename Link> inline Node<Link>* decrement(Node<Link>* x)
    {
      SPATIAL_ASSERT_CHECK((!header(x) || x->parent != 0));
      if (header(x))
        { x = x->right; } // At header, 'right' points to the right-most node
      else if (x->left != 0)
        {
          Node<Link>* y = x->left;
          while (y->right != 0) { y = y->right; }
          x = y;
        }
      else
        {
          Node<Link>* p = x->parent;
          while (!header(p) && x == p->left)
            { x = p; p = x->parent; }
          x = p;
        }
      return x;
    }

    template <typename Link>
    inline void swap_node_aux
    (Node<Link>* a, Node<Link>* b)
    {
      typedef Node<Link>* node_ptr;
      if (a == b) return;
      SPATIAL_ASSERT_CHECK(!header(a));
      SPATIAL_ASSERT_CHECK(!header(b));
      if (a->parent == b)
        {
          if (header(b->parent))
            { b->parent->parent = a; }
          else
            {
              if (b->parent->left == b) { b->parent->left = a; }
              else { b->parent->right = a; }
            }
          if (a->left != 0) { a->left->parent = b; }
          if (a->right != 0) { a->right->parent = b; }
          a->parent = b->parent;
          b->parent = a;
          node_ptr a_left = a->left;
          node_ptr a_right = a->right;
          if (b->left == a)
            {
              if (b->right != 0) { b->right->parent = a; }
              a->left = b;
              a->right = b->right;
            }
          else
            {
              if (b->left != 0) { b->left->parent = a; }
              a->left = b->left;
              a->right = b;
            }
          b->left = a_left;
          b->right = a_right;
        }
      else if (b->parent == a)
        {
          if (header(a->parent))
            { a->parent->parent = b; }
          else
            {
              if (a->parent->left == a) { a->parent->left = b; }
              else { a->parent->right = b; }
            }
          if (b->left != 0) { b->left->parent = a; }
          if (b->right != 0) { b->right->parent = a; }
          b->parent = a->parent;
          a->parent = b;
          node_ptr b_left = b->left;
          node_ptr b_right = b->right;
          if (a->left == b)
            {
              if (a->right != 0) { a->right->parent = b; }
              b->left = a;
              b->right = a->right;
            }
          else
            {
              if (a->left != 0) { a->left->parent = b; }
              b->left = a->left;
              b->right = a;
            }
          a->left = b_left;
          a->right = b_right;
        }
      else
        {
          if (header(a->parent))
            { a->parent->parent = b; }
          else
            {
              if (a->parent->left == a) { a->parent->left = b; }
              else { a->parent->right = b; }
            }
          if (header(b->parent))
            { b->parent->parent = a; }
          else
            {
              if (b->parent->left == b) { b->parent->left = a; }
              else { b->parent->right = a; }
            }
          if (a->left != 0) { a->left->parent = b; }
          if (b->left != 0) { b->left->parent = a; }
          if (a->right != 0) { a->right->parent = b; }
          if (b->right != 0) { b->right->parent = a; }
          std::swap(a->parent, b->parent);
          std::swap(a->left, b->left);
          std::swap(a->right, b->right);
        }
    }

    template <typename Link> inline const Node<Link>*
    preorder_increment(const Node<Link>* x)
    {
      if (x->left != 0) { x = x->left; }
      else if (x->right != 0) { x = x->right; }
      else
        {
          const Node<Link>* p = x->parent;
          while (!header(p) && (x == p->right || p->right == 0))
            { x = p; p = x->parent; }
          x = p;
          if (!header(p)) { x = x->right; }
        }
      return x;
    }

  } // namespace details
} // namespace spatial

#endif // SPATIAL_NODE_HPP