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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
// Copyright 2014 Sonia Keys
// License MIT: http://opensource.org/licenses/MIT
package graph
import (
"fmt"
"math/big"
)
// Bits is bitmap, or bitset, intended to store a single bit of information
// per node of a graph.
//
// The current implementation is backed by a big.Int and so is a reference
// type in the same way a big.Int is.
type Bits struct {
i big.Int
}
// NewBits constructs a Bits value with the bits ns set to 1.
func NewBits(ns ...NI) (b Bits) {
for _, n := range ns {
b.SetBit(n, 1)
}
return
}
// AllNot sets n bits of z to the complement of x.
//
// It is a convenience method for SetAll followed by AndNot.
func (z *Bits) AllNot(n int, x Bits) {
var y Bits
y.SetAll(n)
z.AndNot(y, x)
}
// And sets z = x & y.
func (z *Bits) And(x, y Bits) {
z.i.And(&x.i, &y.i)
}
// AndNot sets z = x &^ y.
func (z *Bits) AndNot(x, y Bits) {
z.i.AndNot(&x.i, &y.i)
}
// Bit returns the value of the n'th bit of x.
func (b Bits) Bit(n NI) uint {
return b.i.Bit(int(n))
}
// Clear sets all bits to 0.
func (z *Bits) Clear() {
*z = Bits{}
}
// Format satisfies fmt.Formatter for fmt.Printf and related methods.
//
// graph.Bits format exactly like big.Ints.
func (b Bits) Format(s fmt.State, ch rune) {
b.i.Format(s, ch)
}
// From returns the position of the first 1 bit at or after (from) position n.
//
// It returns -1 if there is no one bit at or after position n.
//
// This provides one way to iterate over one bits.
// To iterate over the one bits, call with n = 0 to get the the first
// one bit, then call with the result + 1 to get successive one bits.
// Unlike the Iterate method, this technique is stateless and so allows
// bits to be changed between successive calls.
//
// See also Iterate.
//
// (From is just a short word that means "at or after" here;
// it has nothing to do with arc direction.)
func (b Bits) From(n NI) NI {
words := b.i.Bits()
i := int(n)
x := i >> wordExp // x now index of word containing bit i.
if x >= len(words) {
return -1
}
// test for 1 in this word at or after n
if wx := words[x] >> (uint(i) & (wordSize - 1)); wx != 0 {
return n + NI(trailingZeros(wx))
}
x++
for y, wy := range words[x:] {
if wy != 0 {
return NI((x+y)<<wordExp | trailingZeros(wy))
}
}
return -1
}
// Iterate calls Visitor v for each bit with a value of 1, in order
// from lowest bit to highest bit.
//
// Iteration continues to the highest bit as long as v returns true.
// It stops if v returns false.
//
// Iterate returns true normally. It returns false if v returns false.
//
// Bit values should not be modified during iteration, by the visitor function
// for example. See From for an iteration method that allows modification.
func (b Bits) Iterate(v OkNodeVisitor) bool {
for x, w := range b.i.Bits() {
if w != 0 {
t := trailingZeros(w)
i := t // index in w of next 1 bit
for {
if !v(NI(x<<wordExp | i)) {
return false
}
w >>= uint(t + 1)
if w == 0 {
break
}
t = trailingZeros(w)
i += 1 + t
}
}
}
return true
}
// Or sets z = x | y.
func (z *Bits) Or(x, y Bits) {
z.i.Or(&x.i, &y.i)
}
// PopCount returns the number of 1 bits.
func (b Bits) PopCount() (c int) {
// algorithm selected to be efficient for sparse bit sets.
for _, w := range b.i.Bits() {
for w != 0 {
w &= w - 1
c++
}
}
return
}
// Set sets the bits of z to the bits of x.
func (z *Bits) Set(x Bits) {
z.i.Set(&x.i)
}
var one = big.NewInt(1)
// SetAll sets z to have n 1 bits.
//
// It's useful for initializing z to have a 1 for each node of a graph.
func (z *Bits) SetAll(n int) {
z.i.Sub(z.i.Lsh(one, uint(n)), one)
}
// SetBit sets the n'th bit to b, where be is a 0 or 1.
func (z *Bits) SetBit(n NI, b uint) {
z.i.SetBit(&z.i, int(n), b)
}
// Single returns true if b has exactly one 1 bit.
func (b Bits) Single() bool {
// like PopCount, but stop as soon as two are found
c := 0
for _, w := range b.i.Bits() {
for w != 0 {
w &= w - 1
c++
if c == 2 {
return false
}
}
}
return c == 1
}
// Slice returns a slice with the positions of each 1 bit.
func (b Bits) Slice() (s []NI) {
// (alternative implementation might use Popcount and make to get the
// exact cap slice up front. unclear if that would be better.)
b.Iterate(func(n NI) bool {
s = append(s, n)
return true
})
return
}
// Xor sets z = x ^ y.
func (z *Bits) Xor(x, y Bits) {
z.i.Xor(&x.i, &y.i)
}
// Zero returns true if there are no 1 bits.
func (b Bits) Zero() bool {
return len(b.i.Bits()) == 0
}
// trailingZeros returns the number of trailing 0 bits in v.
//
// If v is 0, it returns 0.
func trailingZeros(v big.Word) int {
return deBruijnBits[v&-v*deBruijnMultiple>>deBruijnShift]
}
|
