diff options
| author | Oscar Nihlgård <oscarnihlgard@gmail.com> | 2018-04-10 10:38:16 +0200 |
|---|---|---|
| committer | Andreas Rumpf <rumpf_a@web.de> | 2018-04-10 10:38:16 +0200 |
| commit | 427490a845afa13c460d71c506994a24aae900c8 (patch) | |
| tree | cba7b2fbd228541a6c9aa9653aa9c5d54f3b8e4a /compiler | |
| parent | 992300b30057e2b3b489b90fb0e7011607e3e8cf (diff) | |
| download | Nim-427490a845afa13c460d71c506994a24aae900c8.tar.gz | |
Fix compile time set cardinality (#7558)
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/bitsets.nim | 25 | ||||
| -rw-r--r-- | compiler/nimsets.nim | 16 |
2 files changed, 30 insertions, 11 deletions
diff --git a/compiler/bitsets.nim b/compiler/bitsets.nim index 5454ef5e7..6afd1bd78 100644 --- a/compiler/bitsets.nim +++ b/compiler/bitsets.nim @@ -28,6 +28,7 @@ proc bitSetExcl*(x: var TBitSet, elem: BiggestInt) proc bitSetIn*(x: TBitSet, e: BiggestInt): bool proc bitSetEquals*(x, y: TBitSet): bool proc bitSetContains*(x, y: TBitSet): bool +proc bitSetCard*(x: TBitSet): BiggestInt # implementation proc bitSetIn(x: TBitSet, e: BiggestInt): bool = @@ -69,3 +70,27 @@ proc bitSetContains(x, y: TBitSet): bool = if (x[i] and not y[i]) != int8(0): return false result = true + +# Number of set bits for all values of int8 +const populationCount: array[low(int8)..high(int8), int8] = [ + 1.int8, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7 +] + +proc bitSetCard(x: TBitSet): BiggestInt = + for it in x: + result.inc populationCount[it] diff --git a/compiler/nimsets.nim b/compiler/nimsets.nim index bda753e85..8ec4d3c0d 100644 --- a/compiler/nimsets.nim +++ b/compiler/nimsets.nim @@ -27,7 +27,7 @@ proc intersectSets*(a, b: PNode): PNode proc symdiffSets*(a, b: PNode): PNode proc containsSets*(a, b: PNode): bool proc equalSets*(a, b: PNode): bool -proc cardSet*(s: PNode): BiggestInt +proc cardSet*(a: PNode): BiggestInt # implementation proc inSet(s: PNode, elem: PNode): bool = @@ -156,16 +156,10 @@ proc deduplicate*(a: PNode): PNode = toBitSet(a, x) result = toTreeSet(x, a.typ, a.info) -proc cardSet(s: PNode): BiggestInt = - # here we can do better than converting it into a compact set - # we just count the elements directly - result = 0 - for i in countup(0, sonsLen(s) - 1): - if s.sons[i].kind == nkRange: - result = result + getOrdValue(s.sons[i].sons[1]) - - getOrdValue(s.sons[i].sons[0]) + 1 - else: - inc(result) +proc cardSet(a: PNode): BiggestInt = + var x: TBitSet + toBitSet(a, x) + result = bitSetCard(x) proc setHasRange(s: PNode): bool = if s.kind != nkCurly: |