// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package bitutils

import (
	
	

	
	
)

// IsMultipleOf64 returns whether v is a multiple of 64.
func ( int64) bool { return &63 == 0 }

// LeastSignificantBitMask returns a bit mask to return the least significant
// bits for a value starting from the bit index passed in. ie: if you want a
// mask for the 4 least significant bits, you call LeastSignificantBitMask(4)
func ( int64) uint64 {
	return (uint64(1) << ) - 1
}

// SetBitRun describes a run of contiguous set bits in a bitmap with Pos being
// the starting position of the run and Length being the number of bits.
type SetBitRun struct {
	Pos    int64
	Length int64
}

// AtEnd returns true if this bit run is the end of the set by checking
// that the length is 0.
func ( SetBitRun) () bool {
	return .Length == 0
}

// Equal returns whether rhs is the same run as s
func ( SetBitRun) ( SetBitRun) bool {
	return .Pos == .Pos && .Length == .Length
}

// SetBitRunReader is an interface for reading groups of contiguous set bits
// from a bitmap. The interface allows us to create different reader implementations
// that share the same interface easily such as a reverse set reader.
type SetBitRunReader interface {
	// NextRun will return the next run of contiguous set bits in the bitmap
	NextRun() SetBitRun
	// Reset allows re-using the reader by providing a new bitmap, offset and length. The arguments
	// match the New function for the reader being used.
	Reset([]byte, int64, int64)
	// VisitSetBitRuns calls visitFn for each set in a loop starting from the current position
	// it's roughly equivalent to simply looping, calling NextRun and calling visitFn on the run
	// for each run.
	VisitSetBitRuns(visitFn VisitFn) error
}

type baseSetBitRunReader struct {
	bitmap     []byte
	pos        int64
	length     int64
	remaining  int64
	curWord    uint64
	curNumBits int32
	reversed   bool

	firstBit uint64
}

// NewSetBitRunReader returns a SetBitRunReader for the bitmap starting at startOffset which will read
// numvalues bits.
func ( []byte, ,  int64) SetBitRunReader {
	return newBaseSetBitRunReader(, , , false)
}

// NewReverseSetBitRunReader returns a SetBitRunReader like NewSetBitRunReader, except it will
// return runs starting from the end of the bitmap until it reaches startOffset rather than starting
// at startOffset and reading from there. The SetBitRuns will still operate the same, so Pos
// will still be the position of the "left-most" bit of the run or the "start" of the run. It
// just returns runs starting from the end instead of starting from the beginning.
func ( []byte, ,  int64) SetBitRunReader {
	return newBaseSetBitRunReader(, , , true)
}

func newBaseSetBitRunReader( []byte, ,  int64,  bool) *baseSetBitRunReader {
	 := &baseSetBitRunReader{reversed: }
	.Reset(, , )
	return 
}

func ( *baseSetBitRunReader) ( []byte, ,  int64) {
	.bitmap = 
	.length = 
	.remaining = 
	.curNumBits = 0
	.curWord = 0

	if !.reversed {
		.pos =  / 8
		.firstBit = 1

		 := int8( % 8)
		if  > 0 &&  != 0 {
			.curNumBits = int32(utils.Min(int(), int(8-)))
			.curWord = .loadPartial(, int64(.curNumBits))
		}
		return
	}

	.pos = ( + ) / 8
	.firstBit = uint64(0x8000000000000000)
	 := int8(( + ) % 8)
	if  > 0 &&  != 0 {
		.pos++
		.curNumBits = int32(utils.Min(int(), int()))
		.curWord = .loadPartial(8-, int64(.curNumBits))
	}
}

func ( *baseSetBitRunReader) ( uint64,  int32) uint64 {
	if .reversed {
		return  << 
	}
	return  >> 
}

func ( *baseSetBitRunReader) ( uint64) int32 {
	if .reversed {
		return int32(bits.LeadingZeros64())
	}
	return int32(bits.TrailingZeros64())
}

func ( *baseSetBitRunReader) ( int8,  int64) uint64 {
	var  [8]byte
	 := bitutil.BytesForBits()
	if .reversed {
		.pos -= 
		copy([8-:], .bitmap[.pos:.pos+])
		return (binary.LittleEndian.Uint64([:]) << ) &^ LeastSignificantBitMask(64-)
	}

	copy([:], .bitmap[.pos:.pos+])
	.pos += 
	return (binary.LittleEndian.Uint64([:]) >> ) & LeastSignificantBitMask()
}

func ( *baseSetBitRunReader) () SetBitRun {
	 := .countFirstZeros(.curWord)
	if  >= .curNumBits {
		.remaining -= int64(.curNumBits)
		.curWord = 0
		.curNumBits = 0
		return SetBitRun{0, 0}
	}

	.curWord = .consumeBits(.curWord, )
	.curNumBits -= 
	.remaining -= int64()
	 := .position()

	 := .countFirstZeros(^.curWord)
	.curWord = .consumeBits(.curWord, )
	.curNumBits -= 
	.remaining -= int64()
	return SetBitRun{, int64()}
}

func ( *baseSetBitRunReader) () int64 {
	if .reversed {
		return .remaining
	}
	return .length - .remaining
}

func ( *baseSetBitRunReader) ( SetBitRun) SetBitRun {
	if .reversed {
		.Pos -= .Length
	}
	return 
}

func ( *baseSetBitRunReader) () ( uint64) {
	if .reversed {
		.pos -= 8
	}
	 = binary.LittleEndian.Uint64(.bitmap[.pos : .pos+8])
	if !.reversed {
		.pos += 8
	}
	return
}

func ( *baseSetBitRunReader) () {
	for .remaining >= 64 {
		.curWord = .loadFull()
		 := .countFirstZeros(.curWord)
		if  < 64 {
			.curWord = .consumeBits(.curWord, )
			.curNumBits = 64 - 
			.remaining -= int64()
			return
		}
		.remaining -= 64
	}
	// run of zeros continues in last bitmap word
	if .remaining > 0 {
		.curWord = .loadPartial(0, .remaining)
		.curNumBits = int32(.remaining)
		 := int32(utils.Min(int(.curNumBits), int(.countFirstZeros(.curWord))))
		.curWord = .consumeBits(.curWord, )
		.curNumBits -= 
		.remaining -= int64()
	}
}

func ( *baseSetBitRunReader) () int64 {
	var  int64
	if ^.curWord != 0 {
		 := .countFirstZeros(^.curWord)
		.remaining -= int64()
		.curWord = .consumeBits(.curWord, )
		.curNumBits -= 
		if .curNumBits != 0 {
			return int64()
		}
		 = int64()
	} else {
		.remaining -= 64
		.curNumBits = 0
		 = 64
	}

	for .remaining >= 64 {
		.curWord = .loadFull()
		 := .countFirstZeros(^.curWord)
		 += int64()
		.remaining -= int64()
		if  < 64 {
			.curWord = .consumeBits(.curWord, )
			.curNumBits = 64 - 
			return 
		}
	}

	if .remaining > 0 {
		.curWord = .loadPartial(0, .remaining)
		.curNumBits = int32(.remaining)
		 := .countFirstZeros(^.curWord)
		.curWord = .consumeBits(.curWord, )
		.curNumBits -= 
		.remaining -= int64()
		 += int64()
	}
	return 
}

func ( *baseSetBitRunReader) () SetBitRun {
	var (
		    int64 = 0
		 int64 = 0
	)

	if .curNumBits != 0 {
		 := .findCurrentRun()
		if .Length != 0 && .curNumBits != 0 {
			return .adjustRun()
		}
		 = .Pos
		 = .Length
	}

	if  == 0 {
		// we didn't get any ones in curWord, so we can skip any zeros
		// in the following words
		.skipNextZeros()
		if .remaining == 0 {
			return SetBitRun{0, 0}
		}
		 = .position()
	} else if .curNumBits == 0 {
		if .remaining >= 64 {
			.curWord = .loadFull()
			.curNumBits = 64
		} else if .remaining > 0 {
			.curWord = .loadPartial(0, .remaining)
			.curNumBits = int32(.remaining)
		} else {
			return .adjustRun(SetBitRun{, })
		}
		if (.curWord & .firstBit) == 0 {
			return .adjustRun(SetBitRun{, })
		}
	}

	 += .countNextOnes()
	return .adjustRun(SetBitRun{, })
}

// VisitFn is a callback function for visiting runs of contiguous bits
type VisitFn func(pos int64, length int64) error

func ( *baseSetBitRunReader) ( VisitFn) error {
	for {
		 := .NextRun()
		if .Length == 0 {
			break
		}

		if  := (.Pos, .Length);  != nil {
			return 
		}
	}
	return nil
}

// VisitSetBitRuns is just a convenience function for calling NewSetBitRunReader and then VisitSetBitRuns
func ( []byte,  int64,  int64,  VisitFn) error {
	if  == nil {
		return (0, )
	}
	 := NewSetBitRunReader(, , )
	for {
		 := .NextRun()
		if .Length == 0 {
			break
		}

		if  := (.Pos, .Length);  != nil {
			return 
		}
	}
	return nil
}

func ( []byte,  int64,  int64,  func(,  int64)) {
	if  == nil {
		(0, )
		return
	}
	 := NewSetBitRunReader(, , )
	for {
		 := .NextRun()
		if .Length == 0 {
			break
		}
		(.Pos, .Length)
	}
}