16 #ifndef dealii_index_set_h
17 #define dealii_index_set_h
26 #include <boost/container/small_vector.hpp>
33 #ifdef DEAL_II_WITH_TRILINOS
34 # include <Epetra_Map.h>
35 # ifdef DEAL_II_TRILINOS_WITH_TPETRA
36 # include <Tpetra_Map.hpp>
40 #if defined(DEAL_II_WITH_MPI) || defined(DEAL_II_WITH_PETSC)
44 # ifndef MPI_COMM_WORLD
45 # define MPI_COMM_WORLD 0
140 #ifdef DEAL_II_WITH_TRILINOS
144 explicit IndexSet(
const Epetra_BlockMap &map);
197 template <
typename ForwardIterator>
352 std::vector<IndexSet>
354 const std::vector<types::global_dof_index> &n_indices_per_block)
const;
415 template <
typename VectorType>
423 template <
class StreamType>
425 print(StreamType &out)
const;
432 write(std::ostream &out)
const;
439 read(std::istream &in);
455 #ifdef DEAL_II_WITH_TRILINOS
486 const bool overlapping =
false)
const;
488 # ifdef DEAL_II_TRILINOS_WITH_TPETRA
489 Tpetra::Map<int, types::global_dof_index>
491 const bool overlapping =
false)
const;
505 <<
"The global index " << arg1
506 <<
" is not an element of this set.");
513 template <
class Archive>
515 serialize(Archive &ar,
const unsigned int version);
936 return sizeof(
Range);
944 template <
class Archive>
946 serialize(Archive &ar,
const unsigned int version);
1038 boost::container::small_vector<std::pair<size_type, size_type>, 200>
1040 const bool ranges_are_sorted);
1080 , range_idx(range_idx)
1097 : index_set(other.index_set)
1098 , range_idx(other.range_idx)
1110 return index_set->ranges[range_idx].end - index_set->ranges[range_idx].begin;
1118 return index_set !=
nullptr && range_idx < index_set->n_intervals();
1127 return {index_set, range_idx, index_set->ranges[range_idx].begin};
1138 if (range_idx < index_set->
ranges.size() - 1)
1139 return {index_set, range_idx + 1, index_set->ranges[range_idx + 1].begin};
1141 return index_set->end();
1151 return index_set->ranges[range_idx].end - 1;
1174 "Can not compare accessors pointing to different IndexSets"));
1186 "Can not compare accessors pointing to different IndexSets"));
1198 "Impossible to advance an IndexSet::IntervalIterator that is invalid"));
1202 if (range_idx >= index_set->ranges.size())
1212 : accessor(idxset, range_idx)
1277 return !(*
this == other);
1297 "Can not compare iterators belonging to different IndexSets"));
1300 accessor.index_set->ranges.size() :
1304 accessor.index_set->ranges.size() :
1308 return static_cast<int>(lhs - rhs);
1310 return -
static_cast<int>(rhs - lhs);
1322 , range_idx(range_idx)
1327 "Invalid range index for IndexSet::ElementIterator constructor."));
1332 "Invalid index argument for IndexSet::ElementIterator constructor."));
1350 (range_idx < index_set->
ranges.size() &&
1351 idx < index_set->
ranges[range_idx].end),
1354 return (range_idx < index_set->
ranges.size() &&
1355 idx < index_set->
ranges[range_idx].end);
1366 "Impossible to dereference an IndexSet::ElementIterator that is invalid"));
1378 "Can not compare iterators belonging to different IndexSets"));
1379 return range_idx == other.
range_idx && idx == other.
idx;
1390 "Impossible to advance an IndexSet::ElementIterator that is invalid"));
1391 if (idx < index_set->
ranges[range_idx].
end)
1394 if (idx == index_set->ranges[range_idx].end)
1397 if (range_idx < index_set->
ranges.size() - 1)
1400 idx = index_set->ranges[range_idx].begin;
1436 return !(*
this == other);
1447 "Can not compare iterators belonging to different IndexSets"));
1454 inline std::ptrdiff_t
1460 "Can not compare iterators belonging to different IndexSets"));
1463 if (!(*
this < other))
1464 return -(other - *
this);
1473 std::ptrdiff_t c = index_set->ranges[range_idx].end - idx;
1477 range < index_set->ranges.size() && range <= other.
range_idx;
1479 c += index_set->ranges[range].end - index_set->ranges[range].begin;
1482 other.
range_idx < index_set->ranges.size() ||
1485 "Inconsistent iterator state. Did you invalidate iterators by modifying the IndexSet?"));
1490 c -= index_set->ranges[other.
range_idx].end - other.
idx;
1525 : is_compressed(true)
1526 , index_space_size(size)
1533 : ranges(std::move(is.ranges))
1534 , is_compressed(is.is_compressed)
1535 , index_space_size(is.index_space_size)
1536 , largest_range(is.largest_range)
1539 is.is_compressed =
true;
1540 is.index_space_size = 0;
1551 ranges = std::move(is.ranges);
1552 is_compressed = is.is_compressed;
1553 index_space_size = is.index_space_size;
1554 largest_range = is.largest_range;
1557 is.is_compressed =
true;
1558 is.index_space_size = 0;
1573 return {
this, 0,
ranges[0].begin};
1626 ExcMessage(
"This function can only be called if the current "
1627 "object does not yet contain any elements."));
1658 const Range new_range(index, index + 1);
1660 ranges.push_back(new_range);
1661 else if (index ==
ranges.back().end)
1687 ranges.push_back(new_range);
1699 template <
typename ForwardIterator>
1711 boost::container::small_vector<std::pair<size_type, size_type>, 200>
1713 bool ranges_are_sorted =
true;
1714 for (ForwardIterator p =
begin; p !=
end;)
1718 ForwardIterator q = p;
1720 while ((q !=
end) && (
static_cast<size_type>(*q) == end_index))
1726 tmp_ranges.emplace_back(begin_index, end_index);
1733 if (p !=
end &&
static_cast<size_type>(*p) < end_index)
1734 ranges_are_sorted =
false;
1745 if (
ranges.empty() ==
false)
1754 else if (
ranges.size() > 1)
1769 return (
ranges.size() <= 1);
1797 for (
const auto &range :
ranges)
1798 s += (range.end - range.begin);
1822 const std::vector<Range>::const_iterator main_range =
1825 return main_range->nth_index_in_set;
1840 if (n >= main_range->nth_index_in_set &&
1842 return main_range->begin + (n - main_range->nth_index_in_set);
1867 else if (
ranges.size() > 1)
1901 template <
typename Vector>
1909 std::fill(vector.
begin(), vector.
end(), 0);
1913 for (
const auto &range :
ranges)
1914 for (
size_type i = range.begin; i < range.end; ++i)
1920 template <
class StreamType>
1926 std::vector<Range>::const_iterator p;
1929 if (p->end - p->begin == 1)
1932 out <<
'[' << p->begin <<
',' << p->end - 1 <<
']';
1937 out <<
'}' << std::endl;
1942 template <
class Archive>
1951 template <
class Archive>
size_type operator*() const
bool operator==(const ElementIterator &) const
ElementIterator(const IndexSet *idxset, const size_type range_idx, const size_type index)
std::ptrdiff_t difference_type
ElementIterator & operator++()
bool operator<(const ElementIterator &) const
bool operator!=(const ElementIterator &) const
std::ptrdiff_t operator-(const ElementIterator &p) const
std::forward_iterator_tag iterator_category
const IndexSet * index_set
ElementIterator end() const
size_type n_elements() const
bool operator==(const IntervalAccessor &other) const
IntervalAccessor & operator=(const IntervalAccessor &other)
bool operator<(const IntervalAccessor &other) const
IntervalAccessor(const IndexSet *idxset, const size_type range_idx)
const IndexSet * index_set
ElementIterator begin() const
std::ptrdiff_t difference_type
const IntervalAccessor & operator*() const
IntervalIterator(const IntervalIterator &other)=default
bool operator==(const IntervalIterator &) const
int operator-(const IntervalIterator &p) const
bool operator<(const IntervalIterator &) const
std::forward_iterator_tag iterator_category
IntervalIterator & operator++()
IntervalIterator & operator=(const IntervalIterator &other)=default
const IntervalAccessor * operator->() const
IntervalAccessor accessor
bool operator!=(const IntervalIterator &) const
bool is_element_binary_search(const size_type local_index) const
size_type index_within_set_binary_search(const size_type global_index) const
bool is_contiguous() const
unsigned int n_intervals() const
IndexSet(const IndexSet &)=default
IndexSet & operator=(const IndexSet &)=default
IntervalIterator end_intervals() const
ElementIterator at(const size_type global_index) const
void fill_index_vector(std::vector< size_type > &indices) const
size_type index_within_set(const size_type global_index) const
std::vector< IndexSet > split_by_block(const std::vector< types::global_dof_index > &n_indices_per_block) const
size_type n_elements() const
bool operator==(const IndexSet &is) const
void add_range_lower_bound(const Range &range)
bool is_element(const size_type index) const
void serialize(Archive &ar, const unsigned int version)
ElementIterator begin() const
void set_size(const size_type size)
bool operator!=(const IndexSet &is) const
void read(std::istream &in)
size_type largest_range_starting_index() const
Tpetra::Map< int, types::global_dof_index > make_tpetra_map(const MPI_Comm &communicator=MPI_COMM_WORLD, const bool overlapping=false) const
IndexSet tensor_product(const IndexSet &other) const
void add_index(const size_type index)
void write(std::ostream &out) const
void block_read(std::istream &in)
void add_ranges_internal(boost::container::small_vector< std::pair< size_type, size_type >, 200 > &tmp_ranges, const bool ranges_are_sorted)
IntervalIterator begin_intervals() const
void fill_binary_vector(VectorType &vector) const
std::vector< Range > ranges
void subtract_set(const IndexSet &other)
ElementIterator end() const
Threads::Mutex compress_mutex
IndexSet complete_index_set(const IndexSet::size_type N)
size_type index_space_size
Epetra_Map make_trilinos_map(const MPI_Comm &communicator=MPI_COMM_WORLD, const bool overlapping=false) const
void block_write(std::ostream &out) const
IndexSet get_view(const size_type begin, const size_type end) const
void add_range(const size_type begin, const size_type end)
size_type nth_index_in_set(const size_type local_index) const
bool is_ascending_and_one_to_one(const MPI_Comm &communicator) const
std::size_t memory_consumption() const
void print(StreamType &out) const
size_type nth_index_in_set_binary_search(const size_type local_index) const
types::global_dof_index size_type
void add_indices(const ForwardIterator &begin, const ForwardIterator &end)
IndexSet operator&(const IndexSet &is) const
#define DEAL_II_NAMESPACE_OPEN
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
#define DEAL_II_NAMESPACE_CLOSE
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
static ::ExceptionBase & ExcIndexNotPresent(size_type arg1)
static ::ExceptionBase & ExcInternalError()
static ::ExceptionBase & ExcDimensionMismatch(std::size_t arg1, std::size_t arg2)
#define Assert(cond, exc)
#define AssertIndexRange(index, range)
#define DeclException1(Exception1, type1, outsequence)
static ::ExceptionBase & ExcMessage(std::string arg1)
VectorType::value_type * begin(VectorType &V)
VectorType::value_type * end(VectorType &V)
TrilinosWrappers::types::int_type global_index(const Epetra_BlockMap &map, const ::types::global_dof_index i)
std::string compress(const std::string &input)
static const unsigned int invalid_unsigned_int
const types::global_dof_index invalid_dof_index
unsigned int global_dof_index
static bool end_compare(const IndexSet::Range &x, const IndexSet::Range &y)
static bool nth_index_compare(const IndexSet::Range &x, const IndexSet::Range &y)
friend bool operator==(const Range &range_1, const Range &range_2)
size_type nth_index_in_set
static std::size_t memory_consumption()
void serialize(Archive &ar, const unsigned int version)
friend bool operator<(const Range &range_1, const Range &range_2)
void advance(std::tuple< I1, I2 > &t, const unsigned int n)