%-------------------------------------------------------------------------------

% This file is part of Code_Saturne, a general-purpose CFD tool.
%
% Copyright (C) 1998-2019 EDF S.A.
%
% This program 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.
%
% This program 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
% this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
% Street, Fifth Floor, Boston, MA 02110-1301, USA.

%-------------------------------------------------------------------------------

\section{Common construct types}

In this chapter, commonly-used construct types whose use may require specific
explainations or recommendations are described.

\subsection{Indexed arrays}

In many instance data such as mesh connectivity requires managing a variable
number of entries per data element. This is for example the case of
$faces \rightarrow vertices$ connectivity. The average number of vertices
per face is usually quite low, but the maximum number may be significantly
higher, so using an array with regular stride would be very inefficient
for some data sets.

A common solution to this problem is to use indexed arrays, in which an array
containing data is supplemented by a second array containing the start indexes
of entries in the data array for each element.

These arrays are mainly used in the C parts of the \CS source, though
the interior and boundary $faces \rightarrow vertices$ connectivity is also
visible in the Fortran code. Remember that in Fortran code, arrays
are always one-based (i.e. the first element of an array has index 1),
while in C code, the natural indexing is zero-based, but one-based
indexing may also be used for arrays visible from Fortran code, or for arrays
using global numbers. In \CS, zero-based indexes are often used with
one-based data, for example when defining element connectivities,
where element ids are usually one-based\footnote{both as a convention
to simplify mapping to Fortran, and in the case of $cells \rightarrow faces$
connectivities, so as to use the sign to determine face orientation}.
For C code, when there are no mapping constraints due to Fortran,
the recommendations are the following:

\begin{itemize}
\item local index arrays should be zero-based.
\item global index arrays should be one-based. This should only concern
      indexes read from or written to file.
\item when containing cell, face, or vertex connectivity information, data
      arrays may be either zero or one-based: zero based arrays are less
      error-prone so they should be preferred, but where element ids may be
      signed (so as to convey orientation information), one-based arrays are
      necessary. In a given structure, consistency is recommended, so if
      a $cells \rightarrow faces$ connectivity requires one-based face numbers,
      an associated $faces \rightarrow vertices$ connectivity may also use
      one-based vertex numbers, even though vertices have no orientation.
\end{itemize}

Let us consider an array \texttt{array\_data} indexed by a zero-based
\texttt{array\_index} array. The values of \texttt{array\_data} associated with
element $i_e$, are the values ranging from indexes $i_{start}=i_e$
included to $i_{end}=i_e+1$ excluded (past-the-end index).

The number of values associated with $i_e$ is determined by:
par $array\_index[i_e+1] - array\_index[i_e]$, whether the index
is zero-based or one-based.

For an indexed array of $n$ elements, the size the index array should thus
be equal to $n+1$ (and not $n$ as would be the case for regular 1-d or
strided arrays), and the total size of \texttt{array\_data} is equal to
\texttt{array\_index[n]} for a zero-based index, or
\texttt{array\_index[n] - array\_index[0]} in general.

\subsubsection{similar popular data structures}

Readers familiar with \emph{Compressed Sparse Row} or similar matrix or
graph representations may already have noted the similarity with
the indexed arrays described here. In the case of CSR matrix structures,
2 data arrays are often associated with 1 row index: one array definining
the column indices, and a second one defining the associated values.

This is in reality no different than using an indexed array as described here
to define a $faces \rightarrow vertices$ connectivity, and also associating
data (for example coordinates) to vertices.

In \CS, matrix non-diagonal terms usually correspond to cell faces,
and the CSR matrix representation is very similar to that of a
$cells \rightarrow faces$ connectivity, except for the fact that a
standard CSR representation uses only ``unsigned'' column ids, whereas
face numbers may be signed in the matching mesh representation so as
to convey orientation (an alternative solution would be to use
a separate array for orientation, in which case the similarity to CSR
would be complete).

\subsubsection{Indexed Array Example}

We illustrate the use of an indexed array to define a $faces \rightarrow
vertices$ connectivity for a simple surface mesh:

\newsavebox{\meshexmpl}
\setlength{\unitlength}{1.5cm}
\savebox{\meshexmpl}(4.3,2.5){%
  \put(0,0){\framebox(2,2){}}
  \put(0,1){\line(1,0){4}}
  \put(2,0){\line(2,1){2}}
  \put(4,1){\line(-2,1){2}}
  \put(-0.15,-0.15){\makebox(0,0){1}}
  \put(1.85,-0.15){\makebox(0,0){2}}
  \put(-0.15,0.85){\makebox(0,0){3}}
  \put(1.85,0.85){\makebox(0,0){4}}
  \put(-0.15,1.85){\makebox(0,0){5}}
  \put(1.85,1.85){\makebox(0,0){6}}
  \put(4.15,0.95){\makebox(0,0){7}}
  \put(0.95,0.55){\makebox(0,0){1}}
  \put(2.45,0.55){\makebox(0,0){2}}
  \put(0.95,1.45){\makebox(0,0){3}}
  \put(2.45,1.45){\makebox(0,0){4}}
}

\begin{center}
  \begin{picture}(4.3,2.5)
    \usebox{\meshexmpl}\label{fig:indexed_surf_mesh}
  \end{picture}
\end{center}

The matching arrays are:

\newsavebox{\titletab}
\setlength{\unitlength}{4cm}
\savebox{\titletab}(0,1.3){%
  \put(0.25,0.20){\makebox(0,0){Vertex numbers}}
  \put(0.25,0.10){\makebox(0,0){array}}

  \put(0.25,-0.60){\makebox(0,0){Faces index}}
  \put(0.25,-0.70){\makebox(0,0){array}}
}

\newsavebox{\tableexu}
\setlength{\unitlength}{4cm}
\savebox{\tableexu}(3,1.3){%
  \put(0,0){\framebox(2.8,0.3){}}
  \put(0.1,0.15){\makebox(0,0){1}}\put(0.20,0){\line(0,1){0.3}}
  \put(0.3,0.15){\makebox(0,0){2}}\put(0.40,0){\line(0,1){0.3}}
  \put(0.5,0.15){\makebox(0,0){4}}\put(0.60,0){\line(0,1){0.3}}
  \put(0.7,0.15){\makebox(0,0){3}}\put(0.79,0){\line(0,1){0.3}}\put(0.81,0){\line(0,1){0.3}}
  \put(0.9,0.15){\makebox(0,0){2}}\put(1.00,0){\line(0,1){0.3}}
  \put(1.1,0.15){\makebox(0,0){7}}\put(1.20,0){\line(0,1){0.3}}
  \put(1.3,0.15){\makebox(0,0){4}}\put(1.39,0){\line(0,1){0.3}}\put(1.41,0){\line(0,1){0.3}}
  \put(1.5,0.15){\makebox(0,0){3}}\put(1.60,0){\line(0,1){0.3}}
  \put(1.7,0.15){\makebox(0,0){4}}\put(1.80,0){\line(0,1){0.3}}
  \put(1.9,0.15){\makebox(0,0){6}}\put(2.00,0){\line(0,1){0.3}}
  \put(2.1,0.15){\makebox(0,0){5}}\put(2.19,0){\line(0,1){0.3}}\put(2.21,0){\line(0,1){0.3}}
  \put(2.3,0.15){\makebox(0,0){4}}\put(2.40,0){\line(0,1){0.3}}
  \put(2.5,0.15){\makebox(0,0){7}}\put(2.60,0){\line(0,1){0.3}}
  \put(2.7,0.15){\makebox(0,0){6}}\put(2.82,0){\dashbox{0.01}(0.2,0.3)}

  \put(0.1,-0.10){\makebox(0,0){0}}
  \put(0.3,-0.10){\makebox(0,0){1}}
  \put(0.5,-0.10){\makebox(0,0){2}}
  \put(0.7,-0.10){\makebox(0,0){3}}
  \put(0.9,-0.10){\makebox(0,0){4}}
  \put(1.1,-0.10){\makebox(0,0){5}}
  \put(1.3,-0.10){\makebox(0,0){6}}
  \put(1.5,-0.10){\makebox(0,0){7}}
  \put(1.7,-0.10){\makebox(0,0){8}}
  \put(1.9,-0.10){\makebox(0,0){9}}
  \put(2.1,-0.10){\makebox(0,0){10}}
  \put(2.3,-0.10){\makebox(0,0){11}}
  \put(2.5,-0.10){\makebox(0,0){12}}
  \put(2.7,-0.10){\makebox(0,0){13}}
  \put(2.9,-0.10){\makebox(0,0){14}}

  \put(1.0,-0.8){\framebox(1.0,0.3){}}
  \put(1.1,-0.65){\makebox(0,0){0} }\put(1.20,-0.80){\line(0,1){0.3}}
  \put(1.3,-0.65){\makebox(0,0){4} }\put(1.40,-0.80){\line(0,1){0.3}}
  \put(1.5,-0.65){\makebox(0,0){7} }\put(1.60,-0.80){\line(0,1){0.3}}
  \put(1.7,-0.65){\makebox(0,0){11}}\put(1.80,-0.80){\line(0,1){0.3}}
  \put(1.9,-0.65){\makebox(0,0){14}}

  \put(1.1,-0.90){\makebox(0,0){0}}
  \put(1.3,-0.90){\makebox(0,0){1}}
  \put(1.5,-0.90){\makebox(0,0){2}}
  \put(1.7,-0.90){\makebox(0,0){3}}
  \put(1.9,-0.90){\makebox(0,0){4}}

  \dashline{0.02}(1.1,-0.48)(0.1,-0.15)
  \dashline{0.02}(1.3,-0.48)(0.9,-0.15)
  \dashline{0.02}(1.5,-0.48)(1.5,-0.15)
  \dashline{0.02}(1.7,-0.48)(2.3,-0.15)
  \dashline{0.02}(1.9,-0.48)(2.9,-0.15)
}

\noindent
\begin{minipage}{2cm}
  \begin{picture}(0,1.3)
    \usebox{\titletab}
  \end{picture}
\end{minipage}\hspace{0.5cm}
\begin{minipage}{12.2cm}
  \begin{picture}(3,1.3)
    \usebox{\tableexu}
  \end{picture}
\end{minipage}

Let us now assume that we need to keep track of the association between
faces and some specific areas of the mesh. Continuing on the same example,
consider a single group of interest, with id 1, with which the left part
of the mesh (i.e. on the quadrangles), is associated.
The $faces \rightarrow zones$ connectivity is the defined as follows:

\newsavebox{\tableexd}
\setlength{\unitlength}{4cm}
\savebox{\tableexd}(3,1.3){%
  \put(1.2,0){\framebox(0.4,0.3){}}
  \put(1.3,0.15){\makebox(0,0){1}}\put(1.39,0){\line(0,1){0.3}}\put(1.41,0){\line(0,1){0.3}}
  \put(1.5,0.15){\makebox(0,0){1}}\put(1.62,0){\dashbox{0.01}(0.2,0.3)}

  \put(1.3,-0.10){\makebox(0,0){0}}
  \put(1.5,-0.10){\makebox(0,0){1}}
  \put(1.7,-0.10){\makebox(0,0){2}}

  \put(1.0,-0.8){\framebox(1.0,0.3){}}
  \put(1.1,-0.65){\makebox(0,0){0} }\put(1.20,-0.80){\line(0,1){0.3}}
  \put(1.3,-0.65){\makebox(0,0){1} }\put(1.40,-0.80){\line(0,1){0.3}}
  \put(1.5,-0.65){\makebox(0,0){1} }\put(1.60,-0.80){\line(0,1){0.3}}
  \put(1.7,-0.65){\makebox(0,0){2} }\put(1.80,-0.80){\line(0,1){0.3}}
  \put(1.9,-0.65){\makebox(0,0){2} }

  \put(1.1,-0.90){\makebox(0,0){0}}
  \put(1.3,-0.90){\makebox(0,0){1}}
  \put(1.5,-0.90){\makebox(0,0){2}}
  \put(1.7,-0.90){\makebox(0,0){3}}
  \put(1.9,-0.90){\makebox(0,0){4}}

 \dashline{0.02}(1.1,-0.48)(1.3,-0.15)
 \dashline{0.02}(1.5,-0.48)(1.5,-0.15)
}

\noindent
\begin{minipage}{2cm}
  \begin{picture}(0,1.3)
    \usebox{\titletab}
  \end{picture}
\end{minipage}\hspace{0.5cm}
\begin{minipage}{12cm}
  \begin{picture}(3,1.3)
    \usebox{\tableexd}
  \end{picture}
\end{minipage}

This example, in which the right-side elements (i.e. the triangles)
belong to no specified group illustrates how elements with no
associated data are handled: their index and that of the following
element is simply the same.