src/removeoverlap/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 class Variable;
  20 class Constraint;
  21 template <class T> class PairingHeap;
  22 class StupidPriorityQueue;
  23
  24 class Block
  25 {
  26         friend std::ostream& operator <<(std::ostream &os,const Block &b);
  27 public:
  28         std::vector<Variable*> *vars;
  29         double posn;
  30         double weight;
  31         double wposn;
  32         Block(Variable *v=NULL);
  33         ~Block(void);
  34         Constraint* findMinLM();
  35         Constraint* findMinLMBetween(Variable* lv, Variable* rv);
  36         Constraint* findMinInConstraint();
  37         Constraint* findMinOutConstraint();
  38         void deleteMinInConstraint();
  39         void deleteMinOutConstraint();
  40         double desiredWeightedPosition();
  41         void merge(Block *b, Constraint *c, double dist);
  42         void merge(Block *b, Constraint *c);
  43         void mergeIn(Block *b);
  44         void mergeOut(Block *b);
  45         void split(Block *&l, Block *&r, Constraint *c);
  46         Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
  47         void setUpInConstraints();
  48         void setUpOutConstraints();
  49         double cost();
  50         bool deleted;
  51         long timeStamp;
  52         PairingHeap<Constraint*> *in;
  53         PairingHeap<Constraint*> *out;
  54 private:
  55         typedef enum {NONE, LEFT, RIGHT} Direction;
  56         typedef std::pair<double, Constraint*> Pair;
  57         void reset_active_lm(Variable *v, Variable *u);
  58         double compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm);
  59         Pair compute_dfdv_between(
  60                         Variable*, Variable*, Variable*, Direction, bool);
  61         bool canFollowLeft(Constraint *c, Variable *last);
  62         bool canFollowRight(Constraint *c, Variable *last);
  63         void populateSplitBlock(Block *b, Variable *v, Variable *u);
  64         void addVariable(Variable *v);
  65         void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
  66 };
  67
  68 #endif // SEEN_REMOVEOVERLAP_BLOCK_H