From 4a529a2218a6931aee5be7cd4b59221abbdaa37a Mon Sep 17 00:00:00 2001 From: Rene Gassmoeller Date: Mon, 5 Sep 2016 10:50:20 -0600 Subject: [PATCH] Use struct and call std::sort --- source/grid/manifold.cc | 52 ++++++++++++++++++++++------------------- 1 file changed, 28 insertions(+), 24 deletions(-) diff --git a/source/grid/manifold.cc b/source/grid/manifold.cc index d4f9a9fe9f..c56f44748f 100644 --- a/source/grid/manifold.cc +++ b/source/grid/manifold.cc @@ -25,8 +25,26 @@ DEAL_II_NAMESPACE_OPEN using namespace Manifolds; -/* -------------------------- Manifold --------------------- */ +// This structure is used as comparison function for std::sort when sorting +// points according to their weight. +struct CompareWeights +{ +public: + CompareWeights(const std::vector &weights) + : + compare_weights(&weights) + {} + bool operator() (unsigned int a, unsigned int b) const + { + return (*compare_weights)[a] < (*compare_weights)[b]; + } + +private: + const std::vector *compare_weights; +}; + +/* -------------------------- Manifold --------------------- */ template Manifold::~Manifold () @@ -81,32 +99,18 @@ get_new_point (const std::vector > &surrounding_points, Assert(std::abs(std::accumulate(weights.begin(), weights.end(), 0.0)-1.0) < tol, ExcMessage("The weights for the individual points should sum to 1!")); - // The number of points is small (at most 26 in 3D), therefore try to minize - // overhead and use a very simple search of O(N^2) to find the order in which - // to loop over points. + // First sort points in the order of their weights. This is done to + // produce unique points even if get_intermediate_points is not + // associative (as for the SphericalManifold). std::vector permutation(n_points); - std::vector found(n_points,false); + for (unsigned int i=0; i::max(); + std::sort(permutation.begin(), + permutation.end(), + CompareWeights(weights)); - for (unsigned int j=0; j < n_points; ++j) - { - if ((!found[j]) && (weights[j] < min_weight)) - { - min_weight = weights[j]; - min_index = j; - } - } - permutation[i] = min_index; - found[min_index] = true; - } - - // Now loop over points in the order of their weights. This is done to - // produce unique points even if get_intermediate_points is not - // associative (as for the SphericalManifold). + // Now loop over points in the order of their associated weight Point p = surrounding_points[permutation[0]]; double w = weights[permutation[0]]; -- 2.39.5