/* **********************************************************************************
 *
 * Copyright (c) Microsoft Corporation. All rights reserved.
 *
 * This source code is subject to terms and conditions of the Shared Source License
 * for IronPython. A copy of the license can be found in the License.html file
 * at the root of this distribution. If you can not locate the Shared Source License
 * for IronPython, please send an email to ironpy@microsoft.com.
 * By using this source code in any fashion, you are agreeing to be bound by
 * the terms of the Shared Source License for IronPython.
 *
 * You must not remove this notice, or any other, from this software.
 *
 * **********************************************************************************/

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Reflection;
using System.Collections;
using System.Text;

namespace IronPython.Runtime {

    /// <summary>
    /// Common interface shared by both Set and FrozenSet
    /// </summary>
    public interface ISet : IEnumerable {
        int GetLength();

        bool Contains(object o);
        bool IsSubset(object s);
        bool IsSuperset(object s);

        // private methods used for operations between set types.
        ISet PrivDifference(IEnumerable s);
        ISet PrivIntersection(IEnumerable s);
        ISet PrivSymmetricDifference(IEnumerable s);
        ISet PrivUnion(IEnumerable s);
        void PrivAdd(object o);
        void PrivRemove(object o);
        void PrivFreeze();

        void SetData(Dictionary<object, object> dict);
        void SetData(IEnumerator set);
    }

    /// <summary>
    /// Contains common set functionality between set and forzenSet
    /// </summary>
    static class SetHelpers {
        public static string SetToString(object set, IEnumerable items) {
            string setTypeStr;
            Type setType = set.GetType();
            if (setType == typeof(SetCollection)) {
                setTypeStr = "set";
            } else if (setType == typeof(FrozenSetCollection)) {
                setTypeStr = "frozenset";
            } else {
                setTypeStr = Ops.GetDynamicType(set).__name__.ToString();
            }
            StringBuilder sb = new StringBuilder();
            sb.Append(setTypeStr);
            sb.Append("([");
            string comma = "";
            foreach (object o in items) {
                sb.Append(comma);
                sb.Append(Ops.Repr(o));
                comma = ", ";
            }
            sb.Append("])");

            return sb.ToString();
        }

        /// <summary>
        /// Creates a set that can be hashable.  If the set is currently a FrozenSet the
        /// set is returned.  If the set is a normal Set then a FrozenSet is returned
        /// with its contents.
        /// </summary>
        /// <param name="o"></param>
        /// <returns></returns>
        public static object GetHashableSetIfSet(object o) {
            SetCollection asSet = o as SetCollection;
            if (asSet != null) {
                return FrozenSetCollection.Make(asSet.GetEnumerator());
            }
            return o;
        }

        public static ISet MakeSet(object setObj) {
            Type t = setObj.GetType();
            if (t == typeof(SetCollection)) {
                return new SetCollection();
            } else if (t == typeof(FrozenSetCollection)) {
                return new FrozenSetCollection();
            } else {
                // subclass                
                UserType ut = Ops.GetDynamicType(setObj) as UserType;
                Debug.Assert(ut != null);

                ISet set = ut.Call() as ISet;
                Debug.Assert(set != null);

                return set;
            }
        }

        public static ISet MakeSet(object setObj, ISet set) {
            Type t = setObj.GetType();
            if (t == typeof(SetCollection)) {
                return new SetCollection(set);
            } else if (t == typeof(FrozenSetCollection)) {
                return new FrozenSetCollection(set);
            } else {
                // subclass                
                UserType ut = Ops.GetDynamicType(setObj) as UserType;
                Debug.Assert(ut != null);
                ISet res = ut.Call(new object[] { }) as ISet;

                Debug.Assert(res != null);
                res.SetData(set.GetEnumerator());
                return res;
            }
        }

        public static ISet Intersection(ISet x, object y) {
            ISet res = SetHelpers.MakeSet(x);

            IEnumerator ie = Ops.GetEnumerator(y);
            while (ie.MoveNext()) {
                if (x.Contains(ie.Current))
                    res.PrivAdd(ie.Current);
            }
            res.PrivFreeze();
            return res;
        }

        public static ISet Difference(ISet x, object y) {
            ISet res = SetHelpers.MakeSet(x, x) as ISet;
            Debug.Assert(res != null);

            IEnumerator ie = Ops.GetEnumerator(y);
            while (ie.MoveNext()) {
                if (res.Contains(ie.Current)) {
                    res.PrivRemove(ie.Current);
                }
            }
            res.PrivFreeze();
            return res;
        }

        public static ISet SymmetricDifference(ISet x, object y) {
            SetCollection otherSet = new SetCollection(Ops.GetEnumerator(y));       //make a set to deal w/ dups in the enumerator
            ISet res = SetHelpers.MakeSet(x, x) as ISet;
            Debug.Assert(res != null);

            foreach (object o in otherSet) {
                if (res.Contains(o)) {
                    res.PrivRemove(o);
                } else {
                    res.PrivAdd(o);
                }
            }
            res.PrivFreeze();
            return res;
        }

        public static ISet Union(ISet x, object y) {
            ISet set = SetHelpers.MakeSet(x, x);
            IEnumerator ie = Ops.GetEnumerator(y);
            while (ie.MoveNext()) {
                set.PrivAdd(ie.Current);
            }
            set.PrivFreeze();
            return set;
        }

        public static bool IsSubset(ISet x, object y) {
            SetCollection set = new SetCollection(Ops.GetEnumerator(y));
            foreach (object o in x) {
                if (!set.Contains(o)) {
                    return false;
                }
            }
            return true;
        }
    }

    /// <summary>
    /// Mutable set class
    /// </summary>
    [PythonType("set")]
    public class SetCollection : ISet, IPythonComparable, IPythonEquality {
        IDictionary<object, object> items;

        #region Set contruction

        [PythonName("__init__")]
        public void Initialize() {
            Clear();
        }

        [PythonName("__init__")]
        public void Initialize(object setData) {
            Clear();
            Update(setData);
        }

        public SetCollection() {
            items = new Dict();
        }

        internal SetCollection(object setData) {
            Init(setData);
        }

        internal SetCollection(IEnumerator setData) {
            items = new Dict();
            while (setData.MoveNext()) {
                Add(setData.Current);
            }
        }

        internal SetCollection(Dictionary<object, object> setData) {
            items = setData;
        }

        #endregion

        #region ISet
        [PythonName("len")]
        public int GetLength() {
            return items.Count;
        }

        [PythonName("__contains__")]
        public bool Contains(object o) {
            // promote sets to FrozenSet's for contains checks (so we get a hash code)
            o = SetHelpers.GetHashableSetIfSet(o);

            Ops.Hash(o);    // make sure we have a hashable item
            return items.ContainsKey(o);
        }
        [PythonName("issubset")]
        public bool IsSubset(object s) {
            return SetHelpers.IsSubset(this, s);
        }
        [PythonName("issuperset")]
        public bool IsSuperset(object s) {
            return (bool) GreaterThanOrEqual(new SetCollection(Ops.GetEnumerator(s)));
        }

        ISet ISet.PrivDifference(IEnumerable s) {
            return Difference(s);
        }
        ISet ISet.PrivIntersection(IEnumerable s) {
            return Intersection(s);
        }
        ISet ISet.PrivSymmetricDifference(IEnumerable s) {
            return SymmetricDifference(s);
        }
        ISet ISet.PrivUnion(IEnumerable s) {
            return Union(s);
        }
        void ISet.PrivAdd(object o) {
            Add(o);
        }
        void ISet.PrivRemove(object o) {
            Remove(o);
        }
        void ISet.PrivFreeze() {
            // nop for non-frozen sets.
        }

        void ISet.SetData(Dictionary<object, object> dict) {
            items = dict;
        }

        void ISet.SetData(IEnumerator set) {
            items = new Dictionary<object, object>();
            while (set.MoveNext()) {
                items[set.Current] = set.Current;
            }
        }


        #endregion

        #region NonOperator Operations

        [PythonName("union")]
        public ISet Union(object s) {
            return SetHelpers.Union(this, s);
        }

        [PythonName("intersection")]
        public ISet Intersection(object s) {
            return SetHelpers.Intersection(this, s);
        }

        [PythonName("difference")]
        public ISet Difference(object s) {
            return SetHelpers.Difference(this, s);
        }

        [PythonName("symmetric_difference")]
        public ISet SymmetricDifference(object s) {
            return SetHelpers.SymmetricDifference(this, s);
        }

        [PythonName("copy")]
        public SetCollection Copy() {
            return new SetCollection(this.GetEnumerator());
        }

        [PythonName("__reduce__")]
        public Tuple Reduce() {
            object[] keys = new object[items.Keys.Count];
            items.Keys.CopyTo(keys, 0);

            return Tuple.MakeTuple(new object[] { 
                TypeCache.Set, 
                Tuple.MakeTuple(new List(keys)), 
                null });
        }

        [PythonName("__reduce_ex__")]
        public Tuple ReduceEx(object proto) {
            return Reduce();
        }

        private void Init(params object[] o) {
            if (o.Length > 1) throw Ops.TypeError("set expected at most 1 arguments, got {0}", o.Length);

            items = new Dictionary<object, object>();
            if (o.Length != 0) {
                IEnumerator setData = Ops.GetEnumerator(o[0]);
                while (setData.MoveNext()) {
                    Add(setData.Current);
                }
            }
        }

        public int __len__() {
            return GetLength();
        }

        #endregion

        #region Mutating Members
        /// <summary>
        /// Appends one IEnumerable to an existing set
        /// </summary>
        /// <param name="s"></param>
        [PythonName("update")]
        public void Update(object s) {
            IEnumerator ie = Ops.GetEnumerator(s);
            while (ie.MoveNext()) {
                object o = ie.Current;
                if (!Contains(o)) {
                    Add(o);
                }
            }
        }

        [PythonName("add")]
        public void Add(object o) {
            if (o == null) o = NoneType.InstanceOfNoneType;

            Ops.Hash(o);// make sure we're hashable
            if (!items.ContainsKey(o)) {
                items.Add(o, o);
            }
        }

        [PythonName("intersection_update")]
        public void IntersectionUpdate(object s) {
            SetCollection set = Intersection(s) as SetCollection;
            items = set.items;
        }

        [PythonName("difference_update")]
        public void DifferenceUpdate(object s) {
            SetCollection set = new SetCollection(Ops.GetEnumerator(s));
            foreach (object o in set) {
                if (Contains(o)) {
                    Remove(o);
                }
            }
        }

        [PythonName("symmetric_difference_update")]
        public void SymmetricDifferenceUpdate(object s) {
            SetCollection set = new SetCollection(Ops.GetEnumerator(s));
            foreach (object o in set) {
                if (Contains(o)) {
                    Remove(o);
                } else {
                    Add(o);
                }
            }
        }

        [PythonName("remove")]
        public void Remove(object o) {
            o = SetHelpers.GetHashableSetIfSet(o);

            Ops.Hash(o);
            if (!items.ContainsKey(o)) throw Ops.KeyError("{0}", o.ToString());

            items.Remove(o);
        }

        [PythonName("discard")]
        public void Discard(object o) {
            o = SetHelpers.GetHashableSetIfSet(o);

            items.Remove(o);
        }

        [PythonName("pop")]
        public object Pop() {
            foreach (object o in items.Keys) {
                items.Remove(o);
                return o;
            }
            throw Ops.KeyError("pop from an empty set");
        }

        [PythonName("clear")]
        public void Clear() {
            items.Clear();
        }
        #endregion

        #region Operators

        [PythonName("__iand__")]
        public SetCollection __iand__(ISet s) {
            IntersectionUpdate(s);
            return this;
        }

        [PythonName("__ior__")]
        public SetCollection __ior__(ISet s) {
            Update(s);
            return this;
        }

        [PythonName("__isub__")]
        public SetCollection __isub__(ISet s) {
            DifferenceUpdate(s);
            return this;
        }

        [PythonName("__ixor__")]
        public SetCollection __ixor__(ISet s) {
            SymmetricDifferenceUpdate(s);
            return this;
        }

        [PythonName("__cmp__")]
        public int __cmp__(object o) {
            throw Ops.TypeError("cannot compare sets using cmp()");
        }

        [PythonName("__and__")]
        public ISet __and__(ISet s) {
            if (s.GetLength() < GetLength()) {
                return Intersection(s);
            }

            SetCollection set = s as SetCollection;
            if (set != null) {
                return set.Intersection(this);
            }

            return SetHelpers.MakeSet(this, s.PrivIntersection(this));
        }

        [PythonName("__ror__")]
        public ISet __ror__(ISet s) {
            if (s.GetLength() < GetLength()) {
                return Union(s);
            }

            SetCollection set = s as SetCollection;
            if (set != null) {
                return set.Union(this);
            }

            return SetHelpers.MakeSet(this, s.PrivUnion(this));
        }

        [PythonName("__rsub__")]
        public ISet __rsub__(ISet s) {
            SetCollection set = s as SetCollection;
            if (set != null) {
                return set.Difference(this);
            }

            return SetHelpers.MakeSet(this, s.PrivDifference(this));
        }

        [PythonName("__rxor__")]
        public ISet __rxor__(ISet s) {
            if (s.GetLength() < GetLength()) {
                return SymmetricDifference(s);
            }
            SetCollection set = s as SetCollection;
            if (set != null) {
                return set.SymmetricDifference(this);
            }

            return SetHelpers.MakeSet(this, s.PrivSymmetricDifference(this));
        }

        #endregion

        #region IEnumerable Members

        public IEnumerator GetEnumerator() {
            return items.Keys.GetEnumerator();
        }

        #endregion

        #region Object overrides
        [PythonName("__str__")]
        public override string ToString() {
            return (SetHelpers.SetToString(this, this.items.Keys));
        }

        #endregion

        #region IPythonComparable
        object IPythonComparable.CompareTo(object other) {
            throw Ops.TypeError("cannot compare sets using cmp()");
        }

        [PythonName("__gt__")]
        public object GreaterThan(object other) {
            ISet s = other as ISet;
            if (s == null) throw Ops.TypeError("can only compare to a set");

            if (s.GetLength() >= GetLength()) return false;

            foreach (object o in s) {
                if (!Contains(o)) return false;
            }
            return true;
        }

        [PythonName("__lt__")]
        public object LessThan(object other) {
            ISet s = other as ISet;
            if (s == null) throw Ops.TypeError("can only compare to a set");

            if (s.GetLength() <= GetLength()) return false;

            foreach (object o in this) {
                if (!s.Contains(o)) {
                    return false;
                }
            }
            return true;
        }
        [PythonName("__ge__")]
        public object GreaterThanOrEqual(object other) {
            return ((bool)GreaterThan(other)) || ((bool)PythonEquals(other));
        }

        [PythonName("__le__")]
        public object LessThanOrEqual(object other) {
            return ((bool)LessThan(other)) || ((bool)PythonEquals(other));
        }

        [PythonName("__ne__")]
        public bool NotEquals(object other) {
            return !((bool)PythonEquals(other));
        }

        #endregion

        #region IPythonEquality Members
        [PythonName("__hash__")]
        public object PythonGetHashCode() {
            throw Ops.TypeError("set objects are unhashable");
        }

        [PythonName("__eq__")]
        public object PythonEquals(object other) {
            ISet set = other as ISet;
            if (set != null) {
                if (set.GetLength() != GetLength()) return false;
                return set.IsSubset(this) && this.IsSubset(set);
            }
            return false;
        }

        #endregion
    }


    /// <summary>
    /// Non-mutable set class
    /// </summary>
    [PythonType("frozenset")]
    public class FrozenSetCollection : ISet, IPythonComparable, IPythonEquality {
        IDictionary<object, object> items;
        int hashCode;
#if DEBUG
        int returnedHc;
#endif

        #region Set Construction
        [PythonName("__new__")]
        public static FrozenSetCollection NewInst(object cls) {
            if (cls == TypeCache.FrozenSet) {
                FrozenSetCollection fs = new FrozenSetCollection();
                return fs;
            } else {
                object res = ((PythonType)cls).ctor.Call(cls);
                FrozenSetCollection fs = res as FrozenSetCollection;
                if (fs == null) throw Ops.TypeError("{0} is not a subclass of frozenset", res);
                return fs;
            }
        }

        [PythonName("__new__")]
        public static FrozenSetCollection NewInst(object cls, object setData) {
            if (cls == TypeCache.FrozenSet) {
                FrozenSetCollection fs = setData as FrozenSetCollection;
                if (fs != null) {
                    // constructing frozen set from set, we return the original frozen set.
                    return fs;
                }

                fs = new FrozenSetCollection(Ops.GetEnumerator(setData));
                return fs;
            } else {
                object res = ((PythonType)cls).ctor.Call(cls, setData);
                FrozenSetCollection fs = res as FrozenSetCollection;
                if (fs == null) throw Ops.TypeError("{0} is not a subclass of frozenset", res);

                return fs;
            }
        }

        internal static FrozenSetCollection Make(object setData) {
            FrozenSetCollection fs = setData as FrozenSetCollection;
            if (fs != null) {
                // constructing frozen set from set, we return the original frozen set.
                return fs;
            }

            fs = new FrozenSetCollection(Ops.GetEnumerator(setData));
            return fs;
        }


        public FrozenSetCollection() {
            items = new Dictionary<object, object>();
            // hash code is 0 for empty set
            CalculateHashCode();
        }

        internal FrozenSetCollection(object setData)
            : this(Ops.GetEnumerator(setData)) {
            CalculateHashCode();
        }

        protected FrozenSetCollection(IEnumerator setData) {
            items = new Dict();
            while (setData.MoveNext()) {
                object o = setData.Current;
                if (!items.ContainsKey(o)) {
                    items.Add(o, o);
                }
            }
            CalculateHashCode();
        }

        internal FrozenSetCollection(IDictionary<object, object> dict) {
            items = dict;
            CalculateHashCode();
        }
        #endregion

        #region ISet
        [PythonName("len")]
        public int GetLength() {
            return items.Count;
        }

        [PythonName("__contains__")]
        public bool Contains(object o) {
            // promote sets to FrozenSet's for contains checks (so we get a hash code)
            o = SetHelpers.GetHashableSetIfSet(o);

            Ops.Hash(o);// make sure we have a hashable item
            return items.ContainsKey(o);
        }

        [PythonName("issubset")]
        public bool IsSubset(object s) {
            return SetHelpers.IsSubset(this, s);
        }

        [PythonName("issuperset")]
        public bool IsSuperset(object s) {
            return (bool)GreaterThanOrEqual(new FrozenSetCollection(Ops.GetEnumerator(s)));
        }

        ISet ISet.PrivDifference(IEnumerable s) {
            return Difference(s);
        }
        ISet ISet.PrivIntersection(IEnumerable s) {
            return Intersection(s);
        }
        ISet ISet.PrivSymmetricDifference(IEnumerable s) {
            return SymmetricDifference(s);
        }
        ISet ISet.PrivUnion(IEnumerable s) {
            return Union(s);
        }

        void ISet.PrivAdd(object o) {
            if (o == null) o = NoneType.InstanceOfNoneType;

            Ops.Hash(o);// make sure we're hashable
            if (!items.ContainsKey(o)) {
                items.Add(o, o);
            }
        }

        void ISet.PrivRemove(object o) {
            if (o == null) o = NoneType.InstanceOfNoneType;

            Ops.Hash(o);// make sure we're hashable
            items.Remove(o);
        }

        void ISet.SetData(Dictionary<object, object> dict) {
            items = dict;
        }

        void ISet.SetData(IEnumerator set) {
            items = new Dictionary<object, object>();
            while (set.MoveNext()) {
                items[set.Current] = set.Current;
            }
            CalculateHashCode();
        }

        void ISet.PrivFreeze() {
            CalculateHashCode();
        }

        #endregion

        #region NonOperator operations

        [PythonName("union")]
        public ISet Union(object s) {
            return SetHelpers.Union(this, s);
        }

        [PythonName("intersection")]
        public ISet Intersection(object s) {
            return (SetHelpers.Intersection(this, s));
        }

        [PythonName("difference")]
        public ISet Difference(object s) {
            return SetHelpers.Difference(this, s);
        }

        [PythonName("symmetric_difference")]
        public ISet SymmetricDifference(object s) {
            return SetHelpers.SymmetricDifference(this, s);
        }

        [PythonName("copy")]
        public object Copy() {
            // Python behavior: If we're a non-derived frozen set, we return ourselves. 
            // If we're a derived frozen set we make a new set of our type that contains our
            // contents.
            if (this.GetType() == typeof(FrozenSetCollection)) {
                return (this);
            }
            ISet set = SetHelpers.MakeSet(this, this);
            set.PrivFreeze();
            return (set);
        }

        [PythonName("__init__")]
        public void Init(params object[] o) {
            // nop
        }

        [PythonName("__cmp__")]
        public int Compare(object o) {
            throw Ops.TypeError("cannot compare sets using cmp()");
        }

        [PythonName("__len__")]
        public int OperatorLength() {
            return GetLength();
        }

        [PythonName("__reduce__")]
        public Tuple Reduce() {
            object[] keys = new object[items.Keys.Count];
            items.Keys.CopyTo(keys, 0);

            return Tuple.MakeTuple(new object[] { 
                Ops.GetDynamicTypeFromType(typeof(SetCollection)), 
                Tuple.MakeTuple(new List(keys)), 
                null });
        }

        [PythonName("__reduce_ex__")]
        public Tuple ReduceEx(object param) {
            return Reduce();
        }

        #endregion

        #region Operators

        [PythonName("__and__")]
        public object OperatorAnd(ISet s) {
            if (s.GetLength() < GetLength()) {
                return Intersection(s);
            }

            FrozenSetCollection fs = s as FrozenSetCollection;
            if (fs != null) {
                return fs.Intersection(this);
            }

            ISet set = SetHelpers.MakeSet(this, s.PrivIntersection(this));
            set.PrivFreeze();
            return set;
        }

        [PythonName("__ior__")]
        public object OperatorInPlaceOr(ISet s) {
            if (s.GetLength() < GetLength()) {
                return Union(s);
            }

            FrozenSetCollection fs = s as FrozenSetCollection;
            if (fs != null) {
                return fs.Union(this);
            }

            ISet set = SetHelpers.MakeSet(this, s.PrivUnion(this));
            set.PrivFreeze();
            return set;
        }

        [PythonName("__isub__")]
        public object OperatorInPlaceSub(ISet s) {
            return Difference(s);
        }

        [PythonName("__ixor__")]
        public object OperatorInPlaceXor(ISet s) {
            if (s.GetLength() < GetLength()) {
                return SymmetricDifference(s);
            }

            FrozenSetCollection fs = s as FrozenSetCollection;
            if (fs != null) {
                return fs.SymmetricDifference(this);
            }

            ISet set = SetHelpers.MakeSet(this, s.PrivSymmetricDifference(this));
            set.PrivFreeze();
            return set;
        }

        [PythonName("__ror__")]
        public object OperatorReverseOr(ISet s) {
            if (s.GetLength() < GetLength()) {
                return Union(s);
            }
            FrozenSetCollection fs = s as FrozenSetCollection;
            if (fs != null) {
                return fs.Union(this);
            }
            ISet set = SetHelpers.MakeSet(this, s.PrivUnion(this));
            set.PrivFreeze();
            return set;
        }

        [PythonName("__rsub__")]
        public ISet OperatorReverseSubtract(ISet s) {
            FrozenSetCollection fs = s as FrozenSetCollection;
            if (fs != null) {
                return fs.Difference(this);
            }

            ISet set = SetHelpers.MakeSet(this, s.PrivDifference(this));
            set.PrivFreeze();
            return set;
        }

        [PythonName("__rxor__")]
        public ISet OperatorReverseXor(ISet s) {
            if (s.GetLength() < GetLength()) {
                return SymmetricDifference(s);
            }
            FrozenSetCollection fs = s as FrozenSetCollection;
            if (fs != null) {
                return fs.SymmetricDifference(this);
            }
            ISet set = SetHelpers.MakeSet(this, s.PrivSymmetricDifference(this));
            set.PrivFreeze();
            return set;
        }

        #endregion

        #region IEnumerable Members

        public IEnumerator GetEnumerator() {
            return items.Keys.GetEnumerator();
        }

        #endregion

        void CalculateHashCode() {
            // hash code needs be stable across collections (even if keys are
            // added in different order) and needs to be fairly collision free.
            hashCode = 6551;

            // first get a sorted list of all our hash codes and their respective counts.
            SortedList<int, int> hcList = new SortedList<int, int>();
            foreach (object o in items.Keys) {
                int curHc = Ops.Hash(o);
                if (hcList.ContainsKey(curHc)) {
                    hcList[curHc] = hcList[curHc] + 1;
                } else {
                    hcList[curHc] = 1;
                }
            }

            // then calculate hash code based upon that & cache the result.
            foreach (int curHc in hcList.Keys) {
                for (int i = 0; i < hcList[curHc]; i++) {
                    hashCode = (hashCode << 5) ^ (hashCode >> 26) ^ (curHc);
                }
            }
        }

        #region Object Overrides
        [PythonName("__str__")]
        public override string ToString() {
            return (SetHelpers.SetToString(this, this.items.Keys));
        }
        #endregion

        #region IPythonComparable
        object  IPythonComparable.CompareTo(object other) {
            throw Ops.TypeError("cannot compare sets using cmp()");
        }

        [PythonName("__gt__")]
        public object GreaterThan(object other) {
            ISet s = other as ISet;
            if (s == null) throw Ops.TypeError("can only compare to a set");

            if (s.GetLength() >= GetLength()) return false;

            foreach (object o in s) {
                if (!Contains(o)) return false;
            }
            return true;
        }

        [PythonName("__lt__")]
        public object LessThan(object other) {
            ISet s = other as ISet;
            if (s == null) throw Ops.TypeError("can only compare to a set");

            if (s.GetLength() <= GetLength()) return false;

            foreach (object o in this) {
                if (!s.Contains(o)) {
                    return false;
                }
            }
            return true;
        }

        [PythonName("__ge__")]
        public object GreaterThanOrEqual(object other) {
            return ((bool)GreaterThan(other)) || ((bool)PythonEquals(other));
        }

        [PythonName("__le__")]
        public object LessThanOrEqual(object other) {
            return ((bool)LessThan(other)) || ((bool)PythonEquals(other));
        }

        [PythonName("__ne__")]
        public bool NotEquals(object other) {
            return !((bool)PythonEquals(other));
        }

        #endregion


        #region IPythonEquality Members

        [PythonName("__hash__")]
        public object PythonGetHashCode() {
#if DEBUG
            // make sure we never change the hashcode we hand out in debug builds.
            // if we do then it means we somehow called PrivAdd/PrivRemove after
            // already using the hash code.
            Debug.Assert(returnedHc == hashCode || returnedHc == 0);
            returnedHc = hashCode;
#endif
            return hashCode;
        }

        [PythonName("__eq__")]
        public object PythonEquals(object other) {
            ISet set = other as ISet;
            if (set != null) {
                if (set.GetLength() != GetLength()) return false;
                return set.IsSubset(this) && this.IsSubset(set);
            }
            return false;
        }

        #endregion
    }

}
