//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\
// PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\

using System;
using System.Text;
using System.Collections;
using Ilog.Language.Util;

namespace Ilog.Language.Util
{
  /**
   * This class is a generic data type for sets of objects. Instances of
   * this class denote subsets of a fixed reference set - an <tt>ArrayList</tt>
   * of <b>Object</b>s - called the <i>base structure</i>. All sets operations
   * are implemented efficiently using an underlying bitset representation.
   * In effect, using this class alleviates the need to deal directly with the
   * represention and always manipulate sets as implicit collections of
   * objects.
   * <p>
   * <b>NB:</b> There are some important caveats to be aware of when using
   * <tt>SetOf</tt>:
   * <ul>
   * <li> this class will work correctly assuming that no element
   *      is ever removed from the base structure;
   * <li> for efficiency reasons, no check is made that the base
   *      structure is indeed a set (<i>i.e.</i>, contains no duplicates);
   * </ul>
   *
   *
   * @version     Last modified on Fri May 20 20:02:17 2005 by hak
   * @author      <a href="mailto:hak@ilog.fr">Hassan A&iuml;t-Kaci</a>
   * @copyright   &copy; 2000 <a href="http://www.ilog.fr/">ILOG, S.A.</a>
   */
  public class SetOf : IEnumerable
    {
      /**
       * The base structure comprising the collection of all elements
       * that may belong to this set.
       */
      private ArrayList elements;

      /**
       * This set's underlying representation as a bit word.
       */
      private BitSet carrier;

      /**
       * Constructs a new (empty) set with the specified array.
       * <b>NB:</b> the concrete list structure used is an <tt>ArrayList</tt>.
       *
       * @param elements base structure as an array
       */
      public SetOf (Object[] elements)
	{
	  this.elements = new ArrayList(elements.Length);

	  for (int i=0; i<elements.Length; i++)
	    this.elements.Add(elements[i]);

	  carrier = new BitSet(elements.Length);
	}

      /**
       * Constructs a new (empty) set with the specified ArrayList elements.
       *
       * @param elements the reference set as an ArrayList.
       */
      public SetOf (ArrayList elements)
	{
	  this.elements = elements;
	  carrier = new BitSet();
	}

      /**
       * Constructs a new singleton set containing the element at
       * the specified index from the specified ArrayList of elements.
       *
       * @param elements the reference set as an ArrayList
       * @param index the index of the object
       */
      public SetOf (ArrayList elements, int index)
	{
	  new SetOf(elements).Add(index);
	}

      /**
       * Constructs a new singleton set containing the single
       * specified index from the specified array of elements.
       *
       * @param elements the reference set as an array
       * @param index the index of the object
       */
      public SetOf (Object[] elements, int index)
	{
	  new SetOf(elements).Add(index);
	}

      /**
       * Constructs a new singleton set containing the single
       * specified object from the specified ArrayList of elements.
       *
       * @param elements the reference set as an ArrayList
       * @param object the object
       */
      public SetOf (ArrayList elements, Object elt)
	{
	  new SetOf(elements).Add(elt);
	}

      /**
       * Constructs a new singleton set containing the single
       * specified object from the specified array of elements.
       *
       * @param elements the reference set as an array
       * @param elt the object
       */
      public SetOf (Object[] elements, Object elt)
	{
	  new SetOf(elements).Add(elt);
	}

      /**
       * Constructs a copy of the  specified set.
       *
       * @param set the set to copy
       */
      public SetOf (SetOf set)
	{
	  elements = set.elements;
	  carrier = new BitSet(set.carrier);
	}

      /**
       * Constructs a new set with the specified elements and underlying
       * bitset representation.
       *
       * @param elements the reference set as an array
       * @param carrier the bitset representation
       */
      public SetOf (Object[] elements, BitSet carrier)
	{
	  this.elements = new ArrayList(elements.Length);
	  for (int i=0; i<elements.Length; i++)
	    this.elements.Add(elements[i]);
	  this.carrier = carrier;
	}

      /**
       * Constructs a new set with the specified elements and underlying
       * bitset representation.
       *
       * @param elements the reference set as an ArrayList
       * @param carrier the bitset representation
       */
      public SetOf (ArrayList elements, BitSet carrier)
	{
	  this.elements = elements;
	  this.carrier = carrier;
	}

      //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\

      /**
       * A private representation for the full set.
       */
      private static SetOf FULL_SET;

      //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\

      /**
       * Using this indexer on an object, one can test for containment as
       * it will return true or false depending on whether or not the object
       * belongs to this set. Accordingly, assigning true or false to this
       * set indexed by an object will add or remove it from this set.
       */
      public bool this [Object elt]
	{
	  get
	    {
	      return Contains(elt);
	    }
	  set
	    {
	      if (value)
		Add(elt);
	      else
		Remove(elt);
	    }
	}

      /**
       * This denotes the number of elements in this set.
       * Identical to <tt>Size</tt>.
       */
      public int Count
	{
	  get
	    {
	      return carrier.Cardinality;
	    }	  
	}

      /**
       * This denotes the number of elements in this set.
       * Identical to <tt>Count</tt>.
       */
      public int Size
	{
	  get
	    {
	      return carrier.Cardinality;
	    }	  
	}

      /**
       * This is a set representing this set's reference collection; that is,
       * a set containing all the base structure's elements.
       */
      public SetOf Top
	{
	  get
	    {
	      if (FULL_SET==null || FULL_SET.elements != elements)
	        {
		  FULL_SET = new SetOf(elements);
		  for (int i=0; i<elements.Count; i++)
		    FULL_SET.carrier.Set(i);
		}
	      return FULL_SET;
	    }
	}

      /**
       * This is true iff this set contains all the base structure's elements.
       */
      public bool IsFull
	{
	  get { return carrier.Equals(Top.carrier); }
	}

      /**
       * This is true iff this set is empty.
       */
      public bool IsEmpty
	{
	  get { return carrier.IsEmpty; }
	}

      /**
       * Returns the index of a specified object element of this set.
       *
       * @param elt the object
       * @return the desired index or -1 if the object is not there
       */
      public int IndexOf (Object elt)
	{
	  if (elt is Indexed)			// WARNING: this assumes that elt.index()
	    return ((Indexed)elt).Index;	// is in fact its position in elements

	  return elements.IndexOf(elt);
	}

      /**
       * Clears the contents of this set.
       *
       * @return this empty set
       */
      public SetOf Clear ()
	{
	  carrier.Clear();
	  return this;
	}

      /**
       * Adds the element of specified index into this set.
       *
       * @param index the index
       * @return this set
       */
      public SetOf Add (int index)
	{
	  carrier.Set(index);
	  return this;
	}

      /**
       * Adds a specified object into this set.
       *
       * @param elt the object
       * @return this set
       */
      public SetOf Add (Object elt)
	{
	  carrier.Set(IndexOf(elt));
	  return this;
	}

      /**
       * Returns a new set obtained from the given set after adding
       * the given index.
       *
       * @param s a set
       * @param index the index
       * @return a new set which is s with the object at index added
       */
      public static SetOf Add (SetOf s, int index)
	{
	  SetOf newset = new SetOf(s);
	  newset.carrier.Set(index);
	  return newset;
	}

      /**
       * Removes the element of specified index from this set.
       *
       * @param index the index
       * @return this set
       */
      public SetOf Remove (int index)
	{
	  carrier.Clear(index);
	  return this;
	}

      /**
       * Removes the specified object from this set.
       *
       * @param elt the object
       * @return this set
       */
      public SetOf Remove (Object elt)
	{
	  carrier.Clear(IndexOf(elt));
	  return this;
	}

      /**
       * Returns a new set obtained from the given set after removing
       * the given index.
       *
       * @param s a set
       * @param index the index
       * @return a new set which is s deprived of the object at index
       */
      public static SetOf Remove (SetOf s, int index)
	{
	  SetOf newset = new SetOf(s);
	  newset.carrier.Clear(index);
	  return newset;
	}

      /**
       * Returns the index of the first element in this set or -1
       * if empty.
       *
       * @return the desired index or -1 if empty.
       */
      public int FirstIndex ()
	{
	  foreach (int i in carrier)
	    return i;

	  return -1;
	}

      /**
       * Returns the first element in this set or null if empty.
       *
       * @return the desired element or <b>null</b> if empty.
       */
      public Object FirstElement ()
	{
	  int i = FirstIndex();
	  return (i<0) ? null : elements[i];
	}

      /**
       * <i><b>NB:</b> The following set operations assume that all
       * operands refer to the same base structure.</i>
       */

      /**
       * Modifies this set to the union of this set and the specified set.
       *
       * @param other a set
       * @return this set
       */
      public SetOf Union (SetOf other)
	{
	  carrier.Or(other.carrier);
	  return this;
	}

      /**
       * Returns a new set equal to the union of two sets without modifying
       * either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the union of one and two
       */
      public static SetOf Union (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.Or(two.carrier);
	  return newset;
	}

      /**
       * Returns a new set equal to the union of two sets without modifying
       * either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the union of one and two
       */
      public static SetOf operator + (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.Or(two.carrier);
	  return newset;
	}

      /**
       * Modifies this set to the intersection of this set and the specified set.
       *
       * @param other a set
       * @return this set
       */
      public SetOf Intersection (SetOf other)
	{
	  carrier.And(other.carrier);
	  return this;
	}

      /**
       * Returns a new set equal to the intersection of two sets without
       * modifying either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the intersection of one and two
       */
      public static SetOf Intersection (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.And(two.carrier);
	  return newset;
	}

      /**
       * Returns a new set equal to the intersection of two sets without
       * modifying either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the intersection of one and two
       */
      public static SetOf operator & (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.And(two.carrier);
	  return newset;
	}

      /**
       * Modifies this set to the symmetric difference of this set and the
       * specified set.
       *
       * @param other a set
       * @return this set
       */
      public SetOf Exclusion (SetOf other)
	{
	  carrier.Xor(other.carrier);
	  return this;
	}

      /**
       * Returns a new set equal to the symmetric difference of two sets
       * without modifying either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the symmetric difference of one and two
       */
      public static SetOf Exclusion (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.Xor(two.carrier);
	  return newset;
	}

      /**
       * Returns a new set equal to the symmetric difference of two sets
       * without modifying either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the symmetric difference of one and two
       */
      public static SetOf operator ^ (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.Xor(two.carrier);
	  return newset;
	}

      /**
       * Modifies this set to the set difference of this set and the
       * specified set.
       *
       * @param other a set
       * @return this set
       */
      public SetOf Minus (SetOf other)
	{
	  carrier.AndNot(other.carrier);
	  return this;
	}

      /**
       * Returns a new set equal to the set difference of two sets without
       * modifying either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the difference of one and two
       */
      public static SetOf Minus (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.AndNot(two.carrier);
	  return newset;
	}

      /**
       * Returns a new set equal to the set difference of two sets without
       * modifying either one.
       *
       * @param one a set
       * @param two a set
       * @return a new set which is the difference of one and two
       */
      public static SetOf operator - (SetOf one, SetOf two)
	{
	  SetOf newset = new SetOf(one);
	  newset.carrier.AndNot(two.carrier);
	  return newset;
	}

      /**
       * Modifies this set to its complement (relative to the full set of
       * elements).
       *
       * @return this set
       */
      public SetOf Not ()
	{
	  carrier.Xor(Top.carrier);
	  return this;
	}

      /**
       * Returns a new set equal to the complement (relative to the full
       * set of elements) of the specified set without modifying it.
       *
       * @param s a set
       */
      public static SetOf Not (SetOf s)
	{
	  SetOf newset = new SetOf(s);
	  newset.carrier.Xor(s.Top.carrier);
	  return newset;
	}

      /**
       * Returns a new set equal to the complement (relative to the full
       * set of elements) of the specified set without modifying it.
       *
       * @param s a set
       */
      public static SetOf operator - (SetOf s)
	{
	  SetOf newset = new SetOf(s);
	  newset.carrier.Xor(s.Top.carrier);
	  return newset;
	}

      /**
       * Returns true iff the specified index is that of an element of this set.
       *
       * @param index the index
       */
      public bool ContainsIndex (int index)
	{
	  return carrier.Get(index);
	}

      /**
       * Returns true iff the specified object is an element of this set.
       *
       * @param elt the object
       */
      public bool Contains (Object elt)
	{
	  return carrier.Get(IndexOf(elt));
	}

      /**
       * Returns true iff this set is included in or equal to the
       * specified set.
       *
       * @param other a set
       */
      public bool IsSubsetOf (SetOf other)
	{
	  return carrier.IsSubsetOf(other.carrier);
	}

      /**
       * Returns true iff set one is included in or equal to set two.
       *
       * @param one a set
       * @param two a set
       */
      public static bool operator <= (SetOf one, SetOf two)
	{
	  return one.carrier.IsSubsetOf(two.carrier);
	}

      /**
       * Returns true iff set two is included in or equal to set one.
       *
       * @param one a set
       * @param two a set
       */
      public static bool operator >= (SetOf one, SetOf two)
	{
	  return two.carrier.IsSubsetOf(one.carrier);
	}

      /**
       * Returns true iff this set is strictly included in the
       * specified set.
       *
       * @param other a set
       */
      public bool isStrictSubsetOf (SetOf other)
	{
	  return carrier.IsStrictSubsetOf(other.carrier);
	}

      /**
       * Returns true iff set one is strictly included in set two.
       *
       * @param one a set
       * @param two a set
       */
      public static bool operator < (SetOf one, SetOf two)
	{
	  return one.carrier.IsStrictSubsetOf(two.carrier);
	}

      /**
       * Returns true iff set two is strictly included in set one.
       *
       * @param one a set
       * @param two a set
       */
      public static bool operator > (SetOf one, SetOf two)
	{
	  return two.carrier.IsStrictSubsetOf(one.carrier);
	}

      /**
       * Returns true iff this set is equal to the specified set.
       *
       * @param other a set
       */
      public bool IsEqualTo (SetOf other)
	{
	  return carrier.Equals(other.carrier);
	}

      /**
       * Returns true iff the specified object is a set equal to this.
       *
       * @param other an object
       */
      public override bool Equals (Object other)
	{
	  if (other is SetOf)
	    return carrier.Equals(((SetOf)other).carrier);
	  return false;
	}

      /**
       * Returns a hashcode for this set.
       */
      public override int GetHashCode ()
	{
	  return carrier.GetHashCode();
	}

      /**
       * Returns a string representation of this set as a comma-separated
       * elements of elements between curly braces.
       */
      public override String ToString ()
	{
	  StringBuilder buffer = new StringBuilder(3*Count+2).Append('{');
	  String separator = "";

	  foreach (int i in carrier)
	    {
	      buffer.Append(separator);
	      separator = ", ";
	      buffer.Append(elements[i]);
	    }

	  return buffer.Append('}').ToString();
	}

      /**
       * Returns a string representation of this set as a bit string of 0's and 1's.
       */
      public String ToBitString ()
	{
	  return ToBitString('0','1');
	}

      /**
       * Returns a string representation of this set as a bit string of two
       * specified characters standing for "absent" and "present" respectively.
       *
       * @param out a character
       * @param in a character
       */
      public String ToBitString (char off, char on)
	{
	  StringBuilder s = new StringBuilder(elements.Count);
	  for (int i=0; i<elements.Count; i++)
	    s.Append(carrier.Get(i) ? on : off);
	  return s.ToString();
	}

      /**
       * Returns an enumerator for elements of this set.<br>
       */
      public IEnumerator GetEnumerator ()
	{
	  foreach (int i in carrier)
	    yield return elements[i];
	}

      /**
       * Returns an enumeration-like object over the base structure's indices for
       * the elements of this set.
       */
      public IEnumerator GetIndexEnumerator ()
	{
	  return carrier.GetEnumerator();
	}
    }
}