dextool.plugin.fuzzer.backend.unique

1 /**
2 Copyright: Copyright (c) 2017, Joakim Brännström. All rights reserved.
3 License: MPL-2
4 Author: Joakim Brännström (joakim.brannstrom@gmx.com)
5 
6 This Source Code Form is subject to the terms of the Mozilla Public License,
7 v.2.0. If a copy of the MPL was not distributed with this file, You can obtain
8 one at http://mozilla.org/MPL/2.0/.
9 
10 This file contains the plumbing for generating a unique sequence of numbers
11 that is tightly packed.
12 */
13 module dextool.plugin.fuzzer.backend.unique_sequence;
14 
15 import logger = std.experimental.logger;
16 
17 /// The first number of the sequence will be skipped.
18 /// It is okey.
19 struct Sequence(NumT) {
20     @disable this(this);
21 
22     /// Put a number into the pool or adjust `n` to a valid value.
23     void putOrAdjust(ref NumT n) {
24         if (n <= last_num) {
25             n = next;
26         } else if (auto v = n in used_pool) {
27             n = next;
28         } else {
29             used_pool[n] = true;
30         }
31 
32         if (n % 100 == 0) {
33             vacuumPool;
34         }
35     }
36 
37     NumT next() {
38         while (++last_num in used_pool) {
39         }
40         return last_num;
41     }
42 
43     void vacuumPool() {
44         bool[NumT] new_pool;
45 
46         foreach (n; used_pool) {
47             if (n >= last_num)
48                 new_pool[n] = true;
49         }
50 
51         used_pool = new_pool;
52     }
53 
54 private:
55     bool[NumT] used_pool;
56     NumT last_num;
57 }
58 
59 version (unittest) {
60     import unit_threaded : shouldEqual;
61 }
62 
63 @("Shall be a list of numbers for the holes in the initialized sequence")
64 unittest {
65     Sequence!ulong seq;
66 
67     ulong[] input = [0, 2, 4, 7];
68 
69     foreach (i; 0 .. input.length)
70         seq.putOrAdjust(input[i]);
71 
72     ulong[] output;
73     foreach (i; 0 .. 5)
74         output ~= seq.next;
75 
76     input.shouldEqual([1, 2, 4, 7]);
77     output.shouldEqual([3, 5, 6, 8, 9]);
78 }