Predator  [unstable] git snapshot
worklist.hh
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2010 Kamil Dudka <kdudka@redhat.com>
3  *
4  * This file is part of predator.
5  *
6  * predator 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  * any later version.
10  *
11  * predator 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 predator. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #ifndef H_GUARD_WORKLIST_H
21 #define H_GUARD_WORKLIST_H
22 
23 #include "util.hh"
24 
25 #include <queue>
26 #include <set>
27 #include <stack>
28 
29 template <class T, class TShed> struct WorkListLib { };
30 
31 template <class T>
32 struct WorkListLib<T, std::stack<T> > {
33  static typename std::stack<T>::reference top(std::stack<T> &cont) {
34  return cont.top();
35  }
36 };
37 
38 template <class T>
39 struct WorkListLib<T, std::queue<T> > {
40  static typename std::queue<T>::reference top(std::queue<T> &cont) {
41  return cont.front();
42  }
43 };
44 
45 /// really stupid, but easy to use, DFS implementation
46 template <class T, class TSched = std::stack<T> >
47 class WorkList {
48  public:
49  typedef T value_type;
50 
51  protected:
52  TSched todo_;
53  std::set<T> seen_;
54 
55  public:
56  WorkList() { }
57  WorkList(const T &item) {
58  todo_.push(item);
59  seen_.insert(item);
60  }
61 
62  bool next(T &dst) {
63  if (todo_.empty())
64  return false;
65 
67  todo_.pop();
68  return true;
69  }
70 
71  bool schedule(const T &item) {
72  if (hasKey(seen_, item))
73  return false;
74 
75  todo_.push(item);
76  seen_.insert(item);
77  return true;
78  }
79 
80  bool seen(const T &item) const {
81  return hasKey(seen_, item);
82  }
83 
84  unsigned cntSeen() const { return seen_.size(); }
85  unsigned cntTodo() const { return todo_.size(); }
86 };
87 
88 #endif /* H_GUARD_WORKLIST_H */