tpl_binNode.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  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 for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
# ifndef TPL_BINNODE_H
# define TPL_BINNODE_H
 
# include <iostream>
# include <ahDefs.H>
# include <ahAssert.H>

namespace Aleph {
 
 
struct Empty_Node 
{
  Empty_Node() noexcept { /* empty */ }

  Empty_Node(SentinelCtor) noexcept { /* empty */ }

  void reset() noexcept { /* empty */ }

  Empty_Node & get_data() 
  { 
    throw std::domain_error("Empty_Node has not data"); 
  }
};

# define INIT_CLASS_BINNODE(Name, height, Control_Data)       \
  template <typename Key>                                               \
  class Name : public Control_Data                                      \
  {                                                                     \
  public:                                                               \
    static const size_t MaxHeight = height;                             \
    static Name * const NullPtr;                                        \
    typedef Key key_type;                                               \
    typedef Key Key_Type;                                               \
                                                                        \
  private:                                                              \
                                                                        \
    Key    key = Key();                                                 \
    Name * lLink;                                                       \
    Name * rLink;                                                       \
                                                                        \
  public:                                                               \
                                                                        \
    Key & get_key() noexcept { return key; }                            \
    const Key & get_key() const noexcept { return key; }                \
    Name *& getL() noexcept { return lLink; }                           \
    Name *& getR() noexcept { return rLink; }                           \
    const Name * getL() const noexcept { return lLink; }                \
    const Name * getR() const noexcept { return rLink; }                \
    Name(const Key& k) noexcept(noexcept(Key(key)))                     \
      : key(k), lLink(NullPtr), rLink(NullPtr)                          \
    {                                                                   \
      static_assert(std::is_copy_constructible<Key>::value,             \
                    "No copy constructor for Key");                     \
    }                                                                   \
    Name(Key && k) noexcept(noexcept(std::swap(key, k)))                \
      : key(std::move(k)), lLink(NullPtr), rLink(NullPtr)               \
    {                                                                   \
      static_assert(std::is_move_constructible<Key>::value,             \
                    "No move constructor for Key");                     \
    }                                                                   \
    Name(const Control_Data & control_data, const Key & k)              \
      noexcept(noexcept(Key(k)))                                        \
      : Control_Data(control_data),                                     \
      key(k), lLink(NullPtr), rLink(NullPtr)                            \
    {                                                                   \
      /* Empty */                                                       \
    }                                                                   \
    Name(const Name & node) noexcept(noexcept(Key(node.key)))           \
      : Control_Data(node),                                             \
      key(node.key), lLink(NullPtr), rLink(NullPtr)                     \
    {                                                                   \
      /* Empty */                                                       \
    }                                                                   \
    Name(Name && node)                                                  \
      noexcept(noexcept(std::forward<Key>(node).key))                   \
      : Control_Data(std::forward<Control_Data>(node)),                 \
      key(std::forward<Key>(node).key), lLink(NullPtr), rLink(NullPtr)  \
    {                                                                   \
      /* Empty */                                                       \
    }                                                                   \
    Name(const Control_Data & control_data) noexcept :                  \
      Control_Data(control_data),                                       \
      lLink(NullPtr), rLink(NullPtr)                                    \
    {                                                                   \
      /* Empty */                                                       \
    }                                                                   \
    Name() noexcept(std::is_nothrow_constructible<Key>::value)          \
      : lLink(NullPtr), rLink(NullPtr)                                  \
    {                                                                   \
      static_assert(std::is_default_constructible<Key>::value,          \
                    "No default constructor for Key");                  \
    }                                                                   \
    void reset() noexcept                                               \
    {                                                                   \
      Control_Data::reset();                                            \
      rLink = lLink = NullPtr;                                          \
    }                                                                   \
    static Name * key_to_node(Key & __key) noexcept                     \
    {                                                                   \
      Name * node_zero = 0;                                             \
      size_t offset = (size_t) &(node_zero->key);                       \
      unsigned long addr = (unsigned long)(&__key);                     \
      return (Name*) (addr - offset);                                   \
    }


# define DECLARE_BINNODE(Name, height, Control_Data)                 \
  INIT_CLASS_BINNODE(Name, height, Control_Data)                        \
};                                                                      \
  template <typename Key> Name<Key> * const Name<Key>::NullPtr = nullptr; \
  INIT_CLASS_BINNODE(Name##Vtl, height, Control_Data)                   \
  virtual ~Name##Vtl() { /* empty */ }                                  \
  };                                                                    \
 template <typename Key> Name##Vtl<Key> *                               \
 const Name##Vtl<Key>::NullPtr = nullptr


# define DECLARE_BINNODE_SENTINEL(Name, height, Control_Data)    \
  INIT_CLASS_BINNODE(Name, height, Control_Data)                        \
  Name(SentinelCtor) :                                                  \
  Control_Data(sentinelCtor), lLink(NullPtr), rLink(NullPtr) {}         \
  static Name sentinel_node;                                            \
};                                                                      \
  template <typename Key>                                               \
  Name<Key> Name<Key>::sentinel_node(sentinelCtor);                     \
  template <typename Key>                                               \
  Name<Key> * const Name<Key>::NullPtr = &Name<Key>::sentinel_node;     \
  INIT_CLASS_BINNODE(Name##Vtl, height, Control_Data)                   \
  virtual ~Name##Vtl() { /* empty */ }                                  \
private:                                                                \
 Name##Vtl(SentinelCtor) :                                              \
 Control_Data(sentinelCtor), lLink(NullPtr), rLink(NullPtr) {}          \
 static Name##Vtl sentinel_node;                                        \
 };                                                                     \
   template <typename Key>                                              \
   Name##Vtl<Key> Name##Vtl<Key>::sentinel_node(sentinelCtor);          \
   template <typename Key>                                              \
   Name##Vtl<Key> * const Name##Vtl<Key>::NullPtr =                     \
     &Name##Vtl<Key>::sentinel_node

template <class Node> inline Node *& LLINK(Node * p) noexcept 
{
  return p->getL(); 
}

template <class Node> inline Node *& RLINK(Node * p) noexcept
{
  return p->getR(); 
}


  template <class Node> inline
typename Node::Key_Type & KEY(Node * p) noexcept { return p->get_key(); }

DECLARE_BINNODE(BinNode, 2048, Empty_Node);


} // end namespace Aleph
# endif