/*
  This file is part of p4est.
  p4est is a C library to manage a collection (a forest) of multiple
  connected adaptive quadtrees or octrees in parallel.

  Copyright (C) 2010 The University of Texas System
  Written by Carsten Burstedde, Lucas C. Wilcox, and Tobin Isaac

  p4est is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  p4est is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with p4est; if not, write to the Free Software Foundation, Inc.,
  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/

/** \page ghost The ghost layer
 *
 * An overview of the ghost layer functionalities.
 *
 * ## The basic idea and definition
 * Mesh-based computations may require access to neighboring elements.
 * An example of such a computation using a ghost layer can be found in
 * \ref steps/p4est_step3.c (2D) and \ref steps/p8est_step3.c (3D)
 * -- a simple parallel advection solver.
 * For parallel computations, we we need to ensure that neighboring mesh
 * elements, which are not local to the current process, become accessible
 * locally.
 * The need of process-neighboring mesh elements leads to the definition of the
 * ghost (a.k.a. halo) layer:
 * The ghost layer is the set of all remote, i.e. non-local, mesh elements
 * that are adjacent to the process-local mesh elements.
 * This data structure is ideally suited to establish the communication pattern
 * between mesh-adjacent parallel processes. The ghost layer contains all
 * information required to determine all sender-receiver pairs without
 * additional MPI communication. The pattern is necessarily symmetric: Each
 * sender of a pair is also a receiver and vice versa.
 *
 * ## Constructing the ghost layer
 * \b p4est provides the functions \ref p4est_ghost_new (2D), \ref
 * p8est_ghost_new (3D) to construct a ghost layer.
 * A ghost layer can be constructed from a valid \b input_p4est (cf. \ref
 * p4est_t (2D), \ref p8est_t (3D) and \ref p4est_is_valid (2D), \ref
 * p8est_is_valid (3D)). The forest does not need to be 2:1 balanced.
 *
 * The second and last required parameter to construct a ghost layer is a
 * \b btype (cf. \ref p4est_connect_type_t (2D), \ref p8est_connect_type_t (3D))
 * that specifies if the ghost layer should collect face adjacency, face and
 * edge adjacency in 3D, or full adjacency including corner neighbors.
 *
 * Ghost layer construction in 2D:
 *  > `ghost = p4est_ghost_new (input_p4est, btype)`
 *
 * The returned ghost layer object is explained in the following section.
 *
 * ## The ghost data structure
 * The ghost layer object (cf. \ref p4est_ghost_t (2D), \ref p8est_ghost_t (3D))
 * can be queried and searched without accessing the original \b input_p4est.
 * It is read-only immutable and must be destroyed when no longer needed
 * (cf. \ref p4est_ghost_destroy (2D), \ref p8est_ghost_destroy (3D)).
 *
 * ### Elements of the ghost layer
 * The ghost layer is a public struct with documented entries, most of them
 * arrays.
 * The [2D](\ref p4est_ghost_t) and [3D](\ref p8est_ghost_t) declarations are
 * structurally identical: Linear tree storage is dimension independent, and
 * ghost elements are ordered ascending just as mesh elements.
 * We may index into the element storage by window start and offset indices.
 * We may also use binary search in the linear order to find ghost elements.
 *
 * The elements of the ghost layer start with the
 * [mpisize](\ref p4est_ghost_t::mpisize) and
 * [num_trees](\ref p4est_ghost_t::num_trees).
 * They store the number of MPI ranks and the number of trees of the ghost layer.
 * Both elements are as in the [p4est](\ref p4est) that was used to construct
 * the ghost layer.
 *
 * The array [ghosts](\ref p4est_ghost_t::ghosts) stores the ghost elements that
 * form the ghost layer of the process-local elements.
 * The [quadrants](\ref p4est_quadrant_t) in the [ghosts](\ref p4est_ghost_t::ghosts)
 * array store their tree index and the local number in the owner's
 * numbering in [piggy3](\ref p4est_quadrant::p4est_quadrant_data::piggy3).
 * The [ghosts](\ref p4est_ghost_t::ghosts) array is windowed by the two arrays
 * [tree_offsets](\ref p4est_ghost_t::tree_offsets) and
 * [proc_offsets](\ref p4est_ghost_t::proc_offsets).
 * Therefore, the MPI rank and the tree number of each element
 * in [ghosts](\ref p4est_ghost_t::ghosts) can be deduced.
 * Naturally, some trees or processes may have zero ghost elements for a given
 * process, in which case the window has length zero.
 *
 * The [mirrors](\ref p4est_ghost_t::mirrors) array stores all local quadrants
 * that are ghosts to remote processes, sometimes called the (inside) parallel
 * boundary elements.
 * [ghosts](\ref p4est_ghost_t::ghosts) can be considered as the outside
 * parallel boundary elements.
 * One mirror quadrant may be ghost to more than one remote process.
 * Thus, the indexing structure is slightly less direct than for
 * [ghosts](\ref p4est_ghost_t::ghosts):
 * We have an array [mirror_proc_mirrors](\ref p4est_ghost_t::mirror_proc_mirrors)
 * that contains one set of indices into the
 * [mirrors](\ref p4est_ghost_t::mirrors) for each remote process.
 * The array [mirror_proc_offsets](\ref p4est_ghost_t::mirror_proc_offsets)
 * indexes into these sets, which vary in length by the remote process.
 * As for [ghosts](\ref p4est_ghost_t::ghosts), we have for
 * [mirrors](\ref p4est_ghost_t::mirrors) also an array with tree offsets,
 * namely the array
 * [mirror_tree_offsets](\ref p4est_ghost_t::mirror_tree_offsets).
 *
 * ## Find more information
 * For further elements of the ghost data structure see also \ref p4est_ghost_t
 * and \ref p8est_ghost_t and for parallel ghost data exchange functions see
 * the respective functions in \ref p4est_ghost.h (2D) and \ref p8est_ghost.h
 * (3D).
 *
 * ## Example of ghost usage
 * Besides the already mentioned parallel advection solver in
 * [2D](\ref steps/p4est_step3.c) and [3D](\ref steps/p8est_step3.c), one can
 * also find a simple synthetic usage examples of ghost in \ref
 * timings/timings2.c (2D) and \ref timings/timings3.c (3D).
 */

/** \example steps/p4est_step3.c
 *
 * This 2D example program (3D counterpart: \ref steps/p8est_step3.c) uses p4est
 * to solve a simple advection problem.
 * It is numerically very simple, and intended to demonstrate several methods of
 * interacting with the p4est data after it has been refined and partitioned.
 * It demonstrates the construction of [ghost](\ref ghost) layers (cf. also
 * \ref p4est_ghost.h) and communication of ghost-layer data,
 * and it demonstrates interacting with the quadrants and quadrant boundaries
 * through the \ref p4est_iterate routine (cf. \ref p4est_iterate.h).
 *
 * Usage:
 *    > `p4est_step3`
 */

/** \example steps/p8est_step3.c
 *
 * This 3D example program uses p4est to solve a simple advection problem.  It
 * is numerically very simple, and intended to demonstrate several methods of
 * interacting with the p4est data after it has been refined and partitioned.
 * It demonstrates the construction of [ghost](\ref ghost) layers (cf. also \ref
 * p8est_ghost.h) and communication of ghost-layer data, and it demonstrates
 * interacting with the quadrants and quadrant boundaries through the \ref
 * p8est_iterate routine (cf. \ref p8est_iterate.h).
 *
 * The header file \ref p4est_to_p8est.h defines preprocessor macros that map
 * 2D p4est routines and objects to their 3D p8est counterparts.  By including
 * this file and then including the source for the 2D example \ref
 * steps/p4est_step3.c, we convert the 2D example to a 3D example.
 *
 * It is entirely possible to write a 3D-only program without relying on this
 * mechanism.  In this case use the p8est* header files, functions, and data
 * structures.
 *
 * Usage:
 *    > `p8est_step3`
 */

/** \example timings/timings2.c
 *
 * This 2D example program (3D counterpart: \ref timings/timings3.c) calls
 * p4est's core routines.
 *
 * The example's purpose is to measure the runtime of p4est's core routines.
 *
 * Usage:
 *    > `p4est_timings <configuration> <level>`
 * possible configurations:
 *        * `unit`      Refinement on the unit square.
 *        * `periodic`  Refinement on the unit square with periodic b.c.
 *        * `three`     Refinement on a forest with three trees.
 *        * `moebius`   Refinement on a 5-tree Moebius band.
 *        * `star`      Refinement on a 6-tree star shaped domain.
 */

/** \example timings/timings3.c
 *
 * This 3D example program calls p4est's core routines.
 *
 * The example's purpose is to measure the runtime of p4est's core routines.
 *
 * Usage:
 *    > `p8est_timings <configuration> <level>`
 * possible configurations:
 *        * `unit`      Refinement on the unit cube.
 *        * `periodic`  Refinement on the unit cube with all-periodic b.c.
 *        * `rotwrap`   Refinement on the unit cube with weird periodic b.c.
 *        * `twocubes`  Refinement on a forest with two trees.
 *        * `rotcubes`  Refinement on a forest with six rotated trees.
 *        * `shell`     Refinement on a 24-tree spherical shell..
 */
