← Back to branch summary

~tapaal-ltl/verifypn/rule-D-fix

« back to all changes in this revision

Viewing changes to PetriEngine/Structures/EnhancedPriorityQueue.h

  • Committer: Jonas Finnemann Jensen
  • Date: 2011-09-15 13:30:00 UTC
  • Revision ID: jopsen@gmail.com-20110915133000-wnywm1odf82emiuw
Import of sources from github

Show diffs side-by-side

added added

removed removed

Lines of Context:
PetriEngine/Structures/EnhancedPriorityQueue.h
 
1
/* PeTe - Petri Engine exTremE
 
2
 * Copyright (C) 2011  Jonas Finnemann Jensen <jopsen@gmail.com>,
 
3
 *                     Thomas Søndersø Nielsen <primogens@gmail.com>,
 
4
 *                     Lars Kærlund Østergaard <larsko@gmail.com>,
 
5
 * 
 
6
 * This program is free software: you can redistribute it and/or modify
 
7
 * it under the terms of the GNU General Public License as published by
 
8
 * the Free Software Foundation, either version 3 of the License, or
 
9
 * (at your option) any later version.
 
10
 * 
 
11
 * This program is distributed in the hope that it will be useful,
 
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 * GNU General Public License for more details.
 
15
 * 
 
16
 * You should have received a copy of the GNU General Public License
 
17
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
18
 */
 
19
#ifndef ENHANCEDPRIORITYQUEUE_H
 
20
#define ENHANCEDPRIORITYQUEUE_H
 
21
 
 
22
#include <assert.h>
 
23
#include <map>
 
24
#include <list>
 
25
 
 
26
namespace PetriEngine{
 
27
namespace Structures{
 
28
 
 
29
 
 
30
/** Implementation of simple priority queue, that uses double as priority
 
31
 * @remarks Lower priority is better, e.g. lowest priority comes out first!
 
32
 * Note this is the same as PriorityQueue except this one uses a map and list
 
33
 * internally, also it returns the newest item if two items have the same priority.
 
34
 */
 
35
template<class Item>
 
36
class EnhancedPriorityQueue{
 
37
private:
 
38
        typedef std::list<Item> ItemList;
 
39
        typedef std::map<double, ItemList> Queue;
 
40
        typedef typename Queue::iterator Iter;
 
41
        typedef typename Queue::const_iterator ConstIter;
 
42
        /** Underlying queue */
 
43
        Queue _queue;
 
44
        size_t _size;
 
45
public:
 
46
        EnhancedPriorityQueue(){
 
47
                clear();
 
48
        }
 
49
 
 
50
        /** Test if queue is empty */
 
51
        bool empty() const{
 
52
                return _queue.empty();
 
53
        }
 
54
 
 
55
        /** Get the size of the queue */
 
56
        size_t size() const{
 
57
                return _size;
 
58
        }
 
59
 
 
60
        /** Delete everything in the queue */
 
61
        void clear(){
 
62
                _queue.clear();
 
63
                _size = 0;
 
64
        }
 
65
 
 
66
        /** Put a new item in the queue */
 
67
        void push(double priority, const Item& item){
 
68
                _size += 1;
 
69
                Iter it = _queue.find(priority);
 
70
                if(it != _queue.end())
 
71
                        it->second.push_back(item);
 
72
                else
 
73
                        _queue.insert(std::pair<double, ItemList>(priority, ItemList(1, item)));
 
74
        }
 
75
 
 
76
        /** Pop item with lowest priority */
 
77
        Item pop(bool preferNewest = true){
 
78
                assert(_size > 0);
 
79
                _size -= 1;
 
80
                assert(_queue.begin() != _queue.end());
 
81
                Iter it = _queue.begin();
 
82
                assert(!it->second.empty());
 
83
                Item retval =  preferNewest ? it->second.back() : it->second.front();
 
84
                if(preferNewest)
 
85
                        it->second.pop_back();
 
86
                else
 
87
                        it->second.pop_front();
 
88
                if(it->second.empty())
 
89
                        _queue.erase(it);
 
90
                return retval;
 
91
        }
 
92
 
 
93
        /** Get the top most item */
 
94
        Item& top(bool preferNewest = true){
 
95
                assert(_size > 0);
 
96
                assert(_queue.begin() != _queue.end());
 
97
                Iter it = _queue.begin();
 
98
                assert(!it->second.empty());
 
99
                return preferNewest ? it->second.back() : it->second.front();
 
100
        }
 
101
 
 
102
        /** Get priority of top most item in queue */
 
103
        double topPriority() const {
 
104
                assert(_size > 0);
 
105
                assert(_queue.begin() != _queue.end());
 
106
                ConstIter it = _queue.begin();
 
107
                assert(!it->second.empty());
 
108
                return it->first;
 
109
        }
 
110
};
 
111
 
 
112
} // Structures
 
113
} // PetriEngine
 
114
 
 
115
 
 
116
#endif // ENHANCEDPRIORITYQUEUE_H