-
Notifications
You must be signed in to change notification settings - Fork 0
/
c_empty_points.nim
66 lines (49 loc) · 2.31 KB
/
c_empty_points.nim
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
# Copyright (c) 2018 Mamy André-Ratsimbazafy
# Distributed under the Apache v2 License
# (license terms are at https://www.apache.org/licenses/LICENSE-2.0).
import ../datatypes
func contains(s: EmptyPoints, point: Point): bool {.inline.} =
assert point.GoInt != -1
s.indices[point.GoInt] != -1
func reset_border*(s: var EmptyPoints, point: Point) {.inline.} =
## Add a point to the border
s.indices[point.GoInt] = -1
func reset_empty*(s: var EmptyPoints, point: Point) {.inline.} =
## Add a point to the empty list without pre-checks
s.indices[point.GoInt] = s.len
s.list[s.len] = point
inc s.len
func peek*[N: static[GoInt]](s: EmptyPoints[N]): Point[N] {.inline.} =
## Returns the last point in the set.
## Note: if an item is deleted this is NOT the last inserted point.
assert s.len > 0, "Error: there is no empty points"
s.list[s.len - 1]
func incl*[N: static[GoInt]](s: var EmptyPoints[N], point: Point[N]) {.inline.} =
## Add a Point to a set of EmptyPoints
## The Point should not be in EmptyPoints already. It will throw
## an error in debug mode otherwise
# We assume point is not already in the set to avoid branching when updating the count
assert point notin s, "Error: " & $point & " is already in EmptyPoints"
# Bound checking
assert s.len <= N * N, "EmptyPoints is already at max capacity."
s.indices[point.GoInt] = s.len
s.list[s.len] = point
inc s.len
func excl*(s: var EmptyPoints, point: Point) {.inline.} =
## Remove a Point to a set of EmptyPoints
## The Point should be in EmptyPoints. It will throw
## an error in debug mode otherwise
# We assume point is in the set to avoid branching when updating the count
assert point in s, "Error: " & $point & " is not in EmptyPoints"
# We do constant time deletion by replacing the deleted point
# by the last value in the list
let del_idx = s.indices[point.GoInt]
s.indices[s.peek.GoInt] = del_idx # Last value now points to deleted index
dec s.len
s.list[del_idx] = s.list[s.len] # Deleted item is now last value
when compileOption("boundChecks"):
s.indices[point.GoInt] = -1 # Now we erase last value (take care of border case when we remove last value)
iterator items*[N: static[GoInt]](s: EmptyPoints[N]): Point[N] =
## Iterates over the empty points
for i in 0 ..< s.len:
yield s.list[i]