*
* So computing the set of ancestors of a sort s works as
* follows:
*
*
*
* Let s.index() be the index of sort s in the
* array TAXONOMY (i.e., TAXONOMY[s.index()] ==
* s);
*
* Let nonDescendants be the set represented as a bit
* vector of sort indices i, such that
* nonDescendants.bit(i) = 1 iff
* TAXONOMY[i].bit(s.index()) == 0—in other words, (a
* copy of) the Boolean negation of the bit vector
* TAXONOMY[i] obtained as: nonDescendants =
* TAXONOMY[i].not().copy();
*
* Let s.ancestors be a bit vector initialized to be
* nonDescendants;
*
* Set s.ancestors.bit(j) = 0 whenever
* TAXONOMY[j].bit(s.index()) == 0;
*
* What is left with s.ancestors is a bit vector with
* 1s in all and only those positions that are indices of
* sorts that are in nonDescendants but comparable with
* s; namely its ancestors.
*
*
*
*
*
* This is because all ancestors of s must have a code
* containing a 1 wherever there is a 1 in the
* code of s (because all descendants of s are
* also descencants of any ancestor of s, by definition of
* the transitive-closure code).
*
*/
public BitCode getAncestors (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 null:
if (sort.isTop())
return null;
// If the sort is bottom, return a copy of top:
if (sort.isBottom())
return Sort.top().copy();
// otherwise, create the negation of the sort's code; it will be a
// superset of ancestors (as a set, not as a code)
BitCode wouldBeAncestors = sort.code.not();
for (IntIterator it = wouldBeAncestors.iterator(); it.hasNext();)
{
Int index = it.next();
// TAXONOMY[index] is a potential ancestor of sort"
Sort wouldBeAncestor = TAXONOMY[index];
// keep in as true ancestor only if it is comparable to sort
// (i.e., only if sort.code'sbit at index is equal to 1):
wouldBeAncestors.set(index) = sort.code.get(index);
}
// System.out.println("\t==> "+wouldBeAncestors);
return wouldBeAncestors;
}
//////////////////////////////////////////////////////////////////////
// The following is the old way,. The new way is the version above.
//////////////////////////////////////////////////////////////////////
/**