From 0cc35ad04f9c2997014d7cf62a12f697e79fb534 Mon Sep 17 00:00:00 2001 From: Arnur Nigmetov Date: Sat, 20 Jan 2018 19:11:29 +0100 Subject: Major rewrite, templatized version --- geom_matching/wasserstein/include/auction_oracle.h | 288 +-------------------- 1 file changed, 9 insertions(+), 279 deletions(-) (limited to 'geom_matching/wasserstein/include/auction_oracle.h') diff --git a/geom_matching/wasserstein/include/auction_oracle.h b/geom_matching/wasserstein/include/auction_oracle.h index ef6ec53..d285a1f 100644 --- a/geom_matching/wasserstein/include/auction_oracle.h +++ b/geom_matching/wasserstein/include/auction_oracle.h @@ -26,285 +26,15 @@ derivative works thereof, in binary and source code form. */ -#ifndef AUCTION_ORACLE_H -#define AUCTION_ORACLE_H +#ifndef HERA_AUCTION_ORACLE_H +#define HERA_AUCTION_ORACLE_H +// all oracle classes are in separate h-hpp files +// this file comprises all of them -#define USE_BOOST_HEAP +#include "auction_oracle_base.h" +#include "auction_oracle_kdtree_restricted.h" +#include "auction_oracle_kdtree_single_diag.h" +#include "auction_oracle_stupid_sparse_restricted.h" -#include -#include -#include -#include - -#ifdef USE_BOOST_HEAP -#include -#endif - -#include "basic_defs_ws.h" -#include "dnn/geometry/euclidean-fixed.h" -#include "dnn/local/kd-tree.h" - -namespace geom_ws { - -struct CompPairsBySecondStruct { - bool operator()(const IdxValPair& a, const IdxValPair& b) const - { - return a.second < b.second; - } -}; - -// -struct CompPairsBySecondGreaterStruct { - bool operator()(const IdxValPair& a, const IdxValPair& b) const - { - return a.second > b.second; - } -}; - -struct CompPairsBySecondLexStruct { - bool operator()(const IdxValPair& a, const IdxValPair& b) const - { - return a.second < b.second or (a.second == b.second and a.first > b.first); - } -}; - -struct CompPairsBySecondLexGreaterStruct { - bool operator()(const IdxValPair& a, const IdxValPair& b) const - { - return a.second > b.second or (a.second == b.second and a.first > b.first); - } -}; - -using ItemsTimePair = std::pair; - -using UpdateList = std::list; -using UpdateListIter = UpdateList::iterator; - - -#ifdef USE_BOOST_HEAP -using LossesHeap = boost::heap::d_ary_heap, boost::heap::mutable_, boost::heap::compare>; -#else -template -class IdxValHeap { -public: - using InternalKeeper = std::set; - using handle_type = typename InternalKeeper::iterator; - // methods - handle_type push(const IdxValPair& val) - { - auto resPair = _heap.insert(val); - assert(resPair.second); - assert(resPair.first != _heap.end()); - return resPair.first; - } - - void decrease(handle_type& handle, const IdxValPair& newVal) - { - _heap.erase(handle); - handle = push(newVal); - } - - void increase(handle_type& handle, const IdxValPair& newVal) - { - _heap.erase(handle); - handle = push(newVal); - - size_t size() const - { - return _heap.size(); - } - - handle_type ordered_begin() - { - return _heap.begin(); - } - - handle_type ordered_end() - { - return _heap.end(); - } - - -private: - std::set _heap; -}; - -// if we store losses, the minimal value should come first -using LossesHeap = IdxValHeap; -#endif - -struct DebugOptimalBid { - DebugOptimalBid() : bestItemIdx(-1), bestItemValue(-666.666), secondBestItemIdx(-1), secondBestItemValue(-666.666) {}; - IdxType bestItemIdx; - double bestItemValue; - IdxType secondBestItemIdx; - double secondBestItemValue; -}; - -struct AuctionOracleAbstract { - AuctionOracleAbstract(const std::vector& _bidders, const std::vector& _items, const double _wassersteinPower, const double _internal_p = std::numeric_limits::infinity()); - ~AuctionOracleAbstract() {} - virtual IdxValPair getOptimalBid(const IdxType bidderIdx) = 0; - virtual void setPrice(const IdxType itemsIdx, const double newPrice) = 0; - virtual void adjustPrices(void) = 0; - double getEpsilon() { return epsilon; }; - virtual void setEpsilon(double newEpsilon) { assert(newEpsilon >= 0.0); epsilon = newEpsilon; }; - std::vector getPrices() { return prices; } -protected: - const std::vector& bidders; - const std::vector& items; - std::vector prices; - double wassersteinPower; - double epsilon; - double internal_p; - double getValueForBidder(size_t bidderIdx, size_t itemsIdx); -}; - -struct AuctionOracleLazyHeap final : AuctionOracleAbstract { - AuctionOracleLazyHeap(const std::vector& bidders, const std::vector& items, const double wassersteinPower, const double _internal_p = std::numeric_limits::infinity()); - ~AuctionOracleLazyHeap(); - // data members - // temporarily make everything public - std::vector> weightMatrix; - //double weightAdjConst; - double maxVal; - // vector of heaps to find the best items - std::vector lossesHeap; - std::vector> lossesHeapHandles; - // methods - void fillInLossesHeap(void); - void setPrice(const IdxType itemsIdx, const double newPrice) override final; - IdxValPair getOptimalBid(const IdxType bidderIdx) override final; - double getMatchingWeight(const std::vector& biddersToItems) const; - void adjustPrices(void) override final; - // to update the queue in lazy fashion - std::vector itemsIterators; - UpdateList updateList; - std::vector biddersUpdateMoments; - int updateCounter; - void updateQueueForBidder(const IdxType bidderIdx); - // debug - DebugOptimalBid getOptimalBidDebug(const IdxType bidderIdx); -}; - -struct AuctionOracleLazyHeapRestricted final : AuctionOracleAbstract { - AuctionOracleLazyHeapRestricted(const std::vector& bidders, const std::vector& items, const double wassersteinPower, const double _internal_p = std::numeric_limits::infinity()); - ~AuctionOracleLazyHeapRestricted(); - // data members - // temporarily make everything public - std::vector> weightMatrix; - //double weightAdjConst; - double maxVal; - // vector of heaps to find the best items - std::vector lossesHeap; - std::vector> itemsIndicesForHeapHandles; - std::vector> lossesHeapHandles; - // methods - void fillInLossesHeap(void); - void setPrice(const IdxType itemsIdx, const double newPrice) override final; - IdxValPair getOptimalBid(const IdxType bidderIdx) override final; - double getMatchingWeight(const std::vector& biddersToItems) const; - void adjustPrices(void) override final; - // to update the queue in lazy fashion - std::vector itemsIterators; - UpdateList updateList; - std::vector biddersUpdateMoments; - int updateCounter; - void updateQueueForBidder(const IdxType bidderIdx); - LossesHeap diagItemsHeap; - std::vector diagHeapHandles; - std::vector heapHandlesIndices; - // debug - - DebugOptimalBid getOptimalBidDebug(const IdxType bidderIdx); - - // for diagonal points - bool bestDiagonalItemsComputed; - size_t bestDiagonalItemIdx; - double bestDiagonalItemValue; - size_t secondBestDiagonalItemIdx; - double secondBestDiagonalItemValue; -}; - -struct AuctionOracleKDTree final : AuctionOracleAbstract { - typedef dnn::Point<2, double> DnnPoint; - typedef dnn::PointTraits DnnTraits; - - AuctionOracleKDTree(const std::vector& bidders, const std::vector& items, const double wassersteinPower, const double _internal_p = std::numeric_limits::infinity()); - ~AuctionOracleKDTree(); - // data members - // temporarily make everything public - double maxVal; - double weightAdjConst; - dnn::KDTree* kdtree; - std::vector dnnPoints; - std::vector dnnPointHandles; - dnn::KDTree* kdtreeAll; - std::vector dnnPointsAll; - std::vector dnnPointHandlesAll; - LossesHeap diagItemsHeap; - std::vector diagHeapHandles; - std::vector heapHandlesIndices; - std::vector kdtreeItems; - // vector of heaps to find the best items - void setPrice(const IdxType itemsIdx, const double newPrice) override final; - IdxValPair getOptimalBid(const IdxType bidderIdx) override final; - void adjustPrices(void) override final; - // debug routines - DebugOptimalBid getOptimalBidDebug(IdxType bidderIdx); - void setEpsilon(double newVal) override final; -}; - -struct AuctionOracleKDTreeRestricted final : AuctionOracleAbstract { - typedef dnn::Point<2, double> DnnPoint; - typedef dnn::PointTraits DnnTraits; - - AuctionOracleKDTreeRestricted(const std::vector& bidders, const std::vector& items, const double wassersteinPower, const double _internal_p = std::numeric_limits::infinity()); - ~AuctionOracleKDTreeRestricted(); - // data members - // temporarily make everything public - double maxVal; - double weightAdjConst; - dnn::KDTree* kdtree; - std::vector dnnPoints; - std::vector dnnPointHandles; - std::vector dnnPointsAll; - std::vector dnnPointHandlesAll; - LossesHeap diagItemsHeap; - std::vector diagHeapHandles; - std::vector heapHandlesIndices; - std::vector kdtreeItems; - // vector of heaps to find the best items - void setPrice(const IdxType itemsIdx, const double newPrice) override final; - IdxValPair getOptimalBid(const IdxType bidderIdx) override final; - void adjustPrices(void) override final; - // debug routines - DebugOptimalBid getOptimalBidDebug(IdxType bidderIdx); - void setEpsilon(double newVal) override final; - - - bool bestDiagonalItemsComputed; - size_t bestDiagonalItemIdx; - double bestDiagonalItemValue; - size_t secondBestDiagonalItemIdx; - double secondBestDiagonalItemValue; -}; - -struct AuctionOracleRestricted final : AuctionOracleAbstract { - AuctionOracleRestricted(const std::vector& bidders, const std::vector& items, const double wassersteinPower, const double _internal_p = std::numeric_limits::infinity()); - IdxValPair getOptimalBid(const IdxType bidderIdx) override; - void setPrice(const IdxType itemsIdx, const double newPrice) override; - void adjustPrices(void) override {}; - void setEpsilon(double newEpsilon) override { assert(newEpsilon >= 0.0); epsilon = newEpsilon; }; - // data - std::vector> weightMatrix; - double maxVal; - constexpr static bool isRestricted = true; -}; - -std::ostream& operator<< (std::ostream& output, const DebugOptimalBid& db); - -} // end of namespace geom_ws - -#endif +#endif // HERA_AUCTION_ORACLE_H -- cgit v1.2.3