MFEM  v4.2.0
Finite element discretization library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
table.hpp
Go to the documentation of this file.
1 // Copyright (c) 2010-2020, Lawrence Livermore National Security, LLC. Produced
2 // at the Lawrence Livermore National Laboratory. All Rights reserved. See files
3 // LICENSE and NOTICE for details. LLNL-CODE-806117.
4 //
5 // This file is part of the MFEM library. For more information and source code
6 // availability visit https://mfem.org.
7 //
8 // MFEM is free software; you can redistribute it and/or modify it under the
9 // terms of the BSD-3 license. We welcome feedback and contributions, see file
10 // CONTRIBUTING.md for details.
11 
12 #ifndef MFEM_TABLE
13 #define MFEM_TABLE
14 
15 // Data types for Table.
16 
17 #include "mem_alloc.hpp"
18 #include "array.hpp"
19 #include "globals.hpp"
20 #include <ostream>
21 #include <istream>
22 
23 namespace mfem
24 {
25 
26 /// Helper struct for defining a connectivity table, see Table::MakeFromList.
27 struct Connection
28 {
29  int from, to;
30  Connection() = default;
31  Connection(int from, int to) : from(from), to(to) {}
32 
33  bool operator== (const Connection &rhs) const
34  { return (from == rhs.from) && (to == rhs.to); }
35  bool operator< (const Connection &rhs) const
36  { return (from == rhs.from) ? (to < rhs.to) : (from < rhs.from); }
37 };
38 
39 
40 /** Data type Table. Table stores the connectivity of elements of TYPE I
41  to elements of TYPE II, for example, it may be Element-To-Face
42  connectivity table, etc. */
43 class Table
44 {
45 protected:
46  /// size is the number of TYPE I elements.
47  int size;
48 
49  /** Arrays for the connectivity information in the CSR storage.
50  I is of size "size+1", J is of size the number of connections
51  between TYPE I to TYPE II elements (actually stored I[size]). */
53 
54 public:
55  /// Creates an empty table
56  Table() { size = -1; I.Reset(); J.Reset(); }
57 
58  /// Copy constructor
59  Table(const Table &);
60 
61  /// Assignment operator: deep copy
62  Table& operator=(const Table &rhs);
63 
64  /// Create a table with an upper limit for the number of connections.
65  explicit Table (int dim, int connections_per_row = 3);
66 
67  /** Create a table from a list of connections, see MakeFromList(). */
68  Table(int nrows, Array<Connection> &list) : size(-1)
69  { I.Reset(); J.Reset(); MakeFromList(nrows, list); }
70 
71  /** Create a table with one entry per row with column indices given
72  by 'partitioning'. */
73  Table (int nrows, int *partitioning);
74 
75  /// Next 7 methods are used together with the default constructor
76  void MakeI (int nrows);
77  void AddAColumnInRow (int r) { I[r]++; }
78  void AddColumnsInRow (int r, int ncol) { I[r] += ncol; }
79  void MakeJ();
80  void AddConnection (int r, int c) { J[I[r]++] = c; }
81  void AddConnections (int r, const int *c, int nc);
82  void ShiftUpI();
83 
84  /// Set the size and the number of connections for the table.
85  void SetSize(int dim, int connections_per_row);
86 
87  /** Set the rows and the number of all connections for the table.
88  Does NOT initialize the whole array I ! (I[0]=0 and I[rows]=nnz only) */
89  void SetDims(int rows, int nnz);
90 
91  /// Returns the number of TYPE I elements.
92  inline int Size() const { return size; }
93 
94  /** Returns the number of connections in the table. If Finalize() is
95  not called, it returns the number of possible connections established
96  by the used constructor. Otherwise, it is exactly the number of
97  established connections before calling Finalize(). */
98  inline int Size_of_connections() const { return I[size]; }
99 
100  /** Returns index of the connection between element i of TYPE I and
101  element j of TYPE II. If there is no connection between element i
102  and element j established in the table, then the return value is -1. */
103  int operator() (int i, int j) const;
104 
105  /// Return row i in array row (the Table must be finalized)
106  void GetRow(int i, Array<int> &row) const;
107 
108  int RowSize(int i) const { return I[i+1]-I[i]; }
109 
110  const int *GetRow(int i) const { return J+I[i]; }
111  int *GetRow(int i) { return J+I[i]; }
112 
113  int *GetI() { return I; }
114  int *GetJ() { return J; }
115  const int *GetI() const { return I; }
116  const int *GetJ() const { return J; }
117 
118  Memory<int> &GetIMemory() { return I; }
119  Memory<int> &GetJMemory() { return J; }
120  const Memory<int> &GetIMemory() const { return I; }
121  const Memory<int> &GetJMemory() const { return J; }
122 
123  /// @brief Sort the column (TYPE II) indices in each row.
124  void SortRows();
125 
126  /// Replace the #I and #J arrays with the given @a newI and @a newJ arrays.
127  /** If @a newsize < 0, then the size of the Table is not modified. */
128  void SetIJ(int *newI, int *newJ, int newsize = -1);
129 
130  /** Establish connection between element i and element j in the table.
131  The return value is the index of the connection. It returns -1 if it
132  fails to establish the connection. Possibilities are there is not
133  enough memory on row i to establish connection to j, an attempt to
134  establish new connection after calling Finalize(). */
135  int Push( int i, int j );
136 
137  /** Finalize the table initialization. The function may be called
138  only once, after the table has been initialized, in order to compress
139  array J (by getting rid of -1's in array J). Calling this function
140  will "freeze" the table and function Push will work no more.
141  Note: The table is functional even without calling Finalize(). */
142  void Finalize();
143 
144  /** Create the table from a list of connections {(from, to)}, where 'from'
145  is a TYPE I index and 'to' is a TYPE II index. The list is assumed to be
146  sorted and free of duplicities, i.e., you need to call Array::Sort and
147  Array::Unique before calling this method. */
148  void MakeFromList(int nrows, const Array<Connection> &list);
149 
150  /// Returns the number of TYPE II elements (after Finalize() is called).
151  int Width() const;
152 
153  /// Call this if data has been stolen.
154  void LoseData() { size = -1; I.Reset(); J.Reset(); }
155 
156  /// Prints the table to stream out.
157  void Print(std::ostream & out = mfem::out, int width = 4) const;
158  void PrintMatlab(std::ostream & out) const;
159 
160  void Save(std::ostream &out) const;
161  void Load(std::istream &in);
162 
163  void Copy(Table & copy) const;
164  void Swap(Table & other);
165 
166  void Clear();
167 
168  long MemoryUsage() const;
169 
170  /// Destroys Table.
171  ~Table();
172 };
173 
174 /// Specialization of the template function Swap<> for class Table
175 template <> inline void Swap<Table>(Table &a, Table &b)
176 {
177  a.Swap(b);
178 }
179 
180 /// Transpose a Table
181 void Transpose (const Table &A, Table &At, int _ncols_A = -1);
182 Table * Transpose (const Table &A);
183 
184 /// Transpose an Array<int>
185 void Transpose(const Array<int> &A, Table &At, int _ncols_A = -1);
186 
187 /// C = A * B (as boolean matrices)
188 void Mult (const Table &A, const Table &B, Table &C);
189 Table * Mult (const Table &A, const Table &B);
190 
191 
192 /** Data type STable. STable is similar to Table, but it's for symmetric
193  connectivity, i.e. TYPE I is equivalent to TYPE II. In the first
194  dimension we put the elements with smaller index. */
195 class STable : public Table
196 {
197 public:
198  /// Creates table with fixed number of connections.
199  STable (int dim, int connections_per_row = 3);
200 
201  /** Returns index of the connection between element i of TYPE I and
202  element j of TYPE II. If there is no connection between element i
203  and element j established in the table, then the return value is -1. */
204  int operator() (int i, int j) const;
205 
206  /** Establish connection between element i and element j in the table.
207  The return value is the index of the connection. It returns -1 if it
208  fails to establish the connection. Possibilities are there is not
209  enough memory on row i to establish connection to j, an attempt to
210  establish new connection after calling Finalize(). */
211  int Push( int i, int j );
212 
213  /// Destroys STable.
214  ~STable() {}
215 };
216 
217 
218 class DSTable
219 {
220 private:
221  class Node
222  {
223  public:
224  Node *Prev;
225  int Column, Index;
226  };
227 
228  int NumRows, NumEntries;
229  Node **Rows;
230 #ifdef MFEM_USE_MEMALLOC
231  MemAlloc <Node, 1024> NodesMem;
232 #endif
233 
234  int Push_(int r, int c);
235  int Index(int r, int c) const;
236 
237 public:
238  DSTable(int nrows);
239  int NumberOfRows() const { return (NumRows); }
240  int NumberOfEntries() const { return (NumEntries); }
241  int Push(int a, int b)
242  { return ((a <= b) ? Push_(a, b) : Push_(b, a)); }
243  int operator()(int a, int b) const
244  { return ((a <= b) ? Index(a, b) : Index(b, a)); }
245  ~DSTable();
246 
248  {
249  private:
250  Node *n;
251  public:
252  RowIterator (const DSTable &t, int r) { n = t.Rows[r]; }
253  int operator!() { return (n != NULL); }
254  void operator++() { n = n->Prev; }
255  int Column() { return (n->Column); }
256  int Index() { return (n->Index); }
257  void SetIndex(int new_idx) { n->Index = new_idx; }
258  };
259 };
260 
261 }
262 
263 #endif
Table(int nrows, Array< Connection > &list)
Definition: table.hpp:68
int Push(int i, int j)
Definition: table.cpp:220
int * GetJ()
Definition: table.hpp:114
Memory< int > I
Definition: table.hpp:52
void SetSize(int dim, int connections_per_row)
Set the size and the number of connections for the table.
Definition: table.cpp:128
const Memory< int > & GetJMemory() const
Definition: table.hpp:121
void AddColumnsInRow(int r, int ncol)
Definition: table.hpp:78
int operator()(int i, int j) const
Definition: table.cpp:169
void MakeI(int nrows)
Next 7 methods are used together with the default constructor.
Definition: table.cpp:85
void Swap< Table >(Table &a, Table &b)
Specialization of the template function Swap&lt;&gt; for class Table.
Definition: table.hpp:175
void SortRows()
Sort the column (TYPE II) indices in each row.
Definition: table.cpp:200
bool operator<(const Connection &rhs) const
Definition: table.hpp:35
void Swap(Table &other)
Definition: table.cpp:395
void Mult(const Table &A, const Table &B, Table &C)
C = A * B (as boolean matrices)
Definition: table.cpp:476
void SetDims(int rows, int nnz)
Definition: table.cpp:144
int Push(int a, int b)
Definition: table.hpp:241
const int * GetI() const
Definition: table.hpp:115
void GetRow(int i, Array< int > &row) const
Return row i in array row (the Table must be finalized)
Definition: table.cpp:191
int Push(int i, int j)
Definition: table.cpp:570
void Save(std::ostream &out) const
Definition: table.cpp:348
void LoseData()
Call this if data has been stolen.
Definition: table.hpp:154
Connection()=default
const Memory< int > & GetIMemory() const
Definition: table.hpp:120
int Size_of_connections() const
Definition: table.hpp:98
RowIterator(const DSTable &t, int r)
Definition: table.hpp:252
void AddConnections(int r, const int *c, int nc)
Definition: table.cpp:108
int Width() const
Returns the number of TYPE II elements (after Finalize() is called).
Definition: table.cpp:301
int operator()(int i, int j) const
Definition: table.cpp:558
void Print(std::ostream &out=mfem::out, int width=4) const
Prints the table to stream out.
Definition: table.cpp:311
void MakeFromList(int nrows, const Array< Connection > &list)
Definition: table.cpp:280
Table & operator=(const Table &rhs)
Assignment operator: deep copy.
Definition: table.cpp:44
Memory< int > & GetJMemory()
Definition: table.hpp:119
void Clear()
Definition: table.cpp:381
double b
Definition: lissajous.cpp:42
void AddConnection(int r, int c)
Definition: table.hpp:80
long MemoryUsage() const
Definition: table.cpp:402
void Transpose(const Table &A, Table &At, int _ncols_A)
Transpose a Table.
Definition: table.cpp:414
int Size() const
Returns the number of TYPE I elements.
Definition: table.hpp:92
Connection(int from, int to)
Definition: table.hpp:31
void Reset()
Reset the memory to be empty, ensuring that Delete() will be a no-op.
void PrintMatlab(std::ostream &out) const
Definition: table.cpp:333
STable(int dim, int connections_per_row=3)
Creates table with fixed number of connections.
Definition: table.cpp:554
void SetIndex(int new_idx)
Definition: table.hpp:257
Memory< int > & GetIMemory()
Definition: table.hpp:118
Memory< int > J
Definition: table.hpp:52
void Finalize()
Definition: table.cpp:243
int size
size is the number of TYPE I elements.
Definition: table.hpp:47
void AddAColumnInRow(int r)
Definition: table.hpp:77
int * GetRow(int i)
Definition: table.hpp:111
Helper struct for defining a connectivity table, see Table::MakeFromList.
Definition: table.hpp:27
void ShiftUpI()
Definition: table.cpp:119
double a
Definition: lissajous.cpp:41
void Load(std::istream &in)
Definition: table.cpp:362
~Table()
Destroys Table.
Definition: table.cpp:408
void SetIJ(int *newI, int *newJ, int newsize=-1)
Replace the I and J arrays with the given newI and newJ arrays.
Definition: table.cpp:208
void MakeJ()
Definition: table.cpp:95
int dim
Definition: ex24.cpp:53
bool operator==(const Connection &rhs) const
Definition: table.hpp:33
const int * GetRow(int i) const
Definition: table.hpp:110
~STable()
Destroys STable.
Definition: table.hpp:214
int operator()(int a, int b) const
Definition: table.hpp:243
int NumberOfEntries() const
Definition: table.hpp:240
int * GetI()
Definition: table.hpp:113
int RowSize(int i) const
Definition: table.hpp:108
OutStream out(std::cout)
Global stream used by the library for standard output. Initially it uses the same std::streambuf as s...
Definition: globals.hpp:66
int NumberOfRows() const
Definition: table.hpp:239
void Copy(Table &copy) const
Definition: table.cpp:390
DSTable(int nrows)
Definition: table.cpp:583
const int * GetJ() const
Definition: table.hpp:116
Table()
Creates an empty table.
Definition: table.hpp:56