// 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 (
	
	
	
	

	
	
	
)

// BitRun represents a run of bits with the same value of length Len
// with Set representing if the group of bits were 1 or 0.
type BitRun struct {
	Len int64
	Set bool
}

// BitRunReader is an interface that is usable by multiple callers to provide
// multiple types of bit run readers such as a reverse reader and so on.
//
// It's a convenience interface for counting contiguous set/unset bits in a bitmap.
// In places where BitBlockCounter can be used, then it would be preferred to use that
// as it would be faster than using BitRunReader.
type BitRunReader interface {
	NextRun() BitRun
}

func ( BitRun) () string {
	return fmt.Sprintf("{Length: %d, set=%t}", .Len, .Set)
}

type bitRunReader struct {
	bitmap       []byte
	pos          int64
	length       int64
	word         uint64
	curRunBitSet bool
}

// NewBitRunReader returns a reader for the given bitmap, offset and length that
// grabs runs of the same value bit at a time for easy iteration.
func ( []byte,  int64,  int64) BitRunReader {
	 := &bitRunReader{
		bitmap: [/8:],
		pos:     % 8,
		length: ( % 8) + ,
	}

	if  == 0 {
		return 
	}

	.curRunBitSet = bitutil.BitIsNotSet(, int())
	 :=  + .pos
	.loadWord()
	.word = .word &^ LeastSignificantBitMask(.pos)
	return 
}

// NextRun returns a new BitRun containing the number of contiguous bits with the
// same value. Len == 0 indicates the end of the bitmap.
func ( *bitRunReader) () BitRun {
	if .pos >= .length {
		return BitRun{0, false}
	}

	// This implementation relies on a efficient implementations of
	// CountTrailingZeros and assumes that runs are more often then
	// not.  The logic is to incrementally find the next bit change
	// from the current position.  This is done by zeroing all
	// bits in word_ up to position_ and using the TrailingZeroCount
	// to find the index of the next set bit.

	// The runs alternate on each call, so flip the bit.
	.curRunBitSet = !.curRunBitSet

	 := .pos
	 :=  & 63

	// Invert the word for proper use of CountTrailingZeros and
	// clear bits so CountTrailingZeros can do it magic.
	.word = ^.word &^ LeastSignificantBitMask()

	// Go  forward until the next change from unset to set.
	 := int64(bits.TrailingZeros64(.word)) - 
	.pos += 

	if IsMultipleOf64(.pos) && .pos < .length {
		.advanceUntilChange()
	}
	return BitRun{.pos - , .curRunBitSet}
}

func ( *bitRunReader) () {
	 := int64(0)
	for {
		.bitmap = .bitmap[arrow.Uint64SizeBytes:]
		.loadNextWord()
		 = int64(bits.TrailingZeros64(.word))
		.pos += 
		if !IsMultipleOf64(.pos) || .pos >= .length ||  <= 0 {
			break
		}
	}
}

func ( *bitRunReader) () {
	.loadWord(.length - .pos)
}

func ( *bitRunReader) ( int64) {
	.word = 0
	if  >= 64 {
		.word = binary.LittleEndian.Uint64(.bitmap)
	} else {
		 := bitutil.BytesForBits()
		 := (*(*[8]byte)(unsafe.Pointer(&.word)))[:]
		copy(, .bitmap[:])

		bitutil.SetBitTo(, int(), bitutil.BitIsNotSet(, int(-1)))
		// reset the value to little endian for big endian architectures
		.word = utils.ToLEUint64(.word)
	}

	// Two cases:
	//   1. For unset, CountTrailingZeros works naturally so we don't
	//   invert the word.
	//   2. Otherwise invert so we can use CountTrailingZeros.
	if .curRunBitSet {
		.word = ^.word
	}
}