5 // Jb Evain <jbevain@novell.com>
7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
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
;
31 using System
.Collections
.Generic
;
33 using System
.Runtime
.Serialization
;
34 using System
.Runtime
.InteropServices
;
35 using System
.Security
;
36 using System
.Security
.Permissions
;
37 using System
.Diagnostics
;
39 // SortedSet is basically implemented as a reduction of SortedDictionary<K, V>
43 namespace System
.Collections
.Generic
{
46 [DebuggerDisplay ("Count={Count}")]
47 [DebuggerTypeProxy (typeof (CollectionDebuggerView
))]
48 public class SortedSet
<T
> : ISet
<T
>, ICollection
, ISerializable
, IDeserializationCallback
50 class Node
: RBTree
.Node
{
59 public override void SwapValue (RBTree
.Node other
)
68 class NodeHelper
: RBTree
.INodeHelper
<T
> {
70 static NodeHelper Default
= new NodeHelper (Comparer
<T
>.Default
);
72 public IComparer
<T
> comparer
;
74 public int Compare (T item
, RBTree
.Node node
)
76 return comparer
.Compare (item
, ((Node
) node
).item
);
79 public RBTree
.Node
CreateNode (T item
)
81 return new Node (item
);
84 NodeHelper (IComparer
<T
> comparer
)
86 this.comparer
= comparer
;
89 public static NodeHelper
GetHelper (IComparer
<T
> comparer
)
91 if (comparer
== null || comparer
== Comparer
<T
>.Default
)
94 return new NodeHelper (comparer
);
100 SerializationInfo si
;
103 : this (Comparer
<T
>.Default
)
107 public SortedSet (IEnumerable
<T
> collection
)
108 : this (collection
, Comparer
<T
>.Default
)
112 public SortedSet (IEnumerable
<T
> collection
, IComparer
<T
> comparer
)
115 if (collection
== null)
116 throw new ArgumentNullException ("collection");
118 foreach (var item
in collection
)
122 public SortedSet (IComparer
<T
> comparer
)
124 this.helper
= NodeHelper
.GetHelper (comparer
);
125 this.tree
= new RBTree (this.helper
);
128 protected SortedSet (SerializationInfo info
, StreamingContext context
)
133 public IComparer
<T
> Comparer
{
134 get { return helper.comparer; }
138 get { return tree.Count; }
146 return GetItem (tree
.Count
- 1);
159 T
GetItem (int index
)
161 return ((Node
) tree
[index
]).item
;
164 public bool Add (T item
)
166 return TryAdd (item
);
169 internal virtual bool TryAdd (T item
)
171 var node
= new Node (item
);
172 return tree
.Intern (item
, node
) == node
;
175 public virtual void Clear ()
180 public virtual bool Contains (T item
)
182 return tree
.Lookup (item
) != null;
185 public void CopyTo (T
[] array
)
187 CopyTo (array
, 0, Count
);
190 public void CopyTo (T
[] array
, int index
)
192 CopyTo (array
, index
, Count
);
195 public void CopyTo (T
[] array
, int index
, int count
)
198 throw new ArgumentNullException ("array");
200 throw new ArgumentOutOfRangeException ("index");
201 if (index
> array
.Length
)
202 throw new ArgumentException ("index larger than largest valid index of array");
203 if (array
.Length
- index
< count
)
204 throw new ArgumentException ("destination array cannot hold the requested elements");
206 foreach (Node node
in tree
) {
210 array
[index
++] = node
.item
;
214 public bool Remove (T item
)
216 return TryRemove (item
);
219 internal virtual bool TryRemove (T item
)
221 return tree
.Remove (item
) != null;
224 public int RemoveWhere (Predicate
<T
> match
)
226 var array
= ToArray ();
229 foreach (var item
in array
) {
240 public IEnumerable
<T
> Reverse ()
242 for (int i
= tree
.Count
- 1; i
>= 0; i
--)
243 yield return GetItem (i
);
248 var array
= new T
[this.Count
];
253 public Enumerator
GetEnumerator ()
255 return new Enumerator (this);
258 IEnumerator
<T
> IEnumerable
<T
>.GetEnumerator ()
260 return new Enumerator (this);
263 IEnumerator IEnumerable
.GetEnumerator ()
265 return new Enumerator (this);
268 public static IEqualityComparer
<SortedSet
<T
>> CreateSetComparer ()
270 return CreateSetComparer (EqualityComparer
<T
>.Default
);
274 public static IEqualityComparer
<SortedSet
<T
>> CreateSetComparer (IEqualityComparer
<T
> memberEqualityComparer
)
276 throw new NotImplementedException ();
280 protected virtual void GetObjectData (SerializationInfo info
, StreamingContext context
)
282 throw new NotImplementedException ();
285 void ISerializable
.GetObjectData (SerializationInfo info
, StreamingContext context
)
287 GetObjectData (info
, context
);
291 protected virtual void OnDeserialization (object sender
)
296 throw new NotImplementedException ();
299 void IDeserializationCallback
.OnDeserialization (object sender
)
301 OnDeserialization (sender
);
305 public void ExceptWith (IEnumerable
<T
> other
)
307 throw new NotImplementedException ();
311 public virtual SortedSet
<T
> GetViewBetween (T lowerValue
, T upperValue
)
313 throw new NotImplementedException ();
317 public virtual void IntersectWith (IEnumerable
<T
> other
)
319 throw new NotImplementedException ();
323 public bool IsProperSubsetOf (IEnumerable
<T
> other
)
325 throw new NotImplementedException ();
329 public bool IsProperSupersetOf (IEnumerable
<T
> other
)
331 throw new NotImplementedException ();
335 public bool IsSubsetOf (IEnumerable
<T
> other
)
337 throw new NotImplementedException ();
341 public bool IsSupersetOf (IEnumerable
<T
> other
)
343 throw new NotImplementedException ();
347 public bool Overlaps (IEnumerable
<T
> other
)
349 throw new NotImplementedException ();
353 public bool SetEquals (IEnumerable
<T
> other
)
355 throw new NotImplementedException ();
359 public void SymmetricExceptWith (IEnumerable
<T
> other
)
361 throw new NotImplementedException ();
365 public void UnionWith (IEnumerable
<T
> other
)
367 throw new NotImplementedException ();
370 void ICollection
<T
>.Add (T item
)
375 void ICollection
<T
>.CopyTo (T
[] array
, int index
)
377 CopyTo (array
, index
, Count
);
380 bool ICollection
<T
>.IsReadOnly
{
381 get { return false; }
384 void ICollection
.CopyTo (Array array
, int index
)
389 throw new ArgumentNullException ("array");
390 if (index
< 0 || array
.Length
<= index
)
391 throw new ArgumentOutOfRangeException ("index");
392 if (array
.Length
- index
< Count
)
393 throw new ArgumentException ();
395 foreach (Node node
in tree
)
396 array
.SetValue (node
.item
, index
++);
399 bool ICollection
.IsSynchronized
{
400 get { return false; }
403 // TODO:Is this correct? If this is wrong,please fix.
404 object ICollection
.SyncRoot
{
409 public struct Enumerator
: IEnumerator
<T
>, IDisposable
{
411 RBTree
.NodeEnumerator host
;
415 internal Enumerator (SortedSet
<T
> set)
417 host
= set.tree
.GetEnumerator ();
418 current
= default (T
);
422 get { return current; }
425 object IEnumerator
.Current
{
427 host
.check_current ();
428 return ((Node
) host
.Current
).item
;
432 public bool MoveNext ()
434 if (!host
.MoveNext ())
437 current
= ((Node
) host
.Current
).item
;
441 public void Dispose ()
446 void IEnumerator
.Reset ()