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
|
#
#
# Nimrod's Runtime Library
# (c) Copyright 2006 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
# set handling
type
TMyByte = int8
TNimSet = array [0..4*2048-1, TMyByte]
# implementation:
proc countBits(n: int32): int {.exportc: "countBits".}
# We use a prototype here, not in "cntbits.nim", because that is included
# in math.nim too. So when linking with math.nim it'd give a duplicated
# symbol error which we avoid by renaming here.
include cntbits
proc unionSets(res: var TNimSet, a, b: TNimSet, len: int) {.
compilerproc, inline.} =
for i in countup(0, len-1): res[i] = a[i] or b[i]
proc diffSets(res: var TNimSet, a, b: TNimSet, len: int) {.
compilerproc, inline.} =
for i in countup(0, len-1): res[i] = a[i] and not b[i]
proc intersectSets(res: var TNimSet, a, b: TNimSet, len: int) {.
compilerproc, inline.} =
for i in countup(0, len-1): res[i] = a[i] and b[i]
proc symdiffSets(res: var TNimSet, a, b: TNimSet, len: int) {.
compilerproc, inline.} =
for i in countup(0, len-1): res[i] = a[i] xor b[i]
proc containsSets(a, b: TNimSet, len: int): bool {.compilerproc, inline.} =
# s1 <= s2 ?
for i in countup(0, len-1):
if (a[i] and not b[i]) != 0'i8: return false
return true
proc containsSubsets(a, b: TNimSet, len: int): bool {.compilerproc, inline.} =
# s1 < s2 ?
result = false # assume they are equal
for i in countup(0, len-1):
if (a[i]) and not b[i]) != 0'i32: return false
if a[i] != b[i]: result = true # they are not equal
proc equalSets(a, b: TNimSet, len: int): bool {.compilerproc, inline.} =
for i in countup(0, len-1):
if a[i] != b[i]: return false
return true
proc cardSet(s: TNimSet, len: int): int {.compilerproc, inline.} =
result = 0
for i in countup(0, len-1):
inc(result, countBits(ze(s[i])))
const
WORD_SIZE = sizeof(TMyByte)*8
proc inSet(s: TNimSet, elem: int): bool {.compilerproc, inline.} =
return (s[elem /% WORD_SIZE] and (1 shl (elem %% WORD_SIZE))) != 0
proc inclSets(s: var TNimSet, e: int) {.compilerproc, inline.} =
s[e /% WORD_SIZE] = s[e /% WORD_SIZE] or toU8(1 shl (e %% WORD_SIZE))
proc inclRange(s: var TNimSet, first, last: int) {.compilerproc.} =
# not very fast, but it is seldom used
for i in countup(first, last): inclSets(s, i)
proc smallInclRange(s: var int, first, last: int) {.compilerproc.} =
# not very fast, but it is seldom used
for i in countup(first, last):
s = s or (1 shl (i %% sizeof(int)*8))
proc exclSets(s: var TNimSet, e: int) {.compilerproc, inline.} =
s[e /% WORD_SIZE] = s[e /% WORD_SIZE] and
not toU8(1 shl (e %% WORD_SIZE))
proc smallContainsSubsets(a, b: int): bool {.compilerProc, inline.} =
# not used by new code generator
return ((a and not b) != 0) and (a != b)
|