"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/bits.go" (28 May 2021, 4724 Bytes) of package /linux/misc/gdrive-2.1.1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 // Copyright 2014 Sonia Keys
2 // License MIT: http://opensource.org/licenses/MIT
3
4 package graph
5
6 import (
7 "fmt"
8 "math/big"
9 )
10
11 // Bits is bitmap, or bitset, intended to store a single bit of information
12 // per node of a graph.
13 //
14 // The current implementation is backed by a big.Int and so is a reference
15 // type in the same way a big.Int is.
16 type Bits struct {
17 i big.Int
18 }
19
20 // NewBits constructs a Bits value with the bits ns set to 1.
21 func NewBits(ns ...NI) (b Bits) {
22 for _, n := range ns {
23 b.SetBit(n, 1)
24 }
25 return
26 }
27
28 // AllNot sets n bits of z to the complement of x.
29 //
30 // It is a convenience method for SetAll followed by AndNot.
31 func (z *Bits) AllNot(n int, x Bits) {
32 var y Bits
33 y.SetAll(n)
34 z.AndNot(y, x)
35 }
36
37 // And sets z = x & y.
38 func (z *Bits) And(x, y Bits) {
39 z.i.And(&x.i, &y.i)
40 }
41
42 // AndNot sets z = x &^ y.
43 func (z *Bits) AndNot(x, y Bits) {
44 z.i.AndNot(&x.i, &y.i)
45 }
46
47 // Bit returns the value of the n'th bit of x.
48 func (b Bits) Bit(n NI) uint {
49 return b.i.Bit(int(n))
50 }
51
52 // Clear sets all bits to 0.
53 func (z *Bits) Clear() {
54 *z = Bits{}
55 }
56
57 // Format satisfies fmt.Formatter for fmt.Printf and related methods.
58 //
59 // graph.Bits format exactly like big.Ints.
60 func (b Bits) Format(s fmt.State, ch rune) {
61 b.i.Format(s, ch)
62 }
63
64 // From returns the position of the first 1 bit at or after (from) position n.
65 //
66 // It returns -1 if there is no one bit at or after position n.
67 //
68 // This provides one way to iterate over one bits.
69 // To iterate over the one bits, call with n = 0 to get the the first
70 // one bit, then call with the result + 1 to get successive one bits.
71 // Unlike the Iterate method, this technique is stateless and so allows
72 // bits to be changed between successive calls.
73 //
74 // See also Iterate.
75 //
76 // (From is just a short word that means "at or after" here;
77 // it has nothing to do with arc direction.)
78 func (b Bits) From(n NI) NI {
79 words := b.i.Bits()
80 i := int(n)
81 x := i >> wordExp // x now index of word containing bit i.
82 if x >= len(words) {
83 return -1
84 }
85 // test for 1 in this word at or after n
86 if wx := words[x] >> (uint(i) & (wordSize - 1)); wx != 0 {
87 return n + NI(trailingZeros(wx))
88 }
89 x++
90 for y, wy := range words[x:] {
91 if wy != 0 {
92 return NI((x+y)<<wordExp | trailingZeros(wy))
93 }
94 }
95 return -1
96 }
97
98 // Iterate calls Visitor v for each bit with a value of 1, in order
99 // from lowest bit to highest bit.
100 //
101 // Iteration continues to the highest bit as long as v returns true.
102 // It stops if v returns false.
103 //
104 // Iterate returns true normally. It returns false if v returns false.
105 //
106 // Bit values should not be modified during iteration, by the visitor function
107 // for example. See From for an iteration method that allows modification.
108 func (b Bits) Iterate(v OkNodeVisitor) bool {
109 for x, w := range b.i.Bits() {
110 if w != 0 {
111 t := trailingZeros(w)
112 i := t // index in w of next 1 bit
113 for {
114 if !v(NI(x<<wordExp | i)) {
115 return false
116 }
117 w >>= uint(t + 1)
118 if w == 0 {
119 break
120 }
121 t = trailingZeros(w)
122 i += 1 + t
123 }
124 }
125 }
126 return true
127 }
128
129 // Or sets z = x | y.
130 func (z *Bits) Or(x, y Bits) {
131 z.i.Or(&x.i, &y.i)
132 }
133
134 // PopCount returns the number of 1 bits.
135 func (b Bits) PopCount() (c int) {
136 // algorithm selected to be efficient for sparse bit sets.
137 for _, w := range b.i.Bits() {
138 for w != 0 {
139 w &= w - 1
140 c++
141 }
142 }
143 return
144 }
145
146 // Set sets the bits of z to the bits of x.
147 func (z *Bits) Set(x Bits) {
148 z.i.Set(&x.i)
149 }
150
151 var one = big.NewInt(1)
152
153 // SetAll sets z to have n 1 bits.
154 //
155 // It's useful for initializing z to have a 1 for each node of a graph.
156 func (z *Bits) SetAll(n int) {
157 z.i.Sub(z.i.Lsh(one, uint(n)), one)
158 }
159
160 // SetBit sets the n'th bit to b, where be is a 0 or 1.
161 func (z *Bits) SetBit(n NI, b uint) {
162 z.i.SetBit(&z.i, int(n), b)
163 }
164
165 // Single returns true if b has exactly one 1 bit.
166 func (b Bits) Single() bool {
167 // like PopCount, but stop as soon as two are found
168 c := 0
169 for _, w := range b.i.Bits() {
170 for w != 0 {
171 w &= w - 1
172 c++
173 if c == 2 {
174 return false
175 }
176 }
177 }
178 return c == 1
179 }
180
181 // Slice returns a slice with the positions of each 1 bit.
182 func (b Bits) Slice() (s []NI) {
183 // (alternative implementation might use Popcount and make to get the
184 // exact cap slice up front. unclear if that would be better.)
185 b.Iterate(func(n NI) bool {
186 s = append(s, n)
187 return true
188 })
189 return
190 }
191
192 // Xor sets z = x ^ y.
193 func (z *Bits) Xor(x, y Bits) {
194 z.i.Xor(&x.i, &y.i)
195 }
196
197 // Zero returns true if there are no 1 bits.
198 func (b Bits) Zero() bool {
199 return len(b.i.Bits()) == 0
200 }
201
202 // trailingZeros returns the number of trailing 0 bits in v.
203 //
204 // If v is 0, it returns 0.
205 func trailingZeros(v big.Word) int {
206 return deBruijnBits[v&-v*deBruijnMultiple>>deBruijnShift]
207 }