diff options
Diffstat (limited to 'compiler/bitsets.nim')
-rw-r--r-- | compiler/bitsets.nim | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/compiler/bitsets.nim b/compiler/bitsets.nim new file mode 100644 index 000000000..7d142b01d --- /dev/null +++ b/compiler/bitsets.nim @@ -0,0 +1,97 @@ +# +# +# The Nim Compiler +# (c) Copyright 2012 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# this unit handles Nim sets; it implements bit sets +# the code here should be reused in the Nim standard library + +when defined(nimPreviewSlimSystem): + import std/assertions + +type + ElemType = byte + TBitSet* = seq[ElemType] # we use byte here to avoid issues with + # cross-compiling; uint would be more efficient + # however +const + ElemSize* = 8 + One = ElemType(1) + Zero = ElemType(0) + +template modElemSize(arg: untyped): untyped = arg and 7 +template divElemSize(arg: untyped): untyped = arg shr 3 + +proc bitSetIn*(x: TBitSet, e: BiggestInt): bool = + result = (x[int(e.divElemSize)] and (One shl e.modElemSize)) != Zero + +proc bitSetIncl*(x: var TBitSet, elem: BiggestInt) = + assert(elem >= 0) + x[int(elem.divElemSize)] = x[int(elem.divElemSize)] or + (One shl elem.modElemSize) + +proc bitSetExcl*(x: var TBitSet, elem: BiggestInt) = + x[int(elem.divElemSize)] = x[int(elem.divElemSize)] and + not(One shl elem.modElemSize) + +proc bitSetInit*(b: var TBitSet, length: int) = + newSeq(b, length) + +proc bitSetUnion*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] or y[i] + +proc bitSetDiff*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] and not y[i] + +proc bitSetSymDiff*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] xor y[i] + +proc bitSetIntersect*(x: var TBitSet, y: TBitSet) = + for i in 0..high(x): x[i] = x[i] and y[i] + +proc bitSetEquals*(x, y: TBitSet): bool = + for i in 0..high(x): + if x[i] != y[i]: + return false + result = true + +proc bitSetContains*(x, y: TBitSet): bool = + for i in 0..high(x): + if (x[i] and not y[i]) != Zero: + return false + result = true + +# Number of set bits for all values of int8 +const populationCount: array[uint8, uint8] = block: + var arr: array[uint8, uint8] + + proc countSetBits(x: uint8): uint8 = + return + ( x and 0b00000001'u8) + + ((x and 0b00000010'u8) shr 1) + + ((x and 0b00000100'u8) shr 2) + + ((x and 0b00001000'u8) shr 3) + + ((x and 0b00010000'u8) shr 4) + + ((x and 0b00100000'u8) shr 5) + + ((x and 0b01000000'u8) shr 6) + + ((x and 0b10000000'u8) shr 7) + + + for it in low(uint8)..high(uint8): + arr[it] = countSetBits(cast[uint8](it)) + + arr + +proc bitSetCard*(x: TBitSet): BiggestInt = + result = 0 + for it in x: + result.inc int(populationCount[it]) + +proc bitSetToWord*(s: TBitSet; size: int): BiggestUInt = + result = 0 + for j in 0..<size: + if j < s.len: result = result or (BiggestUInt(s[j]) shl (j * 8)) |