// ----------------------------------------------------------------------------
//
//  Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ----------------------------------------------------------------------------

using System;
using System.Text;
using System.Collections;
using Microsoft.Contracts;

namespace DataStructs
{
    using System;
    using System.Text;
    using System.IO;
    using System.Collections;
    using System.Collections.Specialized;
    using System.Diagnostics;


    /// <summary>
    /// Represents an object that can be copied deeply, as opposed to the shallow ICloneable.
    /// </summary>
    public interface ICopyable
    {
        object! Copy();
    }

    public interface ISet : ICollection, ICopyable
    {
        /// <summary>
        /// Checks whether a given element is part of <c>this</c> set.
        /// </summary>
        /// <param name="elem">element searched into the set</param>
        /// <returns><c>true</c> if <c>elem</c> is in the set, <c>false</c> otherwise</returns>
        bool Contains(Object! o);

    }


    /// <summary>
    /// Interface for the set abstraction: collection of distinct elements.
    /// </summary>
    public interface IMutableSet: ISet, ICloneable
    {
        /// <summary>
        /// Adds an element to <c>this</c> set.
        /// </summary>
        /// <param name="elem">element to add</param>
        /// <returns><c>true</c> if <c>this</c> set was modified as a result of this operation</returns>
        /// 
        bool Add(Object! o);

        /// <summary>
        /// Removes an element from <c>this</c> set. 
        /// </summary>
        /// <param name="elem"></param>
        /// <returns><c>true</c> if <c>this</c> set was modified as a result of this operation</returns>
        bool Remove(Object! o);

        /// <summary>
        /// Adds several elements from <c>this</c> set.
        /// </summary>
        /// <param name="eable"><c>IEnumerable</c> that contains the elements to be added</param>
        /// <returns><c>true</c> if <c>this</c> set was modified as a result of this operation</returns>
        bool AddAll(IEnumerable! eable);

        /// <summary>
        /// Removes several elements from <c>this</c> set.
        /// </summary>
        /// <param name="eable"><c>IEnumerable</c> containing the elements to be removed</param>
        /// <returns><c>true</c> if <c>this</c> set was modified as a result of this operation</returns>
        bool RemoveAll(IEnumerable! eable);

        /// <summary>
        /// Deletes all the elements of <c>this</c> set. As a result the <c>Count</c> property will be <c>0</c>.
        /// </summary>
        /// <returns><c>true</c> if <c>this</c> set was modified as a result of this operation</returns>
        bool Clear();

    }

    public delegate IMutableSet! DSetFactory();
    public delegate IDictionary! DDictionaryFactory();

    /// <summary>
    /// Summary description for DataStructsUtil.
    /// </summary>
    public abstract class DataStructUtil
    {   
        public static readonly DSetFactory! DefaultSetFactory = new DSetFactory(default_set_factory);
        private static IMutableSet! default_set_factory()
        {
            return new HashSet(1);
        }


        public static readonly DSetFactory! SmallSetFactory = new DSetFactory(small_set_factory);
        private static IMutableSet! small_set_factory()
        {
            return new ArraySet(1);
        }


        public static readonly DDictionaryFactory! DefaultDictionaryFactory = new DDictionaryFactory(default_dict_factory);
        private static IDictionary! default_dict_factory()
        {
            return new Hashtable(1);
        }
        

        public static readonly DDictionaryFactory! SmallDictionaryFactory = new DDictionaryFactory(small_dict_factory);
        private static IDictionary! small_dict_factory()
        {
            return new ListDictionary();
        }
        

        public static ISet! EMPTY_SET = new ImmutableSetWrapper(new HashSet());

        public static ISet singleton(object! elem)
        {
            return new SingletonSet(elem);
        }


        public static IList SortedCollection(ICollection! coll)
        {
            return SortedCollection(coll, null);
        }

        public static IList SortedCollection(ICollection! coll,  IComparer comp)
        {
            ArrayList al = new ArrayList(coll);
            if (comp == null)
                al.Sort();
            else
                al.Sort(comp);
            return al;
        }

        /// <summary>
        /// Produces a string representation of an <c>IEnumerable</c> object,
        /// using <c>o2s</c> to produce the string representation of each
        /// element.
        /// </summary>
        /// <param name="eable"></param>
        /// <param name="o2s"></param>
        /// <returns></returns>
        /// 
        public static string! IEnum2String(IEnumerable! eable,  DObj2String o2s)
        {
            StringBuilder buff = new StringBuilder();
            buff.Append("[");
            bool first = true;
            foreach (object o in eable) {
                if (first) first = false;
                else buff.Append(",");
                if (o2s != null)
                    buff.Append(o2s(o));
                else
                    buff.Append(o);
            }
            buff.Append("]");
            return buff.ToString();
        }


    }

    /// <summary>
    /// Conversion object -> string. Useful for classes for which we cannot
    /// modify / override the <c>ToString</c> method. A <c>null</c> value
    /// should be interpreted as the classic <c>ToString</c> method.
    /// </summary>
    public delegate string DObj2String(object obj);

    internal class SingletonSet: ISet
    {
        private object! elem;

        public SingletonSet(object! elem)
        {
            this.elem = elem;
        }

        public bool Contains(object! elem)
        {
            return this.elem.Equals(elem);
        }

        public int Count { 
            [Pure]
            get { return 1; } }

        public override int GetHashCode()
        {
            return elem.GetHashCode();
        }

        public IEnumerator GetEnumerator()
        {
            return new SingletonEnumerator(elem);
        }

        private class SingletonEnumerator: IEnumerator
        {
            private object elem;
            private int index = -1;

            [NotDelayed]
            public SingletonEnumerator(object elem)
            {
                this.elem = elem;
                Reset();
            }

            public virtual object Current
            {
                get 
                {
                    if (index == 0) return elem;
                    else
                        throw new InvalidOperationException();
                }
            }

            public virtual bool MoveNext()
            {
                switch (index) {
                    case -1:
                        index++;
                        return true;
                    case 0:
                        index++;
                        return false;
                    case 1:
                    default:
                        return false;
                }
            }

            public virtual void Reset()
            {
                index = -1;
            }
        }

        public object! Copy()
        {
            SingletonSet copy = (SingletonSet) this.MemberwiseClone();
            assert(copy != null);
            copy.elem = (this.elem is ICopyable) ? ((ICopyable) this.elem).Copy() : this.elem;
            return copy;
        }

        void ICollection.CopyTo (Array! target, int index) 
        {
            assume(target != null);
            target.SetValue(this.elem, index);
        }

        object! ICollection.SyncRoot
        {
            [Pure]
            get 
            {
                return this;
            }
        }

        bool ICollection.IsSynchronized 
        {
            [Pure]
            get { return false; }
        }
    }
    
    
    
    public class OneToManyMap/*<KEY,ELEM>*/ : Hashtable//<KEY,ArrayList<ELEM>>  
    {
        public override void Add (Object! key, Object newItem)
        {
            ArrayList items = base[key] as ArrayList;
            if (items == null) {
                items = new ArrayList();
                base[key] = items;
            }
            items.Add(newItem);
        }


        public virtual bool Contains (Object! key, Object item)
        {
            ArrayList items = base[key] as ArrayList;
            if (items == null)
                return false;
            return items.Contains(item);
        }


        public new ArrayList/*<Object>*/ this [Object! key] 
        {
            get { return base[key] as ArrayList; }
            set { base[key] = value; }
        }

    }



    public class DoubleTable/*<KEY1,KEY2,ELEM>*/ : Hashtable//<KEY1,Hashtable<KEY2,ELEM>>  
    {
        public DoubleTable () : base() { }

        private DoubleTable (Hashtable table) : base(table) { }


        public new Hashtable this [object! key]
        {
            get 
            {
                return base[key] as Hashtable;
                //
                //  if (table == null) {
                //      table = new Hashtable();
                //      base[key] = table;
                //  }
                //  return table;
                //    
            }

            set
            {
                base[key] = value;
            }
        }


        public void Insert (object! key1, object! key2, object element)
        {
            Hashtable table = this[key1];
            if (table == null) {
                table = new Hashtable();
                this[key1] = table;
            }
            table[key2] = element;
        }


        
        public object Lookup (object! key1, object! key2) 
        {
            Hashtable range = this[key1];
            if (range != null) {
                return range[key2];
            }
            else {
                return null;
            }
        }
        
        public override object! Clone ()
        {
            // careful. We have to deep clone the targets of the underlying hashtable.
            DoubleTable copy = new DoubleTable();
            foreach (object key in (IEnumerable!)this.Keys) {
                Hashtable x = this[key];

                assert(x != null);
                copy.Add(key, x.Clone());
            }
            return copy;
        }

        public DoubleTable Copy() 
        {
            return (DoubleTable)this.Clone();
        }
    }


    
    
    /// <summary>
    /// An attempt to make coding with datatypes more pleasant in C#
    /// </summary>
    /// <remarks>
    /// Use <c>Datatype</c> as a base class on each of your abstract data type base classes. When doing
    /// case analysis on such a value, use the method <c>Tag</c> to get a String representation of the 
    /// dynamic class name. This can be matched in the <c>case</c> branches of a switch. 
    /// <p>
    /// For pairwise matching, use <c>x.Tag + y.Tag</c> and <c>case "Foo"+"Bar"</c>.</p>
    /// <p>
    /// Can be extended to compute the set of tags of each abstract datatype instance and utility methods.</p>
    /// </remarks>
    public abstract class Datatype 
    {
        private int tag;

        private static Hashtable!/*<Type,DatatypeInfo>*/ typeTable = new Hashtable();

        private class DatatypeInfo 
        {
            IList!/*<Type>*/ members;
            Type abstractBaseType;
            public DatatypeInfo(Type abstractBaseType) 
            {
                members = new ArrayList();
                this.abstractBaseType = abstractBaseType;
            }

            public void Add(Type variant) 
            {
                members.Add(variant);
            }

            public ICollection! Members { get { return members; } }
        }

        
        private void AddToTable (Type! variant) 
        {
            DatatypeInfo info = GetBaseInfo(variant);
            info.Add(variant);
            typeTable[variant] = info;
        }

        
        private DatatypeInfo! GetBaseInfo (Type! variant) 
        {
            Type abase = FindBase(variant);
            DatatypeInfo info = (DatatypeInfo)Datatype.typeTable[abase];
            if (info == null) {
                // first time we see anything in this class tree.
                info = new DatatypeInfo(abase);
                Datatype.typeTable[abase] = info;
            }
            return info;
        }

        
        private Type! FindBase(Type! variant) 
        {
            Type abase = variant.BaseType;
            assume(abase != null);
            if (abase.IsAbstract) {

                // check that it is not datatype
                if (abase == typeof(Datatype)) {
                    Debug.Assert(false, "Every datatype should have an abstract base class that is a subtype of Datatype: " + variant.Name + " does not.");
                }

                // check if its base is Datatype
                if (abase.BaseType == typeof(Datatype)) {
                    return abase;
                }
                else {
                    // intermediate abstract base
                    return FindBase(abase);
                }
            }
            // recurse until we find abstract base
            return FindBase(abase);
        }

        [NotDelayed]
        protected Datatype (int tag) 
        {
            Type realType = this.GetType();
            assume(realType != null);
            this.tag = tag; //realType.Name;
            if (typeTable[realType] == null) {
                // add this first instance to the type table
                this.AddToTable(realType);
            }
        }

        public virtual int Tag
        {
            get { return tag; }
        }

        public void IncompleteMatch() 
        {
            Type realType = this.GetType();
            assume(realType != null);
            DatatypeInfo info = (DatatypeInfo)Datatype.typeTable[realType];

            assert(info != null);

            System.Text.StringBuilder buffer = new StringBuilder();
            foreach (object member in info.Members) {
                Type m = member as Type;

                assert(m != null);

                buffer.Append(" ");
                buffer.Append(m.Name);
            }

            Console.Write("Incomplete match: {0} was not matched.\nDatatype contains the following variants {1}\n",
                this.Tag, buffer.ToString());
            Debug.Assert(false, "incomplete match");
        }
    }

    public class ConvertingEnumerable : IEnumerator, IEnumerable
    {
        public delegate object ObjectConverter(object o);

        private IEnumerator! underlying;
        private ObjectConverter! objConverter;

        [NotDelayed]
        public ConvertingEnumerable(IEnumerable! underlying, ObjectConverter! objConverter)
        {
            this.underlying = underlying.GetEnumerator();
            this.objConverter = objConverter;
            base();
            Reset();
        }

        public object Current
        {
            get 
            {
                return objConverter(underlying.Current);
            }
        }

        public bool MoveNext()
        {
            return underlying.MoveNext();
        }

        public void Reset()
        {
            underlying.Reset();
        }

        public IEnumerator GetEnumerator()
        {
            return this;
        }
    }

}

namespace DataStructs
{
    using System;
    using System.Text;
    using System.Collections;



    public abstract class Set
    {
        public static ISet Difference(IEnumerable! a, ISet! b)
        {
            IMutableSet diff = new HashSet();
            foreach (object elem in a)
                if(!b.Contains(elem))
                    diff.Add(elem);
            return diff;
        }


        public static ISet Union(ISet! a, ISet! b)
        {
            IMutableSet union = new HashSet(a);
            union.AddAll(b);
            return union;
        }


        public static ISet Intersect(ISet! a, ISet! b) 
        {
            IMutableSet inter = new HashSet();

            if (a.Count < b.Count) {
                ISet c = a;
                a = b;
                b = c;
            }
            foreach (object elem in a) {
                if (b.Contains(elem)) {
                    inter.Add(elem);
                }
            }   
            return inter;
        }

        
        /// <summary>
        /// Returns null if A included in B. Otherwise, returns an element in
        /// A that is not in B.
        /// </summary>
        
        public static object NonSubsetWitness(ISet! a, ISet! b)
        {
            foreach (object elem in a) {
                if (!b.Contains(elem)) {
                    return elem;
                }
            }
            return null;
        }


        public delegate bool SetFilter(object! obj);

        public static ISet Filter(ISet! a, SetFilter! filter) 
        {
            IMutableSet inter = new HashSet();

            foreach (object elem in a) {
                if (filter(elem)) {
                    inter.Add(elem);
                }
            }   
            return inter;
        }


        public static readonly ISet Empty = new ArraySet(0);
    }



    public abstract class AbstrSet: IMutableSet
    {
        public abstract bool Add(object! elem);
        public virtual bool AddAll(IEnumerable! eable) 
        {
            bool modified = false;
            foreach (object elem in eable)
                if(Add(elem)) modified = true;
            return modified;
        }

        public abstract bool Remove(object! elem);

        public virtual bool RemoveAll(IEnumerable! eable)
        {   
            ISet iset = eable as ISet;
            if ((iset != null) && (iset.Count > 2 * this.Count)) {
                // optimized code for the special case when eable is a large ISet
                ArrayList to_remove = new ArrayList();
                foreach (object elem in this)
                    if(iset.Contains(elem))
                        to_remove.Add(elem);
                if (to_remove.Count != 0) {
                    foreach (object elem in to_remove)
                        this.Remove(elem);
                    return true;
                }
                return false;
            }
            
            bool modified = false;
            foreach (object elem in eable)
                if(Remove(elem)) modified = true;
            return modified;
        }           


        public abstract bool Contains(object! elem);
        public abstract bool Clear();
        public abstract int Count { get; }


        public abstract IEnumerator GetEnumerator();

        public virtual void CopyTo(Array! array, int index) 
        {
            foreach (object o in this) 
                array.SetValue(o, index++);
        }


        void ICollection.CopyTo(Array! a, int index) { 
            Array! b = a;
            this.CopyTo(b, index);
        }



        [Confined]
        public override string! ToString()
        {
            return DataStructUtil.IEnum2String(this, null);
        }

        public override int GetHashCode()
        {
            throw new InvalidOperationException("GetHashCode is unimplemented");
        }

        [Confined]
        public override bool Equals(object o)
        {
            ISet iset2 = o as ISet;
            // if o is not an ISet, is a set with a different number of
            // elements, obviously o != this 
            if ((iset2 == null) ||
                (iset2.Count != this.Count))
                return false;
            foreach (object elem in this)
                if(!iset2.Contains(elem))
                    return false;
            return true;
        }

        public virtual bool IsSynchronized { get { return false; } }
        
        public virtual object! SyncRoot {  [Pure] get { return this; } }

        public abstract object! Clone();

        object ICloneable.Clone() { 
            return this.Clone();
        }

        public abstract object! Copy();
    }



    public class ArraySet : AbstrSet
    {
        public ArraySet(int initial_size)
        {
            array = new object[initial_size];
        }

        public ArraySet(object singleton) 
        {
            array = new object[] {singleton};
            count = 1;
        }

        public ArraySet() : this(5) { }

        private object[]! array;
        private int count = 0;

        public override bool Add(object! elem)
        {
            assert(elem != null);

            for (int i = 0; i < count; i++)
                if(elem.Equals(array[i]))
                    return false;
            if (count == array.Length) {
                object[] array2 = new object[count*2];
                for (int i = 0; i < count; i++)
                    array2[i] = array[i];
                array = array2;
            }
            array[count++] = elem;
            return true;
        }

        public override bool Remove(object! elem)
        {
            assert(elem != null);

            for (int i = 0; i < count; i++)
                if(elem.Equals(array[i]))
                {
                    if (i < count - 1)
                        array[i] = array[count-1];
                    // no memory leaks
                    array[count-1] = null;
                    count--;
                    return true;
                }
            return false;
        }

        public override bool Contains(object! elem)
        {
            assert(elem != null);

            for (int i = 0; i < count; i++)
                if(elem.Equals(array[i]))
                    return true;
            return false;
        }

        public override bool Clear()
        {
            bool result = count > 0;
            count = 0;
            return result;
        }

        public override int Count { get { return count; } }

        public override IEnumerator GetEnumerator()
        {
            return new ArrayEnumerator(array, count);
        }

        public override object! Clone()
        {
            ArraySet set2 = (ArraySet) this.MemberwiseClone();
            assume(set2 != null);
            set2.array = (object[]) this.array.Clone();
            return set2;
        }

        public override object! Copy()
        {
            ArraySet set2 = (ArraySet) this.MemberwiseClone();
            assume(set2 != null);

            set2.array = (object[]) this.array.Clone();
            for (int i = 0; i < set2.count; i++) {
                ICopyable elem = set2.array[i] as ICopyable;
                if (elem != null)
                    set2.array[i] = elem.Copy();
            }
            return set2;
        }

    }



    public class ImmutableSetWrapper: IMutableSet
    {
        private ISet! real_set;

        public ImmutableSetWrapper(ISet! s)
        {
            real_set = s;
        }

        public bool Add(object! key)
        {
            throw new ModifyImmutableCollException();
        }

        
        public bool AddAll(IEnumerable! keys)
        {
            throw new ModifyImmutableCollException();
        }


        public bool Remove(object! key)
        {
            throw new ModifyImmutableCollException();
        }


        public bool RemoveAll(IEnumerable! keys)
        {
            throw new ModifyImmutableCollException();
        }


        public bool Clear()
        {
            throw new ModifyImmutableCollException();
        }
        

        public object Clone()
        {
            // memberwise clone is enough because no destructive operations
            // are allowed on this kind of objects.
            return this.MemberwiseClone();
        }

        public bool Contains(object! key)
        {
            return real_set.Contains(key);
        }

        public IEnumerator GetEnumerator()
        {
            return real_set.GetEnumerator();
        }

        public override int GetHashCode()
        {
            return real_set.GetHashCode();
        }

        public int Count { 
            [Pure]
            get { return real_set.Count; } }

        void ICollection.CopyTo(Array! target, int index) 
        {
            this.real_set.CopyTo(target, index);
        }

        bool ICollection.IsSynchronized 
        {
            [Pure]
            get { return this.real_set.IsSynchronized; }
        }

        object! ICollection.SyncRoot 
        {
            [Pure]
            get { return this.real_set.SyncRoot; }
        }

        public object! Copy()
        {
            ImmutableSetWrapper copy = (ImmutableSetWrapper) this.MemberwiseClone();
            assume(copy != null);

            // ISet implements ICopyable so we always do a deep copy of real_set
            copy.real_set = (ISet) this.real_set.Copy();
            return copy;
        }


    }


    public class ModifyImmutableCollException: SystemException
    {
        public ModifyImmutableCollException():
            base("Attempt to modify an immutable collection") {}
    }



    /// <summary>
    /// Full implementation of the <c>ISet</c> interface, backed by a <c>Hashtable</c>.
    /// </summary>
    /// <remarks>
    /// As each <c>HashSet</c> is backed by a
    /// <see cref="System.Collections.Hashtable">Hashtable</see>, all requirements that
    /// apply for the <c>Hashtable</c> keys apply for the elements of a <c>HashSet</c>
    /// as well.
    ///
    /// <p>The <c>HashSet</c> class overrides the methods
    /// <see cref="GetHashCode">GetHashCode</see> and <see cref="Equals">Equals</see>
    /// (inherited from <see cref="System.Object">Object</see>) in order to provide
    /// structural equality:
    /// two sets are equal iff they contain the same elements (where the semantics of "same"
    /// is defined by the <c>Equals</c> method of those objects).  You can put HashSets into
    /// HashSets; however, to avoid infinite loops, you should never insert a <c>HashSet</c>
    /// into itself.
    /// The hashcode of a <c>HashSet</c> is defined as the "xor" of the hashcodes of the set
    /// elements. </p>
    /// 
    /// <p>
    /// The <c>GetHashCode</c> function of a <c>HashSet</c> executes in <c>O(1)</c> time:
    /// the hashcode is dynamically updated after each operation that modifies the set.
    /// If the hashcode functions used for all the other involved objects is good and
    /// is computed in <c>O(1)</c> time, one element addition and removal execute in
    /// <c>O(1)</c> time; <c>Equals</c> works in time linear to the number of elements of
    /// <c>this</c> set.
    /// </p> 
    /// </remarks>
    public class HashSet: AbstrSet
    {
        // the Hashtable that backs up the implementation of this HashSet
        // an element is in the set if it's a key in the Hashtable
        protected Hashtable! hash;

        private Hashtable! Hash { get { return this.hash; } }

        // all keys are associated with the bogus value VALUE
        protected static object VALUE = new object();

        /// <summary>
        /// Constructs an empty <c>HashSet</c>.
        /// </summary>
        public HashSet() : this(0)
        {
        }

        public HashSet(int initialsize)
        {
            if (initialsize != 0) {
                hash = new Hashtable(initialsize);
            }
            else {
                hash = new Hashtable();
            }
            set_hash_code = 0;
            base();
        }

        
        /// <summary>
        /// Constructs a <c>HashSet</c> initialized to contain all
        /// elements from an <c>IEnumerable</c>.
        /// </summary>
        public HashSet(IEnumerable! eable) : this()
        {
            AddAll(eable);
        }

        public override bool Contains(object! elem)
        {
            return hash.ContainsKey(elem);
        }

        public override bool Add(object! elem) 
        {
            if (elem == null)
                throw new ApplicationException("null set element");

            // element already present in the set
            if (hash.ContainsKey(elem)) return false;
            // new element!
            hash[elem] = VALUE;
            set_hash_code ^= elem.GetHashCode();
            return true;
        }

        public override bool Remove(object! elem)
        {
            assert(elem != null);

            if (!hash.ContainsKey(elem)) return false;
            hash.Remove(elem);
            // a^b^b = a; we eliminate the influence of "elem" on the
            // hash code for the entire set
            set_hash_code ^= elem.GetHashCode();
            return true;
        }

        public override bool Clear()
        {
            set_hash_code = 0;
            bool result = (this.Count != 0);
            hash.Clear();
            return result;
        }

        public override int Count { get { return hash.Count; } }

        protected class HashSetEnumerator: IEnumerator 
        {
            HashSet! hash_set;
            IEnumerator! hash_e;

            public HashSetEnumerator(HashSet! hash_set) 
            {
                this.hash_set  = hash_set;
                this.hash_e    = hash_set.Hash.GetEnumerator();
                base();
            }
            
            public object Current
            {
                get
                {
                    DictionaryEntry de = (DictionaryEntry)hash_e.Current;
                    return de.Key;
                }
            }

            public bool MoveNext() 
            {
                return hash_e.MoveNext();
            }

            public void Reset() 
            {
                hash_e.Reset();
            }
        }


        
        public override IEnumerator GetEnumerator() 
        {
            return new HashSetEnumerator(this);
        }
        
        public override int GetHashCode()
        {
            return set_hash_code;
        }
        // hash_code of this set; dynamically maintained after each
        // operation on this set
        protected int set_hash_code;

        // Copy constructor
        private HashSet(HashSet! old, bool deep) : this(old.Count) {
            foreach (object elem in old) {
                if (deep) { 
                    this.Add(elem);
                }
                else {
                    this.Add((elem is ICopyable) ? ((ICopyable) elem).Copy() : elem);
                }
            }
        }

        public override object! Clone()
        {
            return new HashSet(this, false);
        }

        public override object! Copy()
        {
            return new HashSet(this, true);
        }
    }
}

namespace DataStructs
{

    public interface IRelation 
    {
        bool ContainsKey(object! key);

        bool Contains(object! key, object! value);

        ICollection! GetKeys();

        ISet! GetValues(object! key);

        IRelation! Reverse();
    }


    public interface IMutableRelation : IRelation, ICloneable, ICopyable
    {
        bool Add(object! key, object! value);

        bool AddAll(object! key, IEnumerable! values);

        /// <summary>
        /// Adds an entire relation to <d>this</d> relation.
        /// </summary>
        /// <param name="relation">Relation that is unioned with this relation.</param>
        /// <returns><c>true</c> iff <c>this</c> relation changed.</returns>
        bool AddRelation(IRelation! relation);

        bool Remove(object! key, object! value);
        bool RemoveAll(object! key, IEnumerable! values);

        bool RemoveKey(object! key);
        bool RemoveSeveralKeys(IEnumerable! keys); 

        bool RemoveSeveralValues(IEnumerable! values);

        new
        IMutableRelation! Reverse();

    }


    /// <summary>
    /// Full <c>IMutableRelation</c> implementation.
    /// </summary>
    public class Relation: IMutableRelation
    {
        /// <summary>
        /// Full power relation constructor that allows you to finely tune the memory consumption.
        /// Internally, a relation is a dictionary that assigns to each key the set of values that are
        /// in relation with it.  This constructor allows you to specify the dictionary and the set
        /// factory.
        /// </summary>
        /// <param name="dict_fact">Dictionary factory used to construct the underlying dictionary.</param>
        /// <param name="set_fact">Set factory used to construct the set that will store the values
        /// assoctiated with each key.</param>
        public Relation(DDictionaryFactory! dict_fact, DSetFactory! set_fact)
        {
            this.dict_fact = dict_fact;
            this.set_fact  = set_fact;
            this.hash = dict_fact();
            base();
        }

        /// <summary>
        /// Default constructor.  Uses the default factory for dictionaries (i.e., equiv. to new Hashtable())
        /// and sets (i.e., equiv. to new HashSet()).
        /// </summary>
        public Relation() :
            this(DataStructUtil.DefaultDictionaryFactory, DataStructUtil.DefaultSetFactory) {}

        private readonly DDictionaryFactory! dict_fact;
        private readonly DSetFactory!        set_fact;

        // underlying structure that stores the information attached with this relation
        private IDictionary! hash/*<object, ISet<object>>*/;

        public virtual bool Add(object! key, object! value)
        {
            return get_set_for_add(key).Add(value);
        }

        public virtual bool AddAll(object! key, IEnumerable! values)
        {
            return get_set_for_add(key).AddAll(values);
        }

        public virtual bool AddRelation(IRelation! relation)
        {
            if (relation == null) return false;
            bool changed = false;
            foreach (object key in relation.GetKeys())
                if(this.AddAll(key, relation.GetValues(key)))
                    changed = true;
            return changed;
        }

        private IMutableSet! get_set_for_add(object! key)
        {
            IMutableSet s = (IMutableSet) hash[key];
            if (s == null) {
                s = set_fact();
                hash[key] = s;
            }
            return s;
        }

        public virtual ISet! GetValues(object! key)
        {
            ISet s = (ISet) hash[key];
            if (s == null)
                s = DataStructUtil.EMPTY_SET;
            else
                s = new ImmutableSetWrapper(s);
            return s;
        }

        public virtual bool ContainsKey(object! key)
        {
            return hash.Contains(key);
        }

        public virtual bool Contains(object! key, object! value)
        {
            return ((ISet) GetValues(key)).Contains(value);
        }

        public virtual bool Remove(object! key, object! value)
        {
            IMutableSet s = (IMutableSet) hash[key];
            if (s == null)
                return false;

            bool result = s.Remove(value);
            if (s.Count == 0)
                hash.Remove(key);

            return result;
        }

        public virtual bool RemoveAll(object! key, IEnumerable! values)
        {
            IMutableSet s = (IMutableSet) hash[key];
            if (s == null)
                return false;

            bool result = s.RemoveAll(values);
            if (s.Count == 0)
                hash.Remove(key);

            return result;
        }


        public virtual bool RemoveKey(object! key)
        {
            if (hash.Contains(key)) {
                hash.Remove(key);
                return true;
            }
            return false;
        }

        public virtual bool RemoveSeveralKeys(IEnumerable! keys)
        {
            ISet iset_keys = keys as ISet;
            if (iset_keys != null) {
                ICollection keys_of_this = this.GetKeys();
                if (iset_keys.Count > 2 * keys_of_this.Count) {
                    // optimized code for the special case when "keys" is a large ISet
                    // UGLY code! comodif. + IEnumerator has no remove method
                    ArrayList to_remove = new ArrayList();
                    foreach (object key in keys_of_this)
                        // set membership is O(1) :)
                        if (iset_keys.Contains(key))
                            to_remove.Add(key);
                    if (to_remove.Count > 0) {
                        foreach (object key in to_remove)
                            hash.Remove(key);
                        return true;
                    }
                    return false;
                }

            }

            bool modified = false;
            foreach (object key in keys)
                if(hash.Contains(key))
                {
                    hash.Remove(key);
                    modified = true;
                }
            return modified;
        }


        public virtual bool RemoveSeveralValues(IEnumerable! values)
        {
            bool modified = false;

            // the following code is inneficient ... this is due to:
            // 1. the need to avoid Comodification exceptions
            // 2. the lack of a remove method in IEnumerator()
            ArrayList keys = new ArrayList(GetKeys());
            foreach (object key in keys) {
                IMutableSet s = (IMutableSet) hash[key];
                assert(s != null);
                if (s.RemoveAll(values)) {
                    modified = true;
                    if (s.Count == 0)
                        hash.Remove(key);
                }
            }

            return modified;
        }

        
        public virtual ICollection! GetKeys()
        {
            return (ICollection!)hash.Keys;
        }

        public virtual IMutableRelation! Reverse()
        {
            IMutableRelation reverse = new Relation();
            foreach (object key in GetKeys())
                foreach(object value in GetValues(key))
                    reverse.Add(value, key);
            return reverse;
        }

        IRelation! IRelation.Reverse() 
        {
            return this.Reverse();
        }

        /// Copy constructor
        private Relation(Relation! old, bool deep) : this(old.dict_fact, old.set_fact)
        {
            foreach (object key in old.GetKeys()) {
                // deep copy of the key, if requested && possible
                object key2 = (deep && key is ICopyable) ? ((ICopyable) key).Copy() : key;
                foreach (object val in old.GetValues(key)) {
                    // deep copy of the value, if requested && possible
                    object val2 = (deep && val is ICopyable) ? ((ICopyable) val).Copy() : val;
                    this.Add(key2, val2);
                }
            }
        }

        /// <summary>
        /// "Shallow" copy of a relation.  Produces an independent copy of <c>this</c> <c>Relation</c>.
        /// The keys and values are not duplicated.  Operations on the
        /// resulting <c>Relation</c> and on <c>this</c> <c>Relation</c> don't interact.
        /// </summary>
        /// <returns>An independent copy of <c>this</c> Relation.</returns>
        public virtual object Clone()
        {
            return new Relation(this, false);
        }

        /// <summary>
        /// Deep copy of a relation.  Produces an independent copy of <c>this</c> <c>Relation</c>,
        /// in which even the keys and values are duplicated (using deep copy) if they implement
        /// the ICopyable interface.  Operations on the resulting <c>Relation</c> and on <c>this</c>
        /// <c>Relation</c> don't interact.
        /// </summary>
        /// <returns>A really deep copy of <c>this</c> <c>Relation</c>.</returns>
        public virtual object! Copy()
        {
            return new Relation(this, true);
        }


        [Confined]
        public override string! ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            foreach (object key in this.GetKeys()) {
                sb.Append("\n  ");
                sb.Append(key);
                sb.Append(" -> " );
                sb.Append(this.GetValues(key));
            }
            sb.Append("]");
            return sb.ToString();
        }

        public static Hashtable/*<Key,Value[]>*/ Compact(IRelation!/*<Key,Value>*/ irel, Type! value_type) 
        {
            Hashtable hash = new Hashtable();
            foreach (object key in irel.GetKeys()) {
                ISet vals = irel.GetValues(key);
                if (vals.Count == 0)
                    continue;
                System.Array array_vals = System.Array.CreateInstance(value_type, vals.Count);
                vals.CopyTo(array_vals, 0);
                hash.Add(key, array_vals);
            }
            return hash;
        }
    }

}

namespace DataStructs
{
    using System;
    using System.Text;
    using System.Collections;
    using System.Diagnostics;


    
    
    /// <summary>
    /// Interface for Strongly Connected Methods.
    /// </summary>
    public interface IStronglyConnectedComponent
    {
        /// <summary>
        /// Returns the nodes contained into <c>this</c> StronglyConnectedComponent.
        /// </summary>
        IEnumerable! Nodes { get; }

        bool Contains (object! node);

        /// <summary>
        /// Returns the number of nodes in <c>this</c> StronglyConnectedComponent.
        /// </summary>
        /// <returns></returns>
        int Size { get; }

        /// <summary>
        /// Returns the SCCs that are end points of the arcs that starts in
        /// <c>this</c> StronglyConnectedComponent, i.e., the successors of <c>this</c> StronglyConnectedComponent in the
        /// component graph. Does not contain <c>this</c> StronglyConnectedComponent.
        /// </summary>
        IEnumerable! NextComponents { get; }

        /// <summary>
        /// Returns the SCCs that are starting points for arcs that end
        /// in <c>this</c> StronglyConnectedComponent, i.e., the predecessors of <c>this</c> StronglyConnectedComponent
        /// in the component graph. Does not contain <c>this</c> StronglyConnectedComponent.
        /// </summary>
        IEnumerable! PreviousComponents { get; }
        /// <summary>
        /// Checks whether <c>this</c> StronglyConnectedComponent is a cycle, i.e., if it has more than
        /// one node or it has a single node which points to itself.  The only
        /// StronglyConnectedComponent that does not contain a cycle is a StronglyConnectedComponent composed of a single node
        /// which doesn't point to itself.
        /// </summary>
        /// <returns></returns>
        bool ContainsCycle { get; }

        /// <summary>
        /// Detailed text representation of <c>this</c> StronglyConnectedComponent.
        /// <c>ToString</c> will return just a unique text id of the StronglyConnectedComponent,
        /// while the detailed text representation will be produced by
        /// <c>FullToString</c>
        /// </summary>
        /// <returns></returns>
        string! FullToString();
    }



    /// <summary>
    /// StronglyConnectedComponent is a full implementation of the interface <c>ISCC</c>.
    /// It comes with a producer static method that constructs the
    /// component graph for a given graph. 
    /// </summary>
    public sealed class StronglyConnectedComponent: IStronglyConnectedComponent
    {
        // unique numeric id for debug purposes 
        private int id;

        private IMutableSet! nodes     = new HashSet();
        private IMutableSet! next_SCCs = new HashSet();
        private IMutableSet! prev_SCCs = new HashSet();
        private bool contains_cycle = true;


        // SCCs should be created only by Util.ConstructSCCs
        private StronglyConnectedComponent () { }

        private StronglyConnectedComponent (int id)
        {
            this.id = id;
        }


        public IEnumerable! Nodes { get { return this.nodes; } }


        public bool Contains (object! node)
        {
            return nodes.Contains(node);
        }


        public int Size { get { return this.nodes.Count; } }


        public IEnumerable! NextComponents { get { return this.next_SCCs; } }


        public IEnumerable! PreviousComponents { get { return this.prev_SCCs; } }


        public bool ContainsCycle { get { return this.contains_cycle; } }


        /// <summary>
        /// Detailed text representation of <c>this</c> StronglyConnectedComponent.
        /// </summary>
        /// <returns></returns>
        public string! FullToString ()
        {
            StringBuilder buff = new StringBuilder();
            buff.Append(this);
            buff.Append(" (");
            buff.Append(Size);
            buff.Append(") {\n");
            buff.Append(" Nodes: ");
            buff.Append(Nodes);
            buff.Append("\n");
            buff.Append(" ContainsCycle: ");
            buff.Append(ContainsCycle);
            buff.Append("\n");
            if (next_SCCs.Count > 0) {
                buff.Append(" Next: ");
                buff.Append(NextComponents);
                buff.Append("\n");
            }
            if (prev_SCCs.Count > 0) {
                buff.Append(" Prev: ");
                buff.Append(PreviousComponents);
                buff.Append("\n");
            }
            buff.Append("}");
            return buff.ToString();
        }

        /// <summary>
        /// Simplified text representation for debug purposes: "StronglyConnectedComponent" + numeric id.
        /// </summary>
        /// <returns></returns>
        [Confined]
        public override string! ToString()
        {
            return "StronglyConnectedComponent" + id;
        }


        /// <summary>
        /// Use the <c>nav</c> navigator to explore the graph rooted in the
        /// objects from the <c>roots</c> set, decomposes it into strongly
        /// connected components. Returns the set of strongly connected components.
        /// </summary>
        public static IEnumerable!/*<StronglyConnectedComponent>*/ ConstructSCCs(IEnumerable! roots, IGraphNavigator! navigator)
        {
            return (new SCCFactory(navigator)).ConstructSCCs(roots);
        }

        // private class that does the actual job behind ConstructSCCs
        private sealed class SCCFactory
        {
            public SCCFactory (IGraphNavigator! navigator) { this.navigator = navigator; base(); }

            public IEnumerable!/*<StronglyConnectedComponent>*/ ConstructSCCs (IEnumerable! roots)
            {
                
#if DEBUG_GRAPH
                Console.WriteLine("ConstructSCCs doing 1st dfs...");
#endif
                GraphUtil.SearchDepthFirst(
                    roots,
                    navigator,
                    null,
                    null,
                    null,
                    new DNodeVisitor(first_dfs_end_visitor)
                );

#if DEBUG_GRAPH
                Console.WriteLine("ConstructSCCs doing 2nd dfs...");
#endif

                GraphUtil.SearchDepthFirst(
                    nodes_desc_order,
                    new BackwardGraphNavigator(navigator),
                    new DNodePredicate(second_dfs_avoid),
                    new DNodeVisitor(create_new_SCC),
                    new DNodeVisitor(second_dfs_begin_visitor),
                    null
                );

#if DEBUG_GRAPH
                Console.WriteLine("ConstructSCCs doing put_arcs...");
#endif
                put_arcs();

                return all_SCCs;
            }


            // navigator through the graph
            private IGraphNavigator! navigator;
            // the nodes in the subgraph rooted in the roots
            private IMutableSet!  nodes_in_graph = new HashSet();
            // holds all the nodes in the explored subgraph; the top of the stack
            // is the node whose dfs traversal finished last 
            private Stack! nodes_desc_order = new Stack();

            private StronglyConnectedComponent current_scc = null;
            private ArrayList! all_SCCs = new ArrayList();
            private Hashtable!/*<object,StronglyConnectedComponent>*/ node2scc = new Hashtable();

            // numeric id used to generate distinct ids for the generated SCCs
            private int scc_id = 0;

            private void first_dfs_end_visitor(object! node)
            {
                nodes_in_graph.Add(node);
                nodes_desc_order.Push(node);
            }

            // the second dfs will avoid the nodes that are not in the subgraph rooted
            // in the root nodes; this way, the reversed navigator cannot lead us to
            // unexplored regions.
            private bool second_dfs_avoid (object! node)
            {
                return ! nodes_in_graph.Contains(node);
            }

            private void create_new_SCC (object! node)
            {
                current_scc = new StronglyConnectedComponent(scc_id++);
                all_SCCs.Add(current_scc);
            }

            private void second_dfs_begin_visitor (object! node)
            {
                assert current_scc != null;
                current_scc.nodes.Add(node);
                node2scc.Add(node, current_scc);
            }


            private void put_arcs()
            {
                foreach (object node in nodes_in_graph) {
                    StronglyConnectedComponent scc = (StronglyConnectedComponent) node2scc[node];
                    assert(scc != null);
                    // add the arcs from scc to successor SCCs
                    foreach (object next_node in navigator.NextNodes(node)) 
                        if(nodes_in_graph.Contains(next_node))
                        {
                            StronglyConnectedComponent next = (StronglyConnectedComponent) node2scc[next_node];
                            assert(next != null);
                            scc.next_SCCs.Add(next);
                        }
                    // add the arcs from scc to predecessor SCCs
                    foreach (object prev_node in navigator.PreviousNodes(node))
                        if(nodes_in_graph.Contains(prev_node))
                        {
                            StronglyConnectedComponent prev = (StronglyConnectedComponent) node2scc[prev_node];
                            assert(prev != null);
                            scc.prev_SCCs.Add(prev);
                        }
                }

                foreach (StronglyConnectedComponent scc in all_SCCs) {
                    scc.contains_cycle = scc.next_SCCs.Contains(scc);
                    scc.next_SCCs.Remove(scc);
                    scc.prev_SCCs.Remove(scc);
                }
            }
        }

    }

}

namespace DataStructs
{
    using System;
    using System.Collections;

    /// <summary>
    /// Interface for navigating into a graph.
    /// </summary>
    public interface IGraphNavigator
    {
        /// <summary>
        /// Returns the nodes that can be reached from <c>node</c> by
        /// navigating one level along the graph edges.
        /// </summary>
        IEnumerable! NextNodes (object! node);
        /// <summary>
        /// Returns the nodes that can be reached from <c>node</c> by
        /// navigating one level AGAINST the graph edges (i.e., from edge
        /// target to the edge source).
        /// </summary>
        IEnumerable! PreviousNodes (object! node);
    }


    /// <summary>
    /// Navigator for the graph obtained by unioning two graphs.
    /// </summary>
    public class UnionGraphNavigator: IGraphNavigator
    {
        /// <summary>
        /// Constructs a navigator into a graph which is the union of two graphs
        /// (where the graphs are seen as edge sets).
        /// </summary>
        /// <param name="nav1">Navigator for the first graph.</param>
        /// <param name="nav2">Navigator for the second graph.</param>
        public UnionGraphNavigator(IGraphNavigator! nav1, IGraphNavigator! nav2)
        {
            this.nav1 = nav1;
            this.nav2 = nav2;
        }
        private IGraphNavigator! nav1;
        private IGraphNavigator! nav2;

        /// <summary>
        /// In a union graph, the list of successors of a node includes its successors in
        /// the first graph followed by its successors in the second graph.
        /// </summary>
        public virtual IEnumerable! NextNodes (object! node)
        {
            return new CompoundEnumerable(nav1.NextNodes(node), nav2.NextNodes(node));
        }

        /// <summary>
        /// In a union graph, the list of predecessors of a node includes the its predecessors in
        /// the first graph followed by its predecessors in the second graph.
        /// </summary>
        public virtual IEnumerable! PreviousNodes (object! node)
        {
            return new CompoundEnumerable(nav1.PreviousNodes(node), nav2.PreviousNodes(node));
        }
    }


    public abstract class ForwardOnlyGraphNavigator: IGraphNavigator
    {
        public abstract IEnumerable! NextNodes (object! node);

        public virtual IEnumerable! PreviousNodes (object! node)
        {
            throw new InvalidOperationException("should never be called!");
        }
    }

    /// <summary>
    /// Navigator for an inversed graph.  The successors (i.e., <c>NextNodes</c>)
    /// of a node are the predecessors of the node in the original graph.  Analogously
    /// for the predecessors.
    /// </summary>
    public class BackwardGraphNavigator: IGraphNavigator
    {
        private readonly IGraphNavigator! navigator;

        /// <summary>
        /// Constructs a <c>BackwardGraphNavigator</c> that reverses an
        /// <c>IGraphNavigator</c>.
        /// </summary>
        /// <param name="navigator">The navigator that is reversed.</param>
        public BackwardGraphNavigator(IGraphNavigator! navigator)
        {
            this.navigator = navigator;
            base();
        }

        public IEnumerable! NextNodes (object! node)
        {
            return navigator.PreviousNodes(node);
        }

        public IEnumerable! PreviousNodes (object! node)
        {
            return navigator.NextNodes(node);
        }
    }

    
    public class FilteredGraphNavigator : IGraphNavigator
    {

        IGraphNavigator! graph;
        ISet! nodes;

        /// <summary>
        /// Only nodes in given set are considered part of the graph.
        /// </summary>
        public FilteredGraphNavigator(ISet! nodes, IGraphNavigator! graph) 
        {
            this.graph = graph;
            this.nodes = nodes;
        }

        #region IGraphNavigator Members

        public IEnumerable! NextNodes (object! node)
        {
            return new FilterEnumerable(this.nodes, this.graph.NextNodes(node));
        }

        public IEnumerable! PreviousNodes (object! node)
        {
            return new FilterEnumerable(this.nodes, this.graph.PreviousNodes(node));
        }

        private class FilterEnumerable : IEnumerable
        {
            ISet! nodes;
            IEnumerable! edges;

            public FilterEnumerable(ISet! nodes, IEnumerable! edges) 
            {
                this.nodes = nodes;
                this.edges = edges;
                base();
            }

            public IEnumerator GetEnumerator() { return new FilterEnumerator(this.nodes, this.edges.GetEnumerator()); }


            private class FilterEnumerator : IEnumerator
            {
                ISet! nodes;
                IEnumerator! edges;

                public FilterEnumerator(ISet! nodes, IEnumerator! edges) 
                {
                    this.nodes = nodes;
                    this.edges = edges;
                    base();
                }

                #region IEnumerator Members

                public void Reset()
                {
                    this.edges.Reset();
                }

                public object Current
                {
                    get
                    {
                        return this.edges.Current;
                    }
                }

                public bool MoveNext()
                {
                    while (this.edges.MoveNext()) {
                        if (this.nodes.Contains(this.Current)) {
                            return true;
                        }
                    }
                    return false;
                }

                #endregion

            }
        }
        #endregion
    }


    public class MapBasedNavigator: IGraphNavigator
    {
        protected IMutableRelation! n2next;
        protected IMutableRelation! n2prev;

        public MapBasedNavigator (IMutableRelation! nextRelation, IMutableRelation! previousRelation) 
        {
            n2next = nextRelation; 
            n2prev = previousRelation;
        }

        public MapBasedNavigator (IMutableRelation! nextRelation) 
            : this(nextRelation, nextRelation.Reverse())
        {
        }

        public virtual IEnumerable! NextNodes (object! node)
        {
            return n2next.GetValues(node);
        }

        public virtual IEnumerable! PreviousNodes (object! node)
        {
            return n2prev.GetValues(node);
        }       
    }


    public class GraphBuilder : MapBasedNavigator 
    {
        public GraphBuilder () 
            : base (new Relation(), new Relation())
        {
        }

        public IEnumerable Nodes 
        {
            get 
            { 
                return new UnionEnumerable(n2next.GetKeys(), n2prev.GetKeys()); 
            }
        }

        public void AddEdge(object! from, object! to) 
        {
            this.n2next.Add(from, to);
            this.n2prev.Add(to, from);
        }
    }


    /// <summary>
    /// Navigator in a component graph (an acyclic graph of ISCCs).
    /// </summary>
    public class SccNavigator: IGraphNavigator
    {
        public virtual IEnumerable! NextNodes (object! node)
        {
            return ((IStronglyConnectedComponent) node).NextComponents;
        }

        public virtual IEnumerable! PreviousNodes (object! node)
        {
            return ((IStronglyConnectedComponent) node).PreviousComponents;
        }
    }


    public class CyclicGraphException: Exception { }

    public delegate bool DNodePredicate (Object! node);
    public delegate void DNodeVisitor (Object! node);
    public delegate void DEdgeVisitor (Object! from, Object! to);

    public abstract class GraphUtil
    {
        public static ISet! ReachableNodes (IEnumerable! roots, IGraphNavigator! navigator,  DNodePredicate avoid)
        {
            ReachableNodesData data = new ReachableNodesData();
            SearchDepthFirst(roots, navigator, avoid, null,
                new DNodeVisitor(data.reachable_visitor), null);
            return data.all_nodes;
        }

        private class ReachableNodesData
        {
            public IMutableSet! all_nodes  = new HashSet();
            public void reachable_visitor(object! node)
            {
                all_nodes.Add(node);
            }
        }

        public static ISet! ReachableNodes (IEnumerable! roots, IGraphNavigator! navigator) 
        {
            return ReachableNodes(roots, navigator, null);
        }


        /// <summary>
        /// Topologically sorts the graph rooted in <c>roots</c> and described by
        /// <c>nav</c>. Throws a <c>CyclicGraphException</c> if the graph contains
        /// a cycle. Otherwise, returns a topologically sorted list of the graph nodes. 
        /// The returned list is in ascending order: it starts with the nodes that don't
        /// have any out-arc (i.e., arcs going out of them) and ends with the nodes
        /// that don't have any in-arcs (i.e., arcs going into them).  If the navigator
        /// works in constant time, the topological sort works in time linear with the
        /// number of nodes plus the number of edges. 
        /// 
        /// </summary>
        public static IList TopologicallySortGraph (IEnumerable! roots, IGraphNavigator! navigator)
        {
            TopSortData data = new TopSortData();
            data.all_nodes.AddAll(ReachableNodes(roots, navigator));
            if (data.all_nodes.Count == 0)
                return data.list;

            // find the real roots: those nodes with no arcs pointing to them
            data.real_roots.AddAll(roots);
            foreach (object node in data.all_nodes)
                foreach(object next_node in navigator.NextNodes(node))
                    data.real_roots.Remove(next_node);
            // if there is no real root, we have a cycle
            if (data.real_roots.Count == 0)
                throw new CyclicGraphException();

            dfs(data.real_roots, navigator, null, null,
                new DNodeVisitor(data.sort_end_visitor));

#if NEVER
            // check for cyles
            IMutableSet seen = new HashSet();
            foreach (object node in data.list) {
                foreach (object next_node in navigator.NextNodes(node))
                    // all arcs must go behind in the list, to already seen nodes
                    if (!seen.Contains(next_node))
                        throw new CyclicGraphException();
                seen.Add(node);
            }
#endif
            return data.list;
        }

        private class TopSortData
        {
            public ArrayList! list  = new ArrayList();
            public IMutableSet! all_nodes  = new HashSet();
            public IMutableSet! real_roots = new HashSet();
            public void sort_end_visitor(object! node)
            {
                list.Add(node);
            }
        }


        /// <summary>
        /// Topologically sorts a component graph: a graph whose nodes are the
        /// strongly connected components of the original graph (such a graph is
        /// clearly acyclic). Calls the full-fledged TopSortComponentGraph with
        /// the standard <c>ISCCNavigator</c>.
        /// 
        /// </summary>
        /// <param name="roots">The set of the root SCCs, only the SCCs reacheable
        /// from these roots will be considered by the topological sort.</param>
        /// <returns></returns>
        public static IList//<IStronglyConnectedComponent>   
            TopologicallySortComponentGraph(IEnumerable!/*<IStronglyConnectedComponent>*/ roots)
        {
            return TopologicallySortGraph(roots, iscc_navigator);
        }
        // private navigator for TopSortComponentGraph
        private static SccNavigator! iscc_navigator = new SccNavigator();

        /// <summary>
        /// DFS traversal of the (sub)graph rooted in a set of nodes.
        /// </summary>
        /// <param name="roots">Roots of the traversed subgraph. The subgraph
        /// rooted in the first root will be traversed in dfs order; next, if
        /// the second root wasn't reached yet, the subgraph rooted in it will
        /// be traversed in dfs order and so on. The order of
        /// the roots is given by the corresponding <c>IEnumerator</c>.</param>
        /// <param name="navigator">Navigator that describes the graph structure.</param>
        /// <param name="avoid">Encountered nodes that satisfy this predicate will be
        /// ignored by the DFS traversal (together with their attached arcs). <c>null</c>
        /// corresponds to the predicate that is always false (i.e., no encountered node
        /// will be ignored).</param>
        /// <param name="new_subgraph_visitor">Visitor for the root node of each
        /// new subgraph: the roots (see the <see cref="roots">roots</see> parameter)
        /// are explored in order; if a root node has not been already reached
        /// by the dfs traversal of the previous roots, <c>new_subgraph_visitor</c>
        /// will be called on it, and next the subgraph rooted in it will be dfs
        /// traversed.</param>
        /// <param name="begin_visitor">Node visitor to be called when a node is reached
        /// for the first time by the DFS traversal. <c>null</c> corresponds to no
        /// visitor.</param>
        /// <param name="end_visitor">Node visitor to be called when the exploration of
        /// a node has finished. <c>null</c> corresponds to no visitor.</param>
        public static void SearchDepthFirst (
            IEnumerable! roots, 
            IGraphNavigator! navigator,
             DNodePredicate avoid,
             DNodeVisitor new_subgraph_visitor,
             DNodeVisitor begin_visitor,
             DNodeVisitor end_visitor
            )
        {
            // set of already seen nodes
            IMutableSet seen_nodes = new HashSet();
            // DFS Stack: holds the currently explored path; simulates the call
            // stack of a recursive implementation of dfs.
            Stack/*<NodeInfo>*/ stack = new Stack();

            foreach (object root in roots) {
                if (((avoid != null) && avoid(root)) ||
                    seen_nodes.Contains(root)) continue;

                call_visitor(new_subgraph_visitor, root);

                seen_nodes.Add(root);
                call_visitor(begin_visitor, root);
                stack.Push(new NodeInfo(root, navigator));
                while (stack.Count != 0) {
                    NodeInfo info = (NodeInfo) (object!)stack.Peek();
                    if (info.enext.MoveNext()) {
                        object next_node = info.enext.Current;
                        // ignore nodes as dictated by "avoid"
                        if ((avoid != null) && avoid(next_node))
                            continue;
                        
                        if (!seen_nodes.Contains(next_node)) {
                            // new and non-avoidable node!
                            // mark it as seen,
                            seen_nodes.Add(next_node);
                            // call the begin visitor,
                            call_visitor(begin_visitor, next_node);
                            // and put the node on the DFS stack
                            stack.Push(new NodeInfo(next_node, navigator));
                        }
                    }
                    else {
                        // the visit of info.node has finished
                        // apply end visitor
                        call_visitor(end_visitor, info.node);
                        // remove the top of the stack
                        stack.Pop();
                    }
                }
            }
        }


        /// <summary>
        /// Convenient <c>dfs</c> function.  Call the full <c>dfs</c> function
        /// with new_subgraph_visitor set to <c>null</c>.
        /// </summary>
        public static void dfs (
            IEnumerable! roots, 
            IGraphNavigator! navigator,
             DNodePredicate avoid,
             DNodeVisitor begin_visitor,
             DNodeVisitor end_visitor)
        {
            SearchDepthFirst(roots, navigator, avoid, null, begin_visitor, end_visitor);
        }

        private static void call_visitor(  DNodeVisitor visitor, object! node)
        {
            if (visitor != null)
                visitor(node);
        }

        // private class used internally by the dfs method.
        private struct NodeInfo
        {
            public object! node;
            public IEnumerator! enext ;
            public NodeInfo(object! node, IGraphNavigator! navigator)
            {
                this.node  = node;
                this.enext = navigator.NextNodes(node).GetEnumerator();
            }
        }



        /// <summary>
        /// Does a breadth first traversal of the given graph
        /// </summary>
        /// <param name="roots">The roots of the traversal.</param>
        /// <param name="avoid">If not null, is a predicate to avoid certain nodes</param>
        /// <param name="visitRoot">If not null, called for each root that is not avoided.</param>
        /// <param name="visitEdge">Called for each edges in the bf traversal, i.e., only for edges going to unvisited nodes.</param>
        public static void bfs(IEnumerable! roots, IGraphNavigator! navigator,
             DNodePredicate avoid,
             DNodeVisitor visitRoot,
             DEdgeVisitor! visitEdge)
        {
            Queue queue = new Queue();
            IMutableSet seen = new HashSet();

            // initialize queue with roots
            foreach (object o in roots) {
                if (avoid == null || !avoid(o)) {
                    queue.Enqueue(o);
                    seen.Add(o);
                    if (visitRoot != null) visitRoot(o);
                }
            }

            while (queue.Count > 0) {
                object node = queue.Dequeue();
                assert(node != null);
                foreach (object succ in navigator.NextNodes(node)) {
                    if ((avoid == null || !avoid(succ)) && !seen.Contains(succ)) {
                        seen.Add(succ);
                        queue.Enqueue(succ);
                        visitEdge(node, succ);
                    }
                }
            }
        }




        private class BFSpanningBuilder : MapBasedNavigator
        {
            public BFSpanningBuilder () 
                : base (new Relation(), new Relation())
            {
            }

            public void VisitEdge(object! from, object! to) 
            {
                this.n2next.Add(from, to);
                this.n2prev.Add(to, from);
            }
        }

        public static IGraphNavigator BFSpanningTree(IEnumerable! roots, IGraphNavigator! navigator, 
             DNodePredicate avoid) 
        {
            BFSpanningBuilder bfb = new BFSpanningBuilder();

            bfs(roots, navigator, avoid, null, new DEdgeVisitor(bfb.VisitEdge));

            return bfb;
        }
    }

}


namespace DataStructs
{
    using System;
    using System.Collections;


    public class ArrayEnumerable : IEnumerable
    {
        object[]! array;
        int size;

        public ArrayEnumerable(object[]! array, int size) 
        {
            this.array = array;
            this.size = size;
        }

        #region IEnumerable Members

        public IEnumerator GetEnumerator()
        {
            return new ArrayEnumerator(this.array, this.size);
        }

        #endregion

    }



    /// <summary>
    /// Enumerator over a prefix of an array (System.Array.GetEnumerator returns
    /// an enumerator over ALL the elements of the array).
    /// </summary>
    public class ArrayEnumerator : IEnumerator
    {
        /// <summary>
        /// Constructs an enumerator  over the first <c>size</c> elements of <c>array</c>.
        /// NOTE: I couldn't find any way of detecting comodification errors ...
        /// </summary>
        public ArrayEnumerator(object[]! array, int size)
        {
            this.array = array;
            this.size  = size;
            this.index = -1;
        }

        // underlying array
        private readonly object[]! array;
        // length of the prefix of array that we enumerate over
        private readonly int      size;
        // current enumerator position
        private int index;


        public virtual object Current
        {
            get 
            {
                if ((index >= 0) && (index < size)) return array[index];
                else
                    throw new InvalidOperationException();
            }
        }


        public virtual bool MoveNext()
        {
            if (index == size)
                return false;
            index++;
            // check whether we've passed the limit or not
            return index != size;
        }


        public virtual void Reset()
        {
            index = -1;
        }
    }
}


namespace DataStructs 
{
    using System;
    using System.Collections;


    /// <summary>
    /// Union enumerator over two <c>IEnumerable</c> objects. Each key is visited only once
    /// </summary>
    public class UnionEnumerable: IEnumerable 
    {

        public UnionEnumerable(IEnumerable! ieable1, IEnumerable! ieable2) 
            : this(new IEnumerable[]{ieable1, ieable2})
        {
        }

        public UnionEnumerable(IEnumerable!/*<IEnumerable>*/ ienums) 
        {
            this.ienums = ienums;
        }

        private IEnumerable!/*<IEnumerable>*/ ienums;

        public virtual IEnumerator GetEnumerator() 
        {
            return new UnionEnumerator(ienums);
        }
    }

    /// <summary>
    /// Union composition of two enumerators.  Enumerating with a
    /// multi-enumerator is equivalent to enumerating over the union of the elements in
    /// the first and second enumerator.
    /// </summary>
    public class UnionEnumerator: IEnumerator 
    {
        /// <summary>
        /// Creates a <c>UnionEnumerator</c> over both given enumerators.
        /// </summary>
        public UnionEnumerator(IEnumerable!/*<IEnumerable>*/ ienums) 
        {
            this.ies = ienums;

            // Duplicate from Reset 
            IEnumerator ienum = this.ienumate = ienums.GetEnumerator();
            // go to first enumerator.
            MoveEnumerator(ienum);
        }

        public void Reset() 
        {
            seen.Clear();

            IEnumerator ienum = this.ienumate = ies.GetEnumerator();
            // go to first enumerator.
            MoveEnumerator(ienum);
        }

        [Delayed]
        private void MoveEnumerator(IEnumerator! ienum) 
        {
            if (ienum.MoveNext()) {
                this.current_ie = ((IEnumerable)ienum.Current).GetEnumerator();
            }
            else {
                this.current_ie = null;
            }
        }


        public UnionEnumerator(IEnumerable ie1, IEnumerable ie2) : this(new IEnumerable[]{ie1,ie2})
        {
        }

        private HashSet! seen = new HashSet();
        private IEnumerable!/*<IEnumerable>*/ ies;
        private IEnumerator!/*<IEnumerable>*/ ienumate;
        private IEnumerator/*<'a>*/ current_ie;

        public virtual object Current 
        {
            get 
            {
                if (current_ie == null)
                    throw new InvalidOperationException("exhausted enumerator");
                return
                    current_ie.Current;
            }
        }

        public virtual bool MoveNext() 
        {
            while (current_ie != null) {
                if (current_ie.MoveNext()) {
                    if (this.seen.Add(current_ie.Current)) {
                        return true;
                    }
                    // already seen
                    continue;
                }
                // move to next ienumerable
                MoveEnumerator(this.ienumate);
            }
            return false;
        }

    }
}

namespace DataStructs 
{
    using System;
    using System.Collections;


    /// <summary>
    /// Returns null if object should not be returned, otherwise, returns object.
    /// Can thus change objects.
    /// </summary>
    public delegate object EnumeratorFilter(object elem, object context);

    /// <summary>
    /// "Glues" together two <c>IEnumerable</c> objects in a single view.
    /// </summary>
    public class CompoundEnumerable: IEnumerable 
    {

        /// <summary>
        /// Construct an enumerable that enumerators over ieable1, then ieable2. Each element
        /// is passed to the filter which can decide if the element should be returned by
        /// the enumerator or not. The filter can also change the element (map).
        /// </summary>
        /// <param name="filter">can be null</param>
        /// <param name="context">passed to filter</param>
        public CompoundEnumerable (
            IEnumerable! ieable1,
            IEnumerable! ieable2,
            EnumeratorFilter filter, 
            object context) 
        {
            this.ieable1 = ieable1;
            this.ieable2 = ieable2;
            this.filter = filter;
            this.context = context;
        }

        public CompoundEnumerable(IEnumerable! ieable1, IEnumerable! ieable2) : this(ieable1, ieable2, null, null)
        {
        }

        private IEnumerable! ieable1;
        private IEnumerable! ieable2;
        private EnumeratorFilter filter;
        private object context;

        public virtual IEnumerator GetEnumerator() 
        {
            return 
                new MultiEnumerator(ieable1.GetEnumerator(), ieable2.GetEnumerator(), filter, context);
        }
    }

    /// <summary>
    /// Serial composition of two enumerators.  Enumerating with a
    /// multi-enumerator is equivalent to enumerating with the first enumerator,
    /// and next with the second one.  Implements the full <c>IEnumerable</c>
    /// interface.  Aliases to the enumerators are sequentially composed are
    /// internally stored and used by the encapsulating multi-enumerator.
    /// </summary>
    public class MultiEnumerator: IEnumerator 
    {
        /// <summary>
        /// Creates a <c>MultiEnumerator</c> that serially chains the two
        /// enumerators passed as arguments.
        /// </summary>
        [NotDelayed]
        public MultiEnumerator(IEnumerator! ie1, IEnumerator! ie2,  EnumeratorFilter filter, object context) 
        {
            this.filter = filter;
            this.context = context;
            ies = new IEnumerator[]{ie1, ie2};
            base();
            ((IEnumerator!)ies[0]).Reset();
            ((IEnumerator!)ies[1]).Reset();
        }

        
        private EnumeratorFilter filter;
        private IEnumerator[]! ies;
        private int current_ie;
        private object context;

        private object currentValue;

        public virtual object Current 
        {
            get 
            {
                if (current_ie >= ies.Length)
                    throw new InvalidOperationException("exhausted enumerator");
                return
                    this.currentValue;
            }
        }

        public virtual bool MoveNext() 
        {
            if (current_ie >= ies.Length)
                return false;
            while (current_ie < ies.Length) {
                if (((IEnumerator!)ies[current_ie]).MoveNext()) {
                    object value = ((IEnumerator!)ies[current_ie]).Current;
                    if (this.filter != null) {
                        value = filter(value, this.context);
                        if (value == null) // skip this one
                        {
                            continue;
                        }
                    }
                    this.currentValue = value;
                    return true;
                }
                ((IEnumerator!)ies[current_ie]).Reset();
                current_ie++;                
            }
            return false;
        }

        public virtual void Reset() 
        {
            if (current_ie < ies.Length)
                ((IEnumerator!)ies[current_ie]).Reset();
            current_ie = 0;
        }
    }
}