src/libvpsc/block.h

   1 /**
   2  * \brief A block is a group of variables that must be moved together to improve
   3  * the goal function without violating already active constraints.
   4  * The variables in a block are spanned by a tree of active constraints.
   5  *
   6  * Authors:
   7  *   Tim Dwyer <tgdwyer@gmail.com>
   8  *
   9  * Copyright (C) 2005 Authors
  10  *
  11  * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  12  */
  13
  14 #ifndef SEEN_REMOVEOVERLAP_BLOCK_H
  15 #define SEEN_REMOVEOVERLAP_BLOCK_H
  16
  17 #include <vector>
  18 #include <iostream>
  19 template <class T> class PairingHeap;
  20 namespace vpsc {
  21 class Variable;
  22 class Constraint;
  23
  24 class Block
  25 {
  26         typedef std::vector<Variable*> Variables;
  27         typedef std::vector<Constraint*>::iterator Cit;
  28         typedef std::vector<Variable*>::iterator Vit;
  29
  30         friend std::ostream& operator <<(std::ostream &os,const Block &b);
  31 public:
  32         Variables *vars;
  33         double posn;
  34         double weight;
  35         double wposn;
  36         Block(Variable* const v=NULL);
  37     virtual ~Block(void);
  38         Constraint* findMinLM();
  39         Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
  40         Constraint* findMinInConstraint();
  41         Constraint* findMinOutConstraint();
  42         void deleteMinInConstraint();
  43         void deleteMinOutConstraint();
  44         double desiredWeightedPosition();
  45         void merge(Block *b, Constraint *c, double dist);
  46         void merge(Block *b, Constraint *c);
  47         void mergeIn(Block *b);
  48         void mergeOut(Block *b);
  49         void split(Block *&l, Block *&r, Constraint *c);
  50         Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
  51         void setUpInConstraints();
  52         void setUpOutConstraints();
  53         double cost();
  54         bool deleted;
  55         long timeStamp;
  56         PairingHeap<Constraint*> *in;
  57         PairingHeap<Constraint*> *out;
  58         bool isActiveDirectedPathBetween(Variable* u, Variable *v);
  59 private:
  60         typedef enum {NONE, LEFT, RIGHT} Direction;
  61         typedef std::pair<double, Constraint*> Pair;
  62         void reset_active_lm(Variable* const v, Variable* const u);
  63         double compute_dfdv(Variable* const v, Variable* const u,
  64                         Constraint *&min_lm);
  65         Pair compute_dfdv_between(
  66                         Variable*, Variable* const, Variable* const,
  67                         const Direction, bool);
  68         bool canFollowLeft(Constraint *c, const Variable* const last);
  69         bool canFollowRight(Constraint *c, const Variable* const last);
  70         void populateSplitBlock(Block *b, Variable* const v, Variable* const u);
  71         void addVariable(Variable* const v);
  72         void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
  73 };
  74
  75 }
  76 #endif // SEEN_REMOVEOVERLAP_BLOCK_H