1 package frost.collections
2
3 ====================================================================================================
4 An implementation of the set abstract data type. Sets are collections which cannot contain duplicate
5 entries; adding an element which already exists to a set does not do anything.
6 ====================================================================================================
7 class HashSet<T:HashKey<T>> : Collection<T> {
8 @private
9 def contents := HashMap<T, T>()
10
11 ================================================================================================
12 Creates a new empty set.
13 ================================================================================================
14 init() {
15 }
16
17 ================================================================================================
18 Creates a new set containing all of the elements from another collection. Duplicate entries are
19 filtered out, so
20
21 -- testcase HashSetInit
22 HashSet<Int>(list).count
23
24 is an easy way to determine how many unique entries `list` contains.
25 ================================================================================================
26 init(c:CollectionView<T>) {
27 addAll(c)
28 }
29
30 @override
31 method add(value:T) {
32 contents[value] := value
33 }
34
35 @override
36 method addAll(c:CollectionView<T>) {
37 for v in c {
38 add(v)
39 }
40 }
41
42 ================================================================================================
43 Removes an entry from the set, if present.
44 ================================================================================================
45 method remove(value:T) {
46 contents.remove(value)
47 }
48
49 @override
50 function get_count():Int {
51 return contents.count
52 }
53
54 @override
55 method clear() {
56 contents.clear()
57 }
58
59 @override
60 function get_iterator():Iterator<T> {
61 return contents.keys
62 }
63
64 ================================================================================================
65 Returns `true` if the value is present in the set.
66 ================================================================================================
67 function contains(value:T):Bit {
68 return contents.contains(value)
69 }
70
71 @override
72 method filterInPlace(test:(T)=>(Bit)) {
73 contents.filterInPlace((k, v) => test(k))
74 }
75
76 @override
77 method mapInPlace(f:(T)=>(T)) {
78 for (k, v) in contents.entries {
79 contents[k] := f(v)
80 }
81 }
82
83 @override
84 function get_toString():String {
85 def result := MutableString("[")
86 var separator := ""
87 for v in contents.keys {
88 result.append(separator)
89 -- FIXME cast shouldn't be necessary
90 if v->Object? !== null {
91 result.append(v)
92 }
93 else {
94 result.append("<null>")
95 }
96 separator := ", "
97 }
98 result.append("]")
99 return result.finish()
100 }
101 }
102