index : blog

        

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