Decision-diagram style recursive implementation in POLYBORI

The C++ implementation of the functionality in POLYBORI is given in this section, which is recursive and uses caching techniques.

// determine the part of a polynomials of a given degree
template <class CacheType, class NaviType, class DegType, class SetType>
SetType
dd_graded_part(const CacheType& cache, NaviType navi, DegType deg,  
               SetType init) {


  if (deg == 0) {
    while(!navi.isConstant())
      navi.incrementElse();
    return SetType(navi);
  }

  if(navi.isConstant())
    return SetType();

  // Look whether result was cached before
  NaviType cached = cache.find(navi, deg);

  if (cached.isValid())
    return SetType(cached);

  SetType result = 
    SetType(*navi,  
            dd_graded_part(cache, navi.thenBranch(), deg - 1, init),
            dd_graded_part(cache, navi.elseBranch(), deg, init)
            );

  // store result for later reuse
  cache.insert(navi, deg, result.navigation());

  return result;
}

The encoding of integers for the degree as variable is done implicitely by our cache lookup functions.