(sba *sparseBitArray, other *bitArray)
| 71 | } |
| 72 | |
| 73 | func andSparseWithDenseBitArray(sba *sparseBitArray, other *bitArray) BitArray { |
| 74 | if other.IsEmpty() { |
| 75 | return newSparseBitArray() |
| 76 | } |
| 77 | |
| 78 | // Use a duplicate of the sparse array to store the results of the |
| 79 | // bitwise and. More memory-efficient than allocating a new dense bit |
| 80 | // array. |
| 81 | // |
| 82 | // NOTE: this could be faster if we didn't copy the values as well |
| 83 | // (since they are overwritten), but I don't want this method to know |
| 84 | // too much about the internals of sparseBitArray. The performance hit |
| 85 | // should be minor anyway. |
| 86 | ba := sba.copy() |
| 87 | |
| 88 | // Run through the sparse array and attempt comparisons wherever |
| 89 | // possible against the dense bit array. |
| 90 | for selfIndex, selfValue := range ba.indices { |
| 91 | |
| 92 | if selfValue >= uint64(len(other.blocks)) { |
| 93 | // The dense bit array has been exhausted. This is the |
| 94 | // annoying case because we have to trim the sparse |
| 95 | // array to the size of the dense array. |
| 96 | ba.blocks = ba.blocks[:selfIndex-1] |
| 97 | ba.indices = ba.indices[:selfIndex-1] |
| 98 | |
| 99 | // once this is done, there are no more comparisons. |
| 100 | // We're ready to return |
| 101 | break |
| 102 | } |
| 103 | ba.blocks[selfIndex] = ba.blocks[selfIndex].and( |
| 104 | other.blocks[selfValue]) |
| 105 | |
| 106 | } |
| 107 | |
| 108 | // Ensure any zero'd blocks in the resulting sparse |
| 109 | // array are deleted |
| 110 | for i := 0; i < len(ba.blocks); i++ { |
| 111 | if ba.blocks[i] == 0 { |
| 112 | ba.blocks.deleteAtIndex(int64(i)) |
| 113 | ba.indices.deleteAtIndex(int64(i)) |
| 114 | i-- |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | return ba |
| 119 | } |
| 120 | |
| 121 | func andDenseWithDenseBitArray(dba, other *bitArray) BitArray { |
| 122 | min := minUint64(uint64(len(dba.blocks)), uint64(len(other.blocks))) |
searching dependent graphs…