Line data    Source code

       1             : /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
       2             :    Copyright (c) 2011-2023 The plumed team
       3             :    (see the PEOPLE file at the root of the distribution for a list of names)
       4             : 
       5             :    See http://www.plumed.org for more information.
       6             : 
       7             :    This file is part of plumed, version 2.
       8             : 
       9             :    plumed is free software: you can redistribute it and/or modify
      10             :    it under the terms of the GNU Lesser General Public License as published by
      11             :    the Free Software Foundation, either version 3 of the License, or
      12             :    (at your option) any later version.
      13             : 
      14             :    plumed is distributed in the hope that it will be useful,
      15             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      16             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17             :    GNU Lesser General Public License for more details.
      18             : 
      19             :    You should have received a copy of the GNU Lesser General Public License
      20             :    along with plumed.  If not, see <http://www.gnu.org/licenses/>.
      21             : +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
      22             : #ifndef __PLUMED_tools_MergeVectorTools_h
      23             : #define __PLUMED_tools_MergeVectorTools_h
      24             : 
      25             : #include "small_vector/small_vector.h"
      26             : #include <vector>
      27             : #include <algorithm>
      28             : #include <type_traits>
      29             : 
      30             : namespace PLMD {
      31             : 
      32             : namespace mergeVectorTools {
      33             : 
      34             : /// Merge sorted vectors.
      35             : /// Takes a vector of pointers to containers and merge them.
      36             : /// Containers should be already sorted.
      37             : /// The content is appended to the result vector.
      38             : /// Optionally, uses a priority_queue implementation.
      39             : template<class C>
      40       50245 : static void mergeSortedVectors(const C* const* vecs, std::size_t size, std::vector<typename C::value_type> & result) {
      41             : 
      42             :   /// local class storing the range of remaining objects to be pushed
      43             :   class Entry {
      44             :     typename C::const_iterator fwdIt,endIt;
      45             : 
      46             :   public:
      47      137420 :     explicit Entry(C const& v) : fwdIt(v.begin()), endIt(v.end()) {}
      48             :     /// check if this vector still contains something to be pushed
      49             :     bool empty() const {
      50             :       return fwdIt == endIt;
      51             :     }
      52             :     /// to allow using a priority_queu, which selects the highest element.
      53             :     /// we here (counterintuitively) define < as >
      54             :     bool operator< (Entry const& rhs) const {
      55             :       return top() > rhs.top();
      56             :     }
      57             :     // TODO: revert "typename C::value_type" to "auto": nvc++ and icpc seems to do not deduce automatically the return type
      58             :     const typename C::value_type & top() const {
      59             :       return *fwdIt;
      60             :     }
      61             :     void next() {
      62             :       ++fwdIt;
      63             :     };
      64             :   };
      65             : 
      66             :   // preprocessing
      67             :   {
      68       50245 :     std::size_t maxsize=0;
      69      192462 :     for(unsigned i=0; i<size; i++) {
      70             :       // find the largest
      71      193506 :       maxsize=std::max(maxsize,vecs[i]->size());
      72             :     }
      73             :     // this is just to decrease the number of reallocations on push_back
      74       50245 :     result.reserve(maxsize);
      75             :     // if vectors are empty we are done
      76       50245 :     if(maxsize==0) {
      77        3096 :       return;
      78             :     }
      79             :   }
      80             : 
      81             :   // start
      82             :   // heap containing the ranges to be pushed
      83             :   // avoid allocations when it's small
      84             :   gch::small_vector<Entry,32> heap;
      85             : 
      86             :   {
      87      187657 :     for(unsigned i=0; i<size; i++) {
      88      140508 :       if(!vecs[i]->empty()) {
      89             :         // add entry at the end of the array
      90      137420 :         heap.emplace_back(Entry(*vecs[i]));
      91             :       }
      92             :     }
      93             :     // make a sorted heap
      94       47149 :     std::make_heap(std::begin(heap),std::end(heap));
      95             :   }
      96             : 
      97             :   // first iteration, to avoid an extra "if" in main iteration
      98             :   // explanations are below
      99             :   {
     100       47149 :     std::pop_heap(std::begin(heap), std::end(heap));
     101             :     auto & tmp=heap.back();
     102       47149 :     const auto val=tmp.top();
     103             :     // here, we append inconditionally
     104       47149 :     result.push_back(val);
     105             :     tmp.next();
     106       47149 :     if(tmp.empty()) {
     107             :       heap.pop_back();
     108             :     } else {
     109       44604 :       std::push_heap(std::begin(heap), std::end(heap));
     110             :     }
     111             :   }
     112             : 
     113     2567535 :   while(!heap.empty()) {
     114             :     // move entry with the smallest element to the back of the array
     115     2520386 :     std::pop_heap(std::begin(heap), std::end(heap));
     116             :     // entry
     117             :     auto & tmp=heap.back();
     118             :     // element
     119     2520386 :     const auto val=tmp.top();
     120             :     // if the element is larger than the current largest element,
     121             :     // push it to result
     122     2520386 :     if(val > result.back()) {
     123     1439018 :       result.push_back(val);
     124             :     }
     125             :     // move forward the used entry
     126             :     tmp.next();
     127             :     // if this entry is exhausted, remove it from the array
     128     2520386 :     if(tmp.empty()) {
     129             :       heap.pop_back();
     130             :     }
     131             :     // otherwise, sort again the array
     132             :     else {
     133     2385511 :       std::push_heap(std::begin(heap), std::end(heap));
     134             :     }
     135             :   }
     136             : }
     137             : 
     138             : template<typename T, typename = void>
     139             : struct has_size_and_data : std::false_type {};
     140             : 
     141             : template<typename T>
     142             : struct has_size_and_data<T, std::void_t<decltype(std::declval<T>().size()), decltype(std::declval<T>().data())>> : std::true_type {};
     143             : 
     144             : template<class C, class D>
     145       50245 : auto mergeSortedVectors(C& vecs, std::vector<D> & result) -> typename std::enable_if<has_size_and_data<C>::value, void>::type {
     146       50245 :   mergeSortedVectors(vecs.data(),vecs.size(),result);
     147       50245 : }
     148             : 
     149             : }
     150             : }
     151             : 
     152             : #endif
     153             :