LAL: Linear Arrangement Library 24.10.00
A library focused on algorithms on linear arrangements of graphs.
Loading...
Searching...
No Matches
basic_types.hpp
1/*********************************************************************
2 *
3 * Linear Arrangement Library - A library that implements a collection
4 * algorithms for linear arrangments of graphs.
5 *
6 * Copyright (C) 2019 - 2024
7 *
8 * This file is part of Linear Arrangement Library. The full code is available
9 * at:
10 * https://github.com/LAL-project/linear-arrangement-library.git
11 *
12 * Linear Arrangement Library is free software: you can redistribute it
13 * and/or modify it under the terms of the GNU Affero General Public License
14 * as published by the Free Software Foundation, either version 3 of the
15 * License, or (at your option) any later version.
16 *
17 * Linear Arrangement Library is distributed in the hope that it will be
18 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Affero General Public License for more details.
21 *
22 * You should have received a copy of the GNU Affero General Public License
23 * along with Linear Arrangement Library. If not, see <http://www.gnu.org/licenses/>.
24 *
25 * Contact:
26 *
27 * Lluís Alemany Puig (lluis.alemany.puig@upc.edu)
28 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
29 * CQL (Complexity and Quantitative Linguistics Lab)
30 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
31 * Webpage: https://cqllab.upc.edu/people/lalemany/
32 *
33 * Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
34 * LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
35 * CQL (Complexity and Quantitative Linguistics Lab)
36 * Office 220, Omega building
37 * Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona. CATALONIA, SPAIN
38 * Webpage: https://cqllab.upc.edu/people/rferrericancho/
39 *
40 ********************************************************************/
41
42#pragma once
43
44// C++ includes
45#include <cstdint>
46#include <vector>
47
48namespace lal {
49
51typedef uint64_t node;
53typedef uint64_t position;
54
56typedef std::pair<node, node> edge;
58typedef std::vector<uint64_t> head_vector;
60typedef std::vector<edge> edge_list;
62typedef std::pair<edge,edge> edge_pair;
64typedef std::vector<node> neighbourhood;
65
66// I know this is accessible outside the namespace -- #undef at the end
67#define __LAL_IS_INTEGRAL std::enable_if_t<std::is_integral_v<T>, bool> = true
68
70struct node_t {
71 uint64_t value;
72
73 /* CONSTRUCTORS */
74 // These are not necessary in C++20 and would turn the struct
75 // trivially constructible for all integral types.
76
77 node_t() noexcept = default;
78
79 template <typename T, __LAL_IS_INTEGRAL>
80 node_t(const T& _v) noexcept : value(_v) { }
81
82 /* ASSIGNMENT OPERATORS */
83
84 template <typename T, __LAL_IS_INTEGRAL>
85 node_t& operator= (const T& _v) noexcept { value = _v; return *this; }
86
87 /* COMPARISON OPERATORS */
88
89 template <typename T, __LAL_IS_INTEGRAL>
90 bool operator== (const T& t) const noexcept { return value == t; }
91 bool operator== (const node_t& u) const noexcept { return value == u.value; }
92 template <typename T, __LAL_IS_INTEGRAL>
93 friend bool operator== (const T& t, const node_t& u) noexcept { return u.value == t; }
94
95 template <typename T, __LAL_IS_INTEGRAL>
96 bool operator!= (const T& t) const noexcept { return value != t; }
97 bool operator!= (const node_t& u) const noexcept { return value != u.value; }
98 template <typename T, __LAL_IS_INTEGRAL>
99 friend bool operator!= (const T& t, const node_t& u) noexcept { return u.value != t; }
100
101 template <typename T, __LAL_IS_INTEGRAL>
102 bool operator< (const T& t) const noexcept { return value < t; }
103 bool operator< (const node_t& u) const noexcept { return value < u.value; }
104 template <typename T, __LAL_IS_INTEGRAL>
105 friend bool operator< (const T& t, const node_t& u) noexcept { return t < u.value; }
106
107 template <typename T, __LAL_IS_INTEGRAL>
108 bool operator<= (const T& t) const noexcept { return value <= t; }
109 bool operator<= (const node_t& u) const noexcept { return value <= u.value; }
110 template <typename T, __LAL_IS_INTEGRAL>
111 friend bool operator<= (const T& t, const node_t& u) noexcept { return t <= u.value; }
112
113 template <typename T, __LAL_IS_INTEGRAL>
114 bool operator> (const T& t) const noexcept { return value > t; }
115 bool operator> (const node_t& u) const noexcept { return value > u.value; }
116 template <typename T, __LAL_IS_INTEGRAL>
117 friend bool operator> (const T& t, const node_t& u) noexcept { return t > u.value; }
118
119 template <typename T, __LAL_IS_INTEGRAL>
120 bool operator>= (const T& t) const noexcept { return value >= t; }
121 bool operator>= (const node_t& u) const noexcept { return value >= u.value; }
122 template <typename T, __LAL_IS_INTEGRAL>
123 friend bool operator>= (const T& t, const node_t& u) noexcept { return t >= u.value; }
124
125 /* ARITHMETIC OPERATORS */
126
127 template <typename T, __LAL_IS_INTEGRAL>
128 node_t operator+ (const T& t) const noexcept { return node_t{value + t}; }
129 node_t operator+ (const node_t& u) const noexcept { return node_t{value + u.value}; }
130 template <typename T, __LAL_IS_INTEGRAL>
131 friend node_t operator+ (const T& t, const node_t& u) noexcept { return node_t{u.value + t}; }
132
133 template <typename T, __LAL_IS_INTEGRAL>
134 node_t& operator+= (const T& t) noexcept { value += t; return *this; }
135 node_t& operator+= (const node_t& u) noexcept { value += u.value; return *this; }
136
137 template <typename T, __LAL_IS_INTEGRAL>
138 node_t operator- (const T& t) const noexcept { return node_t{value - t}; }
139 node_t operator- (const node_t& u) const noexcept { return node_t{value - u.value}; }
140 template <typename T, __LAL_IS_INTEGRAL>
141 friend node_t operator- (const T& t, const node_t& u) noexcept { return node_t{t - u.value}; }
142
143 template <typename T, __LAL_IS_INTEGRAL>
144 node_t& operator-= (const T& t) noexcept { value -= t; return *this; }
145 node_t& operator-= (const node_t& u) noexcept { value -= u.value; return *this; }
146
147 node_t& operator++() noexcept { ++value; return *this; }
148 node_t& operator--() noexcept { --value; return *this; }
149
150 /* INPUT/OUTPUT OPERATORS */
151
152 template <class stream>
153 friend stream& operator>> (stream& s, node_t& p) noexcept {
154 s >> p.value;
155 return s;
156 }
157
158 template <class stream>
159 friend stream& operator<< (stream& s, const node_t& p) noexcept {
160 s << p.value;
161 return s;
162 }
163
164 uint64_t operator*() const noexcept { return value; }
165};
166
167static_assert( std::is_trivial_v<node_t>);
168
169static_assert( std::is_trivially_copyable_v<node_t>);
170static_assert( std::is_trivially_copy_assignable_v<node_t>);
171static_assert( std::is_copy_assignable_v<node_t>);
172static_assert( std::is_trivially_copy_constructible_v<node_t>);
173static_assert( std::is_copy_constructible_v<node_t>);
174static_assert( std::is_trivially_move_constructible_v<node_t>);
175static_assert( std::is_move_constructible_v<node_t>);
176static_assert( std::is_trivially_destructible_v<node_t>);
177static_assert( std::is_destructible_v<node_t>);
178
179
180static_assert( std::is_trivially_constructible_v<node_t, const node_t&>);
181static_assert( std::is_trivially_constructible_v<node_t, const node_t>);
182static_assert( std::is_trivially_constructible_v<node_t, node_t>);
183static_assert( std::is_trivially_constructible_v<node_t>);
184static_assert(not std::is_trivially_constructible_v<node_t, node>);
185static_assert(not std::is_trivially_constructible_v<node_t, uint64_t>);
186static_assert(not std::is_trivially_constructible_v<node_t, int64_t>);
187static_assert(not std::is_trivially_constructible_v<node_t, uint32_t>);
188static_assert(not std::is_trivially_constructible_v<node_t, int32_t>);
189static_assert(not std::is_trivially_constructible_v<node_t, uint16_t>);
190static_assert(not std::is_trivially_constructible_v<node_t, int16_t>);
191static_assert(not std::is_trivially_constructible_v<node_t, uint8_t>);
192static_assert(not std::is_trivially_constructible_v<node_t, int8_t>);
193
194static_assert( std::is_constructible_v<node_t, const node_t&>); // implied
195static_assert( std::is_constructible_v<node_t, const node_t>); // implied
196static_assert( std::is_constructible_v<node_t, node_t>); // implied
197static_assert( std::is_constructible_v<node_t>); // implied
198static_assert( std::is_constructible_v<node_t, node_t>);
199static_assert( std::is_constructible_v<node_t, node>);
200static_assert( std::is_constructible_v<node_t, uint64_t>);
201static_assert( std::is_constructible_v<node_t, int64_t>);
202static_assert( std::is_constructible_v<node_t, uint32_t>);
203static_assert( std::is_constructible_v<node_t, int32_t>);
204static_assert( std::is_constructible_v<node_t, uint16_t>);
205static_assert( std::is_constructible_v<node_t, int16_t>);
206static_assert( std::is_constructible_v<node_t, uint8_t>);
207static_assert( std::is_constructible_v<node_t, int8_t>);
208
209
210static_assert( std::is_trivially_assignable_v<node_t, const node_t&>);
211static_assert( std::is_trivially_assignable_v<node_t, const node_t>);
212static_assert( std::is_trivially_assignable_v<node_t, node_t>);
213static_assert(not std::is_trivially_assignable_v<node_t, node>);
214static_assert(not std::is_trivially_assignable_v<node_t, uint64_t>);
215static_assert(not std::is_trivially_assignable_v<node_t, int64_t>);
216static_assert(not std::is_trivially_assignable_v<node_t, uint32_t>);
217static_assert(not std::is_trivially_assignable_v<node_t, int32_t>);
218static_assert(not std::is_trivially_assignable_v<node_t, uint16_t>);
219static_assert(not std::is_trivially_assignable_v<node_t, int16_t>);
220static_assert(not std::is_trivially_assignable_v<node_t, uint8_t>);
221static_assert(not std::is_trivially_assignable_v<node_t, int8_t>);
222
223static_assert( std::is_assignable_v<node_t, const node_t&>); // implied
224static_assert( std::is_assignable_v<node_t, const node_t>); // implied
225static_assert( std::is_assignable_v<node_t, node_t>); // implied
226static_assert( std::is_assignable_v<node_t, node_t>);
227static_assert( std::is_assignable_v<node_t, node>);
228static_assert( std::is_assignable_v<node_t, uint64_t>);
229static_assert( std::is_assignable_v<node_t, int64_t>);
230static_assert( std::is_assignable_v<node_t, uint32_t>);
231static_assert( std::is_assignable_v<node_t, int32_t>);
232static_assert( std::is_assignable_v<node_t, uint16_t>);
233static_assert( std::is_assignable_v<node_t, int16_t>);
234static_assert( std::is_assignable_v<node_t, uint8_t>);
235static_assert( std::is_assignable_v<node_t, int8_t>);
236
237
239typedef std::pair<node_t, node_t> edge_t;
241typedef std::pair<edge_t, edge_t> edge_pair_t;
242
244struct position_t {
245 uint64_t value;
246
247 /* CONSTRUCTORS */
248 // These are not necessary in C++20 and would turn the struct
249 // trivially constructible for all integral types.
250
251 position_t() = default;
252
253 template <typename T, __LAL_IS_INTEGRAL>
254 position_t(const T& _v) noexcept : value(_v) { }
255
256 /* ASSIGNMENT OPERATORS */
257
258 template <typename T, __LAL_IS_INTEGRAL>
259 position_t& operator= (const T& _v) noexcept { value = _v; return *this; }
260
261 /* COMPARISON OPERATORS */
262
263 template <typename T, __LAL_IS_INTEGRAL>
264 bool operator== (const T& t) const noexcept { return value == t; }
265 bool operator== (const position_t& u) const noexcept { return value == u.value; }
266 template <typename T, __LAL_IS_INTEGRAL>
267 friend bool operator== (const T& t, const position_t& u) noexcept { return u.value == t; }
268
269 template <typename T, __LAL_IS_INTEGRAL>
270 bool operator!= (const T& t) const noexcept { return value != t; }
271 bool operator!= (const position_t& u) const noexcept { return value != u.value; }
272 template <typename T, __LAL_IS_INTEGRAL>
273 friend bool operator!= (const T& t, const position_t& u) noexcept { return u.value != t; }
274
275 template <typename T, __LAL_IS_INTEGRAL>
276 bool operator< (const T& t) const noexcept { return value < t; }
277 bool operator< (const position_t& u) const noexcept { return value < u.value; }
278 template <typename T, __LAL_IS_INTEGRAL>
279 friend bool operator< (const T& t, const position_t& u) noexcept { return t < u.value; }
280
281 template <typename T, __LAL_IS_INTEGRAL>
282 bool operator<= (const T& t) const noexcept { return value <= t; }
283 bool operator<= (const position_t& u) const noexcept { return value <= u.value; }
284 template <typename T, __LAL_IS_INTEGRAL>
285 friend bool operator<= (const T& t, const position_t& u) noexcept { return t <= u.value; }
286
287 template <typename T, __LAL_IS_INTEGRAL>
288 bool operator> (const T& t) const noexcept { return value > t; }
289 bool operator> (const position_t& u) const noexcept { return value > u.value; }
290 template <typename T, __LAL_IS_INTEGRAL>
291 friend bool operator> (const T& t, const position_t& u) noexcept { return t > u.value; }
292
293 template <typename T, __LAL_IS_INTEGRAL>
294 bool operator>= (const T& t) const noexcept { return value >= t; }
295 bool operator>= (const position_t& u) const noexcept { return value >= u.value; }
296 template <typename T, __LAL_IS_INTEGRAL>
297 friend bool operator>= (const T& t, const position_t& u) noexcept { return t >= u.value; }
298
299 /* ARITHMETIC OPERATORS */
300
301 template <typename T, __LAL_IS_INTEGRAL>
302 position_t operator+ (const T& t) const noexcept { return position_t{value + t}; }
303 position_t operator+ (const position_t& u) const noexcept { return position_t{value + u.value}; }
304 template <typename T, __LAL_IS_INTEGRAL>
305 friend position_t operator+ (const T& t, const position_t& u) noexcept { return position_t{u.value + t}; }
306
307 template <typename T, __LAL_IS_INTEGRAL>
308 position_t& operator+= (const T& t) noexcept { value += t; return *this; }
309 position_t& operator+= (const position_t& u) noexcept { value += u.value; return *this; }
310
311 template <typename T, __LAL_IS_INTEGRAL>
312 position_t operator- (const T& t) const noexcept { return position_t{value - t}; }
313 position_t operator- (const position_t& u) const noexcept { return position_t{value - u.value}; }
314 template <typename T, __LAL_IS_INTEGRAL>
315 friend position_t operator- (const T& t, const position_t& u) noexcept { return position_t{t - u.value}; }
316
317 template <typename T, __LAL_IS_INTEGRAL>
318 position_t& operator-= (const T& t) noexcept { value -= t; return *this; }
319 position_t& operator-= (const position_t& u) noexcept { value -= u.value; return *this; }
320
321 position_t& operator++() noexcept { ++value; return *this; }
322 position_t& operator--() noexcept { --value; return *this; }
323
324 /* INPUT/OUTPUT OPERATORS */
325
326 template <class stream>
327 friend stream& operator>> (stream& s, position_t& p) noexcept {
328 s >> p.value;
329 return s;
330 }
331
332 template <class stream>
333 friend stream& operator<< (stream& s, const position_t& p) noexcept {
334 s << p.value;
335 return s;
336 }
337
338 uint64_t operator*() const noexcept { return value; }
339};
340
341static_assert( std::is_trivial_v<position_t>);
342
343static_assert( std::is_trivially_copyable_v<position_t>);
344static_assert( std::is_trivially_copy_assignable_v<position_t>);
345static_assert( std::is_copy_assignable_v<position_t>);
346static_assert( std::is_trivially_copy_constructible_v<position_t>);
347static_assert( std::is_copy_constructible_v<position_t>);
348static_assert( std::is_trivially_move_constructible_v<position_t>);
349static_assert( std::is_move_constructible_v<position_t>);
350static_assert( std::is_trivially_destructible_v<position_t>);
351static_assert( std::is_destructible_v<position_t>);
352
353
354static_assert( std::is_trivially_constructible_v<position_t, const position_t&>);
355static_assert( std::is_trivially_constructible_v<position_t, const position_t>);
356static_assert( std::is_trivially_constructible_v<position_t, position_t>);
357static_assert( std::is_trivially_constructible_v<position_t>);
358static_assert(not std::is_trivially_constructible_v<position_t, node>);
359static_assert(not std::is_trivially_constructible_v<position_t, uint64_t>);
360static_assert(not std::is_trivially_constructible_v<position_t, int64_t>);
361static_assert(not std::is_trivially_constructible_v<position_t, uint32_t>);
362static_assert(not std::is_trivially_constructible_v<position_t, int32_t>);
363static_assert(not std::is_trivially_constructible_v<position_t, uint16_t>);
364static_assert(not std::is_trivially_constructible_v<position_t, int16_t>);
365static_assert(not std::is_trivially_constructible_v<position_t, uint8_t>);
366static_assert(not std::is_trivially_constructible_v<position_t, int8_t>);
367
368static_assert( std::is_constructible_v<position_t, const position_t&>); // implied
369static_assert( std::is_constructible_v<position_t, const position_t>); // implied
370static_assert( std::is_constructible_v<position_t, position_t>); // implied
371static_assert( std::is_constructible_v<position_t>); // implied
372static_assert( std::is_constructible_v<position_t, position_t>);
373static_assert( std::is_constructible_v<position_t, node>);
374static_assert( std::is_constructible_v<position_t, uint64_t>);
375static_assert( std::is_constructible_v<position_t, int64_t>);
376static_assert( std::is_constructible_v<position_t, uint32_t>);
377static_assert( std::is_constructible_v<position_t, int32_t>);
378static_assert( std::is_constructible_v<position_t, uint16_t>);
379static_assert( std::is_constructible_v<position_t, int16_t>);
380static_assert( std::is_constructible_v<position_t, uint8_t>);
381static_assert( std::is_constructible_v<position_t, int8_t>);
382
383
384static_assert( std::is_trivially_assignable_v<position_t, const position_t&>);
385static_assert( std::is_trivially_assignable_v<position_t, const position_t>);
386static_assert( std::is_trivially_assignable_v<position_t, position_t>);
387static_assert(not std::is_trivially_assignable_v<position_t, node>);
388static_assert(not std::is_trivially_assignable_v<position_t, uint64_t>);
389static_assert(not std::is_trivially_assignable_v<position_t, int64_t>);
390static_assert(not std::is_trivially_assignable_v<position_t, uint32_t>);
391static_assert(not std::is_trivially_assignable_v<position_t, int32_t>);
392static_assert(not std::is_trivially_assignable_v<position_t, uint16_t>);
393static_assert(not std::is_trivially_assignable_v<position_t, int16_t>);
394static_assert(not std::is_trivially_assignable_v<position_t, uint8_t>);
395static_assert(not std::is_trivially_assignable_v<position_t, int8_t>);
396
397static_assert( std::is_assignable_v<position_t, const position_t&>); // implied
398static_assert( std::is_assignable_v<position_t, const position_t>); // implied
399static_assert( std::is_assignable_v<position_t, position_t>); // implied
400static_assert( std::is_assignable_v<position_t, position_t>);
401static_assert( std::is_assignable_v<position_t, node>);
402static_assert( std::is_assignable_v<position_t, uint64_t>);
403static_assert( std::is_assignable_v<position_t, int64_t>);
404static_assert( std::is_assignable_v<position_t, uint32_t>);
405static_assert( std::is_assignable_v<position_t, int32_t>);
406static_assert( std::is_assignable_v<position_t, uint16_t>);
407static_assert( std::is_assignable_v<position_t, int16_t>);
408static_assert( std::is_assignable_v<position_t, uint8_t>);
409static_assert( std::is_assignable_v<position_t, int8_t>);
410
411#undef __LAL_IS_INTEGRAL
412
413} // -- namespace lal
lal
Main namespace of the library.
Definition basic_types.hpp:48
lal::edge_pair
std::pair< edge, edge > edge_pair
Edge pair type.
Definition basic_types.hpp:62
lal::head_vector
std::vector< uint64_t > head_vector
See Head vector page for further details.
Definition basic_types.hpp:58
lal::edge
std::pair< node, node > edge
See Edge page for further details.
Definition basic_types.hpp:56
lal::position
uint64_t position
Node's position type.
Definition basic_types.hpp:53
lal::edge_list
std::vector< edge > edge_list
See Edge list page for further details.
Definition basic_types.hpp:60
lal::edge_pair_t
std::pair< edge_t, edge_t > edge_pair_t
Similar to edge_pair.
Definition basic_types.hpp:241
lal::node
uint64_t node
Node type. See Node / Vertex page for further details.
Definition basic_types.hpp:51
lal::neighbourhood
std::vector< node > neighbourhood
List of nodes.
Definition basic_types.hpp:64
lal::edge_t
std::pair< node_t, node_t > edge_t
Similar to edge.
Definition basic_types.hpp:239
lal::node_t
Typesafe node type.
Definition basic_types.hpp:70
lal::position_t
Typesafe position type.
Definition basic_types.hpp:244
Generated by doxygen 1.11.0