my.set source code

1 /**
2 Copyright: Copyright (c) 2020, Joakim Brännström. All rights reserved.
3 License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0)
4 Author: Joakim Brännström (joakim.brannstrom@gmx.com)
5 */
6 module my.set;
7 
8 import std.algorithm : filter;
9 import std.range : ElementType, isOutputRange;
10 
11 struct Set(T) {
12     alias Type = void[0][T];
13     Type data;
14 
15     bool opBinaryRight(string op)(T key) if (op == "in") {
16         return (key in data) !is null;
17     }
18 
19     bool empty() @safe pure nothrow const @nogc {
20         return data.length == 0;
21     }
22 
23     size_t length() @safe pure nothrow const @nogc {
24         return data.length;
25     }
26 
27     void add(T value) @safe pure nothrow {
28         data[value] = (void[0]).init;
29     }
30 
31     void add(Set!T set) @safe pure nothrow {
32         add(set.data);
33     }
34 
35     void add(Type set) @safe pure nothrow {
36         foreach (key; set.byKey)
37             data[key] = (void[0]).init;
38     }
39 
40     void add(Range)(Range r) @safe pure nothrow if (is(ElementType!Range == T)) {
41         foreach (v; r)
42             data[v] = (void[0]).init;
43     }
44 
45     void remove(T value) {
46         data.remove(value);
47     }
48 
49     Set!T clone() @safe pure nothrow {
50         Set!T result;
51         result.add(data);
52         return result;
53     }
54 
55     bool contains(T value) {
56         return (value in data) !is null;
57     }
58 
59     /** The set difference according to Set Theory.
60      *
61      * It is the set of all members in self that are not members of set.
62      */
63     Set!T setDifference(Set!T set) {
64         typeof(this) r;
65         foreach (k; toRange.filter!(a => !set.contains(a)))
66             r.add(k);
67 
68         return r;
69     }
70 
71     /** The symmetric difference according to Set Theory.
72      *
73      * It is the set of all objects that are a member of exactly one of self and set.
74      */
75     Set!T symmetricDifference(Set!T set) {
76         typeof(this) r;
77         foreach (k; toRange.filter!(a => !set.contains(a)))
78             r.add(k);
79         foreach (k; set.toRange.filter!(a => !contains(a)))
80             r.add(k);
81 
82         return r;
83     }
84 
85     /** The intersection according to Set Theory.
86      *
87      * It is the set of all objects that are members of both self and set.
88      */
89     Set!T intersect(Set!T set) {
90 
91         typeof(this) r;
92         foreach (k; toRange.filter!(a => set.contains(a)))
93             r.add(k);
94 
95         return r;
96     }
97 
98     auto toArray() inout {
99         import std.array : appender;
100 
101         auto app = appender!(T[])();
102         foreach (key; toRange)
103             app.put(key);
104         return app.data;
105     }
106 
107     auto toRange() inout {
108         return data.byKey;
109     }
110 
111     string toString() {
112         import std.array : appender;
113 
114         auto buf = appender!string;
115         toString(buf);
116         return buf.data;
117     }
118 
119     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
120         import std.format : formattedWrite;
121 
122         formattedWrite(w, "Set!(%s)(%-(%s, %))", T.stringof, toRange);
123     }
124 }
125 
126 auto toSet(RangeT)(RangeT range) {
127     import std.traits : Unqual;
128 
129     alias T = ElementType!RangeT;
130 
131     Set!(Unqual!T) result;
132     foreach (item; range)
133         result.add(item);
134     return result;
135 }
136 
137 @("shall calculate the symmetric difference between two sets")
138 unittest {
139     import std.algorithm : sort;
140     import std.array : array;
141 
142     auto a = [1, 2, 3, 4, 5].toSet;
143     auto b = [4, 5, 6, 7, 8].toSet;
144 
145     assert(a.symmetricDifference(b).toArray.sort.array == [1, 2, 3, 6, 7, 8]);
146 }