6 * $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration and implementation of EdgeArray class.
12 * \author Carsten Gutwenger
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
47 #ifndef OGDF_EDGE_ARRAY_H
48 #define OGDF_EDGE_ARRAY_H
51 #include <ogdf/basic/Graph_d.h>
57 //! Abstract base class for edge arrays.
59 * Defines the interface for event handling used by the Graph class.
60 * Use the parameterized class EdgeArray for creating edge arrays.
64 * Pointer to list element in the list of all registered edge
65 * arrays which references this array.
67 ListIterator
<EdgeArrayBase
*> m_it
;
70 const Graph
*m_pGraph
; //!< The associated graph.
72 //! Initializes an edge array not associated with a graph.
73 EdgeArrayBase() : m_pGraph(0) { }
74 //! Initializes an edge array associated with \a pG.
75 EdgeArrayBase(const Graph
*pG
) : m_pGraph(pG
) {
76 if(pG
) m_it
= pG
->registerArray(this);
79 // destructor, unregisters the array
80 virtual ~EdgeArrayBase() {
81 if (m_pGraph
) m_pGraph
->unregisterArray(m_it
);
84 // event interface used by Graph
85 //! Virtual function called when table size has to be enlarged.
86 virtual void enlargeTable(int newTableSize
) = 0;
87 //! Virtual function called when table has to be reinitialized.
88 virtual void reinit(int initTableSize
) = 0;
89 //! Virtual function called when array is disconnected from the graph.
90 virtual void disconnect() = 0;
92 //! Associates the array with a new graph.
93 void reregister(const Graph
*pG
) {
94 if (m_pGraph
) m_pGraph
->unregisterArray(m_it
);
95 if ((m_pGraph
= pG
) != 0) m_it
= pG
->registerArray(this);
97 }; // class EdgeArrayBase
100 //! Dynamic arrays indexed with edges.
102 * Edge arrays represent a mapping from edges to data of type \a T.
103 * They adjust their table size automatically when the graph grows.
105 * @tparam T is the element type.
107 template<class T
> class EdgeArray
: private Array
<T
>, protected EdgeArrayBase
{
108 T m_x
; //!< The default value for array elements.
111 //! Constructs an empty edge array associated with no graph.
112 EdgeArray() : Array
<T
>(), EdgeArrayBase() { }
113 //! Constructs an edge array associated with \a G.
114 EdgeArray(const Graph
&G
) : Array
<T
>(G
.edgeArrayTableSize()), EdgeArrayBase(&G
) { }
115 //! Constructs an edge array associated with \a G.
117 * @param G is the associated graph.
118 * @param x is the default value for all array elements.
120 EdgeArray(const Graph
&G
, const T
&x
) :
121 Array
<T
>(0,G
.edgeArrayTableSize()-1,x
), EdgeArrayBase(&G
), m_x(x
) { }
122 //! Constructs an edge array that is a copy of \a A.
124 * Associates the array with the same graph as \a A and copies all elements.
126 EdgeArray(const EdgeArray
<T
> &A
) : Array
<T
>(A
), EdgeArrayBase(A
.m_pGraph
), m_x(A
.m_x
) { }
128 //! Returns true iff the array is associated with a graph.
129 bool valid() const { return (Array
<T
>::low() <= Array
<T
>::high()); }
131 //! Returns a pointer to the associated graph.
132 const Graph
*graphOf() const {
136 //! Returns a reference to the element with index \a e.
137 const T
&operator[](edge e
) const {
138 OGDF_ASSERT(e
!= 0 && e
->graphOf() == m_pGraph
)
139 return Array
<T
>::operator [](e
->index());
142 //! Returns a reference to the element with index \a e.
143 T
&operator[](edge e
) {
144 OGDF_ASSERT(e
!= 0 && e
->graphOf() == m_pGraph
)
145 return Array
<T
>::operator [](e
->index());
148 //! Returns a reference to the element with index edge of \a adj.
149 const T
&operator[](adjEntry adj
) const {
150 OGDF_ASSERT(adj
!= 0)
151 return Array
<T
>::operator [](adj
->index() >> 1);
154 //! Returns a reference to the element with index edge of \a adj.
155 T
&operator[](adjEntry adj
) {
156 OGDF_ASSERT(adj
!= 0)
157 return Array
<T
>::operator [](adj
->index() >> 1);
160 //! Returns a reference to the element with index \a index.
162 * \attention Make sure that \a index is a valid index for an edge
163 * in the associated graph!
165 const T
&operator[](int index
) const {
166 return Array
<T
>::operator [](index
);
169 //! Returns a reference to the element with index \a index.
171 * \attention Make sure that \a index is a valid index for an edge
172 * in the associated graph!
174 T
&operator[](int index
) {
175 return Array
<T
>::operator [](index
);
178 //! Assignment operator.
179 EdgeArray
<T
> &operator=(const EdgeArray
<T
> &a
) {
180 Array
<T
>::operator =(a
);
182 reregister(a
.m_pGraph
);
186 //! Reinitializes the array. Associates the array with no graph.
188 Array
<T
>::init(); reregister(0);
191 //! Reinitializes the array. Associates the array with \a G.
192 void init(const Graph
&G
) {
193 Array
<T
>::init(G
.edgeArrayTableSize()); reregister(&G
);
196 //! Reinitializes the array. Associates the array with \a G.
198 * @param G is the associated graph.
199 * @param x is the default value.
201 void init(const Graph
&G
, const T
&x
) {
202 Array
<T
>::init(0,G
.edgeArrayTableSize()-1, m_x
= x
); reregister(&G
);
205 //! Sets all array elements to \a x.
206 void fill(const T
&x
) {
207 int high
= m_pGraph
->maxEdgeIndex();
209 Array
<T
>::fill(0,high
,x
);
213 virtual void enlargeTable(int newTableSize
) {
214 Array
<T
>::grow(newTableSize
-Array
<T
>::size(),m_x
);
217 virtual void reinit(int initTableSize
) {
218 Array
<T
>::init(0,initTableSize
-1,m_x
);
221 virtual void disconnect() {
228 }; // class EdgeArray<T>
231 //! Bucket function for edges.
233 * The bucket of an edge is stored in an edge array which is passed
234 * by the user at construction; only a pointer is stored to that array.
236 class OGDF_EXPORT BucketEdgeArray
: public BucketFunc
<edge
>
238 const EdgeArray
<int> *m_pEdgeArray
; //!< Pointer to edge array.
241 //! Constructs a bucket function.
243 * @param edgeArray contains the buckets for the edges. May not be deleted
244 * as long as the bucket function is used.
246 BucketEdgeArray(const EdgeArray
<int> &edgeArray
) : m_pEdgeArray(&edgeArray
) { }
248 //! Returns bucket of edge \a e.
249 int getBucket(const edge
&e
) { return (*m_pEdgeArray
)[e
]; }
253 } // end namespace ogdf
254 #include <ogdf/basic/Graph.h>