lucenenet-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nightowl...@apache.org
Subject [lucenenet] 02/20: Lucene.Net.Support.TreeSet: Finished implementation of ISet<T> and added tests (LUCENENET-616)
Date Tue, 03 Dec 2019 14:03:32 GMT
This is an automated email from the ASF dual-hosted git repository.

nightowl888 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucenenet.git

commit 828621412a7ba8bbad712a7bdab77ec39930bca6
Author: Shad Storhaug <shad@shadstorhaug.com>
AuthorDate: Mon Oct 28 23:26:24 2019 +0700

    Lucene.Net.Support.TreeSet: Finished implementation of ISet<T> and added tests (LUCENENET-616)
---
 src/Lucene.Net.Tests/Support/TestTreeSet.cs | 202 +++++++++++++
 src/Lucene.Net/Support/TreeSet.cs           | 429 +++++++++++++++++++++++-----
 2 files changed, 565 insertions(+), 66 deletions(-)

diff --git a/src/Lucene.Net.Tests/Support/TestTreeSet.cs b/src/Lucene.Net.Tests/Support/TestTreeSet.cs
index 156343e..0c7cd9b 100644
--- a/src/Lucene.Net.Tests/Support/TestTreeSet.cs
+++ b/src/Lucene.Net.Tests/Support/TestTreeSet.cs
@@ -2971,6 +2971,208 @@ namespace Lucene.Net.Support.RBTreeSet
                 dut = null;
             }
         }
+    }
+
+    [TestFixture]
+    public class SCGISet
+    {
+        private SCG.ISet<string> tree;
+
+        [SetUp]
+        public void Init()
+        {
+            tree = new TreeSet<string>(new SC())
+                {
+                    "A", "C", "E"
+                };
+        }
+
+        [TearDown]
+        public void Dispose()
+        {
+            tree = null;
+        }
+
+        [Test, LuceneNetSpecific]
+        public void Add()
+        {
+            Assert.IsTrue(tree.Add("Z"));
+            Assert.AreEqual(4, tree.Count);
+            Assert.IsTrue(tree.Contains("Z"));
+            Assert.IsFalse(tree.Add("A"));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void ExceptWith()
+        {
+            tree.ExceptWith(new SCG.List<string> { "C", "E", "Z" });
+            Assert.AreEqual(1, tree.Count);
+            Assert.IsTrue(tree.Contains("A"));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void IntersectWith()
+        {
+            tree.IntersectWith(new SCG.List<string> { "C", "E", "Z" });
+            Assert.AreEqual(2, tree.Count);
+            Assert.IsTrue(tree.Contains("C"));
+            Assert.IsTrue(tree.Contains("E"));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void IsProperSubsetOf()
+        {
+            Assert.IsFalse(tree.IsProperSubsetOf(new SCG.List<string>()));
+            Assert.IsFalse(tree.IsProperSubsetOf(new SCG.List<string> { "C", "E", "A"
}));
+            Assert.IsTrue(tree.IsProperSubsetOf(new SCG.List<string> { "C", "E", "A",
"X" }));
+            Assert.IsFalse(tree.IsProperSubsetOf(new SCG.List<string> { "C", "Z" }));
+            tree.Clear();
+            Assert.IsTrue(tree.IsProperSubsetOf(new SCG.List<string> { "C", "A" }));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void IsProperSupersetOf()
+        {
+            Assert.IsTrue(tree.IsProperSupersetOf(new SCG.List<string>()));
+            Assert.IsFalse(tree.IsProperSupersetOf(new SCG.List<string> { "C", "E",
"A" }));
+            Assert.IsTrue(tree.IsProperSupersetOf(new SCG.List<string> { "C", "A" }));
+            Assert.IsFalse(tree.IsProperSupersetOf(new SCG.List<string> { "C", "Z"
}));
+            tree.Clear();
+            Assert.IsFalse(tree.IsProperSupersetOf(new SCG.List<string> { "C", "A"
}));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void IsSubsetOf()
+        {
+            Assert.IsFalse(tree.IsSubsetOf(new SCG.List<string>()));
+            Assert.IsTrue(tree.IsSubsetOf(new SCG.List<string> { "C", "E", "A" }));
+            Assert.IsTrue(tree.IsSubsetOf(new SCG.List<string> { "C", "E", "A", "X"
}));
+            Assert.IsFalse(tree.IsSubsetOf(new SCG.List<string> { "C", "Z" }));
+            Assert.IsFalse(tree.IsSubsetOf(new SCG.List<string> { "C", "A", "Z" }));
+            tree.Clear();
+            Assert.IsTrue(tree.IsSubsetOf(new SCG.List<string> { "C", "A" }));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void IsSupersetOf()
+        {
+            Assert.IsTrue(tree.IsSupersetOf(new SCG.List<string>()));
+            Assert.IsTrue(tree.IsSupersetOf(new SCG.List<string> { "C", "E", "A" }));
+            Assert.IsFalse(tree.IsSupersetOf(new SCG.List<string> { "C", "E", "A",
"X" }));
+            Assert.IsFalse(tree.IsSupersetOf(new SCG.List<string> { "C", "Z" }));
+            Assert.IsTrue(tree.IsSupersetOf(new SCG.List<string> { "C", "A" }));
+            tree.Clear();
+            Assert.IsFalse(tree.IsSupersetOf(new SCG.List<string> { "C", "A" }));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void Overlaps()
+        {
+            Assert.IsFalse(tree.Overlaps(new SCG.List<string>()));
+            Assert.IsTrue(tree.Overlaps(new SCG.List<string> { "C", "E", "A" }));
+            Assert.IsTrue(tree.Overlaps(new SCG.List<string> { "C", "E", "A", "X" }));
+            Assert.IsFalse(tree.Overlaps(new SCG.List<string> { "X", "Z" }));
+            Assert.IsTrue(tree.Overlaps(new SCG.List<string> { "C", "A" }));
+            tree.Clear();
+            Assert.IsFalse(tree.Overlaps(new SCG.List<string> { "C", "A" }));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void SetEquals()
+        {
+            Assert.IsFalse(tree.SetEquals(new SCG.List<string>()));
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string> { "C", "E", "A" }));
+            Assert.IsFalse(tree.SetEquals(new SCG.List<string> { "C", "E", "A", "X"
}));
+            Assert.IsFalse(tree.SetEquals(new SCG.List<string> { "X", "Z" }));
+            Assert.IsFalse(tree.SetEquals(new SCG.List<string> { "C", "A" }));
+            tree.Clear();
+            Assert.IsFalse(tree.SetEquals(new SCG.List<string> { "C", "A" }));
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string>()));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void SymmetricExceptWith()
+        {
+            tree.SymmetricExceptWith(new SCG.List<string>());
+            Assert.AreEqual(3, tree.Count);
+            tree.SymmetricExceptWith(new SCG.List<string> { "C", "E", "R", "X" });
+            Assert.AreEqual(3, tree.Count);
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string> { "A", "R", "X" }));
+            tree.SymmetricExceptWith(new SCG.List<string>(new SCG.List<string>
{ "A", "R", "X" }));
+            Assert.AreEqual(0, tree.Count);
 
+            tree.Clear();
+            tree.SymmetricExceptWith(new SCG.List<string> { "C", "E", "A" });
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string> { "C", "E", "A" }));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void UnionWith()
+        {
+            tree.UnionWith(new SCG.List<string>());
+            Assert.AreEqual(3, tree.Count);
+            tree.UnionWith(new SCG.List<string> { "C", "E", "R", "X" });
+            Assert.AreEqual(5, tree.Count);
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string> { "A", "C", "E", "R",
"X" }));
+            tree.UnionWith(new SCG.List<string>(new SCG.List<string> { "A", "R",
"X" }));
+            Assert.AreEqual(5, tree.Count);
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string> { "A", "C", "E", "R",
"X" }));
+
+            tree.Clear();
+            tree.UnionWith(new SCG.List<string> { "C", "E", "A" });
+            Assert.IsTrue(tree.SetEquals(new SCG.List<string> { "C", "E", "A" }));
+        }
+
+        // ICollection<T> members
+        [Test, LuceneNetSpecific]
+        public void Clear()
+        {
+            Assert.AreEqual(3, tree.Count);
+            tree.Clear();
+            Assert.AreEqual(0, tree.Count);
+        }
+
+        [Test, LuceneNetSpecific]
+        public void Contains()
+        {
+            Assert.IsTrue(tree.Contains("A"));
+            Assert.IsFalse(tree.Contains("Z"));
+        }
+
+        [Test, LuceneNetSpecific]
+        public void CopyTo()
+        {
+            var values = new string[tree.Count + 2];
+            tree.CopyTo(values, 1);
+            Assert.AreEqual(null, values[0]);
+            Assert.AreEqual("A", values[1]);
+            Assert.AreEqual("C", values[2]);
+            Assert.AreEqual("E", values[3]);
+            Assert.AreEqual(null, values[4]);
+        }
+
+        [Test, LuceneNetSpecific]
+        public void Remove()
+        {
+            Assert.AreEqual(3, tree.Count);
+            Assert.IsTrue(tree.Remove("A"));
+            Assert.AreEqual(2, tree.Count);
+            Assert.IsFalse(tree.Remove("A"));
+            Assert.AreEqual(2, tree.Count);
+        }
+
+        [Test, LuceneNetSpecific]
+        public void Count()
+        {
+            Assert.AreEqual(3, tree.Count);
+            tree.Add("Foo");
+            Assert.AreEqual(4, tree.Count);
+        }
+
+        [Test, LuceneNetSpecific]
+        public void IsReadOnly()
+        {
+            Assert.AreEqual(false, tree.IsReadOnly);
+        }
     }
 }
\ No newline at end of file
diff --git a/src/Lucene.Net/Support/TreeSet.cs b/src/Lucene.Net/Support/TreeSet.cs
index c1532f3..1b89cdc 100644
--- a/src/Lucene.Net/Support/TreeSet.cs
+++ b/src/Lucene.Net/Support/TreeSet.cs
@@ -553,37 +553,122 @@ namespace Lucene.Net.Support
         /// <summary>
         /// Modifies the current <see cref="TreeSet{T}"/> object to contain all elements
that are present in itself, the specified collection, or both.
         /// </summary>
-        /// <param name="other"></param>
-        public void UnionWith(SCG.IEnumerable<T> other)
+        /// <param name="other">The collection to compare to the current set.</param>
+        public virtual void UnionWith(SCG.IEnumerable<T> other)
         {
+            if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
             AddAll(other);
         }
 
         /// <summary>
-        /// Not implemented
+        /// Modifies the current <see cref="TreeSet{T}"/> object so that it contains
only elements that are also in a specified collection.
         /// </summary>
-        /// <param name="other"></param>
-        public void IntersectWith(SCG.IEnumerable<T> other)
+        /// <param name="other">The collection to compare to the current set.</param>
+        public virtual void IntersectWith(SCG.IEnumerable<T> other)
         {
-            throw new NotImplementedException("Implement as required");
+            if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+            // intersection of anything with empty set is empty set, so return if count is
0
+            if (this.size == 0)
+            {
+                return;
+            }
+
+            // if other is empty, intersection is empty set; remove all elements and we're
done
+            // can only figure this out if implements ICollection<T>. (IEnumerable<T>
has no count)
+            var otherAsCollection = other as SCG.ICollection<T>;
+            if (otherAsCollection != null)
+            {
+                if (otherAsCollection.Count == 0)
+                {
+                    Clear();
+                    return;
+                }
+
+                var otherAsSet = other as TreeSet<T>;
+                // faster if other is a hashset using same equality comparer; so check 
+                // that other is a hashset using the same equality comparer.
+                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
+                {
+                    IntersectWithHashSetWithSameEC(otherAsSet);
+                    return;
+                }
+            }
+
+            IntersectWithEnumerable(other);
         }
 
         /// <summary>
-        /// Not implemented
+        /// Removes all elements in the specified collection from the current <see cref="TreeSet{T}"/>
object.
         /// </summary>
-        /// <param name="other"></param>
-        public void ExceptWith(SCG.IEnumerable<T> other)
+        /// <param name="other">The collection of items to remove from the set.</param>
+        public virtual void ExceptWith(SCG.IEnumerable<T> other)
         {
-            throw new NotImplementedException("Implement as required");
+            if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+            // this is already the enpty set; return
+            if (this.size == 0)
+                return;
+
+            // special case if other is this; a set minus itself is the empty set
+            if (other == this)
+            {
+                Clear();
+                return;
+            }
+
+            // remove every element in other from this
+            foreach (T element in other)
+            {
+                Remove(element);
+            }
         }
 
         /// <summary>
-        /// Not implemented
+        /// Modifies the current set so that it contains only elements that are present either
in the current 
+        /// <see cref="TreeSet{T}"/> object or in the specified collection, but not
both.
         /// </summary>
-        /// <param name="other"></param>
-        public void SymmetricExceptWith(SCG.IEnumerable<T> other)
+        /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>
object.</param>
+        public virtual void SymmetricExceptWith(SCG.IEnumerable<T> other)
         {
-            throw new NotImplementedException("Implement as required");
+            if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+            // if set is empty, then symmetric difference is other
+            if (this.size == 0)
+            {
+                UnionWith(other);
+                return;
+            }
+
+            // special case this; the symmetric difference of a set with itself is the empty
set
+            if (other == this)
+            {
+                Clear();
+                return;
+            }
+
+            var otherAsSet = other as TreeSet<T>;
+            // If other is a HashSet, it has unique elements according to its equality comparer,
+            // but if they're using different equality comparers, then assumption of uniqueness
+            // will fail. So first check if other is a hashset using the same equality comparer;
+            // symmetric except is a lot faster and avoids bit array allocations if we can
assume
+            // uniqueness
+            if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
+            {
+                SymmetricExceptWithUniqueTreeSet(otherAsSet);
+            }
+            else
+            {
+                var temp = new SCG.SortedSet<T>(other, comparer);
+                temp.ExceptWith(this);
+                this.ExceptWith(other);
+                this.UnionWith(temp);
+            }
         }
 
         /// <summary>
@@ -591,22 +676,39 @@ namespace Lucene.Net.Support
         /// </summary>
         /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>
object.</param>
         /// <returns><c>true</c> if the <see cref="TreeSet{T}"/>
object is a subset of other; otherwise, <c>false</c>.</returns>
-        public bool IsSubsetOf(SCG.IEnumerable<T> other)
+        public virtual bool IsSubsetOf(SCG.IEnumerable<T> other)
         {
             if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+            if (this.size == 0)
             {
-                throw new ArgumentNullException("other");
+                return true;
             }
-            if (this.Count == 0)
+
+            var otherAsSet = other as TreeSet<T>;
+            // faster if other has unique elements according to this equality comparer; so
check 
+            // that other is a hashset using the same equality comparer.
+            if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
             {
-                return true;
+                // if this has more elements then it can't be a subset
+                if (this.size > otherAsSet.Count)
+                {
+                    return false;
+                }
+
+                // already checked that we're using same equality comparer. simply check
that 
+                // each element in this is contained in other.
+                return IsSubsetOfTreeSetWithSameEC(otherAsSet);
+            }
+            else
+            {
+                // we just need to return true if the other set
+                // contains all of the elements of the this set,
+                // but we need to use the comparison rules of the current set.
+                this.CheckUniqueAndUnfoundElements(other, false, out int uniqueCount, out
int unfoundCount);
+                return uniqueCount == this.size;
             }
-            // we just need to return true if the other set
-            // contains all of the elements of the this set,
-            // but we need to use the comparison rules of the current set.
-            int foundCount, unfoundCount;
-            this.GetFoundAndUnfoundCounts(other, out foundCount, out unfoundCount);
-            return foundCount == this.Count;
         }
 
         /// <summary>
@@ -614,17 +716,31 @@ namespace Lucene.Net.Support
         /// </summary>
         /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>
object.</param>
         /// <returns><c>true</c> if the <see cref="TreeSet{T}"/>
object is a superset of other; otherwise, <c>false</c>.</returns>
-        public bool IsSupersetOf(SCG.IEnumerable<T> other)
+        public virtual bool IsSupersetOf(SCG.IEnumerable<T> other)
         {
             if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+            // try to fall out early based on counts
+            var is2 = other as SCG.ICollection<T>;
+            if (is2 != null)
             {
-                throw new ArgumentNullException("other");
-            }
-            ICollection<T> is2 = other as ICollection<T>;
-            if (is2 != null && is2.Count == 0)
-            {
-                return true;
+                // if other is the empty set then this is a superset
+                if (is2.Count == 0)
+                    return true;
+
+                var otherAsSet = other as TreeSet<T>;
+                // try to compare based on counts alone if other is a hashset with
+                // same equality comparer
+                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
+                {
+                    if (otherAsSet.Count > this.size)
+                    {
+                        return false;
+                    }
+                }
             }
+
             return this.ContainsAll(other);
         }
 
@@ -633,24 +749,40 @@ namespace Lucene.Net.Support
         /// </summary>
         /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>
object.</param>
         /// <returns><c>true</c> if the <see cref="TreeSet{T}"/>
object is a proper superset of other; otherwise, <c>false</c>.</returns>
-        public bool IsProperSupersetOf(SCG.IEnumerable<T> other)
+        public virtual bool IsProperSupersetOf(SCG.IEnumerable<T> other)
         {
             if (other == null)
-            {
-                throw new ArgumentNullException("other");
-            }
-            if (this.Count == 0)
+                throw new ArgumentNullException(nameof(other));
+
+            // the empty set isn't a proper superset of any set.
+            if (this.size == 0)
             {
                 return false;
             }
-            ICollection<T> is2 = other as ICollection<T>;
-            if (is2 != null && is2.Count == 0)
+
+            var otherAsCollection = other as SCG.ICollection<T>;
+            if (otherAsCollection != null)
             {
-                return true;
+                // if other is the empty set then this is a superset
+                if (otherAsCollection.Count == 0)
+                    return true; // note that this has at least one element, based on above
check
+
+                var otherAsSet = other as TreeSet<T>;
+                // faster if other is a hashset with the same equality comparer
+                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
+                {
+                    if (otherAsSet.Count >= this.size)
+                    {
+                        return false;
+                    }
+                    // now perform element check
+                    return ContainsAll(otherAsSet);
+                }
             }
-            int foundCount, unfoundCount;
-            this.GetFoundAndUnfoundCounts(other, out foundCount, out unfoundCount);
-            return foundCount < this.Count && unfoundCount == 0;
+
+            // couldn't fall out in the above cases; do it the long way
+            this.CheckUniqueAndUnfoundElements(other, true, out int uniqueCount, out int
unfoundCount);
+            return uniqueCount < this.size && unfoundCount == 0;
         }
 
         /// <summary>
@@ -658,23 +790,35 @@ namespace Lucene.Net.Support
         /// </summary>
         /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>
object.</param>
         /// <returns><c>true</c> if the <see cref="TreeSet{T}"/>
object is a proper subset of other; otherwise, <c>false</c>.</returns>
-        public bool IsProperSubsetOf(SCG.IEnumerable<T> other)
+        public virtual bool IsProperSubsetOf(SCG.IEnumerable<T> other)
         {
             if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+
+            var otherAsCollection = other as SCG.ICollection<T>;
+            if (otherAsCollection != null)
             {
-                throw new ArgumentNullException("other");
-            }
-            ICollection<T> is2 = other as ICollection<T>;
-            if (is2 != null && this.Count == 0)
-            {
-                return (is2.Count > 0);
+                // the empty set is a proper subset of anything but the empty set
+                if (this.size == 0)
+                    return otherAsCollection.Count > 0;
+
+                var otherAsSet = other as TreeSet<T>;
+                // faster if other is a hashset (and we're using same equality comparer)
+                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
+                {
+                    if (this.size >= otherAsSet.Count)
+                    {
+                        return false;
+                    }
+                    // this has strictly less than number of items in other, so the following
+                    // check suffices for proper subset.
+                    return IsSubsetOfTreeSetWithSameEC(otherAsSet);
+                }
             }
-            // we just need to return true if the other set
-            // contains all of the elements of the this set plus at least one more,
-            // but we need to use the comparison rules of the current set.
-            int foundCount, unfoundCount;
-            this.GetFoundAndUnfoundCounts(other, out foundCount, out unfoundCount);
-            return foundCount == this.Count && unfoundCount > 0;
+
+            this.CheckUniqueAndUnfoundElements(other, false, out int uniqueCount, out int
unfoundCount);
+            return uniqueCount == this.size && unfoundCount > 0;
         }
 
         /// <summary>
@@ -682,13 +826,12 @@ namespace Lucene.Net.Support
         /// </summary>
         /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>
object.</param>
         /// <returns><c>true</c> if the <see cref="TreeSet{T}"/>
object and other share at least one common element; otherwise, <c>false</c>.</returns>
-        public bool Overlaps(SCG.IEnumerable<T> other)
+        public virtual bool Overlaps(SCG.IEnumerable<T> other)
         {
             if (other == null)
-            {
-                throw new ArgumentNullException("other");
-            }
-            if (this.Count != 0)
+                throw new ArgumentNullException(nameof(other));
+
+            if (this.size != 0)
             {
                 foreach (var local in other)
                 {
@@ -706,28 +849,182 @@ namespace Lucene.Net.Support
         /// </summary>
         /// <param name="other">The collection to compare to the current <see cref="TreeSet{T}"/>.</param>
         /// <returns><c>true</c> if the current <see cref="TreeSet{T}"/>
is equal to other; otherwise, <c>false</c>.</returns>
-        public bool SetEquals(SCG.IEnumerable<T> other)
+        public virtual bool SetEquals(SCG.IEnumerable<T> other)
         {
-            return this.Count.Equals(other.Count()) && this.ContainsAll(other);
+            if (other == null)
+                throw new ArgumentNullException(nameof(other));
+
+            var otherAsSet = other as TreeSet<T>;
+            // faster if other is a hashset and we're using same equality comparer
+            if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
+            {
+                // attempt to return early: since both contain unique elements, if they have

+                // different counts, then they can't be equal
+                if (this.size != otherAsSet.Count)
+                    return false;
+
+                // already confirmed that the sets have the same number of distinct elements,
so if
+                // one is a superset of the other then they must be equal
+                return ContainsAll(otherAsSet);
+            }
+            else
+            {
+                var otherAsCollection = other as SCG.ICollection<T>;
+                if (otherAsCollection != null)
+                {
+                    // if this count is 0 but other contains at least one element, they can't
be equal
+                    if (this.size == 0 && otherAsCollection.Count > 0)
+                        return false;
+                }
+
+                this.CheckUniqueAndUnfoundElements(other, true, out int uniqueCount, out
int unfoundCount);
+                return uniqueCount == this.size && unfoundCount == 0;
+            }
         }
 
-        private void GetFoundAndUnfoundCounts(SCG.IEnumerable<T> other, out int foundCount,
out int unfoundCount)
+        private void CheckUniqueAndUnfoundElements(SCG.IEnumerable<T> other, bool returnIfUnfound,
out int uniqueCount, out int unfoundCount)
         {
-            foundCount = 0;
+            // need special case in case this has no elements.
+            if (this.size == 0)
+            {
+                int numElementsInOther = 0;
+                foreach (T item in other)
+                {
+                    numElementsInOther++;
+                    // break right away, all we want to know is whether other has 0 or 1
elements
+                    break;
+                }
+                uniqueCount = 0;
+                unfoundCount = numElementsInOther;
+                return;
+            }
+
+            int originalLastIndex = this.size;
+            var bitArray = new System.Collections.BitArray(originalLastIndex, false);
+
+            // count of unique items in other found in this
+            uniqueCount = 0;
+            // count of items in other not found in this
             unfoundCount = 0;
+
             foreach (var item in other)
             {
-                if (this.Contains(item))
+                var index = IndexOf(item);
+                if (index >= 0)
                 {
-                    foundCount++;
+                    if (!bitArray.Get(index))
+                    {
+                        // item hasn't been seen yet
+                        bitArray.Set(index, true);
+                        uniqueCount++;
+                    }
                 }
                 else
                 {
                     unfoundCount++;
+                    if (returnIfUnfound)
+                        break;
                 }
             }
         }
 
+        /// <summary>
+        /// Checks if equality comparers are equal. This is used for algorithms that can
+        /// speed up if it knows the other item has unique elements. I.e. if they're using

+        /// different equality comparers, then uniqueness assumption between sets break.
+        /// </summary>
+        /// <param name="set1"></param>
+        /// <param name="set2"></param>
+        /// <returns></returns>
+        private static bool AreEqualityComparersEqual(TreeSet<T> set1, TreeSet<T>
set2)
+        {
+            return set1.Comparer.Equals(set2.Comparer);
+        }
+
+        /// <summary>
+        /// If other is a hashset that uses same equality comparer, intersect is much faster

+        /// because we can use other's Contains
+        /// </summary>
+        /// <param name="other"></param>
+        private void IntersectWithHashSetWithSameEC(TreeSet<T> other)
+        {
+            foreach (var item in this)
+            {
+                if (!other.Contains(item))
+                {
+                    Remove(item);
+                }
+            }
+        }
+
+        private void IntersectWithEnumerable(SCG.IEnumerable<T> other)
+        {
+            // keep track of current last index; don't want to move past the end of our bit
array
+            // (could happen if another thread is modifying the collection)
+            int originalLastIndex = this.size;
+            var bitArray = new System.Collections.BitArray(originalLastIndex, false);
+
+            foreach (var item in other)
+            {
+                int index = IndexOf(item);
+                if (index >= 0)
+                    bitArray.Set(index, true);
+            }
+
+            // if anything unmarked, remove it.
+            for (int i = originalLastIndex - 1; i >= 0; i--)
+            {
+                if (!bitArray.Get(i))
+                    RemoveAt(i);
+            }
+        }
+
+        /// <summary>
+        /// if other is a set, we can assume it doesn't have duplicate elements, so use this
+        /// technique: if can't remove, then it wasn't present in this set, so add.
+        /// 
+        /// As with other methods, callers take care of ensuring that other is a hashset
using the
+        /// same equality comparer.
+        /// </summary>
+        /// <param name="other"></param>
+        private void SymmetricExceptWithUniqueTreeSet(TreeSet<T> other)
+        {
+            foreach (T item in other)
+            {
+                if (!Remove(item))
+                {
+                    Add(item);
+                }
+            }
+        }
+
+        /// <summary>
+        /// Implementation Notes:
+        /// If other is a hashset and is using same equality comparer, then checking subset
is 
+        /// faster. Simply check that each element in this is in other.
+        /// 
+        /// Note: if other doesn't use same equality comparer, then Contains check is invalid,
+        /// which is why callers must take are of this.
+        /// 
+        /// If callers are concerned about whether this is a proper subset, they take care
of that.
+        ///
+        /// </summary>
+        /// <param name="other"></param>
+        /// <returns></returns>
+        private bool IsSubsetOfTreeSetWithSameEC(TreeSet<T> other)
+        {
+
+            foreach (T item in this)
+            {
+                if (!other.Contains(item))
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+
         #endregion
 
         #region IEnumerable<T> Members


Mime
View raw message