CVX
Loading...
Searching...
No Matches
segment_tree.h
Go to the documentation of this file.
1
13
14#include "cvx/fallback.h"
15#include "cvx/flags.h"
16
17// clang-format off
18#ifndef K
19#error "cvx/interval_map.h requires K to be defined (the domain/key type, e.g. #define K int)"
20#endif
21#ifndef V
22#error "cvx/interval_map.h requires V to be defined (the value/codomain type, e.g. #define V int)"
23#endif
24#ifndef SNAME
25#error "cvx/interval_map.h requires SNAME to be defined (the struct name, e.g. #define SNAME my_imap)"
26#endif
27#ifndef PFX
28#error "cvx/interval_map.h requires PFX to be defined (the function prefix, e.g. #define PFX mi)"
29#endif
30#ifndef TAG
31#error "cvx/interval_map.h requires TAG to be defined (a unique integer tag, e.g. #define TAG 1)"
32#endif
33// clang-format on
34
35#include <stdbool.h>
36#include <stdlib.h>
37#include <string.h>
38
39#include "cvx/core.h"
40
41#define FUNC(X) CVX_(PFX, X)
42
43struct SNAME
44{
46 V *tree;
48 V (*combine)(V left, V right);
50};
51
52// ---- Initializers ----
53void FUNC(_init)(struct SNAME *self, K count, V identity, V (*combine)(V left, V right));
54void FUNC(_clone)(struct SNAME *orig, struct SNAME *clone);
55
56// ---- Destructor ----
57void FUNC(_drop)(struct SNAME *self);
58
59// ---- Operations ----
60void FUNC(_build)(struct SNAME *self, const V *array);
61V FUNC(_query)(struct SNAME *self, K left, K right);
62
63// ---- private functions ----
64void FUNC(__build)(struct SNAME *self, const V *array, K node, K start, K end);
65V FUNC(__query)(struct SNAME *self, K node, K start, K end, K left, K right);
66
67void FUNC(_init)(struct SNAME *self, K count, V identity, V (*combine)(V left, V right))
68{
69 if (!combine)
70 {
71 self->super.flag = CVX_FLAG_VTAB;
72 return;
73 }
74
75 self->leaves = count;
76 self->combine = combine;
77 self->identity = identity;
78 self->tree = malloc(4 * count * sizeof(V));
79
80 if (!self->tree)
81 {
82 self->super.flag = CVX_FLAG_ALLOC;
83 return;
84 }
85
86 self->super.flag = CVX_FLAG_OK;
87}
88
89void FUNC(_clone)(struct SNAME *self, struct SNAME *other)
90{
91 FUNC(_init)(other, self->leaves, self->identity, self->combine);
92
93 if (other->super.flag != CVX_FLAG_OK)
94 {
95 return;
96 }
97
98 size_t size = 4 * self->leaves * sizeof(V);
99 memcpy(other->tree, self->tree, size);
100}
101
102void FUNC(_drop)(struct SNAME *self)
103{
104 if (!self)
105 {
106 return;
107 }
108
109 free(self->tree);
110
111 *self = (struct SNAME){
112 .super = {
113 .flag = CVX_FLAG_OK,
114 .tag = self->super.tag,
115 },
116 };
117}
118
119void FUNC(_build)(struct SNAME *self, const V *array)
120{
121 if (self->leaves > 0)
122 {
123 FUNC(__build)(self, array, 1, 0, self->leaves - 1);
124 }
125}
126
127V FUNC(_query)(struct SNAME *self, K left, K right)
128{
129 if (self->leaves == 0)
130 {
131 return self->identity;
132 }
133
134 return FUNC(__query)(self, 1, 0, self->leaves - 1, left, right);
135}
136
137void FUNC(_traverse_leaves)(struct SNAME *self, K node, K start, K end,
138 void (*leaf_action)(K index, V value))
139{
140 // Base case: We are at a leaf
141 if (start == end)
142 {
143 leaf_action(start, self->tree[node]);
144 return;
145 }
146
147 // Internal node: traverse left and right children
148 K mid = start + (end - start) / 2;
149 FUNC(_traverse_leaves)(self, 2 * node, start, mid, leaf_action);
150 FUNC(_traverse_leaves)(self, 2 * node + 1, mid + 1, end, leaf_action);
151}
152
153// Clean wrapper function so the user doesn't have to pass 'node', 'start', and 'end' manually
154void FUNC(_for_each)(struct SNAME *self, void (*leaf_action)(K index, V value))
155{
156 if (self->leaves > 0)
157 {
158 FUNC(_traverse_leaves)(self, 1, 0, self->leaves - 1, leaf_action);
159 }
160}
161
162//
163//
164// Private Functions
165//
166//
167
168void FUNC(__build)(struct SNAME *self, const V *array, K node, K start, K end)
169{
170 if (start == end)
171 {
172 self->tree[node] = array[start];
173 return;
174 }
175
176 K mid = start + (end - start) / 2;
177 FUNC(__build)(self, array, 2 * node, start, mid);
178 FUNC(__build)(self, array, 2 * node + 1, mid + 1, end);
179
180 self->tree[node] = self->combine(self->tree[2 * node], self->tree[2 * node + 1]);
181}
182
183V FUNC(__query)(struct SNAME *self, K node, K start, K end, K left, K right)
184{
185 if (right < start || left > end)
186 {
187 return self->identity;
188 }
189
190 if (left <= start && end <= right)
191 {
192 return self->tree[node];
193 }
194
195 K mid = start + (end - start) / 2;
196 V left_res = FUNC(__query)(self, 2 * node, start, mid, left, right);
197 V right_res = FUNC(__query)(self, 2 * node + 1, mid + 1, end, left, right);
198
199 return self->combine(left_res, right_res);
200}
201
202#include "cvx/undef.h"
@ CVX_FLAG_ALLOC
Allocation failed.
Definition array_iterator.h:82
@ CVX_FLAG_OK
No errors.
Definition array_iterator.h:79
@ CVX_FLAG_VTAB
Required vtab function was not provided.
Definition array_iterator.h:80
#define FUNC(X)
segment_tree.h
Definition segment_tree.h:41
Definition array_iterator.h:135
int * tree
Definition segment_tree.h:46
int leaves
Definition segment_tree.h:47
int identity
Definition segment_tree.h:49
cvx_container super
Definition segment_tree.h:45