bitset.go 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931
  1. /*
  2. Package bitset implements bitsets, a mapping
  3. between non-negative integers and boolean values. It should be more
  4. efficient than map[uint] bool.
  5. It provides methods for setting, clearing, flipping, and testing
  6. individual integers.
  7. But it also provides set intersection, union, difference,
  8. complement, and symmetric operations, as well as tests to
  9. check whether any, all, or no bits are set, and querying a
  10. bitset's current length and number of positive bits.
  11. BitSets are expanded to the size of the largest set bit; the
  12. memory allocation is approximately Max bits, where Max is
  13. the largest set bit. BitSets are never shrunk. On creation,
  14. a hint can be given for the number of bits that will be used.
  15. Many of the methods, including Set,Clear, and Flip, return
  16. a BitSet pointer, which allows for chaining.
  17. Example use:
  18. import "bitset"
  19. var b BitSet
  20. b.Set(10).Set(11)
  21. if b.Test(1000) {
  22. b.Clear(1000)
  23. }
  24. if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
  25. fmt.Println("Intersection works.")
  26. }
  27. As an alternative to BitSets, one should check out the 'big' package,
  28. which provides a (less set-theoretical) view of bitsets.
  29. */
  30. package bitset
  31. import (
  32. "bufio"
  33. "bytes"
  34. "encoding/base64"
  35. "encoding/binary"
  36. "encoding/json"
  37. "errors"
  38. "fmt"
  39. "io"
  40. "strconv"
  41. )
  42. // the wordSize of a bit set
  43. const wordSize = uint(64)
  44. // log2WordSize is lg(wordSize)
  45. const log2WordSize = uint(6)
  46. // allBits has every bit set
  47. const allBits uint64 = 0xffffffffffffffff
  48. // default binary BigEndian
  49. var binaryOrder binary.ByteOrder = binary.BigEndian
  50. // default json encoding base64.URLEncoding
  51. var base64Encoding = base64.URLEncoding
  52. // Base64StdEncoding Marshal/Unmarshal BitSet with base64.StdEncoding(Default: base64.URLEncoding)
  53. func Base64StdEncoding() { base64Encoding = base64.StdEncoding }
  54. // LittleEndian Marshal/Unmarshal Binary as Little Endian(Default: binary.BigEndian)
  55. func LittleEndian() { binaryOrder = binary.LittleEndian }
  56. // A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.
  57. type BitSet struct {
  58. length uint
  59. set []uint64
  60. }
  61. // Error is used to distinguish errors (panics) generated in this package.
  62. type Error string
  63. // safeSet will fixup b.set to be non-nil and return the field value
  64. func (b *BitSet) safeSet() []uint64 {
  65. if b.set == nil {
  66. b.set = make([]uint64, wordsNeeded(0))
  67. }
  68. return b.set
  69. }
  70. // From is a constructor used to create a BitSet from an array of integers
  71. func From(buf []uint64) *BitSet {
  72. return &BitSet{uint(len(buf)) * 64, buf}
  73. }
  74. // Bytes returns the bitset as array of integers
  75. func (b *BitSet) Bytes() []uint64 {
  76. return b.set
  77. }
  78. // wordsNeeded calculates the number of words needed for i bits
  79. func wordsNeeded(i uint) int {
  80. if i > (Cap() - wordSize + 1) {
  81. return int(Cap() >> log2WordSize)
  82. }
  83. return int((i + (wordSize - 1)) >> log2WordSize)
  84. }
  85. // New creates a new BitSet with a hint that length bits will be required
  86. func New(length uint) (bset *BitSet) {
  87. defer func() {
  88. if r := recover(); r != nil {
  89. bset = &BitSet{
  90. 0,
  91. make([]uint64, 0),
  92. }
  93. }
  94. }()
  95. bset = &BitSet{
  96. length,
  97. make([]uint64, wordsNeeded(length)),
  98. }
  99. return bset
  100. }
  101. // Cap returns the total possible capacity, or number of bits
  102. func Cap() uint {
  103. return ^uint(0)
  104. }
  105. // Len returns the number of bits in the BitSet.
  106. // Note the difference to method Count, see example.
  107. func (b *BitSet) Len() uint {
  108. return b.length
  109. }
  110. // extendSetMaybe adds additional words to incorporate new bits if needed
  111. func (b *BitSet) extendSetMaybe(i uint) {
  112. if i >= b.length { // if we need more bits, make 'em
  113. if i >= Cap() {
  114. panic("You are exceeding the capacity")
  115. }
  116. nsize := wordsNeeded(i + 1)
  117. if b.set == nil {
  118. b.set = make([]uint64, nsize)
  119. } else if cap(b.set) >= nsize {
  120. b.set = b.set[:nsize] // fast resize
  121. } else if len(b.set) < nsize {
  122. newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x
  123. copy(newset, b.set)
  124. b.set = newset
  125. }
  126. b.length = i + 1
  127. }
  128. }
  129. // Test whether bit i is set.
  130. func (b *BitSet) Test(i uint) bool {
  131. if i >= b.length {
  132. return false
  133. }
  134. return b.set[i>>log2WordSize]&(1<<(i&(wordSize-1))) != 0
  135. }
  136. // Set bit i to 1, the capacity of the bitset is automatically
  137. // increased accordingly.
  138. // If i>= Cap(), this function will panic.
  139. // Warning: using a very large value for 'i'
  140. // may lead to a memory shortage and a panic: the caller is responsible
  141. // for providing sensible parameters in line with their memory capacity.
  142. func (b *BitSet) Set(i uint) *BitSet {
  143. b.extendSetMaybe(i)
  144. b.set[i>>log2WordSize] |= 1 << (i & (wordSize - 1))
  145. return b
  146. }
  147. // Clear bit i to 0
  148. func (b *BitSet) Clear(i uint) *BitSet {
  149. if i >= b.length {
  150. return b
  151. }
  152. b.set[i>>log2WordSize] &^= 1 << (i & (wordSize - 1))
  153. return b
  154. }
  155. // SetTo sets bit i to value.
  156. // If i>= Cap(), this function will panic.
  157. // Warning: using a very large value for 'i'
  158. // may lead to a memory shortage and a panic: the caller is responsible
  159. // for providing sensible parameters in line with their memory capacity.
  160. func (b *BitSet) SetTo(i uint, value bool) *BitSet {
  161. if value {
  162. return b.Set(i)
  163. }
  164. return b.Clear(i)
  165. }
  166. // Flip bit at i.
  167. // If i>= Cap(), this function will panic.
  168. // Warning: using a very large value for 'i'
  169. // may lead to a memory shortage and a panic: the caller is responsible
  170. // for providing sensible parameters in line with their memory capacity.
  171. func (b *BitSet) Flip(i uint) *BitSet {
  172. if i >= b.length {
  173. return b.Set(i)
  174. }
  175. b.set[i>>log2WordSize] ^= 1 << (i & (wordSize - 1))
  176. return b
  177. }
  178. // Shrink shrinks BitSet so that the provided value is the last possible
  179. // set value. It clears all bits > the provided index and reduces the size
  180. // and length of the set.
  181. //
  182. // Note that the parameter value is not the new length in bits: it is the
  183. // maximal value that can be stored in the bitset after the function call.
  184. // The new length in bits is the parameter value + 1. Thus it is not possible
  185. // to use this function to set the length to 0, the minimal value of the length
  186. // after this function call is 1.
  187. //
  188. // A new slice is allocated to store the new bits, so you may see an increase in
  189. // memory usage until the GC runs. Normally this should not be a problem, but if you
  190. // have an extremely large BitSet its important to understand that the old BitSet will
  191. // remain in memory until the GC frees it.
  192. func (b *BitSet) Shrink(lastbitindex uint) *BitSet {
  193. length := lastbitindex + 1
  194. idx := wordsNeeded(length)
  195. if idx > len(b.set) {
  196. return b
  197. }
  198. shrunk := make([]uint64, idx)
  199. copy(shrunk, b.set[:idx])
  200. b.set = shrunk
  201. b.length = length
  202. b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1))))
  203. return b
  204. }
  205. // Compact shrinks BitSet to so that we preserve all set bits, while minimizing
  206. // memory usage. Compact calls Shrink.
  207. func (b *BitSet) Compact() *BitSet {
  208. idx := len(b.set) - 1
  209. for ; idx >= 0 && b.set[idx] == 0; idx-- {
  210. }
  211. newlength := uint((idx + 1) << log2WordSize)
  212. if newlength >= b.length {
  213. return b // nothing to do
  214. }
  215. if newlength > 0 {
  216. return b.Shrink(newlength - 1)
  217. }
  218. // We preserve one word
  219. return b.Shrink(63)
  220. }
  221. // InsertAt takes an index which indicates where a bit should be
  222. // inserted. Then it shifts all the bits in the set to the left by 1, starting
  223. // from the given index position, and sets the index position to 0.
  224. //
  225. // Depending on the size of your BitSet, and where you are inserting the new entry,
  226. // this method could be extremely slow and in some cases might cause the entire BitSet
  227. // to be recopied.
  228. func (b *BitSet) InsertAt(idx uint) *BitSet {
  229. insertAtElement := (idx >> log2WordSize)
  230. // if length of set is a multiple of wordSize we need to allocate more space first
  231. if b.isLenExactMultiple() {
  232. b.set = append(b.set, uint64(0))
  233. }
  234. var i uint
  235. for i = uint(len(b.set) - 1); i > insertAtElement; i-- {
  236. // all elements above the position where we want to insert can simply by shifted
  237. b.set[i] <<= 1
  238. // we take the most significant bit of the previous element and set it as
  239. // the least significant bit of the current element
  240. b.set[i] |= (b.set[i-1] & 0x8000000000000000) >> 63
  241. }
  242. // generate a mask to extract the data that we need to shift left
  243. // within the element where we insert a bit
  244. dataMask := ^(uint64(1)<<uint64(idx&(wordSize-1)) - 1)
  245. // extract that data that we'll shift
  246. data := b.set[i] & dataMask
  247. // set the positions of the data mask to 0 in the element where we insert
  248. b.set[i] &= ^dataMask
  249. // shift data mask to the left and insert its data to the slice element
  250. b.set[i] |= data << 1
  251. // add 1 to length of BitSet
  252. b.length++
  253. return b
  254. }
  255. // String creates a string representation of the Bitmap
  256. func (b *BitSet) String() string {
  257. // follows code from https://github.com/RoaringBitmap/roaring
  258. var buffer bytes.Buffer
  259. start := []byte("{")
  260. buffer.Write(start)
  261. counter := 0
  262. i, e := b.NextSet(0)
  263. for e {
  264. counter = counter + 1
  265. // to avoid exhausting the memory
  266. if counter > 0x40000 {
  267. buffer.WriteString("...")
  268. break
  269. }
  270. buffer.WriteString(strconv.FormatInt(int64(i), 10))
  271. i, e = b.NextSet(i + 1)
  272. if e {
  273. buffer.WriteString(",")
  274. }
  275. }
  276. buffer.WriteString("}")
  277. return buffer.String()
  278. }
  279. // DeleteAt deletes the bit at the given index position from
  280. // within the bitset
  281. // All the bits residing on the left of the deleted bit get
  282. // shifted right by 1
  283. // The running time of this operation may potentially be
  284. // relatively slow, O(length)
  285. func (b *BitSet) DeleteAt(i uint) *BitSet {
  286. // the index of the slice element where we'll delete a bit
  287. deleteAtElement := i >> log2WordSize
  288. // generate a mask for the data that needs to be shifted right
  289. // within that slice element that gets modified
  290. dataMask := ^((uint64(1) << (i & (wordSize - 1))) - 1)
  291. // extract the data that we'll shift right from the slice element
  292. data := b.set[deleteAtElement] & dataMask
  293. // set the masked area to 0 while leaving the rest as it is
  294. b.set[deleteAtElement] &= ^dataMask
  295. // shift the previously extracted data to the right and then
  296. // set it in the previously masked area
  297. b.set[deleteAtElement] |= (data >> 1) & dataMask
  298. // loop over all the consecutive slice elements to copy each
  299. // lowest bit into the highest position of the previous element,
  300. // then shift the entire content to the right by 1
  301. for i := int(deleteAtElement) + 1; i < len(b.set); i++ {
  302. b.set[i-1] |= (b.set[i] & 1) << 63
  303. b.set[i] >>= 1
  304. }
  305. b.length = b.length - 1
  306. return b
  307. }
  308. // NextSet returns the next bit set from the specified index,
  309. // including possibly the current index
  310. // along with an error code (true = valid, false = no set bit found)
  311. // for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {...}
  312. //
  313. // Users concerned with performance may want to use NextSetMany to
  314. // retrieve several values at once.
  315. func (b *BitSet) NextSet(i uint) (uint, bool) {
  316. x := int(i >> log2WordSize)
  317. if x >= len(b.set) {
  318. return 0, false
  319. }
  320. w := b.set[x]
  321. w = w >> (i & (wordSize - 1))
  322. if w != 0 {
  323. return i + trailingZeroes64(w), true
  324. }
  325. x = x + 1
  326. for x < len(b.set) {
  327. if b.set[x] != 0 {
  328. return uint(x)*wordSize + trailingZeroes64(b.set[x]), true
  329. }
  330. x = x + 1
  331. }
  332. return 0, false
  333. }
  334. // NextSetMany returns many next bit sets from the specified index,
  335. // including possibly the current index and up to cap(buffer).
  336. // If the returned slice has len zero, then no more set bits were found
  337. //
  338. // buffer := make([]uint, 256) // this should be reused
  339. // j := uint(0)
  340. // j, buffer = bitmap.NextSetMany(j, buffer)
  341. // for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) {
  342. // for k := range buffer {
  343. // do something with buffer[k]
  344. // }
  345. // j += 1
  346. // }
  347. //
  348. //
  349. // It is possible to retrieve all set bits as follow:
  350. //
  351. // indices := make([]uint, bitmap.Count())
  352. // bitmap.NextSetMany(0, indices)
  353. //
  354. // However if bitmap.Count() is large, it might be preferable to
  355. // use several calls to NextSetMany, for performance reasons.
  356. func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint) {
  357. myanswer := buffer
  358. capacity := cap(buffer)
  359. x := int(i >> log2WordSize)
  360. if x >= len(b.set) || capacity == 0 {
  361. return 0, myanswer[:0]
  362. }
  363. skip := i & (wordSize - 1)
  364. word := b.set[x] >> skip
  365. myanswer = myanswer[:capacity]
  366. size := int(0)
  367. for word != 0 {
  368. r := trailingZeroes64(word)
  369. t := word & ((^word) + 1)
  370. myanswer[size] = r + i
  371. size++
  372. if size == capacity {
  373. goto End
  374. }
  375. word = word ^ t
  376. }
  377. x++
  378. for idx, word := range b.set[x:] {
  379. for word != 0 {
  380. r := trailingZeroes64(word)
  381. t := word & ((^word) + 1)
  382. myanswer[size] = r + (uint(x+idx) << 6)
  383. size++
  384. if size == capacity {
  385. goto End
  386. }
  387. word = word ^ t
  388. }
  389. }
  390. End:
  391. if size > 0 {
  392. return myanswer[size-1], myanswer[:size]
  393. }
  394. return 0, myanswer[:0]
  395. }
  396. // NextClear returns the next clear bit from the specified index,
  397. // including possibly the current index
  398. // along with an error code (true = valid, false = no bit found i.e. all bits are set)
  399. func (b *BitSet) NextClear(i uint) (uint, bool) {
  400. x := int(i >> log2WordSize)
  401. if x >= len(b.set) {
  402. return 0, false
  403. }
  404. w := b.set[x]
  405. w = w >> (i & (wordSize - 1))
  406. wA := allBits >> (i & (wordSize - 1))
  407. index := i + trailingZeroes64(^w)
  408. if w != wA && index < b.length {
  409. return index, true
  410. }
  411. x++
  412. for x < len(b.set) {
  413. index = uint(x)*wordSize + trailingZeroes64(^b.set[x])
  414. if b.set[x] != allBits && index < b.length {
  415. return index, true
  416. }
  417. x++
  418. }
  419. return 0, false
  420. }
  421. // ClearAll clears the entire BitSet
  422. func (b *BitSet) ClearAll() *BitSet {
  423. if b != nil && b.set != nil {
  424. for i := range b.set {
  425. b.set[i] = 0
  426. }
  427. }
  428. return b
  429. }
  430. // wordCount returns the number of words used in a bit set
  431. func (b *BitSet) wordCount() int {
  432. return len(b.set)
  433. }
  434. // Clone this BitSet
  435. func (b *BitSet) Clone() *BitSet {
  436. c := New(b.length)
  437. if b.set != nil { // Clone should not modify current object
  438. copy(c.set, b.set)
  439. }
  440. return c
  441. }
  442. // Copy into a destination BitSet
  443. // Returning the size of the destination BitSet
  444. // like array copy
  445. func (b *BitSet) Copy(c *BitSet) (count uint) {
  446. if c == nil {
  447. return
  448. }
  449. if b.set != nil { // Copy should not modify current object
  450. copy(c.set, b.set)
  451. }
  452. count = c.length
  453. if b.length < c.length {
  454. count = b.length
  455. }
  456. return
  457. }
  458. // Count (number of set bits).
  459. // Also known as "popcount" or "popularity count".
  460. func (b *BitSet) Count() uint {
  461. if b != nil && b.set != nil {
  462. return uint(popcntSlice(b.set))
  463. }
  464. return 0
  465. }
  466. // Equal tests the equivalence of two BitSets.
  467. // False if they are of different sizes, otherwise true
  468. // only if all the same bits are set
  469. func (b *BitSet) Equal(c *BitSet) bool {
  470. if c == nil || b == nil {
  471. return c == b
  472. }
  473. if b.length != c.length {
  474. return false
  475. }
  476. if b.length == 0 { // if they have both length == 0, then could have nil set
  477. return true
  478. }
  479. // testing for equality shoud not transform the bitset (no call to safeSet)
  480. for p, v := range b.set {
  481. if c.set[p] != v {
  482. return false
  483. }
  484. }
  485. return true
  486. }
  487. func panicIfNull(b *BitSet) {
  488. if b == nil {
  489. panic(Error("BitSet must not be null"))
  490. }
  491. }
  492. // Difference of base set and other set
  493. // This is the BitSet equivalent of &^ (and not)
  494. func (b *BitSet) Difference(compare *BitSet) (result *BitSet) {
  495. panicIfNull(b)
  496. panicIfNull(compare)
  497. result = b.Clone() // clone b (in case b is bigger than compare)
  498. l := int(compare.wordCount())
  499. if l > int(b.wordCount()) {
  500. l = int(b.wordCount())
  501. }
  502. for i := 0; i < l; i++ {
  503. result.set[i] = b.set[i] &^ compare.set[i]
  504. }
  505. return
  506. }
  507. // DifferenceCardinality computes the cardinality of the differnce
  508. func (b *BitSet) DifferenceCardinality(compare *BitSet) uint {
  509. panicIfNull(b)
  510. panicIfNull(compare)
  511. l := int(compare.wordCount())
  512. if l > int(b.wordCount()) {
  513. l = int(b.wordCount())
  514. }
  515. cnt := uint64(0)
  516. cnt += popcntMaskSlice(b.set[:l], compare.set[:l])
  517. cnt += popcntSlice(b.set[l:])
  518. return uint(cnt)
  519. }
  520. // InPlaceDifference computes the difference of base set and other set
  521. // This is the BitSet equivalent of &^ (and not)
  522. func (b *BitSet) InPlaceDifference(compare *BitSet) {
  523. panicIfNull(b)
  524. panicIfNull(compare)
  525. l := int(compare.wordCount())
  526. if l > int(b.wordCount()) {
  527. l = int(b.wordCount())
  528. }
  529. for i := 0; i < l; i++ {
  530. b.set[i] &^= compare.set[i]
  531. }
  532. }
  533. // Convenience function: return two bitsets ordered by
  534. // increasing length. Note: neither can be nil
  535. func sortByLength(a *BitSet, b *BitSet) (ap *BitSet, bp *BitSet) {
  536. if a.length <= b.length {
  537. ap, bp = a, b
  538. } else {
  539. ap, bp = b, a
  540. }
  541. return
  542. }
  543. // Intersection of base set and other set
  544. // This is the BitSet equivalent of & (and)
  545. func (b *BitSet) Intersection(compare *BitSet) (result *BitSet) {
  546. panicIfNull(b)
  547. panicIfNull(compare)
  548. b, compare = sortByLength(b, compare)
  549. result = New(b.length)
  550. for i, word := range b.set {
  551. result.set[i] = word & compare.set[i]
  552. }
  553. return
  554. }
  555. // IntersectionCardinality computes the cardinality of the union
  556. func (b *BitSet) IntersectionCardinality(compare *BitSet) uint {
  557. panicIfNull(b)
  558. panicIfNull(compare)
  559. b, compare = sortByLength(b, compare)
  560. cnt := popcntAndSlice(b.set, compare.set)
  561. return uint(cnt)
  562. }
  563. // InPlaceIntersection destructively computes the intersection of
  564. // base set and the compare set.
  565. // This is the BitSet equivalent of & (and)
  566. func (b *BitSet) InPlaceIntersection(compare *BitSet) {
  567. panicIfNull(b)
  568. panicIfNull(compare)
  569. l := int(compare.wordCount())
  570. if l > int(b.wordCount()) {
  571. l = int(b.wordCount())
  572. }
  573. for i := 0; i < l; i++ {
  574. b.set[i] &= compare.set[i]
  575. }
  576. for i := l; i < len(b.set); i++ {
  577. b.set[i] = 0
  578. }
  579. if compare.length > 0 {
  580. b.extendSetMaybe(compare.length - 1)
  581. }
  582. }
  583. // Union of base set and other set
  584. // This is the BitSet equivalent of | (or)
  585. func (b *BitSet) Union(compare *BitSet) (result *BitSet) {
  586. panicIfNull(b)
  587. panicIfNull(compare)
  588. b, compare = sortByLength(b, compare)
  589. result = compare.Clone()
  590. for i, word := range b.set {
  591. result.set[i] = word | compare.set[i]
  592. }
  593. return
  594. }
  595. // UnionCardinality computes the cardinality of the uniton of the base set
  596. // and the compare set.
  597. func (b *BitSet) UnionCardinality(compare *BitSet) uint {
  598. panicIfNull(b)
  599. panicIfNull(compare)
  600. b, compare = sortByLength(b, compare)
  601. cnt := popcntOrSlice(b.set, compare.set)
  602. if len(compare.set) > len(b.set) {
  603. cnt += popcntSlice(compare.set[len(b.set):])
  604. }
  605. return uint(cnt)
  606. }
  607. // InPlaceUnion creates the destructive union of base set and compare set.
  608. // This is the BitSet equivalent of | (or).
  609. func (b *BitSet) InPlaceUnion(compare *BitSet) {
  610. panicIfNull(b)
  611. panicIfNull(compare)
  612. l := int(compare.wordCount())
  613. if l > int(b.wordCount()) {
  614. l = int(b.wordCount())
  615. }
  616. if compare.length > 0 {
  617. b.extendSetMaybe(compare.length - 1)
  618. }
  619. for i := 0; i < l; i++ {
  620. b.set[i] |= compare.set[i]
  621. }
  622. if len(compare.set) > l {
  623. for i := l; i < len(compare.set); i++ {
  624. b.set[i] = compare.set[i]
  625. }
  626. }
  627. }
  628. // SymmetricDifference of base set and other set
  629. // This is the BitSet equivalent of ^ (xor)
  630. func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet) {
  631. panicIfNull(b)
  632. panicIfNull(compare)
  633. b, compare = sortByLength(b, compare)
  634. // compare is bigger, so clone it
  635. result = compare.Clone()
  636. for i, word := range b.set {
  637. result.set[i] = word ^ compare.set[i]
  638. }
  639. return
  640. }
  641. // SymmetricDifferenceCardinality computes the cardinality of the symmetric difference
  642. func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint {
  643. panicIfNull(b)
  644. panicIfNull(compare)
  645. b, compare = sortByLength(b, compare)
  646. cnt := popcntXorSlice(b.set, compare.set)
  647. if len(compare.set) > len(b.set) {
  648. cnt += popcntSlice(compare.set[len(b.set):])
  649. }
  650. return uint(cnt)
  651. }
  652. // InPlaceSymmetricDifference creates the destructive SymmetricDifference of base set and other set
  653. // This is the BitSet equivalent of ^ (xor)
  654. func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet) {
  655. panicIfNull(b)
  656. panicIfNull(compare)
  657. l := int(compare.wordCount())
  658. if l > int(b.wordCount()) {
  659. l = int(b.wordCount())
  660. }
  661. if compare.length > 0 {
  662. b.extendSetMaybe(compare.length - 1)
  663. }
  664. for i := 0; i < l; i++ {
  665. b.set[i] ^= compare.set[i]
  666. }
  667. if len(compare.set) > l {
  668. for i := l; i < len(compare.set); i++ {
  669. b.set[i] = compare.set[i]
  670. }
  671. }
  672. }
  673. // Is the length an exact multiple of word sizes?
  674. func (b *BitSet) isLenExactMultiple() bool {
  675. return b.length%wordSize == 0
  676. }
  677. // Clean last word by setting unused bits to 0
  678. func (b *BitSet) cleanLastWord() {
  679. if !b.isLenExactMultiple() {
  680. b.set[len(b.set)-1] &= allBits >> (wordSize - b.length%wordSize)
  681. }
  682. }
  683. // Complement computes the (local) complement of a biset (up to length bits)
  684. func (b *BitSet) Complement() (result *BitSet) {
  685. panicIfNull(b)
  686. result = New(b.length)
  687. for i, word := range b.set {
  688. result.set[i] = ^word
  689. }
  690. result.cleanLastWord()
  691. return
  692. }
  693. // All returns true if all bits are set, false otherwise. Returns true for
  694. // empty sets.
  695. func (b *BitSet) All() bool {
  696. panicIfNull(b)
  697. return b.Count() == b.length
  698. }
  699. // None returns true if no bit is set, false otherwise. Returns true for
  700. // empty sets.
  701. func (b *BitSet) None() bool {
  702. panicIfNull(b)
  703. if b != nil && b.set != nil {
  704. for _, word := range b.set {
  705. if word > 0 {
  706. return false
  707. }
  708. }
  709. return true
  710. }
  711. return true
  712. }
  713. // Any returns true if any bit is set, false otherwise
  714. func (b *BitSet) Any() bool {
  715. panicIfNull(b)
  716. return !b.None()
  717. }
  718. // IsSuperSet returns true if this is a superset of the other set
  719. func (b *BitSet) IsSuperSet(other *BitSet) bool {
  720. for i, e := other.NextSet(0); e; i, e = other.NextSet(i + 1) {
  721. if !b.Test(i) {
  722. return false
  723. }
  724. }
  725. return true
  726. }
  727. // IsStrictSuperSet returns true if this is a strict superset of the other set
  728. func (b *BitSet) IsStrictSuperSet(other *BitSet) bool {
  729. return b.Count() > other.Count() && b.IsSuperSet(other)
  730. }
  731. // DumpAsBits dumps a bit set as a string of bits
  732. func (b *BitSet) DumpAsBits() string {
  733. if b.set == nil {
  734. return "."
  735. }
  736. buffer := bytes.NewBufferString("")
  737. i := len(b.set) - 1
  738. for ; i >= 0; i-- {
  739. fmt.Fprintf(buffer, "%064b.", b.set[i])
  740. }
  741. return buffer.String()
  742. }
  743. // BinaryStorageSize returns the binary storage requirements
  744. func (b *BitSet) BinaryStorageSize() int {
  745. return binary.Size(uint64(0)) + binary.Size(b.set)
  746. }
  747. // WriteTo writes a BitSet to a stream
  748. func (b *BitSet) WriteTo(stream io.Writer) (int64, error) {
  749. length := uint64(b.length)
  750. // Write length
  751. err := binary.Write(stream, binaryOrder, length)
  752. if err != nil {
  753. return 0, err
  754. }
  755. // Write set
  756. err = binary.Write(stream, binaryOrder, b.set)
  757. return int64(b.BinaryStorageSize()), err
  758. }
  759. // ReadFrom reads a BitSet from a stream written using WriteTo
  760. func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) {
  761. var length uint64
  762. // Read length first
  763. err := binary.Read(stream, binaryOrder, &length)
  764. if err != nil {
  765. return 0, err
  766. }
  767. newset := New(uint(length))
  768. if uint64(newset.length) != length {
  769. return 0, errors.New("unmarshalling error: type mismatch")
  770. }
  771. // Read remaining bytes as set
  772. err = binary.Read(stream, binaryOrder, newset.set)
  773. if err != nil {
  774. return 0, err
  775. }
  776. *b = *newset
  777. return int64(b.BinaryStorageSize()), nil
  778. }
  779. // MarshalBinary encodes a BitSet into a binary form and returns the result.
  780. func (b *BitSet) MarshalBinary() ([]byte, error) {
  781. var buf bytes.Buffer
  782. writer := bufio.NewWriter(&buf)
  783. _, err := b.WriteTo(writer)
  784. if err != nil {
  785. return []byte{}, err
  786. }
  787. err = writer.Flush()
  788. return buf.Bytes(), err
  789. }
  790. // UnmarshalBinary decodes the binary form generated by MarshalBinary.
  791. func (b *BitSet) UnmarshalBinary(data []byte) error {
  792. buf := bytes.NewReader(data)
  793. reader := bufio.NewReader(buf)
  794. _, err := b.ReadFrom(reader)
  795. return err
  796. }
  797. // MarshalJSON marshals a BitSet as a JSON structure
  798. func (b *BitSet) MarshalJSON() ([]byte, error) {
  799. buffer := bytes.NewBuffer(make([]byte, 0, b.BinaryStorageSize()))
  800. _, err := b.WriteTo(buffer)
  801. if err != nil {
  802. return nil, err
  803. }
  804. // URLEncode all bytes
  805. return json.Marshal(base64Encoding.EncodeToString(buffer.Bytes()))
  806. }
  807. // UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON
  808. func (b *BitSet) UnmarshalJSON(data []byte) error {
  809. // Unmarshal as string
  810. var s string
  811. err := json.Unmarshal(data, &s)
  812. if err != nil {
  813. return err
  814. }
  815. // URLDecode string
  816. buf, err := base64Encoding.DecodeString(s)
  817. if err != nil {
  818. return err
  819. }
  820. _, err = b.ReadFrom(bytes.NewReader(buf))
  821. return err
  822. }