1package roaring 2 3import ( 4 "fmt" 5) 6 7//go:generate msgp -unexported 8 9type arrayContainer struct { 10 content []uint16 11} 12 13func (ac *arrayContainer) String() string { 14 s := "{" 15 for it := ac.getShortIterator(); it.hasNext(); { 16 s += fmt.Sprintf("%v, ", it.next()) 17 } 18 return s + "}" 19} 20 21func (ac *arrayContainer) fillLeastSignificant16bits(x []uint32, i int, mask uint32) { 22 for k := 0; k < len(ac.content); k++ { 23 x[k+i] = uint32(ac.content[k]) | mask 24 } 25} 26 27func (ac *arrayContainer) getShortIterator() shortPeekable { 28 return &shortIterator{ac.content, 0} 29} 30 31func (ac *arrayContainer) getReverseIterator() shortIterable { 32 return &reverseIterator{ac.content, len(ac.content) - 1} 33} 34 35func (ac *arrayContainer) getManyIterator() manyIterable { 36 return &shortIterator{ac.content, 0} 37} 38 39func (ac *arrayContainer) minimum() uint16 { 40 return ac.content[0] // assume not empty 41} 42 43func (ac *arrayContainer) maximum() uint16 { 44 return ac.content[len(ac.content)-1] // assume not empty 45} 46 47func (ac *arrayContainer) getSizeInBytes() int { 48 return ac.getCardinality() * 2 49} 50 51func (ac *arrayContainer) serializedSizeInBytes() int { 52 return ac.getCardinality() * 2 53} 54 55func arrayContainerSizeInBytes(card int) int { 56 return card * 2 57} 58 59// add the values in the range [firstOfRange,endx) 60func (ac *arrayContainer) iaddRange(firstOfRange, endx int) container { 61 if firstOfRange >= endx { 62 return ac 63 } 64 indexstart := binarySearch(ac.content, uint16(firstOfRange)) 65 if indexstart < 0 { 66 indexstart = -indexstart - 1 67 } 68 indexend := binarySearch(ac.content, uint16(endx-1)) 69 if indexend < 0 { 70 indexend = -indexend - 1 71 } else { 72 indexend++ 73 } 74 rangelength := endx - firstOfRange 75 newcardinality := indexstart + (ac.getCardinality() - indexend) + rangelength 76 if newcardinality > arrayDefaultMaxSize { 77 a := ac.toBitmapContainer() 78 return a.iaddRange(firstOfRange, endx) 79 } 80 if cap(ac.content) < newcardinality { 81 tmp := make([]uint16, newcardinality, newcardinality) 82 copy(tmp[:indexstart], ac.content[:indexstart]) 83 copy(tmp[indexstart+rangelength:], ac.content[indexend:]) 84 85 ac.content = tmp 86 } else { 87 ac.content = ac.content[:newcardinality] 88 copy(ac.content[indexstart+rangelength:], ac.content[indexend:]) 89 90 } 91 for k := 0; k < rangelength; k++ { 92 ac.content[k+indexstart] = uint16(firstOfRange + k) 93 } 94 return ac 95} 96 97// remove the values in the range [firstOfRange,endx) 98func (ac *arrayContainer) iremoveRange(firstOfRange, endx int) container { 99 if firstOfRange >= endx { 100 return ac 101 } 102 indexstart := binarySearch(ac.content, uint16(firstOfRange)) 103 if indexstart < 0 { 104 indexstart = -indexstart - 1 105 } 106 indexend := binarySearch(ac.content, uint16(endx-1)) 107 if indexend < 0 { 108 indexend = -indexend - 1 109 } else { 110 indexend++ 111 } 112 rangelength := indexend - indexstart 113 answer := ac 114 copy(answer.content[indexstart:], ac.content[indexstart+rangelength:]) 115 answer.content = answer.content[:ac.getCardinality()-rangelength] 116 return answer 117} 118 119// flip the values in the range [firstOfRange,endx) 120func (ac *arrayContainer) not(firstOfRange, endx int) container { 121 if firstOfRange >= endx { 122 return ac.clone() 123 } 124 return ac.notClose(firstOfRange, endx-1) // remove everything in [firstOfRange,endx-1] 125} 126 127// flip the values in the range [firstOfRange,lastOfRange] 128func (ac *arrayContainer) notClose(firstOfRange, lastOfRange int) container { 129 if firstOfRange > lastOfRange { // unlike add and remove, not uses an inclusive range [firstOfRange,lastOfRange] 130 return ac.clone() 131 } 132 133 // determine the span of array indices to be affected^M 134 startIndex := binarySearch(ac.content, uint16(firstOfRange)) 135 if startIndex < 0 { 136 startIndex = -startIndex - 1 137 } 138 lastIndex := binarySearch(ac.content, uint16(lastOfRange)) 139 if lastIndex < 0 { 140 lastIndex = -lastIndex - 2 141 } 142 currentValuesInRange := lastIndex - startIndex + 1 143 spanToBeFlipped := lastOfRange - firstOfRange + 1 144 newValuesInRange := spanToBeFlipped - currentValuesInRange 145 cardinalityChange := newValuesInRange - currentValuesInRange 146 newCardinality := len(ac.content) + cardinalityChange 147 if newCardinality > arrayDefaultMaxSize { 148 return ac.toBitmapContainer().not(firstOfRange, lastOfRange+1) 149 } 150 answer := newArrayContainer() 151 answer.content = make([]uint16, newCardinality, newCardinality) //a hack for sure 152 153 copy(answer.content, ac.content[:startIndex]) 154 outPos := startIndex 155 inPos := startIndex 156 valInRange := firstOfRange 157 for ; valInRange <= lastOfRange && inPos <= lastIndex; valInRange++ { 158 if uint16(valInRange) != ac.content[inPos] { 159 answer.content[outPos] = uint16(valInRange) 160 outPos++ 161 } else { 162 inPos++ 163 } 164 } 165 166 for ; valInRange <= lastOfRange; valInRange++ { 167 answer.content[outPos] = uint16(valInRange) 168 outPos++ 169 } 170 171 for i := lastIndex + 1; i < len(ac.content); i++ { 172 answer.content[outPos] = ac.content[i] 173 outPos++ 174 } 175 answer.content = answer.content[:newCardinality] 176 return answer 177 178} 179 180func (ac *arrayContainer) equals(o container) bool { 181 182 srb, ok := o.(*arrayContainer) 183 if ok { 184 // Check if the containers are the same object. 185 if ac == srb { 186 return true 187 } 188 189 if len(srb.content) != len(ac.content) { 190 return false 191 } 192 193 for i, v := range ac.content { 194 if v != srb.content[i] { 195 return false 196 } 197 } 198 return true 199 } 200 201 // use generic comparison 202 bCard := o.getCardinality() 203 aCard := ac.getCardinality() 204 if bCard != aCard { 205 return false 206 } 207 208 ait := ac.getShortIterator() 209 bit := o.getShortIterator() 210 for ait.hasNext() { 211 if bit.next() != ait.next() { 212 return false 213 } 214 } 215 return true 216} 217 218func (ac *arrayContainer) toBitmapContainer() *bitmapContainer { 219 bc := newBitmapContainer() 220 bc.loadData(ac) 221 return bc 222 223} 224func (ac *arrayContainer) iadd(x uint16) (wasNew bool) { 225 // Special case adding to the end of the container. 226 l := len(ac.content) 227 if l > 0 && l < arrayDefaultMaxSize && ac.content[l-1] < x { 228 ac.content = append(ac.content, x) 229 return true 230 } 231 232 loc := binarySearch(ac.content, x) 233 234 if loc < 0 { 235 s := ac.content 236 i := -loc - 1 237 s = append(s, 0) 238 copy(s[i+1:], s[i:]) 239 s[i] = x 240 ac.content = s 241 return true 242 } 243 return false 244} 245 246func (ac *arrayContainer) iaddReturnMinimized(x uint16) container { 247 // Special case adding to the end of the container. 248 l := len(ac.content) 249 if l > 0 && l < arrayDefaultMaxSize && ac.content[l-1] < x { 250 ac.content = append(ac.content, x) 251 return ac 252 } 253 254 loc := binarySearch(ac.content, x) 255 256 if loc < 0 { 257 if len(ac.content) >= arrayDefaultMaxSize { 258 a := ac.toBitmapContainer() 259 a.iadd(x) 260 return a 261 } 262 s := ac.content 263 i := -loc - 1 264 s = append(s, 0) 265 copy(s[i+1:], s[i:]) 266 s[i] = x 267 ac.content = s 268 } 269 return ac 270} 271 272// iremoveReturnMinimized is allowed to change the return type to minimize storage. 273func (ac *arrayContainer) iremoveReturnMinimized(x uint16) container { 274 ac.iremove(x) 275 return ac 276} 277 278func (ac *arrayContainer) iremove(x uint16) bool { 279 loc := binarySearch(ac.content, x) 280 if loc >= 0 { 281 s := ac.content 282 s = append(s[:loc], s[loc+1:]...) 283 ac.content = s 284 return true 285 } 286 return false 287} 288 289func (ac *arrayContainer) remove(x uint16) container { 290 out := &arrayContainer{make([]uint16, len(ac.content))} 291 copy(out.content, ac.content[:]) 292 293 loc := binarySearch(out.content, x) 294 if loc >= 0 { 295 s := out.content 296 s = append(s[:loc], s[loc+1:]...) 297 out.content = s 298 } 299 return out 300} 301 302func (ac *arrayContainer) or(a container) container { 303 switch x := a.(type) { 304 case *arrayContainer: 305 return ac.orArray(x) 306 case *bitmapContainer: 307 return x.orArray(ac) 308 case *runContainer16: 309 if x.isFull() { 310 return x.clone() 311 } 312 return x.orArray(ac) 313 } 314 panic("unsupported container type") 315} 316 317func (ac *arrayContainer) orCardinality(a container) int { 318 switch x := a.(type) { 319 case *arrayContainer: 320 return ac.orArrayCardinality(x) 321 case *bitmapContainer: 322 return x.orArrayCardinality(ac) 323 case *runContainer16: 324 return x.orArrayCardinality(ac) 325 } 326 panic("unsupported container type") 327} 328 329func (ac *arrayContainer) ior(a container) container { 330 switch x := a.(type) { 331 case *arrayContainer: 332 return ac.iorArray(x) 333 case *bitmapContainer: 334 return a.(*bitmapContainer).orArray(ac) 335 //return ac.iorBitmap(x) // note: this does not make sense 336 case *runContainer16: 337 if x.isFull() { 338 return x.clone() 339 } 340 return ac.iorRun16(x) 341 } 342 panic("unsupported container type") 343} 344 345func (ac *arrayContainer) iorArray(value2 *arrayContainer) container { 346 value1 := ac 347 len1 := value1.getCardinality() 348 len2 := value2.getCardinality() 349 maxPossibleCardinality := len1 + len2 350 if maxPossibleCardinality > arrayDefaultMaxSize { // it could be a bitmap! 351 bc := newBitmapContainer() 352 for k := 0; k < len(value2.content); k++ { 353 v := value2.content[k] 354 i := uint(v) >> 6 355 mask := uint64(1) << (v % 64) 356 bc.bitmap[i] |= mask 357 } 358 for k := 0; k < len(ac.content); k++ { 359 v := ac.content[k] 360 i := uint(v) >> 6 361 mask := uint64(1) << (v % 64) 362 bc.bitmap[i] |= mask 363 } 364 bc.cardinality = int(popcntSlice(bc.bitmap)) 365 if bc.cardinality <= arrayDefaultMaxSize { 366 return bc.toArrayContainer() 367 } 368 return bc 369 } 370 if maxPossibleCardinality > cap(value1.content) { 371 newcontent := make([]uint16, 0, maxPossibleCardinality) 372 copy(newcontent[len2:maxPossibleCardinality], ac.content[0:len1]) 373 ac.content = newcontent 374 } else { 375 copy(ac.content[len2:maxPossibleCardinality], ac.content[0:len1]) 376 } 377 nl := union2by2(value1.content[len2:maxPossibleCardinality], value2.content, ac.content) 378 ac.content = ac.content[:nl] // reslice to match actual used capacity 379 return ac 380} 381 382// Note: such code does not make practical sense, except for lazy evaluations 383func (ac *arrayContainer) iorBitmap(bc2 *bitmapContainer) container { 384 bc1 := ac.toBitmapContainer() 385 bc1.iorBitmap(bc2) 386 *ac = *newArrayContainerFromBitmap(bc1) 387 return ac 388} 389 390func (ac *arrayContainer) iorRun16(rc *runContainer16) container { 391 bc1 := ac.toBitmapContainer() 392 bc2 := rc.toBitmapContainer() 393 bc1.iorBitmap(bc2) 394 *ac = *newArrayContainerFromBitmap(bc1) 395 return ac 396} 397 398func (ac *arrayContainer) lazyIOR(a container) container { 399 switch x := a.(type) { 400 case *arrayContainer: 401 return ac.lazyIorArray(x) 402 case *bitmapContainer: 403 return ac.lazyIorBitmap(x) 404 case *runContainer16: 405 if x.isFull() { 406 return x.clone() 407 } 408 return ac.lazyIorRun16(x) 409 410 } 411 panic("unsupported container type") 412} 413 414func (ac *arrayContainer) lazyIorArray(ac2 *arrayContainer) container { 415 // TODO actually make this lazy 416 return ac.iorArray(ac2) 417} 418 419func (ac *arrayContainer) lazyIorBitmap(bc *bitmapContainer) container { 420 // TODO actually make this lazy 421 return ac.iorBitmap(bc) 422} 423 424func (ac *arrayContainer) lazyIorRun16(rc *runContainer16) container { 425 // TODO actually make this lazy 426 return ac.iorRun16(rc) 427} 428 429func (ac *arrayContainer) lazyOR(a container) container { 430 switch x := a.(type) { 431 case *arrayContainer: 432 return ac.lazyorArray(x) 433 case *bitmapContainer: 434 return a.lazyOR(ac) 435 case *runContainer16: 436 if x.isFull() { 437 return x.clone() 438 } 439 return x.orArray(ac) 440 } 441 panic("unsupported container type") 442} 443 444func (ac *arrayContainer) orArray(value2 *arrayContainer) container { 445 value1 := ac 446 maxPossibleCardinality := value1.getCardinality() + value2.getCardinality() 447 if maxPossibleCardinality > arrayDefaultMaxSize { // it could be a bitmap! 448 bc := newBitmapContainer() 449 for k := 0; k < len(value2.content); k++ { 450 v := value2.content[k] 451 i := uint(v) >> 6 452 mask := uint64(1) << (v % 64) 453 bc.bitmap[i] |= mask 454 } 455 for k := 0; k < len(ac.content); k++ { 456 v := ac.content[k] 457 i := uint(v) >> 6 458 mask := uint64(1) << (v % 64) 459 bc.bitmap[i] |= mask 460 } 461 bc.cardinality = int(popcntSlice(bc.bitmap)) 462 if bc.cardinality <= arrayDefaultMaxSize { 463 return bc.toArrayContainer() 464 } 465 return bc 466 } 467 answer := newArrayContainerCapacity(maxPossibleCardinality) 468 nl := union2by2(value1.content, value2.content, answer.content) 469 answer.content = answer.content[:nl] // reslice to match actual used capacity 470 return answer 471} 472 473func (ac *arrayContainer) orArrayCardinality(value2 *arrayContainer) int { 474 return union2by2Cardinality(ac.content, value2.content) 475} 476 477func (ac *arrayContainer) lazyorArray(value2 *arrayContainer) container { 478 value1 := ac 479 maxPossibleCardinality := value1.getCardinality() + value2.getCardinality() 480 if maxPossibleCardinality > arrayLazyLowerBound { // it could be a bitmap!^M 481 bc := newBitmapContainer() 482 for k := 0; k < len(value2.content); k++ { 483 v := value2.content[k] 484 i := uint(v) >> 6 485 mask := uint64(1) << (v % 64) 486 bc.bitmap[i] |= mask 487 } 488 for k := 0; k < len(ac.content); k++ { 489 v := ac.content[k] 490 i := uint(v) >> 6 491 mask := uint64(1) << (v % 64) 492 bc.bitmap[i] |= mask 493 } 494 bc.cardinality = invalidCardinality 495 return bc 496 } 497 answer := newArrayContainerCapacity(maxPossibleCardinality) 498 nl := union2by2(value1.content, value2.content, answer.content) 499 answer.content = answer.content[:nl] // reslice to match actual used capacity 500 return answer 501} 502 503func (ac *arrayContainer) and(a container) container { 504 switch x := a.(type) { 505 case *arrayContainer: 506 return ac.andArray(x) 507 case *bitmapContainer: 508 return x.and(ac) 509 case *runContainer16: 510 if x.isFull() { 511 return ac.clone() 512 } 513 return x.andArray(ac) 514 } 515 panic("unsupported container type") 516} 517 518func (ac *arrayContainer) andCardinality(a container) int { 519 switch x := a.(type) { 520 case *arrayContainer: 521 return ac.andArrayCardinality(x) 522 case *bitmapContainer: 523 return x.andCardinality(ac) 524 case *runContainer16: 525 return x.andArrayCardinality(ac) 526 } 527 panic("unsupported container type") 528} 529 530func (ac *arrayContainer) intersects(a container) bool { 531 switch x := a.(type) { 532 case *arrayContainer: 533 return ac.intersectsArray(x) 534 case *bitmapContainer: 535 return x.intersects(ac) 536 case *runContainer16: 537 return x.intersects(ac) 538 } 539 panic("unsupported container type") 540} 541 542func (ac *arrayContainer) iand(a container) container { 543 switch x := a.(type) { 544 case *arrayContainer: 545 return ac.iandArray(x) 546 case *bitmapContainer: 547 return ac.iandBitmap(x) 548 case *runContainer16: 549 if x.isFull() { 550 return ac 551 } 552 return x.andArray(ac) 553 } 554 panic("unsupported container type") 555} 556 557func (ac *arrayContainer) iandBitmap(bc *bitmapContainer) container { 558 pos := 0 559 c := ac.getCardinality() 560 for k := 0; k < c; k++ { 561 // branchless 562 v := ac.content[k] 563 ac.content[pos] = v 564 pos += int(bc.bitValue(v)) 565 } 566 ac.content = ac.content[:pos] 567 return ac 568 569} 570 571func (ac *arrayContainer) xor(a container) container { 572 switch x := a.(type) { 573 case *arrayContainer: 574 return ac.xorArray(x) 575 case *bitmapContainer: 576 return a.xor(ac) 577 case *runContainer16: 578 return x.xorArray(ac) 579 } 580 panic("unsupported container type") 581} 582 583func (ac *arrayContainer) xorArray(value2 *arrayContainer) container { 584 value1 := ac 585 totalCardinality := value1.getCardinality() + value2.getCardinality() 586 if totalCardinality > arrayDefaultMaxSize { // it could be a bitmap! 587 bc := newBitmapContainer() 588 for k := 0; k < len(value2.content); k++ { 589 v := value2.content[k] 590 i := uint(v) >> 6 591 bc.bitmap[i] ^= (uint64(1) << (v % 64)) 592 } 593 for k := 0; k < len(ac.content); k++ { 594 v := ac.content[k] 595 i := uint(v) >> 6 596 bc.bitmap[i] ^= (uint64(1) << (v % 64)) 597 } 598 bc.computeCardinality() 599 if bc.cardinality <= arrayDefaultMaxSize { 600 return bc.toArrayContainer() 601 } 602 return bc 603 } 604 desiredCapacity := totalCardinality 605 answer := newArrayContainerCapacity(desiredCapacity) 606 length := exclusiveUnion2by2(value1.content, value2.content, answer.content) 607 answer.content = answer.content[:length] 608 return answer 609 610} 611 612func (ac *arrayContainer) andNot(a container) container { 613 switch x := a.(type) { 614 case *arrayContainer: 615 return ac.andNotArray(x) 616 case *bitmapContainer: 617 return ac.andNotBitmap(x) 618 case *runContainer16: 619 return ac.andNotRun16(x) 620 } 621 panic("unsupported container type") 622} 623 624func (ac *arrayContainer) andNotRun16(rc *runContainer16) container { 625 acb := ac.toBitmapContainer() 626 rcb := rc.toBitmapContainer() 627 return acb.andNotBitmap(rcb) 628} 629 630func (ac *arrayContainer) iandNot(a container) container { 631 switch x := a.(type) { 632 case *arrayContainer: 633 return ac.iandNotArray(x) 634 case *bitmapContainer: 635 return ac.iandNotBitmap(x) 636 case *runContainer16: 637 return ac.iandNotRun16(x) 638 } 639 panic("unsupported container type") 640} 641 642func (ac *arrayContainer) iandNotRun16(rc *runContainer16) container { 643 rcb := rc.toBitmapContainer() 644 acb := ac.toBitmapContainer() 645 acb.iandNotBitmapSurely(rcb) 646 *ac = *(acb.toArrayContainer()) 647 return ac 648} 649 650func (ac *arrayContainer) andNotArray(value2 *arrayContainer) container { 651 value1 := ac 652 desiredcapacity := value1.getCardinality() 653 answer := newArrayContainerCapacity(desiredcapacity) 654 length := difference(value1.content, value2.content, answer.content) 655 answer.content = answer.content[:length] 656 return answer 657} 658 659func (ac *arrayContainer) iandNotArray(value2 *arrayContainer) container { 660 length := difference(ac.content, value2.content, ac.content) 661 ac.content = ac.content[:length] 662 return ac 663} 664 665func (ac *arrayContainer) andNotBitmap(value2 *bitmapContainer) container { 666 desiredcapacity := ac.getCardinality() 667 answer := newArrayContainerCapacity(desiredcapacity) 668 answer.content = answer.content[:desiredcapacity] 669 pos := 0 670 for _, v := range ac.content { 671 answer.content[pos] = v 672 pos += 1 - int(value2.bitValue(v)) 673 } 674 answer.content = answer.content[:pos] 675 return answer 676} 677 678func (ac *arrayContainer) andBitmap(value2 *bitmapContainer) container { 679 desiredcapacity := ac.getCardinality() 680 answer := newArrayContainerCapacity(desiredcapacity) 681 answer.content = answer.content[:desiredcapacity] 682 pos := 0 683 for _, v := range ac.content { 684 answer.content[pos] = v 685 pos += int(value2.bitValue(v)) 686 } 687 answer.content = answer.content[:pos] 688 return answer 689} 690 691func (ac *arrayContainer) iandNotBitmap(value2 *bitmapContainer) container { 692 pos := 0 693 for _, v := range ac.content { 694 ac.content[pos] = v 695 pos += 1 - int(value2.bitValue(v)) 696 } 697 ac.content = ac.content[:pos] 698 return ac 699} 700 701func copyOf(array []uint16, size int) []uint16 { 702 result := make([]uint16, size) 703 for i, x := range array { 704 if i == size { 705 break 706 } 707 result[i] = x 708 } 709 return result 710} 711 712// flip the values in the range [firstOfRange,endx) 713func (ac *arrayContainer) inot(firstOfRange, endx int) container { 714 if firstOfRange >= endx { 715 return ac 716 } 717 return ac.inotClose(firstOfRange, endx-1) // remove everything in [firstOfRange,endx-1] 718} 719 720// flip the values in the range [firstOfRange,lastOfRange] 721func (ac *arrayContainer) inotClose(firstOfRange, lastOfRange int) container { 722 if firstOfRange > lastOfRange { // unlike add and remove, not uses an inclusive range [firstOfRange,lastOfRange] 723 return ac 724 } 725 // determine the span of array indices to be affected 726 startIndex := binarySearch(ac.content, uint16(firstOfRange)) 727 if startIndex < 0 { 728 startIndex = -startIndex - 1 729 } 730 lastIndex := binarySearch(ac.content, uint16(lastOfRange)) 731 if lastIndex < 0 { 732 lastIndex = -lastIndex - 1 - 1 733 } 734 currentValuesInRange := lastIndex - startIndex + 1 735 spanToBeFlipped := lastOfRange - firstOfRange + 1 736 737 newValuesInRange := spanToBeFlipped - currentValuesInRange 738 buffer := make([]uint16, newValuesInRange) 739 cardinalityChange := newValuesInRange - currentValuesInRange 740 newCardinality := len(ac.content) + cardinalityChange 741 if cardinalityChange > 0 { 742 if newCardinality > len(ac.content) { 743 if newCardinality > arrayDefaultMaxSize { 744 bcRet := ac.toBitmapContainer() 745 bcRet.inot(firstOfRange, lastOfRange+1) 746 *ac = *bcRet.toArrayContainer() 747 return bcRet 748 } 749 ac.content = copyOf(ac.content, newCardinality) 750 } 751 base := lastIndex + 1 752 copy(ac.content[lastIndex+1+cardinalityChange:], ac.content[base:base+len(ac.content)-1-lastIndex]) 753 ac.negateRange(buffer, startIndex, lastIndex, firstOfRange, lastOfRange+1) 754 } else { // no expansion needed 755 ac.negateRange(buffer, startIndex, lastIndex, firstOfRange, lastOfRange+1) 756 if cardinalityChange < 0 { 757 758 for i := startIndex + newValuesInRange; i < newCardinality; i++ { 759 ac.content[i] = ac.content[i-cardinalityChange] 760 } 761 } 762 } 763 ac.content = ac.content[:newCardinality] 764 return ac 765} 766 767func (ac *arrayContainer) negateRange(buffer []uint16, startIndex, lastIndex, startRange, lastRange int) { 768 // compute the negation into buffer 769 outPos := 0 770 inPos := startIndex // value here always >= valInRange, 771 // until it is exhausted 772 // n.b., we can start initially exhausted. 773 774 valInRange := startRange 775 for ; valInRange < lastRange && inPos <= lastIndex; valInRange++ { 776 if uint16(valInRange) != ac.content[inPos] { 777 buffer[outPos] = uint16(valInRange) 778 outPos++ 779 } else { 780 inPos++ 781 } 782 } 783 784 // if there are extra items (greater than the biggest 785 // pre-existing one in range), buffer them 786 for ; valInRange < lastRange; valInRange++ { 787 buffer[outPos] = uint16(valInRange) 788 outPos++ 789 } 790 791 if outPos != len(buffer) { 792 panic("negateRange: internal bug") 793 } 794 795 for i, item := range buffer { 796 ac.content[i+startIndex] = item 797 } 798} 799 800func (ac *arrayContainer) isFull() bool { 801 return false 802} 803 804func (ac *arrayContainer) andArray(value2 *arrayContainer) container { 805 desiredcapacity := minOfInt(ac.getCardinality(), value2.getCardinality()) 806 answer := newArrayContainerCapacity(desiredcapacity) 807 length := intersection2by2( 808 ac.content, 809 value2.content, 810 answer.content) 811 answer.content = answer.content[:length] 812 return answer 813} 814 815func (ac *arrayContainer) andArrayCardinality(value2 *arrayContainer) int { 816 return intersection2by2Cardinality( 817 ac.content, 818 value2.content) 819} 820 821func (ac *arrayContainer) intersectsArray(value2 *arrayContainer) bool { 822 return intersects2by2( 823 ac.content, 824 value2.content) 825} 826 827func (ac *arrayContainer) iandArray(value2 *arrayContainer) container { 828 length := intersection2by2( 829 ac.content, 830 value2.content, 831 ac.content) 832 ac.content = ac.content[:length] 833 return ac 834} 835 836func (ac *arrayContainer) getCardinality() int { 837 return len(ac.content) 838} 839 840func (ac *arrayContainer) rank(x uint16) int { 841 answer := binarySearch(ac.content, x) 842 if answer >= 0 { 843 return answer + 1 844 } 845 return -answer - 1 846 847} 848 849func (ac *arrayContainer) selectInt(x uint16) int { 850 return int(ac.content[x]) 851} 852 853func (ac *arrayContainer) clone() container { 854 ptr := arrayContainer{make([]uint16, len(ac.content))} 855 copy(ptr.content, ac.content[:]) 856 return &ptr 857} 858 859func (ac *arrayContainer) contains(x uint16) bool { 860 return binarySearch(ac.content, x) >= 0 861} 862 863func (ac *arrayContainer) loadData(bitmapContainer *bitmapContainer) { 864 ac.content = make([]uint16, bitmapContainer.cardinality, bitmapContainer.cardinality) 865 bitmapContainer.fillArray(ac.content) 866} 867func newArrayContainer() *arrayContainer { 868 p := new(arrayContainer) 869 return p 870} 871 872func newArrayContainerFromBitmap(bc *bitmapContainer) *arrayContainer { 873 ac := &arrayContainer{} 874 ac.loadData(bc) 875 return ac 876} 877 878func newArrayContainerCapacity(size int) *arrayContainer { 879 p := new(arrayContainer) 880 p.content = make([]uint16, 0, size) 881 return p 882} 883 884func newArrayContainerSize(size int) *arrayContainer { 885 p := new(arrayContainer) 886 p.content = make([]uint16, size, size) 887 return p 888} 889 890func newArrayContainerRange(firstOfRun, lastOfRun int) *arrayContainer { 891 valuesInRange := lastOfRun - firstOfRun + 1 892 this := newArrayContainerCapacity(valuesInRange) 893 for i := 0; i < valuesInRange; i++ { 894 this.content = append(this.content, uint16(firstOfRun+i)) 895 } 896 return this 897} 898 899func (ac *arrayContainer) numberOfRuns() (nr int) { 900 n := len(ac.content) 901 var runlen uint16 902 var cur, prev uint16 903 904 switch n { 905 case 0: 906 return 0 907 case 1: 908 return 1 909 default: 910 for i := 1; i < n; i++ { 911 prev = ac.content[i-1] 912 cur = ac.content[i] 913 914 if cur == prev+1 { 915 runlen++ 916 } else { 917 if cur < prev { 918 panic("then fundamental arrayContainer assumption of sorted ac.content was broken") 919 } 920 if cur == prev { 921 panic("then fundamental arrayContainer assumption of deduplicated content was broken") 922 } else { 923 nr++ 924 runlen = 0 925 } 926 } 927 } 928 nr++ 929 } 930 return 931} 932 933// convert to run or array *if needed* 934func (ac *arrayContainer) toEfficientContainer() container { 935 936 numRuns := ac.numberOfRuns() 937 938 sizeAsRunContainer := runContainer16SerializedSizeInBytes(numRuns) 939 sizeAsBitmapContainer := bitmapContainerSizeInBytes() 940 card := ac.getCardinality() 941 sizeAsArrayContainer := arrayContainerSizeInBytes(card) 942 943 if sizeAsRunContainer <= minOfInt(sizeAsBitmapContainer, sizeAsArrayContainer) { 944 return newRunContainer16FromArray(ac) 945 } 946 if card <= arrayDefaultMaxSize { 947 return ac 948 } 949 return ac.toBitmapContainer() 950} 951 952func (ac *arrayContainer) containerType() contype { 953 return arrayContype 954} 955 956func (ac *arrayContainer) addOffset(x uint16) []container { 957 low := &arrayContainer{} 958 high := &arrayContainer{} 959 for _, val := range ac.content { 960 y := uint32(val) + uint32(x) 961 if highbits(y) > 0 { 962 high.content = append(high.content, lowbits(y)) 963 } else { 964 low.content = append(low.content, lowbits(y)) 965 } 966 } 967 return []container{low, high} 968} 969