LightVector_set_intersection.hpp

Go to the documentation of this file.

#ifndef __LIGHT_VECTOR_SET_INTERSECTION__
#define __LIGHT_VECTOR_SET_INTERSECTION__ t

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

template <bool EARLY_FILTERING, class TYPE>
inline 
bool set_intersection(LightVector<TYPE>& result, const LightVector<TYPE>& x, const LightVector<TYPE>& y, const int minimalSize = 0) {
  assert(x.size() > 0); // 1. make sure inputs are not trivial.
  assert(y.size() > 0);
  assert(minimalSize <= x.size()); // otherwise outcome never can be true.
  assert(minimalSize <= y.size()); // otherwise outcome never can be true.
  assert(! EARLY_FILTERING || minimalSize >= 2); // otherwise EARLY_FILTERING is turned on in vain.

  assert(&result != &x); // 2. make sure output and inputs are not intermingled.
  assert(&result != &y);

  assert(result.capacity() >= minimalSize || result.capacity() >= x.size() || result.capacity() >= y.size()); // 3. make sure output capacity is sufficient. 
  assert(EARLY_FILTERING || result.capacity() >= x.size() || result.capacity() >= y.size());

  // It is a bad idea to perform rowswapping here as this prevents inlining. Now done in the caller.

  // 0. actually we almost only work on iterators: (but for resizeToEndOf we need the object)
  typename LightVector<TYPE>::const_iterator iterx = x.begin(), itery = y.begin(), endx = x.end(), endy = y.end();
  typename LightVector<TYPE>::iterator iterResult = result.beginUnbounded();

  // 1. setup stopping criteria.
  if (EARLY_FILTERING && minimalSize > 1) { // nothing can be gained from minimalSize 0 or 1. 
    endx -= minimalSize - 1; 
    endy -= minimalSize - 1;
  }

  // 2. initialize loop
  typename LightVector<TYPE>::iterator minimalResult = iterResult + minimalSize;
  int itemx = *iterx;
  int itemy = *itery;

  // 3. loop over all elements
  while (true) {
    if (itemx < itemy) { // miss in x
      ++iterx; if (iterx == endx) break;
      itemx = *iterx;
    } else if (itemx > itemy) { // miss in y
      ++itery; if (itery == endy) break;
      itemy = *itery;
    } else { // if (itemx == itemy) { // match
      *iterResult++ = itemx; 
      if (EARLY_FILTERING && iterResult < minimalResult) {
        ++endx;
        ++endy;
      } 
      ++iterx; if (iterx == endx) break;
      ++itery; if (itery == endy) break;
      itemx = *iterx; itemy = *itery;
    }
  }

  result.resizeToEndOf(iterResult);

  return result.size() >= minimalSize;
}

template <bool EARLY_FILTERING, class TYPE>
inline 
int cardinality_of_set_intersection(const LightVector<TYPE>& x, const LightVector<TYPE>& y, const int minimalSize = 0) {
  assert(x.size() > 0); // make sure inputs are not trivial.
  assert(y.size() > 0);
  assert(minimalSize <= x.size()); // otherwise outcome never can be true.
  assert(minimalSize <= y.size()); // otherwise outcome never can be true.
  assert(! EARLY_FILTERING || minimalSize >= 2); // otherwise EARLY_FILTERING is turned on in vain.

  // It is a bad idea to perform rowswapping here as this prevents inlining. Now done in the caller.

  // 0. actually we only work on iterators: 
  typename LightVector<TYPE>::const_iterator iterx = x.begin(), itery = y.begin(), endx = x.end(), endy = y.end();

  // 1. setup stopping criteria.
  if (EARLY_FILTERING && minimalSize > 1) { // nothing can be gained from minimalSize 0 or 1. 
    endx -= minimalSize - 1; 
    endy -= minimalSize - 1;
  }

  // 2. initialize loop
  int itemx = *iterx;
  int itemy = *itery;
  int resultSize = 0;

  // 3. loop over all elements
  while (true) {
    if (itemx < itemy) { // miss in x
      ++iterx; if (iterx == endx) break;
      itemx = *iterx;
    } else if (itemx > itemy) { // miss in y
      ++itery; if (itery == endy) break;
      itemy = *itery;
    } else { // if (itemx == itemy) { // match
      ++resultSize;
      if (EARLY_FILTERING && resultSize < minimalSize) {
        ++endx;
        ++endy;
      } 
      ++iterx; if (iterx == endx) break;
      ++itery; if (itery == endy) break;
      itemx = *iterx; itemy = *itery;
    }
  }

  if (resultSize < minimalSize) // due to early filtering resultSize might not be correct if it is < minimalSize; so set it to 0.
    resultSize = 0;

  return resultSize;
}


#endif

---