<commit_before>// Copyright 2015, University of Freiburg,
// Chair of Algorithms and Data Structures.
// Author: <NAME> (<EMAIL>)

#include "./FTSAlgorithms.h"
#include <cmath>
#include <map>
#include <set>
#include <utility>
#include "../util/HashMap.h"
#include "../util/HashSet.h"

using std::pair;

// _____________________________________________________________________________
void FTSAlgorithms::filterByRange(const IdRange& idRange,
                                  const vector<Id>& blockCids,
                                  const vector<Id>& blockWids,
                                  const vector<Score>& blockScores,
                                  vector<Id>& resultCids,
                                  vector<Score>& resultScores) {
  AD_CHECK(blockCids.size() == blockWids.size());
  AD_CHECK(blockCids.size() == blockScores.size());
  LOG(DEBUG) << "Filtering " << blockCids.size()
             << " elements by ID range...\n";

  resultCids.resize(blockCids.size() + 2);
  resultScores.resize(blockCids.size() + 2);
  size_t nofResultElements = 0;

  for (size_t i = 0; i < blockWids.size(); ++i) {
    if (blockWids[i] >= idRange._first && blockWids[i] <= idRange._last) {
      resultCids[nofResultElements] = blockCids[i];
      resultScores[nofResultElements++] = blockScores[i];
    }
  }

  resultCids.resize(nofResultElements);
  resultScores.resize(nofResultElements);

  AD_CHECK(resultCids.size() == resultScores.size());
  LOG(DEBUG) << "Filtering by ID range done. Result has " << resultCids.size()
             << " elements.\n";
}

// _____________________________________________________________________________
void FTSAlgorithms::intersect(const vector<Id>& matchingContexts,
                              const vector<Id>& eBlockCids,
                              const vector<Id>& eBlockWids,
                              const vector<Score>& eBlockScores,
                              vector<Id>& resultCids, vector<Id>& resultEids,
                              vector<Score>& resultScores) {
  LOG(DEBUG) << "Intersection to filter the entity postings from a block "
             << "so that only matching ones remain\n";
  LOG(DEBUG) << "matchingContexts size: " << matchingContexts.size() << '\n';
  LOG(DEBUG) << "eBlockCids size: " << eBlockCids.size() << '\n';
  resultCids.reserve(eBlockCids.size() + 2);
  resultEids.reserve(eBlockCids.size() + 2);
  resultScores.reserve(eBlockCids.size() + 2);
  resultCids.resize(eBlockCids.size());
  resultEids.resize(eBlockCids.size());
  resultScores.resize(eBlockCids.size());
  // TODO(schnelle): This use of sentinels needs to go, it's not thread safe.
  // This is a BUG!!
  // Cast away constness so we can add sentinels that will be removed
  // in the end and create and add those sentinels.
  // Note: this is only efficient if capacity + 2 >= size for the input
  // context lists. For now, we assume that all lists are read from disk
  // where they had more than enough size allocated.
  auto& l1 = const_cast<vector<Id>&>(matchingContexts);
  auto& l2 = const_cast<vector<Id>&>(eBlockCids);
  // The two below are needed for the final sentinel match
  auto& wids = const_cast<vector<Id>&>(eBlockWids);
  auto& scores = const_cast<vector<Score>&>(eBlockScores);

  Id sent1 = std::numeric_limits<Id>::max();
  Id sent2 = std::numeric_limits<Id>::max() - 1;
  Id sentMatch = std::numeric_limits<Id>::max() - 2;

  l1.push_back(sentMatch);
  l2.push_back(sentMatch);
  l1.push_back(sent1);
  l2.push_back(sent2);
  wids.push_back(0);
  scores.push_back(0);

  size_t i = 0;
  size_t j = 0;
  size_t n = 0;

  while (l1[i] < sent1) {
    while (l1[i] < l2[j]) {
      ++i;
    }
    while (l2[j] < l1[i]) {
      ++j;
    }
    while (l1[i] == l2[j]) {
      // Make sure we get all matching elements from the entity list (l2)
      // that match the current context.
      // If there are multiple elements for that context in l1,
      // we can safely skip them unless we want to incorporate the scores
      // later on.
      resultCids[n] = l2[j];
      resultEids[n] = wids[j];
      resultScores[n++] = scores[j++];
    }
    ++i;
  }

  // Remove sentinels
  l1.resize(l1.size() - 2);
  l2.resize(l2.size() - 2);
  wids.resize(wids.size() - 1);
  scores.resize(scores.size() - 1);
  resultCids.resize(n - 1);
  resultEids.resize(n - 1);
  resultScores.resize(n - 1);
  LOG(DEBUG) << "Intersection done. Size: " << resultCids.size() << "\n";
}

// _____________________________________________________________________________
void FTSAlgorithms::intersectTwoPostingLists(const vector<Id>& cids1,
                                             const vector<Score>& scores1,
                                             const vector<Id>& cids2,
                                             const vector<Score>& scores2,
                                             vector<Id>& resultCids,
                                             vector<Score>& resultScores) {
  LOG(DEBUG) << "Intersection of words lists of sizes " << cids1.size()
             << " and " << cids2.size() << '\n';
  resultCids.reserve(cids1.size() + 2);
  resultScores.reserve(cids1.size() + 2);
  resultCids.resize(cids1.size());
  resultScores.resize(cids1.size());
  // TODO(schnelle): This use of sentinels needs to go, it's not thread safe.
  // This is a BUG!!
  // Cast away constness so we can add sentinels that will be removed
  // in the end and create and add those sentinels.
  // Note: this is only efficient if capacity + 2 >= size for the input
  // context lists. For now, we assume that all lists are read from disk
  // where they had more than enough size allocated.
  auto& l1 = const_cast<vector<Id>&>(cids1);
  auto& l2 = const_cast<vector<Id>&>(cids2);
  // The two below are needed for the final sentinel match
  auto& s1 = const_cast<vector<Score>&>(scores1);
  auto& s2 = const_cast<vector<Score>&>(scores2);

  Id sent1 = std::numeric_limits<Id>::max();
  Id sent2 = std::numeric_limits<Id>::max() - 1;
  Id sentMatch = std::numeric_limits<Id>::max() - 2;

  l1.push_back(sentMatch);
  l2.push_back(sentMatch);
  l1.push_back(sent1);
  l2.push_back(sent2);
  s1.push_back(0);
  s2.push_back(0);

  size_t i = 0;
  size_t j = 0;
  size_t n = 0;

  while (l1[i] < sent1) {
    while (l1[i] < l2[j]) {
      ++i;
    }
    while (l2[j] < l1[i]) {
      ++j;
    }
    while (l1[i] == l2[j]) {
      resultCids[n] = l2[j];
      resultScores[n++] = s1[i] + s2[j];
      ++i;
      ++j;
    }
  }

  // Remove sentinels
  l1.resize(l1.size() - 2);
  l2.resize(l2.size() - 2);
  s1.resize(s1.size() - 1);
  s2.resize(s2.size() - 1);
  resultCids.resize(n - 1);
  resultScores.resize(n - 1);

  LOG(DEBUG) << "Intersection done. Size: " << resultCids.size() << "\n";
}

// _____________________________________________________________________________
void FTSAlgorithms::intersectKWay(const vector<vector<Id>>& cidVecs,
                                  const vector<vector<Score>>& scoreVecs,<commit_msg>Remove sentinels in FTSAlgorithms intersects<commit_after>// Copyright 2015, University of Freiburg,
// Chair of Algorithms and Data Structures.
// Author: <NAME> (<EMAIL>)

#include "./FTSAlgorithms.h"
#include <cmath>
#include <map>
#include <set>
#include <utility>
#include "../util/HashMap.h"
#include "../util/HashSet.h"

using std::pair;

// _____________________________________________________________________________
void FTSAlgorithms::filterByRange(const IdRange& idRange,
                                  const vector<Id>& blockCids,
                                  const vector<Id>& blockWids,
                                  const vector<Score>& blockScores,
                                  vector<Id>& resultCids,
                                  vector<Score>& resultScores) {
  AD_CHECK(blockCids.size() == blockWids.size());
  AD_CHECK(blockCids.size() == blockScores.size());
  LOG(DEBUG) << "Filtering " << blockCids.size()
             << " elements by ID range...\n";

  resultCids.resize(blockCids.size() + 2);
  resultScores.resize(blockCids.size() + 2);
  size_t nofResultElements = 0;

  for (size_t i = 0; i < blockWids.size(); ++i) {
    if (blockWids[i] >= idRange._first && blockWids[i] <= idRange._last) {
      resultCids[nofResultElements] = blockCids[i];
      resultScores[nofResultElements++] = blockScores[i];
    }
  }

  resultCids.resize(nofResultElements);
  resultScores.resize(nofResultElements);

  AD_CHECK(resultCids.size() == resultScores.size());
  LOG(DEBUG) << "Filtering by ID range done. Result has " << resultCids.size()
             << " elements.\n";
}

// _____________________________________________________________________________
void FTSAlgorithms::intersect(const vector<Id>& matchingContexts,
                              const vector<Id>& eBlockCids,
                              const vector<Id>& eBlockWids,
                              const vector<Score>& eBlockScores,
                              vector<Id>& resultCids, vector<Id>& resultEids,
                              vector<Score>& resultScores) {
  LOG(DEBUG) << "Intersection to filter the entity postings from a block "
             << "so that only matching ones remain\n";
  LOG(DEBUG) << "matchingContexts size: " << matchingContexts.size() << '\n';
  LOG(DEBUG) << "eBlockCids size: " << eBlockCids.size() << '\n';
  // Handle trivial empty case
  if (matchingContexts.empty() || eBlockCids.empty()) {
    return;
  }
  resultCids.reserve(eBlockCids.size());
  resultCids.clear();
  resultEids.reserve(eBlockCids.size());
  resultEids.clear();
  resultScores.reserve(eBlockCids.size());
  resultScores.clear();

  size_t i = 0;
  size_t j = 0;

  while (i < matchingContexts.size() && j < eBlockCids.size()) {
    while (matchingContexts[i] < eBlockCids[j]) {
      ++i;
      if (i >= matchingContexts.size()) {
        return;
      }
    }
    while (eBlockCids[j] < matchingContexts[i]) {
      ++j;
      if (j >= eBlockCids.size()) {
        return;
      }
    }
    while (matchingContexts[i] == eBlockCids[j]) {
      // Make sure we get all matching elements from the entity list (l2)
      // that match the current context.
      // If there are multiple elements for that context in l1,
      // we can safely skip them unless we want to incorporate the scores
      // later on.
      resultCids.push_back(matchingContexts[j]);
      resultEids.push_back(eBlockWids[j]);
      resultScores.push_back(eBlockScores[j]);
      j++;
      if (j >= eBlockCids.size()) {
        break;
      }
    }
    ++i;
  }
}

// _____________________________________________________________________________
void FTSAlgorithms::intersectTwoPostingLists(const vector<Id>& cids1,
                                             const vector<Score>& scores1,
                                             const vector<Id>& cids2,
                                             const vector<Score>& scores2,
                                             vector<Id>& resultCids,
                                             vector<Score>& resultScores) {
  LOG(DEBUG) << "Intersection of words lists of sizes " << cids1.size()
             << " and " << cids2.size() << '\n';
  // Handle trivial empty case
  if (cids1.empty() || cids2.empty()) {
    return;
  }
  // TODO(schnelle): Need clear because a test reuses the result
  // vectors. we should probably just specify that it appends
  resultCids.reserve(cids1.size());
  resultCids.clear();
  resultScores.reserve(cids1.size());
  resultScores.clear();

  size_t i = 0;
  size_t j = 0;

  while (i < cids1.size() && j < cids2.size()) {
    while (cids1[i] < cids2[j]) {
      ++i;
      if (i >= cids1.size()) {
        return;
      }
    }
    while (cids2[j] < cids1[i]) {
      ++j;
      if (j >= cids2.size()) {
        return;
      }
    }
    while (cids1[i] == cids2[j]) {
      resultCids.push_back(cids2[j]);
      resultScores.push_back(scores1[i] + scores2[j]);
      ++i;
      ++j;
      if (i >= cids1.size() || j >= cids2.size()) {
        break;
      }
    }
  }
}

// _____________________________________________________________________________
void FTSAlgorithms::intersectKWay(const vector<vector<Id>>& cidVecs,
                                  const vector<vector<Score>>& scoreVecs,
{'fraction_non_alphanumeric': 0.1388302193338749, 'fraction_numerical': 0.012428919577579203, 'mean_word_length': 2.4737584650112865, 'pattern_counts': {'":': 0, '<': 187, '<?xml version=': 0, '>': 92, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3598521', 'n_tokens_mistral': 3988, 'n_tokens_neox': 3842, 'n_words': 896}