SparseBitmatrix_setdifference.cpp

Go to the documentation of this file.

#include "SparseBitmatrix_setdifference.hpp"
#include "common/debug.hpp"

int cardinalitySetdifferenceBySparseBitmatrix_TwoRows(SparseBitmatrix* bmIn, int maxdefect) {
  assert(bmIn->numRows == 2);
  // int row = 0;

  // 1. reset structure of bmOut.
  // int numRowsIn = 2;
  int** rowsIn = bmIn->rows;
  int* rowLengthsIn = bmIn->rowLengths;

  // 2. do the intersection:
  int* row1 = rowsIn[0];
  int len1 = rowLengthsIn[0];
  
  // int fromr = 1;
  int* row2 = rowsIn[1];
  int len2 = rowLengthsIn[1];

  if (len1 == 0)
    return len2;

  int posOut = 0;
  if (len2 > 0) { // something to do:
    int pos1 = 0, pos2 = 0;
    int item1 = row1[0], item2 = row2[0];
    
    // a. compute cardinality of set difference:
    while (true) {
      if (item1 < item2) {
        pos1++; 
        if (pos1 >= len1) break;
        item1 = row1[pos1];
      } else if (item1 > item2) {
        assert(posOut >= 0);
        assert(posOut < len2); 
        posOut++;
        if (posOut > maxdefect) break;
        
        pos2++; 
        if (pos2 >= len2) break;
        item2 = row2[pos2];
      } else { // if (item1 == item2) {
        pos2++; if (pos2 >= len2) break; // first check for pos2 as we add all remaining row2 items at the end !
        pos1++; if (pos1 >= len1) break;
        item1 = row1[pos1]; item2 = row2[pos2];
      }
    }
    // copy remaining items of row2:
    if (pos2 < len2) {
      posOut += (len2-pos2);
    }
  } else { // nothing to do: row2 is empty. // [was:] copy whole row as is.
    posOut = 0; // len1;
  }

  return posOut <= maxdefect ? posOut : maxdefect + 1;
}

---