//
// Authors:
// Jb Evain <jbevain@novell.com>
+// Marek Safar (marek.safar@gmail.com)
//
// Copyright (C) 2010 Novell, Inc (http://www.novell.com)
+// Copyright (C) 2014 Xamarin Inc (http://www.xamarin.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
using System;
using System.Collections;
using System.Collections.Generic;
-using System.Linq;
using System.Runtime.Serialization;
using System.Runtime.InteropServices;
using System.Security;
}
public int Count {
- get { return tree.Count; }
+ get { return GetCount (); }
}
public T Max {
return GetItem (0);
}
+ internal virtual int GetCount ()
+ {
+ return tree.Count;
+ }
+
T GetItem (int index)
{
return ((Node) tree [index]).item;
}
public Enumerator GetEnumerator ()
+ {
+ return TryGetEnumerator ();
+ }
+
+ internal virtual Enumerator TryGetEnumerator ()
{
return new Enumerator (this);
}
IEnumerator<T> IEnumerable<T>.GetEnumerator ()
{
- return new Enumerator (this);
+ return GetEnumerator ();
}
IEnumerator IEnumerable.GetEnumerator ()
{
- return new Enumerator (this);
+ return GetEnumerator ();
}
public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
[MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
public void ExceptWith (IEnumerable<T> other)
{
+ if (other == this) {
+ Clear ();
+ return;
+ }
+
CheckArgumentNotNull (other, "other");
foreach (T item in other)
Remove (item);
[MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
public void SymmetricExceptWith (IEnumerable<T> other)
{
+ if (other == this) {
+ Clear ();
+ return;
+ }
+
SortedSet<T> that_minus_this = new SortedSet<T> (Comparer);
// compute this - that and that - this in parallel
{
Add (item);
}
-
- void ICollection<T>.CopyTo (T [] array, int index)
- {
- CopyTo (array, index, Count);
- }
-
+
bool ICollection<T>.IsReadOnly {
get { return false; }
}
RBTree.NodeEnumerator host;
+ IComparer<T> comparer;
+
T current;
+ T upper;
internal Enumerator (SortedSet<T> set)
+ : this ()
{
host = set.tree.GetEnumerator ();
- current = default (T);
+ }
+
+ internal Enumerator (SortedSet<T> set, T lower, T upper)
+ : this ()
+ {
+ host = set.tree.GetSuffixEnumerator (lower);
+ comparer = set.Comparer;
+ this.upper = upper;
}
public T Current {
return false;
current = ((Node) host.Current).item;
- return true;
+ return comparer == null || comparer.Compare (upper, current) >= 0;
}
public void Dispose ()
this.set = set;
this.lower = lower;
this.upper = upper;
+
}
internal override T GetMin ()
{
- for (int i = 0; i < set.tree.Count; i++) {
- var item = set.GetItem (i);
- if (InRange (item))
- return item;
- }
+ RBTree.Node lb = null, ub = null;
+ set.tree.Bound (lower, ref lb, ref ub);
- return default (T);
+ if (ub == null || set.helper.Compare (upper, ub) < 0)
+ return default (T);
+
+ return ((Node) ub).item;
}
internal override T GetMax ()
{
- for (int i = set.tree.Count - 1; i >= 0; i--) {
- var item = set.GetItem (i);
- if (InRange (item))
- return item;
- }
+ RBTree.Node lb = null, ub = null;
+ set.tree.Bound (upper, ref lb, ref ub);
- return default (T);
+ if (lb == null || set.helper.Compare (lower, lb) > 0)
+ return default (T);
+
+ return ((Node) lb).item;
+ }
+
+ internal override int GetCount ()
+ {
+ int count = 0;
+ using (var e = set.tree.GetSuffixEnumerator (lower)) {
+ while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
+ ++count;
+ }
+ return count;
}
internal override bool TryAdd (T item)
return new SortedSubSet (set, lowerValue, upperValue);
}
- public IEnumerator<T> GetEnumerator ()
- {
- var yielding = false;
-
- foreach (Node node in set.tree) {
- var item = node.item;
-
- if (InRange (item)) {
- yield return item;
- yielding = true;
- } else if (yielding)
- yield break;
- }
- }
-
- IEnumerator<T> IEnumerable<T>.GetEnumerator ()
- {
- return GetEnumerator ();
- }
-
- IEnumerator IEnumerable.GetEnumerator ()
+ internal override Enumerator TryGetEnumerator ()
{
- return GetEnumerator ();
+ return new Enumerator (set, lower, upper);
}
public override void IntersectWith (IEnumerable<T> other)