source: GTP/trunk/Lib/Vis/Preprocessing/src/HashPvs.h @ 2199

#ifndef __HASHPVS_H
#define __HASHPVS_H

//#include <hash_set>
#include "common.h"
#include <math.h>
#include "PvsBase.h"
#include "google/dense_hash_set"
#include "google/dense_hash_map"


namespace GtpVisibilityPreprocessor {


/*template<typename T>
struct my_hash_compare
{
   enum
   {
      bucket_size = 1,
      min_buckets = 16
   };

   int operator()(int a) const
   {
           return a;
   }


   bool operator()(T a, T b) const
   {
      return a < b;
   }
};*/


//#define HASH_SET google::dense_hash_set<T, my_hash_compare<T> >
#define HASH_SET google::dense_hash_map<int, T>//, hash_compare<int> >
//#define HASH_SET stdext::hash_set<T, my_hash_compare<T> >
#define HASH_ITERATOR HASH_SET::iterator
#define CONST_HASH_ITERATOR HASH_SET::const_iterator

/** Iterator over a hash pvs.
*/
template<typename T, typename S>
class HashPvsIterator
{
public:
        
        HashPvsIterator<T, S>() {}

        HashPvsIterator<T, S>(const typename CONST_HASH_ITERATOR &itCurrent,
                                                  const typename CONST_HASH_ITERATOR &itEnd):
        mItCurrent(itCurrent), mItEnd(itEnd)
        {
        }

        bool HasMoreEntries() const 
        {
                return (mItCurrent != mItEnd);
        }

        T Next(S &pdf)
        {
                T sample = (*mItCurrent).second;
                ++ mItCurrent;

                return sample;
        }

        T Next()
        {
                T sample = (*mItCurrent).second;
                ++ mItCurrent;

                return sample;
        }
        
private:
        typename CONST_HASH_ITERATOR mItCurrent;
        typename CONST_HASH_ITERATOR mItEnd;
};


/** Template class representing the Potentially Visible Set (PVS) 
        mainly from a view cell, but also e.g., from objects.
*/
template<typename T, typename S>
class HashPvs//: public PvsBase<T>
{
        template<typename T, typename S> friend class HashPvsIterator;

public:

        HashPvs()//: mEntries(1009)
        {
                 mEntries.set_deleted_key(-1);
                 mEntries.set_empty_key(-2);
        };
        //virtual ~HashPvs() {};

        int GetSize() const;
        bool Empty() const;

        /** Adds sample to PVS.
                @returns contribution of sample (0 or 1)
        */
        float AddSample(T sample, const float pdf);

        /** Adds sample to PVS without checking for presence of the sample
                warning: pvs remains unsorted!
        */
        void AddSampleDirty(T sample, const float pdf);

        /** Adds sample dirty (on the end of the vector) but
                first checks if sample is already in clean part of the pvs.
        */
        bool AddSampleDirtyCheck(T sample, const float pdf);

        /** Sort pvs entries - this should always be called after a
                sequence of AddSampleDirty calls 
        */
        void Sort();

        /** Clears the pvs.
        */
        void Clear(const bool trim = true);

        bool IsDirty() const;

        inline bool RequiresResort() const;

        /** Finds sample in PVS.
                @param checkDirty if dirty part of the pvs should be checked for entry 
                (warning: linear runtime in dirty part)
                @returns iterator on the sample if found, else the place where 
                it would be added in the sorted vector.
        */
        inline bool Find(T sample, typename HASH_ITERATOR &it);

        typename HashPvsIterator<T, S> GetIterator() const;

        /** Compute continuous PVS difference 
        */
        float GetPvsHomogenity(HashPvs<T, S> &pvs);

        static void Merge(HashPvs<T, S> &mergedPvs, 
                                          const HashPvs<T, S> &a, 
                                          const HashPvs<T, S> &b);

        static int GetEntrySizeByte(); 
        static float GetEntrySize();

        bool GetSampleContribution(T sample,
                                                   const float pdf,
                                                           float &contribution);

        int GetSamples() const
        {
                return mSamples;
        }

        void MergeInPlace(const HashPvs<T, S> &a)
        {
                cerr << "not implemented yet" << endl;
        }

        bool RequiresResortLog() const
        {
                return false;
        }

        void Reserve(const int n) 
        { 
                // not necessary
        }

        /** Sort pvs entries assume that the pvs contains unique entries
        */
        void SimpleSort()
        {
                // not necessary
        }

        int SubtractPvs(const HashPvs<T, S> &pvs)
        {
                cerr << "not yet implemented" << endl;
                return 0;
        }

        /** Compute continuous PVS difference 
        */
        void ComputeContinuousPvsDifference(HashPvs<T, S> &pvs, 
                                                                                float &pvsReduction,
                                                                                float &pvsEnlargement)
        {
                cerr << "not yet implemented" << endl;
        }
protected:

        /// hash table of PVS entries
        HASH_SET mEntries; 

        /// Number of samples used to create the PVS
        int mSamples;
};


template <typename T, typename S>
bool HashPvs<T, S>::Find(T sample, typename HASH_ITERATOR &it)
{
        it = mEntries.find(sample->GetId());

        // already in map
        return (it != mEntries.end());
}


template <typename T, typename S>
int HashPvs<T, S>::GetSize() const
{
        return (int)mEntries.size();
}


template <typename T, typename S>
bool HashPvs<T, S>::Empty() const
{
        return mEntries.empty();
}


template <typename T, typename S>
float HashPvs<T, S>::AddSample(T sample, const float pdf)
{
        static HASH_ITERATOR it;

        if (Find(sample, it))
                return 0.0f;
        
        mEntries.insert(pair<int, T>(sample->GetId(), sample));
        return 1.0f;
}
        

template <typename T, typename S>
void HashPvs<T, S>::AddSampleDirty(T sample, const float pdf)
{
        static HASH_ITERATOR it;

        // not yet in map
        if (!Find(sample, it))
        {
                mEntries.insert(pair<int, T>(sample->GetId(), sample));
        }
}


template <typename T, typename S>
bool HashPvs<T, S>::AddSampleDirtyCheck(T sample, 
                                                                                const float pdf)
{
        static pair<HASH_ITERATOR, bool> result;
        result = mEntries.insert(pair<int, T>(sample->GetId(), sample));
        return result.second;

        /*
        static CONST_HASH_ITERATOR it;

        it = mEntries.find(sample->GetId());//, sample);

        // already in map
        const bool found = (it != mEntries.end());

        //return false;
        // already in map
        if (found)
        //if (Find(pair<int, T>(sample->GetId(), sample), it))
                return false;

        mEntries.insert(pair<int, T>(sample->GetId(), sample));
        
        return true;*/
}


template <typename T, typename S>
void HashPvs<T, S>::Sort()
{
}


template <typename T, typename S>
void HashPvs<T, S>::Clear(const bool trim = true)
{
        mEntries.clear();
}


template <typename T, typename S>
bool HashPvs<T, S>::IsDirty() const
{
        return false;
}


template <typename T, typename S>
bool HashPvs<T, S>::RequiresResort() const
{
        return false;
}


template <typename T, typename S>
typename HashPvsIterator<T, S> HashPvs<T, S>::GetIterator() const
{
        HashPvsIterator<T, S> pit(mEntries.begin(), mEntries.end());

        return pit;
}


template <typename T, typename S>
float HashPvs<T, S>::GetEntrySize()
{
        return (float)(sizeof(T)) / float(1024 * 1024);
}


template <typename T, typename S>
int HashPvs<T, S>::GetEntrySizeByte()
{
        return sizeof(T);
}


template <typename T, typename S>
float HashPvs<T, S>::GetPvsHomogenity(HashPvs<T, S> &pvs) 
{
        float pvsReduction, pvsEnlargement;

        ComputeContinuousPvsDifference(pvs,     pvsReduction, pvsEnlargement);

        return pvsReduction + pvsEnlargement;
}


template <typename T, typename S>
bool HashPvs<T, S>::GetSampleContribution(T sample,
                                                                          const float pdf,
                                                                          float &contribution) 
{
        HASH_SET::iterator it;
        const bool entryFound = Find(sample, it);

        if (entryFound)  
        {
                contribution = 0.0f;
                return false;
        }
        else 
        {
                contribution = 1.0f;
                return true;
        }
}


template <typename T, typename S>
void HashPvs<T, S>::Merge(HashPvs<T, S> &mergedPvs, 
                                                  const HashPvs<T, S> &a, 
                                                  const HashPvs<T, S> &b)
{
        CONST_HASH_ITERATOR ait, ait_end = a.mEntries.end();

        for (ait = a.mEntries.begin(); ait != ait_end; ++ ait)
        {
                mergedPvs.AddSample((*ait).second, 1.0f);
        }

        CONST_HASH_ITERATOR bit, bit_end = b.mEntries.end();

        for (bit = b.mEntries.begin(); bit != bit_end; ++ bit)
        {
                mergedPvs.AddSample((*bit).second, 1.0f);
        }
}

}

#endif