5 // Alexander Chebaturkin (chebaturkin@gmail.com)
7 // Copyright (C) 2011 Alexander Chebaturkin
9 // Permission is hereby granted, free of charge, to any person obtaining
10 // a copy of this software and associated documentation files (the
11 // "Software"), to deal in the Software without restriction, including
12 // without limitation the rights to use, copy, modify, merge, publish,
13 // distribute, sublicense, and/or sell copies of the Software, and to
14 // permit persons to whom the Software is furnished to do so, subject to
15 // the following conditions:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 using System.Collections.Generic;
33 namespace Mono.CodeContracts.Static.DataStructures {
34 class ImmutableSet<T> : IImmutableSet<T>
35 where T : IEquatable<T> {
36 private readonly IImmutableMap<T, Dummy> underlying;
38 public ImmutableSet (IImmutableMap<T, Dummy> immutableMap)
40 this.underlying = immutableMap;
43 #region Implementation of IImmutableSet<T>
46 get { return this.underlying.AnyKey; }
51 get { return this.underlying.Count; }
54 public IEnumerable<T> Elements
56 get { return this.underlying.Keys; }
59 public IImmutableSet<T> Add (T item)
61 return new ImmutableSet<T> (this.underlying.Add (item, Dummy.Value));
64 public IImmutableSet<T> Remove (T item)
66 return new ImmutableSet<T> (this.underlying.Remove (item));
69 public bool Contains (T item)
71 return this.underlying.ContainsKey (item);
74 public bool IsContainedIn (IImmutableSet<T> that)
76 if (Count > that.Count)
79 this.underlying.Visit ((e, dummy) => {
80 if (that.Contains (e))
81 return VisitStatus.ContinueVisit;
84 return VisitStatus.StopVisit;
89 public IImmutableSet<T> Intersect (IImmutableSet<T> that)
96 IImmutableSet<T> larger;
97 if (Count < that.Count) {
106 IImmutableSet<T> result = set;
108 if (!larger.Contains (e))
109 result = result.Remove (e);
114 public IImmutableSet<T> Union (IImmutableSet<T> that)
120 IImmutableSet<T> smaller;
121 IImmutableSet<T> larger;
122 if (Count < that.Count) {
131 IImmutableSet<T> result = larger;
132 smaller.Visit (e => { result = result.Add (e); });
136 public void Visit (Action<T> visitor)
138 this.underlying.Visit ((elem, dummy) => {
140 return VisitStatus.ContinueVisit;
144 public void Dump (TextWriter tw)
148 foreach (T key in this.underlying.Keys) {
153 tw.Write ("{0}", key);
158 public static IImmutableSet<T> Empty ()
160 return new ImmutableSet<T> (ImmutableMap<T, Dummy>.Empty);
163 public static IImmutableSet<T> Empty (Func<T, int> keyConverter)
165 return new ImmutableSet<T> (ImmutableIntKeyMap<T, Dummy>.Empty (keyConverter));