1 /**
2  * This module provides storage for a set of items of the same type.
3  *
4  * The API offers add(), remove(), in (returning a bool for membership),
5  * clear, length, and iteration.
6  *
7  * See the unittest block for examples.
8  *
9  * Authors: Mark Summerfield, mark@qtrac.eu
10  * License: Apache 2.0
11  * Copyright © 2020 Mark Summerfield. All rights reserved.
12 */
13 module qtrac.aaset;
14 
15 /**
16  * A collection type that stores items of the same type. The item type
17  * must support toHash and ==
18 */
19 struct AAset(T) if (is(int[T])) {
20     private {
21         alias Unit = void[0];
22         enum unit = Unit.init;
23         Unit[T] set;
24     }
25 
26     /** Returns: how many items are in the set */
27     size_t length() const { return set.length; }
28 
29     /**
30      * Adds an item to the set.
31      * Params: item to add.
32     */
33     void add(T item) { set[item] = unit; }
34 
35     /**
36      * Attempts to remove the given item from the set.
37      * Params: item to remove.
38      * Returns: true if item present (and therefore removed) or false if
39      * the item wasn't present.
40     */
41     bool remove(T item) { return set.remove(item); }
42 
43     /**
44      * Removes all items leaving the set empty.
45     */
46     void clear() { set.clear; }
47 
48     /**
49      * Provides a range.
50      * Returns: a range over the set's items.
51     */
52     auto range() const { return set.byKey; }
53     alias range this;
54 
55     /**
56      * Supports the `in` operator.
57      * Params: item to check for membership in the set.
58      * Returns: true if the item is in the set, or false if it isn't.
59     */
60     bool opBinaryRight(string op: "in")(T lhs) const {
61         return (lhs in set) != null;
62     }
63 
64     // TODO union(), intersection(), difference(), symmetric_difference()
65 }
66 
67 unittest {
68     import std.algorithm: sort;
69     import std.array: array;
70     import std.range: enumerate;
71     import std.stdio: writeln;
72     import std.typecons: Tuple;
73 
74     writeln("unittest for the aaset library.");
75 
76     alias Pair = Tuple!(int, "count", string, "word");
77 
78     immutable inputs = [Pair(1, "one"), Pair(2, "two"), Pair(3, "three"),
79                         Pair(4, "four"), Pair(4, "two"), Pair(5, "five"),
80                         Pair(6, "six")];
81     AAset!string words;
82     assert(words.length == 0);
83     foreach (pair; inputs) {
84         words.add(pair.word);
85         assert(words.length == pair.count);
86     }
87     immutable len = words.length;
88     assert(!words.remove("missing"));
89     assert(words.remove("one"));
90     assert(words.length == len - 1);
91     immutable expected = ["five", "four", "six", "three", "two"];
92     foreach (i, word; words.array.sort.enumerate)
93         assert(word == expected[i]);
94     assert("Z" !in words);
95     assert("three" in words);
96     assert(words.length == 5);
97     words.clear;
98     assert(words.length == 0);
99 }