Function IntersectWithLinPacked

algo/packed.go:35–93

IntersectWithLinPacked performs the liner intersection between two compressed uid lists.

(u, v *pb.UidPack)

// IntersectWithLinPacked performs the liner intersection between two compressed uid lists.
func IntersectWithLinPacked(u, v *pb.UidPack) *pb.UidPack {
	if u == nil || v == nil {
		return nil
	}

	uDec := codec.NewDecoder(u)
	uuids := uDec.Uids()
	vDec := codec.NewDecoder(v)
	vuids := vDec.Uids()
	uIdx, vIdx := 0, 0
	result := codec.Encoder{BlockSize: int(u.BlockSize)}

	for {
		// Break if the end of a list has been reached.
		if len(uuids) == 0 || len(vuids) == 0 {
			break
		}

		// Load the next block of the encoded lists if necessary.
		if uIdx == len(uuids) {
			if uDec.Valid() {
				uuids = uDec.Next()
				uIdx = 0
			} else {
				break
			}

		}
		if vIdx == len(vuids) {
			if vDec.Valid() {
				vuids = vDec.Next()
				vIdx = 0
			} else {
				break
			}
		}

		uLen := len(uuids)
		vLen := len(vuids)

		for uIdx < uLen && vIdx < vLen {
			uid := uuids[uIdx]
			vid := vuids[vIdx]
			switch {
			case uid > vid:
				for vIdx = vIdx + 1; vIdx < vLen && vuids[vIdx] < uid; vIdx++ {
				}
			case uid == vid:
				result.Add(uid)
				vIdx++
				uIdx++
			default:
				for uIdx = uIdx + 1; uIdx < uLen && uuids[uIdx] < vid; uIdx++ {
				}
			}
		}
	}
	return result.Done()