|
Taxonomy.java
|
// FILE. . . . . /home/hak/hlt/src/hlt/osf/exec/Taxonomy.java // EDIT BY . . . Hassan Ait-Kaci // ON MACHINE. . Hp-Dv7 // STARTED ON. . Mon Nov 05 18:05:54 2012
|
package hlt.osf.exec; import hlt.osf.base.Sort; import hlt.osf.io.DisplayManager; import hlt.osf.util.BitCode; import hlt.osf.util.LockedBitCodeException; import hlt.language.tools.Misc; import hlt.language.tools.Debug; import hlt.language.util.ArrayList; import hlt.language.util.IntArrayList; import hlt.language.util.IntIterator;
| This is a class extending ArrayList for storing Sort objects. |
public class Taxonomy extends ArrayList implements Contextable
{
/* ************************************************************************ */
| Construct a taxonomy. |
public Taxonomy ()
{
super();
_RANKS = new IntArrayList();
}
| Construct a taxonomy of the specified initial capaciity. |
public Taxonomy (int initialCapacity)
{
super(initialCapacity);
_RANKS = new IntArrayList(initialCapacity);
}
| Construct a taxonomy with the specified Context. |
public Taxonomy (Context context)
{
this();
_context = context;
}
| Construct a taxonomy of the specified initial capaciity and the specified Context. |
public Taxonomy (int initialCapacity, Context context)
{
this(initialCapacity);
_context = context;
}
/* ************************************************************************ */
| This taxonomy's sort ordering context. |
private Context _context;
| Returns this taxonomy's sort ordering context. |
public Context context ()
{
return _context;
}
| Set this taxonomy's sort ordering context to the specified one. |
public Taxonomy setContext (Context context)
{
_context = context;
return this;
}
/* ************************************************************************ */
| This IntArrayList contains the actual ranks for each sort in this taxonomy based on their index fields (since those no longre correspond to their ranks after reordering, while they do correspond to the bit positions in the encoded sorts codes). Hence, it is a permutation of the first integers from 0 to size()-1. |
private IntArrayList _RANKS;
/* ************************************************************************ */
| This returns the sort with specified index in this taxonomy. |
public Sort getSort (int index)
{
return (Sort)get(_RANKS.get(index));
}
/* ************************************************************************ */
| This is false as long as the current sort taxonomy has not been encoded; true otherwise. |
private static boolean _isLocked = false;
| Returns true iff the current sort taxonomy has been been encoded. |
public static boolean isLocked ()
{
return _isLocked;
}
| Locks this taxonomy, initializes the top sort to have the correct number of bits set, sets the top and bottom sorts to have the right context and registers them in the named sort array and the code cache. |
private void _lock ()
{
_isLocked = true;
}
| Unlocks this taxonomy. |
public void unlock ()
{
_isLocked = false;
}
/* ************************************************************************ */
| Encodes all the sorts of this taxonomy. |
public void encodeSorts () throws AnomalousSituationException
{
// encode all the defined sorts in this sort code array:
encodeSorts(0,size()-1);
// sets the sort code size to be the size of this code array + 1
// to account for top (added further down in this method):
Sort.setCodeSize(size()+1);
// lock this code array:
_lock();
// add the top sort at the highest index in this sort code array
// and set its bit code to be all ones for the relevant bit code
// width:
add(Sort.top());
Sort.top().setIndex(size()-1).code.set(0,size());
_RANKS.set(Sort.top().index,Sort.top().index);
// initialize the context of the bottom and top sorts:
Sort.bottom().setContext(_context);
Sort.top().setContext(_context);
// register top and bottom in the named sort array and the code cache:
_context.namedSorts().put(Sort.top().name,Sort.top());
_context.codeCache().put(Sort.top().code,Sort.top());
_context.namedSorts().put(Sort.bottom().name,Sort.bottom());
_context.codeCache().put(Sort.bottom().code,Sort.bottom());
}
| Encodes the sorts between index first and index last (both inclusive) of this sort code array, reorders it so that a sort is always below its upper sorts, and check for cycles, committing all defined sorts in the specified range. |
public void encodeSorts (int first, int last)
throws AnomalousSituationException, LockedCodeArrayException, CyclicSortOrderingException
{
if (first > last)
throw new AnomalousSituationException("No sorts have been defined to encode");
if (_isLocked)
throw new LockedCodeArrayException("Unable to encode an already encoded sort taxonomy");
// perform the encoding by transitive closure:
_transitiveClosure(first,last);
// reorder this sort array to have a sort below its upper sorts:
_reorder(first,last);
// check for cycles and commit all defined sorts:
if (_checkForCycles(first,last))
throw new CyclicSortOrderingException(_cycles);
}
/* ************************************************************************ */
| This performs an transitive closure on the codes of the sorts stored in this taxonomy using Warshall's algorithm. This assumes that all the elements's codes have been set to their initial values as explained in the specification. |
private void _transitiveClosure ()
{
_transitiveClosure(0,size()-1);
}
| This performs in-place transitive closure on the codes of the sorts stored in this taxonomy of all the elements between index first and index last (both inclusive). |
private void _transitiveClosure (int first, int last)
{
for (int k=first; k<=last; k++)
for (int i=first; i<=last; i++)
for (int j=first; j<=last; j++)
{
Sort sort_i = (Sort)get(i);
if (!sort_i.code.get(j))
sort_i.code.set(j,sort_i.code.get(k) && ((Sort)get(k)).code.get(j));
}
}
/* ************************************************************************ */
| This reorders in-place this taxonomy using the "precedes" comparison on Sort objects with (non-recursive) QuickSort. This assumes that all the elements' codes have their final values after transitive closure. |
private void _reorder ()
{
Misc.sort(this);
}
| This reorders in-place the elements of this taxonomy between index first and index last (both inclusive) using the "precedes" comparison on Sort objects with (non-recursive) QuickSort. This assumes that all the elements' codes have their final values after transitive closure. |
private void _reorder (int first, int last)
{
Misc.sort(this,first,last);
}
/* ************************************************************************ */
| This is used to record and report potential cycles that may be detected in the current taxonomy. |
private ArrayList _cycles = new ArrayList();
| Checks for cycles in this taxonomy as explained in the specification for all its elements. (Assuming it has been encoded and reordered.) |
private boolean _checkForCycles ()
{
return _checkForCycles(0,size()-1);
}
| Checks for cycles in this taxonomy as explained in the specification for its elements between index first and index last (both inclusive). As this proceeds, all defined sorts in the specifes range are committed. This assumes that this sort code array has been encoded and reordered. |
private boolean _checkForCycles (int first, int last)
{
// make sure that _RANKS can contain all defined sorts + top
_RANKS.ensureCapacity(size()+1);
_cycles.clear();
ArrayList cycle = null;
Sort sort = null;
Sort prev = null;
for (int i=first; i<=last; i++)
{
sort = (Sort)_commitSort(i);
if (prev != null && sort.code.equals(prev.code))
{ // this is a cycle
if (cycle == null)
{ // this cycle is new; create a record for it
cycle = new ArrayList();
// and initialize it with the previous sort
cycle.add(prev.name);
}
// record the current sort as part of the cycle
cycle.add(sort.name);
}
else
{ // this sort is not part of a cycle; make it the previous sort
prev = sort;
if (cycle != null)
{ // a complete cycle was detected: record it
_cycles.add(cycle);
// and reinitialize it for potential new cycles
cycle = null;
}
}
}
return !_cycles.isEmpty();
}
/* ************************************************************************ */
public void reset (int minIndex)
{
clear(minIndex);
_RANKS.clear(minIndex);
}
/* ************************************************************************ */
| This returns the sort at the specified rank position in this taxonomy after recording this position in this taxonomy in _RANKS, and registering its name and code in the named sort table and its code in the code cache. It also does some cleaning up of the sort, erasing its set of is-a declarations set since it is no longer needed and takes useless space. This method is used in the _checkForCycles method as it visits each taxonomy element exactly once - unless a cycle is detected. In the latter case, a CyclicSortOrderingException is thrown that invalidates the sort ordering context, which should then be reset upon catching this exception. |
private Sort _commitSort (int rank)
{
Sort sort = (Sort)get(rank);
_RANKS.set(sort.index,rank);
_context.namedSorts().put(sort.name,sort);
_context.codeCache().put(sort.code,sort);
sort.clearIsaDeclarations();
return sort.lock();
}
/* ************************************************************************ */
| This returns a bit code representing the set of sorts whose codes are the maximal lower bounds of the specified bit code as explained in the specification. Note that the returned bit code may be empty (if the code is the bottom sort's code). This assumes that this this taxonomy has been encoded (and therefore reordered). |
public BitCode maxLowerBounds (BitCode code) throws LockedCodeArrayException
{
return maxLowerBounds(code,new BitCode());
}
public BitCode maxLowerBounds (BitCode code, BitCode mlbs)
throws LockedCodeArrayException, LockedBitCodeException
{
if (!_isLocked)
throw new LockedCodeArrayException("Attempt to perform an operation requiring prior sort encoding");
Sort s = null;
Sort t = null;
int size = size();
for (int i=0; i<size; i++)
{
s = (Sort)get(i);
if (code.isContainedIn(s.code))
// no need to go further: all higher sorts are supersorts or incomparable
break;
if (s.code.isContainedIn(code))
{
// this is a lower bound; if mlbs has subsorts of this
// remove them before keeping this higher lower bound:
for (IntIterator it = mlbs.iterator(); it.hasNext();)
{
t = getSort(it.next());
if (t.code.isStrictlyContainedIn(s.code))
mlbs.remove(t.index);
}
mlbs.add(s.index);
}
}
return mlbs.lock();
}
/* ************************************************************************ */
| This returns a bit code representing the set of sorts whose codes are the minimal upper bounds of the specified bit code as explained in the specification. Note that the returned bit code may be empty (if the code is the top sort's code). This assumes that this this taxonomy has been encoded (and therefore reordered). |
public BitCode minUpperBounds (BitCode code) throws LockedCodeArrayException
{
return minUpperBounds(code,new BitCode());
}
public BitCode minUpperBounds (BitCode code, BitCode mubs)
throws LockedCodeArrayException, LockedBitCodeException
{
if (!_isLocked)
throw new LockedCodeArrayException("Attempt to perform an operation requiring prior sort encoding");
Sort s = null;
Sort t = null;
for (int i=size(); i-->0;)
{
s = (Sort)get(i);
if (s.code.isContainedIn(code))
// no need to go further: all lower sorts are subsorts or incomparable
break;
if (code.isContainedIn(s.code))
{
// this is an upper bound; if mubs has supersorts of this
// remove them before keeping this lower upper bound:
for (IntIterator it = mubs.iterator(); it.hasNext();)
{
t = getSort(it.next());
if (s.code.isStrictlyContainedIn(t.code))
mubs.remove(t.index);
}
mubs.add(s.index);
}
}
return mubs.lock();
}
/* ************************************************************************ */
| Returns the height of the specified sort in its taxonomy. (See the specification.) |
public int computeHeight (Sort sort) throws LockedCodeArrayException
{
if (!isLocked())
throw new LockedCodeArrayException("Can't compute sort heights in a non-encoded taxonomy");
int height = 0;
for (IntIterator it = sort.code.iterator(); it.hasNext();)
{
int index = it.next();
if (index >= size())
break;
if (index == sort.index)
continue;
height = Math.max(height,computeHeight((Sort)getSort(index)));
}
return 1 + height;
}
/* ************************************************************************ */
| Returns the set of descendants of the specified sort as a BitCode. (See the specification.) |
public BitCode computeDescendants (Sort sort) throws LockedCodeArrayException
{
if (!isLocked())
throw new LockedCodeArrayException("Can't compute sort descendantss in a non-encoded taxonomy");
return sort.code.copy().remove(sort.index).lock();
}
/* ************************************************************************ */
| Returns the set of ancestors of the specified sort as a BitCode. (See the specification.) |
public BitCode computeAncestors (Sort sort) throws LockedCodeArrayException
{
if (!isLocked())
throw new LockedCodeArrayException("Can't compute sort ancestors in a non-encoded taxonomy");
// If the sort is top, return its code (top's):
if (sort.isTop())
return sort.code;
// If the sort is bottom, return all the sorts, except top:
if (sort.isBottom())
return Sort.top().descendants();
BitCode ancs = new BitCode();
// Collect all sorts of higher rank (except top) with a bit at sort's index set to true:
int index = sort.index;
int rank = _RANKS.get(index)+1;
for (int i=size()-1; i-->rank;)
{
Sort s = (Sort)get(i);
if (s.code.get(index))
ancs.add(s.index);
}
return ancs.lock();
}
/* ************************************************************************ */
| This displays all the defined sorts in this taxonomy using the specified display manager. |
public void showSortCodes ()
{
showSortCodes(0,size()-2);
}
| This displays the elements of this taxonomy between index first and index last (both inclusive) using the specified display manager. It always displays @ at the top (with no index) and {} at the bottom (with no index). |
public void showSortCodes (int first, int last)
{
int width = Misc.numWidth(last);
DisplayManager dm = _context.displayManager();
dm.println(Misc.repeat(2*width+1,' ')+" "+
Sort.top().code+" "+
Sort.top().name);
for (int i=last; i>=first; i--)
{
Sort sort = (Sort)get(i);
dm.println(Misc.numberString(i,width)+" "+
Misc.numberString(sort.index,width)+" "+
sort.code+" "+
sort.name);
}
dm.println(Misc.repeat(2*width+1,' ')+" "+
Sort.bottom().code+" "+
Sort.bottom().name);
}
/* ************************************************************************ */
}
This file was generated on Wed Jan 30 13:26:29 CET 2013 from file Taxonomy.java
by the hlt.language.tools.Hilite Java tool written by Hassan Aït-Kaci