From 4b758c41d11a0a1b300a6b8c8a0005ca093f8056 Mon Sep 17 00:00:00 2001 From: bangerth Date: Sat, 10 Oct 2009 16:50:21 +0000 Subject: [PATCH] Implement merging individual indices into ranges. git-svn-id: https://svn.dealii.org/trunk@19804 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/base/source/index_set.cc | 71 ++++++++++++++++++++++++++++++++ 1 file changed, 71 insertions(+) diff --git a/deal.II/base/source/index_set.cc b/deal.II/base/source/index_set.cc index f19984c9b2..ec940c07cf 100644 --- a/deal.II/base/source/index_set.cc +++ b/deal.II/base/source/index_set.cc @@ -60,6 +60,77 @@ IndexSet::compress () const // next see if we can roll any of // the individual entries into the // contiguous ranges + { + std::set::iterator + next_range = contiguous_ranges.begin(); + std::set::iterator + next_individual_index = individual_indices.begin(); + + while ((next_range != contiguous_ranges.end()) + && + (next_individual_index != individual_indices.end())) + { + // if the next individual + // index is beyond the upper + // bound of the next range, + // then we need to inspect + // the next range + if (*next_individual_index > next_range->second) + { + ++next_range; + continue; + } + + // if, on the other hand, the + // next individual index is + // below the lower bound of + // the next range, then we + // need to inspect the next + // index + if (*next_individual_index < next_range->first-1) + { + ++next_individual_index; + continue; + } + + // now we know that the + // individual index is within + // the next range, or + // possibly one element + // before, or one element + // after. so they can be + // merged. note that ranges + // are half open, so in the + // upper bound we have to + // consider the next index+1 + ContiguousRange new_range (std::min (*next_individual_index, + next_range->first), + std::max (*next_individual_index+1, + next_range->second)); + + // erase old index and range, + // and reset iterators + // + // note that the following + // index can't possibly be + // *next_index+1, since we + // have merged contiguous + // sets of individual indices + // above. however, there may + // be more individual indices + // that lie within the + // current range, so we'll + // delete all of them + const unsigned int old_index = *next_individual_index; + individual_indices.erase (next_individual_index); + next_individual_index = individual_indices.lower_bound (old_index); + + contiguous_ranges.erase (next_range); + contiguous_ranges.insert (new_range); + + next_range = contiguous_ranges.lower_bound (new_range); + } + } // finally see if any of the -- 2.39.5