Traduction d'algorithmes Common Lisp en C++

defun ph-and-p (ln mask)
  (loop for i in ln
        for hv = (logand i mask) do
    (if (eql (aref *ht* hv) mask) ;; ht est un tableau global de taille suffisante pour l'algorithme
        (return nil)
      (setf (aref *ht* hv) mask))
    finally return t))

defun ph-and (ln) ;; LN is an integer list
  (if (null (cdr ln))
    1
  (let ((mask (logxor (apply #’logior ln) (apply #’logand ln)))) ;; MASK consists of all discriminant bits
    (fill *ht* nil :start 0 :end (1+ mask)) ;; resets *HT*
    (loop for b from (highest-bit mask) by 1 downto 0
      when (logbitp b mask) do ;; for each 1-bit in MASK
      (let ((new (logxor mask (ash 1 b)))) ;; NEW = MASK with switched bit
        (when (ph-and-p ln new) (setf mask new)))
      finally return (1+ mask)))))

bool ph_and_p(std::vector<std::size_t> const& ln, std::size_t mask)
{
        std::vector<bool> seen(mask + 1, false); // Le ht de la version Lisp, j'ai choisi d'utiliser une variable locale
        for (auto i : ln)
        {
                std::size_t hv{i & mask};
                if (seen[hv])
                        return false;

                seen[hv] = true;
        }

        return true;
}

std::size_t ph_and(std::vector<std::size_t> const& ln)
{
    if (ln.size() == 1)
        return 1;

    std::size_t acc_or{ln[0]};
    std::size_t acc_and{ln[0]};

    for (auto it = std::begin(ln) + 1 ; it < std::end(ln) ; ++it)
    {
        acc_or |= *it;
        acc_and &= *it;
    }

    std::size_t mask{acc_or ^ acc_and};

    for (int b{__builtin_ffsl(mask) - 1} ; b >= 0 ; --b)
    {
        if ((mask & (1 << b)) != 0)
        {
            std::size_t new_mask{mask ^ (1 << b)};
            if (ph_and_p(ln, new_mask))
                mask = new_mask;
        }
    }

    return mask + 1;
}

defun compute-least-free-ids-and (n mask)
  (loop for i in *free* until (= n 0) ;; free est un tableau global
        for hv =  (logand i mask)
        unless (eql (aref *ht* hv) mask)
        collect (progn (setf (aref *ht* hv) mask)
                       (decf n)
                       i)))

defun pn-and (ln n)
  (let ((mask (1- (ph-and ln))))
    (loop for b from 0 by 1
          while (> (+ (length ln) n) (ash 1 (logcount mask))) ;; when there are not enough 1-bits
          unless (logbitp b mask) ;; rightmost 0-bit
          do (setf mask (logxor mask (ash 1 b)))) ;; switch
    (ph-and-p ln mask) ;; resets *HT*
    (values (compute-least-free-ids-and n mask) (1+ mask))))

std::vector<std::size_t> free_values;

std::vector<std::size_t> compute_least_free_ids_and(std::size_t n, std::size_t mask)
{
    std::vector<std::size_t> ids{};
    std::vector<bool> seen(mask + 1, false);
    for (std::size_t i : free_values)
    {
        if (n == 0)
            break;

        std::size_t hv{i & mask};
        if (seen[hv])
            continue;

        seen[hv] = true;
        ids.push_back(i);
        --n;
    }

    return ids;
}

std::pair<std::vector<std::size_t>, std::size_t> pn_and(std::vector<std::size_t> const& ln, std::size_t n)
{
    std::size_t mask{ph_and(ln) - 1};
    for (size_t b{0} ; (ln.size() + n) > (1 << __builtin_popcount(mask)) ; ++b)
    {
        if ((mask & (1 << b)) == 0)
            mask ^= 1 << b;
    }

    return std::make_pair(compute_least_free_ids_and(n, mask), mask + 1);
}