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         typeof(this) r;
91         foreach (k; toRange.filter!(a => set.contains(a)))
92             r.add(k);
93 
94         return r;
95     }
96 
97     auto toArray() inout {
98         import std.array : appender;
99 
100         auto app = appender!(T[])();
101         foreach (key; toRange)
102             app.put(key);
103         return app.data;
104     }
105 
106     auto toRange() inout {
107         return data.byKey;
108     }
109 
110     string toString() {
111         import std.array : appender;
112 
113         auto buf = appender!string;
114         toString(buf);
115         return buf.data;
116     }
117 
118     void toString(Writer)(ref Writer w) const if (isOutputRange!(Writer, char)) {
119         import std.format : formattedWrite;
120 
121         formattedWrite(w, "Set!(%s)(%-(%s, %))", T.stringof, toRange);
122     }
123 }
124 
125 auto toSet(RangeT)(RangeT range) {
126     import std.traits : Unqual;
127 
128     alias T = ElementType!RangeT;
129 
130     Set!(Unqual!T) result;
131     foreach (item; range)
132         result.add(item);
133     return result;
134 }
135 
136 @("shall calculate the symmetric difference between two sets")
137 unittest {
138     import std.algorithm : sort;
139     import std.array : array;
140 
141     auto a = [1, 2, 3, 4, 5].toSet;
142     auto b = [4, 5, 6, 7, 8].toSet;
143 
144     assert(a.symmetricDifference(b).toArray.sort.array == [1, 2, 3, 6, 7, 8]);
145 }