attributeIndexingFeatureSet.h

Go to the documentation of this file.

/******************************************************************************
 * Copyright (c) 2015 MAK Technologies, Inc.
 * All rights reserved.
 ******************************************************************************/


#pragma once

#include <features/featuresDefines.h>
#include <features/feature.h>
#include <features/featureSet.h>
#include <features/featureSetList.h>
#include <features/featureSetWrappers.h>
#include <features/tileFeature.h>

#include <vrfutil/terrainInterfaceConfig.h>

#include <atomic>

#include <boost/optional.hpp>

namespace MAKVRinTerra
{
   template <typename FS, typename S = typename FS::Sink>
   class DtAttributeIndexingFeatureSet
      : public FS
      , public std::enable_shared_from_this<DtAttributeIndexingFeatureSet<FS,S> >
   {
   protected:
      class Subtile;
   
   public:
      typedef std::shared_ptr<DtAttributeIndexingFeatureSet>       Ptr;
      typedef std::shared_ptr<const DtAttributeIndexingFeatureSet> CPtr;
      typedef std::weak_ptr<DtAttributeIndexingFeatureSet>         WPtr;

      typedef typename FS::Feature         Feature;
      typedef typename FS::ForEachFunction ForEachFunction;
      typedef typename FS::LoadedCallback  LoadedCallback;
      typedef typename FS::DetachCallback  DetachCallback;

      typedef S                  Sink;
      typedef typename Sink::Ptr SinkPtr;

      typedef std::string Bound;

      class Config : public DtTerrainInterfaceConfig
      {
      public:
         typedef std::shared_ptr<Config> Ptr;

         explicit Config(FS* input, const DtFeature::Key& key)
            : inputSink(Sink::Make(input)), indexKey(key) { }
         explicit Config(const SinkPtr& input, const DtFeature::Key& key)
            : inputSink(input ? input : Sink::Make(0)), indexKey(key) { }

         explicit Config(const Config& cfg)
            : inputSink(cfg.inputSink)
            , indexKey(cfg.indexKey)
         {
            static_cast<DtTerrainInterfaceConfig&>(*this) = cfg;
         }

         const SinkPtr inputSink;
         const DtFeature::Key indexKey;
      };

      static FS* Make(Config* cfg, const Bound& lower=Bound(), const Bound& upper=Bound())
      {
         return Make(typename Config::Ptr(cfg), lower, upper);
      }

      static FS* Make(
         const typename Config::Ptr& cfg,
         Bound lower=Bound(), Bound upper=Bound())
      {
         if (lower.empty()) lower = " ";
         if (upper.empty()) upper = "~";

         Ptr set(new DtAttributeIndexingFeatureSet(cfg, lower, upper));
         set->init();

         return FS::Wrap(set);
      }

      FS* clone() const
      {
         return FS::Wrap(this->shared_from_this());
      }

      std::string label() const
      {
         return myConfig->inputSink->label() + " index level " 
            + boost::lexical_cast<std::string>(myLevel);
      }

      bool loaded(double timeout) const
      {
         return myFeatures->loaded(timeout);
      }

      DetachCallback addLoadedCallback(const LoadedCallback& cb) const
      {
         return myFeatures->addLoadedCallback(cb);
      }

      unsigned numberOfFeatures() const
      {
         return myFeatures->numberOfFeatures();
      }

      bool elided() const
      {
         return myFeatures->elided();
      }

      bool empty() const
      {
         return myFeatures->empty();
      }

      class QueryVisitor : public DtQuery::Visitor<DtQuery>
      {
      public:
         explicit QueryVisitor(const DtFeature::Key& key, const Subtile& subtile)
            : attribute(key)
            , subtile(subtile)
         {
         }

         virtual DtQuery visit(const DtQuery& query) override
         {
            if (const DtHasAttribute* i = query.trycast<DtHasAttribute>())
            {
               if (i->key() != attribute)
                  return query;

               const DtHasAttributeValue* val = query.trycast<DtHasAttributeValue>();

               if (!val)
                  return query;

               DtQuery mlower = DtHasAttributeValue::Merge(*val, subtile.lowerBoundQuery());
               if (mlower.isFalse())
                  return false;

               DtQuery mupper = DtHasAttributeValue::Merge(*val, subtile.upperBoundQuery());
               if (mupper.isFalse())
                  return false;
            }

            return query;
         }

      private:
         DtFeature::Key attribute;
         const Subtile& subtile;
      };

      FS* filter(
         const DtQuery& query,
         const boost::optional<DtFeatureGeometry>& geometry,
         DtLoadType load) const
      {
         if (load == DO_NOT_LOAD)
            return new typename FS::Filtered(FS::Wrap(this->shared_from_this()), query, geometry);

         if (query.isTrue())
            return myFeatures->filter(true, geometry, load);

         if (myState != ACTIVE)
            return myFeatures->filter(query, geometry, load);

         bool covers[2] = { false, false };
         bool intersections[2] = { false, false };
         size_t lastIntersection = 0;
         unsigned numIntersects = 0;

         for (unsigned i=0 ; i < 2; ++i)
         {
            QueryVisitor visitor(myConfig->indexKey, this->getSubtile(i));
            DtQuery processed = visitor.apply(query);
            if (processed.isFalse())
               continue;

            intersections[i] = true;
            lastIntersection = i;
            ++numIntersects;

         }

         switch (numIntersects)
         {
         case 0:  return 0;
         case 1:  return getSubtile(lastIntersection).indexedFeatures().filter(
                     !covers[lastIntersection] ? query : true,
                     geometry,
                     load);
         }

         std::unique_ptr< DtFeatureSetList<FS> > list(new DtFeatureSetList<FS>(4));
         for (size_t i=0; i != 4; ++i)
         {
            if (!intersections[i])
               continue;

            list->add(getSubtile(i).indexedFeatures().filter(
               !covers[i] ? query : true,
               geometry,
               load));
         }

         return list.release();
      }

      void forEachFeatureParallel(const ForEachFunction& func) const
      {
         myFeatures->forEachFeatureParallel(func);
      }

      DetachCallback forEachFeatureAsync(const ForEachFunction& func) const
      {
         return myFeatures->forEachFeatureAsync(func);
      }

   protected:
      DtAttributeIndexingFeatureSet(const Ptr& parent, const Subtile& subtile)
         : myConfig(parent->myConfig)
         , myLevel(parent->myLevel + 1)
         , myParent(parent)
         , myFeatures(subtile.sink())
         , mySubtile0(*myFeatures, myConfig->indexKey, subtile.lowerBound(), subtile.upperBound(), 0)
         , mySubtile1(*myFeatures, myConfig->indexKey, subtile.lowerBound(), subtile.upperBound(), 1)
      {
         myState = START;
      }

      DtAttributeIndexingFeatureSet(
         const std::shared_ptr<Config>& cfg,
         const Bound& lower, const Bound& upper)
         : myConfig(cfg)
         , myLevel(0)
         , myFeatures(cfg->inputSink)
         , mySubtile0(*myFeatures, myConfig->indexKey, lower, upper, 0)
         , mySubtile1(*myFeatures, myConfig->indexKey, lower, upper, 1)
      {
         myState = START;
      }

      const Subtile& getSubtile(unsigned i) const
      {
         switch (i)
         {
         case 0: return mySubtile0;
         case 1: return mySubtile1;
         }

         assert(false);
         DtTHROW_NEW(DtException, "Tile index out of bounds");
      }

      void init()
      {
         Ptr This(this->shared_from_this());
         
         mySubtile0.init(This);
         mySubtile1.init(This);
      }

      bool activateSubtiles()
      {
         auto expected = START;
         if (!myState.compare_exchange_strong(expected, ACTIVATING))
            return false;

         try
         {
            Ptr This(this->shared_from_this());
            mySubtile0.activate(This);
            mySubtile1.activate(This);
         }
         catch (...)
         {
            myState = FAULT;
            throw;
         }

         expected = ACTIVATING;
         if (!myState.compare_exchange_strong(expected, ACTIVE))
         {
            DtWarn << "Error activating subtile" << std::endl;
            myState = FAULT;
            return false;
         }

         return true;
      }

      const std::shared_ptr<Config> myConfig;

      const int myLevel;

      const WPtr myParent;

      SinkPtr myFeatures;

      class Subtile
      {
         static std::string removePrefix(std::string& s1, std::string& s2)
         {
            assert(s1 < s2);

            std::string prefix;
            while (!s1.empty() && !s2.empty() && s1[0] == s2[0])
            {
               prefix.push_back(s1[0]);

               s1 = s1.substr(1);
               s2 = s2.substr(1);
            }

            assert(s1 < s2);
            return prefix;
         }

         static std::string findMiddle(const std::string& lower, const std::string& upper)
         {
            using namespace std;

            string s1=lower, s2=upper;

            string prefix = removePrefix(s1, s2);
            char c1 = s1.empty() ? ' ' : s1[0];
            char c2 = s2.empty() ? '~' : s2[0];

            assert(c1 < c2);

            string ret;
            if (c1 + 1 == c2)
            {
               ret = prefix + c1 + "z";
            }
            else
            {
               int middle = (c1+c2)/2;
               ret = prefix + static_cast<char>(middle);
            }

            assert(lower <= ret);
            assert(ret < upper);

            //DtWarn << "[" << prefix << s1 << "," << prefix << s2 << "] -> " << prefix << std::endl;
            return ret;
         }

         static DtQuery makeQuery(
            const DtFeature::Key& indexKey, const Bound& bound, 
            DtHasAttributeValue::Comparison comp)
         {
            return DtHasAttributeValue::Create(indexKey, bound, comp);
         }
         
         std::shared_ptr<DtAttributeIndexingFeatureSet> myIndexingSet;
         Bound myLowerBound;
         DtQuery myLowerBoundQuery;
         Bound myUpperBound;
         DtQuery myUpperBoundQuery;
         DtQuery myQuery;
         SinkPtr mySink;

      public:
         const DtQuery& query() const          { return myQuery; }
         const DtHasAttributeValue& lowerBoundQuery() const { return *myLowerBoundQuery.trycast<DtHasAttributeValue>(); }
         const DtHasAttributeValue& upperBoundQuery() const { return *myUpperBoundQuery.trycast<DtHasAttributeValue>(); }
         const Bound& upperBound() const   { return myUpperBound; }
         const Bound& lowerBound() const   { return myLowerBound; }
         const SinkPtr& sink() const       { return mySink; }
         const FS& indexedFeatures() const { return *myIndexingSet; }

         Subtile(
            const Sink& parentFeatures,
            const DtFeature::Key& indexKey,
            const Bound& plower, const Bound& pupper,
            unsigned i)
             : myLowerBound(i == 0 ? plower : findMiddle(plower, pupper))
             , myLowerBoundQuery(makeQuery(indexKey, myLowerBound, DtHasAttributeValue::GreaterEqual))
             , myUpperBound(i == 1 ? pupper : findMiddle(plower, pupper))
             , myUpperBoundQuery(makeQuery(indexKey, myUpperBound, DtHasAttributeValue::Less))
             , myQuery(myLowerBoundQuery && myUpperBoundQuery)
             , mySink(Sink::Make(parentFeatures, query()))
         {
            DtWarn << "Level " << i << ": " << plower
               << " -> " << pupper
               << " query " << query()
               << std::endl;
         }

         void init(const Ptr& parent)
         {
            Caller caller(parent, *this);
            mySink->addLoadedCallback(caller);

            checkIndex(*parent);
         }

         void activate(const Ptr& parent)
         {
            myIndexingSet.reset(new DtAttributeIndexingFeatureSet(parent, *this));
            myIndexingSet->init();
         }

      private:
         void checkIndex(DtAttributeIndexingFeatureSet& parent)
         {
            try
            {
               if (!mySink->loaded())
                  return;
            }
            catch (DtFeatureSetLoadingException&)
            {
               return;
            }

            if (parent.myLevel >= parent.myConfig->featuresMaxIndexLOD)
               return;

            size_t pc = parent.numberOfFeatures();
            size_t c = mySink->numberOfFeatures();

            assert(pc >= c);

            if (pc <= parent.myConfig->minFeaturesToIndexTile)
               return;

            //if (c > 0)
            if (c > 10)
            {
               //if (pc/(double)c >= parent.myConfig->featuresIndexRatio)
                  parent.activateSubtiles();
            }
            else
            {
               //if (pc > 0)
            }
         }

         class Caller
         {
         public:
            explicit Caller(const Ptr& set, Subtile& subtile)
               : set(set), subtile(subtile)
            {
            }

            void operator()() const
            {
               Ptr p(set.lock());
               if (p)
                  subtile.checkIndex(*p);
            }

         private:
            WPtr set;
            Subtile& subtile;
         };
      };

      friend class Subtile;

      Subtile mySubtile0;
      Subtile mySubtile1;

      enum State
      {
         START, ACTIVATING, ACTIVE, FAULT
      };

      std::atomic<State> myState;
   };
}