-
Notifications
You must be signed in to change notification settings - Fork 3
/
sparse.jai
104 lines (88 loc) · 2.21 KB
/
sparse.jai
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#scope_module
Sparse_Set :: struct {
count: u32;
sparse: [..] u32;
dense: [..] u32;
}
init :: (set: *Sparse_Set, size: int) {
array_resize(*set.sparse, size, false);
array_resize(*set.dense, size, false);
}
add :: (set: *Sparse_Set, i: int) {
if !contains(<<set, i) {
add_unchecked(set, i);
}
}
add_unchecked :: (using set: *Sparse_Set, i: int) {
assert(!contains(<<set, i));
assert(count < dense.count);
sparse[i] = count;
dense[count] = cast(u32)i;
count += 1;
}
contains :: (using set: Sparse_Set, i: int) -> bool {
assert(i >= 0);
assert(i < dense.count);
return sparse[i] < count && dense[sparse[i]] == i;
}
for_expansion :: (set: *Sparse_Set, body: Code, flags: For_Flags) #expand {
assert(!flags, "reverse/pointer are not yet supported");
i := 0;
while i < set.count {
`it := set.dense[i];
`it_index := i;
defer i += 1;
#insert body;
}
}
Sparse_Array :: struct(Value: Type) {
count: u32;
sparse: [..] u32;
dense: [..] Index_Value;
Index_Value :: struct {
index: u32;
value: Value;
}
}
init :: (array: *Sparse_Array, size: int) {
array_resize(*array.sparse, size, false);
array_resize(*array.dense, size, false);
}
add_or_set :: (array: *Sparse_Array($T), i: int, value: T) {
if !contains(array, i) {
add_unchecked(array, i, value);
} else {
set(array, i, value);
}
}
add_unchecked :: (using array: *Sparse_Array($T), i: int, value: T) {
assert(!contains(<<array, i));
assert(count < dense.count);
sparse[i] = count;
dense[count].index = cast(u32)i;
dense[count].value = value;
count += 1;
}
set :: (using array: *Sparse_Array($T), i: int, value: T) {
assert(contains(<<array, i));
dense[sparse[i]].value = value;
}
contains :: (using array: Sparse_Array, i: int) -> bool {
assert(i >= 0);
assert(i < dense.count);
return sparse[i] < count && dense[sparse[i]].index == i;
}
get :: (using array: Sparse_Array($T), i: int) -> T {
assert(contains(array, i));
return dense[sparse[i]].value;
}
for_expansion :: (array: *$T/Sparse_Array, body: Code, flags: For_Flags) #expand {
assert(!flags, "reverse/pointer are not yet supported");
i := 0;
while i < array.count {
`it := array.dense[i];
`it_index := i;
defer i += 1;
#insert body;
}
}