14#include "cvx/fallback.h"
19#error "cvx/interval_map.h requires K to be defined (the domain/key type, e.g. #define K int)"
22#error "cvx/interval_map.h requires V to be defined (the value/codomain type, e.g. #define V int)"
25#error "cvx/interval_map.h requires SNAME to be defined (the struct name, e.g. #define SNAME my_imap)"
28#error "cvx/interval_map.h requires PFX to be defined (the function prefix, e.g. #define PFX mi)"
31#error "cvx/interval_map.h requires TAG to be defined (a unique integer tag, e.g. #define TAG 1)"
41#define FUNC(X) CVX_(PFX, X)
48 V (*combine)(V left, V right);
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);
57void FUNC(_drop)(
struct SNAME *self);
60void FUNC(_build)(
struct SNAME *self,
const V *array);
61V
FUNC(_query)(
struct SNAME *self, K left, K right);
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);
67void FUNC(_init)(
struct SNAME *self, K count, V identity, V (*combine)(V left, V right))
76 self->combine = combine;
77 self->identity = identity;
78 self->tree = malloc(4 * count *
sizeof(V));
89void FUNC(_clone)(
struct SNAME *self,
struct SNAME *other)
91 FUNC(_init)(other, self->leaves, self->identity, self->combine);
98 size_t size = 4 * self->leaves *
sizeof(V);
99 memcpy(other->tree, self->tree, size);
102void FUNC(_drop)(
struct SNAME *self)
111 *self = (
struct SNAME){
114 .tag = self->super.tag,
119void FUNC(_build)(
struct SNAME *self,
const V *array)
121 if (self->leaves > 0)
123 FUNC(__build)(self, array, 1, 0, self->leaves - 1);
127V
FUNC(_query)(
struct SNAME *self, K left, K right)
129 if (self->leaves == 0)
131 return self->identity;
134 return FUNC(__query)(self, 1, 0, self->leaves - 1, left, right);
137void FUNC(_traverse_leaves)(
struct SNAME *self, K node, K start, K end,
138 void (*leaf_action)(K index, V value))
143 leaf_action(start, self->tree[node]);
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);
154void FUNC(_for_each)(
struct SNAME *self, void (*leaf_action)(K index, V value))
156 if (self->leaves > 0)
158 FUNC(_traverse_leaves)(self, 1, 0, self->leaves - 1, leaf_action);
168void FUNC(__build)(
struct SNAME *self,
const V *array, K node, K start, K end)
172 self->tree[node] = array[start];
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);
180 self->tree[node] = self->combine(self->tree[2 * node], self->tree[2 * node + 1]);
183V
FUNC(__query)(
struct SNAME *self, K node, K start, K end, K left, K right)
185 if (right < start || left > end)
187 return self->identity;
190 if (left <= start && end <= right)
192 return self->tree[node];
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);
199 return self->combine(left_res, right_res);
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