MFEM  v4.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, Lawrence Livermore National Security, LLC. Produced at
2 // the Lawrence Livermore National Laboratory. LLNL-CODE-443211. All Rights
3 // reserved. See file COPYRIGHT for details.
4 //
5 // This file is part of the MFEM library. For more information and source code
6 // availability see http://mfem.org.
7 //
8 // MFEM is free software; you can redistribute it and/or modify it under the
9 // terms of the GNU Lesser General Public License (as published by the Free
10 // Software Foundation) version 2.1 dated February 1999.
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 
196 class STable : public Table
197 {
198 public:
199  /// Creates table with fixed number of connections.
200  STable (int dim, int connections_per_row = 3);
201 
202  /** Returns index of the connection between element i of TYPE I and
203  element j of TYPE II. If there is no connection between element i
204  and element j established in the table, then the return value is -1. */
205  int operator() (int i, int j) const;
206 
207  /** Establish connection between element i and element j in the table.
208  The return value is the index of the connection. It returns -1 if it
209  fails to establish the connection. Possibilities are there is not
210  enough memory on row i to establish connection to j, an attempt to
211  establish new connection after calling Finalize(). */
212  int Push( int i, int j );
213 
214  /// Destroys STable.
215  ~STable() {}
216 };
217 
218 
219 class DSTable
220 {
221 private:
222  class Node
223  {
224  public:
225  Node *Prev;
226  int Column, Index;
227  };
228 
229  int NumRows, NumEntries;
230  Node **Rows;
231 #ifdef MFEM_USE_MEMALLOC
232  MemAlloc <Node, 1024> NodesMem;
233 #endif
234 
235  int Push_(int r, int c);
236  int Index(int r, int c) const;
237 
238 public:
239  DSTable(int nrows);
240  int NumberOfRows() const { return (NumRows); }
241  int NumberOfEntries() const { return (NumEntries); }
242  int Push(int a, int b)
243  { return ((a <= b) ? Push_(a, b) : Push_(b, a)); }
244  int operator()(int a, int b) const
245  { return ((a <= b) ? Index(a, b) : Index(b, a)); }
246  ~DSTable();
247 
249  {
250  private:
251  Node *n;
252  public:
253  RowIterator (const DSTable &t, int r) { n = t.Rows[r]; }
254  int operator!() { return (n != NULL); }
255  void operator++() { n = n->Prev; }
256  int Column() { return (n->Column); }
257  int Index() { return (n->Index); }
258  void SetIndex(int new_idx) { n->Index = new_idx; }
259  };
260 };
261 
262 }
263 
264 #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:242
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:253
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
int dim
Definition: ex3.cpp:48
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
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:258
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
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
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:215
int operator()(int a, int b) const
Definition: table.hpp:244
int NumberOfEntries() const
Definition: table.hpp:241
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:64
int NumberOfRows() const
Definition: table.hpp:240
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