UT_RTreeImpl.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        RTree.C (UT library, C++)
 *
 * COMMENTS:
 */
 
#ifndef __UT_RTREEIMPL_H_INCLUDED__
#define __UT_RTREEIMPL_H_INCLUDED__

#include "UT_UniquePtr.h"

#include <utility>

template< typename BOX, typename ITEM_INDEX_REP >
struct UT_BoxedItemT
{
    //TODO: C++17: static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
    
    using Box = BOX;
    using ItemIndexRep = ITEM_INDEX_REP;

    Box myBox;
    ItemIndexRep myItem;

    UT_BoxedItemT() :
        myBox(),
        myItem(-1)
    {
    }

    UT_BoxedItemT(
        const Box& box,
        const ItemIndexRep item
    ) :
        myBox( box ),
        myItem( item )
    {
    }
};

#if 0

template< typename BOX, typename ITEM_INDEX_REP >
inline std::ostream& operator<<(std::ostream& os, const UT_BoxedItemT< BOX, ITEM_INDEX_REP >& bf)
{
    os << "BoxedItem{ ";
    os << "box = ";
    os << bf.myBox << ", ";
    os << "item = ";
    os << bf.myItem;
    os << " }";
    return os;
}

#endif

// Compute the bounding box for a range of boxes [begin, end)
template< typename BOX >
inline void computeBoundingBox(
    BOX& bounding_box,
    const BOX*const begin,
    const BOX*const end
)
{
    bounding_box = BOX(); // empty

    for( const BOX* i = begin; i != end; ++i )
    {
        bounding_box.absorbBox(*i);
    }
}

// Compute the bounding box for all the boxes in
// a range of boxed items [begin, end)
template< typename BOX, typename ITEM_INDEX_REP >
inline void computeBoundingBoxItem(
    BOX& bounding_box,
    const UT_BoxedItemT< BOX, ITEM_INDEX_REP >*const begin,
    const UT_BoxedItemT< BOX, ITEM_INDEX_REP >*const end
)
{
    static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );

    UT_ASSERT_P( end != begin );

    bounding_box = begin->myBox;

    for( const UT_BoxedItemT< BOX, ITEM_INDEX_REP >* i = begin + 1; i != end; ++i )
    {
        bounding_box.absorbBox(i->myBox);
    }
}

namespace UT
{

template< typename ITEM_INDEX_REP, int MAX_ORDER >
class RNodeT
{
public:
    //TODO: C++17: static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );

    using Slot = std::make_unsigned_t< ITEM_INDEX_REP >;

    RNodeT()
    {
        clear();
    }

    ~RNodeT()
    {
    }

    void clear()
    {
        setInternal(false);
        for( int s = 0; s < MAX_ORDER; ++s )
        {
            mySlots[s] = SLOT_VALUE_EMPTY;
        }
    }

    void setInternal(const bool isInternal)
    {
        mySlots[0] = ( (mySlots[0] & SLOT_MASK_INDEX) |
                       (isInternal ? SLOT_FLAG_INTERNAL : 0) );
    }

    // Assuming this is an internal node, assign a node index to slot #s
    void assignSubtree( const int s, const Slot index_root_subtree )
    {
        UT_ASSERT_P( isInternal() );
        UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
        UT_ASSERT_P( 0 <= index_root_subtree );
        UT_ASSERT_P( ( index_root_subtree & SLOT_MASK_INDEX ) == index_root_subtree );

        mySlots[s] = index_root_subtree | SLOT_FLAG_INTERNAL;
    }

    // Assign an item to slot #s
    void assignItem( const int s, const ITEM_INDEX_REP item )
    {
        UT_ASSERT_P( !isInternal() );
        UT_ASSERT_P( (0 <= s) && (s < MAX_ORDER) );
        UT_ASSERT_P( 0 <= item );
        UT_ASSERT_P( ( item & SLOT_MASK_INDEX) == item );

        mySlots[s] = item;
    }

    bool isInternal() const
    {
        return ((mySlots[0] & SLOT_FLAG_INTERNAL) != 0);
    }

    // Get node stored in slot.
    // This assumes that the last configuration to this slot was an node!
    // (not an item)
    Slot getSubtree(const int s) const
    {
        UT_ASSERT( isInternal() );
        UT_ASSERT( (0 <= s) && (s < MAX_ORDER) );
        UT_ASSERT( (mySlots[s] & SLOT_MASK_INDEX) != SLOT_VALUE_EMPTY );

        return (mySlots[s] & SLOT_MASK_INDEX);
    }

    // For internal nodes, count the number of children
    // For leaf nodes, count the number of items
    ITEM_INDEX_REP countNumItems() const
    {
        ITEM_INDEX_REP num_items(0);
        for( int s = 0; s < MAX_ORDER; ++s )
        {
            if( (mySlots[s] & SLOT_MASK_INDEX) == SLOT_VALUE_EMPTY )
                break;

            ++num_items;
        }

        return num_items;
    }

    // Get item index stored in slot.
    // This assumes that the last configuration to this slot was an item!
    // (not an RTree node)
    SYS_FORCE_INLINE ITEM_INDEX_REP getItemIndexRep( const int s ) const
    {
        UT_ASSERT( !isInternal() );
        UT_ASSERT( (0 <= s) && (s < MAX_ORDER) );
        UT_ASSERT( (mySlots[s] & SLOT_MASK_INDEX) != SLOT_VALUE_EMPTY );

        return (mySlots[s] & SLOT_MASK_INDEX);
    }

    static const Slot SLOT_FLAG_INTERNAL = Slot( 1 ) << ( ( sizeof( Slot ) * 8 ) - 1 );
    static const Slot SLOT_MASK_INDEX    = SLOT_FLAG_INTERNAL - 1;
    static const Slot SLOT_VALUE_EMPTY   = SLOT_MASK_INDEX;

    //
    // mySlots[0] has a bit that defines whether the node is an internal
    // node. This is the SLOT_FLAG_INTERNAL bit.
    // In an internal node, each non-empty slot has the index of a child
    // node.
    // In a leaf node, each non-empty slot has the index of an item.
    //
    // A node (internal or leaf) may not always be full
    // (fewer than MAX_ORDER children for internal node case, or fewer than
    // MAX_ORDER items for leaf case).
    // When the node is not full, then the empty slots form
    // a contiguous range after all the nonempty slots.
    // The full range consists of the slots s in the half-open range
    // [ 0, num_items )
    //

    Slot mySlots[ MAX_ORDER ];
};

// Determine the exact number of nodes needed to store an R-tree of MAX_ORDER
// based on "size" nonempty boxes.
// The O(log n) cost of this calculation is insignificant compared to
// the time it takes to construct the tree.
inline size_t
subtreeDetermineNumNodes( const int MAX_ORDER, const size_t size )
{
    int num_nodes(0);

    if( size > MAX_ORDER )
    {
        // Internal node

        ++num_nodes;

        size_t m(MAX_ORDER);
        while( m * MAX_ORDER < size )
        {
            m *= MAX_ORDER;
        }

        UT_ASSERT_P( MAX_ORDER <= m );
        UT_ASSERT_P( m < size );

        // Count number of nodes for the at most MAX_ORDER subtrees that
        // have exactly m elements

        const size_t num_subtrees_size_m( size / m );

        UT_ASSERT_P( num_subtrees_size_m <= MAX_ORDER );

        const size_t num_nodes_for_m( subtreeDetermineNumNodes(MAX_ORDER, m) );

        num_nodes += num_subtrees_size_m * num_nodes_for_m;

        // Count number of nodes for the subtree with the less than m
        // remaining elements (if this exists)

        const size_t num_remaining_items( size % m );
        if( num_remaining_items > 0 )
        {
            num_nodes += subtreeDetermineNumNodes(MAX_ORDER, num_remaining_items);
        }
    }
    else
    {
        // Leaf node

        ++num_nodes;
    }

    return num_nodes;
}

/// Partition the range of boxed items [begin, end) according to the given
/// comparison function such that all items in the range [0, m-1] are less than
/// or equal to all items in [m, 2m-1], which are less than or equal to all
/// items in [2m, 3m-1], etc, where m is the subtree size.
template< typename BOX, typename ITEM_INDEX_REP >
struct PartitionForSubtrees
{
    template< typename IS_LESS_THAN >
    constexpr inline void operator()(
        UT_BoxedItemT< BOX, ITEM_INDEX_REP >*const begin,
        UT_BoxedItemT< BOX, ITEM_INDEX_REP >*const end,
        IS_LESS_THAN&& is_less_than,
        const ITEM_INDEX_REP m,
        const int num_subtrees
    ) const noexcept
    {
        if( num_subtrees <= 1 )
        {
            return;
        }
        
        // Choose a multiple of the subtree size that's close to the middle, and
        // partition so that all items in [begin, begin + i) are less than or equal
        // to all items in [begin + i, end).
        const auto mid{ num_subtrees / 2 };
        const auto i{ mid * m };
        UTnth_element( begin, begin + i, end, is_less_than );

        // Recursively partition each side.
        PartitionForSubtrees< BOX, ITEM_INDEX_REP >{}( begin, begin + i, std::forward< IS_LESS_THAN >( is_less_than ), m, mid);
        PartitionForSubtrees< BOX, ITEM_INDEX_REP >{}( begin + i, end, std::forward< IS_LESS_THAN >( is_less_than ), m, num_subtrees - mid);
    }
};

// Create a subtree for the range of boxed items [begin, end).
// Return a pointer to the subtree root (this points into in shared_nodes)
// In addition, bounding_box will be a bounding box for the subtree.
// PRE: Each boxed item in [begin, end) has a nonempty box
// NOTE: No allocations are performed by this function, the returned pointer
// points into the array 'shared_nodes'
template< typename BOX, typename ITEM_INDEX_REP, int MAX_ORDER >
inline RNodeT< ITEM_INDEX_REP, MAX_ORDER >*
subtreeCreate(
    BOX& bounding_box,
    BOX shared_boxes[],
    UT_BoxedItemT< BOX, ITEM_INDEX_REP >*const begin,
    UT_BoxedItemT< BOX, ITEM_INDEX_REP >*const end,
    RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[],
    RNodeT< ITEM_INDEX_REP, MAX_ORDER >*& shared_nodes_end
)
{
    static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );

    using RNode = RNodeT< ITEM_INDEX_REP, MAX_ORDER >;
    using Box = BOX;
    using BoxedItem = UT_BoxedItemT< Box, ITEM_INDEX_REP >;
    
    SYS_STATIC_ASSERT( MAX_ORDER >= 2 );

#if UT_ASSERT_LEVEL >= UT_ASSERT_LEVEL_PARANOID
    for( const BoxedItem* i = begin; i != end; ++i )
    {
        UT_ASSERT_P( ! i->myBox.isEmpty() );
    }
#endif

    // Claim storage for the root node
    RNode* node( shared_nodes_end++ );

    node->clear();

    // node_boxes is the sub-array that contains the at most MAX_ORDER boxes
    // for the node that we're building
    Box*const node_boxes( shared_boxes + ((node - shared_nodes) * MAX_ORDER) );

    const size_t size(end - begin);

    UT_ASSERT_P( size > 0 );

    computeBoundingBoxItem(bounding_box, begin, end);

    if( size > MAX_ORDER )
    {
        // Create an internal node at most MAX_ORDER nonempty slots.
        // slot #s will have the index of the root of a subtree,
        // which is contained in node_boxes[s]

        node->setInternal(true);

        // Partition in a way that is balanced but that aims
        // to keep the number of unused slots in leaves very small
        // Pick "m" to be the ideal number of items per subtree.
        ITEM_INDEX_REP m{ MAX_ORDER };
        while( m * MAX_ORDER < size )
        {
            m *= MAX_ORDER;
        }

        UT_ASSERT_P( MAX_ORDER <= m );
        UT_ASSERT_P( m < size );

        // Create at most MAX_ORDER subtrees, each of which has exactly m elements
        const int num_subtrees_size_m( size / m );

        UT_ASSERT_P( num_subtrees_size_m <= MAX_ORDER );

        // 
        {
            // TODO: perhaps splitting along a single axis is not the best
            // if MAX_ORDER > 2
        
            const int largest_axis = bounding_box.getLargestAxis();

            const auto is_less_than = [largest_axis]( const BoxedItem& a, const BoxedItem& b )
            {
                return ( signAxisCenterComparison( largest_axis, a.myBox, b.myBox ) == 1 );
            };

            // Partition the elements for each subtree.
            PartitionForSubtrees< Box, ITEM_INDEX_REP >{}(
                begin, end,
                is_less_than,
                m, num_subtrees_size_m
            );
        }

        // offset relative to 'begin':
        // the at most 'm' elements for subtree #s start at begin + offset
        size_t offset(0);

        for( int s = 0; s < num_subtrees_size_m; ++s )
        {
            if( size - offset < m )
            {
                break;
            }

            const size_t next_offset( offset + m );

            node->assignSubtree(
                s,
                subtreeCreate(
                    node_boxes[s],
                    shared_boxes,
                    begin + offset, begin + next_offset,
                    shared_nodes,
                    shared_nodes_end
                ) - shared_nodes //FIXME: ugly pointer arithmetic
            );

            offset = next_offset;
        }

        // If needed, construct a subtree for any remaining elements (strictly less than m)
        const size_t num_remaining_items( size % m );
        if( num_remaining_items > 0 )
        {
            UT_ASSERT_P( num_subtrees_size_m < MAX_ORDER );
            UT_ASSERT_P( num_remaining_items == size - offset );

            const size_t next_offset( offset + num_remaining_items );

            node->assignSubtree(
                num_subtrees_size_m,
                subtreeCreate(
                    node_boxes[num_subtrees_size_m],
                    shared_boxes,
                    begin + offset, begin + next_offset,
                    shared_nodes,
                    shared_nodes_end
                ) - shared_nodes //FIXME: ugly pointer arithmetic
            );

            offset = next_offset;
        }

        UT_ASSERT_P( offset == size );

        UT_ASSERT_P( node->countNumItems() > 0 );
    }
    else
    {
        // Create a leaf with size nonempty slots.
        // Each slot has the index of a shared node box.
        node->setInternal(false);

        int s(0);
        for( const BoxedItem* i = begin; i != end; ++i )
        {
        node_boxes[s] = i->myBox;
            node->assignItem(s, i->myItem);
            ++s;
        }
    }

    return node;
}

template< typename ITEM_INDEX_REP, int MAX_ORDER, typename ITEM_BOX, typename FT >
inline void
subtreeAssignItemBoxArray(
    UT_BoxT< FT >& bounding_box,
    UT_BoxT< FT > shared_boxes[],
    const RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[],
    const RNodeT< ITEM_INDEX_REP, MAX_ORDER >*const node,
    ITEM_BOX&& item_box
)
{
    static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );
    
    using RNode = RNodeT< ITEM_INDEX_REP, MAX_ORDER >;
    using Box = UT_BoxT< FT >;

    UT_ASSERT_P( node != 0 );

    // s_box is the sub-array that contains the MAX_ORDER boxes
    // for the node that we're visiting
    Box*const s_box(
        shared_boxes +
        ((node - shared_nodes) * MAX_ORDER)
    );

    if( node->isInternal() )
    {
        for( int s = 0; s < MAX_ORDER; ++s )
        {
            if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
            {
                break;
            }

            subtreeAssignItemBoxArray(
                s_box[s],
                shared_boxes,
                shared_nodes,
                shared_nodes + node->getSubtree(s),
                item_box
            );
        }
    }
    else
    {
        int s = 0;
        for( ; s < MAX_ORDER; ++s )
        {
            if( ( node->mySlots[ s ] & RNode::SLOT_MASK_INDEX ) == RNode::SLOT_VALUE_EMPTY )
            {
                break;
            }
            
                s_box[s] = item_box[ node->getItemIndexRep( s ) ];
            }
        
        for( ; s < MAX_ORDER; ++s )
            {
                s_box[s] = UT_BoxT< FT >(); // Empty set
            }
    }

    computeBoundingBox(bounding_box, s_box, s_box + MAX_ORDER);
}

template< typename ITEM_INDEX, int MAX_ORDER >
struct SubtreeForEachIntersectingItem
{
    using ItemIndexRep = ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX >;

    template< typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
    constexpr void operator()( 
        ACCEPT_ITEM&& accept_item,
        const RNodeT< ItemIndexRep, MAX_ORDER > shared_nodes[],
        const UT_BoxT< FT > shared_boxes[],
        const RNodeT< ItemIndexRep, MAX_ORDER >*const node,
        const QUERY_SHAPE& query_shape
    ) const noexcept
    {
        static_assert( SYS_IsIntegral_v< ItemIndexRep > );

        using RNode = RNodeT< ItemIndexRep, MAX_ORDER >;
        using Box = UT_BoxT< FT >;
        
        UT_ASSERT( node != nullptr );

        // node_boxes is the sub-array that contains the MAX_ORDER boxes
        // for the node that we're visiting
        const Box*const node_boxes(
            shared_boxes +
            ((node - shared_nodes) * MAX_ORDER)
        );

        if( node->isInternal() )
        {
            for( int s = 0; s < MAX_ORDER; ++s )
            {
                if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
                {
                    break;
                }
                    
                if( intersects( query_shape, node_boxes[ s ] ) )
                {
                    SubtreeForEachIntersectingItem< ITEM_INDEX, MAX_ORDER >{}(
                        std::forward< ACCEPT_ITEM >( accept_item ),
                        shared_nodes, shared_boxes,
                        shared_nodes + node->getSubtree( s ),
                        query_shape
                    );
                }
            }
        }
        else
        {
            for( int s = 0; s < MAX_ORDER; ++s )
            {
                if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
                {
                    break;
                }
                
                if( intersects( query_shape, node_boxes[ s ] ) )
                {
                    accept_item( ITEM_INDEX{ node->getItemIndexRep( s ) } );
                }
            }
        }
    }
};

template< typename ITEM_INDEX_REP, int MAX_ORDER >
inline exint subtreeComputeMaxDepth(
    const RNodeT< ITEM_INDEX_REP, MAX_ORDER > shared_nodes[],
    const RNodeT< ITEM_INDEX_REP, MAX_ORDER >*const node
)
{
    static_assert( SYS_IsIntegral_v< ITEM_INDEX_REP > );

    using RNode = RNodeT< ITEM_INDEX_REP, MAX_ORDER >;
    
    UT_ASSERT_P( node != 0 );

    if( node->isInternal() )
    {
        int max_depth_children(0);

        for( int s = 0; s < MAX_ORDER; ++s )
        {
            if( (node->mySlots[s] & RNode::SLOT_MASK_INDEX) == RNode::SLOT_VALUE_EMPTY )
            {
                break;
            }
                
            max_depth_children = std::max(
                max_depth_children,
                UTsubtreeComputeMaxDepth(shared_nodes, shared_nodes + node->getSubtree(s))
            );
        }

        return 1 + max_depth_children;
    }
    else
    {
        return 0;
    }
}

}
// namespace UT

template< typename FT >
UT::RTreeConfigurationT< FT >::RTreeConfigurationT(
    const exint node_slot_box_size,
    UT_UniquePtr< UT_BoxT< FT >[] > node_slot_box
) :
    myNodeSlotBoxSize( node_slot_box_size ),
    myNodeSlotBox( std::move( node_slot_box ) )
{
}
    
template< typename FT >
UT::RTreeConfigurationT< FT >::RTreeConfigurationT( RTreeConfigurationT&& a ) :
    myNodeSlotBoxSize( a.myNodeSlotBoxSize ),
    myNodeSlotBox( std::move( a.myNodeSlotBox ) )
{
}

template< typename ITEM_INDEX, int MAX_ORDER >
template< typename FT >
UT::RTreeT< ITEM_INDEX, MAX_ORDER >::RTreeT(
    const UT_BoxT< FT > item_box[],
    const ItemIndex num_items
) :
    myNumNodes( 0 ),
    myNodes( nullptr ),
    myRoot( nullptr ),
    myNumItems( ItemIndexUnderlyingInteger< ITEM_INDEX >{}( num_items ) )
{
    using ItemIndexRep = ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX >;
    using Box = UT_BoxT< FT >;
    using BoxedItem = UT_BoxedItemT< Box, ItemIndexRep >;

    SYS_STATIC_ASSERT( MAX_ORDER >= 2 );
 

    UT_ASSERT( myNumItems >= 0 );
    UT_ASSERT( myNumItems < ( ItemIndexRep(1) << ( ( 8 * sizeof(ItemIndexRep) ) - 2 ) ) );

    auto boxed_items = UTmakeUnique< BoxedItem[] >( myNumItems );
    ItemIndexRep num_boxed_items = 0;
    for( ItemIndexRep i = 0; i < myNumItems; ++i )
    {
        const Box& box( item_box[ i ] );
        if( box.isEmpty() )
        {
            continue;
        }

        boxed_items[ num_boxed_items ] = BoxedItem( box, i );
        num_boxed_items++;
    }

    if( num_boxed_items <= 0 )
    {
        // Verify nonempty tree with invalid root
        UT_ASSERT( myNumNodes == 0 );
        UT_ASSERT( myNodes == nullptr );
        UT_ASSERT( myRoot == nullptr );
        
        return;
    }
    
    myNumNodes = subtreeDetermineNumNodes( MAX_ORDER, num_boxed_items );
    myNodes = std::make_unique< Node[] >( myNumNodes );

    // Create the R-tree nodes, based on boxed_items
    Box bounding_box_root; // empty
    auto shared_boxes = UTmakeUnique< Box[] >( MAX_ORDER * myNumNodes );
    
    Node* shared_nodes_end = myNodes.get();

    myRoot = subtreeCreate(
        bounding_box_root,
        shared_boxes.get(),
        boxed_items.get(), boxed_items.get() + num_boxed_items,
        myNodes.get(),
        shared_nodes_end
    );

    UT_ASSERT( shared_nodes_end - myNodes.get() == myNumNodes );
    
    // Verify nonempty tree with valid root
    UT_ASSERT( myNumNodes > 0 );
    UT_ASSERT( myNodes != nullptr );
    UT_ASSERT( ( myNodes.get() <= myRoot ) && ( myRoot < myNodes.get() + myNumNodes ) );

#if 0
    std::cout << "RTree stats: " << std::endl;
    std::cout << "Number of items: " << num_items << std::endl;
    std::cout << "Tree size (in node): " << myNumNodes << std::endl;
    std::cout << "MAX_ORDER (max children/items per node) = " << MAX_ORDER << std::endl;
    std::cout << "Number of items per node: " << fpreal64(num_items) / fpreal64(myNumNodes) << std::endl;
    std::cout << "Max tree depth: " << UTsubtreeComputeMaxDepth(myNodes, myRoot) << std::endl;
#endif // 0
}

template< typename ITEM_INDEX, int MAX_ORDER >
template< typename FT >
UT::RTreeT< ITEM_INDEX, MAX_ORDER >::RTreeT(
    const UT_Array< UT_BoxT< FT > >& item_box
) :
    // Delegate to constructor that takes built-in array with size
    RTreeT( item_box.array(), item_box.size() )
{
}

template< typename ITEM_INDEX, int MAX_ORDER >
UT::RTreeT< ITEM_INDEX, MAX_ORDER >::RTreeT( RTreeT&& a ) :
    myNumNodes( a.myNumNodes ),
    myNodes( std::move( a.myNodes ) ),
    myRoot( a.myRoot ),
    myNumItems( a.myNumItems )
{
    // Mark tree as invalid
    a.myNumItems = -1;
    a.myRoot = nullptr;
    a.myNumNodes = -1;
}

template< typename ITEM_INDEX, int MAX_ORDER >
UT::RTreeT< ITEM_INDEX, MAX_ORDER >::~RTreeT()
{
    // Mark tree as invalid
    myNumItems = -1;
    myRoot = nullptr;
    myNumNodes = -1;
}

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline UT::RTreeT< ITEM_INDEX, MAX_ORDER > UT::constructRTree( const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items )
{
    return RTreeT< ITEM_INDEX, MAX_ORDER >( item_box, num_items );
}

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline UT::RTreeT< ITEM_INDEX, MAX_ORDER > UT::constructRTree( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return constructRTree< ITEM_INDEX, MAX_ORDER >( item_box.array(), item_box.size() );
}

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline UT::RTreeConfigurationT< FT > UT::constructRTreeConfiguration( const UT::RTreeT< ITEM_INDEX, MAX_ORDER >& tree, const UT_BoxT< FT > item_box[], const ITEM_INDEX num_items )
{
    using Box = UT_BoxT< FT >;

    exint node_slot_box_size = -1;
    UT_UniquePtr< Box[] > node_slot_box;
    
    UT_ASSERT( tree.myNumNodes != -1 );
    UT_ASSERT( ItemIndexUnderlyingInteger< ITEM_INDEX >{}( num_items ) == tree.myNumItems );

    if( tree.myRoot == nullptr )
    {
        UT_ASSERT( tree.myNumNodes == 0 );
    
        node_slot_box_size = 0;
        node_slot_box.reset();
        
        return UT::RTreeConfigurationT< FT >(
            node_slot_box_size,
            std::move( node_slot_box )
        );
    }
    
    UT_ASSERT( tree.myNumNodes > 0 );
    
    node_slot_box_size = MAX_ORDER * tree.myNumNodes;
    node_slot_box = std::make_unique< Box[] >( node_slot_box_size );
    
    UT_ASSERT( node_slot_box != nullptr );
    
    Box bounding_box_root; // empty
    subtreeAssignItemBoxArray(
        bounding_box_root,
        node_slot_box.get(),
        tree.myNodes.get(),
        tree.myRoot,
        item_box
    );
    
    return UT::RTreeConfigurationT< FT >(
        node_slot_box_size,
        std::move( node_slot_box )
    );
}

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline UT::RTreeConfigurationT< FT > UT::constructRTreeConfiguration( const UT::RTreeT< ITEM_INDEX, MAX_ORDER >& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return constructRTreeConfiguration( tree, item_box.array(), ITEM_INDEX( item_box.size() ) );
}

template< typename FT >
inline exint UT::heapMemoryUsage( const UT::RTreeConfigurationT< FT >& configuration )
{
    using Box = UT_BoxT< FT >;

    return configuration.myNodeSlotBoxSize * sizeof(Box);
}

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline void UT::updateConfiguration(
    RTreeConfigurationT< FT >& configuration,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const UT_BoxT< FT > item_box[],
    const ITEM_INDEX num_items
)
{
    using Box = UT_BoxT< FT >;

    UT_ASSERT( tree.myNumNodes != -1 );
    UT_ASSERT( num_items == tree.myNumItems );

    if( tree.myRoot == nullptr )
    {
        UT_ASSERT( tree.myNumNodes == 0 );
        UT_ASSERT( configuration.myNodeSlotBoxSize == 0 );
        UT_ASSERT( configuration.myNodeSlotBox == nullptr );

        return;
    }
    
    UT_ASSERT( tree.myNumNodes > 0 );
    UT_ASSERT( configuration.myNodeSlotBoxSize = MAX_ORDER * tree.myNumNodes );
    UT_ASSERT( configuration.myNodeSlotBox != nullptr );
    
    Box bounding_box_root; // empty
    subtreeAssignItemBoxArray(
            bounding_box_root,
            configuration.myNodeSlotBox.get(),
            tree.myNodes.get(),
            tree.myRoot,
            item_box
    );
}

template< typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline void UT::updateConfiguration(
    RTreeConfigurationT< FT >& configuration,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const UT_Array< UT_BoxT< FT > >& item_box
)
{
    updateConfiguration( configuration, tree, item_box.data(), ITEM_INDEX( item_box.size() ) );
}

template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline void UT::getIntersecting(
    UT_Array< ITEM_INDEX >& results,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const RTreeConfigurationT< FT >& configuration,
    const QUERY_SHAPE& query_shape
)
{
    results.clear();
        
    UT::forEachIntersecting(
        [ &results ]( const ITEM_INDEX i ) { results.append( i ); },
        tree, configuration,
        query_shape
    );
}

/// For each item i for which item_box[i] intersects query_box,
/// call accept_item( i ).
/// There must exist a free-standing 'intersects' function that takes a 
/// QUERY_SHAPE and a UT_BoxT< FT >.
template< typename ITEM_INDEX, int MAX_ORDER, typename FT, typename QUERY_SHAPE, typename ACCEPT_ITEM >
inline void UT::forEachIntersecting(
    ACCEPT_ITEM&& accept_item,
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const RTreeConfigurationT< FT >& configuration,
    const QUERY_SHAPE& query_shape
)
{
    UT_ASSERT( tree.myNumNodes != -1 );

    UT_ASSERT( configuration.myNodeSlotBoxSize == MAX_ORDER * tree.myNumNodes );

    if( tree.myRoot == nullptr )
    {
        return;
    }
    
    SubtreeForEachIntersectingItem< ITEM_INDEX, MAX_ORDER >{}(
        std::forward< ACCEPT_ITEM >( accept_item ),
        tree.myNodes.get(),
        configuration.myNodeSlotBox.get(),
        tree.myRoot, query_shape
    );
}

template< typename ITEM_INDEX, int MAX_ORDER >
inline exint UT::heapMemoryUsage( const UT::RTreeT< ITEM_INDEX, MAX_ORDER >& tree )
{
    using ItemIndexRep = ItemIndex_UnderlyingIntegerType_t< ITEM_INDEX >;
    using RNode = RNodeT< ItemIndexRep, MAX_ORDER >;

    return tree.myNumNodes * sizeof(RNode);
}

template< typename QUERY_SHAPE, typename ITEM_INDEX, int MAX_ORDER, typename FT >
inline ITEM_INDEX* UT::getIntersectingRaw(
    const RTreeT< ITEM_INDEX, MAX_ORDER >& tree,
    const RTreeConfigurationT< FT >& configuration,
    const QUERY_SHAPE& query_box, 
    ITEM_INDEX*const items_begin
)
{
    ITEM_INDEX* it = items_begin;

    UT::forEachIntersecting(
        [ &it ]( const ITEM_INDEX i ) { *it++ = i; },
        tree, configuration,
        query_box
    );

    return it;
}

template< typename FT >
inline UT_RTree16Int UTconstructRTree16Int( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTree< UT_RTree16Int::ItemIndex, UT_RTree16Int::max_order, FT >( item_box );
}

template< typename FT >
inline UT_RTree2Int UTconstructRTree2Int( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTree< UT_RTree2Int::ItemIndex, UT_RTree2Int::max_order, FT >( item_box );
}

template< typename FT >
inline UT_RTreeInt UTconstructRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTreeInt::ItemIndex num_items )
{
    return UT::constructRTree< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( item_box, num_items );
}

template< typename FT >
inline UT_RTreeInt UTconstructRTreeInt( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTree< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( item_box );
}

template< typename FT >
inline UT_RTree UTconstructRTree( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
{
    return UT::constructRTree< UT_RTree::ItemIndex, UT_RTree::max_order, FT >( item_box, num_items );
}

template< typename FT >
inline UT_RTree UTconstructRTree( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTree< UT_RTree::ItemIndex, UT_RTree::max_order, FT >( item_box );
}

template< typename FT >
inline UT_RTree2IntConfigurationT< FT > UTconstructRTree2IntConfiguration( const UT_RTree2Int& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTreeConfiguration< UT_RTree2Int::ItemIndex, UT_RTree2Int::max_order, FT >( tree, item_box );
}

template< typename FT >
inline UT_RTree16IntConfigurationT< FT > UTconstructRTree16IntConfiguration( const UT_RTree16Int& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTreeConfiguration< UT_RTree16Int::ItemIndex, UT_RTree16Int::max_order, FT >( tree, item_box );
}

template< typename FT >
inline UT_RTreeIntConfigurationT< FT > UTconstructRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTreeConfiguration< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( tree, item_box );
}

template< typename FT >
inline UT_RTreeIntConfigurationT< FT > UTconstructRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
{
    return UT::constructRTreeConfiguration< UT_RTreeInt::ItemIndex, UT_RTreeInt::max_order, FT >( tree, item_box, num_items );
}

template< typename FT >
inline UT_RTreeConfigurationT< FT > UTconstructRTreeConfiguration( const UT_RTree& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UT::constructRTreeConfiguration< UT_RTree::ItemIndex, UT_RTree::max_order, FT >( tree, item_box );
}

template< typename FT >
inline auto UTmakeUniqueRTree2Int( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UTmakeUnique< const UT_RTree2Int >( UTconstructRTree2Int( item_box ) );
}

template< typename FT >
inline auto UTmakeUniqueRTree16Int( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UTmakeUnique< const UT_RTree16Int >( UTconstructRTree16Int( item_box ) );
}

template< typename FT >
inline auto UTmakeUniqueRTreeInt( const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UTmakeUnique< const UT_RTreeInt >( UTconstructRTreeInt( item_box ) );
}

template< typename FT >
inline auto UTmakeUniqueRTreeInt( const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
{
    return UTmakeUnique< const UT_RTreeInt >( UTconstructRTreeInt( item_box, num_items ) );
}

template< typename FT >
inline auto UTmakeUniqueRTree2IntConfiguration( const UT_RTree2Int& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTree2IntConfiguration( tree, item_box ) );
}

template< typename FT >
inline auto UTmakeUniqueRTree16IntConfiguration( const UT_RTree16Int& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTree16IntConfiguration( tree, item_box ) );
}

template< typename FT >
inline auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_Array< UT_BoxT< FT > >& item_box )
{
    return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTreeIntConfiguration( tree, item_box ) );
}

template< typename FT >
auto UTmakeUniqueRTreeIntConfiguration( const UT_RTreeInt& tree, const UT_BoxT< FT > item_box[], const UT_RTree::ItemIndex num_items )
{
    return UTmakeUnique< const UT::RTreeConfigurationT< FT > >( UTconstructRTreeIntConfiguration( tree, item_box, num_items ) );
}

#endif // __UT_RTREEIMPL_H_INCLUDED__