ordered_lists_merger.h

Go to the documentation of this file.

// Copyright 2012 Yandex Artem Babenko
#pragma once

#include "data_util.h"
#include "multitable.hpp"

typedef vector<int> MergedItemIndices;

template<class OrderType, class MetaInfo>
class OrderedListsMerger {
 public:
  OrderedListsMerger();
  void setLists(const vector<vector<pair<OrderType, MetaInfo> > >& lists);
  inline bool GetNextMergedItemIndices(MergedItemIndices* merged_item_indices);
  const vector<vector<pair<OrderType, MetaInfo> > >* lists_ptr;
  Multitable<char>& GetYieldedItems() {
    return yielded_items_indices_;
  }
 private:
  void InsertMergedItemIndicesInHeap(const MergedItemIndices& merged_item_indices);
  void UpdatePrioirityQueue(MergedItemIndices& merged_item_indices);
  multimap<OrderType, MergedItemIndices> heap_;
  Multitable<char> yielded_items_indices_;
};


template<class OrderType, class MetaInfo>
OrderedListsMerger<OrderType, MetaInfo>::OrderedListsMerger() {
}

template<class OrderType, class MetaInfo>
void OrderedListsMerger<OrderType, MetaInfo>::InsertMergedItemIndicesInHeap(const MergedItemIndices& merged_item_indices) {
  OrderType sum = 0;
  for(int list_index = 0; list_index < lists_ptr->size(); ++list_index) {
    sum += lists_ptr->at(list_index)[merged_item_indices[list_index]].first;
  }
  heap_.insert(std::make_pair(sum, merged_item_indices));
}

template<class OrderType, class MetaInfo>
void OrderedListsMerger<OrderType, MetaInfo>::setLists(const vector<vector<pair<OrderType, MetaInfo> > >& lists) {
  lists_ptr = &lists;
  heap_.clear();
  MergedItemIndices first_item_indices(lists.size());
  for(int list_index = 0; list_index < lists.size(); ++list_index) {
    first_item_indices[list_index] = 0;
  }
  memset(&(yielded_items_indices_.table[0]), 0, yielded_items_indices_.table.size());
  InsertMergedItemIndicesInHeap(first_item_indices);
}

template<class OrderType, class MetaInfo>
void OrderedListsMerger<OrderType, MetaInfo>::UpdatePrioirityQueue(MergedItemIndices& merged_item_indices) {
  for(int list_index = 0; list_index < lists_ptr->size(); ++list_index) {
    if(merged_item_indices[list_index] >= lists_ptr->at(list_index).size()) {
      return;
    }
    int current_index = merged_item_indices[list_index];
    merged_item_indices[list_index] -= 1;
    if(current_index > 0 && !yielded_items_indices_.GetValue(merged_item_indices)) {
      merged_item_indices[list_index] += 1;
      return;
    } else {
      merged_item_indices[list_index] += 1;
    }
  }
  InsertMergedItemIndicesInHeap(merged_item_indices);
}

template<class OrderType, class MetaInfo>
inline bool OrderedListsMerger<OrderType, MetaInfo>::GetNextMergedItemIndices(MergedItemIndices* next_merged_item_indices) {
  if(heap_.empty()) {
    return false;
  }
  *next_merged_item_indices = heap_.begin()->second;
  yielded_items_indices_.SetValue(1, *next_merged_item_indices);
  for(int list_index = 0; list_index < lists_ptr->size(); ++list_index) {
    next_merged_item_indices->at(list_index) += 1;
    UpdatePrioirityQueue(*next_merged_item_indices);
    next_merged_item_indices->at(list_index) -= 1;
  }
  heap_.erase(heap_.begin());
  return true;
}

template class OrderedListsMerger<Distance, PointId>;
template class OrderedListsMerger<Distance, pair<ClusterId, ClusterId> >;