Src/DasherCore/ExpansionPolicy.h

   1 /*
   2  *  ExpansionPolicy.h
   3  *  Dasher
   4  *
   5  *  Created by Alan Lawrence on 03/06/2009.
   6  *  Copyright 2009 Cavendish Laboratory. All rights reserved.
   7  *
   8  */
   9
  10 #ifndef __ExpansionPolicy_h__
  11 #define __ExpansionPolicy_h__
  12
  13 #include <vector>
  14 #include <queue>
  15 #include <limits>
  16 #include <algorithm>
  17 #include "DasherNode.h"
  18
  19 class CNodeCreationManager;
  20
  21 namespace Dasher {
  22   class CDasherModel;
  23 class CExpansionPolicy
  24 {
  25 public:
  26   virtual ~CExpansionPolicy() = default;
  27   ///dMaxCost should be the value returned by pushNode from the call for the node most closely enclosing pNode (that was pushed!)
  28   ///for the first (outermost) node, i.e. when no enclosing node has been passed, (+ive) INFINITY should be passed in.
  29         virtual double pushNode(CDasherNode *pNode, int iDasherMinY, int iDasherMaxY, bool bExpand, double dMaxCost)=0;
  30   ///Return TRUE if another frame should be forced.
  31   virtual bool apply()=0;
  32   ///Expand node immediately (do not wait for a call to apply()) - subclasses may use
  33   /// to implement their apply() methods, but public so the view can call directly for nodes
  34   /// which must be expanded during rendering. (Delegates to CDasherModel.)
  35   void ExpandNode(CDasherNode *pNode);
  36 protected:
  37   CExpansionPolicy(CDasherModel *pModel) : m_pModel(pModel) {}
  38 private:
  39   CDasherModel *m_pModel;
  40 };
  41
  42 class NoExpansions : public CExpansionPolicy
  43 {
  44 public:
  45   NoExpansions() = default;
  46   ~NoExpansions() override = default;
  47         double pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dMaxCost) override {return dMaxCost;}
  48   bool apply() override {return false;}
  49 };
  50
  51 ///A policy that expands/collapses nodes to maintain a given node budget.
  52 ///Also ascribes uniform costs, according to size within the range 0-4096.
  53 class BudgettingPolicy : public CExpansionPolicy
  54 {
  55 public:
  56   BudgettingPolicy(CDasherModel *pModel, unsigned int iNodeBudget);
  57   ~BudgettingPolicy() override = default;
  58   ///sets cost according to getCost(pNode,iMin,iMax);
  59   ///then assures node is cheaper (less important) than its parent;
  60   ///then adds to relevant queue
  61   double pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dParentCost) override;
  62   bool apply() override;
  63 protected:
  64   virtual double getCost(CDasherNode *pNode, int iDasherMinY, int iDasherMaxY);
  65   ///return the intersection of the ranges (y1-y2) and (iMin-iMax)
  66   int getRange(int y1, int y2, int iMin, int iMax);
  67   std::vector<std::pair<double,CDasherNode *> > sExpand, sCollapse;
  68   unsigned int m_iNodeBudget;
  69 };
  70
  71 ///limits expansion to a few nodes (per instance i.e. per frame)
  72 ///(collapsing is at present unlimited, have to test this...)
  73 class AmortizedPolicy : public BudgettingPolicy
  74 {
  75 public:
  76   AmortizedPolicy(CDasherModel *pModel, unsigned int iNodeBudget);
  77         AmortizedPolicy(CDasherModel *pModel, unsigned int iNodeBudget, unsigned int iMaxExpands);
  78   ~AmortizedPolicy() override = default;
  79   bool apply() override;
  80   double pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dParentCost) override;
  81 private:
  82         unsigned int m_iMaxExpands;
  83   void trim();
  84 };
  85 }
  86 #endif /*defined __ExpansionPolicy_h__*/