<commit_before>#ifndef HELIUM_SIMILARITY_H
#define HELIUM_SIMILARITY_H

#include "fingerprints.h"

#include <numeric>

namespace Helium {

  /**
   * @brief Brute force similarity search.
   *
   * This function computes the tanimoto coefficient between the query and
   * all fingerprints in the fingerprint sotrage. If the tanimoto is above the
   * specified threshold, it is added to the list of results.
   *
   * @param query The query fingerprint.
   * @param storage The fingerprints to search.
   * @param Tmin The minimum tanimoto score, must be in the range [0,1].
   * @param k When non-zero, this limits the number of requested results.
   */
  template<typename RowMajorFingerprintStorageType>
  std::vector<std::pair<unsigned int, double> > brute_force_similarity_search(const Word *query,
      RowMajorFingerprintStorageType &storage, double Tmin, unsigned int k = 0)
  {
    TIMER("brute_force_fimilarity_search():");
    int numWords = bitvec_num_words_for_bits(storage.numBits());

    std::vector<std::pair<unsigned int, double> > result;
    for (unsigned int i = 0; i < storage.numFingerprints(); ++i) {
      const Word *fingerprint = storage.fingerprint(i);
      double T = bitvec_tanimoto(query, fingerprint, numWords);
      if (T >= Tmin)
        result.push_back(std::make_pair(i, T));
    }

    return result;
  }

  /**
   * @brief Similarity search fingerpint index.
   *
   */
  template<typename FingerprintStorageType>
  class SimilaritySearchIndex
  {
      /**
       * Base class for tree nodes in the kD-grid.
       */
      struct Node
      {
      };

      /**
       * An intermediate tree node in the kD-grid.
       */
      struct TreeNode : public Node
      {
        /**
         * Constructor.
         *
         * @param size The number of children.
         */
        TreeNode(int size)
        {
          children.resize(size, 0);
        }

        std::vector<Node*> children; //!< Child nodes
      };

      /**
       * Leaf node for tree in the kD-grid.
       */
      struct LeafNode : public Node
      {
        std::vector<unsigned int> fingerprints; //!< The fingerprint indices
      };

      /**
       * Get the bit count for the portion of the fingerprint at a certain
       * depth.
       */
      int bitCount(const Word *fingerprint, int depth) const
      {
        int beginBit = depth * (m_numBits / m_k);
        int endBit = (depth + 1) * (m_numBits / m_k);
        
        if (depth == m_k - 1)
          endBit = (depth + 1) * (m_numBits / m_k) + (m_numBits % ((depth + 1) * (m_numBits / m_k)));

        /*
        int bitCount = 0;
        for (int i = beginBit; i < endBit; ++i)
          if (bitvec_get(i, fingerprint))
            ++bitCount;

        return bitCount;
        */

        return bitvec_count(fingerprint, bitvec_num_words_for_bits(m_numBits), beginBit, endBit);
      }

      int childSize() const
      {
        return m_numBits / m_k + 1;
      }

      std::vector<unsigned int>& findLeaf(const Word *fingerprint)
      {
        int depth = 0;
        TreeNode *node = m_tree;

        while (depth < m_k) {
          int count = bitCount(fingerprint, depth);<commit_msg>similarity.h: Use new range bitcount function<commit_after>#ifndef HELIUM_SIMILARITY_H
#define HELIUM_SIMILARITY_H

#include "fingerprints.h"

#include <numeric>

namespace Helium {

  /**
   * @brief Brute force similarity search.
   *
   * This function computes the tanimoto coefficient between the query and
   * all fingerprints in the fingerprint sotrage. If the tanimoto is above the
   * specified threshold, it is added to the list of results.
   *
   * @param query The query fingerprint.
   * @param storage The fingerprints to search.
   * @param Tmin The minimum tanimoto score, must be in the range [0,1].
   * @param k When non-zero, this limits the number of requested results.
   */
  template<typename RowMajorFingerprintStorageType>
  std::vector<std::pair<unsigned int, double> > brute_force_similarity_search(const Word *query,
      RowMajorFingerprintStorageType &storage, double Tmin, unsigned int k = 0)
  {
    TIMER("brute_force_fimilarity_search():");
    int numWords = bitvec_num_words_for_bits(storage.numBits());

    std::vector<std::pair<unsigned int, double> > result;
    for (unsigned int i = 0; i < storage.numFingerprints(); ++i) {
      const Word *fingerprint = storage.fingerprint(i);
      double T = bitvec_tanimoto(query, fingerprint, numWords);
      if (T >= Tmin)
        result.push_back(std::make_pair(i, T));
    }

    return result;
  }

  /**
   * @brief Similarity search fingerpint index.
   *
   */
  template<typename FingerprintStorageType>
  class SimilaritySearchIndex
  {
      /**
       * Base class for tree nodes in the kD-grid.
       */
      struct Node
      {
      };

      /**
       * An intermediate tree node in the kD-grid.
       */
      struct TreeNode : public Node
      {
        /**
         * Constructor.
         *
         * @param size The number of children.
         */
        TreeNode(int size)
        {
          children.resize(size, 0);
        }

        std::vector<Node*> children; //!< Child nodes
      };

      /**
       * Leaf node for tree in the kD-grid.
       */
      struct LeafNode : public Node
      {
        std::vector<unsigned int> fingerprints; //!< The fingerprint indices
      };

      /**
       * Get the bit count for the portion of the fingerprint at a certain
       * depth.
       */
      int bitCount(const Word *fingerprint, int depth) const
      {
        int beginBit = depth * (m_numBits / m_k);
        int endBit = (depth + 1) * (m_numBits / m_k);
        
        if (depth == m_k - 1)
          endBit = (depth + 1) * (m_numBits / m_k) + (m_numBits % ((depth + 1) * (m_numBits / m_k)));

        return bitvec_count(fingerprint, beginBit, endBit);
      }

      int childSize() const
      {
        return m_numBits / m_k + 1;
      }

      std::vector<unsigned int>& findLeaf(const Word *fingerprint)
      {
        int depth = 0;
        TreeNode *node = m_tree;

        while (depth < m_k) {
          int count = bitCount(fingerprint, depth);
{'fraction_non_alphanumeric': 0.10448002587740579, 'fraction_numerical': 0.0037198770823224972, 'mean_word_length': 2.2258737610850288, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1727913', 'n_tokens_mistral': 1973, 'n_tokens_neox': 1865, 'n_words': 553}