UT/UT_PriorityQueue.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.
 *
 * Produced by:
 *      Neil
 *      Side Effects Software Inc.
 *      20 Maud St.
 *      Toronto, Ontario,  M5V 2M5
 *      Canada
 *      416-366-4607
 *
 * NAME:        Utility Library (C++)
 *
 * COMMENTS:
 *      This is a class template that implements a resizable array of 
 *      arbitrary objects. The template parameter represents the type
 *      of object, and is called utPtr. You can instantiate this class
 *      with any object or pointer, such as:
 *              UT_PtrArray<GeoPoint*>          pObj;
 *      The utCompare class should be a class with a very simple constructor
 *      which provides a single method "isLess" which compares two utPtr's.
 */

#ifndef __UT_PriorityQueue_h__
#define __UT_PriorityQueue_h__

#include "UT_RefArray.h"


template <class utPtr, class utCompare, bool need_changed_position>
class UT_PriorityQueue
{

public:
    // Trivial constructor and destructor:
    explicit UT_PriorityQueue(unsigned int sz=0) 
        : myArray(sz) 
    { }
    virtual ~UT_PriorityQueue() {}

    // Copy constructor that uses operator '=' to assign each of a's Things
    // to this array.
    UT_PriorityQueue(const UT_PriorityQueue<utPtr, utCompare,
                    need_changed_position> &a) : myArray(a.myArray) { }

    unsigned int        insert(utPtr t)
                        {
                            unsigned int        temp;
                            temp = myArray.append(t);
                            if (need_changed_position)
                                changedPosition( myArray( temp ), temp );
                            return bubbleUp( temp );
                        }


    // calls remove before destroying
    void                destroy(unsigned int entry)
                        {
                            utPtr ptr = myArray(entry);
                            remove( entry );
                            delete ptr;
                        }

    void                remove(unsigned int entry)
                        {
                            if( myArray.entries()>1 )
                            {
                                myArray( entry ) = myArray.last();
                                if (need_changed_position)
                                    changedPosition( myArray( entry ), entry );
                                myArray.entries( myArray.entries()-1 );
                                bubbleDown( entry );
                            }
                            else
                            {
                                myArray.entries( 0 );
                            }
                        }

    unsigned int        entries(void) const     { return myArray.entries(); }

    int64               getMemoryUsage() const
                        { return sizeof(*this) + myArray.getMemoryUsage(); }

    unsigned short      isEmpty(void) const     { return myArray.isEmpty(); }

    // make sure is queue is not empty
    utPtr               head() const { return myArray(0); };

    // In almost all cases, you only want to pull from the head of the
    // queue.  But, to make the remove(unsigned int entry) sensible,
    // you must be able to query.
    utPtr               getEntry(int idx) const { return myArray(idx); };
                    

    /*
       . allows nodes to keep track of where they are in the queue
       .. this way nodes can be placed in two queues and delete from both
       .. and allows deletiong with just a node pointer
    */
    virtual void        changedPosition( utPtr /*a*/,
                                         unsigned int /*newposition*/ ) const
                        { }

    unsigned int        bubbleDown( unsigned int entry )
                        {
                            utCompare   comp;
                            for( ;; )
                            {
                                unsigned int    l = leftChild( entry );
                                unsigned int    r = l+1;
                                unsigned int    newplace;

                                if( nodeExists( r ) )   // both children exist
                                {
                                    if( comp.isLess(myArray(entry), myArray(l)))
                                    {
                                        if (comp.isLess(myArray(l), myArray(r)))
                                            newplace = r;
                                        else
                                            newplace = l;
                                    }
                                    else if (comp.isLess(myArray(entry),
                                                         myArray(r)))
                                    {
                                        newplace = r;
                                    }
                                    else break;

                                }
                                else if( nodeExists( l ) ) // just left child
                                {
                                    if (comp.isLess(myArray(entry), myArray(l)))
                                        newplace = l;
                                    else break;
                                }
                                else    // no children
                                {
                                    break;
                                }

                                swap( entry, newplace );
                                entry = newplace;
                            }
                            return entry;
                        }

    unsigned int        bubbleUp( unsigned int entry )
                        {
                            utCompare   comp;
                            while( entry )      // while not root
                            {
                                int     nextentry = parent( entry );
                                if (!comp.isLess(myArray(entry),
                                                 myArray(nextentry)))
                                {
                                    swap( entry, nextentry );
                                    entry = nextentry;
                                }
                                else
                                {
                                    break;
                                }
                            }
                            return entry;
                        }

private:
    static unsigned int parent( unsigned int node )
                        {
                            return (node-1)>>1;
                        }

    static unsigned int leftChild( unsigned int node )
                        {
                            return (node<<1) + 1;
                        }

    static unsigned int rightChild( unsigned int node )
                        {
                            return (node<<1) + 2;
                        }

    bool                nodeExists( unsigned int node )
                        {
                            return node < myArray.entries();
                        }

    void                swap( unsigned int a, unsigned int b )
                        {
                            utPtr               temp = myArray( a );
                            myArray( a ) = myArray( b );
                            myArray( b ) = temp;

                            if (need_changed_position)
                            {
                                changedPosition( myArray( a ), a );
                                changedPosition( myArray( b ), b );
                            }
                        }

protected:
    // In almost all cases, you probably want to extract the queue in sorted
    // order.  However, some sub-classes may not require this, so we make this
    // protected so that the sub-classes can access the queue without the
    // sorting requirement (see IMG3D_Photon).
    UT_RefArray< utPtr >                myArray;
};


#endif

---