OptimizedIndexSet.h

Go to the documentation of this file.

/******************************************************************************
 * Copyright (c) 2021.                                                        *
 * The Regents of the University of Michigan and DFT-EFE developers.          *
 *                                                                            *
 * This file is part of the DFT-EFE code.                                     *
 *                                                                            *
 * DFT-EFE is free software: you can redistribute it and/or modify            *
 *   it under the terms of the Lesser GNU General Public License as           *
 *   published by the Free Software Foundation, either version 3 of           *
 *   the License, or (at your option) any later version.                      *
 *                                                                            *
 * DFT-EFE is distributed in the hope that it will be useful, but             *
 *   WITHOUT ANY WARRANTY; without even the implied warranty                  *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                     *
 *   See the Lesser GNU General Public License for more details.              *
 *                                                                            *
 * You should have received a copy of the GNU Lesser General Public           *
 *   License at the top level of DFT-EFE distribution.  If not, see           *
 *   <https://www.gnu.org/licenses/>.                                         *
 ******************************************************************************/
 
/*
 * @author Bikash Kanungo
 */
#ifndef dftefeOptimizedIndexSet_h
#define dftefeOptimizedIndexSet_h
 
#include <utils/TypeConfig.h>
#include <set>
#include <vector>
namespace dftefe
{
  namespace utils
  {
    /*
     * @brief Class to create an optimized index set which
     * creates contiguous sub-ranges within an index set for faster
     * search operation. This is useful when the number of contiguous sub-ranges
     * are fewer compared to the size of the index set. If the number of
     * contiguous sub-ranges competes with the size of the index set (i.e., the
     * index set is very random) then it default to the behavior of an std::set.
     *
     * @tparam ValueType The data type of the indices (e.g., unsigned int, unsigned long int)
     */
 
    template <typename T>
    class OptimizedIndexSet
    {
    public:
      OptimizedIndexSet(const std::set<T> &inputSet = std::set<T>());
      ~OptimizedIndexSet() = default;
 
      void
      getPosition(const T &index, size_type &pos, bool &found) const;
 
      bool
      getPosition(const OptimizedIndexSet<T> &rhs) const;
 
      bool
      operator==(const OptimizedIndexSet<T> &rhs) const;
 
      const std::vector<T> &
      getContiguousRanges() const;
 
    private:
      size_type d_numContiguousRanges;
 
      /*
       * Vector of size 2*(d_numContiguousRanges in d_set).
       * The entries are arranged as:
       * <contiguous range1 startId> <continguous range1 endId> <contiguous
       * range2 startId> <continguous range2 endId> ... NOTE: The endId is one
       * past the lastId in the continguous range
       */
      std::vector<T> d_contiguousRanges;
 
      std::vector<size_type> d_numEntriesBefore;
    };
 
  } // end of namespace utils
 
} // end of namespace dftefe
#include <utils/OptimizedIndexSet.t.cpp>
#endif // dftefeOptimizedSet_h