SparseBitmatrix_intersection.hpp

Go to the documentation of this file.

#ifndef __SPARSEBITMATRIX_INTERSECTION_HPP_
#define __SPARSEBITMATRIX_INTERSECTION_HPP_ t

#include "SparseBitvector_intersection.hpp"
// #include "SparseBitmatrix.hpp"
//#include "SparseBitmatrix_singleblock.hpp"
#include "common/debug.hpp"
#include <vector>

template <bool EARLY_FILTERING, bool INTERSECTION_ROWSWAPPING, bool REMOVE_IDENTICAL_ROWS, class OutputIterator>
int intersectSparseBitmatrix(const SparseBitmatrix& bmIn, const int row, SparseBitmatrix& bmOut, 
                             const int minimalLength, OutputIterator identicalRowsIterator) {
  assert(row >= 0 && row < bmIn.nRows());

  // 1. setup loop
  int tor = 0;
  int maxRowLength = 0;
  bmOut.setNRows(bmIn.nRows() - row - 1);
  const GET_ROW(row1, bmIn, row); // legacy: const SparseBitvector row1(bmIn.getRow(row));

  // 2. iterate over all other rows, i.e. otherrow > row.
  for (int otherRow = row+1; otherRow < bmIn.nRows(); otherRow++) {
    const GET_ROW(row2, bmIn, otherRow); // legacy: const SparseBitvector row2(bmIn.getRow(otherrow));
    GET_ROW(rowOut, bmOut, tor);         // legacy: SparseBitvector rowOut(bmOut.getRow(tor));

    bool hasMinimalLength = INTERSECTION_ROWSWAPPING && row1.length() < row2.length()
      ? intersection<EARLY_FILTERING>(rowOut, row2, row1, minimalLength)
      : intersection<EARLY_FILTERING>(rowOut, row1, row2, minimalLength);

    // intersect and only do anything if output row has at least minimalLength elements.
    if (hasMinimalLength) {
      if (REMOVE_IDENTICAL_ROWS && rowOut.length() == row1.length())
        // a. identical row: skip, but output to identicalRowsIterator.
        *identicalRowsIterator++ = bmIn.rowLabel(otherRow); 
      else {
        // b. retain row:
        // bmOut.setRowLength(tor, rowOut.length());
        bmOut.setRowLabel(tor, bmIn.rowLabel(otherRow));
        if (rowOut.length() > maxRowLength)
          maxRowLength = rowOut.length();
        tor++;
      }
    }
  }

  // 3. remember matrix structure.
  bmOut.setNRows(tor);
  bmOut.setMaxRowLength(maxRowLength);

  return tor;
}


template <bool EARLY_FILTERING, bool INTERSECTION_ROWSWAPPING, bool REMOVE_IDENTICAL_ROWS, class OutputIterator>
int intersectSparseBitmatrix(const SparseBitmatrix& bmIn, const int row, const vector<int> otherRows, SparseBitmatrix& bmOut, 
                             const int minimalLength, OutputIterator identicalRowsIterator) {
  assert(row >= 0 && row < bmIn.nRows());

  // 1. setup loop
  int tor = 0;
  int maxRowLength = 0;
  bmOut.setNRows(otherRows.size());
  const GET_ROW(row1, bmIn, row);

  // 2. iterate over all other rows
  for (vector<int>::iterator iter = otherRows.begin(); iter != otherRows.end(); iter++ ) {
    int otherRow = *iter;
    const GET_ROW(row2, bmIn, otherRow);
    GET_ROW(rowOut, bmOut, tor);

    bool hasMinimalLength = INTERSECTION_ROWSWAPPING && row1.length() < row2.length()
      ? intersection<EARLY_FILTERING>(rowOut, row2, row1, minimalLength)
      : intersection<EARLY_FILTERING>(rowOut, row1, row2, minimalLength);

    // intersect and only do anything if output row has at least minimalLength elements.
    if (hasMinimalLength) {
      if (REMOVE_IDENTICAL_ROWS && rowOut.length() == row1.length())
        // a. identical row: skip, but output to identicalRowsIterator.
        *identicalRowsIterator++ = bmIn.rowLabel(otherRow); 
      else {
        // b. retain row:
        // bmOut.setRowLength(tor, rowOut.length());
        bmOut.setRowLabel(tor, bmIn.rowLabel(otherRow));
        if (rowOut.length() > maxRowLength)
          maxRowLength = rowOut.length();
        tor++;
      }
    }
  }

  // 3. remember matrix structure.
  bmOut.setNRows(tor);
  bmOut.setMaxRowLength(maxRowLength);

  return tor;
}


template <bool EARLY_FILTERING>
int cardinalityIntersectionSparseBitmatrix_TwoRows(const SparseBitmatrix& bmIn, const int minimalLength) {
  const GET_ROW(row0, bmIn, 0); // legacy: const SparseBitvector row0(bmIn.getRow(0));
  const GET_ROW(row1, bmIn, 1); // legacy: const SparseBitvector row1(bmIn.getRow(1));
  return cardinalityOfIntersection<EARLY_FILTERING>(row0, row1, minimalLength);
}


#endif

---