stoprique.h

Go to the documentation of this file.

/*
 * $Id: stoprique.h 17555 2014-09-18 07:36:52Z predoehl $
 */

#ifndef STOPRIQUE3_H_INCLUDED_PREDOEHL_UOFARIZONAVISION
#define STOPRIQUE3_H_INCLUDED_PREDOEHL_UOFARIZONAVISION 1

#include <l/l_sys_lib.h>
#include <l/l_sys_rand.h>
#include <l_cpp/l_util.h>

#include <qd_cpp/redblack.h>

namespace kjb
{
namespace qd
{

template< typename SATELLITE_TYPE, int POWERLAW_NUM, int POWERLAW_DEN >
class StochasticPriorityQueue
:   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;

    inline static Key_tp power_law()
    {
        return Key_tp( POWERLAW_NUM ) / Key_tp( POWERLAW_DEN );
    }

    enum {
        BAD_LOC = 0 
    };

private:

    struct SatLoc {
        Sat_tp dat;     
        Loc_tp spqloc;  
        SatLoc( const Sat_tp& sat = Sat_tp(), Loc_tp bxl = 0 )
        :   dat( sat ), spqloc( bxl )
        {}
    };

    typedef Redblack_subtree_sum< SatLoc > RBT;

    enum {
        LOC_BIAS = 12345    
    };

    struct Compo {
        RBT* subq;  
        Loc_tp loc; 
        Sat_tp sat; 
        Key_tp enr; 

        Compo( RBT* pq, Loc_tp pl, const Sat_tp& ps, const Key_tp& pe )
        :   subq( pq ), loc( pl ), sat( ps ), enr( pe )
        {}

        void clear_it()
        {
            subq = 00;
        }

        bool is_cleared() const
        {
            return 00 == subq;
        }
    };

    std::vector< Compo > m_master;



    RBT m_always;

    RBT m_sometimes;

    RBT m_never;



    static inline
    Key_tp MAX_ENERGY() { return std::numeric_limits< Key_tp >::max(); }


    static inline
    Key_tp DUMMY_WT() { return 0; }


    static inline Key_tp energy2weight( const Key_tp& energy )
    {
        /*
         * polynomial decay:  1/(energy + epsilon) to some positive power
         */
        return pow( energy, power_law() );

        /*
         * exponential decay:  base ^ {-energy}.
        return pow( power_law(), -energy );
         */
    }


    static inline Key_tp nice_e2w( const Key_tp& enr )
    {
        return 0 < enr && enr < MAX_ENERGY() ? energy2weight(enr) : DUMMY_WT();
    }



    inline RBT& which_sub_queue( const Key_tp& energy )
    {
        if ( 0 == energy )
        {
            return m_always;
        }
        if ( MAX_ENERGY() <= energy )
        {
            return m_never;
        }
        return m_sometimes;
    }


    Loc_tp insert_here( RBT& subq, const Sat_tp& sat, const Key_tp& energy )
    {
        SatLoc satloc( sat, LOC_BIAS + m_master.size() );
        Loc_tp inner_loc = subq.insert( nice_e2w( energy ), satloc );
        m_master.push_back( Compo( & subq, inner_loc, sat, energy ) );
        return satloc.spqloc;
    }


    Compo* ref( Loc_tp spqloc )
    {
        if ( spqloc < LOC_BIAS )
        {
            return 00;
        }
        register Loc_tp unbiased = spqloc - LOC_BIAS;
        return m_master.size() <= unbiased ? 00 : & m_master[ unbiased ];
    }


    const Compo* ref( Loc_tp spqloc ) const
    {
        if ( spqloc < LOC_BIAS )
        {
            return 00;
        }
        register Loc_tp unbiased = spqloc - LOC_BIAS;
        return m_master.size() <= unbiased ? 00 : & m_master[ unbiased ];
    }



public:

    size_t size() const
    {
        return m_always.size() + m_sometimes.size() + m_never.size();
    }


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


    void clear()
    {
        m_always.clear();
        m_sometimes.clear();
        m_never.clear();
        m_master.clear();
    }


    Loc_tp ins_max_key( const Sat_tp& sat )
    {
        return insert_here( m_never, sat, MAX_ENERGY() );
    }


    Loc_tp insert( const Key_tp& energy, const Sat_tp& sat )
    {
        return insert_here( which_sub_queue( energy ), sat, energy );
    }


    bool access_loc( Loc_tp spqloc, Key_tp* energy, Sat_tp* serialnum ) const
    {
        const Compo* ccc = ref( spqloc );
        if ( 00 == ccc || ccc -> is_cleared() )
        {
            return false;
        }
        if ( energy )
        {
            *energy = ccc -> enr;
        }
        if ( serialnum )
        {
            *serialnum = ccc -> sat;
        }
        return true;
    }


    bool erase_loc( Loc_tp spqloc )
    {
        Compo* ccc = ref( spqloc );
        if ( 00 == ccc || ccc -> is_cleared() )
        {
            return false;
        }
        bool result = ccc -> subq -> erase_loc( ccc -> loc );
        ccc -> clear_it();
        return result;
    }


    bool rekey_loc( Loc_tp spqloc, const Key_tp& newenergy )
    {
        Compo* ccc = ref( spqloc );
        if ( 00 == ccc || ccc -> is_cleared() )
        {
            return false;
        }
        register const Key_tp oldenergy = ccc -> enr;
        if ( newenergy == oldenergy )
        {
            return true; // energy has not changed so nothing to do
        }
        ccc -> enr = newenergy;

        // handle the common case of node that stays within the same subqueue
        const Key_tp new_weight = nice_e2w( newenergy );
        RBT& newsubq = which_sub_queue( newenergy );
        if ( & newsubq == ccc -> subq ) // if node stays in same subqueue
        {
            return ccc -> subq -> rekey_loc( ccc -> loc, new_weight );
        }

        // node has to hop out of one subqueue and into another
        bool result = ccc -> subq -> erase_loc( ccc -> loc );
        ccc -> subq = & newsubq;
        ccc -> loc
            = ccc -> subq -> insert( new_weight, SatLoc( ccc -> sat, spqloc ));
        return result;
    }



    Loc_tp low_energy_sample() const
    {
        const bool alwaysland_empty = m_always.is_empty();
        if ( alwaysland_empty && m_sometimes.is_empty() )
        {
            return BAD_LOC;
        }
        const RBT& pq( alwaysland_empty ? m_sometimes : m_always );
        Loc_tp loc( alwaysland_empty ? Loc_tp(BAD_LOC) : m_always.loc_max() );
        if ( alwaysland_empty )
        {
            // Pick, at random, a value in range (0,M)
            // where M = sum of tree's keys:
            Key_tp seek_wt = m_sometimes.root_sum() * kjb_c::kjb_rand();

            // Now find a node n such that an inorder (by key) listing of nodes
            // from smallest-keyed to n
            // has a sum of keys S equal to or barely exceeding 'seek_wt' --
            // minimal in the sense that (S - n.key) < seek_wt <= S.

            // The cumulative key sum is like the inverse CDF of the mass
            // function,
            // and selection via seek_wt is basically a transformation method
            // of sampling from the inverse CDF.
            loc = m_sometimes.loc_using_cumulative_key_sum( seek_wt );
        }
        SatLoc sl;
#ifdef TEST
        bool found =
#endif
                     pq.access_loc( loc, 00, &sl );
        KJB( ASSERT( found ) );
        return sl.spqloc;
    }


    Loc_tp loc_min() const
    {
        const bool alwaysland_empty = m_always.is_empty();
        if ( alwaysland_empty && m_sometimes.is_empty() )
        {
            return BAD_LOC;
        }
        const RBT& pq( alwaysland_empty ? m_sometimes : m_always );
        SatLoc sl;
        bool found = pq.access_loc( pq.loc_max(), 00, &sl );
        KJB( ASSERT( found ) );
        return sl.spqloc;
    }


    Loc_tp Dijkstra_extraction() const
    {
        return low_energy_sample();
        //return kjb_c::kjb_rand() < 0.5 ? low_energy_sample() : loc_min();
    }

};

}
}

#endif /* STOPRIQUE3_H_INCLUDED_PREDOEHL_UOFARIZONAVISION */