From 2e36feaaeceb1eb818b724e1b24048109074a82c Mon Sep 17 00:00:00 2001 From: Timo Heister Date: Mon, 24 Jun 2013 08:25:48 +0000 Subject: [PATCH] add CellId CellAccessor::id() git-svn-id: https://svn.dealii.org/trunk@29859 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/doc/news/changes.h | 7 ++ deal.II/include/deal.II/grid/cell_id.h | 118 +++++++++++++++++++ deal.II/include/deal.II/grid/tria_accessor.h | 46 +++++++- 3 files changed, 170 insertions(+), 1 deletion(-) create mode 100644 deal.II/include/deal.II/grid/cell_id.h diff --git a/deal.II/doc/news/changes.h b/deal.II/doc/news/changes.h index 621adb6962..efcb9bcf2a 100644 --- a/deal.II/doc/news/changes.h +++ b/deal.II/doc/news/changes.h @@ -147,6 +147,13 @@ this function.
    +
  1. New: CellAccessor::id() that returns a unique CellId that +also works in parallel computations (where level and index is not +useful). +
    +(Timo Heister, 2013/06/24) +
    2. +
  2. New: added ConstantTensorFunction and ZeroTensorFunction to provide a tensor valued analogue to ConstantFunction and ZeroFunction.
    diff --git a/deal.II/include/deal.II/grid/cell_id.h b/deal.II/include/deal.II/grid/cell_id.h new file mode 100644 index 0000000000..5dee60740f --- /dev/null +++ b/deal.II/include/deal.II/grid/cell_id.h @@ -0,0 +1,118 @@ +//--------------------------------------------------------------------------- +// $Id: tria_accessor.h 29697 2013-05-31 21:53:39Z bangerth $ +// +// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 by the deal.II authors +// +// This file is subject to QPL and may not be distributed +// without copyright and license information. Please refer +// to the file deal.II/doc/license.html for the text and +// further information on this license. +// +//--------------------------------------------------------------------------- +#ifndef __deal2__cell_id_h +#define __deal2__cell_id_h + +DEAL_II_NAMESPACE_OPEN + + +/** + * A class to represent a unique ID for a cell in a Triangulation. + * This class stores the index of the coarse cell together with the + * information on how to reach the cell from that coarse cell (which + * child index to take on each level). The internal representation + * is not exposed on purpose. + * + * TODO: does it make sense to implement a more efficient representation + * (internally and/or as a string)? If yes, something like a 64bit int + * as in p4est would be a good option. + */ +class CellId +{ +public: + /** + * construct CellId with a given coarse_cell_index and list of child indices + */ + explicit CellId(unsigned int coarse_cell_id_, std::vector id_) + : coarse_cell_id(coarse_cell_id_), id(id_) + {} + + /** + * construct an empty CellId. + */ + CellId() + : coarse_cell_id(-1) + {} + + /** + * compare two CellIds + */ + bool operator== (const CellId & other) const; + + /** + * compare two CellIds + */ + bool operator!= (const CellId & other) const; + + + friend std::istream& operator>> (std::istream& is, CellId& cid); + friend std::ostream& operator<< (std::ostream& os, const CellId& cid); +private: + unsigned int coarse_cell_id; + std::vector id; +}; + +/** + * output CellId into a stream + */ +inline std::ostream& operator<< (std::ostream& os, const CellId& cid) +{ + os << cid.coarse_cell_id << '_' << cid.id.size() << ':'; + for (unsigned int i=0;i(cid.id[i]); + return os; +} + +/** + * read CellId from a stream + */ +inline std::istream& operator>> (std::istream& is, CellId& cid) +{ + is >> cid.coarse_cell_id; + char dummy; + is >> dummy; + Assert(dummy=='_', ExcMessage("invalid CellId")); + unsigned int idsize; + is >> idsize; + is >> dummy; + Assert(dummy==':', ExcMessage("invalid CellId")); + + char value; + cid.id.clear(); + for (unsigned int i=0;i> value; + cid.id.push_back(value-'0'); + } + return is; +} + +inline bool +CellId::operator== (const CellId & other) const +{ + if (this->coarse_cell_id != other.coarse_cell_id) + return false; + return id == other.id; +} + +/** + * + */ +inline bool +CellId::operator!= (const CellId & other) const +{ + return !(*this == other); +} + +DEAL_II_NAMESPACE_CLOSE + +#endif diff --git a/deal.II/include/deal.II/grid/tria_accessor.h b/deal.II/include/deal.II/grid/tria_accessor.h index 349756f612..6bb84f8646 100644 --- a/deal.II/include/deal.II/grid/tria_accessor.h +++ b/deal.II/include/deal.II/grid/tria_accessor.h @@ -19,6 +19,7 @@ #include #include #include +#include namespace std @@ -2821,7 +2822,8 @@ public: /** * Return an iterator to the - * parent. + * parent. Throws an exception if this cell has no parent, i.e. has + * level 0. */ TriaIterator > parent () const; @@ -2990,6 +2992,15 @@ public: void set_neighbor (const unsigned int i, const TriaIterator > &pointer) const; + /** + * Return a unique ID for the current cell. This ID is constructed from the + * path in the hierarchy from the coarse father cell and works correctly + * in parallel computations. + * + * Note: This operation takes O(log(level)) time. + */ + CellId id() const; + /** * @} */ @@ -3170,6 +3181,39 @@ CellAccessor (const TriaAccessor &) "the conversion is not valid in the current context.")); } +template +CellId +CellAccessor::id() const +{ + std::vector id(this->level(), -1); + unsigned int coarse_index; + + CellAccessor ptr = *this; + while (ptr.level()>0) + { + // find the 'v'st child of our parent we are + unsigned char v=-1; + for (unsigned int c=0;cn_children();++c) + { + if (ptr.parent()->child_index(c)==ptr.index()) + { + v = c; + break; + } + } + + Assert(v!=-1, ExcInternalError()); + id[ptr.level()-1] = v; + + ptr.copy_from( *(ptr.parent())); + } + + Assert(ptr.level()==0, ExcInternalError()); + coarse_index = ptr.index(); + + return CellId(coarse_index, id); +} + #ifndef DOXYGEN -- 2.39.5