// FILE. . . . . /home/hak/hlt/src/hlt/osfv1/base/Sort.java
// EDIT BY . . . Hassan Ait-Kaci
// ON MACHINE. . Hak-Laptop
// STARTED ON. . Mon Sep 02 09:16:33 2013

/**
 * This is the class of sorts as explained in the <a
 * href="../specs/basic.html#SortClass">specification</a>.
 *
 * @version     Last modified on Fri Sep 06 08:19:06 2013 by hak
 * @author      <a href="mailto:hak@acm.org">Hassan A&iuml;t-Kaci</a>
 * @copyright   &copy; <a href="http://www.hassan-ait-kaci.net/">by the author</a>
 */

package hlt.osf.base;

import java.util.HashSet;

import hlt.osf.util.BitCode;
import hlt.osf.exec.Context;
import hlt.osf.exec.Taxonomy;
import hlt.osf.exec.LockedCodeArrayException;

import hlt.language.util.Comparable;

public class Sort implements Comparable
  {
    /* ************************************************************************ */

    /**
     * The index of this Sort.
     */
    public int index;

    /**
     * The name of this Sort.
     */
    public String name;

    /**
     * The bit vector code of this Sort.
     */
    public BitCode code;

    /* ************************************************************************ */

    /**
     * Constructs a Sort object with the specified name.
     */
    public Sort (String name)
    {
      this.name = name.intern();
    }
    
    /**
     * Constructs a Sort object with the specified index and name.
     */
    public Sort (int index, String name)
    {
      this.index = index;
      this.name = name.intern();
    }
    
    /**
     * Constructs a Sort object with the specified index, name, and bit code.
     */
    public Sort (int index, String name, BitCode code)
    {
      this.index = index;
      this.name = name.intern();
      this.code = code;
    }

    /**
     * Sets the index of this Sort object to the specified index, and
     * returns this sort.
     */
    public Sort setIndex (int index)
    {
      this.index = index;
      return this;
    }

    /* ************************************************************************ */
    
    /**
     * Sets the bit code of this Sort object to the specified bit code,
     * and returns this sort.
     */
    public Sort setCode (BitCode code)
    {
      this.code = code;
      return this;
    }

    /* ************************************************************************ */

    /**
     * Returns true iff this sort is a subsort of the specified sort.
     */
    public boolean isSubsortOf (Sort sort)
    {
      return this.code.isContainedIn(sort.code);
    }

    /**
     * Returns true iff this sort is a strict subsort of the specified sort.
     */
    public boolean isStrictSubsortOf (Sort sort)
    {
      return this.code.isStrictlyContainedIn(sort.code);
    }

    /**
     * Returns true iff this sort is unrelated to the specified sort.
     */
    public boolean isUnrelatedTo (Sort sort)
    {
      return this.code.isUnrelatedTo(sort.code);
    }

    /* ************************************************************************ */

    private Context _context;

    public Context context ()
    {
      return _context;
    }

    public Sort setContext (Context context)
    {
      _context = context;
      return this;
    }

    /* ************************************************************************ */

    /**
     * This defines the sort code size for all Boolean computations on,
     * and printing of, sort codes. This is necessary for consistency
     * since only bits within this code size do matter. It is set in the
     * <tt><a href="Taxonomy.html">Taxonomy</a></tt> class
     * upon locking the defined sorts' code array.  This constant is
     * taken into account in Boolean operations (essentially by
     * '<i>not</i>') and code printing methods defined the <tt><a
     * href="BitCode.html">BitCode</a></tt> class.  For all sort codes,
     * all bits of index greater than or equal to this constant are
     * always false. This is also the index of top when it is
     * initialized and installed in the sort code array upon locking it.
     */
    private static int _CODESIZE;

    /**
     * Returns the sort code size for an encoded taxonomy. Raises a
     * LockedCodeArrayException if the sort code array is not locked.
     */
    public static int codeSize () throws LockedCodeArrayException
    {
      // if (!Taxonomy.isLocked())
      // 	throw new LockedCodeArrayException("Attempt to access code size for a non-encoded taxonomy");

      return _CODESIZE;
    }

    /**
     * Sets the sort code size for an encoded taxonomy. Raises a
     * LockedCodeArrayException if the sort code array is locked.
     */
    public static void setCodeSize (int size) throws LockedCodeArrayException
    {
      if (Taxonomy.isLocked())
	throw new LockedCodeArrayException("Cannot change the sort code size for an encoded taxonomy");

      _CODESIZE = size;
    }      

    /* ************************************************************************ */

    /**
     * This defines top as a static constant. Note that the index is set
     * to 0.  But this is temporary, as it will updated to its final
     * index when initialized and be stored in the sort code array. Its
     * final index will then be the value of _CODESIZE.
     */
    // private static Sort _TOP = new Sort(0,"@",new BitCode().lock());
    private static Sort _TOP = new Sort(0,"*EVERYTHING*",new BitCode().lock());

    /**
     * Returns the top sort as a static constant. This is safe only if
     * the taxonomy this is relative to has been encoded.  Raises a
     * LockedCodeArrayException if the sort code array is locked. This
     * is because its correct code size is only dtermined after the
     * sorts have been all encoded.
     */
    public static Sort top () // throws LockedCodeArrayException
    {
      // if (!Taxonomy.isLocked())
      // 	throw new LockedCodeArrayException("Attempt to access unsafe top sort for a non-encoded taxonomy");

      return _TOP;
    }

    /**
     * Return true iff this sort is top.
     */
    public boolean isTop ()
    {
      // return name == "@";
      return name == "*EVERYTHING*";
    }

    /* ************************************************************************ */

    /**
     * This defines bottom as a static constant. Note that the index is
     * set to -1.  This is because it is not stored in the sort code
     * array and therefore, its index is irrelevant. It is the only
     * sort not stored in the code array and whose height is always 0.
     */
    // private static Sort _BOTTOM = new Sort(-1,"{}",new BitCode().lock()).setHeight(0);
    private static Sort _BOTTOM = new Sort(-1,"*NOTHING*",new BitCode().lock()).setHeight(0);

    /**
     * Returns the bottom sort as a static constant.
     */
    public static Sort bottom ()
    {
      // if (!Taxonomy.isLocked())
      // 	throw new LockedCodeArrayException("Attempt to access unsafe bottom sort for a non-encoded taxonomy");

      return _BOTTOM;
    }

    /**
     * Return true iff this sort is bottom.
     */
    public boolean isBottom ()
    {
      // return name == "{}";
      return name == "*NOTHING*";
    }

    /* ************************************************************************ */

    /**
     * This contains the sorts that are declared as immediate parents of
     * this sort.
     */
    private HashSet _parents = new HashSet();

    /**
     * Returns the declared parents of this sort.
     */
    public HashSet parents ()
    {
      return _parents;
    }

    /**
     * Adds the specified sort as a parent of this sort, and returns
     * true iff that sort was not already a parent.
     */
    public boolean addParent (Sort s)
    {
      return _parents.add(s);
    }
   
    /**
     * Removes the specified sort as a parent of this sort, and returns
     * true iff that sort was indeed a parent.
     */
    public boolean removeParent (Sort s)
    {
      return _parents.remove(s);
    }
   
    /* ************************************************************************ */

    /**
     * This contains the sorts that are declared as immediate children
     * of this sort.
     */
    private HashSet _children = new HashSet();

    /**
     * Returns the declared children of this sort.
     */
    public HashSet children ()
    {
      return _children;
    }

    /**
     * Adds the specified sort as a child of this sort, and returns
     * true iff that sort was not already a child.
     */
    public boolean addChild (Sort s)
    {
      return _children.add(s);
    }

    /**
     * Removes the specified sort as a child of this sort, and returns
     * true iff that sort was indeed a child.
     */
    public boolean removeChild (Sort s)
    {
      return _children.remove(s);
    }
   
    /* ************************************************************************ */

    boolean minimal = true;
    boolean maximal = true;

    /**
     * Adds the specified sort to the set of parents of this sort, and
     * and this sort to the set of children of the specified
     * sort. Returns true if neither was there before (i.e., already
     * declared to be so). This also maintains the correct set for the
     * parents of bottom (i.e., the minimal sorts) and the children of
     * top (i.e., the maximal sorts).
     */
    public boolean addIsaDeclaration (Sort sort)
    {
      boolean b1 = addParent(sort);
      boolean b2 = sort.addChild(this);      
      
      if (minimal)
	{
	  _BOTTOM.addParent(this);
	  this.addChild(_BOTTOM);
	}

      if (maximal)
	{
	  maximal = false;
	  _TOP.removeChild(this);
	  this.removeParent(_TOP);
	}

      if (sort.maximal)
	{
	  _TOP.addChild(sort);
	  sort.addParent(_TOP);
	}

      if (sort.minimal)
	{
	  sort.minimal = false;
	  _BOTTOM.removeParent(sort);
	  sort.removeChild(_BOTTOM);
	}

      return b1 && b2;
    }

    /* ************************************************************************ */

    /**
     * The height of this Sort in its taxonomy. (See the <a
     * href="../specs/basic.html#height">specification</a>.)
     */
    private int _height = -1;

    /**
     * Returns the height of this Sort in its taxonomy. (See the <a
     * href="../specs/basic.html#height">specification</a>.)
     */
    public int height () throws LockedCodeArrayException
    {
      if (!Taxonomy.isLocked())
	throw new LockedCodeArrayException("Can't compute sort heights in a non-encoded taxonomy");
      
      if (_height != -1)
	return _height;

      return _height = _context.taxonomy().computeHeight(this);
    }

    public Sort setHeight (int height)
    {
      _height = height;
      return this;
    }

    public void resetHeight ()
    {
      _height = -1;
    }

    /* ************************************************************************ */

    /**
     * Returns the number of subsorts of this sort (not including itself).
     */
    public int numberOfDescendants ()
    {
      return this.code.cardinality()-1;
    }

    /* ************************************************************************ */

    /**
     * The set of descendants of this Sort in its taxonomy.
     */
    private HashSet _descendants;

    /**
     * Returns the set of descendants of this sort as a HashSet.
     */
    public HashSet descendants () throws LockedCodeArrayException
    {
      if (!Taxonomy.isLocked())
	throw new LockedCodeArrayException("Attempt to perform an operation requiring prior sort encoding");

      if (_descendants != null)
	return _descendants;

      if (isBottom())
	return null;

      return _descendants = _context.taxonomy().computeDescendants(this);
    }

    /* ************************************************************************ */

    /**
     * Returns the number of supersorts of this sort (not including itself).
     */
    int numberOfAncestors (Sort sort)
    {
      return ancestors().size();
    }

    /**
     * The set of ancestors of this Sort in its taxonomy.
     */
    private HashSet _ancestors;

    /**
     * Returns the set of ancestors of this sort as a HashSet.
     */
    public HashSet ancestors () throws LockedCodeArrayException
    {
      if (!Taxonomy.isLocked())
	throw new LockedCodeArrayException("Attempt to perform an operation requiring prior sort encoding");

      if (_ancestors != null)
	return _ancestors;

      if (isTop())
	return null;

      return _ancestors = _context.taxonomy().computeAncestors(this);
    }

    /* ************************************************************************ */

    /**
     * Returns true iff this is a strict lower sort of the specified
     * sort. This is used by the <tt>hlt.language.tools.Misc.sort</tt>
     * method used in class <tt>Taxonomy</tt> to sort the declared
     * sorts.
     */
    public boolean lessThan (Comparable sort)
    {
      return precedes((Sort)sort);
    }

    /**
     *  This defines the "precedes" ordering as described in the <a
     *  href="../specs/basic.html#precedes">specification</a>.  This is a
     *  topological ordering that respects the is-a ordering to ease the
     *  detection of potential cycles. A cycle is a set of sorts with
     *  equal codes after transitive closure has been performed. Using
     *  this "precedes" comparison to reorder the array will make all
     *  elements in a cycle be contiguous.
     */
    public boolean precedes (Sort sort)
    {
      if (this.code.isStrictlyContainedIn(sort.code))	// this is a proper subsort of sort
	return true;

      if (this.code.equals(sort.code))	// respect the index ordering for equal codes
	return this.index < sort.index;

      if (!sort.code.isContainedIn(this.code))	// for unrelated sorts
	{
	  int thisCodeSize = this.code.cardinality();
	  int sortCodeSize = sort.code.cardinality();

	  if (thisCodeSize == sortCodeSize)
	    { // So here, the two codes have same cardinality: the "least"
	      // code is the one with the least differring true bit
	      int i = this.code.nextSetBit(0);
	      int j = sort.code.nextSetBit(0);
	      while (i == j)
		{
		  i = this.code.nextSetBit(i+1);
		  j = sort.code.nextSetBit(j+1);
		}
	      return (i < j);
	    }
	  else
	    return (thisCodeSize < sortCodeSize);
	}

      return false;      
    }

    /**
     * Returns true iff this sort's name is equal to the specified one's.
     */
    public boolean equals (Sort sort)
    {
      return name == sort.name;
    }

    /**
     * Locks this sort's bit code - which means that its code will not
     * be modified by the 3 Boolean static bit code operations 'not',
     * 'and', and 'or'.
     */
    public Sort lock ()
    {
      code.lock();
      return this;
    }

    /**
     * Unlocks this sort's bit code - which means that its code may be
     * modified by the 3 Boolean static bit code operations 'not',
     * 'and', and 'or'.
     */
    public Sort unlock ()
    {
      code.unlock();
      return this;
    }

    /**
     * Returns true iff this sort's bit code is locked - which means
     * that its bit code will not be modified by the 3 Boolean static
     * operations 'not', 'and', and 'or'.
     */
    public boolean isLocked ()
    {
      return code.isLocked();
    }
    
    /**
     * Returns a string form of this Sort object. This string is its
     * name.
     */
    public String toString ()
    {
      return name;
    }
    
  }