TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
DepthFirstSearcher.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cstdlib>
28 #include <utility>
29 #include <vector>
30 
31 #include "../util/MyList.hpp"
32 
33 namespace tdzdd {
34 
35 template<typename S>
36 class DepthFirstSearcher {
37  typedef S Spec;
38  static int const AR = Spec::ARITY;
39 
40  Spec spec;
41  int const datasize;
42 
43  MyList<char> statePool;
44  std::vector<std::pair<int,int> > valueList;
45 
46 public:
47  DepthFirstSearcher(Spec const& spec) :
48  spec(spec), datasize(spec.datasize()) {
49  }
50 
58  std::vector<std::pair<int,int> > findOneInstance() {
59  valueList.clear();
60  void* p = statePool.alloc_front(datasize);
61  int n = spec.get_root(p);
62  bool ok;
63 
64  if (n <= 0) {
65  ok = (n != 0);
66  }
67  else {
68  valueList.reserve(n);
69 
70  ok = findOneInstanceStep(p, n);
71 
72  for (int i = n; i >= 1; --i) {
73  spec.destructLevel(i);
74  }
75  }
76 
77  spec.destruct(p);
78  statePool.pop_front();
79  if (!ok) throw std::runtime_error("No instance");
80  return valueList;
81  }
82 
83 private:
84  bool findOneInstanceStep(void* p, int i) {
85  int b0 = std::rand() % AR;
86  void* pp = statePool.alloc_front(datasize);
87  bool ok = false;
88 
89  for (int bb = 0; bb < AR; ++bb) {
90  int b = (b0 + bb) % AR;
91 
92  spec.get_copy(pp, p);
93  int ii = spec.get_child(pp, i, b);
94  if (ii <= 0) {
95  ok = (ii != 0);
96  }
97  else {
98  assert(ii < i);
99  ok = findOneInstanceStep(pp, ii);
100  }
101  spec.destruct(pp);
102 
103  if (ok) {
104  valueList.push_back(std::make_pair(i, b));
105  break;
106  }
107  }
108 
109  statePool.pop_front();
110  return ok;
111  }
112 };
113 
114 } // namespace tdzdd