HOG2
NBSQueue.h
Go to the documentation of this file.
1 //
2 // NBSQueue.h
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 2/10/17.
6 // Copyright © 2017 University of Denver. All rights reserved.
7 //
8 
9 #ifndef NBSQueue_h
10 #define NBSQueue_h
11 
12 #include "BDOpenClosed.h"
13 #include "BDIndexOpenClosed.h"
14 
15 //low g -> low f
16 template <class state, class DS>
17 struct NBSCompareOpenReady {
18  bool operator()(const DS &i1, const DS &i2) const
19  {
20  double f1 = i1.g + i1.h;
21  double f2 = i2.g + i2.h;
22 
23  if (fequal(i1.g, i2.g))
24  {
25  return (!fless(f1, f2));
26  }
27  return (fgreater(i1.g, i2.g)); // low g over high
28  }
29 };
30 
31 template <class state, class DS>
32 struct NBSCompareOpenWaiting {
33  bool operator()(const DS &i1, const DS &i2) const
34  {
35  double f1 = i1.g + i1.h;
36  double f2 = i2.g + i2.h;
37 
38  if (fequal(f1, f2))
39  {
40  return (!fgreater(i1.g, i2.g));
41  }
42  return (fgreater(f1, f2)); // low f over high
43  }
44 };
45 
46 
47 
48 template <typename state, int epsilon = 0, bool moveLessEqToOpen = true, class pQueue = BDOpenClosed<state, NBSCompareOpenReady<state, BDOpenClosedData<state>>, NBSCompareOpenWaiting<state, BDOpenClosedData<state>>>>
49 class NBSQueue {
50 public:
51  bool GetNextPair(uint64_t &nextForward, uint64_t &nextBackward)
52  {
53  // move items with f<CLowerBound to ready
54  while (forwardQueue.OpenWaitingSize() != 0)
55  {
56  if (moveLessEqToOpen)
57  {
58  if (flesseq(forwardQueue.PeekAt(kOpenWaiting).g+forwardQueue.PeekAt(kOpenWaiting).h, CLowerBound))
59  forwardQueue.PutToReady();
60  else
61  break;
62  }
63  else if (!moveLessEqToOpen)
64  {
65  if (fless(forwardQueue.PeekAt(kOpenWaiting).g+forwardQueue.PeekAt(kOpenWaiting).h, CLowerBound))
66  forwardQueue.PutToReady();
67  else
68  break;
69  }
70  }
71  while (backwardQueue.OpenWaitingSize() != 0)
72  {
73  if (moveLessEqToOpen)
74  {
75  if (flesseq(backwardQueue.PeekAt(kOpenWaiting).g+backwardQueue.PeekAt(kOpenWaiting).h, CLowerBound))
76  backwardQueue.PutToReady();
77  else
78  break;
79  }
80  else if (!moveLessEqToOpen)
81  {
82  if (fless(backwardQueue.PeekAt(kOpenWaiting).g+backwardQueue.PeekAt(kOpenWaiting).h, CLowerBound))
83  backwardQueue.PutToReady();
84  else
85  break;
86  }
87  }
88 // while (backwardQueue.OpenWaitingSize() != 0)
89 // {
90 // if (moveLessEqToOpen &&
91 // flesseq(backwardQueue.PeekAt(kOpenWaiting).g+backwardQueue.PeekAt(kOpenWaiting).h, CLowerBound))
92 // {
93 // backwardQueue.PutToReady();
94 // }
95 // else if (!moveLessEqToOpen &&
96 // fless(backwardQueue.PeekAt(kOpenWaiting).g+backwardQueue.PeekAt(kOpenWaiting).h, CLowerBound))
97 // {
98 // backwardQueue.PutToReady();
99 // }
100 // }
101 
102  while (true)
103  {
104  if (forwardQueue.OpenSize() == 0)
105  return false;
106  if (backwardQueue.OpenSize() == 0)
107  return false;
108  if ((forwardQueue.OpenReadySize() != 0) && (backwardQueue.OpenReadySize() != 0) &&
109  (!fgreater(forwardQueue.PeekAt(kOpenReady).g + backwardQueue.PeekAt(kOpenReady).g + epsilon, CLowerBound)))
110  {
111  nextForward = forwardQueue.Peek(kOpenReady);
112  nextBackward = backwardQueue.Peek(kOpenReady);
113  return true;
114  }
115  bool changed = false;
116 
117  if (backwardQueue.OpenWaitingSize() != 0)
118  {
119  const auto i4 = backwardQueue.PeekAt(kOpenWaiting);
120  if (!fgreater(i4.g+i4.h, CLowerBound))
121  {
122  changed = true;
123  backwardQueue.PutToReady();
124  }
125  }
126  if (forwardQueue.OpenWaitingSize() != 0)
127  {
128  const auto i3 = forwardQueue.PeekAt(kOpenWaiting);
129  if (!fgreater(i3.g+i3.h, CLowerBound))
130  {
131  changed = true;
132  forwardQueue.PutToReady();
133  }
134  }
135  if (!changed)
136  {
137  CLowerBound = DBL_MAX;
138  if (forwardQueue.OpenWaitingSize() != 0)
139  {
140  const auto i5 = forwardQueue.PeekAt(kOpenWaiting);
141  CLowerBound = std::min(CLowerBound, i5.g+i5.h);
142  }
143  if (backwardQueue.OpenWaitingSize() != 0)
144  {
145  const auto i6 = backwardQueue.PeekAt(kOpenWaiting);
146  CLowerBound = std::min(CLowerBound, i6.g+i6.h);
147  }
148  if ((forwardQueue.OpenReadySize() != 0) && (backwardQueue.OpenReadySize() != 0))
149  CLowerBound = std::min(CLowerBound, forwardQueue.PeekAt(kOpenReady).g + backwardQueue.PeekAt(kOpenReady).g + epsilon);
150  }
151 
152  }
153  return false;
154  }
155  void Reset(int maxHash)
156  {
157  CLowerBound = 0;
158  forwardQueue.Reset(maxHash);
159  backwardQueue.Reset(maxHash);
160  }
161  double GetLowerBound() { return CLowerBound; }
162  bool TerminateOnG() {
163  if (forwardQueue.OpenReadySize() > 0 && backwardQueue.OpenReadySize() > 0)
164  return CLowerBound == forwardQueue.PeekAt(kOpenReady).g + backwardQueue.PeekAt(kOpenReady).g + epsilon;
165  return false;
166  }
167  pQueue forwardQueue;
168  pQueue backwardQueue;
169 private:
170  double CLowerBound;
171 };
172 
173 #endif /* NBSQueue_h */
kOpenWaiting
@ kOpenWaiting
Definition: BDOpenClosed.h:24
NBSCompareOpenWaiting
Definition: NBSQueue.h:32
BDIndexOpenClosed.h
NBSQueue::backwardQueue
pQueue backwardQueue
Definition: NBSQueue.h:168
NBSQueue::TerminateOnG
bool TerminateOnG()
Definition: NBSQueue.h:162
min
double min(double a, double b)
Definition: FPUtil.h:35
kOpenReady
@ kOpenReady
Definition: BDOpenClosed.h:23
NBSQueue::Reset
void Reset(int maxHash)
Definition: NBSQueue.h:155
NBSQueue::forwardQueue
pQueue forwardQueue
Definition: NBSQueue.h:167
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
NBSQueue::CLowerBound
double CLowerBound
Definition: NBSQueue.h:170
BDOpenClosed.h
NBSCompareOpenReady
Definition: NBSQueue.h:17
NBSQueue::GetNextPair
bool GetNextPair(uint64_t &nextForward, uint64_t &nextBackward)
Definition: NBSQueue.h:51
NBSCompareOpenReady::operator()
bool operator()(const DS &i1, const DS &i2) const
Definition: NBSQueue.h:18
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
NBSCompareOpenWaiting::operator()
bool operator()(const DS &i1, const DS &i2) const
Definition: NBSQueue.h:33
NBSQueue::GetLowerBound
double GetLowerBound()
Definition: NBSQueue.h:161
NBSQueue
Definition: NBSQueue.h:49
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
flesseq
bool flesseq(double a, double b)
Definition: FPUtil.h:30
Generated by   doxygen 1.8.17