public class GCI extends Inclusion {
    
    /**
     * 
     */
    private static final long serialVersionUID = 1L;

    // Logger
    private final static Logger log = LoggerFactory.getLogger(GCI.class);
    
    private static final int PRIME = 31;

    final private AbstractConcept lhs;
    final private AbstractConcept rhs;
    final private int hashCode;

    /**
     * lhs &#8849; rhs
     * 
     * @param lhs
     * @param rhs
     */
    public GCI(final AbstractConcept lhs, final AbstractConcept rhs) {
        if (null == lhs) {
            throw new IllegalArgumentException("LHS cannot be null (RHS = "
                    + rhs + ")");
        }
        this.lhs = lhs;
        if (null == rhs) {
            this.rhs = new Concept(IFactory.TOP_CONCEPT);
        } else {
            this.rhs = rhs;
        }
        hashCode = PRIME * (PRIME + this.lhs.hashCode()) + this.rhs.hashCode();
    }

    public GCI(final int lhs, final AbstractConcept rhs) {
        this(new Concept(lhs), rhs);
    }

    public GCI(final AbstractConcept lhs, final int rhs) {
        this(lhs, new Concept(rhs));
    }

    public GCI(final int lhs, final int rhs) {
        this(new Concept(lhs), new Concept(rhs));
    }

    public AbstractConcept lhs() {
        return lhs;
    }

    public AbstractConcept rhs() {
        return rhs;
    }

    public Inclusion[] normalise1(final IFactory factory) {
        final Inclusion[] result = { null, null };

        if (rule2(factory, result) || rule3(factory, result) || rule4(result)) {
            return result;
        }

        return null;
    }

    public Inclusion[] normalise2(final IFactory factory) {
        final Inclusion[] result = { null, null, null, null, null, null, null,
                null };

        if (isRule7Applicable()) {
            return rule7(result);
        } else if (rule6(factory, result) || rule5(factory, result)) {
            return result;
        }

        return null;
    }

    /**
     * C &#8851; D' &#8849; E &rarr; {D' &#8849; A, C &#8851; A &#8849; E}
     * 
     * @param gcis
     * @return
     */
    boolean rule2(final IFactory factory, final Inclusion[] gcis) {
        boolean result = false;

        if (lhs instanceof Conjunction) {
            Conjunction conjunction = (Conjunction) lhs;
            final AbstractConcept[] concepts = conjunction.getConcepts();

            if (concepts.length == 1) {
                // unwrap redundant conjuncts
                gcis[0] = new GCI(concepts[0], rhs);
                result = true;
            } else if (concepts.length == 0) {
                log.warn("Empty conjunct detected in: " + this);
                gcis[0] = new GCI(IFactory.TOP_CONCEPT, rhs);
                result = true;
            } else {
                // Swap out any non-Concept concepts (ie Existentials)
                for (int i = 0; !result && i < concepts.length; i++) {
                    if (!(concepts[i] instanceof Concept)) {
                        final Concept a = getA(factory, concepts[i]);
                        gcis[0] = new GCI(concepts[i], a);

                        final AbstractConcept[] newConcepts = new AbstractConcept[concepts.length];
                        System.arraycopy(concepts, 0, newConcepts, 0,
                                concepts.length);
                        newConcepts[i] = a;
                        gcis[1] = new GCI(new Conjunction(newConcepts), rhs);
                        result = true;
                    }
                }

                if (!result) {
                    if (concepts.length > 2) {
                        // Binarise a conjunction of Concepts (expected/assumed
                        // by NF1)
                        result = true;
                        final AbstractConcept[] newConcepts = new AbstractConcept[concepts.length - 1];
                        System.arraycopy(concepts, 1, newConcepts, 0,
                                concepts.length - 1);
                        final AbstractConcept d = new Conjunction(newConcepts);
                        final Concept a = getA(factory, d);
                        final AbstractConcept cAndA = new Conjunction(
                                new AbstractConcept[] { concepts[0], a });

                        gcis[0] = new GCI(cAndA, rhs);
                        gcis[1] = new GCI(d, a);
                    } else if (concepts.length < 2) {
                        throw new AssertionError(
                                "Conjunctions of fewer than "
                                        + "two elements should not exist at this point: "
                                        + this);
                    }
                }
            }
        }

        return result;
    }

    /**
     * &#8707;r.C' &#8849; D &rarr; {C' &#8849; A, &#8707;r.A &#8849; D}
     * 
     * @param gcis
     * @return
     */
    boolean rule3(final IFactory factory, final Inclusion[] gcis) {
        boolean result = false;

        if (lhs instanceof Existential) {
            Existential existential = (Existential) lhs;
            final AbstractConcept cHat = existential.getConcept();
            if (!(cHat instanceof Concept)) {
                result = true;
                Concept a = getA(factory, cHat);
                gcis[0] = new GCI(cHat, a);
                gcis[1] = new GCI(new Existential(existential.getRole(), a),
                        rhs);
            }
        }

        return result;
    }

    /**
     * &#8869; &#8849; D &rarr; &empty;
     * 
     * This rule matches &#8869; (bottom), but there is no &#x22A5; in our
     * Ontologies (AFAIK) so it's redundant.
     * 
     * @param gcis
     * @return
     */
    boolean rule4(Inclusion[] gcis) {
        boolean result = false;
        return result;
    }

    /**
     * C' &#8849; D' &rarr; {C' &#8849; A, A &#8849; D'}
     * 
     * @param gcis
     * @return
     */
    boolean rule5(final IFactory factory, final Inclusion[] gcis) {
        boolean result = false;

        if (!(lhs instanceof Concept) && !(rhs instanceof Concept)) {
            result = true;
            Concept a = getA(factory, lhs);
            gcis[0] = new GCI(lhs, a);
            gcis[1] = new GCI(a, rhs);
        }

        return result;
    }

    /**
     * B &#8849; &#8707;r.C' &rarr; {B &#8849; &#8707;r.A, A &#8849; C'}
     * 
     * @param gcis
     * @return
     */
    boolean rule6(final IFactory factory, final Inclusion[] gcis) {
        boolean result = false;

        if (rhs instanceof Existential) {
            Existential existential = (Existential) rhs;
            final AbstractConcept cHat = existential.getConcept();
            if (!(cHat instanceof Concept)) {
                result = true;
                Concept a = getA(factory, cHat);
                gcis[0] = new GCI(lhs,
                        new Existential(existential.getRole(), a));
                gcis[1] = new GCI(a, cHat);
            }
        }

        return result;
    }

    private Concept getA(final IFactory factory, final AbstractConcept cHat) {
        final boolean alreadyExists = factory.conceptExists(cHat);
        final int a = factory.getConcept(cHat);
        if(!alreadyExists) {
            factory.setVirtualConcept(a, true);
        }
        return new Concept(a);
    }

    boolean isRule7Applicable() {
        return rhs instanceof Conjunction;
    }

    /**
     * B &#8849; C &#8851; D &rarr; {B &#8849; C, B &#8849; D}
     * 
     * @param gcis
     * @return
     */
    Inclusion[] rule7(Inclusion[] gcis) {
        assert isRule7Applicable();

        final Conjunction conjunction = (Conjunction) rhs;
        final AbstractConcept[] concepts = conjunction.getConcepts();

        if (concepts.length > gcis.length) {
            gcis = new Inclusion[concepts.length];
        }

        for (int i = 0; i < concepts.length; i++) {
            gcis[i] = new GCI(lhs, concepts[i]);
        }

        return gcis;
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final GCI other = (GCI) obj;
        if (!lhs.equals(other.lhs))
            return false;
        if (!rhs.equals(other.rhs))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return lhs.toString() + " [ " + rhs.toString();
    }

    @Override
    public NormalFormGCI getNormalForm() {
        final NormalFormGCI result;
        // try {
        if (lhs instanceof Concept) {
            if (rhs instanceof Concept) {
                final int newLhs = lhs.hashCode();
                result = NF1a.getInstance(newLhs, rhs.hashCode());
            } else if (rhs instanceof Existential) {
                final Existential existential = (Existential) rhs;
                result = NF2.getInstance(lhs.hashCode(), existential.getRole(),
                        existential.getConcept().hashCode());
            } else if (rhs instanceof Datatype) {
                final Datatype datatype = (Datatype) rhs;
                result = NF7.getInstance(lhs.hashCode(), datatype);
            } else {
                throw new IllegalStateException("GCI is not in Normal Form: " +
                		"lhs is Concept but rhs is neither Concept, " +
                		"Existential nor Datatype; it is " + rhs);
            }
        } else if (lhs instanceof Conjunction) {
            final Conjunction conjunction = (Conjunction) lhs;
            final AbstractConcept[] concepts = conjunction.getConcepts();
            if (concepts.length == 1) {
                result = NF1a.getInstance(concepts[0].hashCode(),
                        rhs.hashCode());
            } else if (concepts.length == 2) {
                result = NF1b.getInstance(concepts[0].hashCode(),
                        concepts[1].hashCode(), rhs.hashCode());
            } else {
                throw new IllegalStateException(
                        "Conjunction should have exactly one or two "
                                + "concepts not " + concepts.length + ": "
                                + conjunction);
            }
        } else if (lhs instanceof Existential) {
            Existential existential = (Existential) lhs;
            result = NF3.getInstance(existential.getRole(), existential
                    .getConcept().hashCode(), rhs.hashCode());
        } else if (lhs instanceof Datatype) {
            Datatype datatype = (Datatype) lhs;
            result = NF8.getInstance(datatype, rhs.hashCode());
        } else {
            throw new IllegalStateException("GCI is not in Normal Form: "
                    + lhs + ", " + rhs);
        }

        return result;
    }

}
 public interface IConjunctionQueueEntry extends Serializable {
    /**
     * The right hand side of the entry.
     * 
     * @return
     */
    int getB();

    /**
     * The second conjunct of the entry.
     * 
     * @return
     */
    int getBi();
}
 public interface IRoleQueueEntry extends Serializable {

    int getR();

    int getB();

} abstract public class Inclusion implements Serializable {
    /**
     * 
     */
    private static final long serialVersionUID = 1L;

    /**
     * Runs the first phase in the normalisation process (see Pushing the EL
     * Envelope).
     * 
     * @param factory
     * @return
     */
    abstract public Inclusion[] normalise1(IFactory factory);

    /**
     * Runs the second phase in the normalisation process (see Pushing the EL
     * Envelope).
     * 
     * @param factory
     * @return
     */
    abstract public Inclusion[] normalise2(IFactory factory);

    @Override
    abstract public int hashCode();

    @Override
    abstract public boolean equals(Object o);

    @Override
    abstract public String toString();

    abstract public NormalFormGCI getNormalForm();

}
 public final class NF1a extends NormalFormGCI implements IConjunctionQueueEntry {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 2L;
    
    final private int lhsA;
    final private int rhsB;

    private NF1a(final int lhs, final int rhs) {
        rhsB = rhs;

        lhsA = lhs;
    }

    static public NF1a getInstance(final int lhs, final int rhs) {
        return new NF1a(lhs, rhs);
    }

    public IConjunctionQueueEntry getQueueEntry() {
        return this;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(lhsA);
        // sb.append(" \u2291 ");
        sb.append(" [ ");
        sb.append(rhsB);

        return sb.toString();
    }

    public int getB() {
        return rhsB;
    }

    public int getBi() {
        return IFactory.TOP_CONCEPT;
    }

    public int lhsA() {
        return lhsA;
    }

    public int b() {
        return rhsB;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] { lhsA, rhsB };
    }

}
 public final class NF1b extends NormalFormGCI implements IConjunctionQueueEntry {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final private int lhsA1;
    final private int lhsA2;
    final private int rhsB;

    private IConjunctionQueueEntry entryA2;

    private NF1b(final int lhs1, final int lhs2, final int rhs) {
        rhsB = rhs;

        lhsA1 = lhs1;
        lhsA2 = lhs2;

        entryA2 = new IConjunctionQueueEntry() {
            /**
             * 
             */
            private static final long serialVersionUID = 1L;

            public int getB() {
                return rhsB;
            }

            public int getBi() {
                return lhsA1;
            }

            public String toString() {
                return "ConjunctionQueueEntry[" + lhsA1 + " [ " + rhsB + ": "
                        + lhsA2 + "]";
            }
        };
    }

    static public NF1b getInstance(final int lhs1, final int lhs2, final int rhs) {
        return new NF1b(lhs1, lhs2, rhs);
    }

    public IConjunctionQueueEntry getQueueEntry1() {
        return this;
    }

    public IConjunctionQueueEntry getQueueEntry2() {
        return entryA2;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append(lhsA1);
        if (lhsA2 >= 0) {
            sb.append(" & ");
            sb.append(lhsA2);
        }
        // sb.append(" \u2291 ");
        sb.append(" [ ");
        sb.append(rhsB);

        return sb.toString();
    }

    public int lhsA1() {
        return lhsA1;
    }

    public int lhsA2() {
        return lhsA2;
    }

    public int b() {
        return rhsB;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] { lhsA1, lhsA2, rhsB };
    }

    public int getB() {
        return rhsB;
    }

    public int getBi() {
        return lhsA2;
    }

}
 public final class NF2 extends NormalFormGCI implements IRoleQueueEntry {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final public int lhsA;
    final public int rhsB;
    final public int rhsR;

    private NF2(int a, int r, int b) {
        lhsA = a;
        rhsB = b;
        rhsR = r;
    }

    /**
     * A [ r.B
     * 
     * @param ontology
     * @param a
     * @param r
     * @param b
     * @return
     */
    static public NF2 getInstance(final int a, final int r, final int b) {
        return new NF2(a, r, b);
    }

    public String toString() {
        return lhsA + " [ " + rhsR + "." + rhsB;
    }

    // ----------------------
    // RoleQueueEntry methods

    public int getB() {
        return rhsB;
    }

    public int getR() {
        return rhsR;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] { lhsA, rhsB };
    }

}
 public final class NF3 extends NormalFormGCI implements IConjunctionQueueEntry {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final public int lhsR;
    final public int lhsA;
    final public int rhsB;

    /**
     * r.A [ B
     * 
     * @param ontology
     * @param a
     * @param r
     * @param b
     */
    private NF3(int r, int a, int b) {
        lhsR = r;
        lhsA = a;
        rhsB = b;
    }

    public IConjunctionQueueEntry getQueueEntry() {
        return this;
    }

    public String toString() {
        return lhsR + "." + lhsA + " [ " + rhsB;
    }

    public static NF3 getInstance(int r, int A, int B) {
        return new NF3(r, A, B);
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] { lhsA, rhsB };
    }

    public int getB() {
        return rhsB;
    }

    public int getBi() {
        return IFactory.TOP_CONCEPT;
    }

}
 public final class NF4 extends NormalFormGCI {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final private int lhsR;
    final private int rhsS;

    public NF4(int r, int s) {
        lhsR = r;
        rhsS = s;
    }

    public int getR() {
        return lhsR;
    }

    public int getS() {
        return rhsS;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] {};
    }
    
    @Override
    public String toString() {
        return lhsR+" [ "+rhsS;
    }

}
 public final class NF5 extends NormalFormGCI {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private int lhsR;
    private int lhsS;
    private int rhsT;

    public NF5(int r, int s, int t) {
        lhsR = r;
        lhsS = s;
        rhsT = t;
    }

    public int getR() {
        return lhsR;
    }

    public int getS() {
        return lhsS;
    }

    public int getT() {
        return rhsT;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] {};
    }
    
    @Override
    public String toString() {
        return lhsR+" o "+lhsS+" [ "+rhsT;
    }

}
 public final class NF6 extends NormalFormGCI {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final private int lhsR;

    public NF6(int r) {
        lhsR = r;
    }

    public int getR() {
        return lhsR;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] {};
    }

}
 public final class NF7 extends NormalFormGCI implements IFeatureQueueEntry {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final public int lhsA;
    final public Datatype rhsD;

    /**
	 * 
	 */
    public NF7(int lhsA, Datatype rhsD) {
        this.lhsA = lhsA;
        this.rhsD = rhsD;
    }

    public Datatype getD() {
        return rhsD;
    }

    static public NF7 getInstance(final int a, Datatype d) {
        return new NF7(a, d);
    }

    public String toString() {
        return lhsA + " [ " + rhsD.getFeature() + ".(" + rhsD.getLiteral() + ")";
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] { lhsA };
    }

}
 public final class NF8 extends NormalFormGCI {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final public Datatype lhsD;
    final public int rhsB;

    /**
	 * 
	 */
    public NF8(Datatype lhsD, int rhsB) {
        this.lhsD = lhsD;
        this.rhsB = rhsB;
    }

    public static NF8 getInstance(Datatype d, int b) {
        return new NF8(d, b);
    }

    public String toString() {
        return lhsD.getFeature() + ".(" + lhsD.getLiteral() + ")" + " [ " + rhsB;
    }

    @Override
    public int[] getConceptsInAxiom() {
        return new int[] { rhsB };
    }

}
 public abstract class NormalFormGCI implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = 1L;

    /**
     * Returns an array with all the concept ids in the axiom.
     * 
     * @return int[]
     */
    public abstract int[] getConceptsInAxiom();
}
 public class RI extends Inclusion {

    /**
     * 
     */
    private static final long serialVersionUID = 1L;

    private static final int PRIME = 31;

    final private int[] lhs;
    final private int rhs;
    final private int hashCode;

    @SuppressFBWarnings("EI_EXPOSE_REP")
    public RI(final int[] lhs, final int rhs) {
        assert null != lhs;
        assert -1 < rhs;
        this.lhs = lhs;
        this.rhs = rhs;
        hashCode = PRIME * (PRIME + Arrays.hashCode(this.lhs)) + this.rhs;
    }

    public RI(int lhs, int rhs) {
        this(new int[] { lhs }, rhs);
    }

    @SuppressFBWarnings("EI_EXPOSE_REP")
    public int[] getLhs() {
        return lhs;
    }

    public int getRhs() {
        return rhs;
    }

    @Override
    public Inclusion[] normalise1(final IFactory factory) {
        Inclusion[] result = { null, null };

        if (rule1(factory, result)) {

        } else {
            result = null;
        }

        return result;
    }

    @Override
    public Inclusion[] normalise2(final IFactory factory) {
        return null;
    }

    /**
     * r<sub>1</sub> &#8728; &#133; &#8728; r<sub>k</sub> &#8849; s &rarr;
     * {r<sub>1</sub> &#8728; &#133; &#8728; r<sub>k-1</sub> &#8849; u, u
     * &#8728; r<sub>k</sub> &#8849; s}
     * 
     * @param gcis
     * @return
     */
    boolean rule1(final IFactory factory, final Inclusion[] gcis) {
        boolean result = false;

        // TODO: make this "binarisation" more efficient by doing it for all
        // elements rather than relying on multiple calls to this rule and 
        // stripping off one Role for each call.
        if (lhs.length > 2) {
            result = true;

            final int k = lhs.length - 1;
            int[] newLhs1 = new int[k];
            System.arraycopy(lhs, 0, newLhs1, 0, newLhs1.length);
            int u = factory.getRole(newLhs1);

            int[] newLhs2 = { u, lhs[k] };

            gcis[0] = new RI(newLhs1, u);
            gcis[1] = new RI(newLhs2, rhs);
        }

        return result;
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final RI other = (RI) obj;
        if (!Arrays.equals(lhs, other.lhs))
            return false;
        if (rhs != other.rhs)
            return false;
        return true;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        if (lhs.length > 0) {
            sb.append(lhs[0]);
        }
        for (int i = 1; i < lhs.length; i++) {
            sb.append(" ");
            sb.append(lhs[i]);
        }
        sb.append(" [ ");
        sb.append(rhs);

        return sb.toString();
    }

    @Override
    public NormalFormGCI getNormalForm() {
        switch (lhs.length) {
        case 1:
            return new NF4(lhs[0], rhs);
        case 2:
            return new NF5(lhs[0], lhs[1], rhs);
        case 0:
            return new NF6(rhs);
        default:
            throw new IllegalStateException("RI is not in Normal Form");
        }
    }

}
 public final class CR implements Serializable {
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private IConceptSet[] data;

    public CR(final int roles) {
        this.data = new IConceptSet[roles];
    }

    public boolean containsRole(int role) {
        return data[role] != null;
    }

    /**
     * 
     * @param r
     * @return
     */
    protected IConceptSet getConcept(int r) {
        if (r >= data.length) {
            resizeRoles(r + 1);
        }
        if (null == data[r]) {
            data[r] = new SparseConceptSet();
        }
        return data[r];
    }

    /**
     * Returns the set of concepts associated to the concept in a
     * {@link Context} by role r.
     * 
     * @param r
     *            The role
     * @return The set of concepts associated to the concept in the context.
     */
    public IConceptSet lookupConcept(int r) {
        if (r >= data.length) {
            return IConceptSet.EMPTY_SET;
        }

        if (null == data[r]) {
            return IConceptSet.EMPTY_SET;
        } else {
            return new ReadonlyConceptSet(data[r]);
        }
    }

    public void clear() {
        Arrays.fill(data, null);
    }

    private void resizeRoles(int maxRole) {
        final IConceptSet[] oldData = data;

        data = new IConceptSet[maxRole];
        System.arraycopy(oldData, 0, data, 0, oldData.length);
    }

    public String toString() {
        final StringBuilder sb = new StringBuilder();

        for (int index = 0; index < data.length; index++) {
            IConceptSet cs = data[index];
            if (null != cs) {
                sb.append(index + "." + cs.toString());
            }
        }

        return sb.toString();
    }

    /**
     * Record C [ r.B, where C is implicit (the concept in a context).
     * 
     * @param r
     * @param B
     */
    synchronized void store(int r, int B) {
        getConcept(r).add(B);
    }
    
    /**
     * Returns the roles stored in this data structure.
     * @return
     */
    public int[] getRoles() {
        List<Integer> roles = new ArrayList<Integer>();
        for(int i = 0; i < data.length; i++) {
            if(data[i] != null) {
                roles.add(i);
            }
        }
        
        int[] res = new int[roles.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = roles.get(i);
        }
        return res;
    }

}
 public class Context implements Serializable {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;

    /**
     * The internal concept id.
     */
    private final int concept;

    /**
     * Flag to indicate if this context is active or not.
     */
    private final AtomicBoolean active = new AtomicBoolean(false);

    /**
     * Queue (List) of ConjunctionQueueEntries indicating work to be done for this concept.
     */
    private final Queue<IConjunctionQueueEntry> conceptQueue = new ConcurrentLinkedQueue<IConjunctionQueueEntry>();

    /**
     * Queue (List) of RoleQueueEntries indicating work to be done for this concept.
     */
    private final IQueue<IRoleQueueEntry> roleQueue = new QueueImpl<IRoleQueueEntry>(IRoleQueueEntry.class);

    /**
     * Queue (List) of FeatureQueueEntries indicating work to be done for this concept. Queue entries of the form
     * A [ f.(o, v).
     */
    private final IQueue<IFeatureQueueEntry> featureQueue = new QueueImpl<IFeatureQueueEntry>(IFeatureQueueEntry.class);

    /**
     * Queue used to process entries from other contexts that trigger calls to processNewEdge.
     */
    private final Queue<IRoleQueueEntry> externalQueue = new ConcurrentLinkedQueue<IRoleQueueEntry>();

    /**
     * Keeps track of the parents of this concept.
     */
    private final IConceptSet s;

    /**
     * Keeps track of the concepts that are linked this concept through some role.
     */
    private final CR pred;

    /**
     * Keeps track of the concepts that this concept is liked to through some role.
     */
    private final CR succ;

    /**
     * Flag to indicate if changes to the subsumptions of this context should be tracked.
     */
    private AtomicBoolean track = new AtomicBoolean(false);

    /**
     * Flag used to indicate if this context has generated new subsumptions while being tracked.
     */
    private boolean changed = false;

    /**
     * Reference to the parent context queue. Used to add this context back to the queue when reactivated.
     */
    private Queue<Context> parentTodo;

    /**
     * Reference to the parent context index. Used to add queue entries to other contexts.
     */
    private IConceptMap<Context> contextIndex;

    /**
     * Reference to the global role closure cache.
     */
    private Map<Integer, RoleSet> roleClosureCache;

    /**
     * Reference to the global factory.
     */
    private IFactory factory;

    /**
     * The set of NF1 terms in the ontology.
     *
     * These terms are of the form A n Ai [ B and are indexed by A.
     */
    private IConceptMap<MonotonicCollection<IConjunctionQueueEntry>> ontologyNF1;

    /**
     * The set of NF2 terms in the ontology.
     *
     * These terms are of the form A [ r.B and are indexed by A.
     */
    private IConceptMap<MonotonicCollection<NF2>> ontologyNF2;

    /**
     * The set of NF3 terms in the ontology.
     *
     * These terms are of the form r.A [ b and indexed by A.
     */
    private IConceptMap<ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>>> ontologyNF3;

    /**
     * The set of NF4 terms in the ontology
     */
    private IMonotonicCollection<NF4> ontologyNF4;

    /**
     * The set of NF5 terms in the ontology
     */
    private IMonotonicCollection<NF5> ontologyNF5;

    /**
     * The set of reflexive roles in the ontology
     */
    private IConceptSet reflexiveRoles = new SparseConceptSet();

    /**
     * The set of NF7 terms in the ontology.
     *
     * These terms are of the form A [ f.(o, v) and are indexed by A.
     */
    private IConceptMap<MonotonicCollection<NF7>> ontologyNF7;

    /**
     * The set of NF8 terms in the ontology.
     *
     * These terms are of the form f.(o, v) [ A. These are indexed by f.
     */
    private FeatureMap<MonotonicCollection<NF8>> ontologyNF8;

    /**
     * The set of functional data properties
     */
    private IConceptSet functionalFeatures;

    /**
     * The set of datatypes asserted for a given (functional) feature
     */
    private FeatureMap<Set<Datatype>> functionalFeatureValues = new FeatureMap<>(2);

    /**
     * The map of global affected contexts used in incremental classification.
     */
    private Set<Context> affectedContexts;

    /**
     * Initialises the shared variables.
     *
     * @param ont
     */
    private void init(NormalisedOntology ont) {
        parentTodo = ont.getTodo();
        contextIndex = ont.getContextIndex();
        ontologyNF1 = ont.getOntologyNF1();
        ontologyNF2 = ont.getOntologyNF2();
        ontologyNF3 = ont.getOntologyNF3();
        ontologyNF4 = ont.getOntologyNF4();
        ontologyNF5 = ont.getOntologyNF5();
        reflexiveRoles = ont.getReflexiveRoles();
        ontologyNF7 = ont.getOntologyNF7();
        ontologyNF8 = ont.getOntologyNF8();
        functionalFeatures = ont.getFunctionalFeatures();
        roleClosureCache = ont.getRoleClosureCache();
        factory = ont.getFactory();
        affectedContexts = ont.getAffectedContexts();
    }

    /**
     * Constructor.
     *
     * @param concept
     */
    public Context(int concept, NormalisedOntology ont) {
        init(ont);
        this.concept = concept;
        s = new SparseConceptSet();
        s.add(concept);
        s.add(IFactory.TOP_CONCEPT);

        pred = new CR(factory.getTotalRoles());
        succ = new CR(factory.getTotalRoles());

        // Prime queues for this context
        primeQueue();
    }

    public int getConcept() {
        return concept;
    }

    private void addToConceptQueue(
            MonotonicCollection<IConjunctionQueueEntry> entries) {
        Iterator<IConjunctionQueueEntry> it = entries.iterator();
        while (it.hasNext()) {
            conceptQueue.add(it.next());
        }
    }

    private void primeQueue() {
        final MonotonicCollection<IConjunctionQueueEntry> nf1e = ontologyNF1.get(concept);
        if (nf1e != null)
            addToConceptQueue(nf1e);

        final MonotonicCollection<NF2> nf2e = ontologyNF2.get(concept);
        if (nf2e != null)
            roleQueue.addAll(nf2e);

        final MonotonicCollection<NF7> nf7e = ontologyNF7.get(concept);
        if (nf7e != null)
            featureQueue.addAll(nf7e);
    }

    /**
     * Adds queue entries for this concept based on the new axioms added in an incremental classification.
     *
     * @param conceptEntries
     * @param roleEntries
     * @param featureEntries
     */
    public void primeQueuesIncremental(
            MonotonicCollection<IConjunctionQueueEntry> conceptEntries,
            MonotonicCollection<IRoleQueueEntry> roleEntries,
            MonotonicCollection<IFeatureQueueEntry> featureEntries) {
        if (conceptEntries != null)
            addToConceptQueue(conceptEntries);
        if (roleEntries != null)
            roleQueue.addAll(roleEntries);
        if (featureEntries != null)
            featureQueue.addAll(featureEntries);
    }

    /**
     * Returns this concept's subsumptions.
     *
     * @return
     */
    public IConceptSet getS() {
        return s;
    }

    /**
     * Returns the data structure used to hold the concepts and roles that point to this concept.
     *
     * @return
     */
    public CR getPred() {
        return pred;
    }

    /**
     * Returns the data structure used to hold the concepts and roles that this concept points at.
     *
     * @return
     */
    public CR getSucc() {
        return succ;
    }

    /**
     * Activates the context. Returns true if the context was inactive and was activated by this method call or false
     * otherwise.
     *
     * @return boolean
     */
    public boolean activate() {
        return active.compareAndSet(false, true);
    }

    /**
     * Deactivates the context. Returns true if the context was active and was deactivated by this method call or false
     * otherwise.
     */
    public void deactivate() {
        active.set(false);
        if (!(conceptQueue.isEmpty() && roleQueue.isEmpty() && featureQueue.isEmpty())) {
            if (activate()) {
                parentTodo.add(this);
            }
        }
    }

    /**
     * Adds an entry to this context's concept queue.
     *
     * @param entry
     */
    public void addConceptQueueEntry(IConjunctionQueueEntry entry) {
        conceptQueue.add(entry);
    }

    public void addConceptQueueEntries(
            Collection<IConjunctionQueueEntry> entries) {
        conceptQueue.addAll(entries);
    }

    /**
     * Adds an entry to this context's role queue.
     *
     * @param entry
     */
    public void addRoleQueueEntry(IRoleQueueEntry entry) {
        roleQueue.add(entry);
    }

    /**
     * Adds and entry to this context's feature queue.
     *
     * @param entry
     */
    public void addFeatureQueueEntry(IFeatureQueueEntry entry) {
        featureQueue.add(entry);
    }

    /**
     * Triggers the processing of an edge based on events that happened in another {@link Context}.
     *
     * @param role
     * @param src
     */
    public void processExternalEdge(final int role, final int src) {
        externalQueue.add(new IRoleQueueEntry() {
            /**
             * Serialisation version.
             */
            private static final long serialVersionUID = 1L;

            @Override
            public int getR() {
                return role;
            }

            @Override
            public int getB() {
                return src;
            }
        });
    }

    /**
     * Starts the classification process.
     */
    public void processOntology() {
        // This code is duplicated for performance reasons. When not running in
        // incremental mode the evaluation of the track flag is only done once
        // for each time the context is activated.
        if (track.get()) {
            processOntologyTracking();
        } else {
            processOntologyInternal();
        }

        deactivate();
    }

    private void processOntologyInternal() {
        boolean done;

        do {
            done = true;

            // Process concept queue
            if (!conceptQueue.isEmpty()) {
                do {
                    done = false;
                    final IConjunctionQueueEntry entry = conceptQueue.remove();
                    final int b = entry.getB();

                    if (!s.contains(b)) {
                        final int bi = entry.getBi();
                        if (s.contains(bi)) {
                            s.add(b);
                            processNewSubsumption(b);
                        }
                    }
                } while (!conceptQueue.isEmpty());
            }

            // Process feature queue
            if (!featureQueue.isEmpty()) {
                do {
                    done = false;
                    final IFeatureQueueEntry entry = featureQueue.remove();

                    Datatype d = entry.getD();

                    // Handle functional features
                    checkFunctionalFeatures(d);

                    // Get right hand sides from NF8 expressions that
                    // match d on their left hand side
                    MonotonicCollection<NF8> entries = ontologyNF8.get(d.getFeature());

                    if (entries == null)
                        continue;

                    // Evaluate to determine the ones that match
                    MonotonicCollection<IConjunctionQueueEntry> res =
                            new MonotonicCollection<IConjunctionQueueEntry>(2);
                    for (final NF8 e : entries) {
                        Datatype d2 = e.lhsD;

                        // If they match add a conjunction queue entry
                        // to queueA
                        if (datatypeMatches(d, d2)) {
                            res.add(new IConjunctionQueueEntry() {
                                /**
                                 * Serialisation version.
                                 */
                                private static final long serialVersionUID = 1L;

                                @Override
                                public int getBi() {
                                    return CoreFactory.TOP_CONCEPT;
                                }

                                @Override
                                public int getB() {
                                    return e.rhsB;
                                }
                            });
                        }
                    }

                    addToConceptQueue(res);
                } while (!featureQueue.isEmpty());
            }

            // Process role queue
            if (!roleQueue.isEmpty()) {
                done = false;
                final IRoleQueueEntry entry = roleQueue.remove();

                if (!succ.lookupConcept(entry.getR()).contains(entry.getB())) {
                    processNewEdge(entry.getR(), entry.getB());
                }
            }

            if (!externalQueue.isEmpty()) {
                done = false;
                final IRoleQueueEntry entry = externalQueue.remove();
                processNewEdge(entry.getR(), entry.getB());
            }

        } while (!done);
    }

    private void checkFunctionalFeatures(Datatype d) {
        int f = d.getFeature();
        if (functionalFeatures.contains(f)) {
            Set<Datatype> datatypes = functionalFeatureValues.get(f);
            if (null == datatypes) {
                datatypes = new HashSet<>();
                functionalFeatureValues.put(f, datatypes);
            } else {
                for (Datatype dt: datatypes) {
                    // Check if d and dt are incompatible
                    if (!datatypeMatches(d, dt) && !datatypeMatches(dt, d)) {
                        System.err.println("Functional data property " + f + " has multiple distinct value constraints: " + dt + " and " + d);       // FIXME delete
                        final MonotonicCollection<IConjunctionQueueEntry> entries =
                                new MonotonicCollection<IConjunctionQueueEntry>(1);
                        entries.add(new IConjunctionQueueEntry() {
                            /**
                             * Serialisation version.
                             */
                            private static final long serialVersionUID = 1L;

                            @Override
                            public int getBi() {
                                return CoreFactory.TOP_CONCEPT;
                            }

                            @Override
                            public int getB() {
                                return CoreFactory.BOTTOM_CONCEPT;
                            }
                        });
                        addToConceptQueue(entries);
                    }
                }
            }
            datatypes.add(d);
        }
    }

    private void processNewSubsumption(final int b) {
        // Get the set of parent concepts of (b n x) in the ontology
        final MonotonicCollection<IConjunctionQueueEntry> bConceptEntries = ontologyNF1.get(b);
        if (null != bConceptEntries && bConceptEntries.size() > 0) {
            // Add these to the queue of a
            addToConceptQueue(bConceptEntries);
        }
        final MonotonicCollection<NF2> bRoleEntries = ontologyNF2.get(b);
        if (null != bRoleEntries) {
            roleQueue.addAll(bRoleEntries);
        }

        // inlined ontHat(conceptQueues.get(pairA(p)), r, b) in following
        // to move test and fetch outside innermost loop
        //
        final ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>> map = ontologyNF3.get(b);
        if (null != map) {
            for (Entry<Integer, Collection<IConjunctionQueueEntry>> entrySet : map.entrySet()) {
                int r = entrySet.getKey();
                final Collection<IConjunctionQueueEntry> entries = entrySet.getValue();

                if (null != entries) {
                    final IConceptSet aPrimes = pred.lookupConcept(r);
                    for (final IntIterator itr = aPrimes.iterator(); itr.hasNext();) {
                        final int aa = itr.next();
                        // Add to queue aa
                        if (concept == aa) {
                            conceptQueue.addAll(entries);
                        } else {
                            // Add to external context concept queue and
                            // activate
                            Context oc = contextIndex.get(aa);
                            oc.addConceptQueueEntries(entries);
                            if (oc.activate())
                                parentTodo.add(oc);
                        }
                    }
                }
            }
        }

        final MonotonicCollection<NF7> nf7Entries = ontologyNF7.get(b);
        if (null != nf7Entries && nf7Entries.size() > 0) {
            featureQueue.addAll(nf7Entries);
        }
    }

    /**
     * Evaluates the equivalence of two {@link Datatype}s. This method assumes that the literals both have the same
     * matching literal types.
     *
     * @param d1
     *            Data type from an NF7 entry.
     * @param d2
     *            Data type from an NF8 entry.
     * @return boolean
     */
    private boolean datatypeMatches(Datatype d1, Datatype d2) {
        assert (d1.getFeature() == d2.getFeature());

        AbstractLiteral lhsLit = d1.getLiteral();
        AbstractLiteral rhsLit = d2.getLiteral();

        Operator lhsOp = d1.getOperator();
        Operator rhsOp = d2.getOperator();

        if (rhsOp == Operator.EQUALS) {
            // If the rhs operator is =, then the expression will only match
            // if the lhs operator is also = and the literal values are the
            // same.
            if(lhsOp != Operator.EQUALS) {
                return false;
            } else {
                return d1.getLiteral().equals(d2.getLiteral());
            }
        } else if (rhsOp == Operator.GREATER_THAN) {
            if (lhsOp == Operator.LESS_THAN
                    || lhsOp == Operator.LESS_THAN_EQUALS) {
                return false;
            } else if (lhsOp == Operator.EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) > 0) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.GREATER_THAN) {
                if (compareLiterals(lhsLit, rhsLit) >= 0) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.GREATER_THAN_EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) > 0) {
                    return true;
                } else {
                    return false;
                }
            }
        } else if (rhsOp == Operator.GREATER_THAN_EQUALS) {
            if (lhsOp == Operator.LESS_THAN
                    || lhsOp == Operator.LESS_THAN_EQUALS) {
                return false;
            } else if (lhsOp == Operator.EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) >= 0) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.GREATER_THAN) {
                if (compareLiterals(lhsLit, rhsLit) >= -1) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.GREATER_THAN_EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) >= 0) {
                    return true;
                } else {
                    return false;
                }
            }
        } else if (rhsOp == Operator.LESS_THAN) {
            if (lhsOp == Operator.GREATER_THAN
                    || lhsOp == Operator.GREATER_THAN_EQUALS) {
                return false;
            } else if (lhsOp == Operator.EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) < 0) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.LESS_THAN) {
                if (compareLiterals(lhsLit, rhsLit) <= 0) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.LESS_THAN_EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) < 0) {
                    return true;
                } else {
                    return false;
                }
            }
        } else if (rhsOp == Operator.LESS_THAN_EQUALS) {
            if (lhsOp == Operator.GREATER_THAN
                    || lhsOp == Operator.GREATER_THAN_EQUALS) {
                return false;
            } else if (lhsOp == Operator.EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) <= 0) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.LESS_THAN) {
                if (compareLiterals(lhsLit, rhsLit) <= 1) {
                    return true;
                } else {
                    return false;
                }
            } else if (lhsOp == Operator.LESS_THAN_EQUALS) {
                if (compareLiterals(lhsLit, rhsLit) <= 0) {
                    return true;
                } else {
                    return false;
                }
            }
        }

        return d1.getLiteral().equals(d2.getLiteral());
    }

    /**
     * Return 0 if both literals are equals. Returns an int > 0 if l1 is greater than l2 and an int < 0 if l1 is less
     * than l2.
     *
     * @param l1
     * @param l2
     * @return
     */
    private int compareLiterals(AbstractLiteral l1, AbstractLiteral l2) {
        return l1.compareTo(l2);
    }

    /**
     * Process new subsumption: a [ role.b
     *
     * @param a
     * @param role
     * @param b
     */
    private void processNewEdge(int role, int b) {
        final RoleSet roleClosure = getRoleClosure(role);
        processRole(role, b);
        for (int s = roleClosure.first(); s >= 0; s = roleClosure.next(s + 1)) {
            if (s == role)
                continue;
            processRole(s, b);
        }
    }

    private void processRole(int s, int b) {
        // R(s) := R(s) u {(A,B)}
        succ.store(s, b);

        // Add the predecessor to the the corresponding context
        // Is this necessary?
        Context bContext = contextIndex.get(b);

        bContext.getPred().store(s, concept);

        // queue(A) := queue(A) u U{B'|B' in S(B)}.O^(s.B')
        final IConceptSet sb = contextIndex.get(b).getS();

        // Computes the minimal set of QueueEntries from s.a [ bb is in O
        for (IntIterator itr = sb.iterator(); itr.hasNext();) {
            final int bb = itr.next();
            final ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>> map = ontologyNF3.get(bb);

            if (null != map) {
                final Collection<IConjunctionQueueEntry> entries = map.get(s);
                if (null != entries) {
                    conceptQueue.addAll(entries);
                }
            }
        }

        // Handle reflexive roles
        if (reflexiveRoles.contains(s)) {
            // check for (a,a) in R(s)
            if (!pred.lookupConcept(s).contains(concept)) {
                processNewEdge(s, concept);
            }

            // check for (b,b) in R(s)
            Context tc = contextIndex.get(b);
            if (!tc.getPred().lookupConcept(s).contains(b)) {
                tc.processExternalEdge(s, b);
                if (tc.activate()) {
                    parentTodo.add(tc);
                }
            }
        }

        final List<int[]> work = new ArrayList<int[]>();
        for (final NF5 nf5 : ontologyNF5) {
            if (s == nf5.getS()) {
                final int t = nf5.getR();
                final int u = nf5.getT();
                final IConceptSet aTPrimes = pred.lookupConcept(t);

                // Again in this case there is a dependency with the
                // predecessors of an external context.
                final IConceptSet bUPrimes = contextIndex.get(b).getPred().lookupConcept(u);

                for (final IntIterator itr = aTPrimes.iterator();
                        itr.hasNext();) {
                    final int aa = itr.next();

                    if (!bUPrimes.contains(aa)) {
                        work.add(new int[] { aa, u });
                    }

                }
            }
        }

        for (final int[] pair : work) {
            if (pair[0] == concept) {
                processNewEdge(pair[1], b);
            } else {
                Context tc = contextIndex.get(pair[0]);
                tc.processExternalEdge(pair[1], b);
                if (tc.activate()) {
                    parentTodo.add(tc);
                }
            }
        }

        work.clear();
        for (final NF5 nf5 : ontologyNF5) {
            if (s == nf5.getR()) {
                final int t = nf5.getS();
                final int u = nf5.getT();
                // In this case there is a dependency with the
                // successors of an external context.
                final IConceptSet bTPrimes = contextIndex.get(b).getSucc().lookupConcept(t);
                final IConceptSet aUPrimes = succ.lookupConcept(u);

                for (final IntIterator itr = bTPrimes.iterator();
                        itr.hasNext();) {
                    final int bb = itr.next();

                    if (!aUPrimes.contains(bb)) {
                        work.add(new int[] { u, bb });
                    }

                }
            }
        }
        for (final int[] pair : work) {
            processNewEdge(pair[0], pair[1]);
        }
    }

    private RoleSet getRoleClosure(final int r) {
        RoleSet result = roleClosureCache.get(r);
        if (null == result) {
            result = new RoleSet();
            result.add(r);
            for (final NF4 nf4 : ontologyNF4) {
                if (r == nf4.getR()) {
                    result.addAll(getRoleClosure(nf4.getS()));
                }
            }
            // We do this after the above recursive call to trigger a stack
            // overflow in case there's a role-inclusion cycle
            roleClosureCache.put(r, result);
        }
        return result;
    }

    /**
     * Starts tracking changes in the context's subsumptions. It is used in incremental classification to detect which
     * contexts have been affected by the new axioms.
     */
    public void startTracking() {
        if (track.compareAndSet(false, true)) {
            changed = false;
        }
    }

    /**
     * Stops tracking changes to the context's subsumptions.
     */
    public void endTracking() {
        track.set(false);
    }

    /**
     * Indicates if the context has generated new subsumptions while being
     * tracked.
     */
    public boolean hasNewSubsumptions() {
        return changed;
    }

    ////////////////////////////////////////////////////////////////////////////
    // Tracking versions of the methods
    ////////////////////////////////////////////////////////////////////////////

    private void processOntologyTracking() {
        boolean done;

        do {
            done = true;

            // Process concept queue
            if (!conceptQueue.isEmpty()) {
                do {
                    done = false;
                    final IConjunctionQueueEntry entry = conceptQueue.remove();
                    final int b = entry.getB();

                    if (!s.contains(b)) {
                        final int bi = entry.getBi();
                        if (s.contains(bi)) {
                            s.add(b);
                            changed = true;
                            processNewSubsumptionTracking(b);
                        }
                    }
                } while (!conceptQueue.isEmpty());
            }

            // Process feature queue
            if (!featureQueue.isEmpty()) {
                do {
                    done = false;
                    final IFeatureQueueEntry entry = featureQueue.remove();

                    Datatype d = entry.getD();

                    // Handle functional features
                    checkFunctionalFeatures(d);

                    // Get right hand sides from NF8 expressions that
                    // match d on their left hand side
                    MonotonicCollection<NF8> entries =
                            ontologyNF8.get(d.getFeature());

                    if (entries == null)
                        continue;

                    // Evaluate to determine the ones that match
                    MonotonicCollection<IConjunctionQueueEntry> res =
                            new MonotonicCollection<IConjunctionQueueEntry>(2);
                    for (final NF8 e : entries) {
                        Datatype d2 = e.lhsD;

                        // If they match add a conjunction queue entry
                        // to queueA
                        if (datatypeMatches(d, d2)) {
                            res.add(new IConjunctionQueueEntry() {
                                /**
                                 * Serialisation version.
                                 */
                                private static final long serialVersionUID = 1L;

                                @Override
                                public int getBi() {
                                    return CoreFactory.TOP_CONCEPT;
                                }

                                @Override
                                public int getB() {
                                    return e.rhsB;
                                }
                            });
                        }
                    }

                    addToConceptQueue(res);
                } while (!featureQueue.isEmpty());
            }

            // Process role queue
            if (!roleQueue.isEmpty()) {
                done = false;
                final IRoleQueueEntry entry = roleQueue.remove();

                if (!succ.lookupConcept(entry.getR()).contains(entry.getB())) {
                    processNewEdgeTracking(entry.getR(), entry.getB());
                }
            }

            if (!externalQueue.isEmpty()) {
                done = false;
                final IRoleQueueEntry entry = externalQueue.remove();
                processNewEdgeTracking(entry.getR(), entry.getB());
            }

        } while (!done);
    }

    private void processNewSubsumptionTracking(final int b) {
        // Get the set of parent concepts of (b n x) in the ontology
        final MonotonicCollection<IConjunctionQueueEntry> bConceptEntries = ontologyNF1.get(b);
        if (null != bConceptEntries && bConceptEntries.size() > 0) {
            // Add these to the queue of a
            addToConceptQueue(bConceptEntries);
        }
        final MonotonicCollection<NF2> bRoleEntries = ontologyNF2.get(b);
        if (null != bRoleEntries) {
            roleQueue.addAll(bRoleEntries);
        }

        // inlined ontHat(conceptQueues.get(pairA(p)), r, b) in following
        // to move test and fetch outside innermost loop
        //
        final ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>> map = ontologyNF3
                .get(b);
        if (null != map) {
            for (Entry<Integer, Collection<IConjunctionQueueEntry>> entrySet: map.entrySet()) {
                int r = entrySet.getKey();
                final Collection<IConjunctionQueueEntry> entries = entrySet.getValue();

                if (null != entries) {
                    final IConceptSet aPrimes = pred.lookupConcept(r);
                    for (final IntIterator itr = aPrimes.iterator(); itr.hasNext();) {
                        final int aa = itr.next();
                        // Add to queue aa
                        if (concept == aa) {
                            conceptQueue.addAll(entries);
                        } else {
                            // Add to external context concept queue and
                            // activate
                            Context oc = contextIndex.get(aa);
                            oc.addConceptQueueEntries(entries);
                            affectedContexts.add(oc);
                            oc.startTracking();
                            if (oc.activate())
                                parentTodo.add(oc);
                        }
                    }
                }
            }
        }

        final MonotonicCollection<NF7> nf7Entries = ontologyNF7.get(b);
        if (null != nf7Entries && nf7Entries.size() > 0) {
            featureQueue.addAll(nf7Entries);
        }
    }

    private void processNewEdgeTracking(int role, int b) {
        final RoleSet roleClosure = getRoleClosure(role);
        processRoleTracking(role, b);
        for (int s = roleClosure.first(); s >= 0; s = roleClosure.next(s + 1)) {
            if (s == role)
                continue;
            processRoleTracking(s, b);
        }
    }

    private void processRoleTracking(int s, int b) {
        // R(s) := R(s) u {(A,B)}
        succ.store(s, b);

        // Add the predecessor to the the corresponding context
        // Is this necessary?
        Context bContext = contextIndex.get(b);

        bContext.getPred().store(s, concept);

        // queue(A) := queue(A) u U{B'|B' in S(B)}.O^(s.B')
        final IConceptSet sb = contextIndex.get(b).getS();

        // Computes the minimal set of QueueEntries from s.a [ bb is in O
        for (IntIterator itr = sb.iterator(); itr.hasNext();) {
            final int bb = itr.next();
            final ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>> map = ontologyNF3.get(bb);

            if (null != map) {
                final Collection<IConjunctionQueueEntry> entries = map.get(s);
                if (null != entries) {
                    conceptQueue.addAll(entries);
                }
            }
        }

        // Handle reflexive roles
        if (reflexiveRoles.contains(s)) {
            // check for (a,a) in R(s)
            if (!pred.lookupConcept(s).contains(concept)) {
                processNewEdgeTracking(s, concept);
            }

            // check for (b,b) in R(s)
            Context tc = contextIndex.get(b);
            if (!tc.getPred().lookupConcept(s).contains(b)) {
                tc.processExternalEdge(s, b);
                affectedContexts.add(tc);
                tc.startTracking();
                if (tc.activate()) {
                    parentTodo.add(tc);
                }
            }
        }

        final List<int[]> work = new ArrayList<int[]>();
        for (final NF5 nf5 : ontologyNF5) {
            if (s == nf5.getS()) {
                final int t = nf5.getR();
                final int u = nf5.getT();
                final IConceptSet aTPrimes = pred.lookupConcept(t);

                // Again in this case there is a dependency with the
                // predecessors of an external context.
                final IConceptSet bUPrimes =
                        contextIndex.get(b).getPred().lookupConcept(u);

                for (final IntIterator itr = aTPrimes.iterator();
                        itr.hasNext();) {
                    final int aa = itr.next();

                    if (!bUPrimes.contains(aa)) {
                        work.add(new int[] { aa, u });
                    }

                }
            }
        }

        for (final int[] pair : work) {
            if (pair[0] == concept) {
                processNewEdgeTracking(pair[1], b);
            } else {
                Context tc = contextIndex.get(pair[0]);
                tc.processExternalEdge(pair[1], b);
                affectedContexts.add(tc);
                tc.startTracking();
                if (tc.activate()) {
                    parentTodo.add(tc);
                }
            }
        }

        work.clear();
        for (final NF5 nf5 : ontologyNF5) {
            if (s == nf5.getR()) {
                final int t = nf5.getS();
                final int u = nf5.getT();
                // In this case there is a dependency with the
                // successors of an external context.
                final IConceptSet bTPrimes = contextIndex.get(b).getSucc()
                        .lookupConcept(t);
                final IConceptSet aUPrimes = succ.lookupConcept(u);

                for (final IntIterator itr = bTPrimes.iterator();
                        itr.hasNext();) {
                    final int bb = itr.next();

                    if (!aUPrimes.contains(bb)) {
                        work.add(new int[] { u, bb });
                    }

                }
            }
        }
        for (final int[] pair : work) {
            processNewEdgeTracking(pair[0], pair[1]);
        }
    }

}
 public class TaxonomyWorker1 implements Runnable {
    
    private final IConceptMap<Context> contextIndex;
    
    private final ConcurrentMap<Integer, IConceptSet> equiv;
    
    private final ConcurrentMap<Integer, IConceptSet> direc;
    
    private final IFactory factory;
    
    private final Queue<Integer> todo;
    
    /**
     * 
     */
    public TaxonomyWorker1(IConceptMap<Context> contextIndex, 
            ConcurrentMap<Integer, IConceptSet> equiv, 
            ConcurrentMap<Integer, IConceptSet> direc, IFactory factory,
            Queue<Integer> todo) {
        this.contextIndex = contextIndex;
        this.equiv = equiv;
        this.direc = direc;
        this.factory = factory;
        this.todo = todo;
    }
    
    public void run() {
        while(true) {
            Integer aInt = todo.poll();
            if(aInt == null) break;
            
            // Get the context
            int a = aInt.intValue();
            Context ctx = contextIndex.get(a);
            
            // Ignore if virtual
            if(factory.isVirtualConcept(a)) continue;
            
            // For every non-virtual parent get its parents
            for (IntIterator it = ctx.getS().iterator(); it.hasNext(); ) {
                int c = it.next();
                if(factory.isVirtualConcept(c)) continue;
                
                if (c == IFactory.BOTTOM_CONCEPT) {
                    addToSet(equiv, a, c);
                    addToSet(equiv, c, a);
                    continue;
                }
                
                // TODO: why is the context for BOTTOM including TOP?
                if(a == IFactory.BOTTOM_CONCEPT && c == IFactory.TOP_CONCEPT) {
                    continue;
                }
                
                IConceptSet cs = contextIndex.get(c).getS();
                if(cs != null && cs.contains(a)) {
                    addToSet(equiv, a, c);
                } else {
                    boolean isDirect = true;
                    IConceptSet d = direc.get(a);
                    if (d != null) {
                        IConceptSet toRemove = 
                                IConceptSet.FACTORY.createConceptSet();
                        for(IntIterator it2 = d.iterator(); it2.hasNext(); ) {
                            int b = it2.next();
                            IConceptSet bs = contextIndex.get(b).getS();
                            if (bs != null && bs.contains(c)) {
                                isDirect = false;
                                break;
                            }
                            if (cs != null && cs.contains(b)) {
                                toRemove.add(b);
                            }
                        }
                        d.removeAll(toRemove);
                    }
                    if (isDirect) {
                        addToSet(direc, a, c);
                    }
                }
            }
        }
    }
    
    public static void addToSet(ConcurrentMap<Integer, IConceptSet> set, 
            int key, int val) {
        IConceptSet valSet = set.get(key);
        if(valSet == null) {
            IConceptSet temp = new FastConceptHashSet();
            valSet = set.putIfAbsent(key, temp);
            if(valSet == null) {
                temp.add(val);
            } else {
                valSet.add(val);
            }
        } else {
            valSet.add(val);
        }
    }

}
 public class TaxonomyWorker2 implements Runnable {
    
    private final IFactory factory;
    private final Map<String, Node> conceptNodeIndex;
    private final ConcurrentMap<Integer, IConceptSet> direc;
    private final Queue<Node> todo;
    private final Set<Node> nodeSet;
    
    /**
     * 
     */
    public TaxonomyWorker2(IFactory factory, 
            Map<String, Node> conceptNodeIndex, 
            ConcurrentMap<Integer, IConceptSet> direc, Queue<Node> todo, 
            Set<Node> nodeSet) {
        this.factory = factory;
        this.conceptNodeIndex = conceptNodeIndex;
        this.direc = direc;
        this.todo = todo;
        this.nodeSet = nodeSet;
    }

    public void run() {
        while(true) {
            Node node = todo.poll();
            if(node == null) break;
            if(node.getEquivalentConcepts().contains(NamedConcept.BOTTOM)) continue;
            
            for (String c : node.getEquivalentConcepts()) {
                // Get direct super-concepts
                IConceptSet dc = direc.get(factory.getConcept(c));
                if (dc != null) {
                    for(IntIterator it = dc.iterator(); it.hasNext(); ) {
                        int d = it.next();
                        Node parent = conceptNodeIndex.get(
                                factory.lookupConceptId(d));
                        if (parent != null) {
                            node.getParents().add(parent);
                            parent.getChildren().add(node);
                            nodeSet.remove(parent);
                        }
                    }
                }
            }
        }
    }

}
 public class Worker implements Runnable {

    private final Queue<Context> todo;

    /**
     * 
     * @param todo
     */
    public Worker(Queue<Context> todo) {
        this.todo = todo;
    }

    /**
     * @see java.lang.Runnable#run()
     */
    public void run() {
        // Process contexts until there are no more left in the queue
        while (true) {
            Context ctx = todo.poll();
            if (ctx == null)
                break;
            ctx.processOntology();
        }
    }

} public abstract class AbstractConcept implements Comparable<AbstractConcept>, Serializable {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;

    @Override
    abstract public String toString();

    @Override
    abstract public int hashCode();

    @Override
    abstract public boolean equals(Object o);

    /**
     * Called to compare this object with the specified object when the
     * {@link #hashCode}s are equal.
     * 
     * @param other
     *            the Object to be compared.
     * 
     * @return a negative integer, zero, or a positive integer as this object is
     *         less than, equal to, or greater than the specified object.
     * @see {@link #compareTo(AbstractConcept)},
     *      {@link Comparable#compareTo(Object)}
     */
    abstract int compareToWhenHashCodesEqual(AbstractConcept other);

    /**
     * Default {@link Comparable#compareTo(Object)} implementation that calls
     * {@link #compareToWhenHashCodesEqual(AbstractConcept)} if and only if the
     * {@link #hashCode()} values of {@code this} and {@code other} are equal.
     * 
     * @return a negative integer, zero, or a positive integer as this object is
     *         less than, equal to, or greater than the specified object.
     */
    public int compareTo(AbstractConcept other) {
        // Need to sort by concrete subclass first, and then by object hashCode
        final int meta = getClass().hashCode() - other.getClass().hashCode();
        final int quickCompare = hashCode() - other.hashCode();

        int result = 0 == meta ? (0 == quickCompare ? compareToWhenHashCodesEqual(other)
                : quickCompare)
                : meta;

        // If compare result is 0, then the objects must be equal()
        assert 0 != result || this.equals(other);

        return result;
    }

} public abstract class AbstractLiteral implements Serializable, Comparable<AbstractLiteral> {

    private static final long serialVersionUID = 1L;

} public class Conjunction extends AbstractConcept {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final private AbstractConcept[] concepts;
    final private int hashCode;

    public Conjunction(final AbstractConcept[] concepts) {
        final SortedSet<AbstractConcept> sorted = new TreeSet<AbstractConcept>();
        for (AbstractConcept concept : concepts) {
            sorted.add(concept);
        }
        this.concepts = sorted.toArray(new AbstractConcept[sorted.size()]);
        hashCode = sorted.hashCode();
    }

    public Conjunction(final Collection<? extends AbstractConcept> concepts) {
        // store the concepts in hashCode order so that equals() is order
        // independent
        // i.e. Conjunctions are reflexive (should also be transitive, but Agile
        // says STTCPW)

        final SortedSet<AbstractConcept> sorted = new TreeSet<AbstractConcept>(
                concepts);
        this.concepts = sorted.toArray(new AbstractConcept[sorted.size()]);
        hashCode = sorted.hashCode();
    }

    @SuppressFBWarnings("EI_EXPOSE_REP")
    public AbstractConcept[] getConcepts() {
        return concepts;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("(");
        if(concepts != null && concepts.length > 0) {
            sb.append(concepts[0]);
            for (int i = 1; i < concepts.length; i++) {
                sb.append(" + ");
                sb.append(concepts[i]);
            }   
        }
        sb.append(")");
        return sb.toString();
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Conjunction other = (Conjunction) obj;
        return hashCode == other.hashCode
                && Arrays.equals(concepts, other.concepts);
    }

    @Override
    int compareToWhenHashCodesEqual(AbstractConcept other) {
        assert hashCode() == other.hashCode();
        assert other instanceof Conjunction;

        final Conjunction otherConjunction = (Conjunction) other;

        // First check that the conjunctions have the same length
        int result = concepts.length - otherConjunction.concepts.length;

        // Then, compare members in order
        for (int i = 0; 0 == result && i < concepts.length; i++) {
            result = concepts[i].compareTo(otherConjunction.concepts[i]);
        }

        return result;
    }

}
 public class Datatype extends AbstractConcept {
    
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private int feature;
    private Operator operator;
    private AbstractLiteral literal;

    /**
         * 
         */
    public Datatype(int feature, Operator operator, AbstractLiteral literal) {
        this.feature = feature;
        this.operator = operator;
        this.literal = literal;
    }

    public int getFeature() {
        return feature;
    }

    public Operator getOperator() {
        return operator;
    }

    public AbstractLiteral getLiteral() {
        return literal;
    }

    @Override
    public String toString() {
        return feature + ".(" + operator + "," + literal + ")";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + feature;
        result = prime * result + ((literal == null) ? 0 : literal.hashCode());
        result = prime * result
                + ((operator == null) ? 0 : operator.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Datatype other = (Datatype) obj;
        if (feature != other.feature)
            return false;
        if (literal == null) {
            if (other.literal != null)
                return false;
        } else if (!literal.equals(other.literal))
            return false;
        if (operator != other.operator)
            return false;
        return true;
    }

    @Override
    int compareToWhenHashCodesEqual(AbstractConcept other) {
        assert hashCode() == other.hashCode();
        assert other instanceof Datatype;

        final Datatype otherDatatype = (Datatype) other;

        final int featureCompare = feature - otherDatatype.feature;

        if (featureCompare == 0) {
            final int operatorCompare = operator.compareTo(
                    otherDatatype.operator);
            if (operatorCompare == 0) {
                return literal.toString().compareTo(otherDatatype.literal.toString());
            } else {
                return operatorCompare;
            }
        } else {
            return featureCompare;
        }
    }

}
 public class DateLiteral extends AbstractLiteral {

    private final SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
    private final Calendar value;

    public DateLiteral(Calendar value) {
        this.value = value;
    }

    /**
     * @return the value
     */
    public Calendar getValue() {
        return value;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((value == null) ? 0 : value.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        DateLiteral other = (DateLiteral) obj;
        if (value == null) {
            if (other.value != null)
                return false;
        } else if (!value.equals(other.value))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return sdf.format(value.getTime());
    }

    public int compareTo(AbstractLiteral o) {
        DateLiteral dl = (DateLiteral) o;
        Calendar otherValue = dl.value;
        return value.compareTo(otherValue);
    }

}
 public class DecimalLiteral extends AbstractLiteral {

    private final BigDecimal value;

    /**
     * Constructor.
     * 
     * @param type
     */
    public DecimalLiteral(BigDecimal value) {
        this.value = value;
    }

    /**
     * @return the value
     */
    public BigDecimal getValue() {
        return value;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((value == null) ? 0 : value.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        DecimalLiteral other = (DecimalLiteral) obj;
        if (value == null) {
            if (other.value != null)
                return false;
        } else if (!value.equals(other.value))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }

    public int compareTo(AbstractLiteral o) {
        return value.compareTo(((DecimalLiteral) o).value);
    }
    
}
 public class Existential extends AbstractConcept {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private int role;
    private AbstractConcept concept;

    public Existential(int role, AbstractConcept concept) {
        this.role = role;
        this.concept = concept;
    }

    @Override
    public String toString() {
        return role + " . " + concept;
        // return "\u2203 " + role + "." + concept;
    }

    public int getRole() {
        return role;
    }

    public AbstractConcept getConcept() {
        return concept;
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        final int PRIME = 31;
        int result = 1;
        result = PRIME * result + ((concept == null) ? 0 : concept.hashCode());
        result = PRIME * result + role;
        return result;
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Existential other = (Existential) obj;
        if (concept == null) {
            if (other.concept != null)
                return false;
        } else if (!concept.equals(other.concept))
            return false;
        if (role != other.role)
            return false;
        return true;
    }

    @Override
    int compareToWhenHashCodesEqual(AbstractConcept other) {
        assert hashCode() == other.hashCode();
        assert other instanceof Existential;

        final Existential otherExistential = (Existential) other;

        final int roleCompare = role - otherExistential.role;

        return 0 == roleCompare ? (null == concept ? (null == otherExistential.concept ? 0
                : -1)
                : (concept.compareTo(otherExistential.concept)))
                : roleCompare;
    }

    // @Override
    // public String getKey() {
    // return role.getKey() + " . " + concept.getKey();
    // }

}
 public class IntegerLiteral extends AbstractLiteral {

    private final int value;

    /**
     * Constructor.
     * 
     * @param type
     */
    public IntegerLiteral(int value) {
        this.value = value;
    }

    /**
     * @return the value
     */
    public int getValue() {
        return value;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + value;
        return result;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        IntegerLiteral other = (IntegerLiteral) obj;
        if (value != other.value)
            return false;
        return true;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }

    public int compareTo(AbstractLiteral o) {
        int thisVal = this.value;
        int anotherVal = ((IntegerLiteral) o).value;
        return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }

}
 public class StringLiteral extends AbstractLiteral {

    private final String value;

    public StringLiteral(String value) {
        this.value = value;
    }

    /**
     * @return the value
     */
    public String getValue() {
        return value;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((value == null) ? 0 : value.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        StringLiteral other = (StringLiteral) obj;
        if (value == null) {
            if (other.value != null)
                return false;
        } else if (!value.equals(other.value))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return value;
    }

    public int compareTo(AbstractLiteral o) {
        StringLiteral sl = (StringLiteral) o;
        String otherValue = sl.value;
        return value.compareTo(otherValue);
    }

}
 public class AxiomSet implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = 1L;
    
    private final Collection<NF1a> nf1aAxioms = new HashSet<NF1a>();
    private final Collection<NF1b> nf1bAxioms = new HashSet<NF1b>();
    private final Collection<NF2> nf2Axioms = new HashSet<NF2>();
    private final Collection<NF3> nf3Axioms = new HashSet<NF3>();
    private final Collection<NF4> nf4Axioms = new HashSet<NF4>();
    private final Collection<NF5> nf5Axioms = new HashSet<NF5>();
    private final Collection<NF6> nf6Axioms = new HashSet<NF6>();
    private final Collection<NF7> nf7Axioms = new HashSet<NF7>();
    private final Collection<NF8> nf8Axioms = new HashSet<NF8>();

    public void addAxiom(NormalFormGCI a) {
        if (a instanceof NF1a) {
            nf1aAxioms.add((NF1a) a);
        } else if (a instanceof NF1b) {
            nf1bAxioms.add((NF1b) a);
        } else if (a instanceof NF2) {
            nf2Axioms.add((NF2) a);
        } else if (a instanceof NF3) {
            nf3Axioms.add((NF3) a);
        } else if (a instanceof NF4) {
            nf4Axioms.add((NF4) a);
        } else if (a instanceof NF5) {
            nf5Axioms.add((NF5) a);
        } else if (a instanceof NF6) {
            nf6Axioms.add((NF6) a);
        } else if (a instanceof NF7) {
            nf7Axioms.add((NF7) a);
        } else if (a instanceof NF8) {
            nf8Axioms.add((NF8) a);
        }
    }

    public Collection<NF1a> getNf1aAxioms() {
        return nf1aAxioms;
    }

    public Collection<NF1b> getNf1bAxioms() {
        return nf1bAxioms;
    }

    public Collection<NF2> getNf2Axioms() {
        return nf2Axioms;
    }

    public Collection<NF3> getNf3Axioms() {
        return nf3Axioms;
    }

    public Collection<NF4> getNf4Axioms() {
        return nf4Axioms;
    }

    public Collection<NF5> getNf5Axioms() {
        return nf5Axioms;
    }

    public Collection<NF6> getNf6Axioms() {
        return nf6Axioms;
    }

    public Collection<NF7> getNf7Axioms() {
        return nf7Axioms;
    }

    public Collection<NF8> getNf8Axioms() {
        return nf8Axioms;
    }
    
    public void clear() {
        nf1aAxioms.clear();
        nf1bAxioms.clear();
        nf2Axioms.clear();
        nf3Axioms.clear();
        nf4Axioms.clear();
        nf5Axioms.clear();
        nf6Axioms.clear();
        nf7Axioms.clear();
        nf8Axioms.clear();
    }
    
    public boolean isEmpty() {
        return nf1aAxioms.isEmpty() && nf1bAxioms.isEmpty() && nf2Axioms.isEmpty() && nf3Axioms.isEmpty() && 
                nf4Axioms.isEmpty() && nf5Axioms.isEmpty() && nf6Axioms.isEmpty() && nf7Axioms.isEmpty() && 
                nf8Axioms.isEmpty();
    }

}
 public final class DenseConceptMap<V> extends AbstractConceptMap<V> {
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private V[] members;

    /**
     * 
     * @param capacity
     *            estimated maximum key value + 1
     */
    @SuppressWarnings("unchecked")
    public DenseConceptMap(final int capacity) {
        members = (V[]) new Object[capacity];
    }

    public boolean containsKey(int key) {
        return key < members.length && null != members[key];
    }

    public V get(int key) {
        return key < members.length ? members[key] : null;
    }

    @SuppressWarnings("unchecked")
    public void put(int key, V value) {
        final int len = members.length;
        if (key >= len) {
            V[] newMembers = (V[]) new Object[key + 1];
            System.arraycopy(members, 0, newMembers, 0, len);
            members = newMembers;
            // System.err.println(getClass().getSimpleName() + " resize: " +
            // members.length /* + ", " + keySet.size() */);
        }
        members[key] = value;
    }

    public void remove(int key) {
        if (key < members.length) {
            members[key] = null;
        }
    }

    public IntIterator keyIterator() {
        return new IntIterator() {

            int next = 0;

            public boolean hasNext() {
                while (next < members.length && null == members[next]) {
                    next++;
                }
                return next < members.length;
            }

            public int next() {
                return hasNext() ? next++ : -1;
            }

        };
    }

    public void clear() {
        Arrays.fill(members, null);
    }

    public int size() {
        // throw new UnsupportedOperationException();
        return members.length;
    }

    @SuppressWarnings("unchecked")
    public void grow(int newSize) {
        V[] newMembers = (V[]) new Object[newSize];
        System.arraycopy(members, 0, newMembers, 0, members.length);
        members = newMembers;
    }

    @Override
    public String toString() {
        boolean separator = false;
        final StringBuilder sb = new StringBuilder();
        for (final IntIterator itr = keyIterator(); itr.hasNext();) {
            if (separator) {
                sb.append(", ");
            }
            int key = itr.next();
            sb.append(key);
            sb.append(" [ ");
            sb.append(get(key));

            separator = true;
        }
        return sb.toString();
    }
}
 public final class FastConceptHashSet implements IConceptSet {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private static final int TOMBSTOMB = -2;
    private static final int EMPTY = -1;

    private final static int REPROBE_LIMIT = 10;

    private int[] _keys;
    private int _size;

    public FastConceptHashSet() {
        clear();
    }

    /**
     * @param size
     *            must be a power of 2
     */
    private void reallocate(final int size) {
        _keys = new int[size];
        java.util.Arrays.fill(_keys, EMPTY);
        _size = 0;
    }

    public void add(final int concept) {
        final int len = _keys.length;
        final int mask = len - 1;
        int reprobe_count = 0;
        int idx = concept & mask;
        while (true) {
            final int K = _keys[idx];
            if (K < 0) { // K == EMPTY || K == TOMBSTONE
                _keys[idx] = concept;
                _size++;
                return;
            }
            if (concept == K) {
                return;
            }
            if (++reprobe_count > reprobeLimit(len)) {
                break;
            }
            idx = (idx + 1) & mask;
        }
        resize();
        add(concept);
    }

    private void resize() {
        grow(_keys.length * 2);
        // System.err.println(hashCode() + " resize from " + items.length);
    }

    public void addAll(IConceptSet set) {
        for (final IntIterator itr = set.iterator(); itr.hasNext();) {
            add(itr.next());
        }
    }

    public void clear() {
        reallocate(1);
    }

    public boolean contains(int concept) {
        final int len = _keys.length;
        final int mask = len - 1;
        int reprobe_count = 0;
        int idx = concept & mask;
        while (true) {
            final int K = _keys[idx];
            if (K == EMPTY) {
                return false;
            }
            if (concept == K) {
                return true;
            }
            if (++reprobe_count > reprobeLimit(len)) {
                break;
            }
            idx = (idx + 1) & mask;
        }
        return false;
    }

    private int reprobeLimit(final int len) {
        return REPROBE_LIMIT + (len >> 2);
    }

    public boolean containsAll(IConceptSet concepts) {
        throw new UnsupportedOperationException();
    }

    public boolean isEmpty() {
        return 0 == _size;
    }

    public IntIterator iterator() {
        if (_size < (_keys.length >> 1)) {
            // System.err.println("Shrinking from " + _keys.length);
            final int[] oldItems = _keys;
            reallocate(_keys.length >> 1);

            for (int i = 0; i < oldItems.length; i++) {
                final int concept = oldItems[i];
                if (concept >= 0) { // concept != EMPTY && concept != TOMBSTONE
                    add(concept);
                }
            }
        }
        return new IntIterator() {

            int next = 0;

            public boolean hasNext() {
                while (next < _keys.length && _keys[next] < 0) {
                    next++;
                }
                return next < _keys.length;
            }

            public int next() {
                return hasNext() ? _keys[next++] : EMPTY;
            }

        };
    }

    public void remove(final int concept) {
        final int len = _keys.length;
        final int mask = _keys.length - 1;
        int reprobe_count = 0;
        int idx = concept & mask;
        while (true) {
            final int K = _keys[idx];
            if (EMPTY == K) {
                return;
            }
            if (concept == K) {
                _size--;
                _keys[idx] = TOMBSTOMB;
            }
            if (++reprobe_count > reprobeLimit(len)) {
                break;
            }
            idx = (idx + 1) & mask;
        }
    }

    public void removeAll(IConceptSet set) {
        if (size() < set.size()) {
            // Can't use iterator since we're going to modify the set
            for (int i = 0; i < _keys.length; i++) {
                final int concept = _keys[i];
                if (concept >= 0 && set.contains(concept)) {
                    _keys[i] = TOMBSTOMB;
                    _size--;
                }
            }
        } else {
            for (final IntIterator itr = set.iterator(); itr.hasNext();) {
                final int concept = itr.next();
                remove(concept);
            }
        }
    }

    public int size() {
        return _size;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (final IntIterator itr = iterator(); itr.hasNext();) {
            final int c = itr.next();
            sb.append(c);
            if (itr.hasNext()) {
                sb.append(", ");
            }
        }
        sb.append("}");
        return sb.toString();
    }

    public void grow(int newSize) {
        final int[] oldItems = _keys;
        reallocate(newSize);

        for (int i = 0; i < oldItems.length; i++) {
            final int concept = oldItems[i];
            if (concept >= 0) { // concept != EMPTY && concept != TOMBSTONE
                add(concept);
            }
        }
    }

    public int[] toArray() {
        throw new UnsupportedOperationException();
    }
}
 public final class FastConceptMap<V> implements IConceptMap<V> {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private final static int EMPTY = -1;
    private final static Object TOMBSTOMB = null;

    private final static int REPROBE_LIMIT = 10;

    private int[] _keys;
    private Object[] _values;
    private int _size;

    public FastConceptMap(final int size, String label) {
        this();
    }

    public FastConceptMap() {
        clear();
    }

    public void clear() {
        reallocate(2);
    }

    private void reallocate(final int size) {
        _keys = new int[size];
        Arrays.fill(_keys, EMPTY);
        _values = new Object[size];
        Arrays.fill(_values, TOMBSTOMB);
        _size = 0;
    }

    public boolean containsKey(final int key) {
        return null != get(key);
    }

    @SuppressWarnings("unchecked")
    public V get(int key) {
        final int len = _keys.length;
        final int mask = len - 1;
        int reprobe_count = 0;
        int idx = key & mask;
        while (true) {
            final int K = _keys[idx];
            if (EMPTY == K) {
                return null;
            }
            if (key == K) {
                final Object val = _values[idx];
                return TOMBSTOMB == val ? null : (V) val;
            }
            if (++reprobe_count > (REPROBE_LIMIT + (len >> 2))) {
                break;
            }
            idx = (idx + 1) & mask;
        }
        resize();
        return get(key);
    }

    private void resize() {
        grow(_keys.length * 2);
    }

    public IntIterator keyIterator() {
        return new IntIterator() {

            int next = 0;

            public boolean hasNext() {
                while (next < _keys.length
                        && (EMPTY == _keys[next] || TOMBSTOMB == _values[next])) {
                    next++;
                }
                return next < _keys.length;
            }

            public int next() {
                return hasNext() ? _keys[next++] : EMPTY;
            }

        };
    }

    public void put(int key, V value) {
        final int len = _keys.length;
        final int mask = len - 1;
        int reprobe_count = 0;
        int idx = key & mask;
        while (true) {
            final int K = _keys[idx];
            if (EMPTY == K) {
                _keys[idx] = key;
                _values[idx] = value;
                _size++;
                return;
            }
            if (key == K) {
                if (TOMBSTOMB == _values[idx]) {
                    _size++;
                }
                _values[idx] = value;
                return;
            }
            if (++reprobe_count > (REPROBE_LIMIT + (len >> 2))) {
                break;
            }
            idx = (idx + 1) & mask;
        }
        resize();
        put(key, value);
    }

    public void remove(int key) {
        final int mask = _keys.length - 1;
        int idx = key & mask;
        while (true) {
            final int K = _keys[idx];
            if (EMPTY == K) {
                return;
            }
            if (key == K) {
                if (TOMBSTOMB != _values[idx]) {
                    _size--;
                    _values[idx] = TOMBSTOMB;
                }
                return;
            }
            idx = (idx + 1) & mask;
        }
    }

    public int size() {
        return _size;
    }

    @SuppressWarnings("unchecked")
    public void grow(final int newSize) {
        final int[] oldKeys = _keys;
        final Object[] oldValues = _values;

        reallocate(newSize);

        // System.err.println("resize from " + oldSize + " to " + newSize);
        // new Exception().printStackTrace();

        for (int i = 0; i < oldKeys.length; i++) {
            final int key = oldKeys[i];
            final Object val = oldValues[i];
            if (EMPTY != key && TOMBSTOMB != val) {
                put(key, (V) val);
            }
        }
    }

}
 public class FeatureMap<V> implements Serializable {
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final private FeatureSet keySet;
    private V[] members;

    @SuppressWarnings("unchecked")
    public FeatureMap(final int size) {
        keySet = new FeatureSet();
        members = (V[]) new Object[size];
    }

    public boolean containsKey(int key) {
        return keySet.contains(key);
    }

    public V get(int key) {
        if (key >= members.length)
            return null;
        return members[key];
    }

    public FeatureSet keySet() {
        return keySet;
    }

    @SuppressWarnings("unchecked")
    public void put(int key, V value) {
        keySet.add(key);
        final int len = members.length;
        if (key >= len) {
            V[] newMembers = (V[]) new Object[key + 1];
            System.arraycopy(members, 0, newMembers, 0, len);
            members = newMembers;
        }
        members[key] = value;
    }

    public void clear() {
        keySet.clear();
        Arrays.fill(members, null);
    }

}
 final public class FeatureSet extends BitSet implements Serializable {
    
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;

    public FeatureSet() {
    }

    public FeatureSet(final FeatureSet initial) {
        or(initial);
    }

    public void add(int feature) {
        set(feature);
    }

    public void addAll(FeatureSet set) {
        or(set);
    }

    public boolean contains(int feature) {
        return get(feature);
    }

    public int first() {
        return nextSetBit(0);
    }

    public int next(int feature) {
        return nextSetBit(feature);
    }
} public interface IConceptMap<V> extends Serializable {
    public boolean containsKey(int key);

    public V get(int key);

    public IntIterator keyIterator();

    public void put(int key, V value);

    public void remove(int key);

    public void clear();

    public int size();

    public void grow(int newSize);

    interface IConceptMapFactory {
        IConceptMap<IConceptSet> createSparseConceptMap(int size);

        IConceptMap<IConceptSet> createDenseConceptMap(int size);
    }

    public static IConceptMapFactory FACTORY = new IConceptMapFactory() {

        public IConceptMap<IConceptSet> createSparseConceptMap(final int size) {
            return new SparseConceptMap<IConceptSet>(size);
        }

        public IConceptMap<IConceptSet> createDenseConceptMap(final int size) {
            return new DenseConceptMap<IConceptSet>(size);
        }
    };

}
 public interface IConceptSet extends Serializable {
    final static IConceptSet EMPTY_SET = new EmptyConceptSet();

    public static ConceptSetFactory FACTORY = new ConceptSetFactory() {

        public IConceptSet createConceptSet() {
            return new SparseConceptHashSet();
        }

        public IConceptSet createConceptSet(final int size) {
            return new SparseConceptHashSet(size);
        }

        public IConceptSet createConceptSet(final IConceptSet initial) {
            final IConceptSet result;
            if (null == initial) {
                result = createConceptSet();
            } else {
                result = createConceptSet(initial.size());
                result.addAll(initial);
            }
            return result;
        }
    };

    public void add(int concept);

    public void addAll(IConceptSet set);

    public boolean contains(int concept);

    public boolean containsAll(IConceptSet concepts);

    public void remove(int concept);

    public void removeAll(IConceptSet set);

    public boolean isEmpty();

    public int hashCode();

    public boolean equals(Object o);

    public String toString();

    public IntIterator iterator();

    public void clear();

    public int size();

    public void grow(int newSize);

    public int[] toArray();
}
 public interface IMonotonicCollection<T> extends Iterable<T>, Serializable {

    public void add(T element);

    public int size();

}
 public interface IntIterator {

    public boolean hasNext();

    public int next();

} public class MonotonicCollection<T> implements IMonotonicCollection<T> {
    
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;

    // Logger
    private final static Logger log = LoggerFactory.getLogger(
            MonotonicCollection.class);
    
    public T[] data;
    private int count = 0;

    @SuppressWarnings("unchecked")
    public MonotonicCollection(final int size) {
        data = (T[]) new Object[size];
    }

    public void add(T element) {
        checkSize();
        data[count++] = element;
    }

    @SuppressWarnings("unchecked")
    private void checkSize() {
        if (count == data.length) {
            final int newSize = count < 134217728 ? count << 1
                    : count + 10000000;
            if (log.isTraceEnabled() && count > 1024)
                log.trace(hashCode() + "\t"
                        + getClass().getSimpleName() + " resize to: "
                        + (newSize));
            // For SNOMED 20061230, only a couple of these grow to 2048 entries
            T[] newData = (T[]) new Object[newSize];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
    }

    public Iterator<T> iterator() {
        return new Iterator<T>() {

            int next = 0;

            public boolean hasNext() {
                return next < count;
            }

            public T next() {
                return hasNext() ? data[next++] : null;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }

        };
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (final Iterator<T> itr = iterator(); itr.hasNext();) {
            final T o = itr.next();
            sb.append(o);
            if (itr.hasNext()) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public void addAll(MonotonicCollection<T> collection) {
        for (T element : collection) {
            add(element);
        }
    }

    protected T getData(int idx) {
    	return data[idx];
    }
    
    public int size() {
        return count;
    }

    public void clear() {
        count = 0;
    }

}
 final public class RoleSet extends BitSet implements Serializable {
    
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;

    public RoleSet() {
    }

    public RoleSet(final RoleSet initial) {
        or(initial);
    }

    public void add(int role) {
        set(role);
    }

    public void addAll(RoleSet set) {
        or(set);
    }

    public boolean contains(int role) {
        return get(role);
    }

    public int first() {
        return nextSetBit(0);
    }

    public int next(int role) {
        return nextSetBit(role);
    }
}
 public final class SparseConceptHashSet implements IConceptSet {

    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private static final int TOMBSTOMB = -2;
    private static final int EMPTY = -1;

    private int[] _items;
    private int _size;

    public SparseConceptHashSet() {
        clear();
    }

    public SparseConceptHashSet(final int initialCapacity) {
        reallocate(initialCapacity);
    }

    private void reallocate(int initialCapacity) {
        if (initialCapacity < 1) {
            initialCapacity = 1;
        }
        // we should maybe check that size is a "good" number (e.g., prime-ish)
        _items = new int[initialCapacity];
        java.util.Arrays.fill(_items, EMPTY);
        _size = 0;
    }

    private int hash1(final int concept) {
        return concept % _items.length;
    }

    private int hash2(final int concept, final int base) {
        // System.err.println(base + " " + items.length);
        return (base + 1) % _items.length;
    }

    public void add(final int concept) {
        // first ensure there's room for an extra concept
        if (_size >= (_items.length)) {
            resize(_items.length * 2);
        }

        int h = hash1(concept);

        // Since there must be room in _items for a new concept
        // (we did a resize above to ensure this), then we must
        // find an empty (or tombstoned) spot or the concept is
        // already there.

        while (_items[h] >= 0 && _items[h] != concept) {
            h = hash2(concept, h);
        }

        if (_items[h] < 0) {
            // Note, we can get here if the slot is a TOMBSTONE and we will
            // re-use the slot (unlike Cliff Click's lock-free hashtable),
            // but this may result in the same value being stored more than
            // once. We compensate for this in remove(), ensuring that all
            // values are deleted. Another consequence is that size() returns
            // the number of stored values, not the number of unique stored
            // values.
            _items[h] = concept;
            _size++;
        }

        assert _items[h] == concept;
    }

    public void addAll(final IConceptSet set) {
        for (final IntIterator itr = set.iterator(); itr.hasNext();) {
            add(itr.next());
        }
    }

    public void clear() {
        reallocate(1);
    }

    public boolean contains(final int concept) {
        int h = hash1(concept);

        // Use counter to handle the case when there are no EMPTY slots and the
        // item is not present.
        int counter = _items.length;
        while (_items[h] != EMPTY && _items[h] != concept && counter-- > 0) {
            h = hash2(concept, h);
        }

        return _items[h] == concept;
    }

    public boolean containsAll(IConceptSet concepts) {
        throw new UnsupportedOperationException();
    }

    public void remove(final int concept) {
        int h = hash1(concept);

        // Use counter to handle the case when there are no EMPTY slots and the
        // item is not present.
        int counter = _items.length;
        while (_items[h] != EMPTY && counter-- > 0) {
            if (concept == _items[h]) {
                _items[h] = TOMBSTOMB;
                _size--;
            }
            h = hash2(concept, h);
        }
    }

    public void removeAll(IConceptSet set) {
        if (size() < set.size()) {
            // Can't use iterator since we're going to modify the set
            for (int i = 0; i < _items.length; i++) {
                final int concept = _items[i];
                if (concept >= 0 && set.contains(concept)) {
                    _items[i] = TOMBSTOMB;
                    _size--;
                }
            }
        } else {
            for (final IntIterator itr = set.iterator(); itr.hasNext();) {
                final int concept = itr.next();
                remove(concept);
            }
        }
    }

    public boolean isEmpty() {
        return 0 == _size;
    }

    public IntIterator iterator() {
        // shrink table to reduce iterator cost when suitable
        //
        if (_items.length > 1000 && _size < (_items.length >> 3)) {
            // final double emptySpace = _items.length-_size;
            // System.err.println("OH: " + emptySpace + "\t" +
            // (emptySpace/_items.length));
            resize(_items.length >> 2);
        }
        return new IntIterator() {

            int next = 0;

            public boolean hasNext() {
                while (next < _items.length && _items[next] < 0) {
                    next++;
                }
                return next < _items.length;
            }

            public int next() {
                return hasNext() ? _items[next++] : EMPTY;
            }

        };
    }

    /**
     * The number of values stored in the set's backing store. Note that this
     * may be larger than the number of unique values in the set.
     */
    public int size() {
        return _size;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (final IntIterator itr = iterator(); itr.hasNext();) {
            final int c = itr.next();
            sb.append(c);
            if (itr.hasNext()) {
                sb.append(", ");
            }
        }
        sb.append("}");
        return sb.toString();
    }

    public void grow(int newSize) {
        resize(newSize);
    }

    private void resize(final int newSize) {
        // System.err.println(hashCode() + " resize from " + items.length);
        final int[] oldItems = _items;
        reallocate(newSize);

        for (int i = 0; i < oldItems.length; i++) {
            final int concept = oldItems[i];
            if (concept >= 0) {
                add(concept);
            }
        }
    }

    public int[] toArray() {
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (IntIterator i = iterator(); i.hasNext();) {
            res.add(i.next());
        }
        int[] arr = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arr[i] = res.get(i);
        }
        return arr;
    }

}
 public final class SparseConceptMap<V> extends AbstractConceptMap<V> {
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    final private IConceptSet keySet;
    protected SparseArray<V> members;
    protected String lbl;

    // public ConceptMap() {
    // this(Concept.getTotalConcepts());
    // }

    // public void finalize() {
    // int unused = 0;
    // for (int i = 0; i < members.length; i++) {
    // if (null == members[i]) {
    // unused++;
    // }
    // }
    // System.err.println(lbl + ": " + members.length + ", " + unused + ", " +
    // 100.0*unused/members.length);
    // }

    public int size() {
        return keySet.size();
    }

    public SparseConceptMap(final int size) {
        this(size, null);
    }

    public SparseConceptMap(final int size, String lbl) {
        this.lbl = lbl;
        keySet = IConceptSet.FACTORY.createConceptSet(size);
        members = new SparseArray<V>(size);
        // System.err.println("ConceptMap: " + size);
    }

    public boolean containsKey(int key) {
        return null != members.get(key);
        // return key < members.length && null != members[key];
    }

    public V get(int key) {
        return members.get(key);
    }

    // public ConceptSet keySet() {
    // return keySet;
    // }

    public void put(int key, V value) {
        keySet.add(key);
        members.set(key, value);
    }

    public void remove(int key) {
        keySet.remove(key);
        members.set(key, null);
    }

    public IntIterator keyIterator() {
        return keySet.iterator();
    }

    public void clear() {
        keySet.clear();
        members.clear();
    }

    public void grow(int newSize) {
        keySet.grow(newSize);
        members.grow(newSize);
    }

}
 final public class SparseConceptSet implements IConceptSet {
    
    /**
     * Serialisation version.
     */
    private static final long serialVersionUID = 1L;
    
    private int[] items;
    private int size;

    /**
     * 
     * @param capacity
     *            initial size of underlying array
     */
    public SparseConceptSet(final int capacity) {
        items = new int[capacity];
        size = 0;
        items[size] = -1;
    }

    public SparseConceptSet() {
        this(10);
    }

    @SuppressFBWarnings("IM_AVERAGE_COMPUTATION_COULD_OVERFLOW")
    public synchronized void add(final int concept) {
        int low = 0;
        int high = size;
        while ((high - low) > 16) {
            // binary search
            int probe = (low + high) >> 1; // don't need to worry about overflow
            if (items[probe] > concept) {
                low = probe + 1;
            } else if (items[probe] < concept) {
                high = probe - 1;
            } else {
                // concept found - nothing to do
                return;
            }
        }

        // fall through to linear search
        while (concept < items[low]) {
            low++;
        }

        if (concept > items[low]) {
            size++;
            if (items.length == size) {
                final int increment = 10;
                final int[] newItems = new int[size + increment];
                System.arraycopy(items, 0, newItems, 0, low);
                System.arraycopy(items, low, newItems, low + 1, size - low);
                items = newItems;
                // System.err.println(size + ", " + i + ", " + items.length +
                // ", " + (size-i));
            } else {
                System.arraycopy(items, low, items, low + 1, size - low);
            }
            items[low] = concept;
        } // else items[i] == concept, so do nothing
        else if (concept != items[low]) {
            throw new AssertionError(
                    "Internal error detected, expecting items[i] == concept where i = "
                            + low + ", items[i] = " + items[low]
                            + ", and concept = " + concept);
        }
    }

    public void addAll(final IConceptSet set) {
        for (final IntIterator itr = set.iterator(); itr.hasNext();) {
            add(itr.next());
        }
    }

    public void clear() {
        throw new UnsupportedOperationException();
    }

    @SuppressFBWarnings("IM_AVERAGE_COMPUTATION_COULD_OVERFLOW")
    public synchronized boolean contains(final int concept) {
        int low = 0;
        int high = size;
        while ((high - low) > 16) {
            // binary search
            int probe = (low + high) >> 1; // don't need to worry about overflow
            if (items[probe] > concept) {
                low = probe + 1;
            } else if (items[probe] < concept) {
                high = probe - 1;
            } else {
                return true;
            }
        }

        // fall through to linear search
        while (low < items.length && concept < items[low]) {
            low++;
        }

        return low < items.length && concept == items[low];
    }

    public boolean containsAll(IConceptSet concepts) {
        if (concepts.isEmpty()) {
            return true;
        }
        final IConceptSet s = IConceptSet.FACTORY.createConceptSet(concepts);
        s.removeAll(this);
        return s.isEmpty();
        // return false;
    }

    public boolean isEmpty() {
        return 0 == size();
    }

    public synchronized IntIterator iterator() {
        return new SparseConceptSetIntIterator(items, size);
    }

    public void remove(int concept) {
        throw new UnsupportedOperationException();
    }

    public void removeAll(IConceptSet set) {
        throw new UnsupportedOperationException();
    }

    public synchronized String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < size; i++) {
            sb.append(items[i]);
            if (i + 1 < size) {
                sb.append(", ");
            }
        }
        sb.append("}");
        return sb.toString();
        // return size + ":" +Arrays.toString(items);
    }

    public int size() {
        return size;
    }

    public synchronized void grow(int newSize) {
        assert newSize >= size;

        final int[] newItems = new int[newSize];
        System.arraycopy(items, 0, newItems, 0, size);
        items = newItems;
    }

    public synchronized int[] toArray() {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = items[i];
        }

        return res;
    }

}

import java.io.Serializable;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.TimeUnit;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import au.csiro.ontology.Node;
import au.csiro.ontology.model.Axiom;
import au.csiro.ontology.model.Concept;
import au.csiro.ontology.model.ConceptInclusion;
import au.csiro.ontology.model.FunctionalFeature;
import au.csiro.ontology.model.Literal;
import au.csiro.ontology.model.NamedFeature;
import au.csiro.ontology.model.NamedRole;
import au.csiro.ontology.model.Role;
import au.csiro.ontology.model.RoleInclusion;
import au.csiro.ontology.util.Statistics;
import au.csiro.snorocket.core.axioms.GCI;
import au.csiro.snorocket.core.axioms.IConjunctionQueueEntry;
import au.csiro.snorocket.core.axioms.IRoleQueueEntry;
import au.csiro.snorocket.core.axioms.Inclusion;
import au.csiro.snorocket.core.axioms.NF1a;
import au.csiro.snorocket.core.axioms.NF1b;
import au.csiro.snorocket.core.axioms.NF2;
import au.csiro.snorocket.core.axioms.NF3;
import au.csiro.snorocket.core.axioms.NF4;
import au.csiro.snorocket.core.axioms.NF5;
import au.csiro.snorocket.core.axioms.NF6;
import au.csiro.snorocket.core.axioms.NF7;
import au.csiro.snorocket.core.axioms.NF8;
import au.csiro.snorocket.core.axioms.NormalFormGCI;
import au.csiro.snorocket.core.axioms.RI;
import au.csiro.snorocket.core.concurrent.CR;
import au.csiro.snorocket.core.concurrent.Context;
import au.csiro.snorocket.core.concurrent.TaxonomyWorker1;
import au.csiro.snorocket.core.concurrent.TaxonomyWorker2;
import au.csiro.snorocket.core.concurrent.Worker;
import au.csiro.snorocket.core.model.AbstractConcept;
import au.csiro.snorocket.core.model.AbstractLiteral;
import au.csiro.snorocket.core.model.Conjunction;
import au.csiro.snorocket.core.model.Datatype;
import au.csiro.snorocket.core.model.DateLiteral;
import au.csiro.snorocket.core.model.DecimalLiteral;
import au.csiro.snorocket.core.model.Existential;
import au.csiro.snorocket.core.model.IntegerLiteral;
import au.csiro.snorocket.core.model.StringLiteral;
import au.csiro.snorocket.core.util.AxiomSet;
import au.csiro.snorocket.core.util.DenseConceptMap;
import au.csiro.snorocket.core.util.FastConceptHashSet;
import au.csiro.snorocket.core.util.FastConceptMap;
import au.csiro.snorocket.core.util.FeatureMap;
import au.csiro.snorocket.core.util.FeatureSet;
import au.csiro.snorocket.core.util.IConceptMap;
import au.csiro.snorocket.core.util.IConceptSet;
import au.csiro.snorocket.core.util.IMonotonicCollection;
import au.csiro.snorocket.core.util.IntIterator;
import au.csiro.snorocket.core.util.MonotonicCollection;
import au.csiro.snorocket.core.util.RoleSet;
import au.csiro.snorocket.core.util.SparseConceptHashSet;
import au.csiro.snorocket.core.util.SparseConceptMap;
import au.csiro.snorocket.core.util.SparseConceptSet;
    /**
     * 
     * @param factory
     * @param inclusions
     */
    public NormalisedOntology(final IFactory factory, final Set<? extends Axiom> inclusions) {
        this(factory);
        
        loadAxioms(inclusions);
        
        if(log.isTraceEnabled()) {
            printNormalisedAxioms();
        }
    }

    final static int CONCEPT_COUNT_ESTIMATE = 500000;

    /**
     * 
     * @param baseConceptCount
     * @param conceptCount
     *            if this value is too small, the algorithm performance will be
     *            impacted
     * @param roleCount
     */
    public NormalisedOntology(final IFactory factory) {
        // TODO: how do we estimate these numbers better?
        this(
            factory,
            new DenseConceptMap<MonotonicCollection<IConjunctionQueueEntry>>(CONCEPT_COUNT_ESTIMATE),
            new SparseConceptMap<MonotonicCollection<NF2>>(CONCEPT_COUNT_ESTIMATE, "ontologyNF2"),
            new SparseConceptMap<ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>>>(CONCEPT_COUNT_ESTIMATE, "ontologyNF3"),
            new MonotonicCollection<NF4>(15), new MonotonicCollection<NF5>(1), 
            new SparseConceptMap<MonotonicCollection<NF7>>(10, "ontologyNF7"),
            new FeatureMap<MonotonicCollection<NF8>>(10)
        );
    }

    /**
     * 
     * @param factory
     * @param nf1q
     * @param nf2q
     * @param nf3q
     * @param nf4q
     * @param nf5q
     * @param nf7q
     * @param nf8q
     */
    protected NormalisedOntology(
            final IFactory factory,
            final IConceptMap<MonotonicCollection<IConjunctionQueueEntry>> nf1q,
            final IConceptMap<MonotonicCollection<NF2>> nf2q,
            final IConceptMap<ConcurrentMap<Integer, Collection<IConjunctionQueueEntry>>> nf3q,
            final IMonotonicCollection<NF4> nf4q,
            final IMonotonicCollection<NF5> nf5q,
            final IConceptMap<MonotonicCollection<NF7>> nf7q,
            final FeatureMap<MonotonicCollection<NF8>> nf8q) {
        this.factory = factory;
        contextIndex = new FastConceptMap<Context>(factory.getTotalConcepts(), "");
        roleClosureCache = new ConcurrentHashMap<Integer, RoleSet>(factory.getTotalRoles());

        this.ontologyNF1 = nf1q;
        this.ontologyNF2 = nf2q;
        this.ontologyNF3 = nf3q;
        this.ontologyNF4 = nf4q;
        this.ontologyNF5 = nf5q;
        this.ontologyNF7 = nf7q;
        this.ontologyNF8 = nf8q;
    }

    /**
     * Normalises and loads a set of axioms.
     * 
     * @param inclusions
     */
    public void loadAxioms(final Set<? extends Axiom> inclusions) {
        long start = System.currentTimeMillis();
        if(log.isInfoEnabled())
            log.info("Loading " + inclusions.size() + " axioms");
        Set<Inclusion> normInclusions = normalise(inclusions);
        if(log.isInfoEnabled()) log.info("Processing " + normInclusions.size() + " normalised axioms");
        Statistics.INSTANCE.setTime("normalisation", System.currentTimeMillis() - start);
        start = System.currentTimeMillis();
        for (Inclusion i : normInclusions) {
            addTerm(i.getNormalForm());
        }
        
        Statistics.INSTANCE.setTime("indexing", System.currentTimeMillis() - start);
    }
    
    /**
     * EXPERIMENTAL
     * 
     * TODO deal with missing NF1bs axioms!
     * 
     * TODO: inspect NF1bs and hierarchy to derive missing axioms!
     */
    public void prapareForInferred() {
        log.info("Adding additional axioms to calculate inferred axioms");
        int key = 0;
        
        int numNf3 = 0;
        int numNf8 = 0;
        for(final IntIterator itr = ontologyNF2.keyIterator(); itr.hasNext();) {
            MonotonicCollection<NF2> nf2s = ontologyNF2.get(itr.next());
            for(final Iterator<NF2> itr2 = nf2s.iterator(); itr2.hasNext();) {
                NF2 nf2 = itr2.next();
                
                // TODO remove
                if(factory.lookupConceptId(nf2.lhsA).equals("287402001")) {
                    System.err.println(nf2);
                    
                    key = nf2.rhsB;
                    
                }
                // TODO remove
                
                // The problem is likely to be in this method call!
                if(!containsExistentialInNF3s(nf2.rhsR, nf2.rhsB, nf2.lhsA)) {
                    NF3 nnf = NF3.getInstance(nf2.rhsR, nf2.rhsB, factory.getConcept(new Existential(nf2.rhsR, 