|
695
|
1 /**
|
|
|
2 * Stone of Orthanc
|
|
|
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
|
|
|
4 * Department, University Hospital of Liege, Belgium
|
|
|
5 * Copyright (C) 2017-2019 Osimis S.A., Belgium
|
|
|
6 *
|
|
|
7 * This program is free software: you can redistribute it and/or
|
|
|
8 * modify it under the terms of the GNU Affero General Public License
|
|
|
9 * as published by the Free Software Foundation, either version 3 of
|
|
|
10 * the License, or (at your option) any later version.
|
|
|
11 *
|
|
|
12 * This program is distributed in the hope that it will be useful, but
|
|
|
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
|
15 * Affero General Public License for more details.
|
|
|
16 *
|
|
|
17 * You should have received a copy of the GNU Affero General Public License
|
|
|
18 * along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
|
19 **/
|
|
|
20
|
|
|
21
|
|
|
22 #include "gtest/gtest.h"
|
|
|
23
|
|
|
24 #include <Core/OrthancException.h>
|
|
|
25
|
|
|
26 #include <boost/noncopyable.hpp>
|
|
|
27 #include <vector>
|
|
|
28
|
|
|
29 namespace OrthancStone
|
|
|
30 {
|
|
|
31 class IFetchingStrategy : public boost::noncopyable
|
|
|
32 {
|
|
|
33 public:
|
|
|
34 virtual ~IFetchingStrategy()
|
|
|
35 {
|
|
|
36 }
|
|
|
37
|
|
|
38 virtual unsigned int GetItemsCount() const = 0;
|
|
|
39
|
|
|
40 virtual unsigned int GetMaxQuality() const = 0;
|
|
|
41
|
|
|
42 virtual bool GetNext(unsigned int& item,
|
|
|
43 unsigned int& quality) = 0;
|
|
|
44
|
|
|
45 virtual void SetCurrent(unsigned int item) = 0;
|
|
|
46
|
|
|
47 // Ask the strategy to re-schedule the item with the lowest
|
|
|
48 // priority in the fetching order. This allows to know which item
|
|
|
49 // should be dropped from a cache.
|
|
|
50 virtual void RecycleFurthest(unsigned int& item) = 0;
|
|
|
51 };
|
|
|
52
|
|
|
53
|
|
|
54 class IFetchingItemsSorter : public boost::noncopyable
|
|
|
55 {
|
|
|
56 public:
|
|
|
57 virtual ~IFetchingItemsSorter()
|
|
|
58 {
|
|
|
59 }
|
|
|
60
|
|
|
61 virtual unsigned int GetItemsCount() const = 0;
|
|
|
62
|
|
|
63 // Sort a set of items given the current item
|
|
|
64 virtual void Sort(std::vector<unsigned int>& target,
|
|
|
65 unsigned int current) = 0;
|
|
|
66 };
|
|
|
67
|
|
|
68
|
|
|
69
|
|
|
70 class BasicFetchingItemsSorter : public IFetchingItemsSorter
|
|
|
71 {
|
|
|
72 private:
|
|
|
73 unsigned int itemsCount_;
|
|
|
74
|
|
|
75 public:
|
|
|
76 BasicFetchingItemsSorter(unsigned int itemsCount) :
|
|
|
77 itemsCount_(itemsCount)
|
|
|
78 {
|
|
|
79 if (itemsCount == 0)
|
|
|
80 {
|
|
|
81 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange);
|
|
|
82 }
|
|
|
83 }
|
|
|
84
|
|
|
85 virtual unsigned int GetItemsCount() const
|
|
|
86 {
|
|
|
87 return itemsCount_;
|
|
|
88 }
|
|
|
89
|
|
|
90 virtual void Sort(std::vector<unsigned int>& target,
|
|
|
91 unsigned int current)
|
|
|
92 {
|
|
|
93 if (current >= itemsCount_)
|
|
|
94 {
|
|
|
95 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange);
|
|
|
96 }
|
|
|
97
|
|
|
98 target.clear();
|
|
|
99 target.reserve(itemsCount_);
|
|
|
100 target.push_back(current);
|
|
|
101
|
|
|
102 const unsigned int countBelow = current;
|
|
|
103 const unsigned int countAbove = (itemsCount_ - 1) - current;
|
|
|
104 const unsigned int n = std::min(countBelow, countAbove);
|
|
|
105
|
|
|
106 for (unsigned int i = 1; i <= n; i++)
|
|
|
107 {
|
|
|
108 assert(current + i < itemsCount_ &&
|
|
|
109 current >= i);
|
|
|
110 target.push_back(current + i);
|
|
|
111 target.push_back(current - i);
|
|
|
112 }
|
|
|
113
|
|
|
114 for (unsigned int i = current - n; i > 0; i--)
|
|
|
115 {
|
|
|
116 target.push_back(i - 1);
|
|
|
117 }
|
|
|
118
|
|
|
119 for (unsigned int i = current + n + 1; i < itemsCount_; i++)
|
|
|
120 {
|
|
|
121 target.push_back(i);
|
|
|
122 }
|
|
|
123
|
|
|
124 assert(target.size() == itemsCount_);
|
|
|
125 }
|
|
|
126 };
|
|
|
127
|
|
|
128
|
|
|
129 class BasicFetchingStrategy : public IFetchingStrategy
|
|
|
130 {
|
|
|
131 private:
|
|
|
132 struct Item
|
|
|
133 {
|
|
|
134 unsigned int item_;
|
|
|
135 unsigned int quality_;
|
|
|
136 };
|
|
|
137
|
|
|
138 std::auto_ptr<IFetchingItemsSorter> sorter_;
|
|
|
139 std::vector<unsigned int> nextQuality_;
|
|
|
140 unsigned int maxQuality_;
|
|
|
141 std::vector<Item> content_;
|
|
|
142 size_t currentItem_;
|
|
|
143
|
|
|
144 public:
|
|
|
145 BasicFetchingStrategy(IFetchingItemsSorter* sorter, // Takes ownership
|
|
|
146 unsigned int maxQuality) :
|
|
|
147 sorter_(sorter),
|
|
|
148 nextQuality_(sorter_->GetItemsCount(), 0),
|
|
|
149 maxQuality_(maxQuality),
|
|
|
150 currentItem_(0)
|
|
|
151 {
|
|
|
152 if (sorter == NULL)
|
|
|
153 {
|
|
|
154 throw Orthanc::OrthancException(Orthanc::ErrorCode_NullPointer);
|
|
|
155 }
|
|
|
156
|
|
|
157 SetCurrent(0);
|
|
|
158 }
|
|
|
159
|
|
|
160 virtual unsigned int GetItemsCount() const
|
|
|
161 {
|
|
|
162 return sorter_->GetItemsCount();
|
|
|
163 }
|
|
|
164
|
|
|
165 virtual unsigned int GetMaxQuality() const
|
|
|
166 {
|
|
|
167 return maxQuality_;
|
|
|
168 }
|
|
|
169
|
|
|
170 virtual bool GetNext(unsigned int& item,
|
|
|
171 unsigned int& quality)
|
|
|
172 {
|
|
|
173 if (currentItem_ >= content_.size())
|
|
|
174 {
|
|
|
175 return false;
|
|
|
176 }
|
|
|
177 else
|
|
|
178 {
|
|
|
179 item = content_[currentItem_].item_;
|
|
|
180 quality = content_[currentItem_].quality_;
|
|
|
181
|
|
|
182 assert(nextQuality_[item] <= quality);
|
|
|
183 nextQuality_[item] = quality + 1;
|
|
|
184
|
|
|
185 return true;
|
|
|
186 }
|
|
|
187 }
|
|
|
188
|
|
|
189 virtual void SetCurrent(unsigned int item)
|
|
|
190 {
|
|
|
191 std::vector<unsigned int> v;
|
|
|
192 sorter_->Sort(v, item);
|
|
|
193
|
|
|
194 assert(v.size() == GetItemsCount());
|
|
|
195
|
|
|
196 content_.clear();
|
|
|
197 content_.reserve(v.size() * maxQuality_);
|
|
|
198
|
|
|
199 for (unsigned int q = 0; q < maxQuality_; q++)
|
|
|
200 {
|
|
|
201 for (size_t i = 0; i < v.size(); i++)
|
|
|
202 {
|
|
|
203
|
|
|
204 }
|
|
|
205 }
|
|
|
206 }
|
|
|
207
|
|
|
208 // Ask the strategy to re-schedule the item with the lowest
|
|
|
209 // priority in the fetching order. This allows to know which item
|
|
|
210 // should be dropped from a cache.
|
|
|
211 virtual void RecycleFurthest(unsigned int& item)
|
|
|
212 {
|
|
|
213 throw Orthanc::OrthancException(Orthanc::ErrorCode_NotImplemented);
|
|
|
214 }
|
|
|
215 };
|
|
|
216 }
|
|
|
217
|
|
|
218
|
|
|
219
|
|
|
220 TEST(BasicFetchingStrategy, Test)
|
|
|
221 {
|
|
|
222 OrthancStone::BasicFetchingStrategy s(new OrthancStone::BasicFetchingItemsSorter(10), 3);
|
|
|
223 }
|
|
|
224
|
|
|
225
|
|
|
226
|
|
|
227
|
|
|
228 TEST(BasicFetchingItemsSorter, Small)
|
|
|
229 {
|
|
|
230 ASSERT_THROW(OrthancStone::BasicFetchingItemsSorter(0), Orthanc::OrthancException);
|
|
|
231 std::vector<unsigned int> v;
|
|
|
232
|
|
|
233 {
|
|
|
234 OrthancStone::BasicFetchingItemsSorter s(1);
|
|
|
235 s.Sort(v, 0);
|
|
|
236 ASSERT_EQ(1u, v.size());
|
|
|
237 ASSERT_EQ(0u, v[0]);
|
|
|
238
|
|
|
239 ASSERT_THROW(s.Sort(v, 1), Orthanc::OrthancException);
|
|
|
240 }
|
|
|
241
|
|
|
242 {
|
|
|
243 OrthancStone::BasicFetchingItemsSorter s(2);
|
|
|
244 s.Sort(v, 0);
|
|
|
245 ASSERT_EQ(2u, v.size());
|
|
|
246 ASSERT_EQ(0u, v[0]);
|
|
|
247 ASSERT_EQ(1u, v[1]);
|
|
|
248
|
|
|
249 s.Sort(v, 1);
|
|
|
250 ASSERT_EQ(2u, v.size());
|
|
|
251 ASSERT_EQ(1u, v[0]);
|
|
|
252 ASSERT_EQ(0u, v[1]);
|
|
|
253
|
|
|
254 ASSERT_THROW(s.Sort(v, 2), Orthanc::OrthancException);
|
|
|
255 }
|
|
|
256
|
|
|
257 {
|
|
|
258 OrthancStone::BasicFetchingItemsSorter s(3);
|
|
|
259 s.Sort(v, 0);
|
|
|
260 ASSERT_EQ(3u, v.size());
|
|
|
261 ASSERT_EQ(0u, v[0]);
|
|
|
262 ASSERT_EQ(1u, v[1]);
|
|
|
263 ASSERT_EQ(2u, v[2]);
|
|
|
264
|
|
|
265 s.Sort(v, 1);
|
|
|
266 ASSERT_EQ(3u, v.size());
|
|
|
267 ASSERT_EQ(1u, v[0]);
|
|
|
268 ASSERT_EQ(2u, v[1]);
|
|
|
269 ASSERT_EQ(0u, v[2]);
|
|
|
270
|
|
|
271 s.Sort(v, 2);
|
|
|
272 ASSERT_EQ(3u, v.size());
|
|
|
273 ASSERT_EQ(2u, v[0]);
|
|
|
274 ASSERT_EQ(1u, v[1]);
|
|
|
275 ASSERT_EQ(0u, v[2]);
|
|
|
276
|
|
|
277 ASSERT_THROW(s.Sort(v, 3), Orthanc::OrthancException);
|
|
|
278 }
|
|
|
279 }
|
|
|
280
|
|
|
281
|
|
|
282 TEST(BasicFetchingItemsSorter, Odd)
|
|
|
283 {
|
|
|
284 OrthancStone::BasicFetchingItemsSorter s(7);
|
|
|
285 std::vector<unsigned int> v;
|
|
|
286
|
|
|
287 ASSERT_THROW(s.Sort(v, 7), Orthanc::OrthancException);
|
|
|
288
|
|
|
289 {
|
|
|
290 s.Sort(v, 0);
|
|
|
291 ASSERT_EQ(7u, v.size());
|
|
|
292 ASSERT_EQ(0u, v[0]);
|
|
|
293 ASSERT_EQ(1u, v[1]);
|
|
|
294 ASSERT_EQ(2u, v[2]);
|
|
|
295 ASSERT_EQ(3u, v[3]);
|
|
|
296 ASSERT_EQ(4u, v[4]);
|
|
|
297 ASSERT_EQ(5u, v[5]);
|
|
|
298 ASSERT_EQ(6u, v[6]);
|
|
|
299 }
|
|
|
300
|
|
|
301 {
|
|
|
302 s.Sort(v, 1);
|
|
|
303 ASSERT_EQ(7u, v.size());
|
|
|
304 ASSERT_EQ(1u, v[0]);
|
|
|
305 ASSERT_EQ(2u, v[1]);
|
|
|
306 ASSERT_EQ(0u, v[2]);
|
|
|
307 ASSERT_EQ(3u, v[3]);
|
|
|
308 ASSERT_EQ(4u, v[4]);
|
|
|
309 ASSERT_EQ(5u, v[5]);
|
|
|
310 ASSERT_EQ(6u, v[6]);
|
|
|
311 }
|
|
|
312
|
|
|
313 {
|
|
|
314 s.Sort(v, 2);
|
|
|
315 ASSERT_EQ(7u, v.size());
|
|
|
316 ASSERT_EQ(2u, v[0]);
|
|
|
317 ASSERT_EQ(3u, v[1]);
|
|
|
318 ASSERT_EQ(1u, v[2]);
|
|
|
319 ASSERT_EQ(4u, v[3]);
|
|
|
320 ASSERT_EQ(0u, v[4]);
|
|
|
321 ASSERT_EQ(5u, v[5]);
|
|
|
322 ASSERT_EQ(6u, v[6]);
|
|
|
323 }
|
|
|
324
|
|
|
325 {
|
|
|
326 s.Sort(v, 3);
|
|
|
327 ASSERT_EQ(7u, v.size());
|
|
|
328 ASSERT_EQ(3u, v[0]);
|
|
|
329 ASSERT_EQ(4u, v[1]);
|
|
|
330 ASSERT_EQ(2u, v[2]);
|
|
|
331 ASSERT_EQ(5u, v[3]);
|
|
|
332 ASSERT_EQ(1u, v[4]);
|
|
|
333 ASSERT_EQ(6u, v[5]);
|
|
|
334 ASSERT_EQ(0u, v[6]);
|
|
|
335 }
|
|
|
336
|
|
|
337 {
|
|
|
338 s.Sort(v, 4);
|
|
|
339 ASSERT_EQ(7u, v.size());
|
|
|
340 ASSERT_EQ(4u, v[0]);
|
|
|
341 ASSERT_EQ(5u, v[1]);
|
|
|
342 ASSERT_EQ(3u, v[2]);
|
|
|
343 ASSERT_EQ(6u, v[3]);
|
|
|
344 ASSERT_EQ(2u, v[4]);
|
|
|
345 ASSERT_EQ(1u, v[5]);
|
|
|
346 ASSERT_EQ(0u, v[6]);
|
|
|
347 }
|
|
|
348
|
|
|
349 {
|
|
|
350 s.Sort(v, 5);
|
|
|
351 ASSERT_EQ(7u, v.size());
|
|
|
352 ASSERT_EQ(5u, v[0]);
|
|
|
353 ASSERT_EQ(6u, v[1]);
|
|
|
354 ASSERT_EQ(4u, v[2]);
|
|
|
355 ASSERT_EQ(3u, v[3]);
|
|
|
356 ASSERT_EQ(2u, v[4]);
|
|
|
357 ASSERT_EQ(1u, v[5]);
|
|
|
358 ASSERT_EQ(0u, v[6]);
|
|
|
359 }
|
|
|
360
|
|
|
361 {
|
|
|
362 s.Sort(v, 6);
|
|
|
363 ASSERT_EQ(7u, v.size());
|
|
|
364 ASSERT_EQ(6u, v[0]);
|
|
|
365 ASSERT_EQ(5u, v[1]);
|
|
|
366 ASSERT_EQ(4u, v[2]);
|
|
|
367 ASSERT_EQ(3u, v[3]);
|
|
|
368 ASSERT_EQ(2u, v[4]);
|
|
|
369 ASSERT_EQ(1u, v[5]);
|
|
|
370 ASSERT_EQ(0u, v[6]);
|
|
|
371 }
|
|
|
372 }
|
|
|
373
|
|
|
374
|
|
|
375 TEST(BasicFetchingItemsSorter, Even)
|
|
|
376 {
|
|
|
377 OrthancStone::BasicFetchingItemsSorter s(6);
|
|
|
378 std::vector<unsigned int> v;
|
|
|
379
|
|
|
380 {
|
|
|
381 s.Sort(v, 0);
|
|
|
382 ASSERT_EQ(6u, v.size());
|
|
|
383 ASSERT_EQ(0u, v[0]);
|
|
|
384 ASSERT_EQ(1u, v[1]);
|
|
|
385 ASSERT_EQ(2u, v[2]);
|
|
|
386 ASSERT_EQ(3u, v[3]);
|
|
|
387 ASSERT_EQ(4u, v[4]);
|
|
|
388 ASSERT_EQ(5u, v[5]);
|
|
|
389 }
|
|
|
390
|
|
|
391 {
|
|
|
392 s.Sort(v, 1);
|
|
|
393 ASSERT_EQ(6u, v.size());
|
|
|
394 ASSERT_EQ(1u, v[0]);
|
|
|
395 ASSERT_EQ(2u, v[1]);
|
|
|
396 ASSERT_EQ(0u, v[2]);
|
|
|
397 ASSERT_EQ(3u, v[3]);
|
|
|
398 ASSERT_EQ(4u, v[4]);
|
|
|
399 ASSERT_EQ(5u, v[5]);
|
|
|
400 }
|
|
|
401
|
|
|
402 {
|
|
|
403 s.Sort(v, 2);
|
|
|
404 ASSERT_EQ(6u, v.size());
|
|
|
405 ASSERT_EQ(2u, v[0]);
|
|
|
406 ASSERT_EQ(3u, v[1]);
|
|
|
407 ASSERT_EQ(1u, v[2]);
|
|
|
408 ASSERT_EQ(4u, v[3]);
|
|
|
409 ASSERT_EQ(0u, v[4]);
|
|
|
410 ASSERT_EQ(5u, v[5]);
|
|
|
411 }
|
|
|
412
|
|
|
413 {
|
|
|
414 s.Sort(v, 3);
|
|
|
415 ASSERT_EQ(6u, v.size());
|
|
|
416 ASSERT_EQ(3u, v[0]);
|
|
|
417 ASSERT_EQ(4u, v[1]);
|
|
|
418 ASSERT_EQ(2u, v[2]);
|
|
|
419 ASSERT_EQ(5u, v[3]);
|
|
|
420 ASSERT_EQ(1u, v[4]);
|
|
|
421 ASSERT_EQ(0u, v[5]);
|
|
|
422 }
|
|
|
423
|
|
|
424 {
|
|
|
425 s.Sort(v, 4);
|
|
|
426 ASSERT_EQ(6u, v.size());
|
|
|
427 ASSERT_EQ(4u, v[0]);
|
|
|
428 ASSERT_EQ(5u, v[1]);
|
|
|
429 ASSERT_EQ(3u, v[2]);
|
|
|
430 ASSERT_EQ(2u, v[3]);
|
|
|
431 ASSERT_EQ(1u, v[4]);
|
|
|
432 ASSERT_EQ(0u, v[5]);
|
|
|
433 }
|
|
|
434
|
|
|
435 {
|
|
|
436 s.Sort(v, 5);
|
|
|
437 ASSERT_EQ(6u, v.size());
|
|
|
438 ASSERT_EQ(5u, v[0]);
|
|
|
439 ASSERT_EQ(4u, v[1]);
|
|
|
440 ASSERT_EQ(3u, v[2]);
|
|
|
441 ASSERT_EQ(2u, v[3]);
|
|
|
442 ASSERT_EQ(1u, v[4]);
|
|
|
443 ASSERT_EQ(0u, v[5]);
|
|
|
444 }
|
|
|
445 }
|
