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       50163 : 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             :   {
      45             :     typename C::const_iterator fwdIt,endIt;
      46             : 
      47             :   public:
      48      137267 :     explicit Entry(C const& v) : fwdIt(v.begin()), endIt(v.end()) {}
      49             :     /// check if this vector still contains something to be pushed
      50             :     bool empty() const { return fwdIt == endIt; }
      51             :     /// to allow using a priority_queu, which selects the highest element.
      52             :     /// we here (counterintuitively) define < as >
      53             :     bool operator< (Entry const& rhs) const { return top() > rhs.top(); }
      54             :     // TODO: revert "typename C::value_type" to "auto": nvc++ and icpc seems to do not deduce automatically the return type
      55             :     const typename C::value_type & top() const { return *fwdIt; }
      56             :     void next() { ++fwdIt;};
      57             :   };
      58             : 
      59             :   // preprocessing
      60             :   {
      61       50163 :     std::size_t maxsize=0;
      62      192213 :     for(unsigned i=0; i<size; i++) {
      63             :       // find the largest
      64      193271 :       maxsize=std::max(maxsize,vecs[i]->size());
      65             :     }
      66             :     // this is just to decrease the number of reallocations on push_back
      67       50163 :     result.reserve(maxsize);
      68             :     // if vectors are empty we are done
      69       50163 :     if(maxsize==0) return;
      70             :   }
      71             : 
      72             :   // start
      73             :   // heap containing the ranges to be pushed
      74             :   // avoid allocations when it's small
      75             :   gch::small_vector<Entry,32> heap;
      76             : 
      77             :   {
      78      187422 :     for(unsigned i=0; i<size; i++) {
      79      140341 :       if(!vecs[i]->empty()) {
      80             :         // add entry at the end of the array
      81      137267 :         heap.emplace_back(Entry(*vecs[i]));
      82             :       }
      83             :     }
      84             :     // make a sorted heap
      85       47081 :     std::make_heap(std::begin(heap),std::end(heap));
      86             :   }
      87             : 
      88             :   // first iteration, to avoid an extra "if" in main iteration
      89             :   // explanations are below
      90             :   {
      91       47081 :     std::pop_heap(std::begin(heap), std::end(heap));
      92             :     auto & tmp=heap.back();
      93       47081 :     const auto val=tmp.top();
      94             :     // here, we append inconditionally
      95       47081 :     result.push_back(val);
      96             :     tmp.next();
      97       47081 :     if(tmp.empty()) heap.pop_back();
      98       44536 :     else std::push_heap(std::begin(heap), std::end(heap));
      99             :   }
     100             : 
     101     2523923 :   while(!heap.empty()) {
     102             :     // move entry with the smallest element to the back of the array
     103     2476842 :     std::pop_heap(std::begin(heap), std::end(heap));
     104             :     // entry
     105             :     auto & tmp=heap.back();
     106             :     // element
     107     2476842 :     const auto val=tmp.top();
     108             :     // if the element is larger than the current largest element,
     109             :     // push it to result
     110     2476842 :     if(val > result.back()) result.push_back(val);
     111             :     // move forward the used entry
     112             :     tmp.next();
     113             :     // if this entry is exhausted, remove it from the array
     114     2476842 :     if(tmp.empty()) heap.pop_back();
     115             :     // otherwise, sort again the array
     116     2342120 :     else std::push_heap(std::begin(heap), std::end(heap));
     117             :   }
     118             : }
     119             : 
     120             : template<typename T, typename = void>
     121             : struct has_size_and_data : std::false_type {};
     122             : 
     123             : template<typename T>
     124             : struct has_size_and_data<T, std::void_t<decltype(std::declval<T>().size()), decltype(std::declval<T>().data())>> : std::true_type {};
     125             : 
     126             : template<class C, class D>
     127       50163 : auto mergeSortedVectors(C& vecs, std::vector<D> & result) -> typename std::enable_if<has_size_and_data<C>::value, void>::type {
     128       50163 :   mergeSortedVectors(vecs.data(),vecs.size(),result);
     129       50163 : }
     130             : 
     131             : }
     132             : }
     133             : 
     134             : #endif
     135             :