/*****************************************************************************
 * $Id: eng_sort.hh,v 1.5 2006/11/08 17:46:58 devel Exp $
 * @file
 * @author	Jim E. Brooks  http://www.jimbrooks.org
 * @brief	Class containing sorted Objects in back-to-front order.
 *//*
 * LEGAL:	COPYRIGHT (C) 2006 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE (GPL).
 *****************************************************************************/

#ifndef ENG_SORT_HH
#define ENG_SORT_HH 1

////////////////////////////////////////////////////////////////////////////////
/// Class to contain Objects sorted according to their distance from the viewplane.
/// Rendering Objects in back-to-front order is necessary for blending.
///
class Sorter
{
PREVENT_COPYING(Sorter)
public:
                Sorter( void );
            	~Sorter();
    void        Draw( void );

private:
    enum eSortCommand  // sorting can be skipped on some frames
    {
        eSortCommand_SORT,
        eSortCommand_SKIP
    };

//----
#if ENG_SORT_CC  // public to Listener*() but otherwise private
public:
#endif
    enum eSortAlgorithm  // which sort algorithm
	{
		eSortAlgorithm_QUICKSORT,  // STL vector with std::sort()
		eSortAlgorithm_TREE,       // STL multimap
	};
	static Sorter&	GetInstance( void );
	void			Disrupt( void );
	void			SetAlgorithm( eSortAlgorithm sortAlgorithm );
//----

private:
	// Object's distance and its ptr (key,val).
    class DistObj
    {
    public:
        DistObj( fp distance, ObjectPtr obj ) : mDistance(distance), mObj(obj) { }
        fp			mDistance;
        ObjectPtr	mObj;
        friend bool operator<( const DistObj& a, const DistObj& b )
        {
            return a.mDistance > b.mDistance;  // greater than
        }
    };

    // Pile sorted by tree [STL std::multimap]:
    // Specify greater<> so that the most distant Object is first.
	// Use multimap in case multiple Objects have the same distance.
	typedef std::multimap<fp,ObjectPtr,greater<fp> >  PileTree;
    typedef PileTree::iterator                        PileTreeIterator;
	ObjectPtr GetObject( PileTreeIterator itr ) { return itr->second; }

    // Pile sorted by quicksort [STL std::vector and std::sort()]:
	typedef std::vector<DistObj>     PileQuicksort;
    typedef PileQuicksort::iterator  PileQuicksortIterator;
	ObjectPtr GetObject( PileQuicksortIterator itr ) { return itr->mObj; }

private:
    bool            Sort( void );

private:
    eSortAlgorithm      mSortAlgorithm;		///< which sort algorithm
	eSortCommand		mSortCommand;		///< how to sort Objects in current frame
    PileTree            mPileTree;			///< pile of sorted Objects
	PileQuicksort  		mPileQuicksort;
	static Sorter*		msInstance;			///< TODO: per-View

};

#if ENG_SORT_CC
static void Listener_Sorter_EyeChange( EngineEvents::eEyeChange eyeChange );
static void Listener_Sorter_LocusChange( void );
static void Listener_Sorter_DynaChange( DynaPtr dyna );
static void Listener_Sorter_LodUserChange( void );
static void Listener_Sorter_VisibilityChange( void );
#endif // ENG_SORT_CC

#endif // ENG_SORT_HH
