SparseBitvector_setdifference.hpp

Go to the documentation of this file.

/*
 * SparseBitvector_setdifference.hpp
 *
 * Time-stamp: <05/05/14 21:39:44 lars>
 *
 */

#ifndef __SPARSE_BITVECTOR_SETDIFFERENCE__
#define __SPARSE_BITVECTOR_SETDIFFERENCE__ t

#include <iostream>
using namespace std;

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

template <bool EARLY_FILTERING>
inline 
bool setdifference(SparseBitvector& result, const SparseBitvector& x, const SparseBitvector& y,
                   const int maximalLength) {
  assert(x.length() > 0);
  assert(y.length() > 0);
  assert(&result != &x);
  assert(&result != &y);
  assert(!EARLY_FILTERING || maximalLength <= x.length());
  assert(result.capacity() >= maximalLength || result.capacity() >= x.length());

  // 1. initialize loop
  SparseBitvector::iterator maximalResult = result.beginUnbounded(), 
    iterResult = result.beginUnbounded();
  if (EARLY_FILTERING)
    maximalResult += maximalLength;

  SparseBitvector::const_iterator endx = x.end(), endy = y.end();

#ifndef BALAZS
  SparseBitvector::const_iterator iterx = x.begin(), itery = y.begin();
  int itemx = *iterx;
  int itemy = *itery;
  // 2. loop over all elements
  while (true) {
    if (itemx < itemy) {
      if (EARLY_FILTERING && iterResult >= maximalResult) { return false; }
      *iterResult++ = itemx; 
      ++iterx; if (iterx == endx) break;
      itemx = *iterx;
    } else if (itemx > itemy) {
      ++itery; if (itery == endy) break;
      itemy = *itery;
    } else { // if (itemx == itemy) {
      ++iterx; if (iterx == endx) break;
      ++itery; if (itery == endy) break;
      itemx = *iterx;
      itemy = *itery;
    }
  }
#else
  
  register SparseBitvector::const_iterator iterx = x.begin();
  register SparseBitvector::const_iterator itery = y.begin();
  register int itemx = *iterx;
  register int itemy = *itery;
  
  while (true) {
    if (itemx < itemy) {
      do {
        if (EARLY_FILTERING && iterResult >= maximalResult) { return false; }
        *iterResult++ = itemx; 
        ++iterx; if (iterx == endx) goto exit;
        itemx = *iterx;
      } while (itemx<itemy);
    } else {
      ++itery;
      asm("leal 4(%[xref]),%%eax \n"
          "cmpl %[yvalue],%[xvalue]\n"
          "cmove %%eax,%[xref] \n"
          "cmove (%%eax),%[xvalue] \n"
          : [xvalue]"+r" (itemx) ,[xref] "+r" (iterx) : [yvalue] "r" (itemy) : "eax");
      if (itery == endy) break;
      if (iterx == endx) break;
      itemy = *itery;
    }
  }
  exit:
#endif
  /*    *iterResult=itemx;
    if (EARLY_FILTERING && (itemx<itemy) && iterResult >= maximalResult) { return false; }
    iterResult+=(itemx<itemy);
    iterx+=(itemx<=itemy);
    if (iterx == endx) break;
    itery+=(itemy<=itemx);
    if (itery == endy) break;
    itemx=*iterx;
    itemy=*itery;
  */

  // 3. copy remaining items of x:
  for ( ; iterx != endx; ++iterx)
    *iterResult++ = *iterx;

  result.resizeToEndOf(iterResult);

  return result.length() <= maximalLength;
}


template <bool EARLY_FILTERING>
inline 
int cardinalityOfSetdifference(const SparseBitvector& x, const SparseBitvector& y, const int maximalLength) {
  assert(x.length() > 0);
  assert(y.length() > 0);

  // 1. initialize loop
  int resultLength = 0;
  SparseBitvector::const_iterator endx = x.end(), endy = y.end();
  SparseBitvector::const_iterator iterx = x.begin(), itery = y.begin();
  int itemx = *iterx;
  int itemy = *itery;

  // 2. loop over all elements
  while (true) {
        if (itemx < itemy) {
      if (EARLY_FILTERING && resultLength >= maximalLength) { return maximalLength+1; }
      ++resultLength;
      ++iterx; if (iterx == endx) break;
      itemx = *iterx;
    } else if (itemx > itemy) {
      ++itery; if (itery == endy) break;
      itemy = *itery;
    } else { // if (itemx == itemy) {
      ++iterx; if (iterx == endx) break;
      ++itery; if (itery == endy) break;
      itemx = *iterx;
      itemy = *itery;
    }

    /*    if (EARLY_FILTERING && (itemx<itemy) && resultLength >= maximalLength) { return maximalLength+1; }
    resultLength+=(itemx<itemy);
    iterx+=(itemx<=itemy);
    if (iterx == endx) break;
    itery+=(itemy<=itemx);
    if (itery == endy) break;
    itemx=*iterx;
    itemy=*itery;*/

  }
  
  // 3. copy remaining items of x:
  resultLength += endx - iterx;

  return resultLength;
}

#endif

---