1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19 module thrift.util.hashset;
20
21 import std.algorithm : joiner, map;
22 import std.conv : to;
23 import std.traits : isImplicitlyConvertible, ParameterTypeTuple;
24 import std.range : ElementType, isInputRange;
25
26 struct Void {}
27
28 /**
29 * A quickly hacked together hash set implementation backed by built-in
30 * associative arrays to have something to compile Thrift's set<> to until
31 * std.container gains something suitable.
32 */
33 // Note: The funky pointer casts (i.e. *(cast(immutable(E)*)&e) instead of
34 // just cast(immutable(E))e) are a workaround for LDC 2 compatibility.
HashSet(E)35 final class HashSet(E) {
36 ///
37 this() {}
38
39 ///
40 this(E[] elems...) {
41 insert(elems);
42 }
43
44 ///
45 void insert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, E)) {
46 aa_[*(cast(immutable(E)*)&stuff)] = Void.init;
47 }
48
49 ///
50 void insert(Stuff)(Stuff stuff) if (
51 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, E)
52 ) {
53 foreach (e; stuff) {
54 aa_[*(cast(immutable(E)*)&e)] = Void.init;
55 }
56 }
57
58 ///
59 void opOpAssign(string op : "~", Stuff)(Stuff stuff) {
60 insert(stuff);
61 }
62
63 ///
64 void remove(E e) {
65 aa_.remove(*(cast(immutable(E)*)&e));
66 }
67 alias remove removeKey;
68
69 ///
70 void removeAll() {
71 aa_ = null;
72 }
73
74 ///
75 size_t length() @property const {
76 return aa_.length;
77 }
78
79 ///
80 size_t empty() @property const {
81 return !aa_.length;
82 }
83
84 ///
85 bool opBinaryRight(string op : "in")(E e) const {
86 return (e in aa_) !is null;
87 }
88
89 ///
90 auto opSlice() const {
91 // TODO: Implement using AA key range once available in release DMD/druntime
92 // to avoid allocation.
93 return cast(E[])(aa_.keys);
94 }
95
96 ///
97 override string toString() const {
98 // Only provide toString() if to!string() is available for E (exceptions are
99 // e.g. delegates).
100 static if (is(typeof(to!string(E.init)) : string)) {
101 return "{" ~ to!string(joiner(map!`to!string(a)`(aa_.keys), ", ")) ~ "}";
102 } else {
103 // Cast to work around Object not being const-correct.
104 return (cast()super).toString();
105 }
106 }
107
108 ///
109 override bool opEquals(Object other) const {
110 auto rhs = cast(const(HashSet))other;
111 if (rhs) {
112 return aa_ == rhs.aa_;
113 }
114
115 // Cast to work around Object not being const-correct.
116 return (cast()super).opEquals(other);
117 }
118
119 private:
120 Void[immutable(E)] aa_;
121 }
122
123 /// Ditto
hashSet(E)124 auto hashSet(E)(E[] elems...) {
125 return new HashSet!E(elems);
126 }
127
128 unittest {
129 import std.exception;
130
131 auto a = hashSet(1, 2, 2, 3);
132 enforce(a.length == 3);
133 enforce(2 in a);
134 enforce(5 !in a);
135 enforce(a.toString().length == 9);
136 a.remove(2);
137 enforce(a.length == 2);
138 enforce(2 !in a);
139 a.removeAll();
140 enforce(a.empty);
141 enforce(a.toString() == "{}");
142
143 void delegate() dg;
144 auto b = hashSet(dg);
145 static assert(__traits(compiles, b.toString()));
146 }
147