1/** \file
2 * \brief Declaration and implementation of EdgeArray class.
3 *
4 * \author Carsten Gutwenger
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#pragma once
33
34#include <ogdf/basic/Graph_d.h>
35
36
37namespace ogdf {
38
39
40//! Abstract base class for edge arrays.
41/**
42 * Defines the interface for event handling used by the Graph class.
43 * Use the parameterized class EdgeArray for creating edge arrays.
44 */
45class EdgeArrayBase {
46 /**
47 * Pointer to list element in the list of all registered edge
48 * arrays which references this array.
49 */
50 ListIterator<EdgeArrayBase*> m_it;
51
52public:
53 const Graph *m_pGraph; //!< The associated graph.
54
55 //! Initializes an edge array not associated with a graph.
56 EdgeArrayBase() : m_pGraph(nullptr) { }
57
58 //! Initializes an edge array associated with \p pG.
59 explicit EdgeArrayBase(const Graph *pG) : m_pGraph(pG) {
60 if(pG) m_it = pG->registerArray(this);
61 }
62
63 //! Moves edge array \p base to this edge array.
64 EdgeArrayBase(EdgeArrayBase &base) : m_it(base.m_it), m_pGraph(base.m_pGraph) {
65 if(m_pGraph) m_pGraph->moveRegisterArray(m_it, this);
66 base.m_pGraph = nullptr;
67 base.m_it = ListIterator<EdgeArrayBase*>();
68 }
69
70 // destructor, unregisters the array
71 virtual ~EdgeArrayBase() {
72 if (m_pGraph) m_pGraph->unregisterArray(m_it);
73 }
74
75 // event interface used by Graph
76 //! Virtual function called when table size has to be enlarged.
77 virtual void enlargeTable(int newTableSize) = 0;
78 //! Virtual function called when table has to be reinitialized.
79 virtual void reinit(int initTableSize) = 0;
80 //! Virtual function called when array is disconnected from the graph.
81 virtual void disconnect() = 0;
82
83 //! Associates the array with a new graph.
84 void reregister(const Graph *pG) {
85 if (m_pGraph) m_pGraph->unregisterArray(m_it);
86 if ((m_pGraph = pG) != nullptr) m_it = pG->registerArray(this);
87 }
88
89 //! Moves array registration from \p base to this array.
90 void moveRegister(EdgeArrayBase &base) {
91 if (m_pGraph) m_pGraph->unregisterArray(m_it);
92 m_pGraph = base.m_pGraph;
93 m_it = base.m_it;
94 base.m_pGraph = nullptr;
95 base.m_it = ListIterator<EdgeArrayBase*>();
96 if (m_pGraph != nullptr)
97 m_pGraph->moveRegisterArray(m_it, this);
98 }
99};
100
101//! Dynamic arrays indexed with edges.
102/**
103 * @ingroup graph-containers
104 *
105 * Edge arrays represent a mapping from edges to data of type \a T.
106 * They adjust their table size automatically when the graph grows.
107 *
108 * @warn_undef_behavior_array
109 *
110 * @tparam T is the element type.
111 */
112template<class T> class EdgeArray : private Array<T>, protected EdgeArrayBase {
113 T m_x; //!< The default value for array elements.
114
115public:
116 //! The type for array keys.
117 using key_type = edge;
118 //! The type for array entries.
119 using value_type = T;
120
121 //! The type for edge array iterators.
122 using iterator = internal::GraphArrayIterator<EdgeArray<T>>;
123 //! The type for edge array const iterators.
124 using const_iterator = internal::GraphArrayConstIterator<EdgeArray<T>>;
125
126
127 //! Constructs an empty edge array associated with no graph.
128 EdgeArray() : Array<T>(), EdgeArrayBase() { }
129
130 //! Constructs an edge array associated with \p G.
131 explicit EdgeArray(const Graph &G) : Array<T>(G.edgeArrayTableSize()), EdgeArrayBase(&G) { }
132
133 //! Constructs an edge array associated with \p G.
134 /**
135 * @param G is the associated graph.
136 * @param x is the default value for all array elements.
137 */
138 EdgeArray(const Graph &G, const T &x) :
139 Array<T>(0,G.edgeArrayTableSize()-1,x), EdgeArrayBase(&G), m_x(x) { }
140
141 //! Constructs an edge array that is a copy of \p A.
142 /**
143 * Associates the array with the same graph as \p A and copies all elements.
144 */
145 EdgeArray(const EdgeArray<T> &A) : Array<T>(A), EdgeArrayBase(A.m_pGraph), m_x(A.m_x) { }
146
147 //! Constructs an edge array containing the elements of \p A (move semantics).
148 /**
149 * Edge array \p A is empty afterwards and not associated with any graph.
150 */
151 EdgeArray(EdgeArray<T> &&A) : Array<T>(std::move(A)), EdgeArrayBase(A), m_x(A.m_x) { }
152
153
154 /**
155 * @name Access methods
156 * These methods provide access to elements, size, and corresponding graph.
157 */
158 //@{
159
160 //! Returns true iff the array is associated with a graph.
161 bool valid() const { return Array<T>::low() <= Array<T>::high(); }
162
163 //! Returns a pointer to the associated graph.
164 const Graph *graphOf() const {
165 return m_pGraph;
166 }
167
168 //! Returns a reference to the element with index \p e.
169 const T &operator[](edge e) const {
170 OGDF_ASSERT(e != nullptr);
171 OGDF_ASSERT(e->graphOf() == m_pGraph);
172 return Array<T>::operator [](e->index());
173 }
174
175 //! Returns a reference to the element with index \p e.
176 T &operator[](edge e) {
177 OGDF_ASSERT(e != nullptr);
178 OGDF_ASSERT(e->graphOf() == m_pGraph);
179 return Array<T>::operator [](e->index());
180 }
181
182 //! Returns a reference to the element with index \p e.
183 const T &operator()(edge e) const {
184 OGDF_ASSERT(e != nullptr);
185 OGDF_ASSERT(e->graphOf() == m_pGraph);
186 return Array<T>::operator [](e->index());
187 }
188
189 //! Returns a reference to the element with index \p e.
190 T &operator()(edge e) {
191 OGDF_ASSERT(e != nullptr);
192 OGDF_ASSERT(e->graphOf() == m_pGraph);
193 return Array<T>::operator [](e->index());
194 }
195
196 //! Returns a reference to the element with index edge of \p adj.
197 const T &operator[](adjEntry adj) const {
198 OGDF_ASSERT(adj != nullptr);
199 return Array<T>::operator [](adj->index() >> 1);
200 }
201
202 //! Returns a reference to the element with index edge of \p adj.
203 T &operator[](adjEntry adj) {
204 OGDF_ASSERT(adj != nullptr);
205 return Array<T>::operator [](adj->index() >> 1);
206 }
207
208 //! Returns a reference to the element with index edge of \p adj.
209 const T &operator()(adjEntry adj) const {
210 OGDF_ASSERT(adj != nullptr);
211 return Array<T>::operator [](adj->index() >> 1);
212 }
213
214 //! Returns a reference to the element with index edge of \p adj.
215 T &operator()(adjEntry adj) {
216 OGDF_ASSERT(adj != nullptr);
217 return Array<T>::operator [](adj->index() >> 1);
218 }
219
220 //! Returns a reference to the element with index \p index.
221 //! \attention Make sure that \p index is a valid index for an edge in the associated graph!
222 OGDF_DEPRECATED("Edge arrays should be indexed by an edge, not an integer index.")
223 const T &operator[](int index) const
224 { return Array<T>::operator [](index); }
225
226 //! Returns a reference to the element with index \p index.
227 //! \attention Make sure that \p index is a valid index for an edge in the associated graph!
228 OGDF_DEPRECATED("Edge arrays should be indexed by an edge, not an integer index.")
229 T &operator[](int index)
230 { return Array<T>::operator [](index); }
231
232 //@}
233 /**
234 * @name Iterators
235 * These methods return bidirectional iterators to elements in the array.
236 */
237 //@{
238
239 //! Returns an iterator to the first entry in the edge array.
240 /**
241 * If the edge array is empty, a null pointer iterator is returned.
242 */
243 iterator begin() { return iterator(m_pGraph->firstEdge(), this); }
244
245 //! Returns a const iterator to the first entry in the edge array.
246 /**
247 * If the edge array is empty, a null pointer iterator is returned.
248 */
249 const_iterator begin() const { return const_iterator(m_pGraph->firstEdge(), this); }
250
251 //! Returns a const iterator to the first entry in the edge array.
252 /**
253 * If the edge array is empty, a null pointer iterator is returned.
254 */
255 const_iterator cbegin() const { return const_iterator(m_pGraph->firstEdge(), this); }
256
257 //! Returns an iterator to one-past-last entry in the edge array.
258 /**
259 * This is always a null pointer iterator.
260 */
261 iterator end() { return iterator(nullptr, this); }
262
263 //! Returns a const iterator to one-past-last entry in the edge array.
264 /**
265 * This is always a null pointer iterator.
266 */
267 const_iterator end() const { return const_iterator(nullptr, this); }
268
269 //! Returns a const iterator to one-past-last entry in the edge array.
270 /**
271 * This is always a null pointer iterator.
272 */
273 const_iterator cend() const { return const_iterator(nullptr, this); }
274
275 //@}
276 /**
277 * @name Initialization and assignment
278 * These methods can be used to reinitialize the array, or to initialize all elements with a given value.
279 */
280 //@{
281
282 //! Reinitializes the array. Associates the array with no graph.
283 void init() {
284 Array<T>::init(); reregister(nullptr);
285 }
286
287 //! Reinitializes the array. Associates the array with \p G.
288 void init(const Graph &G) {
289 Array<T>::init(G.edgeArrayTableSize()); reregister(&G);
290 }
291
292 //! Reinitializes the array. Associates the array with \p G.
293 /**
294 * @param G is the associated graph.
295 * @param x is the default value.
296 */
297 void init(const Graph &G, const T &x) {
298 Array<T>::init(0,G.edgeArrayTableSize()-1, m_x = x); reregister(&G);
299 }
300
301 //! Sets all array elements to \p x.
302 void fill(const T &x) {
303 int high = m_pGraph->maxEdgeIndex();
304 if(high >= 0)
305 Array<T>::fill(0,high,x);
306 }
307
308 //! Assignment operator.
309 EdgeArray<T> &operator=(const EdgeArray<T> &a) {
310 Array<T>::operator=(a);
311 m_x = a.m_x;
312 reregister(a.m_pGraph);
313 return *this;
314 }
315
316 //! Assignment operator (move semantics).
317 /**
318 * Edge array \p a is empty afterwards and not associated with any graph.
319 */
320 EdgeArray<T> &operator=(EdgeArray<T> &&a) {
321 Array<T>::operator=(std::move(a));
322 m_x = a.m_x;
323 moveRegister(a);
324 return *this;
325 }
326
327
328 //@}
329 /**
330 * @name Helper functions
331 * These methods are mainly intended for internal use.
332 */
333 //@{
334
335 static key_type findSuccKey(key_type key) { return key->succ(); }
336 static key_type findPredKey(key_type key) { return key->pred(); }
337
338 //@}
339
340private:
341 virtual void enlargeTable(int newTableSize) {
342 Array<T>::resize(newTableSize,m_x);
343 }
344
345 virtual void reinit(int initTableSize) {
346 Array<T>::init(0,initTableSize-1,m_x);
347 }
348
349 virtual void disconnect() {
350 Array<T>::init();
351 m_pGraph = nullptr;
352 }
353
354 OGDF_NEW_DELETE
355};
356
357//! Bucket function for edges.
358/**
359 * The bucket of an edge is stored in an edge array which is passed
360 * by the user at construction; only a pointer is stored to that array.
361 */
362class OGDF_EXPORT BucketEdgeArray : public BucketFunc<edge>
363{
364 const EdgeArray<int> *m_pEdgeArray; //!< Pointer to edge array.
365
366public:
367 //! Constructs a bucket function.
368 /**
369 * @param edgeArray contains the buckets for the edges. May not be deleted
370 * as long as the bucket function is used.
371 */
372 explicit BucketEdgeArray(const EdgeArray<int> &edgeArray) : m_pEdgeArray(&edgeArray) { }
373
374 //! Returns bucket of edge \p e.
375 int getBucket(const edge &e) override { return (*m_pEdgeArray)[e]; }
376};
377
378}
379