text: // Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
  
  #include "posting_list_merger.h"
  #include <algorithm>
  
  namespace search::attribute {
  
  template <typename DataT>
  PostingListMerger<DataT>::PostingListMerger(uint32_t docIdLimit)
      : _array(),
        _startPos(),
        _bitVector(),
        _docIdLimit(docIdLimit),
        _arrayValid(false)
  {
  }
  
  template <typename DataT>
  PostingListMerger<DataT>::~PostingListMerger() = default;
  
  template <typename DataT>
  void
  PostingListMerger<DataT>::reserveArray(uint32_t postingsCount, size_t postingsSize)
  {
      _array.reserve(postingsSize);
      _startPos.reserve(postingsCount + 1);
      _startPos.push_back(0);
  }
  
  
  template <typename DataT>
  void
  PostingListMerger<DataT>::allocBitVector()
  {
      _bitVector = BitVector::create(_docIdLimit);
  }
  
  template <typename DataT>
  void
  PostingListMerger<DataT>::merge()
  {
      if (_bitVector) {
          _bitVector->invalidateCachedCount();
      } else {
          if (_startPos.size() > 2) {
              PostingVector temp(_array.size());
              _array.swap(merge(_array, temp, _startPos));
          }
          StartVector().swap(_startPos);
          _arrayValid = true;
      }
  }
  
  
  template <typename DataT>
  typename PostingListMerger<DataT>::PostingVector &
  PostingListMerger<DataT>::merge(PostingVector &v, PostingVector &temp, const StartVector &startPos)
  {
      StartVector nextStartPos;
      nextStartPos.reserve((startPos.size() + 1) / 2);
      nextStartPos.push_back(0);
      for (size_t i(0), m((startPos.size() - 1) / 2); i < m; i++) {
          size_t aStart = startPos[i * 2 + 0];
          size_t aEnd = startPos[i * 2 + 1];
          size_t bStart = aEnd;
          size_t bEnd = startPos[i * 2 + 2];
          typename PostingVector::const_iterator it = v.begin();
          std::merge(it + aStart, it + aEnd,
                     it + bStart, it + bEnd,
                     temp.begin() + aStart);
          nextStartPos.push_back(bEnd);
      }
      if ((startPos.size() - 1) % 2) {
          for (size_t i(startPos[startPos.size() - 2]), m(v.size()); i < m; i++) {
              temp[i] = v[i];
          }
          nextStartPos.push_back(temp.size());
      }
      return (nextStartPos.size() > 2) ? merge(temp, v, nextStartPos) : temp;
  }
  
  
  template class PostingListMerger<vespalib::btree::BTreeNoLeafData>;
  template class PostingListMerger<int32_t>;
  
  }
  