inline const bool ClauseCleaner::cleanClause(XorClause& c)
{
    Lit *i, *j, *end;
    Var origVar1 = c[0].var();
    Var origVar2 = c[1].var();
    uint32_t origSize = c.size();
    for (i = j = c.getData(), end = i + c.size();  i != end; i++) {
        const lbool& val = solver.assigns[i->var()];
        if (val.isUndef()) {
            *j = *i;
            j++;
        } else c.invert(val.getBool());
    }
    c.shrink(i-j);

    assert(c.size() != 1);
    switch (c.size()) {
        case 0: {
            solver.detachModifiedClause(origVar1, origVar2, origSize, &c);
            return true;
        }
        case 2: {
            c[0] = c[0].unsign();
            c[1] = c[1].unsign();
            solver.varReplacer->replace(c, c.xorEqualFalse(), c.getGroup());
            solver.detachModifiedClause(origVar1, origVar2, origSize, &c);
            return true;
        }
        default: {
            if (i-j > 0) {
                solver.clauses_literals -= i-j;
            }
            return false;
        }
    }

    assert(false);
    return false;
}

void XorFinder::addXorAsNormal3(XorClause& c)
{
    assert(c.size() == 3);
    Clause *tmp;
    vec<Var> vars;
    vec<Lit> vars2(c.size());
    const bool inverted = c.xor_clause_inverted();

    for (uint32_t i = 0; i < c.size(); i++) {
        vars.push(c[i].var());
    }

    vars2[0] = Lit(vars[0], false ^ inverted);
    vars2[1] = Lit(vars[1], false ^ inverted);
    vars2[2] = Lit(vars[2], false ^ inverted);
    tmp = solver.addClauseInt(vars2, c.getGroup());
    if (tmp) solver.clauses.push(tmp);

    vars2[0] = Lit(vars[0], true ^ inverted);
    vars2[1] = Lit(vars[1], true ^ inverted);
    vars2[2] = Lit(vars[2], false ^ inverted);
    tmp = solver.addClauseInt(vars2, c.getGroup());
    if (tmp) solver.clauses.push(tmp);

    vars2[0] = Lit(vars[0], true ^ inverted);
    vars2[1] = Lit(vars[1], false ^ inverted);
    vars2[2] = Lit(vars[2], true ^ inverted);
    tmp = solver.addClauseInt(vars2, c.getGroup());
    if (tmp) solver.clauses.push(tmp);

    vars2[0] = Lit(vars[0], false ^ inverted);
    vars2[1] = Lit(vars[1], true ^ inverted);
    vars2[2] = Lit(vars[2], true ^ inverted);
    tmp = solver.addClauseInt(vars2, c.getGroup());
    if (tmp) solver.clauses.push(tmp);
}

/**
@brief Helper function for replace_set()
*/
bool VarReplacer::handleUpdatedClause(XorClause& c, const Var origVar1, const Var origVar2)
{
    uint32_t origSize = c.size();
    std::sort(c.getData(), c.getDataEnd());
    Lit p;
    uint32_t i, j;
    for (i = j = 0, p = lit_Undef; i != c.size(); i++) {
        if (c[i].var() == p.var()) {
            //added, but easily removed
            j--;
            p = lit_Undef;
            if (!solver.assigns[c[i].var()].isUndef())
                c.invert(solver.assigns[c[i].var()].getBool());
        } else if (solver.assigns[c[i].var()].isUndef()) //just add
            c[j++] = p = c[i];
        else c.invert(solver.assigns[c[i].var()].getBool()); //modify xorEqualFalse instead of adding
    }
    c.shrink(i - j);

    //Even if i==j, the clause *has* changed
    c.setChanged();

    #ifdef VERBOSE_DEBUG
    cout << "xor-clause after replacing: ";
    c.plainPrint();
    #endif

    switch (c.size()) {
    case 0:
        solver.detachModifiedClause(origVar1, origVar2, origSize, &c);
        if (!c.xorEqualFalse()) {
            solver.ok = false;
        }
        return true;
    case 1:
        solver.detachModifiedClause(origVar1, origVar2, origSize, &c);
        solver.uncheckedEnqueue(Lit(c[0].var(), c.xorEqualFalse()));
        solver.ok = (solver.propagate<false>().isNULL());
        return true;
    case 2: {
        solver.detachModifiedClause(origVar1, origVar2, origSize, &c);
        c[0] = c[0].unsign() ^ c.xorEqualFalse();
        c[1] = c[1].unsign();
        addBinaryXorClause(c[0], c[1]);
        return true;
    }
    default:
        solver.detachModifiedClause(origVar1, origVar2, origSize, &c);
        solver.attachClause(c);
        return false;
    }

    assert(false);
    return false;
}

const bool XorSubsumer::removeDependent()
{
    for (Var var = 0; var < occur.size(); var++) {
        if (cannot_eliminate[var] || !solver.decision_var[var] || solver.assigns[var] != l_Undef) continue;
        vec<XorClauseSimp>& occ = occur[var];

        if (occ.size() == 1) {
#ifdef VERBOSE_DEBUG
            std::cout << "Eliminating dependent var " << var + 1 << std::endl;
            std::cout << "-> Removing dependent clause ";
            occ[0].clause->plainPrint();
#endif //VERBOSE_DEBUG
            unlinkClause(occ[0], var);
            solver.setDecisionVar(var, false);
            var_elimed[var] = true;
            numElimed++;
        } else if (occ.size() == 2) {
            vec<Lit> lits;
            XorClause& c1 = *(occ[0].clause);
            lits.growTo(c1.size());
            std::copy(c1.getData(), c1.getDataEnd(), lits.getData());
            bool inverted = c1.xorEqualFalse();

            XorClause& c2 = *(occ[1].clause);
            lits.growTo(lits.size() + c2.size());
            std::copy(c2.getData(), c2.getDataEnd(), lits.getData() + c1.size());
            inverted ^= !c2.xorEqualFalse();
            uint32_t group = c2.getGroup();
            uint32_t ret = removeAll(lits, var);
            release_assert(ret == 2);

#ifdef VERBOSE_DEBUG
            std::cout << "Eliminating var " << var + 1 << " present in 2 xor-clauses" << std::endl;
            std::cout << "-> Removing xor clause ";
            occ[0].clause->plainPrint();
            std::cout << "-> Removing xor clause ";
            occ[1].clause->plainPrint();
#endif //VERBOSE_DEBUG
            XorClauseSimp toUnlink0 = occ[0];
            XorClauseSimp toUnlink1 = occ[1];
            unlinkClause(toUnlink0);
            unlinkClause(toUnlink1, var);
            solver.setDecisionVar(var, false);
            var_elimed[var] = true;
            numElimed++;

            for (uint32_t i = 0; i < lits.size(); i++)
                cannot_eliminate[lits[i].var()] = true;
            XorClause* c = solver.addXorClauseInt(lits, inverted, group);
#ifdef VERBOSE_DEBUG
            if (c != NULL) {
                std::cout << "-> Added combined xor clause:";
                c->plainPrint();
            } else
                std::cout << "-> Combined xor clause is NULL" << std::endl;
#endif
            if (c != NULL) linkInClause(*c);
            if (!solver.ok) {
#ifdef VERBOSE_DEBUG
                std::cout << "solver.ok is false after var-elim through xor" << std::endl;
#endif //VERBOSE_DEBUG
                return false;
            }
        }
    }

    return true;
}

bool XorFinder::findXors(uint& sumLengths)
{
    #ifdef VERBOSE_DEBUG
    cout << "Finding Xors started" << endl;
    #endif

    sumLengths = 0;

    ClauseTable::iterator begin = table.begin();
    ClauseTable::iterator end = table.begin();
    vec<Lit> lits;
    bool impair;
    while (getNextXor(begin,  end, impair)) {
        const Clause& c = *(begin->first);
        lits.clear();
        for (const Lit *it = &c[0], *cend = it+c.size() ; it != cend; it++) {
            lits.push(Lit(it->var(), false));
        }
        uint old_group = c.getGroup();

        #ifdef VERBOSE_DEBUG
        cout << "- Found clauses:" << endl;
        #endif

        for (ClauseTable::iterator it = begin; it != end; it++)
            if (impairSigns(*it->first) == impair){
            #ifdef VERBOSE_DEBUG
            it->first->plainPrint();
            #endif
            toRemove[it->second] = true;
            solver.removeClause(*it->first);
        }

        switch(lits.size()) {
        case 2: {
            solver.varReplacer->replace(lits, impair, old_group);

            #ifdef VERBOSE_DEBUG
            XorClause* x = XorClause_new(lits, impair, old_group);
            cout << "- Final 2-long xor-clause: ";
            x->plainPrint();
            clauseFree(x);
            #endif
            break;
        }
        default: {
            XorClause* x = solver.clauseAllocator.XorClause_new(lits, impair, old_group);
            solver.xorclauses.push(x);
            solver.attachClause(*x);

            #ifdef VERBOSE_DEBUG
            cout << "- Final xor-clause: ";
            x->plainPrint();
            #endif
        }
        }

        foundXors++;
        sumLengths += lits.size();
    }

    return solver.ok;
}