redblacktree_fwd.h

// Description: Red-black tree types

#ifndef PASTELSYS_REDBLACKTREE_FWD_H
#define PASTELSYS_REDBLACKTREE_FWD_H

#include "pastel/sys/generic/class.h"
#include "pastel/sys/range.h"

#include <type_traits>
#include <memory>

namespace Pastel
{

    namespace RedBlackTree_
    {

        template <typename, typename, bool>
        class Iterator;

        class Node;

        template <typename>
        class Propagation_Node;

        template <typename>
        class Sentinel_Node;

        template <typename>
        class Data_Node;

        template <typename>
        class Key_Node;

    }

    template <typename, template <typename> class>
    class RedBlackTree;

    template <typename Settings>
    class RedBlackTree_Fwd
    {
    public:
        using Fwd = Settings;

        PASTEL_FWD(Key);
        PASTEL_FWD(Propagation);
        PASTEL_FWD(Data);
        PASTEL_FWD(SentinelData);
        PASTEL_FWD(Less);

        static constexpr bool MultipleKeys =
            Settings::MultipleKeys;

        static constexpr bool UserDataInSentinelNodes =
            Settings::UserDataInSentinelNodes;

        static constexpr bool UserDataInSentinelNodes_ =
            UserDataInSentinelNodes;

        struct Key_Tag;
        using Key_Class = Class<Key, Key_Tag>;
        using Key_Class_ = Key_Class;

        struct Data_Tag;
        using Data_Class = Class<Data, Data_Tag>;
        using Data_Class_ = Data_Class;

        struct Propagation_Tag;
        using Propagation_Class = Class<Propagation, Propagation_Tag>;
        using Propagation_Class_ = Propagation_Class;

        struct SentinelData_Tag;
        using SentinelData_Class = Class<SentinelData, SentinelData_Tag>;
        using SentinelData_Class_ = SentinelData_Class;

        static constexpr bool DereferenceToData =
            !std::is_same<Data, void>::value;

        class Node_Settings;
        using Propagation_Node = RedBlackTree_::Propagation_Node<Node_Settings>;
        using Data_Node = RedBlackTree_::Data_Node<Node_Settings>;

        class Node_Settings
        {
        public:
            PASTEL_FWD(Key);
            using Key_Class = Key_Class_;
            using Propagation_Class = Propagation_Class_;
            using Data_Class = Data_Class_;
            using SentinelData_Class = SentinelData_Class_;
            static constexpr bool UserDataInSentinelNodes =
                UserDataInSentinelNodes_;
            using EndBase = typename std::conditional<
                UserDataInSentinelNodes,
                Data_Node,
                Propagation_Node>::type;
        };

        using Node = RedBlackTree_::Node;
        using Sentinel_Node = RedBlackTree_::Sentinel_Node<Node_Settings>;
        using SentinelPtr = std::shared_ptr<Sentinel_Node>;
        using Key_Node = RedBlackTree_::Key_Node<Node_Settings>;

        template <
            typename NodePtr, 
            bool DereferenceToData>
        class Range_
        : public boost::iterator_range<RedBlackTree_::Iterator<
            NodePtr, Node_Settings, DereferenceToData>>
        {
        public:
            using Base = boost::iterator_range<RedBlackTree_::Iterator<
                NodePtr, Node_Settings, DereferenceToData>>;

            //! Forwards all constructors to the underlying range.
            /*!
           Time complexity: O(1)
           Exception safety: nothrow
           */
            template <typename... Type>
            explicit Range_(Type&&... that)
                : Base(std::forward<Type>(that)...)
            {
            }

            template <typename That_NodePtr, bool That_DereferenceToData>
            Range_(const Range_<That_NodePtr, That_DereferenceToData>& that)
            : Base(that)
            {
            }

            using Key_Range = Range_<NodePtr, false>;
            using Data_Range = Range_<NodePtr, true>;

            Key_Range dereferenceKey() const
            {
                return *this;
            }

            Data_Range dereferenceData() const
            {
                return *this;
            }
        };

        using Iterator = 
            RedBlackTree_::Iterator<Node*, Node_Settings, DereferenceToData>;
        using ConstIterator = 
            RedBlackTree_::Iterator<const Node*, Node_Settings, DereferenceToData>;
        using Range = 
            Range_<Node*, DereferenceToData>;
        using ConstRange = 
            Range_<const Node*, DereferenceToData>;

        using Insert_Return =
            typename std::conditional<MultipleKeys,
            Iterator,
            std::pair<Iterator, bool >>::type;

        struct FindEqual_Return
        {
            //! The top-most element equivalent to the key.
            ConstIterator equal;

            //! An element greater than the key.
            /*!
           This is the least element greater than the key,
           subject to being an ancestor of 'equal'.
           */
            ConstIterator upper;
        };

        struct FindInsert_Return
        {
            //! The element under which the key should be inserted.
            /*!
           The position is chosen subject only to the binary search
           property. Simply linking the key under the returned
           node preserves the binary-search property, but
           usually breaks the red-black invariants.
           */
            ConstIterator parent;

            //! Whether the insertion should be to the right child.
            bool right;

            //! An element greater than the key.
            /*!
           This is the least element greater than the key,
           subject to being an ancestor of 'parent'.
           */
            ConstIterator upper;
        };
    };

}

namespace Pastel
{

    template <
        typename Key_ = void, 
        typename Data_ = void,
        typename Less_ = LessThan,
        typename Propagation_ = void,
        typename SentinelData_ = void,
        bool MultipleKeys_ = false,
        bool UserDataInSentinelNodes_ = false>
    class RedBlackTree_Set_Settings
    {
    public:
        using Key = Key_;
        using Data = Data_;
        using Less = Less_;
        using Propagation = Propagation_;
        using SentinelData = SentinelData_;
        static constexpr bool MultipleKeys = MultipleKeys_;
        static constexpr bool UserDataInSentinelNodes = UserDataInSentinelNodes_;
    };

}

// FIX: We could do the below much clearer by forwarding a parameter pack
// instead. Unfortunately, that triggers a bug in Visual Studio 2013 SP2.
// Fix this after the bug is resolved.

namespace Pastel
{

    // Map

    template <
        typename Key = void, 
        typename Data = void,
        typename Less = LessThan,
        typename Propagation = void,
        typename SentinelData = void,
        bool UserDataInSentinelNodes = false>
    using RedBlackTree_Set_Fwd = 
        RedBlackTree_Fwd<RedBlackTree_Set_Settings<
            Key, Data, Less, Propagation, SentinelData, false,
            UserDataInSentinelNodes>>;

    // Multi-map

    template <
        typename Key = void, 
        typename Data = void,
        typename Less = LessThan,
        typename Propagation = void,
        typename SentinelData = void,
        bool UserDataInSentinelNodes = false>
    using RedBlackTree_MultiSet_Fwd = 
        RedBlackTree_Fwd<RedBlackTree_Set_Settings<
            Key, Data, Less, Propagation, SentinelData, true,
            UserDataInSentinelNodes>>;

}

#endif