Java 类org.apache.lucene.util.OpenBitSet 实例源码

/**
     * Build the prefix blocks for a level. It is a Hashmap containing the
     * prefix as a key and the corresponding attributes as  the value.
     */
    private void buildPrefixBlocks() {
//      System.out.println("Start BuildPrefixBlocks");
        this.prefix_blocks.clear();
        for (OpenBitSet level_iter : level0.keySet()) {
            OpenBitSet prefix = getPrefix(level_iter);

            if (prefix_blocks.containsKey(prefix)) {
                prefix_blocks.get(prefix).add(level_iter);
            } else {
                ObjectArrayList<OpenBitSet> list = new ObjectArrayList<OpenBitSet>();
                list.add(level_iter);
                prefix_blocks.put(prefix, list);
            }
        }
//      System.out.println("Stop BuildPrefixBlocks");
    }

public FDTreeElement addGeneralization(OpenBitSet lhs, OpenBitSet rhs) {
    FDTreeElement currentNode = this;
    currentNode.addRhsAttributes(rhs);

    boolean newElement = false;
    for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
        if (currentNode.getChildren() == null) {
            currentNode.setChildren(new FDTreeElement[this.numAttributes]);
            currentNode.getChildren()[i] = new FDTreeElement(this.numAttributes);
            newElement = true;
        }
        else if (currentNode.getChildren()[i] == null) {
            currentNode.getChildren()[i] = new FDTreeElement(this.numAttributes);
            newElement = true;
        }

        currentNode = currentNode.getChildren()[i];
        currentNode.addRhsAttributes(rhs);
    }

    if (newElement)
        return currentNode;
    return null;
}

protected void getUCCAndGeneralizations(OpenBitSet ucc, int currentUCCAttr, OpenBitSet currentUCC, List<OpenBitSet> foundUCCs) {
    if (this.isUCC)
        foundUCCs.add(currentUCC.clone());

    if (this.children == null)
        return;

    while (currentUCCAttr >= 0) {
        int nextLhsAttr = ucc.nextSetBit(currentUCCAttr + 1);

        if (this.children[currentUCCAttr] != null) {
            currentUCC.set(currentUCCAttr);
            this.children[currentUCCAttr].getUCCAndGeneralizations(ucc, nextLhsAttr, currentUCC, foundUCCs);
            currentUCC.clear(currentUCCAttr);
        }

        currentUCCAttr = nextLhsAttr;
    }
}

public void filterSpecializations(FDTree filteredTree, OpenBitSet activePath) {
    int attr;
    for (attr = 1; attr <= maxAttributeNumber; attr++) {
        if (children[attr - 1] != null) {
            activePath.set(attr);
            children[attr - 1].filterSpecializations(filteredTree, activePath);
            activePath.clear(attr);
        }
    }

    for (attr = 1; attr <= maxAttributeNumber; attr++) {
        if (this.isfd[attr - 1]) {
            // TODO: containsSpecialization should be enough
            if (!filteredTree.getSpecialization(activePath, attr, 0, new OpenBitSet())) {
                filteredTree.addFunctionalDependency(activePath, attr);
            }
        }
    }
}

public void removeLhs(OpenBitSet lhs) {
    LhsTrieElement[] path = new LhsTrieElement[(int)lhs.cardinality()];
    int currentPathIndex = 0;

    LhsTrieElement currentNode = this;
    path[currentPathIndex] = currentNode;
    currentPathIndex++;

    for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
        currentNode = currentNode.getChildren()[i];
        path[currentPathIndex] = currentNode;
        currentPathIndex++;
    }

    for (int i = path.length - 1; i >= 0; i --) {
        path[i].removeChild(i);
        if (path[i].getChildren() != null)
            break;
    }
}

@Test
public void testGetGeneralizationAndDelete() {
    OpenBitSet lhs = new OpenBitSet();
    lhs.set(1);
    lhs.set(2);
    lhs.set(4);
    lhs.set(5);
    OpenBitSet specLhs = new OpenBitSet();
    assertTrue(fdtree.getGeneralizationAndDelete(lhs, 3, 0, specLhs));

    OpenBitSet expResult = new OpenBitSet();

    expResult.set(1);
    expResult.set(2);
    expResult.set(4);
    assertEquals(expResult, specLhs);
}

@Test
public void testDeleteGeneralizations() {
    fdtree = new FDTree(4);
    OpenBitSet lhs = new OpenBitSet();
    lhs.set(1);
    lhs.set(2);

    fdtree.addFunctionalDependency(lhs, 4);
    lhs.clear(2);
    lhs.set(3);
    fdtree.addFunctionalDependency(lhs, 4);

    lhs.set(2);
    fdtree.deleteGeneralizations(lhs, 4, 0);
    assertTrue(fdtree.isEmpty());
}

private OpenBitSet searchRequestToBitSet(@Nullable final Search searchreq, IndexSearcher searcher,
    IndexReader reader) throws IOException
{
    if( searchreq != null )
    {
        Filter filters = getFilter(searchreq);
        Query query = getQuery(searchreq, null, false);

        BitSetCollector collector = new BitSetCollector();
        searcher.search(query, filters, collector);
        return collector.getBitSet();
    }
    else
    {
        return (OpenBitSet) new InstitutionFilter().getDocIdSet(reader);
    }
}

public boolean add(int[][] compressedRecords, OpenBitSet lhs, int nextLhsAttr, int recordId, int content) {
    if (nextLhsAttr < 0)
        return this.content != -1 && this.content == content;

    int nextCluster = compressedRecords[recordId][nextLhsAttr];
    if (nextCluster < 0)
        return true;

    ClusterTreeElement child = this.children.get(nextCluster);
    if (child == null) {
        child = new ClusterTreeElement(compressedRecords, lhs, lhs.nextSetBit(nextLhsAttr + 1), recordId, content);
        this.children.put(nextCluster, child);
        return true;
    }

    return child.add(compressedRecords, lhs, lhs.nextSetBit(nextLhsAttr + 1), recordId, content);
}

protected void getFdAndGeneralizations(OpenBitSet lhs, int rhs, int currentLhsAttr, OpenBitSet currentLhs, List<OpenBitSet> foundLhs) {
    if (this.isFd(rhs))
        foundLhs.add(currentLhs.clone());

    if (this.children == null)
        return;

    while (currentLhsAttr >= 0) {
        int nextLhsAttr = lhs.nextSetBit(currentLhsAttr + 1);

        if ((this.children[currentLhsAttr] != null) && (this.children[currentLhsAttr].hasRhsAttribute(rhs))) {
            currentLhs.set(currentLhsAttr);
            this.children[currentLhsAttr].getFdAndGeneralizations(lhs, rhs, nextLhsAttr, currentLhs, foundLhs);
            currentLhs.clear(currentLhsAttr);
        }

        currentLhsAttr = nextLhsAttr;
    }
}

protected void filterGeneralizations(OpenBitSet lhs, int rhs, int currentLhsAttr, OpenBitSet currentLhs) {
    if (currentLhs.equals(lhs))
        return;

    this.rhsFds.clear(rhs);

    // Is the dependency already read and we have not yet found a generalization?
    if (currentLhsAttr < 0)
        return;

    if (this.children != null) {
        for (int nextLhsAttr = lhs.nextSetBit(currentLhsAttr); nextLhsAttr >= 0; nextLhsAttr = lhs.nextSetBit(nextLhsAttr + 1)) {
            if ((this.children[nextLhsAttr] != null) && (this.children[nextLhsAttr].hasRhsAttribute(rhs))) {
                currentLhs.set(nextLhsAttr);
                this.children[nextLhsAttr].filterGeneralizations(lhs, rhs, lhs.nextSetBit(nextLhsAttr + 1), currentLhs);
                currentLhs.clear(nextLhsAttr);
            }
        }
    }
}

/**
 * Checks whether all subsets of X (with length of X - 1) are part of the last level.
 * Only if this check return true X is added to the new level.
 *
 * @param X
 * @return
 */
private boolean checkSubsets(OpenBitSet X) {
    boolean xIsValid = true;

    // clone of X for usage in the following loop
    OpenBitSet Xclone = (OpenBitSet) X.clone();

    for (int l = X.nextSetBit(0); l >= 0; l = X.nextSetBit(l + 1)) {
        Xclone.clear(l);
        if (!level0.containsKey(Xclone)) {
            xIsValid = false;
            break;
        }
        Xclone.set(l);
    }

    return xIsValid;
}

public FDTreeElement addFunctionalDependency(OpenBitSet lhs, OpenBitSet rhs) {
    FDTreeElement currentNode = this;
    currentNode.addRhsAttributes(rhs);

    int lhsLength = 0;
    for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
        lhsLength++;

        if (currentNode.getChildren() == null) {
            currentNode.setChildren(new FDTreeElement[this.numAttributes]);
            currentNode.getChildren()[i] = new FDTreeElement(this.numAttributes);
        }
        else if (currentNode.getChildren()[i] == null) {
            currentNode.getChildren()[i] = new FDTreeElement(this.numAttributes);
        }

        currentNode = currentNode.getChildren()[i];
        currentNode.addRhsAttributes(rhs);
    }
    currentNode.markFds(rhs);

    this.depth = Math.max(this.depth, lhsLength);
    return currentNode;
}

public UCCTreeElement addUniqueColumnCombination(OpenBitSet ucc) {
    UCCTreeElement currentNode = this;

    int uccLength = 0;
    for (int i = ucc.nextSetBit(0); i >= 0; i = ucc.nextSetBit(i + 1)) {
        uccLength++;

        if (currentNode.getChildren() == null) {
            currentNode.setChildren(new UCCTreeElement[this.numAttributes]);
            currentNode.getChildren()[i] = new UCCTreeElement(this.numAttributes, false);
        }
        else if (currentNode.getChildren()[i] == null) {
            currentNode.getChildren()[i] = new UCCTreeElement(this.numAttributes, false);
        }

        currentNode = currentNode.getChildren()[i];
    }
    currentNode.setUCC(true);

    this.depth = Math.max(this.depth, uccLength);
    return currentNode;
}

private void executePara(int attribute) throws CouldNotReceiveResultException, ColumnNameMismatchException {

        for (OpenBitSet lhs : this.lhss.get(attribute)) {
            if (lhs.get(attribute)) {
                continue;
            }
            IntList bits = new IntArrayList();
            int lastIndex = lhs.nextSetBit(0);
            while (lastIndex != -1) {
                bits.add(lastIndex);
                lastIndex = lhs.nextSetBit(lastIndex + 1);
            }

            FunctionalDependencyGroup2 fdg = new FunctionalDependencyGroup2(attribute, bits);
            this.fdrr.receiveResult((fdg.buildDependency(this.relationName, this.columns)));
            this.result.add(fdg);
        }
    }

protected void minimize(OpenBitSet lhs, FDTree fdTree) {
    // Traverse children and minimize their FDs
    if (this.children != null) {
        for (int childAttr = 0; childAttr < this.numAttributes; childAttr++) {
            FDTreeElement element = this.children[childAttr];
            if (element != null) {
                lhs.set(childAttr);
                element.minimize(lhs, fdTree);
                lhs.clear(childAttr);
            }
        }
    }

    // Minimize Fds by checking for generalizations
    for (int rhs = this.rhsFds.nextSetBit(0); rhs >= 0; rhs = this.rhsFds.nextSetBit(rhs + 1)) {
        this.rhsFds.clear(rhs);

        // If the FD was minimal, i.e. no generalization exists, set it again
        if (!fdTree.containsFdOrGeneralization(lhs, rhs))
            this.rhsFds.set(rhs);
    }
}

public void getLevel(int level, int currentLevel, OpenBitSet currentLhs, List<FDTreeElementLhsPair> result) {
    if (level == currentLevel) {
        result.add(new FDTreeElementLhsPair(this, currentLhs.clone()));
    }
    else {
        currentLevel++;
        if (this.children == null)
            return;

        for (int child = 0; child < this.numAttributes; child++) {
            if (this.children[child] == null)
                continue;

            currentLhs.set(child);
            this.children[child].getLevel(level, currentLevel, currentLhs, result);
            currentLhs.clear(child);
        }
    }
}

public FDTreeElement addGeneralization(OpenBitSet lhs, int rhs) {
    FDTreeElement currentNode = this;
    currentNode.addRhsAttribute(rhs);

    boolean newElement = false;
    for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
        if (currentNode.getChildren() == null) {
            currentNode.setChildren(new FDTreeElement[this.numAttributes]);
            currentNode.getChildren()[i] = new FDTreeElement(this.numAttributes);
            newElement = true;
        }
        else if (currentNode.getChildren()[i] == null) {
            currentNode.getChildren()[i] = new FDTreeElement(this.numAttributes);
            newElement = true;
        }

        currentNode = currentNode.getChildren()[i];
        currentNode.addRhsAttribute(rhs);
    }

    if (newElement)
        return currentNode;
    return null;
}

private void addAllDependenciesToResultReceiver(FDTreeElement fds, OpenBitSet activePath) throws CouldNotReceiveResultException, ColumnNameMismatchException {
        if (this.fdResultReceiver == null) {
            return;
        }
        for (int attr = 1; attr <= numberAttributes; attr++) {
            if (fds.isFd(attr - 1)) {
                int j = 0;
                ColumnIdentifier[] columns = new ColumnIdentifier[(int) activePath.cardinality()];
                for (int i = activePath.nextSetBit(0); i >= 0; i = activePath.nextSetBit(i + 1)) {
                    columns[j++] = this.columnIdentifiers.get(i - 1);
                }
                ColumnCombination colCombination = new ColumnCombination(columns);
                de.metanome.algorithm_integration.results.FunctionalDependency fdResult = new de.metanome.algorithm_integration.results.FunctionalDependency(colCombination, columnIdentifiers.get((int) attr - 1));
//              System.out.println(fdResult.toString());
                fdResultReceiver.receiveResult(fdResult);
            }
        }

        for (int attr = 1; attr <= numberAttributes; attr++) {
            if (fds.getChild(attr - 1) != null) {
                activePath.set(attr);
                this.addAllDependenciesToResultReceiver(fds.getChild(attr - 1), activePath);
                activePath.clear(attr);
            }
        }
    }

private void fetchNonFdsWindowingOverClusters(Set<OpenBitSet> negCover, int[][] compressedRecords, List<PositionListIndex> plis) {
    System.out.println("\tMoving window over small clusters ...");
    for (PositionListIndex pli : plis) {
        boolean selectSmallClustersOnly = pli.getClusters().size() < this.attributeThreshold;   // If there are too few clusters, then the clusters are large and we have already executed sufficient comparisons between the records of these clusters

        for (IntArrayList cluster : pli.getClusters()) {
            if (selectSmallClustersOnly && (cluster.size() > this.windowSize))                  // But if the current cluster is very small, we should still use it for comparisons (the other cluster(s) must be very large)
                continue;

            for (int recordIndex = 0; recordIndex < cluster.size(); recordIndex++) {
                int recordId = cluster.getInt(recordIndex);

                for (int partnerRecordIndex = recordIndex + 1; partnerRecordIndex < Math.min(recordIndex + this.windowSize, cluster.size()); partnerRecordIndex++) {
                    int partnerRecordId = cluster.getInt(partnerRecordIndex);

                    negCover.add(this.getViolatedFds(compressedRecords[recordId], compressedRecords[partnerRecordId]));
                }
            }
        }
    }
}

protected boolean containsFdOrSpecialization(OpenBitSet lhs, int rhs, int currentLhsAttr) {
    if (!this.hasRhsAttribute(rhs))
        return false;

    // Is the dependency already covered?
    if (currentLhsAttr < 0)
        return true; // TODO: unsafe if fds can be removed from the tree without adding a specialization of the removed fd. Then, we cannot be sure here: maybe the attributes of the lhs are covered but the current lhs is not part of a valid fd if no isFd() is set for larger lhs in the tree (this might occur if the fd has been removed from the tree)

    if (this.children == null)
        return false;

    for (int child = 0; child < this.numAttributes; child++) {
        if (this.children[child] == null)
            continue;

        if (child == currentLhsAttr) {
            if (this.children[child].containsFdOrSpecialization(lhs, rhs, lhs.nextSetBit(currentLhsAttr + 1)))
                return true;
        }
        else {
            if (this.children[child].containsFdOrSpecialization(lhs, rhs, currentLhsAttr))
                return true;
        }   
    }
    return false;
}

protected boolean containsFdOrGeneralization(OpenBitSet lhs, int rhs, int currentLhsAttr) {
    if (this.isFd(rhs))
        return true;

    // Is the dependency already read and we have not yet found a generalization?
    if (currentLhsAttr < 0)
        return false;

    int nextLhsAttr = lhs.nextSetBit(currentLhsAttr + 1);

    if ((this.children != null) && (this.children[currentLhsAttr] != null) && (this.children[currentLhsAttr].hasRhsAttribute(rhs)))
        if (this.children[currentLhsAttr].containsFdOrGeneralization(lhs, rhs, nextLhsAttr))
            return true;

    return this.containsFdOrGeneralization(lhs, rhs, nextLhsAttr);
}

public boolean add(int[][] compressedRecords, OpenBitSet lhs, int nextLhsAttr, int recordId, int content) {
    if (nextLhsAttr < 0)
        return this.content != -1 && this.content == content;

    int nextCluster = compressedRecords[recordId][nextLhsAttr];
    if (nextCluster < 0)
        return true;

    ClusterTreeElement child = this.children.get(nextCluster);
    if (child == null) {
        child = new ClusterTreeElement(compressedRecords, lhs, lhs.nextSetBit(nextLhsAttr + 1), recordId, content);
        this.children.put(nextCluster, child);
        return true;
    }

    return child.add(compressedRecords, lhs, lhs.nextSetBit(nextLhsAttr + 1), recordId, content);
}

public void runNext(FDList newNonFds, int[][] compressedRecords) {
    this.windowDistance++;
    int numNewNonFds = 0;
    int numComparisons = 0;
    OpenBitSet equalAttrs = new OpenBitSet(this.posCover.getNumAttributes());

    int previousNegCoverSize = newNonFds.size();
    Iterator<IntArrayList> clusterIterator = this.clusters.iterator();
    while (clusterIterator.hasNext()) {
        IntArrayList cluster = clusterIterator.next();

        if (cluster.size() <= this.windowDistance) {
            clusterIterator.remove();
            continue;
        }

        for (int recordIndex = 0; recordIndex < (cluster.size() - this.windowDistance); recordIndex++) {
            int recordId = cluster.getInt(recordIndex);
            int partnerRecordId = cluster.getInt(recordIndex + this.windowDistance);

            this.sampler.match(equalAttrs, compressedRecords[recordId], compressedRecords[partnerRecordId]);

            if (!this.negCover.contains(equalAttrs)) {
                OpenBitSet equalAttrsCopy = equalAttrs.clone();
                this.negCover.add(equalAttrsCopy);
                newNonFds.add(equalAttrsCopy);

                this.memoryGuardian.memoryChanged(1);
                this.memoryGuardian.match(this.negCover, this.posCover, newNonFds);
            }
            numComparisons++;
        }
    }
    numNewNonFds = newNonFds.size() - previousNegCoverSize;

    this.numNewNonFds.add(numNewNonFds);
    this.numComparisons.add(numComparisons);
}

@Override
public DocIdSet getDocIdSet(IndexReader reader) throws IOException
{
    int max = reader.maxDoc();
    OpenBitSet good = new OpenBitSet(max);
    Institution institution = CurrentInstitution.get();
    Term term = new Term(FreeTextQuery.FIELD_INSTITUTION, Long.toString(institution.getUniqueId()));
    TermDocs docs = reader.termDocs(term);
    while( docs.next() )
    {
        good.set(docs.doc());
    }
    docs.close();
    return good;
}

public UCCTreeElement addUniqueColumnCombinationGetIfNew(OpenBitSet ucc) {
    UCCTreeElement currentNode = this;

    boolean isNew = false;
    int lhsLength = 0;
    for (int i = ucc.nextSetBit(0); i >= 0; i = ucc.nextSetBit(i + 1)) {
        lhsLength++;

        if (currentNode.getChildren() == null) {
            currentNode.setChildren(new UCCTreeElement[this.numAttributes]);
            currentNode.getChildren()[i] = new UCCTreeElement(this.numAttributes, false);
            isNew = true;
        }
        else if (currentNode.getChildren()[i] == null) {
            currentNode.getChildren()[i] = new UCCTreeElement(this.numAttributes, false);
            isNew = true;
        }

        currentNode = currentNode.getChildren()[i];
    }
    currentNode.setUCC(true);

    this.depth = Math.max(this.depth, lhsLength);
    if (isNew)
        return currentNode;
    return null;
}

public Set<OpenBitSet> bitSets(FDTree negCoverTree) {
    Set<OpenBitSet> posCoverTree = new HashSet<>(this.numAttributes);
    OpenBitSet activePath = new OpenBitSet();

    this.fetchBitSets(posCoverTree, negCoverTree, activePath);

    return posCoverTree;
}

public boolean add(int[][] compressedRecords, OpenBitSet lhs, int recordId, int content) {
    int firstLhsAttr = lhs.nextSetBit(0);
    int firstCluster = compressedRecords[recordId][firstLhsAttr];
    if (firstCluster < 0)
        return true;

    ClusterTreeElement child = this.children.get(firstCluster);
    if (child == null) {
        child = new ClusterTreeElement(compressedRecords, lhs, lhs.nextSetBit(firstLhsAttr + 1), recordId, content);
        this.children.put(firstCluster, child);
        return true;
    }

    return child.add(compressedRecords, lhs, lhs.nextSetBit(firstLhsAttr + 1), recordId, content);
}

public boolean getGeneralizationAndDelete(OpenBitSet lhs, int a, int currentAttr, OpenBitSet specLhs) {
    boolean found = false;
    int nextSetAttr;
    if (this.isfd[a - 1]) {
        this.isfd[a - 1] = false;
        this.rhsAttributes.clear(a);
        return true;
    }
    nextSetAttr = lhs.nextSetBit(currentAttr + 1);
    if (nextSetAttr < 0) {
        return false;
    }

    if (this.children[nextSetAttr - 1] != null) {
        if (this.children[nextSetAttr - 1].getRhsAttributes().get(a)) {
            found = this.children[nextSetAttr - 1].getGeneralizationAndDelete(lhs, a, nextSetAttr, specLhs);
            if (found) {
                if (this.isFinalNode(a)) {
                    this.rhsAttributes.clear(a);
                }
                specLhs.set(nextSetAttr);
            }
        }
    }
    if (!found) {
        found = this.getGeneralizationAndDelete(lhs, a, nextSetAttr, specLhs);
    }

    return found;
}

protected int specializePositiveCover(OpenBitSet nonUCC, UCCList nonUCCs) {
    int numAttributes = this.posCover.getChildren().length;
    int newUCCs = 0;
    List<OpenBitSet> specUCCs;

    if (!(specUCCs = this.posCover.getUCCAndGeneralizations(nonUCC)).isEmpty()) { // TODO: May be "while" instead of "if"?
        for (OpenBitSet specUCC : specUCCs) {
            this.posCover.removeUniqueColumnCombination(specUCC);

            if ((this.posCover.getMaxDepth() > 0) && (specUCC.cardinality() >= this.posCover.getMaxDepth()))
                continue;

            for (int attr = numAttributes - 1; attr >= 0; attr--) {
                if (!nonUCC.get(attr)) {
                    specUCC.set(attr);
                    if (!this.posCover.containsUCCOrGeneralization(specUCC)) {
                        this.posCover.addUniqueColumnCombination(specUCC);
                        newUCCs++;  

                        // If dynamic memory management is enabled, frequently check the memory consumption and trim the positive cover if it does not fit anymore
                        this.memoryGuardian.memoryChanged(1);
                        this.memoryGuardian.match(this.negCover, this.posCover, nonUCCs);
                    }
                    specUCC.clear(attr);
                }
            }
        }
    }
    return newUCCs;
}

public boolean contains(OpenBitSet ucc) {
    int length = (int) ucc.cardinality();

    if ((this.maxDepth > 0) && (length > this.maxDepth))
        return false;

    return this.uccLevels.get(length).contains(ucc);
}

public void addFunctionalDependenciesInto(List<FunctionalDependency> functionalDependencies, OpenBitSet lhs, ObjectArrayList<ColumnIdentifier> columnIdentifiers, List<PositionListIndex> plis) {
    for (int rhs = this.rhsFds.nextSetBit(0); rhs >= 0; rhs = this.rhsFds.nextSetBit(rhs + 1)) {
        ColumnIdentifier[] columns = new ColumnIdentifier[(int) lhs.cardinality()];
        int j = 0;
        for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
            int columnId = plis.get(i).getAttribute(); // Here we translate the column i back to the real column i before the sorting
            columns[j++] = columnIdentifiers.get(columnId); 
        }

        ColumnCombination colCombination = new ColumnCombination(columns);
        int rhsId = plis.get(rhs).getAttribute(); // Here we translate the column rhs back to the real column rhs before the sorting
        FunctionalDependency fdResult = new FunctionalDependency(colCombination, columnIdentifiers.get(rhsId));
        functionalDependencies.add(fdResult);
    }

    if (this.getChildren() == null)
        return;

    for (int childAttr = 0; childAttr < this.numAttributes; childAttr++) {
        FDTreeElement element = this.getChildren()[childAttr];
        if (element != null) {
            lhs.set(childAttr);
            element.addFunctionalDependenciesInto(functionalDependencies, lhs, columnIdentifiers, plis);
            lhs.clear(childAttr);
        }
    }
}

/**
 * @return
 */
public void filterSpecializations() {
    OpenBitSet activePath = new OpenBitSet();
    FDTree filteredTree = new FDTree(maxAttributeNumber);
    this.filterSpecializations(filteredTree, activePath);

    this.children = filteredTree.children;
    this.isfd = filteredTree.isfd;

}

public void updatePositiveCover(FDList nonFds) {
/*      if (nonFds.isEmpty())
            return;

        // Sort the negative cover
        Logger.getInstance().writeln("Sorting FD-violations ...");
        Collections.sort(nonFds, new Comparator<OpenBitSet>() {
            @Override
            public int compare(OpenBitSet o1, OpenBitSet o2) {
                return (int)(o1.cardinality() - o2.cardinality());
            }
        });
*/      // THE SORTING IS NOT NEEDED AS THE UCCSet SORTS THE NONUCCS BY LEVEL ALREADY

        Logger.getInstance().writeln("Inducing FD candidates ...");
        for (int i = nonFds.getFdLevels().size() - 1; i >= 0; i--) {
            if (i >= nonFds.getFdLevels().size()) // If this level has been trimmed during iteration
                continue;

            List<OpenBitSet> nonFdLevel = nonFds.getFdLevels().get(i);
            for (OpenBitSet lhs : nonFdLevel) {

                OpenBitSet fullRhs = lhs.clone();
                fullRhs.flip(0, this.posCover.getNumAttributes());

                for (int rhs = fullRhs.nextSetBit(0); rhs >= 0; rhs = fullRhs.nextSetBit(rhs + 1))
                    this.specializePositiveCover(lhs, rhs, nonFds);
            }
            nonFdLevel.clear();
        }
    }

@Before
public void setUp() throws Exception {
    fdtree = new FDTree(5);
    OpenBitSet lhs = new OpenBitSet();
    lhs.set(1);
    lhs.set(2);
    lhs.set(4);
    fdtree.addFunctionalDependency(lhs, 3);
}

@Test
public void testContainsGeneralization() {
    OpenBitSet lhs = new OpenBitSet();
    lhs.set(1);
    lhs.set(2);
    assertFalse(fdtree.containsGeneralization(lhs, 3, 0));
    lhs.set(4);
    lhs.set(5);
    assertTrue(fdtree.containsGeneralization(lhs, 3, 0));
}

@Test
public void testFilterSpecialization() {
    OpenBitSet lhs = new OpenBitSet();
    lhs.set(1);
    lhs.set(4);
    fdtree.addFunctionalDependency(lhs, 3);

    fdtree.filterSpecializations();

    OpenBitSet expResult = new OpenBitSet();
    expResult.set(1);
    expResult.set(2);
    expResult.set(4);
    assertFalse(fdtree.containsGeneralization(lhs, 3, 0));
}

public boolean containsFunctionalDependency(OpenBitSet lhs, int rhs) {
    FDTreeElement currentNode = this;

    for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
        if ((currentNode.getChildren() == null) || (currentNode.getChildren()[i] == null))
            return false;

        currentNode = currentNode.getChildren()[i];
    }

    return currentNode.isFd(rhs);
}

/**
 * Build the prefix blocks for a level. It is a HashMap containing the
 * prefix as a key and the corresponding attributes as  the value.
 */
private void buildPrefixBlocks() {
    this.prefix_blocks.clear();
    for (OpenBitSet level_iter : level0.keySet()) {
        OpenBitSet prefix = getPrefix(level_iter);

        if (prefix_blocks.containsKey(prefix)) {
            prefix_blocks.get(prefix).add(level_iter);
        } else {
            ObjectArrayList<OpenBitSet> list = new ObjectArrayList<OpenBitSet>();
            list.add(level_iter);
            prefix_blocks.put(prefix, list);
        }
    }
}

/**
 * Add the functional dependency to the ResultReceiver.
 *
 * @param X: A OpenBitSet representing the Columns of the determinant.
 * @param a: The number of the dependent column (starting from 1).
 * @throws CouldNotReceiveResultException if the result receiver cannot handle the functional dependency.
 * @throws ColumnNameMismatchException 
 */
private void addDependencyToResultReceiver(OpenBitSet X, int a) throws CouldNotReceiveResultException, ColumnNameMismatchException {
    if (this.fdResultReceiver == null) {
        return;
    }
    ColumnIdentifier[] columns = new ColumnIdentifier[(int) X.cardinality()];
    int j = 0;
    for (int i = X.nextSetBit(0); i >= 0; i = X.nextSetBit(i + 1)) {
        columns[j++] = this.columnIdentifiers.get(i - 1);
    }
    ColumnCombination colCombination = new ColumnCombination(columns);
    FunctionalDependency fdResult = new FunctionalDependency(colCombination, columnIdentifiers.get((int) a - 1));
    this.fdResultReceiver.receiveResult(fdResult);
}