api/legacy/include/gromacs/utility/listoflists.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2019,2020,2021, by the GROMACS development team, led by
   5  * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   6  * and including many others, as listed in the AUTHORS file in the
   7  * top-level source directory and at http://www.gromacs.org.
   8  *
   9  * GROMACS is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public License
  11  * as published by the Free Software Foundation; either version 2.1
  12  * of the License, or (at your option) any later version.
  13  *
  14  * GROMACS 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 GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with GROMACS; if not, see
  21  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  23  *
  24  * If you want to redistribute modifications to GROMACS, please
  25  * consider that scientific software is very special. Version
  26  * control is crucial - bugs must be traceable. We will be happy to
  27  * consider code for inclusion in the official distribution, but
  28  * derived work must not be called official GROMACS. Details are found
  29  * in the README & COPYING files - if they are missing, get the
  30  * official version at http://www.gromacs.org.
  31  *
  32  * To help us fund GROMACS development, we humbly ask that you cite
  33  * the research papers on the package. Check out http://www.gromacs.org.
  34  */
  35 /*! \file
  36  * \brief
  37  * Declares gmx::ListOfLists
  38  *
  39  * \author Berk Hess <hess@kth.se>
  40  * \inpublicapi
  41  * \ingroup module_utility
  42  */
  43 #ifndef GMX_UTILITY_LISTOFLISTS_H
  44 #define GMX_UTILITY_LISTOFLISTS_H
  45
  46 #include <vector>
  47
  48 #include "gromacs/utility/arrayref.h"
  49 #include "gromacs/utility/basedefinitions.h"
  50 #include "gromacs/utility/exceptions.h"
  51
  52 namespace gmx
  53 {
  54
  55 /*! \brief A list of lists, optimized for performance
  56  *
  57  * This class holds a list of \p size() lists of elements of type \p T.
  58  * To optimize performance, the only modification operation supporting
  59  * is adding a new list at the end of the list of lists.
  60  *
  61  * This implementation stores all data internally in two std::vector objects
  62  * and thereby avoids the overhead of managing \p size() separate objects
  63  * in memory.
  64  *
  65  * Internal storage consists of one std::vector<int> listRanges_ of size number
  66  * of lists plus one and a std::vector<T> elements_ with the elements of all
  67  * lists concatenated. List i is stored in entries listRanges_[i] to
  68  * listRanges_[i+1] in elements_.
  69  *
  70  * \note This class is currently limited to arithmetic types, mainly because
  71  * this should only be used for performance critical applications.
  72  * When performance is not critical, a std::vector of std::vector can be used.
  73  *
  74  * \tparam T value type
  75  */
  76
  77 template<typename T>
  78 class ListOfLists
  79 {
  80     // TODO: Use std::is_arithmetic_v when CUDA 11 is a requirement.
  81     static_assert(std::is_arithmetic<T>::value, "This class is limited to arithmetic types");
  82
  83 public:
  84     //! Constructs an empty list of lists
  85     ListOfLists() = default;
  86
  87     /*! \brief Constructs a list of list from raw data in internal layout
  88      *
  89      * Does basic consistency checks and throws when one of those fail.
  90      *
  91      * \param[in] listRanges  Ranges of the lists concatenated (see above), is consumed
  92      * \param[in] elements    Elements for all lists concatenated, is consumed
  93      */
  94     ListOfLists(std::vector<int>&& listRanges, std::vector<T>&& elements) :
  95         listRanges_(std::move(listRanges)), elements_(std::move(elements))
  96     {
  97         if (listRanges_.empty() || listRanges_.at(0) != 0)
  98         {
  99             GMX_THROW(InconsistentInputError(
 100                     "listRanges does not have a first element with value 0"));
 101         }
 102         if (int(elements_.size()) != listRanges_.back())
 103         {
 104             GMX_THROW(InconsistentInputError(
 105                     "The size of elements does not match the last value in listRanges"));
 106         }
 107     }
 108
 109     //! Returns the number of lists
 110     std::size_t size() const { return listRanges_.size() - 1; }
 111
 112     /*! \brief Returns the number of lists
 113      *
 114      * \note Use ssize for any expression involving arithmetic operations
 115      * (including loop indices).
 116      */
 117     index ssize() const { return index(listRanges_.size()) - 1; }
 118
 119     //! Returns whether the list holds no lists
 120     bool empty() const { return listRanges_.size() == 1; }
 121
 122     //! Returns the sum of the number of elements over all lists
 123     int numElements() const { return listRanges_.back(); }
 124
 125     //! Appends a new list with elements \p values, pass {} to add an empty list
 126     void pushBack(ArrayRef<const T> values)
 127     {
 128         elements_.insert(elements_.end(), values.begin(), values.end());
 129         listRanges_.push_back(int(elements_.size()));
 130     }
 131
 132     //! Appends a new list with \p numElements elements
 133     void pushBackListOfSize(int numElements)
 134     {
 135         // With arithmetic types enforced, this assertion is always true
 136         // TODO: Use std::is_default_constructible_v when CUDA 11 is a requirement.
 137         static_assert(std::is_default_constructible<T>::value,
 138                       "pushBackListOfSize should only be called with default constructable types");
 139         elements_.resize(elements_.size() + numElements);
 140         listRanges_.push_back(int(elements_.size()));
 141     }
 142
 143     //! Returns an ArrayRef to the elements of the list with the given index
 144     ArrayRef<const T> operator[](std::size_t listIndex) const
 145     {
 146         return ArrayRef<const T>(elements_.data() + listRanges_[listIndex],
 147                                  elements_.data() + listRanges_[listIndex + 1]);
 148     }
 149
 150     //! Returns the list of elements for the list with index \p listIndex, throws an \p out_of_range exception when out of range
 151     ArrayRef<const T> at(std::size_t listIndex) const
 152     {
 153         return ArrayRef<const T>(elements_.data() + listRanges_.at(listIndex),
 154                                  elements_.data() + listRanges_.at(listIndex + 1));
 155     }
 156
 157     /*! \brief Returns a reference to the first list
 158      *
 159      * \returns a reference to the first list
 160      */
 161     ArrayRef<T> front()
 162     {
 163         GMX_ASSERT(size() > 0, "Must contain a list if front() is called");
 164         auto* beginPtr = elements_.data();
 165         auto* endPtr   = beginPtr + listRanges_[1];
 166         return { beginPtr, endPtr };
 167     }
 168     /*! \brief Returns a reference to the final list
 169      *
 170      * \returns a reference to the final list
 171      */
 172     ArrayRef<T> back()
 173     {
 174         GMX_ASSERT(size() > 0, "Must contain a list if bank() is called");
 175         auto endIndex   = *(listRanges_.end() - 1);
 176         auto beginIndex = *(listRanges_.end() - 2);
 177         return { elements_.data() + beginIndex, elements_.data() + endIndex };
 178     }
 179
 180     //! Clears the list
 181     void clear()
 182     {
 183         listRanges_.resize(1);
 184         elements_.clear();
 185     }
 186
 187     //! Appends a ListOfLists at the end and increments the appended elements by \p offset
 188     void appendListOfLists(const ListOfLists& listOfLists, const T offset = 0)
 189     {
 190         listRanges_.insert(
 191                 listRanges_.end(), listOfLists.listRanges_.begin() + 1, listOfLists.listRanges_.end());
 192         const int oldNumElements = elements_.size();
 193         for (std::size_t i = listRanges_.size() - listOfLists.size(); i < listRanges_.size(); i++)
 194         {
 195             listRanges_[i] += oldNumElements;
 196         }
 197         elements_.insert(elements_.end(), listOfLists.elements_.begin(), listOfLists.elements_.end());
 198
 199         if (offset != 0)
 200         {
 201             for (std::size_t i = elements_.size() - listOfLists.elements_.size(); i < elements_.size(); i++)
 202             {
 203                 elements_[i] += offset;
 204             }
 205         }
 206     }
 207
 208     //! Returns concatenated ranges of the lists (see above for details)
 209     ArrayRef<const int> listRangesView() const { return listRanges_; }
 210
 211     //! Returns the a view of the elements of all lists concatenated
 212     ArrayRef<const T> elementsView() const { return elements_; }
 213
 214 private:
 215     //! The ranges of the lists, list i uses range \p listRanges_[i], \p listRanges_[i+1].
 216     std::vector<int> listRanges_ = { 0 };
 217     //! The elements in all lists concatenated
 218     std::vector<T> elements_;
 219 };
 220
 221 } // namespace gmx
 222
 223 #endif