From 2cfa1fbfd31aa593c0c80f9f9e77e63f711e0d93 Mon Sep 17 00:00:00 2001 From: Wolfgang Bangerth Date: Thu, 15 Oct 2009 22:31:15 +0000 Subject: [PATCH] Use a std::vector instead of a std::set. Keep it always sorted. git-svn-id: https://svn.dealii.org/trunk@19896 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/base/include/base/index_set.h | 39 ++++++++++++++----- deal.II/base/source/index_set.cc | 56 ++++++++++++++------------- 2 files changed, 59 insertions(+), 36 deletions(-) diff --git a/deal.II/base/include/base/index_set.h b/deal.II/base/include/base/index_set.h index ae290dec15..eb6a8b2bf1 100644 --- a/deal.II/base/include/base/index_set.h +++ b/deal.II/base/include/base/index_set.h @@ -16,7 +16,8 @@ #include #include -#include +#include +#include DEAL_II_NAMESPACE_OPEN @@ -154,12 +155,24 @@ class IndexSet * A type that denotes the half * open index range * [begin,end). + * + * The nth_index_in_set denotes + * the how many-th index within + * this IndexSet the first + * element of the current range + * is. This information is only + * accurate if + * IndexSet::compress() has been + * called after the last + * insertion. */ struct Range { unsigned int begin; unsigned int end; + unsigned int nth_index_in_set; + Range (const unsigned int i1, const unsigned int i2); @@ -178,7 +191,8 @@ class IndexSet /** * A set of contiguous ranges of * indices that make up (part of) - * this index set. + * this index set. This variable + * is always kept sorted. * * The variable is marked * "mutable" so that it can be @@ -188,7 +202,7 @@ class IndexSet * representation of this index * set. */ - mutable std::set ranges; + mutable std::vector ranges; /** * True if compress() has been @@ -280,7 +294,11 @@ IndexSet::add_range (const unsigned int begin, if (begin != end) { - ranges.insert (Range(begin,end)); + const Range new_range(begin,end); + ranges.insert (std::lower_bound (ranges.begin(), + ranges.end(), + new_range), + new_range); is_compressed = false; } } @@ -294,7 +312,11 @@ IndexSet::add_index (const unsigned int index) Assert (index < index_space_size, ExcIndexRange (index, 0, index_space_size)); - ranges.insert (Range(index, index+1)); + const Range new_range(index, index+1); + ranges.insert (std::lower_bound (ranges.begin(), + ranges.end(), + new_range), + new_range); is_compressed = false; } @@ -355,7 +377,7 @@ IndexSet::is_element (const unsigned int index) const // of the following ranges // because otherwise p would be // a different iterator - std::set::const_iterator + std::vector::const_iterator p = std::upper_bound (ranges.begin(), ranges.end(), Range (index, size()+1)); @@ -396,12 +418,11 @@ unsigned int IndexSet::n_elements () const { // make sure we have - // non-overlapping ranges and - // individual indices + // non-overlapping ranges compress (); unsigned int s = 0; - for (std::set::iterator range = ranges.begin(); + for (std::vector::iterator range = ranges.begin(); range != ranges.end(); ++range) s += (range->end - range->begin); diff --git a/deal.II/base/source/index_set.cc b/deal.II/base/source/index_set.cc index 4b7e0a2a29..70e99070b0 100644 --- a/deal.II/base/source/index_set.cc +++ b/deal.II/base/source/index_set.cc @@ -25,12 +25,11 @@ IndexSet::compress () const // merged. since they are sorted by // their first index, determining // overlap isn't all that hard - for (std::set::iterator + for (std::vector::iterator i = ranges.begin(); - i != ranges.end(); - ++i) + i != ranges.end(); ) { - std::set::const_iterator + std::vector::iterator next = i; ++next; @@ -50,33 +49,36 @@ IndexSet::compress () const if (can_merge == true) { - // delete the old - // ranges and insert the - // new range - ranges.erase (i, next); - ranges.insert (Range(first_index, - last_index)); - - // then set iterator to - // the same position as - // before. in the next - // step, the loop is then - // going to increase 'i' - // by one. note that we - // don't need to - // reconsider the same - // iterator for merging - // with the next range - // because we have made - // sure we gobble up as - // many of the following - // ranges as possible - i = ranges.lower_bound (Range(first_index, - last_index)); + // delete the old ranges + // and insert the new range + // in place of the previous + // one + *i = Range(first_index, last_index); + i = ranges.erase (i+1, next); } + else + ++i; } + + // now compute indices within set + unsigned int next_index = 0; + for (std::vector::iterator + i = ranges.begin(); + i != ranges.end(); + ++i) + { + i->nth_index_in_set = next_index; + next_index += (i->end - i->begin); + } is_compressed = true; + + // check that next_index is + // correct. needs to be after the + // previous statement because we + // otherwise will get into an + // endless loop + Assert (next_index == n_elements(), ExcInternalError()); } -- 2.39.5