dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
ds.h
Go to the documentation of this file.
1// Copyright 2024 Markus Anders
2// This file is part of dejavu 2.0.
3// See LICENSE for extended copyright information.
4
5#ifndef DEJAVU_DS_H
6#define DEJAVU_DS_H
7
8#include <list>
9#include <iostream>
10#include <cstring>
11#include <functional>
12#include <algorithm>
13#include <cassert>
14#include "utility.h"
15#include "coloring.h"
16
17namespace dejavu {
18
23 namespace ds {
24
32 template<class T>
33 void inline sort_t(T *arr, int sz) {
34 std::sort(arr, arr + sz);
35 }
36
42 template<class T>
43 class stack_t {
44 private:
45 std::vector<T> queue;
46 public:
51 void add(T &t) {
52 queue.emplace_back(t);
53 }
54
59 void reserve(int n) {
60 queue.reserve(n);
61 }
62
66 bool empty() {
67 return queue.empty();
68 }
69
75 T pop() {
76 auto element = queue.back();
77 queue.pop_back();
78 return element;
79 }
80 };
81
89 template<class T>
90 class worklist_t {
91 private:
96 void alloc(const int size) {
97 dealloc();
98 arr = new T[size];
99 arr_sz = size;
100 }
101
102 void dealloc() {
103 //if(arr) free(arr);
104 if(arr) delete[] arr;
105 arr = nullptr;
106 }
107
108 public:
112 worklist_t() = default;
113
114 worklist_t(const worklist_t<T>& other) {
115 copy(&other);
116 }
117
118 worklist_t(const worklist_t<T>&& other) {
119 swap(other);
120 }
121
123 if(other.arr == arr) return *this;
124 copy(&other);
125 return *this;
126 }
127
134 explicit worklist_t(int size) {
135 dej_assert(size >= 0);
136 allocate(size);
137 }
138
139 void swap(worklist_t<T>& other) {
140 auto swap_arr = arr;
141 auto swap_arr_sz = arr_sz;
142 auto swap_cur_pos = cur_pos;
143 arr = other.arr;
144 arr_sz = other.arr_sz;
145 cur_pos = other.cur_pos;
146 other.arr = swap_arr;
147 other.arr_sz = swap_arr_sz;
148 other.cur_pos = swap_cur_pos;
149 }
150
151 void copy(const worklist_t<T>* other) {
152 alloc(other->arr_sz);
153 for(int i = 0; i < other->arr_sz; ++i) {
154 arr[i] = other->arr[i];
155 }
156 arr_sz = other->arr_sz;
157 cur_pos = other->cur_pos;
158 }
159
166 void allocate(int size) {
167 dej_assert(size >= 0);
168 alloc(size);
169 cur_pos = 0;
170 }
171
177 inline void push_back(T value) {
178 dej_assert(cur_pos >= 0 && cur_pos < arr_sz);
179 arr[cur_pos] = value;
180 cur_pos += 1;
181 }
182
191 inline T pop_back() {
192 dej_assert(cur_pos > 0);
193 return arr[--cur_pos];
194 }
195
199 inline T *last() const {
200 return &arr[cur_pos - 1];
201 }
202
206 dej_nodiscard bool empty() const {
207 return cur_pos == 0;
208 }
209
215 void set_size(const int size) {
216 cur_pos = size;
217 }
218
222 dej_nodiscard int size() const {
223 return cur_pos;
224 }
225
229 inline void reset() {
230 cur_pos = 0;
231 }
232
233 int max() {
234 int max_val = arr[0];
235 for(int i = 1; i < cur_pos; ++i) {
236 const int val = arr[i];
237 if(val > max_val) max_val = val;
238 }
239 return max_val;
240 }
241
248 void resize(const int size) {
249 dej_assert(size >= 0);
250 if (arr && size <= arr_sz) return;
251 T *old_arr = nullptr;
252 int old_arr_sz = arr_sz;
253 if (arr) old_arr = arr;
254 arr = nullptr;
255 alloc(size);
256 if (old_arr != nullptr) {
257 int cp_pt = std::min(old_arr_sz, arr_sz);
258 memcpy(arr, old_arr, cp_pt * sizeof(T));
259 delete[] old_arr;
260 }
261 }
262
267 dealloc();
268 }
269
273 void sort() {
274 sort_t<T>(arr, cur_pos);
275 }
276
280 inline T *get_array() const {
281 return arr;
282 }
283
290 inline T &operator[](int index) const {
291 dej_assert(index >= 0);
292 dej_assert(index < arr_sz);
293 return arr[index];
294 }
295
296 void sort_after_map(T *map) {
297 struct comparator_map {
298 T *map;
299
300 explicit comparator_map(T *m) {
301 this->map = m;
302 }
303
304 bool operator()(const T &a, const T &b) {
305 return map[a] < map[b];
306 }
307 };
308 comparator_map c = comparator_map(map);
309 std::sort(arr, arr + cur_pos, c);
310 }
311
312 int cur_pos = 0;
313 private:
314 int arr_sz = 0;
315 T *arr = nullptr;
316 };
317
319
326 class workspace {
327 private:
332 void alloc(const int size) {
333 dej_assert(size >= 0);
334 dealloc();
335 arr = (int*) calloc(size, sizeof(int));
336 arr_sz = size;
337 }
338
339 void dealloc() {
340 if(arr) free(arr);
341 arr = nullptr;
342 }
343
344 public:
348 workspace() = default;
349
356 explicit workspace(int size) {
357 allocate(size);
358 }
359
360 workspace(const workspace& other) {
361 copy(other);
362 }
363
365 if(other.arr == arr) return *this;
366 copy(other);
367 return *this;
368 }
369
371 swap(other);
372 return *this;
373 }
374
375 void swap(workspace& other) {
376 auto swap_arr = arr;
377 auto swap_arr_sz = arr_sz;
378 arr = other.arr;
379 arr_sz = other.arr_sz;
380 other.arr = swap_arr;
381 other.arr_sz = swap_arr_sz;
382 }
383
384 void copy(const workspace& other) {
385 alloc(other.arr_sz);
386 memcpy(arr, other.arr, other.arr_sz * sizeof(int));
387 arr_sz = other.arr_sz;
388 }
389
396 void allocate(int size) {
397 alloc(size);
398 }
399
403 inline void reset() {
404 memset(arr, 0, arr_sz * sizeof(int));
405 }
406
413 void resize(const int size) {
414 dej_assert(size >= 0);
415 if (arr && size <= arr_sz) return;
416 int *old_arr = arr;
417 arr = nullptr;
418 int old_arr_sz = arr_sz;
419 alloc(size);
420 if (old_arr) {
421 int cp_pt = std::min(old_arr_sz, arr_sz);
422 memcpy(arr, old_arr, cp_pt * sizeof(int));
423 free(old_arr);
424 }
425 }
426
431 dealloc();
432 }
433
437 dej_nodiscard inline int* get_array() const {
438 return arr;
439 }
440
447 inline int &operator[](int index) const {
448 dej_assert(index >= 0);
449 dej_assert(index < arr_sz);
450 return arr[index];
451 }
452
453 private:
454 int arr_sz = 0;
455 int *arr = nullptr;
456 };
457
458
465 template<class T>
466 class workset_t {
467 public:
471 workset_t() = default;
472
479 explicit workset_t(int size) {
480 initialize(size);
481 }
482
483 void initialize(int size) {
484 s = new T[size];
485 reset_queue.allocate(size);
486
487 memset(s, -1, size * sizeof(T));
488
489 init = true;
490 sz = size;
491 }
492
493 void set(int index, T value) {
494 dej_assert(index >= 0);
495 dej_assert(index < sz);
496 s[index] = value;
497 }
498
499 T get(int index) {
500 dej_assert(index >= 0);
501 dej_assert(index < sz);
502 return s[index];
503 }
504
505 void reset() {
506 while (!reset_queue.empty()) s[reset_queue.pop_back()] = -1;
507 }
508
509 void reset_hard() {
510 memset(s, -1, sz * sizeof(T));
512 }
513
514 T inc(int index) {
515 dej_assert(index >= 0);
516 dej_assert(index < sz);
517 if (s[index]++ == -1)
518 reset_queue.push_back(index);
519 return s[index];
520 }
521
522 void inline inc_nr(int index) {
523 dej_assert(index >= 0 && index < sz);
524 ++s[index];
525 }
526
528 if (init)
529 delete[] s;
530 }
531
533 private:
534 bool init = false;
535 T *s = nullptr;
536 int sz = 0;
537 };
538
540
546 class markset {
547 int *s = nullptr;
548 int mark = 0;
549 int sz = 0;
550
551 void full_reset() {
552 memset(s, mark, sz * sizeof(int));
553 }
554
555 public:
559 markset() = default;
560
561 markset(const markset& other) {
562 copy(&other);
563 }
564
565 markset(markset&& other) {
566 swap(other);
567 }
568
569 markset& operator=(const markset& other) {
570 if(other.s == s) return *this;
571 copy(&other);
572 return *this;
573 }
574
579 explicit markset(int size) {
580 initialize(size);
581 }
582
588 void initialize(int size) {
589 dej_assert(size >= 0);
590 if(s && sz == size) {
591 reset();
592 return;
593 }
594 if(s) free(s);
595 s = (int*) calloc((unsigned int) size, sizeof(int));
596 sz = size;
597 mark = 0;
598 reset();
599 }
600
605 inline bool get(int pos) {
606 dej_assert(pos >= 0);
607 dej_assert(pos < sz);
608 return s[pos] == mark;
609 }
610
616 inline void set(int pos) {
617 dej_assert(pos >= 0);
618 dej_assert(pos < sz);
619 s[pos] = mark;
620 }
621
626 inline void unset(int pos) {
627 dej_assert(pos >= 0);
628 dej_assert(pos < sz);
629 s[pos] = mark - 1;
630 }
634 void reset() {
635 if(mark == -1) full_reset();
636 ++mark;
637 }
638
639 void swap(markset& other) {
640 auto swap_s = s;
641 auto swap_mark = mark;
642 auto swap_sz = sz;
643 s = other.s;
644 mark = other.mark;
645 sz = other.sz;
646 other.s = swap_s;
647 other.mark = swap_mark;
648 other.sz = swap_sz;
649 }
650
651 void copy(const markset* other) {
652 initialize(other->sz);
653 for(int i = 0; i < other->sz; ++i) {
654 s[i] = other->s[i];
655 }
656 mark = other->mark;
657 sz = other->sz;
658 }
659
661 if(s) free(s);
662 }
663 };
664
665// static void bucket_sort(worklist& list, markset& buckets, int limit) {
666// buckets.reset();
667// for(int i = 0; i < list.size(); ++i) buckets.set(list[i]);
668// list.reset();
669// for(int i = 0; i <= limit; ++i) if(buckets.get(i)) list.push_back(i);
670// buckets.reset();
671// }
672 }
673}
674
675#endif //DEJAVU_DS_H
Set specialized for quick resets.
Definition: ds.h:546
markset(markset &&other)
Definition: ds.h:565
void swap(markset &other)
Definition: ds.h:639
void copy(const markset *other)
Definition: ds.h:651
markset(int size)
Definition: ds.h:579
bool get(int pos)
Definition: ds.h:605
markset(const markset &other)
Definition: ds.h:561
void reset()
Definition: ds.h:634
markset & operator=(const markset &other)
Definition: ds.h:569
void initialize(int size)
Definition: ds.h:588
void set(int pos)
Definition: ds.h:616
void unset(int pos)
Definition: ds.h:626
Stack datastructure.
Definition: ds.h:43
bool empty()
Definition: ds.h:66
void reserve(int n)
Definition: ds.h:59
void add(T &t)
Definition: ds.h:51
Fixed-size array, uninitialized.
Definition: ds.h:90
void copy(const worklist_t< T > *other)
Definition: ds.h:151
T * last() const
Definition: ds.h:199
dej_nodiscard bool empty() const
Definition: ds.h:206
void sort_after_map(T *map)
Definition: ds.h:296
worklist_t< T > & operator=(const worklist_t< T > &other)
Definition: ds.h:122
T * get_array() const
Definition: ds.h:280
void swap(worklist_t< T > &other)
Definition: ds.h:139
void allocate(int size)
Definition: ds.h:166
void set_size(const int size)
Definition: ds.h:215
void resize(const int size)
Definition: ds.h:248
T & operator[](int index) const
Definition: ds.h:290
worklist_t(int size)
Definition: ds.h:134
worklist_t(const worklist_t< T > &other)
Definition: ds.h:114
dej_nodiscard int size() const
Definition: ds.h:222
worklist_t(const worklist_t< T > &&other)
Definition: ds.h:118
void push_back(T value)
Definition: ds.h:177
Set with counting.
Definition: ds.h:466
workset_t(int size)
Definition: ds.h:479
T get(int index)
Definition: ds.h:499
void reset_hard()
Definition: ds.h:509
worklist reset_queue
Definition: ds.h:532
void set(int index, T value)
Definition: ds.h:493
void inc_nr(int index)
Definition: ds.h:522
void reset()
Definition: ds.h:505
void initialize(int size)
Definition: ds.h:483
T inc(int index)
Definition: ds.h:514
Fixed-size integer array, 0-initialized.
Definition: ds.h:326
void reset()
Definition: ds.h:403
workspace & operator=(const workspace &other)
Definition: ds.h:364
void copy(const workspace &other)
Definition: ds.h:384
void resize(const int size)
Definition: ds.h:413
int & operator[](int index) const
Definition: ds.h:447
dej_nodiscard int * get_array() const
Definition: ds.h:437
workspace & operator=(workspace &&other)
Definition: ds.h:370
void allocate(int size)
Definition: ds.h:396
workspace(int size)
Definition: ds.h:356
workspace(const workspace &other)
Definition: ds.h:360
void swap(workspace &other)
Definition: ds.h:375
worklist_t< int > worklist
Definition: ds.h:318
void sort_t(T *arr, int sz)
Definition: ds.h:33
workset_t< int > work_set_int
Definition: ds.h:539
Definition: bfs.h:10
#define dej_assert(expr)
Definition: utility.h:40
#define dej_nodiscard
Definition: utility.h:46