redblack.h

Go to the documentation of this file.

/*
 * $Id: redblack.h 18227 2014-11-14 19:00:04Z predoehl $
 */

#ifndef REDBLACK_H_PREDOEHL_12_DEC_2011_VISION
#define REDBLACK_H_PREDOEHL_12_DEC_2011_VISION 1

#include <l/l_sys_lib.h>
#include <l/l_sys_io.h>
#include <l/l_debug.h>
#include <l_cpp/l_util.h>

#ifdef DEBUGGING
#include <sstream>
#include <map> /* oh the irony */
#endif

#include <qd_cpp/diprique.h>

#include <iosfwd>                       /* std::ostream                  */
#include <algorithm>                    /* std::sort and several others  */
#include <numeric>                      /* std::accumulate               */
#include <limits>                       /* std::numeric_limits           */
#include <new>
#include <iterator>

#define REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY 1

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
/* Implement location list in a std::vector. */
#include <vector>
#else
/* Implement location list in a std::map. */
#include <map>
#endif

namespace kjb
{
namespace qd
{


template < typename SATELLITE_TYPE >
class Redblack_subtree_sum
:   public DijkstraPriorityQueue< SATELLITE_TYPE >
{
public:
    typedef SATELLITE_TYPE                                              Sat_tp;
    typedef typename DijkstraPriorityQueue< SATELLITE_TYPE >::Key_tp    Key_tp;
    typedef typename DijkstraPriorityQueue< SATELLITE_TYPE >::Loc_tp    Loc_tp;

private:
    enum
    {
        VERBOSE = 0,            
        TREE_THRESH = 7,        
        BLACKHEIGHT_BAD = -1,   
        LOCATOR_BASE = 987000   
    };

#ifdef DEBUGGING
    typedef std::map< Loc_tp, char > LocCensus_tp;
#endif

    struct Node
    {
        Key_tp  key,        
                sum;        
        Sat_tp  sat;        
        Loc_tp  locator;    
        Node    *left,      
                *right,     
                *parent;    
        bool    is_black;   

        Node()
        {}

        Node(
            const Key_tp& kk,
            const Sat_tp& ss,
            bool bk,
            Node* ll,
            Node* rr,
            Loc_tp loc
        )
        :   key( kk ),
            sum( kk ),
            sat( ss ),
            locator( loc ),
            left( ll ),
            right( rr ),
            parent( 00 ),
            is_black( bk )
        {}

        bool is_red() const
        {
            return ! is_black;
        }

        bool operator<( const Node& other ) const
        {
            return key < other.key;
        }

        void update_sum()
        {
            KJB(ASSERT( left && right ));
            sum = key + left -> sum + right -> sum;
        }

        void you_are_my_child( Node* child, Node* Node::* branch )
        {
            KJB(ASSERT( child ));
            this ->* branch = child;
            child -> parent = this;
        }

        void link_left_child( Node* child )
        {
            you_are_my_child( child, & Node::left );
        }

        void link_right_child( Node* child )
        {
            you_are_my_child( child, & Node::right );
        }
    };

    struct AddKey
    {
        Key_tp operator()( const Key_tp& a, const Node& n ) { return a+n.key; }
    };


    Node m_nil;

    Node *root;

    unsigned m_size;

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
    std::vector< Node* > location_list;
#else
    typedef std::map< Loc_tp, Node* > LocationList;
    typedef typename LocationList::const_iterator LLCI;

    LocationList location_list;
#endif

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
    std::vector< Loc_tp > free_locator_list;
#endif

#ifdef DEBUGGING
    void chatter( const char* s ) const
    {
        if ( VERBOSE ) KJB(TEST_PSE(( "CHATTER: %s\n", s )));
    }

    void enter( const char* s ) const
    {
        if ( VERBOSE ) KJB(TEST_PSE(( "CHATTER: Entering %s\n", s )));
    }

    bool fail( const char *s ) const
    {
        chatter( s );
        return false;
    }

    bool fail( int nnn ) const
    {
        KJB(TEST_PSE(( "FAIL: line %d\n", nnn )));
        return false;
    }

#else
    void chatter( const char* ) const {}

    void enter( const char* ) const {}

    bool fail( const char* ) const { return false; }

    bool fail( int ) const { return false; }
#endif



    Loc_tp obtain_avail_locator()
    {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        Loc_tp nuloc = location_list.size();

        if ( free_locator_list.size() )
        {
            // we can recycle an old one!  good!
            nuloc = free_locator_list.back();
            free_locator_list.pop_back();
        }
        else
        {
            location_list.push_back( 00 );
        }

        return nuloc;
#else
        if (location_list.empty()) return 0;

        LLCI i = location_list.end();
        --i;
        return 1 + i -> first;
#endif
    }


#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY

    void opportunistic_cleanup_of_idle_locators()
    {
        while (  location_list.size()
              && 00 == location_list.back()
              && free_locator_list.size()
              && 1 + free_locator_list.back() == location_list.size()
              )
        {
            location_list.pop_back();
            free_locator_list.pop_back();
        }
    }
#endif

    void release_locator( Loc_tp loc )
    {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(ASSERT( loc < location_list.size() ));

        // also could test whether loc is in free list (shouldn't be)
        free_locator_list.push_back( loc );
        location_list[ loc ] = 00;

        // if location_list has A LOT of null entries, try to collapse them.
        if (    free_locator_list.size() & ~0xFFF     // more than 4095 nulls,
            &&  size() < free_locator_list.size()>>3  // more than 87% nulls,
            &&  00 == location_list.back()            // last entry is null.
           )
        {
            std::sort(free_locator_list.begin(), free_locator_list.end());
            opportunistic_cleanup_of_idle_locators();

            /*
             * To encourage the use of low-value locators, put them toward the
             * end of the free_locator_list, because we draw off the back.
             */
            std::reverse(free_locator_list.begin(), free_locator_list.end());
        }
#else
#ifdef DEBUGGING
        const size_t count =
#endif
            location_list.erase(loc);
        KJB(ASSERT(1 == count));
#endif
    }


    Node* new_node( const Key_tp& key, const Sat_tp& sat, bool black )
    {
        const Loc_tp nuloc = obtain_avail_locator();
        Node* nn = new Node( key, sat, black, & m_nil, & m_nil, nuloc );
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(ASSERT( nuloc < location_list.size() ));
        KJB(ASSERT( 00 == location_list.at( nuloc ) ));
#endif
        KJB(ASSERT( nuloc == nn -> locator ));
        location_list[ nuloc ] = nn;
        return nn;
    }


    Node* new_node( const Node& old_node )
    {
        return new_node( old_node.key, old_node.sat, old_node.is_black );
    }


    bool loc_list_good_here( const Node* ppp ) const
    {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        return ppp && location_list.at( ppp -> locator ) == ppp;
#else
        if (00 == ppp) return false;
        LLCI i = location_list.find( ppp -> locator );
        return i != location_list.end() && i -> second == ppp;
#endif
    }


    void dispose( Node* ppp )
    {
        KJB(ASSERT( ppp ));
        KJB(ASSERT( loc_list_good_here( ppp ) ));
        const Loc_tp ploc = ppp -> locator;
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(ASSERT( location_list.at( ploc ) == ppp ));
#else
        KJB(ASSERT( location_list[ ploc ] == ppp ));
#endif
        release_locator( ploc );
        delete ppp;
    }


    bool is_nil( const Node* ppp ) const
    {
        return ppp == & m_nil;
    }


    bool is_not_nil( const Node* ppp ) const
    {
        return ppp != & m_nil;
    }


    bool are_both_children_nil( const Node* ppp ) const
    {
        return      ppp
                &&  is_not_nil( ppp )
                &&  is_nil( ppp -> left )
                &&  is_nil( ppp -> right );
    }


    int blackheight_in_linear_time( const Node* ppp ) const
    {
        KJB(ASSERT( ppp ));
        if ( is_nil( ppp ) )
        {
            return 1;   // because nil is black
        }

        int bh = blackheight_in_linear_time( ppp -> left );

        if  (       bh != BLACKHEIGHT_BAD
                &&  bh == blackheight_in_linear_time( ppp -> right )
            )
        {
            return bh + ( ppp -> is_black ? 1 : 0 );
        }

        return BLACKHEIGHT_BAD;
    }


    void recursive_destroy( Node* ppp )
    {
        if ( ppp && is_not_nil( ppp ) )
        {
            recursive_destroy( ppp -> left );
            recursive_destroy( ppp -> right );
            dispose( ppp );
        }
    }


    void make_it_a_real_tree_now()
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        std::sort( root, root + TREE_THRESH );
        Node sorty[ TREE_THRESH ];
        std::copy( root, root + TREE_THRESH, sorty );
        delete[] root;

        // build tree (unfortunately, this inserts fresh, unwanted locators)
        KJB(ASSERT( 7 == TREE_THRESH ));
        root =                              new_node( sorty[ 3 ] );
        root -> link_left_child(            new_node( sorty[ 1 ] ) );
        root -> link_right_child(           new_node( sorty[ 5 ] ) );
        root -> left -> link_left_child(    new_node( sorty[ 0 ] ) );
        root -> left -> link_right_child(   new_node( sorty[ 2 ] ) );
        root -> right -> link_left_child(   new_node( sorty[ 4 ] ) );
        root -> right -> link_right_child(  new_node( sorty[ 6 ] ) );
        root -> parent = m_nil.parent = 00;

        // unfortunately that little tree is now full of unwanted locators
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        release_locator( root                   -> locator );
        release_locator( root -> left           -> locator );
        release_locator( root -> right          -> locator );
        release_locator( root -> left -> left   -> locator );
        release_locator( root -> left -> right  -> locator );
        release_locator( root -> right -> left  -> locator );
        release_locator( root -> right -> right -> locator );
#else
        location_list.clear();
#endif

        // fix the location_list
        location_list[ sorty[ 3 ].locator ] = root;
        location_list[ sorty[ 1 ].locator ] = root -> left;
        location_list[ sorty[ 5 ].locator ] = root -> right;
        location_list[ sorty[ 0 ].locator ] = root -> left -> left;
        location_list[ sorty[ 2 ].locator ] = root -> left -> right;
        location_list[ sorty[ 4 ].locator ] = root -> right -> left;
        location_list[ sorty[ 6 ].locator ] = root -> right -> right;

        // fix the tree's embedded locator indices
        root                    -> locator = sorty[ 3 ].locator;
        root -> left            -> locator = sorty[ 1 ].locator;
        root -> right           -> locator = sorty[ 5 ].locator;
        root -> left -> left    -> locator = sorty[ 0 ].locator;
        root -> left -> right   -> locator = sorty[ 2 ].locator;
        root -> right -> left   -> locator = sorty[ 4 ].locator;
        root -> right -> right  -> locator = sorty[ 6 ].locator;

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        // discard idle locators (loops just TREE_THRESH times)
        opportunistic_cleanup_of_idle_locators();
#endif

        // update the sums
        KJB(ASSERT( 7 == TREE_THRESH ));
        root -> left -> update_sum();
        root -> right -> update_sum();
        root -> update_sum();
    }




    int insert_parent( Node** toparent, bool pn_left, Node* n00b )
    {
        KJB(ASSERT( n00b && toparent && *toparent ));
        Node* parent = *toparent;

        Node* Node::* branch = pn_left ? & Node::left : & Node::right;
        if ( is_nil( parent ->* branch ) )
        {
            KJB(ASSERT( n00b -> is_red() ));
            parent -> you_are_my_child( n00b, branch );
            parent -> sum += n00b -> sum;
            return 1; // red child at depth 2 in subtree rooted at gramp
        }
        else
        {
#ifdef DEBUGGING
            int rc = insert_gp( toparent, pn_left, n00b );
            /*
             * If rc is zero, that is fine:  it means no-red-red is satisfied.
             * If rc is 2 or 4, we can handle it:  it means no-red-red might
             * be unsatisfied, but
             */
            KJB(ASSERT( 0 == rc || 2 == rc || 4 == rc ));
            KJB(ASSERT( rc != 2 || ( parent ->* branch ) -> is_red() ));
            KJB(ASSERT( rc != 4 || parent -> is_red() ));

            /*
             * Shift that return value downwards, because it describes the tree
             * status for a deeper context, but we want to return the tree
             * status for the current context.
             */
            return rc >> 1;
#else
            return insert_gp( toparent, pn_left, n00b ) >> 1;
#endif
        }
    }


    int insert_gp( Node** togramp, bool gp_left, Node* n00b )
    {
        KJB(ASSERT( n00b && togramp && *togramp ));

        Node    *gramp = *togramp,
                **toparent = gp_left ? & gramp -> left : & gramp -> right;

        gramp -> sum += n00b -> sum;

        KJB(ASSERT( toparent ));
        Node *parent = *toparent;

        KJB(ASSERT( parent ));
        bool pn_left = *n00b < *parent;

        /*
         * The semantics of the value in rc and of the value returned by this
         * function are the same.  This is important, pay attention!
         *
         * rc tells us about a red node that might be the child of a red node,
         * i.e., a potential violation of the @ref redblacki2.
         * The possible values are in the set {0, 1, 2}.
         *
         * If 0==rc, then the invariant is satisfied in this subtree.
         * If 1==rc, then new node n00b is red; must check *parent.
         * If 2==rc, then *parent is newly painted red; must check *gramp.
         *
         * In like wise, the value 4 would indicate *gramp is newly painted
         * red (see below).  Thus the value in rc and the return value below
         * have consistent semantics.
         */
        int rc = insert_parent( toparent, pn_left, n00b );
        KJB(ASSERT( 0 == rc || 1 == rc || 2 == rc ));

        /*
         * The return value below is in the set {0, 2, 4}.
         * Values 0 and 2 have the same semantics as 'rc' above.
         * Value 4 means *gramp is newly painted red and the caller must
         * check its parent.
         */
        return rb_balance( togramp, gp_left, pn_left, rc );
    }


    Node* Node::* opposite_direction( Node* Node::* some_direction ) const
    {
        return some_direction == & Node::left ? & Node::right : & Node::left;
    }


    void unzigzag( Node* gramp, Node* Node::* p_branch )
    {
        Node* Node::* u_branch = opposite_direction( p_branch );//towards uncle

        KJB(ASSERT( gramp ));
        KJB(ASSERT( is_not_nil( gramp ->* p_branch ) ));
        KJB(ASSERT( is_not_nil( gramp ->* p_branch ->* u_branch ) ));

        Node    *oldparent = gramp ->* p_branch,
                *oldchild = oldparent ->* u_branch,
                *med_tree = oldchild ->* p_branch; // could be nil

        gramp -> you_are_my_child( oldchild, p_branch );
        oldchild -> you_are_my_child( oldparent, p_branch );

        oldparent ->* u_branch = med_tree;
        if ( is_not_nil( med_tree ) )
        {
            med_tree -> parent = oldparent;
        }

        /*
         * Now "oldparent" is the child of "oldchild" -- it's freaky friday.
         */
        oldparent -> update_sum();
        oldchild -> update_sum();
    }


    void rotate( Node** togramp, Node* Node::* p_branch )
    {
        KJB(ASSERT( togramp && *togramp ));

        Node* Node::* u_branch = opposite_direction( p_branch ); // to uncle
        Node* oldgramp = *togramp;

        KJB(ASSERT( is_not_nil( oldgramp ) ));
        KJB(ASSERT( is_not_nil( oldgramp ->* p_branch ) ));

        Node    *oldparent = oldgramp ->* p_branch,
                *medmed_tree = oldparent ->* u_branch;

        KJB(ASSERT( oldparent -> parent == oldgramp ));

        // rotate the descendant relationships
        *togramp = oldparent;

        // update the ancestor relationships
        oldparent -> parent = oldgramp -> parent;
        oldparent -> you_are_my_child( oldgramp, u_branch );

        oldgramp ->* p_branch = medmed_tree;
        if ( is_not_nil( medmed_tree ) )
        {
            medmed_tree -> parent = oldgramp;
        }

        /*
         * Now "oldparent" and "oldgramp" have swapped parent-child statuses.
         * Also they have to swap colors.
         * The former sibling of "oldparent" is still the child of "oldgramp"
         * and so it is now become a grandchild of "oldparent."  IF ANY.
         */
        std::swap( oldgramp -> is_black, oldparent -> is_black );

        oldgramp -> update_sum();
        oldparent -> update_sum();
    }


    int rb_balance( Node** togramp, bool gp_left, bool pn_left, int red_child )
    {
        /*
         * On input, red_child is...
         * 3 if n00b is newly red and that fact must be handled.
         * 2 if parent is newly red and that fact must be handled.
         * 1 if gramp is newly red and that fact must be handled.
         * 0 if no one's redness must be handled.
         */
        if ( red_child != 1 )
        {
            return red_child;
        }

        KJB(ASSERT( togramp && *togramp ));

        Node* Node::* gp_branch = gp_left ? & Node::left : & Node::right;

        Node    *gramp = *togramp,
                *parent = gramp ->* gp_branch,
                *uncle = gramp ->* opposite_direction( gp_branch );

        KJB(ASSERT( parent ));
        if ( parent -> is_black )
        {
            return 0;   // if parent is black then a red child is not a problem
        }
        KJB(ASSERT( gramp -> is_black )); //parent and gramp cannot both be red

        if ( uncle -> is_black ) // also, uncle could be "nil" (black).
        {
            // unzigzag, if necessary
            if ( gp_left != pn_left )
            {
                unzigzag( gramp, gp_branch );
            }
            // rotate like alexander the great
            rotate( togramp, gp_branch );
            KJB(ASSERT( 00 == m_nil.parent ));
            return 0;
        }

        KJB(ASSERT( is_not_nil( uncle ) ));
        uncle -> is_black = parent -> is_black = true;
        gramp -> is_black = false;
        return 1 << 2;  // now gramp is a red child 2 levels higher
    }


#ifdef DEBUGGING
    void dbp_indent( int depth, std::ostream& os ) const
    {
        static const char* INDENT = "\t";
        for ( int iii = 0; iii < depth; ++iii )
        {
            os << INDENT;
        }
    }


    void db_print_child(
        const Node* ppp,
        int depth,
        Node* Node::* branchpp,
        const char* branchss,
        std::ostream& os
    )   const
    {
        dbp_indent( depth, os );
        os << branchss << " subtree:";
        if ( is_nil( ppp ->* branchpp ) )
        {
            os << " NIL\n";
        }
        else
        {
            if ( ppp != root && ( ppp ->* branchpp ) -> parent != ppp )
            {
                os << " BROKEN!!!! ";
            }
            os << '\n';
            recursive_db_print( ppp ->* branchpp, 1 + depth, os );
        }
    }


    void recursive_db_print(
        const Node* ppp,
        int depth,
        std::ostream& os
    ) const
    {
        if ( is_nil( ppp ) )
        {
            return;
        }

        dbp_indent( depth, os );
        os << "key=" << ppp -> key << ", sum=" << ppp -> sum
            << ", color=" << ( ppp -> is_black ? "BLACK" : "red" )
            << ", sat=" << ppp -> sat
            << ", loc=" << ppp -> locator;

        if ( ! dictionary_is_small_linear_array() )
        {
            os << ", blackheight=" << blackheight_in_linear_time( ppp );
        }
        else if ( ! are_both_children_nil( ppp ) )
        {
            os << ", WARNING: children are not nil";
        }

        if ( are_both_children_nil( ppp ) )
        {
            os << '\n';
            return;
        }
        os << ", left=" << ppp -> left << ", right=" << ppp -> right << '\n';

        db_print_child( ppp, depth, & Node::left, "Left", os );
        db_print_child( ppp, depth, & Node::right, "Right", os );
    }
#endif


    bool red_node_has_red_child_in_linear_time( const Node* ppp ) const
    {
        KJB(ASSERT( ppp ));
        if ( is_nil( ppp ) || are_both_children_nil( ppp ) )
        {
            return false;
        }
        if ( ppp -> is_red() && ppp -> left -> is_red() )
        {
            return true;
        }
        if ( ppp -> is_red() && ppp -> right -> is_red() )
        {
            return true;
        }
        return      red_node_has_red_child_in_linear_time( ppp -> left )
                ||  red_node_has_red_child_in_linear_time( ppp -> right );
    }


    bool sums_are_correct_in_linear_time( const Node* ppp ) const
    {
        KJB(ASSERT( ppp ));
        if ( is_nil( ppp ) ) return true;
        Key_tp sts = ppp -> key;
        if ( is_not_nil( ppp -> left ) ) sts += ppp -> left -> sum;
        if ( is_not_nil( ppp -> right ) ) sts += ppp -> right -> sum;
#ifdef DEBUGGING
        if ( sts != ppp -> sum )
        {
            chatter( "internal sums are incorrect" );
        }
#endif
        return      sts == ppp -> sum
                &&  sums_are_correct_in_linear_time( ppp -> left )
                &&  sums_are_correct_in_linear_time( ppp -> right );
    }


    bool sums_are_close_enough_in_linear_time( const Node* ppp ) const
    {
        const Key_tp SMALL = 1e-3;
        KJB(ASSERT( ppp ));
        if ( is_nil( ppp ) )
            return true;

        Key_tp sts = ppp -> key;
        if ( is_not_nil( ppp -> left ) ) sts += ppp -> left -> sum;
        if ( is_not_nil( ppp -> right ) ) sts += ppp -> right -> sum;

        Key_tp rrr = fabs( sts - ppp -> sum )/(fabs( sts )+fabs( ppp -> sum ));

#ifdef DEBUGGING
        if ( !( sts == ppp -> sum || rrr < SMALL ) )
        {
            chatter( "internal sums are inadequately accurate" );
            std::ostringstream ess;
            ess << "rrr=" <<rrr <<" which exceeds SMALL=" << SMALL << '\n';
            chatter( ess.str().c_str() );
            return fail( __LINE__ );
        }
#endif

        return      ( sts == ppp -> sum || rrr < SMALL )
                &&  sums_are_close_enough_in_linear_time( ppp -> left )
                &&  sums_are_close_enough_in_linear_time( ppp -> right );
    }


    bool linear_search(
        const Key_tp& qkey,
        Sat_tp* sat_out,
        Loc_tp* loc_out,
        size_t* ix
    )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        for ( size_t iii = 0; iii < m_size; ++iii )
        {
            if ( root[ iii ].key == qkey )
            {
                if ( sat_out ) *sat_out = root[ iii ].sat;
                if ( loc_out ) *loc_out = root[ iii ].locator;
                if ( ix ) *ix = iii;
                KJB(ASSERT( loc_list_good_here( root + iii ) ));
                return true;
            }
        }
        return false;
    }


    Node* tree_search(
        const Key_tp& qkey,
        Sat_tp* sat_out,
        Node* ppp,
        Loc_tp* loc_out
    )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( ppp ));
        if ( is_nil( ppp ) )
        {
            return 00;
        }
        if ( qkey == ppp -> key )
        {
            if ( sat_out ) *sat_out = ppp -> sat;
            if ( loc_out ) *loc_out = ppp -> locator;
            return ppp;
        }
        Node* Node::* branch= qkey < ppp -> key ? & Node::left : & Node::right;
        return tree_search( qkey, sat_out, ppp ->* branch, loc_out );
    }


    Node* recursive_condense( Node* tree, Node* dest )
    {
        KJB(ASSERT( tree && dest ));
        if ( is_nil( tree ) )
        {
            return dest;
        }

        // first, recurse on left subtree
        Node* d2 = recursive_condense( tree -> left, dest );
        // second, store the current node
        *d2++ = *tree;
        // third and last, recurse on right subtree
        Node* d3 = recursive_condense( tree -> right, d2 );
        return d3;
    }



    // trivial functor to extract locator field from Node object
    struct GetLocator { Loc_tp operator()(const Node& n) {return n.locator;} };


    /*
     * This is a functor to alter a node into a black, parentless leaf (i.e.,
     * ready to be stored in a small linear array).  Also, this rebuilds the
     * locator - pointer links.  We assume the location list holds nulls.
     * Only the key and sat fields are left undisturbed.
     */
    class Leafify
    {
        Redblack_subtree_sum< SATELLITE_TYPE >* const tree;

    public:
        Leafify(Redblack_subtree_sum< SATELLITE_TYPE >* t) : tree(t) {}

        void operator()(Node& node) const
        {
            node.left = node.right = & tree -> m_nil; // children now nil
            node.parent = 00;                         // parent now null
            node.is_black = true;                     // blacken
            node.sum = node.key;                      // sum is key

            // update locator
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            KJB(ASSERT(node.locator < tree -> location_list.size()));
            KJB(ASSERT( 00 == tree -> location_list[ node.locator ] ));
#endif
            tree -> location_list[ node.locator ] = &node;
        }
    };


#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
    /*
     * There is a linear array in root -- small, most likely, but we do not
     * care about the size.  The locators recorded in the array are correct,
     * but we assume the back-end bookkeeping is spoiled, i.e., location_list
     * and free_locator_list are assumed to be hopelessly wrong, and not worth
     * consulting.  This rebuilds them.
     *
     * An earlier software revision tried to repair them, but because of the
     * opportunistic cleanup that was added, their state became too hard to
     * predict, and I decided it's safer just to trash them and start over.
     */
    void rebuild_locator_list_for_linear_array()
    {
        // First, get a sorted list of live locators.
        std::vector< Loc_tp > locs( size() );
        std::transform(root, root+size(), locs.begin(), GetLocator());
        std::sort(locs.begin(), locs.end());

        // Locators in 'locs' must be pairwise-distinct.
        KJB(ASSERT(std::adjacent_find(locs.begin(),locs.end()) == locs.end()));

        // Rebuild list of pointers, one for each possible locator.
        // Unfortunately, this could be a huge number even for small size().
        // We are currently ignoring that fact.  If necessary, we could cope
        // with sparsity in location_list by using a std::map to get from
        // locator to pointer.
        const size_t llsz = 1 + locs.back();
        location_list.assign(llsz, 00);

        // Create list of free locators -- it's just set subtraction:
        // the set {0 to max live locator value} minus locs.
        // Store it into free_locator_list (replacing previous contents).
        std::vector< Loc_tp > panloc(llsz);
        for (size_t i = 0; i < llsz; ++i)
        {
            panloc[i] = i;
        }
        free_locator_list.resize(location_list.size() - locs.size());
#ifdef DEBUGGING
        typename std::vector< Loc_tp >::iterator z =
#endif
            std::set_difference(panloc.begin(), panloc.end(),
                            locs.begin(), locs.end(),
                            free_locator_list.begin());
        KJB(ASSERT(free_locator_list.end() == z));
        // Put small free locators at the beginning so they'll be used sooner.
        std::reverse(free_locator_list.begin(), free_locator_list.end());
    }
#endif



    void condense_into_linear_array()
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( size() ));

        /*
         * Copy tree entries into linear array.  Dispose of tree.
         * (Unfortunately, the second step also disposes of the locators.)
         */
        Node *la = new Node[ size() ];
#ifdef DEBUGGING
        const Node *full =
#endif
            recursive_condense( root, la );
        KJB(ASSERT( full - la == int( size() ) ));
        recursive_destroy( root );
        root = la;

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        // The previous locators were unfairly disposed of, so restore them.
        rebuild_locator_list_for_linear_array();
#else
        KJB(ASSERT(location_list.empty()));
#endif

        // Finally, fix up the node fields in the array, and re-link locators.
        std::for_each(root, root + size(), Leafify(this));
    }


    Node** to_parent_link( Node* ppp )
    {
        if ( ppp == root )
        {
            return & root;
        }

        KJB(ASSERT( ppp && is_not_nil( ppp ) ));

        Node* parent = ppp -> parent;
        KJB(ASSERT( parent && is_not_nil( parent ) ));
        KJB(ASSERT( parent -> right == ppp || parent -> left == ppp ));

        return parent -> left == ppp ? & parent -> left : & parent -> right;
    }


    Node* Node::* parent_branch_to_me( Node* ppp ) const
    {
        KJB(ASSERT( ppp && ppp != root /* && is_not_nil( ppp ) */ ));
        KJB(ASSERT( ppp -> parent ));
        KJB(ASSERT(     ppp -> parent -> right == ppp
                    ||  ppp -> parent -> left == ppp  ));
        return ppp -> parent -> right == ppp ? & Node::right : & Node::left;
    }


    Node* splice_me( Node* ppp, Node* Node::* par_br, Node* Node::* child_br )
    {
        KJB(ASSERT( ppp && ppp != root ));

        Node    *child_p = ppp ->* child_br,
                *par_p = ppp -> parent;
        KJB(ASSERT( par_p && is_not_nil( par_p ) ));
        KJB(ASSERT( ppp == par_p ->* par_br ));
        KJB(ASSERT( is_nil( ppp ->* opposite_direction( child_br ) ) ));
        KJB(ASSERT( child_p ));
        KJB(ASSERT( is_nil( child_p ) || ppp == child_p -> parent ));
        KJB(ASSERT( 00 == m_nil.parent ));

        /*
         * NOTE WELL:  we do the following EVEN WHEN CHILD IS THE NIL NODE!!
         * That's because it is the easiest way to remember the bereaved
         * parent node, an entity we often must manipulate during a deletion.
         * The alternative was something like the following:
         *
                par_p ->* par_br = child_p;
                if ( is_not_nil( child_p ) )
                    child_p -> parent = par_p;
        */
        par_p -> you_are_my_child( child_p, par_br );

        KJB(ASSERT( (ppp ->* child_br) -> parent == ppp -> parent ));
        KJB(ASSERT( ppp -> parent ->* par_br == ppp ->* child_br ));

        return ppp;
    }


    Node* semiauto_splice( Node* ppp, Node* Node::* child_br )
    {
        if ( ppp == root )
        {
            KJB(ASSERT( is_nil( ppp ->* opposite_direction( child_br ) ) ));
            KJB(ASSERT(     is_nil( ppp ->* child_br )
                        ||  ppp == ( ppp ->* child_br ) -> parent ));
            root = ppp ->* child_br;
            return ppp;
        }
        return splice_me( ppp, parent_branch_to_me( ppp ), child_br );
    }


    Node* fully_auto_splice( Node* ppp, Node ** tochild )
    {
        if ( is_nil( ppp -> left ) )
        {
            *tochild = ppp -> right;
            return semiauto_splice( ppp, & Node::right );
        }
        if ( is_nil( ppp -> right ) )
        {
            *tochild = ppp -> left;
            return semiauto_splice( ppp, & Node::left );
        }
        return 00;  // cannot splice ppp because it has two children
    }


    Node* del_child_not_target( Node* target, Node** to_child )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( target && is_not_nil( target ) ));
        KJB(ASSERT( is_not_nil( target -> right ) ));
        KJB(ASSERT( 00 == m_nil.parent ));

        // must find victim (vic)
        Node *vic = target -> right;
        for ( ; is_not_nil( vic -> left ); vic = vic -> left )
            ;

        KJB(ASSERT( is_not_nil( vic ) && is_nil( vic -> left ) ));

        /*
         * Now target assumes the identity of victim, by taking its key, its
         * satellite value, its locator, and its location_list entry.
         */
        target -> key = vic -> key;
        target -> sat = vic -> sat;
        Loc_tp &TaLo( target -> locator ), &ViLo( vic -> locator );
        std::swap( location_list[ TaLo ], location_list[ ViLo ] );
        std::swap( TaLo, ViLo );

        // update subtree-sums between target, victim (i.e., retrace the path).
        for ( Node* ppp = target -> right; ppp != vic; ppp = ppp -> left )
        {
            KJB(ASSERT( is_not_nil( ppp ) ));
            ppp -> sum -= vic -> key;
        }

        // splice out vic; vic's parent vp claims vic's right child (if any).
        *to_child = vic -> right;
        return semiauto_splice( vic, & Node::right );
    }


    void resolve_double_black( Node* xblack )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( xblack ));
        KJB(ASSERT( m_nil.is_black ));
        KJB(ASSERT( root && is_not_nil( root ) ));

        if ( xblack -> is_red() )
        {
            // whoa, this is too easy!
            xblack -> is_black = true;
            return;
        }

        if ( xblack == root )
        {
            return; // ignore extra black at root b/c root has no sibling
        }

        // Let "me" = xblack.  Since I am black, I must have a sibling.
        Node* Node::* xb_br = parent_branch_to_me( xblack );
        Node* Node::* sib_br = opposite_direction( xb_br );
        Node* sib = xblack -> parent ->* sib_br;
        KJB(ASSERT( sib && is_not_nil( sib ) )); // CLRS page 290

        // If my sibling is red, it can be rotated to become my (black) parent.
        if ( sib -> is_red() )
        {
            return case_of_the_red_sibling(
                                            xblack,
                                            xb_br
#ifdef DEBUGGING
                                            ,sib
#endif
                                        );
        }

        Node    *near_nephew = sib ->* xb_br,
                *far_nephew = sib ->* sib_br;
        KJB(ASSERT( far_nephew && near_nephew )); // could be nil

        // Resolution depends on my nephews (possibly nil).  Tail recursion:
        if ( far_nephew -> is_red() )
        {
            return case_of_the_far_red_nephew( sib, xb_br );
        }

        if ( near_nephew -> is_black )
        {
            return case_of_the_black_sib_and_nephews( sib );
        }

        return case_of_the_near_red_nephew( xblack, sib, xb_br );
    }


    void case_of_the_black_sib_and_nephews( Node* sib )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( sib && is_not_nil( sib ) && sib -> is_black ));
        KJB(ASSERT( sib -> left && sib -> left -> is_black ));
        KJB(ASSERT( sib -> right && sib -> right -> is_black ));
        KJB(ASSERT( m_nil.is_black ));
        sib -> is_black = false;
        m_nil.parent = 00;

        return resolve_double_black( sib -> parent );
    }


    void case_of_the_far_red_nephew( Node* oldsib, Node* Node::* xb_br )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( m_nil.is_black ));

        Node* Node::* sib_br = opposite_direction( xb_br );

        KJB(ASSERT( oldsib ));

        Node    *oldparent = oldsib -> parent,
                *old_far_nephew = oldsib ->* sib_br;
        KJB(ASSERT( oldparent && is_not_nil( oldparent ) ));
        KJB(ASSERT( oldsib == oldparent ->* sib_br ));
        KJB(ASSERT( oldsib -> is_black ));
        KJB(ASSERT( old_far_nephew -> is_red() ));

        rotate( to_parent_link( oldparent ), sib_br );
        old_far_nephew -> is_black = true;
        m_nil.parent = 00;
    }


    void case_of_the_near_red_nephew(
        Node* xblack,
        Node* oldsib,
        Node* Node::* xb_br
    )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( xblack -> parent == oldsib -> parent ));
        KJB(ASSERT( oldsib && is_not_nil( oldsib ) && oldsib -> is_black ));
        KJB(ASSERT( oldsib -> left && oldsib -> right ));
        KJB(ASSERT( m_nil.is_black ));

        Node    *old_red_nef = ( oldsib ->* xb_br ),
                *parent = xblack -> parent;

        // far nephew must be black too!  only the near nephew is red.
        KJB(ASSERT( ( oldsib ->* opposite_direction( xb_br ) ) -> is_black ));
        KJB(ASSERT( old_red_nef -> is_red() ));

        /* unzigzag xblack's parent,sib,near-nephew, make them swap colors.
         * oldsib becomes new far-nephew.  old near-nephew becomes new sib.
         *
         * Also, unzigzag likely corrupts xblack -> parent if *xblack is nil.
         * However, I think we have no need to care about that anymore.
         */
        unzigzag( parent, opposite_direction( xb_br ) );
        m_nil.parent = 00;
        oldsib -> is_black = false;

        Node *& new_blk_sib = old_red_nef;  // alias for clarity
        new_blk_sib -> is_black = true;

        // old_red_nef has become the new black sibling of xblack
        KJB(ASSERT( new_blk_sib == parent ->* opposite_direction( xb_br ) ));
        KJB(ASSERT( oldsib == new_blk_sib ->* opposite_direction( xb_br ) ));
        return case_of_the_far_red_nephew( new_blk_sib, xb_br );
    }


    void case_of_the_red_sibling(
        Node* xblack,
        Node* Node::* xb_br
#ifdef DEBUGGING
        ,Node* sib
#endif
    )
    {
#ifdef DEBUGGING
        enter( __func__ );
        KJB(ASSERT( m_nil.is_black ));
        KJB(ASSERT( sib && is_not_nil( sib ) ));
        KJB(ASSERT( xblack -> parent == sib -> parent ));
        KJB(ASSERT( xblack -> is_black &&  sib -> is_red() ));
        KJB(ASSERT( xblack != root ));
#endif

        Node* xb_parent = xblack -> parent;

        Node* Node::* sib_br = opposite_direction( xb_br );
        rotate( to_parent_link( xb_parent ), sib_br );
        m_nil.parent = 00;

        // the following can be useful if xblack is nil, otherwise is benign:
        xblack -> parent = xb_parent;

        KJB(ASSERT( xb_parent -> is_red() ));
#ifdef DEBUGGING
        KJB(ASSERT( xb_parent == sib ->* xb_br ));
        KJB(ASSERT( sib -> is_black ));
#endif
        KJB(ASSERT( (xb_parent ->* sib_br) -> is_black ));
        KJB(ASSERT( (xb_parent ->* xb_br ) == xblack ));
        KJB(ASSERT( xblack -> is_black ));

        resolve_double_black( xblack );
    }


    void kill_a_node( Node* target )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        KJB(ASSERT( 00 == m_nil.parent ));
        KJB(ASSERT( target && is_not_nil( target ) ));
        const Key_tp& query_key( target -> key );

        for ( Node* ppp = target; ppp != root; ppp = ppp -> parent )
        {
            ppp -> sum -= query_key;
        }
        root -> sum -= query_key;

        // Splice out target if possible, otherwise replace its contents
        Node *xblack, *tar2 = fully_auto_splice( target, & xblack );

        // *xblack is nil iff xblack -> parent equals tar2.
        KJB(ASSERT( 00 == tar2 || 00 == m_nil.parent || is_nil( xblack ) ));
        KJB(ASSERT( 00 == tar2 || m_nil.parent || is_not_nil( xblack ) ));

        if ( 00 == tar2 )
        {
            tar2 = del_child_not_target( target, & xblack );
        }

        KJB(ASSERT( tar2 ));
        KJB(ASSERT( is_nil( tar2 -> left ) || is_nil( tar2 -> right ) ));
        KJB(ASSERT( is_nil( tar2 -> left ) || xblack == tar2 -> left ));
        KJB(ASSERT( is_nil( tar2 -> right ) || xblack == tar2 -> right ));
        KJB(ASSERT( tar2 == root || xblack -> parent == tar2 -> parent ));
        KJB(ASSERT(     tar2 == root
                    ||  tar2 -> parent -> left == xblack
                    ||  tar2 -> parent -> right == xblack ));

        if ( tar2 -> is_black )
        {
            resolve_double_black( xblack );
        }
        m_nil.parent = 00;
        dispose( tar2 );
    }


    bool dictionary_is_small_linear_array() const
    {
        return size() <= TREE_THRESH;
    }


    int blackheight_in_linear_time() const
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        if ( dictionary_is_small_linear_array() )
        {
            return 0;
        }
        return blackheight_in_linear_time( root );
    }

    bool red_node_has_red_child_in_linear_time() const
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        return red_node_has_red_child_in_linear_time( root );
    }

    bool sums_are_correct_in_linear_time() const
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        return sums_are_correct_in_linear_time( root );
    }


    Node* recursive_copy(
        const Node* src,
        const Redblack_subtree_sum< SATELLITE_TYPE >& st
    )
    {
        KJB(ASSERT( src ));
        if ( st.is_nil( src ) ) // the other tree's nil node
        {
            return & m_nil;
        }

        Node* my_copy = new Node( *src );
        /* my_copy -> parent = 00; not actually necessary */
        my_copy -> link_left_child( recursive_copy( src -> left, st ) );
        my_copy -> link_right_child( recursive_copy( src -> right, st ) );
        m_nil.parent = 00;

        const Loc_tp l = src -> locator;
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(ASSERT( l < location_list.size() ));
        location_list.at( l ) = my_copy;
#else
        location_list[ l ] = my_copy;
#endif

        return my_copy;
    }



#ifdef DEBUGGING
    bool is_bst_in_linear_time() const
    {
        const Key_tp KMAX( std::numeric_limits< Key_tp >::max() );
        enter( __func__ );
        return is_bst_in_linear_time( root, -KMAX, +KMAX );
    }


    bool is_bst_in_linear_time(
        const Node* ppp,
        const Key_tp& min,
        const Key_tp& max
    )   const
    {
        KJB(ASSERT( ppp ));
        if ( is_nil( ppp ) )
        {
            return true;
        }
        const Key_tp& kii = ppp -> key;

        /*
         * When we insert, we put equal keys in the right subtree, but when
         * we rotate, equal keys could end up in the left subtree too.
         * Thus, kii==min or kii==max is acceptable.
         */
        if ( kii < min || max < kii )   // equality is not a failure
        {
            return false;
        }

        const Node  *pl = ppp -> left,
                    *pr = ppp -> right;

        return      ( is_nil( pl ) || pl -> parent == ppp )
                &&  ( is_nil( pr ) || pr -> parent == ppp )
                &&  is_bst_in_linear_time( pr, kii, max )
                &&  is_bst_in_linear_time( pl, min, kii );
    }


    void locators_scan_nlogn_time(
        LocCensus_tp* census_ptr,
        const Node* ppp
    )   const
    {
        KJB(ASSERT( census_ptr ));
        KJB(ASSERT( ppp ));
        LocCensus_tp& census( *census_ptr );
        if ( is_nil( ppp ) )
        {
            return;
        }
        census[ ppp -> locator ] += 1;
        locators_scan_nlogn_time( census_ptr, ppp -> left );
        locators_scan_nlogn_time( census_ptr, ppp -> right );
    }

    bool locators_valid_in_nlogn_time() const
    {
        enter( __func__ );
        typedef typename LocCensus_tp::iterator LCI;

        LocCensus_tp census;

        // scan dictionary and record all locators stored in the records
        if ( dictionary_is_small_linear_array() )
        {
            for ( size_t iii = 0; iii < size(); ++iii )
            {
                Loc_tp loc = root[ iii ].locator;
                census[ loc ] += 1;
                if ( ! loc_list_good_here( root + iii ) )
                {
                    return fail( __LINE__ );
                }
            }
        }
        else
        {
            locators_scan_nlogn_time( & census, root );
        }

        /*
         * Look at census result.  Each map entry should record a locator that
         * is found in exactly one node, and the node claiming the locator
         * should be at the address recorded in locator_list at that index.
         */
        for ( LCI iii = census.begin(); iii != census.end(); ++iii )
        {
            Loc_tp loc = iii -> first;
            if ( iii -> second != 1 )
            {
                return fail( __LINE__ );
            }
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            Node* ppp = location_list[ loc ];
            if ( 00 == ppp || ppp -> locator != loc )
            {
                return fail( __LINE__ );
            }
#else
            LLCI i = location_list.find(loc);
            if (  location_list.end() == i
               || 00 == i -> second
               || i -> first != loc
            )
            {
                return fail( __LINE__ );
            }
#endif
        }

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        // Scan the list of unused locators.
        LocCensus_tp unused;
        for ( size_t iii = 0; iii < free_locator_list.size(); ++iii )
        {
            unused[ free_locator_list[ iii ] ] += 1;
        }

        /*
         * Scan the results of the unused list.  Each entry (if any) should
         * record a locator that is found just once, and it should not be
         * found in the tree; likewise that index should mark a NULL entry in
         * the table.
         */
        for ( LCI iii = unused.begin(); iii != unused.end(); ++iii )
        {
            Loc_tp loc = iii -> first;
            // test for free_list duplicates
            if ( iii -> second != 1 ) return fail( __LINE__ );
            // loc must not be found in tree
            if ( census[ loc ] != 0 )
            {
                KJB(TEST_PSE(( "census loc is %d\n", int(census[loc]) )));
                return fail( __LINE__ );
            }
            // loc must be valid
            if ( location_list.size() <= loc ) return fail( __LINE__ );
            // loc must be unused
            if ( location_list[ loc ] != 00 ) return fail( __LINE__ );
        }
#endif

        /*
         * Scan location_list.  Every entry must correspond to an entry in
         * census (for pointers not equal to NULL) or to unused (for pointers
         * equal to NULL).
         */
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        for ( Loc_tp loc = 0; loc < location_list.size(); ++loc )
        {
            if ( location_list[ loc ] )
            {
                if ( census[ loc ] != 1 )
                {
                    std::ostringstream oss;
                    oss << "locator index " << loc
                        << " has\n\tcensus value " << int(census[loc])
                        << "\n\tptr value " << location_list[loc]
                        << "\n\tptr loc " << location_list[loc]->locator
                        << '\n';
                    KJB(TEST_PSE(( "%s\n", oss.str().c_str() )));
                    return fail( __LINE__ );
                }
            }
            else if ( unused[ loc ] != 1 )
            {
                return fail( __LINE__ );
            }
        }
#else
        for (LLCI i = location_list.begin(); i != location_list.end(); ++i)
        {
            const Loc_tp loc = i -> first;
            if (00 == i -> second) return fail( __LINE__ );
            
            if ( census[ loc ] != 1 )
            {
                std::ostringstream oss;
                oss << "locator index " << loc
                    << " has\n\tcensus value " << int(census[loc])
                    << "\n\tptr value " << i -> second
                    << "\n\tptr loc " << i -> second -> locator
                    << '\n';
                KJB(TEST_PSE(( "%s\n", oss.str().c_str() )));
                return fail( __LINE__ );
            }
        }
#endif

        return true;
    }
#endif


    Loc_tp linear_insert( const Key_tp& key, const Sat_tp& sat )
    {
        const int BLACK = 1;
        Loc_tp nuloc = obtain_avail_locator();
        root[ m_size ] = Node( key, sat, BLACK, & m_nil, & m_nil, nuloc );
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(ASSERT( 00 == location_list.at( nuloc ) ));
#endif
        location_list[ nuloc ] = root + m_size;
        ++m_size;
        return nuloc;
    }


    Loc_tp tree_insert( const Key_tp& key, const Sat_tp& sat )
    {
        if ( TREE_THRESH == size() )
        {
            make_it_a_real_tree_now();
        }
        Node* n00b = new_node( key, sat, 0 ); // red
        insert_gp( &root, *n00b < *root, n00b );
        root -> is_black = true;
        ++m_size;
        KJB(ASSERT( 00 == m_nil.parent ));
        KJB(ASSERT( n00b ));
        return n00b -> locator;
    }


    void db_print_locators() const
    {
#ifdef DEBUGGING
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(TEST_PSE(( "Locs in use: " )));
        for ( size_t iii = 0; iii < location_list.size(); ++iii )
        {
            if ( location_list.at( iii ) )
            {
                KJB(TEST_PSE(( "%s%d", (iii ? "," : ""), iii )));
            }
        }
        KJB(TEST_PSE(( "\nLocs avail: " )));
        for ( size_t iii = 0; iii < free_locator_list.size(); ++iii )
        {
            KJB(TEST_PSE(( "%s%d", (iii ? ",":""),
                                   free_locator_list.at( iii ) )));
        }
#else
        KJB(TEST_PSE(( "Locs in use:" )));
        for (LLCI i = location_list.begin(); i != location_list.end(); ++i)
        {
            KJB(TEST_PSE((" %u", i -> first)));
        }
#endif
        KJB(TEST_PSE(( "\n" )));
#endif
    }


    bool del_array_elt( size_t index )
    {
        KJB(ASSERT( index < size() ));

        Loc_tp loc = root[ index ].locator;
        release_locator( loc );
        --m_size; // shrink the array size -- yes, a little bit premature

        /*
         * If the record we want to erase is anywhere except the last
         * array entry, then we clobber it with the last array entry.
         * The reason we already decremented m_size was to state this operation
         * a bit more cleanly.
         */
        if ( index < m_size )
        {
            // clobber the key and satellite data
            root[ index ] = root[ m_size ];
            // Clobbering record needs its location_list pointer updated.
            KJB(ASSERT( location_list[ root[index].locator ] == root+m_size ));
            location_list[ root[ index ].locator ] = root + index;
        }

        if ( 0 == m_size )
        {
            delete[] root;
        }

        return true;
    }


    bool del_tree_node( Node* ppp )
    {
        KJB(ASSERT( ppp && loc_list_good_here( ppp ) ));
        kill_a_node( ppp );
        --m_size;
        KJB(ASSERT( 00 == m_nil.parent ));

        // Test whether the dictionary has just now shrunk down to lin-arr size
        if ( TREE_THRESH == m_size )
        {
            condense_into_linear_array();
        }
        return true;
    }


    Loc_tp loc_extremum(
        Node* Node::* branch,
        const Node* ( *pf )( const Node*, const Node* )
    )   const
    {
        if ( 0 == size() )
        {
            return 0;   // sentinel value for empty dictionaries
        }

        // handle the small linear array case
        if ( dictionary_is_small_linear_array() )
        {
            const Node* ppp = (*pf)( root, root + size() );
            return LOCATOR_BASE + ppp -> locator;
        }

        // common case: search the tree down its chosen branch
        KJB(ASSERT( root ));
        const Node* ppp;
        for ( ppp = root; ppp && is_not_nil( ppp ->* branch );
                                                        ppp = ppp ->* branch )
        {
            KJB(ASSERT( ppp ));
        }
        KJB(ASSERT( ppp && is_nil( ppp ->* branch ) ));
        return LOCATOR_BASE + ppp -> locator;
    }


    Loc_tp array_seek_cukes( Key_tp cumulative_keysum ) const
    {
#if 0
        std::vector< Node > dicopy( root, root + size() );
        std::sort( dicopy.begin(), dicopy.end() ); // sort by keys
#else
        Node dicopy[ TREE_THRESH ];
        std::copy(root, root + size(), dicopy);
        std::sort( dicopy, dicopy + size() ); // sort by keys
        KJB(ASSERT(0 < size() && size() <= TREE_THRESH));
#endif
        Key_tp sum_so_far = 0;
        for ( size_t iii = 0; iii < size(); ++iii )
        {
            if ( cumulative_keysum <= ( sum_so_far += dicopy[ iii ].key ) )
            {
                return dicopy[ iii ].locator;
            }
        }
        KJB(ASSERT( sum_so_far < cumulative_keysum ));
        chatter( "sought a cumulative key sum larger than sum of all keys 1" );
        // ret loc to last record anyway -- maybe it's a floating point glitch.
        // We deliberately use at() here to throw in case that size is zero.
#if 0
        return dicopy.at( int(size()) - 1 ).locator;
#else
        return dicopy[ size() - 1 ].locator;
#endif
    }


    Loc_tp tree_seek_cukes( const Node* ppp, Key_tp cumulative_keysum ) const
    {
        KJB(ASSERT( ppp && is_not_nil( ppp ) ));
        if ( are_both_children_nil( ppp ) )
        {
            if ( ppp -> key < cumulative_keysum )
            {
                chatter( "sought a cumulative key sum larger than "
                                                        "sum of all keys 2" );
            }
            return ppp -> locator;
        }
        const Key_tp lsum = is_not_nil( ppp -> left ) ? ppp -> left -> sum : 0;
        // Uncommon case:  go left.
        if ( is_not_nil( ppp -> left ) && cumulative_keysum <= lsum )
        {
            return tree_seek_cukes( ppp -> left, cumulative_keysum );
        }
        cumulative_keysum -= lsum;
        // Also uncommon case:  retrieve this node
        if ( cumulative_keysum <= ppp -> key )
        {
            return ppp -> locator;
        }
        // Degenerate case:  ck is too big but we cannot go right; we forgive.
        if ( is_nil( ppp -> right ) )
        {
            chatter( "sought a cumulative key sum larger than "
                                                        "sum of all keys 3" );
            return ppp -> locator;
        }
        cumulative_keysum -= ppp -> key;
        // Common case:  go right.  We have already shrunk c_k appropriately.
        return tree_seek_cukes( ppp -> right, cumulative_keysum );
    }


    void copy_tree_into_empty(
        const Redblack_subtree_sum< SATELLITE_TYPE >& tree
    )
    {
        KJB(ASSERT(0 == size()));
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        KJB(ASSERT(0 == location_list.size()));
        KJB(ASSERT(0 == free_locator_list.size()));
#else
        KJB(ASSERT(location_list.empty()));
#endif

        if ( 0 == tree.size() ) return;
        root = 00; // must contain a defined value, if "catch" clause runs.

        try
        {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            location_list.resize(tree.location_list.size());
            free_locator_list.resize(tree.free_locator_list.size());
            std::copy(tree.free_locator_list.begin(),
                    tree.free_locator_list.end(), free_locator_list.begin());
#endif
            m_size = tree.size();

            if ( tree.dictionary_is_small_linear_array() )
            {
                root = new Node[ TREE_THRESH ];
                std::copy(tree.root, tree.root + tree.size(), root);

                for ( size_t iii = 0; iii < tree.size(); ++iii )
                {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
                    const Loc_tp l = root[iii].locator;
                    KJB(ASSERT( l < location_list.size() ));
                    location_list.at( l ) = root + iii;
#else
                    location_list[ root[iii].locator ] = root + iii;
#endif
                }
            }
            else
            {
                root = recursive_copy( tree.root, tree );
            }
        }
        catch (std::bad_alloc& e)
        {
            // If we cannot do the whole thing, retract any partial progress.
            clear();
            throw e;
        }
    }


public:

    Redblack_subtree_sum()
    :   m_nil( 0, Sat_tp(), true, 00, 00, 00 ),
        m_size( 0 )
    {} // root is undefined, you got a problem with that???


    void clear()
    {
        KJB(ASSERT( 00 == m_nil.parent ));
        if ( 0 == size() )
        {
            return;
        }

        if ( dictionary_is_small_linear_array() )
        {
            delete[] root;
        }
        else
        {
            recursive_destroy( root );
        }

        m_size = 0;
        location_list.clear();
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        free_locator_list.clear();
#endif
    }


    Redblack_subtree_sum( const Redblack_subtree_sum< SATELLITE_TYPE >& tree )
    :   m_nil( 0, Sat_tp(), true, 00, 00, 00 ),
        m_size( 0 )
    {
        copy_tree_into_empty( tree );
    }


    Redblack_subtree_sum& operator=(
        const Redblack_subtree_sum< SATELLITE_TYPE >& tree
    )
    {
        if ( this != &tree )
        {
            clear();
            copy_tree_into_empty( tree );
        }
        return *this;
    }


    ~Redblack_subtree_sum()
    {
        clear();
    }


    Loc_tp insert( const Key_tp& key, const Sat_tp& sat )
    {
        KJB(ASSERT( 00 == m_nil.parent ));
        if ( 0 == size() )
        {
            root = new Node[ TREE_THRESH ];
        }
        // Test whether we can do the insertion and STILL remain a linear array
        if ( size() < TREE_THRESH )
        {
            return LOCATOR_BASE + linear_insert( key, sat );
        }
        return LOCATOR_BASE + tree_insert( key, sat );
    }

    Loc_tp ins_max_key( const Sat_tp& sat )
    {
        return insert( std::numeric_limits< Key_tp >::max(), sat );
    }

#ifdef DEBUGGING
    void debug_print( std::ostream& os ) const
    {
        if ( 0 == size() )
        {
            os << "tree is empty\n";
        }
        else if ( dictionary_is_small_linear_array() )
        {
            os << "tiny tree is in an unsorted array, root=" << root << '\n';
            for ( size_t iii = 0; iii < size(); ++iii )
            {
                KJB(ASSERT( are_both_children_nil( root + iii ) ));
                recursive_db_print( root + iii, 0, os );
            }
        }
        else
        {
            os << "Big tree with nil at " << & m_nil
               << ", root=" << root << '\n';
            recursive_db_print( root, 0, os );
        }
        db_print_locators();
    }
#else
    void debug_print( std::ostream& ) const {}
#endif

    bool tree_valid_in_nlogn_time() const
    {
#ifdef DEBUGGING
        enter( __func__ );
        if ( m_nil.is_red() )
        {
            return fail( "nil is red" );
        }

        if ( m_nil.parent )
        {
            return fail( "nil points to a parent" );
        }

        if ( ! locators_valid_in_nlogn_time() )
        {
            return fail( "locators are bad" );
        }

        if ( dictionary_is_small_linear_array() )
        {
            return true;
        }

        if  (       blackheight_in_linear_time() == BLACKHEIGHT_BAD
                ||  root -> is_red()
                ||  red_node_has_red_child_in_linear_time()
                //  ||  ! sums_are_correct_in_linear_time()
                ||  ! sums_are_close_enough_in_linear_time( root )
                ||  ! is_bst_in_linear_time()
            )
        {
            return fail( "tree structure is bad" );
        }
#endif
        return true;
    }

    bool find_key( const Key_tp& key, Sat_tp* sat_out, Loc_tp* loc_out )
    {
        bool is_found;
        if ( dictionary_is_small_linear_array() )
        {
            is_found = linear_search( key, sat_out, loc_out, 00 );
        }
        else
        {
            is_found = tree_search( key, sat_out, root, loc_out );
        }

        // We bias the locator to make it a little bit more opaque.
        if ( is_found && loc_out )
        {
            *loc_out += LOCATOR_BASE;
        }

        return is_found;
    }


    bool erase_key( const Key_tp& query_key, Sat_tp* sat_out )
    {
        KJB(ASSERT( 00 == m_nil.parent ));

        // handle the mini-array case
        if ( dictionary_is_small_linear_array() )
        {
            size_t index;
            if ( ! linear_search( query_key, sat_out, 00, & index ) )
            {
                return false; // not found
            }
            return del_array_elt( index );
        }

        // common case: dictionary is a tree
        Node* ppp = tree_search( query_key, sat_out, root, 00 );
        if ( 00 == ppp )
        {
            return false;
        }
        KJB(ASSERT( ppp -> key == query_key ));

        return del_tree_node( ppp );
    }


    bool access_loc( Loc_tp query_loc, Key_tp* key_out, Sat_tp* sat_out ) const
    {
        if ( query_loc < LOCATOR_BASE )
        {
            return false;
        }
        query_loc -= LOCATOR_BASE; // this is why we pass in the loc by value

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        if ( location_list.size() <= query_loc )
        {
            return false;
        }

        const Node* ppp = location_list.at( query_loc );
        if ( 00 == ppp )
        {
            return false;
        }
#else
        LLCI i = location_list.find(query_loc);
        if (location_list.end() == i) return false;
        const Node* const ppp = i -> second;
#endif
        KJB(ASSERT( ppp -> locator == query_loc ));

        if ( key_out )
        {
            *key_out = ppp -> key;
        }
        if ( sat_out )
        {
            *sat_out = ppp -> sat;
        }
        return true;
    }


    bool erase_loc( Loc_tp query_loc )
    {
        KJB(ASSERT( LOCATOR_BASE <= query_loc ));
        query_loc -= LOCATOR_BASE; // this is why we pass in the loc by value

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        if ( location_list.size() <= query_loc )
        {
            return false;
        }
#else
        LLCI i = location_list.find(query_loc);
        if (location_list.end() == i) return false;
#endif

        Node* ppp = location_list[ query_loc ];
        if ( 00 == ppp )
        {
            return false;
        }
        KJB(ASSERT( ppp -> locator == query_loc ));

        // handle the linear array case
        if ( dictionary_is_small_linear_array() )
        {
            if ( ppp < root || root + size() <= ppp )
            {
                return false;
            }
            KJB(ASSERT( loc_list_good_here( ppp ) ));
            return del_array_elt( ppp - root );
        }

        // common case: dictionary is a tree
        return del_tree_node( ppp );
    }



    Loc_tp loc_min() const
    {
        return loc_extremum( & Node::left, & std::min_element< const Node* > );
    }


    Loc_tp loc_max() const
    {
        return loc_extremum( & Node::right, & std::max_element< const Node* >);
    }


    size_t size() const
    {
        return m_size;
    }


    bool is_empty() const
    {
        return 0 == m_size;
    }


    bool rekey_loc( Loc_tp query_loc, const Key_tp& newkey )
    {
#ifdef DEBUGGING
        enter( __func__ );
#endif
        if ( query_loc < LOCATOR_BASE )
        {
            return false;
        }

        query_loc -= LOCATOR_BASE; // this is why we pass in the loc by value

#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        if ( location_list.size() <= query_loc )
        {
            return false;
        }

        Node* const ppp = location_list[ query_loc ];
        if ( 00 == ppp )
        {
            return false;
        }
#else
        LLCI i = location_list.find(query_loc);
        if (location_list.end() == i) return false;
        Node* const ppp = i -> second;
#endif
        KJB(ASSERT( ppp -> locator == query_loc ));

        // handle the linear array case:  unsorted, so just update key field
        if ( dictionary_is_small_linear_array() )
        {
            if ( ppp < root || root + size() <= ppp )
            {
                return false;
            }
            ppp -> key = newkey;
            return true;
        }

        // common case: dictionary is a tree
        // strategy:  insert an "impostor," a new node w/ new key, old sat
        Loc_tp newloc = insert( newkey, ppp -> sat ) - LOCATOR_BASE;
        Node* const qqq = location_list[ newloc ];
        KJB(ASSERT( qqq -> locator == newloc ));

        // now swap their locators, so impostor bears the query_loc locator
        std::swap( location_list[ query_loc ], location_list[ newloc ] );
        std::swap( ppp -> locator, qqq -> locator );
        KJB(ASSERT( loc_list_good_here( ppp ) ));
        KJB(ASSERT( ppp == location_list[ newloc ] ));

        // now we can "disappear" the old node and no one will even notice.
        bool ok = del_tree_node( ppp );
        // the perfect crime: the old locator continues to work
        KJB(ASSERT( newkey == location_list[ query_loc ] -> key ));

        /*
         * Warning:  ppp could now be dangling, or qqq could now be dangling!
         * Neither is safe to use anymore!
         *
         * If *ppp had one child or was a leaf, then ppp is now dangling.
         * But if *ppp had two children, some other node was deleted and its
         * fields moved into *ppp, and the location list was also twiddled to
         * make *ppp look like the victim -- which is all FINE.  However, it is
         * possible (as I learned the hard way) that *qqq was this victim!
         * In which case, qqq is dangling.
         *
         * Conclusion:  do NOT assert qqq == location_list[ query_loc ].
         */

        return ok;
    }


    Key_tp root_sum() const
    {
        if ( 0 == size() )
        {
            return 0;
        }
        if ( dictionary_is_small_linear_array() )
        {
            return std::accumulate( root, root+size(), Key_tp( 0 ), AddKey() );
        }
        return root -> sum;
    }

    Loc_tp loc_using_cumulative_key_sum( Key_tp cumulative_keysum ) const
    {
        if ( 0 == size() )
        {
            return 0;   // obviously bad because good locators are positive
        }
        if ( dictionary_is_small_linear_array() )
        {
            return LOCATOR_BASE + array_seek_cukes( cumulative_keysum );
        }
        return LOCATOR_BASE + tree_seek_cukes( root, cumulative_keysum );
    }

    Loc_tp Dijkstra_extraction() const
    {
        return loc_min();
    }


    /*
     * ==============================
     *           ITERATOR
     * ==============================
     *
     * The iterator enumerates all the nodes in the tree, using the
     * location_list vector.  That vector, as you know, contains pointers
     * to tree nodes, but also unused cells that contain NULL values.
     * Thus, this iterator has to skip over the NULLs.
     */
    friend class const_iterator;

    class const_iterator
    :   public std::iterator< std::bidirectional_iterator_tag, Loc_tp >
    {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        size_t m_index;

        const Redblack_subtree_sum< Sat_tp > *m_tree;

        void advance_()
        {
            // skip index forward, over null pointers in location list
            while (   m_index < m_tree -> location_list.size()
                  &&  00 == m_tree -> location_list[m_index]
                  )
            {
                ++m_index;
            }
        }

        void retreat_()
        {
            // skip index backward, over null pointers in location list
            while ( 0 < m_index && 00 == m_tree -> location_list[m_index] )
            {
                --m_index;
            }
            if (0 == m_index) advance_();
        }
#else
        typedef typename Redblack_subtree_sum< Sat_tp >::LLCI RBLLI;
        RBLLI m_it;
#endif

    public:
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        const_iterator(size_t ix, const Redblack_subtree_sum< Sat_tp > *t)
        :   m_index(ix),
            m_tree(t)
        {
            NTX(t);
            advance_();
        }
#else
        const_iterator(RBLLI i) : m_it(i) {}
#endif

        Loc_tp operator*() const
        {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            const Node* n = m_tree -> location_list[m_index];
            KJB(ASSERT(n && n -> locator == m_index));
            return LOCATOR_BASE + m_index;
#else
            KJB(ASSERT(m_it -> second));
            KJB(ASSERT(m_it -> second -> locator == m_it -> first));
            return LOCATOR_BASE + m_it -> first;
#endif
        }

        bool operator==(const const_iterator& i) const
        {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            return m_index == i.m_index && m_tree == i.m_tree;
#else
            return m_it == i.m_it;
#endif
        }

        bool operator!=(const const_iterator& i) const
        {
            return ! operator==(i);
        }

        const_iterator& operator++()
        {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            ++m_index;
            advance_();
#else
            ++m_it;
#endif
            return *this;
        }
        const_iterator operator++(int)
        {
            const_iterator temp(*this);
            operator++();
            return temp;
        }
        const_iterator& operator--()
        {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
            --m_index;
            retreat_();
#else
            --m_it;
#endif
            return *this;
        }
        const_iterator operator--(int)
        {
            const_iterator temp(*this);
            operator--();
            return temp;
        }
    };

    const_iterator begin() const
    {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        return const_iterator(0, this);
#else
        return const_iterator(location_list.begin());
#endif
    }

    const_iterator end() const
    {
#if REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY
        return const_iterator(location_list.size(), this);
#else
        return const_iterator(location_list.end());
#endif
    }

#if 0
    /*
     * DOES NOT WORK -- as designed, the tree not entirely "pimpl" since it
     * has a member m_nil.  The leaf nodes all point to it.  If we swap the
     * representations we would have to change all the pointers formerly to
     * m_nil to the new member.  Otherwise, after the swap, ownership of m_nil
     * and ownership of the nodes pointing to it will differ, which is
     * intolerable.
     */
    void swap(Redblack_subtree_sum< SATELLITE_TYPE >& other)
    {
        std::swap(m_nil, other.m_nil);
        std::swap(root, other.root);
        std::swap(m_size, other.m_size);
        location_list.swap(other.location_list);
        free_locator_list.swap(other.free_locator_list);
    }
#endif
};


}
}


#if 0
namespace std
{
    template <typename S>
    inline void swap(
        kjb::qd::Redblack_subtree_sum< S >& rb1,
        kjb::qd::Redblack_subtree_sum< S >& rb2
    )
    {
        rb1.swap(rb2);
    }
}
#endif

#endif /* REDBLACK_H_PREDOEHL_12_DEC_2011_VISION */