MutablePriorityQueueT.hh 2.89 KB
Newer Older
David Bommes's avatar
David Bommes committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//=============================================================================
//
//  CLASS MutablePriorityQueue
//
//=============================================================================


#ifndef COMISO_MUTABLEPRIORITYQUEUET_HH
#define COMISO_MUTABLEPRIORITYQUEUET_HH


//== INCLUDES =================================================================

//== FORWARDDECLARATIONS ======================================================

//== NAMESPACES ===============================================================

namespace COMISO {

//== CLASS DEFINITION =========================================================

	      

/** \class MutablePriorityQueue MutablePriorityQueue.hh 

    Brief Description.
  
    A more elaborate description follows.
*/


// Helper Class for sorting triples
template<class A, class B, class C>
class Triple
{
public: 

  // default constructor
  Triple() {}
  Triple(const A& _a, const B& _b, const C& _c) : first(_a), second(_b), third(_c) {}

  bool operator<(const Triple& _t) const
  { return (  this->first <  _t.first || 
	      (this->first == _t.first && ( this->second <  _t.second || 
					    ( this->second == _t.second && this->third < _t.third))));}
	
  void print_info()
  { std::cerr << first << " " << second << " " << third << std::endl; }

  A first;
  B second;
  C third;
};

template<class VType, class IType>
class MutablePriorityQueueT
{
public:


  typedef Triple<VType,IType,unsigned int> TripleVII;
   
  /// Default constructor
  MutablePriorityQueueT() {}
 
  /// Destructor
  ~MutablePriorityQueueT() {}

  // reset timestamps
Max Lyon's avatar
Max Lyon committed
70
  void clear(size_t _n)
David Bommes's avatar
David Bommes committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
  {
    timestamp_.clear();
    timestamp_.resize(_n,0);
  }

  // update value of index _id
  void update(const IType& _id, const VType& _value)
  {
    queue_.insert( TripleVII(_value,_id, ++timestamp_[_id]));
  }

  // get index of next element4
  IType get_next()
  {
    while(!queue_.empty())
    {
      // get and delete first element
      TripleVII tri = *queue_.begin();
      queue_.erase(queue_.begin());

      // if valid -> return
      if( timestamp_[tri.second] == tri.third)
	return tri.second;
    }

    // if empty return dummy
    return IType(0);
  }


  // priority queue empty?
  bool empty()
  {
    while(!queue_.empty())
    {
      // get and delete first element
      TripleVII tri = *queue_.begin();
      
      // if valid -> return true
      if( timestamp_[tri.second] == tri.third)
	return false;

      queue_.erase(queue_.begin());
    }
    return true;
  }
  
private:

  // timestamps
  std::vector<unsigned int> timestamp_;

  // priority queue
  std::set<TripleVII> queue_;
};


//=============================================================================
} // namespace COMISO
//=============================================================================
#endif // COMISO_MUTABLEPRIORITYQUEUET_HH defined
//=============================================================================