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

import (
	
	
	
	
	
	

	
	
	
	
	
	
	
	
	
)

// Dictionary represents the type for dictionary-encoded data with a data
// dependent dictionary.
//
// A dictionary array contains an array of non-negative integers (the "dictionary"
// indices") along with a data type containing a "dictionary" corresponding to
// the distinct values represented in the data.
//
// For example, the array:
//
//	["foo", "bar", "foo", "bar", "foo", "bar"]
//
// with dictionary ["bar", "foo"], would have the representation of:
//
//	indices: [1, 0, 1, 0, 1, 0]
//	dictionary: ["bar", "foo"]
//
// The indices in principle may be any integer type.
type Dictionary struct {
	array

	indices arrow.Array
	dict    arrow.Array
}

// NewDictionaryArray constructs a dictionary array with the provided indices
// and dictionary using the given type.
func ( arrow.DataType, ,  arrow.Array) *Dictionary {
	 := &Dictionary{}
	.refCount.Add(1)
	 := NewData(, .Len(), .Data().Buffers(), .Data().Children(), .NullN(), .Data().Offset())
	.dictionary = .Data().(*Data)
	.Data().Retain()

	defer .Release()
	.setData()
	return 
}

// checkIndexBounds returns an error if any value in the provided integer
// arraydata is >= the passed upperlimit or < 0. otherwise nil
func checkIndexBounds( *Data,  uint64) error {
	if .length == 0 {
		return nil
	}

	var  uint64
	switch .dtype.ID() {
	case arrow.UINT8:
		 = math.MaxUint8
	case arrow.UINT16:
		 = math.MaxUint16
	case arrow.UINT32:
		 = math.MaxUint32
	case arrow.UINT64:
		 = math.MaxUint64
	}
	// for unsigned integers, if the values array is larger than the maximum
	// index value (especially for UINT8/UINT16), then there's no need to
	// boundscheck. for signed integers we still need to bounds check
	// because a value could be < 0.
	 :=  == 0
	if ! &&  >  {
		return nil
	}

	 := .offset
	 := .offset + .length

	// TODO(ARROW-15950): lift BitSetRunReader from parquet to utils
	// and use it here for performance improvement.

	switch .dtype.ID() {
	case arrow.INT8:
		 := arrow.Int8Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxInt8([:])
		if  < 0 ||  >= int8() {
			return fmt.Errorf("contains out of bounds index: min: %d, max: %d", , )
		}
	case arrow.UINT8:
		 := arrow.Uint8Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxUint8([:])
		if  >= uint8() {
			return fmt.Errorf("contains out of bounds index: max: %d", )
		}
	case arrow.INT16:
		 := arrow.Int16Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxInt16([:])
		if  < 0 ||  >= int16() {
			return fmt.Errorf("contains out of bounds index: min: %d, max: %d", , )
		}
	case arrow.UINT16:
		 := arrow.Uint16Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxUint16([:])
		if  >= uint16() {
			return fmt.Errorf("contains out of bounds index: max: %d", )
		}
	case arrow.INT32:
		 := arrow.Int32Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxInt32([:])
		if  < 0 ||  >= int32() {
			return fmt.Errorf("contains out of bounds index: min: %d, max: %d", , )
		}
	case arrow.UINT32:
		 := arrow.Uint32Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxUint32([:])
		if  >= uint32() {
			return fmt.Errorf("contains out of bounds index: max: %d", )
		}
	case arrow.INT64:
		 := arrow.Int64Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxInt64([:])
		if  < 0 ||  >= int64() {
			return fmt.Errorf("contains out of bounds index: min: %d, max: %d", , )
		}
	case arrow.UINT64:
		 := arrow.Uint64Traits.CastFromBytes(.buffers[1].Bytes())
		,  := utils.GetMinMaxUint64([.offset : .offset+.length])
		if  >=  {
			return fmt.Errorf("contains out of bounds value: max: %d", )
		}
	default:
		return fmt.Errorf("invalid type for bounds checking: %T", .dtype)
	}

	return nil
}

// NewValidatedDictionaryArray constructs a dictionary array from the provided indices
// and dictionary arrays, while also performing validation checks to ensure correctness
// such as bounds checking at are usually skipped for performance.
func ( *arrow.DictionaryType, ,  arrow.Array) (*Dictionary, error) {
	if .DataType().ID() != .IndexType.ID() {
		return nil, fmt.Errorf("dictionary type index (%T) does not match indices array type (%T)", .IndexType, .DataType())
	}

	if !arrow.TypeEqual(.ValueType, .DataType()) {
		return nil, fmt.Errorf("dictionary value type (%T) does not match dict array type (%T)", .ValueType, .DataType())
	}

	if  := checkIndexBounds(.Data().(*Data), uint64(.Len()));  != nil {
		return nil, 
	}

	return NewDictionaryArray(, , ), nil
}

// NewDictionaryData creates a strongly typed Dictionary array from
// an ArrayData object with a datatype of arrow.Dictionary and a dictionary
func ( arrow.ArrayData) *Dictionary {
	 := &Dictionary{}
	.refCount.Add(1)
	.setData(.(*Data))
	return 
}

func ( *Dictionary) () {
	.refCount.Add(1)
}

func ( *Dictionary) () {
	debug.Assert(.refCount.Load() > 0, "too many releases")

	if .refCount.Add(-1) == 0 {
		.data.Release()
		.data, .nullBitmapBytes = nil, nil
		.indices.Release()
		.indices = nil
		if .dict != nil {
			.dict.Release()
			.dict = nil
		}
	}
}

func ( *Dictionary) ( *Data) {
	.array.setData()

	 := .dtype.(*arrow.DictionaryType)
	if .dictionary == nil {
		if .length > 0 {
			panic("arrow/array: no dictionary set in Data for Dictionary array")
		}
	} else {
		debug.Assert(arrow.TypeEqual(.ValueType, .dictionary.DataType()), "mismatched dictionary value types")
	}

	 := NewData(.IndexType, .length, .buffers, .childData, .nulls, .offset)
	defer .Release()
	.indices = MakeFromData()
}

// Dictionary returns the values array that makes up the dictionary for this
// array.
func ( *Dictionary) () arrow.Array {
	if .dict == nil {
		.dict = MakeFromData(.data.dictionary)
	}
	return .dict
}

// Indices returns the underlying array of indices as it's own array
func ( *Dictionary) () arrow.Array {
	return .indices
}

// CanCompareIndices returns true if the dictionary arrays can be compared
// without having to unify the dictionaries themselves first.
// This means that the index types are equal too.
func ( *Dictionary) ( *Dictionary) bool {
	if !arrow.TypeEqual(.indices.DataType(), .indices.DataType()) {
		return false
	}

	 := int64(min(.data.dictionary.length, .data.dictionary.length))
	return SliceEqual(.Dictionary(), 0, , .Dictionary(), 0, )
}

func ( *Dictionary) ( int) string {
	if .IsNull() {
		return NullValueStr
	}
	return .Dictionary().ValueStr(.GetValueIndex())
}

func ( *Dictionary) () string {
	return fmt.Sprintf("{ dictionary: %v\n  indices: %v }", .Dictionary(), .Indices())
}

// GetValueIndex returns the dictionary index for the value at index i of the array.
// The actual value can be retrieved by using d.Dictionary().(valuetype).Value(d.GetValueIndex(i))
func ( *Dictionary) ( int) int {
	 := .data.buffers[1].Bytes()
	// we know the value is non-negative per the spec, so
	// we can use the unsigned value regardless.
	switch .indices.DataType().ID() {
	case arrow.UINT8, arrow.INT8:
		return int(uint8([.data.offset+]))
	case arrow.UINT16, arrow.INT16:
		return int(arrow.Uint16Traits.CastFromBytes()[.data.offset+])
	case arrow.UINT32, arrow.INT32:
		 := arrow.Uint32Traits.CastFromBytes()[.data.offset+]
		debug.Assert(bits.UintSize == 64 ||  <= math.MaxInt32, "arrow/dictionary: truncation of index value")
		return int()
	case arrow.UINT64, arrow.INT64:
		 := arrow.Uint64Traits.CastFromBytes()[.data.offset+]
		debug.Assert((bits.UintSize == 32 &&  <= math.MaxInt32) || (bits.UintSize == 64 &&  <= math.MaxInt64), "arrow/dictionary: truncation of index value")
		return int()
	}
	debug.Assert(false, "unreachable dictionary index")
	return -1
}

func ( *Dictionary) ( int) interface{} {
	if .IsNull() {
		return nil
	}
	 := .GetValueIndex()
	return .Dictionary().GetOneForMarshal()
}

func ( *Dictionary) () ([]byte, error) {
	 := make([]any, .Len())
	for  := range .Len() {
		[] = .GetOneForMarshal()
	}
	return json.Marshal()
}

func arrayEqualDict(,  *Dictionary) bool {
	return Equal(.Dictionary(), .Dictionary()) && Equal(.indices, .indices)
}

func arrayApproxEqualDict(,  *Dictionary,  equalOption) bool {
	return arrayApproxEqual(.Dictionary(), .Dictionary(), ) && arrayApproxEqual(.indices, .indices, )
}

// helper for building the properly typed indices of the dictionary builder
type IndexBuilder struct {
	Builder
	Append func(int)
}

func createIndexBuilder( memory.Allocator,  arrow.FixedWidthDataType) ( IndexBuilder,  error) {
	 = IndexBuilder{Builder: NewBuilder(, )}
	switch .ID() {
	case arrow.INT8:
		.Append = func( int) {
			.Builder.(*Int8Builder).Append(int8())
		}
	case arrow.UINT8:
		.Append = func( int) {
			.Builder.(*Uint8Builder).Append(uint8())
		}
	case arrow.INT16:
		.Append = func( int) {
			.Builder.(*Int16Builder).Append(int16())
		}
	case arrow.UINT16:
		.Append = func( int) {
			.Builder.(*Uint16Builder).Append(uint16())
		}
	case arrow.INT32:
		.Append = func( int) {
			.Builder.(*Int32Builder).Append(int32())
		}
	case arrow.UINT32:
		.Append = func( int) {
			.Builder.(*Uint32Builder).Append(uint32())
		}
	case arrow.INT64:
		.Append = func( int) {
			.Builder.(*Int64Builder).Append(int64())
		}
	case arrow.UINT64:
		.Append = func( int) {
			.Builder.(*Uint64Builder).Append(uint64())
		}
	default:
		debug.Assert(false, "dictionary index type must be integral")
		 = fmt.Errorf("dictionary index type must be integral, not %s", )
	}

	return
}

// helper function to construct an appropriately typed memo table based on
// the value type for the dictionary
func createMemoTable( memory.Allocator,  arrow.DataType) ( hashing.MemoTable,  error) {
	switch .ID() {
	case arrow.INT8:
		 = hashing.NewMemoTable[int8](0)
	case arrow.UINT8:
		 = hashing.NewMemoTable[uint8](0)
	case arrow.INT16:
		 = hashing.NewMemoTable[int16](0)
	case arrow.UINT16:
		 = hashing.NewMemoTable[uint16](0)
	case arrow.INT32:
		 = hashing.NewMemoTable[int32](0)
	case arrow.UINT32:
		 = hashing.NewMemoTable[uint32](0)
	case arrow.INT64:
		 = hashing.NewMemoTable[int64](0)
	case arrow.UINT64:
		 = hashing.NewMemoTable[uint64](0)
	case arrow.DURATION, arrow.TIMESTAMP, arrow.DATE64, arrow.TIME64:
		 = hashing.NewMemoTable[int64](0)
	case arrow.TIME32, arrow.DATE32, arrow.INTERVAL_MONTHS:
		 = hashing.NewMemoTable[int32](0)
	case arrow.FLOAT16:
		 = hashing.NewMemoTable[uint16](0)
	case arrow.FLOAT32:
		 = hashing.NewMemoTable[float32](0)
	case arrow.FLOAT64:
		 = hashing.NewMemoTable[float64](0)
	case arrow.BINARY, arrow.FIXED_SIZE_BINARY, arrow.DECIMAL32, arrow.DECIMAL64,
		arrow.DECIMAL128, arrow.DECIMAL256, arrow.INTERVAL_DAY_TIME, arrow.INTERVAL_MONTH_DAY_NANO:
		 = hashing.NewBinaryMemoTable(0, 0, NewBinaryBuilder(, arrow.BinaryTypes.Binary))
	case arrow.STRING:
		 = hashing.NewBinaryMemoTable(0, 0, NewBinaryBuilder(, arrow.BinaryTypes.String))
	case arrow.NULL:
	default:
		 = fmt.Errorf("unimplemented dictionary value type, %s", )
	}

	return
}

type DictionaryBuilder interface {
	Builder

	NewDictionaryArray() *Dictionary
	NewDelta() (indices, delta arrow.Array, err error)
	AppendArray(arrow.Array) error
	AppendIndices([]int, []bool)
	ResetFull()
	DictionarySize() int
}

type dictionaryBuilder struct {
	builder

	dt          *arrow.DictionaryType
	deltaOffset int
	memoTable   hashing.MemoTable
	idxBuilder  IndexBuilder
}

func createDictBuilder[ arrow.ValueType]( memory.Allocator,  IndexBuilder,  hashing.MemoTable,  *arrow.DictionaryType,  arrow.Array) DictionaryBuilder {
	 := &dictBuilder[]{
		dictionaryBuilder: dictionaryBuilder{
			builder:    builder{mem: },
			idxBuilder: ,
			memoTable:  ,
			dt:         ,
		},
	}
	.refCount.Add(1)

	if  != nil {
		if  := .InsertDictValues(.(arrValues[]));  != nil {
			panic()
		}
	}
	return 
}

func createBinaryDictBuilder( memory.Allocator,  IndexBuilder,  hashing.MemoTable,  *arrow.DictionaryType,  arrow.Array) DictionaryBuilder {
	 := &BinaryDictionaryBuilder{
		dictionaryBuilder: dictionaryBuilder{
			builder:    builder{mem: },
			idxBuilder: ,
			memoTable:  ,
			dt:         ,
		},
	}
	.refCount.Add(1)

	if  != nil {
		switch v := .(type) {
		case *String:
			if  := .InsertStringDictValues();  != nil {
				panic()
			}
		case *Binary:
			if  := .InsertDictValues();  != nil {
				panic()
			}
		}
	}
	return 
}

func createFixedSizeDictBuilder[ fsbType]( memory.Allocator,  IndexBuilder,  hashing.MemoTable,  *arrow.DictionaryType,  arrow.Array) DictionaryBuilder {
	var  
	 := &fixedSizeDictionaryBuilder[]{
		dictionaryBuilder: dictionaryBuilder{
			builder:    builder{mem: },
			idxBuilder: ,
			memoTable:  ,
			dt:         ,
		},
		byteWidth: int(unsafe.Sizeof()),
	}
	.refCount.Add(1)

	if  != nil {
		if  := .InsertDictValues(.(arrValues[]));  != nil {
			panic()
		}
	}

	return 
}

// NewDictionaryBuilderWithDict initializes a dictionary builder and inserts the values from `init` as the first
// values in the dictionary, but does not insert them as values into the array.
func ( memory.Allocator,  *arrow.DictionaryType,  arrow.Array) DictionaryBuilder {
	if  != nil && !arrow.TypeEqual(.ValueType, .DataType()) {
		panic(fmt.Errorf("arrow/array: cannot initialize dictionary type %T with array of type %T", .ValueType, .DataType()))
	}

	,  := createIndexBuilder(, .IndexType.(arrow.FixedWidthDataType))
	if  != nil {
		panic(fmt.Errorf("arrow/array: unsupported builder for index type of %T", ))
	}

	,  := createMemoTable(, .ValueType)
	if  != nil {
		panic(fmt.Errorf("arrow/array: unsupported builder for value type of %T", ))
	}

	switch .ValueType.ID() {
	case arrow.NULL:
		 := &NullDictionaryBuilder{
			dictionaryBuilder: dictionaryBuilder{
				builder:    builder{mem: },
				idxBuilder: ,
				memoTable:  ,
				dt:         ,
			},
		}
		.refCount.Add(1)
		debug.Assert( == nil, "arrow/array: doesn't make sense to init a null dictionary")
		return 
	case arrow.UINT8:
		return createDictBuilder[uint8](, , , , )
	case arrow.INT8:
		return createDictBuilder[int8](, , , , )
	case arrow.UINT16:
		return createDictBuilder[uint16](, , , , )
	case arrow.INT16:
		return createDictBuilder[int16](, , , , )
	case arrow.UINT32:
		return createDictBuilder[uint32](, , , , )
	case arrow.INT32:
		return createDictBuilder[int32](, , , , )
	case arrow.UINT64:
		return createDictBuilder[uint64](, , , , )
	case arrow.INT64:
		return createDictBuilder[int64](, , , , )
	case arrow.FLOAT16:
		return createDictBuilder[float16.Num](, , , , )
	case arrow.FLOAT32:
		return createDictBuilder[float32](, , , , )
	case arrow.FLOAT64:
		return createDictBuilder[float64](, , , , )
	case arrow.STRING, arrow.BINARY:
		return createBinaryDictBuilder(, , , , )
	case arrow.FIXED_SIZE_BINARY:
		 := &FixedSizeBinaryDictionaryBuilder{
			dictionaryBuilder: dictionaryBuilder{
				builder:    builder{mem: },
				idxBuilder: ,
				memoTable:  ,
				dt:         ,
			},
			byteWidth: .ValueType.(*arrow.FixedSizeBinaryType).ByteWidth,
		}
		.refCount.Add(1)

		if  != nil {
			if  = .InsertDictValues(.(*FixedSizeBinary));  != nil {
				panic()
			}
		}
		return 
	case arrow.DATE32:
		return createDictBuilder[arrow.Date32](, , , , )
	case arrow.DATE64:
		return createDictBuilder[arrow.Date64](, , , , )
	case arrow.TIMESTAMP:
		return createDictBuilder[arrow.Timestamp](, , , , )
	case arrow.TIME32:
		return createDictBuilder[arrow.Time32](, , , , )
	case arrow.TIME64:
		return createDictBuilder[arrow.Time64](, , , , )
	case arrow.INTERVAL_MONTHS:
		return createDictBuilder[arrow.MonthInterval](, , , , )
	case arrow.INTERVAL_DAY_TIME:
		return createFixedSizeDictBuilder[arrow.DayTimeInterval](, , , , )
	case arrow.DECIMAL32:
		return createFixedSizeDictBuilder[decimal.Decimal32](, , , , )
	case arrow.DECIMAL64:
		return createFixedSizeDictBuilder[decimal.Decimal64](, , , , )
	case arrow.DECIMAL128:
		return createFixedSizeDictBuilder[decimal.Decimal128](, , , , )
	case arrow.DECIMAL256:
		return createFixedSizeDictBuilder[decimal.Decimal256](, , , , )
	case arrow.LIST:
	case arrow.STRUCT:
	case arrow.SPARSE_UNION:
	case arrow.DENSE_UNION:
	case arrow.DICTIONARY:
	case arrow.MAP:
	case arrow.EXTENSION:
	case arrow.FIXED_SIZE_LIST:
	case arrow.DURATION:
		return createDictBuilder[arrow.Duration](, , , , )
	case arrow.LARGE_STRING:
	case arrow.LARGE_BINARY:
	case arrow.LARGE_LIST:
	case arrow.INTERVAL_MONTH_DAY_NANO:
		return createFixedSizeDictBuilder[arrow.MonthDayNanoInterval](, , , , )
	}

	panic("arrow/array: unimplemented dictionary key type")
}

func ( memory.Allocator,  *arrow.DictionaryType) DictionaryBuilder {
	return NewDictionaryBuilderWithDict(, , nil)
}

func ( *dictionaryBuilder) () arrow.DataType { return .dt }

func ( *dictionaryBuilder) () {
	debug.Assert(.refCount.Load() > 0, "too many releases")

	if .refCount.Add(-1) == 0 {
		.idxBuilder.Release()
		.idxBuilder.Builder = nil
		if ,  := .memoTable.(*hashing.BinaryMemoTable);  {
			.Release()
		}
		.memoTable = nil
	}
}

func ( *dictionaryBuilder) () {
	.length += 1
	.nulls += 1
	.idxBuilder.AppendNull()
}

func ( *dictionaryBuilder) ( int) {
	for  := 0;  < ; ++ {
		.AppendNull()
	}
}

func ( *dictionaryBuilder) () {
	.length += 1
	.idxBuilder.AppendEmptyValue()
}

func ( *dictionaryBuilder) ( int) {
	for  := 0;  < ; ++ {
		.AppendEmptyValue()
	}
}

func ( *dictionaryBuilder) ( int) {
	.idxBuilder.Reserve()
}

func ( *dictionaryBuilder) ( int) {
	.idxBuilder.Resize()
	.length = .idxBuilder.Len()
}

func ( *dictionaryBuilder) () {
	.reset()
	.idxBuilder.NewArray().Release()
	.memoTable.Reset()
}

func ( *dictionaryBuilder) () int { return .idxBuilder.Cap() }

func ( *dictionaryBuilder) ( int) bool { return .idxBuilder.IsNull() }

func ( *dictionaryBuilder) ( []byte) error {
	 := json.NewDecoder(bytes.NewReader())
	,  := .Token()
	if  != nil {
		return 
	}

	if ,  := .(json.Delim); ! ||  != '[' {
		return fmt.Errorf("dictionary builder must unpack from json array, found %s", )
	}

	return .Unmarshal()
}

func ( *dictionaryBuilder) ( *json.Decoder) error {
	 := NewBuilder(.mem, .dt.ValueType)
	defer .Release()

	if  := .Unmarshal();  != nil {
		return 
	}

	 := .NewArray()
	defer .Release()
	return .AppendArray()
}

func ( *dictionaryBuilder) ( string) error {
	 := NewBuilder(.mem, .dt.ValueType)
	defer .Release()

	if  := .AppendValueFromString();  != nil {
		return 
	}

	 := .NewArray()
	defer .Release()
	return .AppendArray()
}

func ( *dictionaryBuilder) ( *json.Decoder) error {
	 := NewBuilder(.mem, .dt.ValueType)
	defer .Release()

	if  := .UnmarshalOne();  != nil {
		return 
	}

	 := .NewArray()
	defer .Release()
	return .AppendArray()
}

func ( *dictionaryBuilder) () arrow.Array {
	return .NewDictionaryArray()
}

func ( *dictionaryBuilder) () *Data {
	, ,  := .newWithDictOffset(0)
	if  != nil {
		panic()
	}

	.dtype = .dt
	.dictionary = 
	return 
}

func ( *dictionaryBuilder) () *Dictionary {
	 := &Dictionary{}
	.refCount.Add(1)

	 := .newData()
	.setData()
	.Release()
	return 
}

func ( *dictionaryBuilder) ( int) (,  *Data,  error) {
	 := .idxBuilder.NewArray()
	defer .Release()

	 = .Data().(*Data)

	.deltaOffset = .memoTable.Size()
	,  = GetDictArrayData(.mem, .dt.ValueType, .memoTable, )
	.reset()
	.Retain()
	return
}

// NewDelta returns the dictionary indices and a delta dictionary since the
// last time NewArray or NewDictionaryArray were called, and resets the state
// of the builder (except for the dictionary / memotable)
func ( *dictionaryBuilder) () (,  arrow.Array,  error) {
	, ,  := .newWithDictOffset(.deltaOffset)
	if  != nil {
		return nil, nil, 
	}

	defer .Release()
	defer .Release()
	,  = MakeFromData(), MakeFromData()
	return
}

func ( *dictionaryBuilder) ( interface{}) error {
	, ,  := .memoTable.GetOrInsert()
	return 
}

func ( *dictionaryBuilder) ( []byte) error {
	, ,  := .memoTable.GetOrInsertBytes()
	return 
}

func ( *dictionaryBuilder) ( interface{}) error {
	, ,  := .memoTable.GetOrInsert()
	.idxBuilder.Append()
	.length += 1
	return 
}

func ( *dictionaryBuilder) ( []byte) error {
	, ,  := .memoTable.GetOrInsertBytes()
	.idxBuilder.Append()
	.length += 1
	return 
}

func getvalFn( arrow.Array) func( int) interface{} {
	switch typedarr := .(type) {
	case *Int8:
		return func( int) interface{} { return .Value() }
	case *Uint8:
		return func( int) interface{} { return .Value() }
	case *Int16:
		return func( int) interface{} { return .Value() }
	case *Uint16:
		return func( int) interface{} { return .Value() }
	case *Int32:
		return func( int) interface{} { return .Value() }
	case *Uint32:
		return func( int) interface{} { return .Value() }
	case *Int64:
		return func( int) interface{} { return .Value() }
	case *Uint64:
		return func( int) interface{} { return .Value() }
	case *Float16:
		return func( int) interface{} { return .Value().Uint16() }
	case *Float32:
		return func( int) interface{} { return .Value() }
	case *Float64:
		return func( int) interface{} { return .Value() }
	case *Duration:
		return func( int) interface{} { return int64(.Value()) }
	case *Timestamp:
		return func( int) interface{} { return int64(.Value()) }
	case *Date64:
		return func( int) interface{} { return int64(.Value()) }
	case *Time64:
		return func( int) interface{} { return int64(.Value()) }
	case *Time32:
		return func( int) interface{} { return int32(.Value()) }
	case *Date32:
		return func( int) interface{} { return int32(.Value()) }
	case *MonthInterval:
		return func( int) interface{} { return int32(.Value()) }
	case *Binary:
		return func( int) interface{} { return .Value() }
	case *FixedSizeBinary:
		return func( int) interface{} { return .Value() }
	case *String:
		return func( int) interface{} { return .Value() }
	case *Decimal32:
		return func( int) interface{} {
			 := .Value()
			return (*(*[arrow.Decimal32SizeBytes]byte)(unsafe.Pointer(&)))[:]
		}
	case *Decimal64:
		return func( int) interface{} {
			 := .Value()
			return (*(*[arrow.Decimal64SizeBytes]byte)(unsafe.Pointer(&)))[:]
		}
	case *Decimal128:
		return func( int) interface{} {
			 := .Value()
			return (*(*[arrow.Decimal128SizeBytes]byte)(unsafe.Pointer(&)))[:]
		}
	case *Decimal256:
		return func( int) interface{} {
			 := .Value()
			return (*(*[arrow.Decimal256SizeBytes]byte)(unsafe.Pointer(&)))[:]
		}
	case *DayTimeInterval:
		return func( int) interface{} {
			 := .Value()
			return (*(*[arrow.DayTimeIntervalSizeBytes]byte)(unsafe.Pointer(&)))[:]
		}
	case *MonthDayNanoInterval:
		return func( int) interface{} {
			 := .Value()
			return (*(*[arrow.MonthDayNanoIntervalSizeBytes]byte)(unsafe.Pointer(&)))[:]
		}
	}

	panic("arrow/array: invalid dictionary value type")
}

func ( *dictionaryBuilder) ( arrow.Array) error {
	debug.Assert(arrow.TypeEqual(.dt.ValueType, .DataType()), "wrong value type of array to append to dict")

	 := getvalFn()
	for  := 0;  < .Len(); ++ {
		if .IsNull() {
			.AppendNull()
		} else {
			if  := .appendValue(());  != nil {
				return 
			}
		}
	}
	return nil
}

func ( *dictionaryBuilder) () IndexBuilder {
	return .idxBuilder
}

func ( *dictionaryBuilder) ( []int,  []bool) {
	.length += len()
	switch idxbldr := .idxBuilder.Builder.(type) {
	case *Int8Builder:
		 := make([]int8, len())
		for ,  := range  {
			[] = int8()
		}
		.AppendValues(, )
	case *Int16Builder:
		 := make([]int16, len())
		for ,  := range  {
			[] = int16()
		}
		.AppendValues(, )
	case *Int32Builder:
		 := make([]int32, len())
		for ,  := range  {
			[] = int32()
		}
		.AppendValues(, )
	case *Int64Builder:
		 := make([]int64, len())
		for ,  := range  {
			[] = int64()
		}
		.AppendValues(, )
	case *Uint8Builder:
		 := make([]uint8, len())
		for ,  := range  {
			[] = uint8()
		}
		.AppendValues(, )
	case *Uint16Builder:
		 := make([]uint16, len())
		for ,  := range  {
			[] = uint16()
		}
		.AppendValues(, )
	case *Uint32Builder:
		 := make([]uint32, len())
		for ,  := range  {
			[] = uint32()
		}
		.AppendValues(, )
	case *Uint64Builder:
		 := make([]uint64, len())
		for ,  := range  {
			[] = uint64()
		}
		.AppendValues(, )
	}
}

func ( *dictionaryBuilder) () int {
	return .memoTable.Size()
}

type NullDictionaryBuilder struct {
	dictionaryBuilder
}

func ( *NullDictionaryBuilder) () arrow.Array {
	return .NewDictionaryArray()
}

func ( *NullDictionaryBuilder) () *Dictionary {
	 := .idxBuilder.NewArray()
	defer .Release()

	 := .Data().(*Data)
	 := NewNull(0)
	defer .Release()

	.data.Retain()
	.dtype = .dt
	.dictionary = .data

	return NewDictionaryData()
}

func ( *NullDictionaryBuilder) ( arrow.Array) error {
	if .DataType().ID() != arrow.NULL {
		return fmt.Errorf("cannot append non-null array to null dictionary")
	}

	for  := 0;  < .(*Null).Len(); ++ {
		.AppendNull()
	}
	return nil
}

type dictBuilder[ arrow.ValueType] struct {
	dictionaryBuilder
}

func ( *dictBuilder[]) ( ) error {
	return .appendValue()
}

type arrValues[ arrow.ValueType] interface {
	Values() []
}

func ( *dictBuilder[]) ( arrValues[]) ( error) {
	for ,  := range .Values() {
		if  = .insertDictValue();  != nil {
			break
		}
	}
	return
}

type Int8DictionaryBuilder = dictBuilder[int8]
type Uint8DictionaryBuilder = dictBuilder[uint8]
type Int16DictionaryBuilder = dictBuilder[int16]
type Uint16DictionaryBuilder = dictBuilder[uint16]
type Int32DictionaryBuilder = dictBuilder[int32]
type Uint32DictionaryBuilder = dictBuilder[uint32]
type Int64DictionaryBuilder = dictBuilder[int64]
type Uint64DictionaryBuilder = dictBuilder[uint64]
type Float16DictionaryBuilder = dictBuilder[float16.Num]
type Float32DictionaryBuilder = dictBuilder[float32]
type Float64DictionaryBuilder = dictBuilder[float64]
type DurationDictionaryBuilder = dictBuilder[arrow.Duration]
type TimestampDictionaryBuilder = dictBuilder[arrow.Timestamp]
type Time32DictionaryBuilder = dictBuilder[arrow.Time32]
type Time64DictionaryBuilder = dictBuilder[arrow.Time64]
type Date32DictionaryBuilder = dictBuilder[arrow.Date32]
type Date64DictionaryBuilder = dictBuilder[arrow.Date64]
type MonthIntervalDictionaryBuilder = dictBuilder[arrow.MonthInterval]
type DayTimeDictionaryBuilder = fixedSizeDictionaryBuilder[arrow.DayTimeInterval]
type Decimal32DictionaryBuilder = fixedSizeDictionaryBuilder[decimal.Decimal32]
type Decimal64DictionaryBuilder = fixedSizeDictionaryBuilder[decimal.Decimal64]
type Decimal128DictionaryBuilder = fixedSizeDictionaryBuilder[decimal.Decimal128]
type Decimal256DictionaryBuilder = fixedSizeDictionaryBuilder[decimal.Decimal256]
type MonthDayNanoDictionaryBuilder = fixedSizeDictionaryBuilder[arrow.MonthDayNanoInterval]

type BinaryDictionaryBuilder struct {
	dictionaryBuilder
}

func ( *BinaryDictionaryBuilder) ( []byte) error {
	if  == nil {
		.AppendNull()
		return nil
	}

	return .appendBytes()
}

func ( *BinaryDictionaryBuilder) ( string) error { return .appendBytes([]byte()) }
func ( *BinaryDictionaryBuilder) ( *Binary) ( error) {
	if !arrow.TypeEqual(.DataType(), .dt.ValueType) {
		return fmt.Errorf("dictionary insert type mismatch: cannot insert values of type %T to dictionary type %T", .DataType(), .dt.ValueType)
	}

	for  := 0;  < .Len(); ++ {
		if  = .insertDictBytes(.Value());  != nil {
			break
		}
	}
	return
}

func ( *BinaryDictionaryBuilder) ( *String) ( error) {
	if !arrow.TypeEqual(.DataType(), .dt.ValueType) {
		return fmt.Errorf("dictionary insert type mismatch: cannot insert values of type %T to dictionary type %T", .DataType(), .dt.ValueType)
	}

	for  := 0;  < .Len(); ++ {
		if  = .insertDictValue(.Value());  != nil {
			break
		}
	}
	return
}

func ( *BinaryDictionaryBuilder) ( int) int {
	switch b := .idxBuilder.Builder.(type) {
	case *Uint8Builder:
		return int(.Value())
	case *Int8Builder:
		return int(.Value())
	case *Uint16Builder:
		return int(.Value())
	case *Int16Builder:
		return int(.Value())
	case *Uint32Builder:
		return int(.Value())
	case *Int32Builder:
		return int(.Value())
	case *Uint64Builder:
		return int(.Value())
	case *Int64Builder:
		return int(.Value())
	default:
		return -1
	}
}

func ( *BinaryDictionaryBuilder) ( int) []byte {
	switch mt := .memoTable.(type) {
	case *hashing.BinaryMemoTable:
		return .Value()
	}
	return nil
}

func ( *BinaryDictionaryBuilder) ( int) string {
	return string(.Value())
}

type fsbType interface {
	arrow.DayTimeInterval | arrow.MonthDayNanoInterval |
		decimal.Decimal32 | decimal.Decimal64 | decimal.Decimal128 | decimal.Decimal256
}

type fixedSizeDictionaryBuilder[ fsbType] struct {
	dictionaryBuilder
	byteWidth int
}

func ( *fixedSizeDictionaryBuilder[]) ( ) error {
	if ,  := any().([]byte);  {
		return .appendBytes([:.byteWidth])
	}

	 := struct {
		 *
		  int
		  int
	}{&, .byteWidth, .byteWidth}
	 := *(*[]byte)(unsafe.Pointer(&))
	return .appendValue()
}

func ( *fixedSizeDictionaryBuilder[]) ( arrValues[]) ( error) {
	 := arrow.GetBytes(.Values())
	for len() > 0 {
		if  = .insertDictBytes([:.byteWidth]);  != nil {
			break
		}
		 = [.byteWidth:]
	}
	return
}

type FixedSizeBinaryDictionaryBuilder struct {
	dictionaryBuilder
	byteWidth int
}

func ( *FixedSizeBinaryDictionaryBuilder) ( []byte) error {
	return .appendValue([:.byteWidth])
}

func ( *FixedSizeBinaryDictionaryBuilder) ( *FixedSizeBinary) ( error) {
	var (
		 = .data.offset * .byteWidth
		 = (.data.offset + .data.length) * .byteWidth
	)
	 := .valueBytes[:]
	for len() > 0 {
		if  = .insertDictValue([:.byteWidth]);  != nil {
			break
		}
		 = [.byteWidth:]
	}
	return
}

func ( []int32) bool {
	for ,  := range  {
		if  != int32() {
			return false
		}
	}
	return true
}

func ( memory.Allocator,  arrow.ArrayData, ,  arrow.DataType,  arrow.ArrayData,  []int32) (arrow.ArrayData, error) {
	// inType may be different from data->dtype if data is ExtensionType
	if .ID() != arrow.DICTIONARY || .ID() != arrow.DICTIONARY {
		return nil, errors.New("arrow/array: expected dictionary type")
	}

	var (
		   = .(*arrow.DictionaryType)
		  = .(*arrow.DictionaryType)
		  = .IndexType
		 = .IndexType.(arrow.FixedWidthDataType)
	)

	if .ID() == .ID() && IsTrivialTransposition() {
		// index type and values will be identical, we can reuse the existing buffers
		return NewDataWithDictionary(, .Len(), []*memory.Buffer{.Buffers()[0], .Buffers()[1]},
			.NullN(), .Offset(), .(*Data)), nil
	}

	// default path: compute the transposed indices as a new buffer
	 := memory.NewResizableBuffer()
	.Resize(.Len() * int(bitutil.BytesForBits(int64(.BitWidth()))))
	defer .Release()

	// shift null buffer if original offset is non-zero
	var  *memory.Buffer
	if .Offset() != 0 && .NullN() != 0 {
		 = memory.NewResizableBuffer()
		.Resize(int(bitutil.BytesForBits(int64(.Len()))))
		bitutil.CopyBitmap(.Buffers()[0].Bytes(), .Offset(), .Len(), .Bytes(), 0)
		defer .Release()
	} else {
		 = .Buffers()[0]
	}

	 := NewDataWithDictionary(, .Len(),
		[]*memory.Buffer{, }, .NullN(), 0, .(*Data))
	 := utils.TransposeIntsBuffers(, ,
		.Buffers()[1].Bytes(), .Bytes(), .Offset(), .offset, .Len(), )
	return , 
}

// DictionaryUnifier defines the interface used for unifying, and optionally producing
// transposition maps for, multiple dictionary arrays incrementally.
type DictionaryUnifier interface {
	// Unify adds the provided array of dictionary values to be unified.
	Unify(arrow.Array) error
	// UnifyAndTranspose adds the provided array of dictionary values,
	// just like Unify but returns an allocated buffer containing a mapping
	// to transpose dictionary indices.
	UnifyAndTranspose(dict arrow.Array) (transposed *memory.Buffer, err error)
	// GetResult returns the dictionary type (choosing the smallest index type
	// that can represent all the values) and the new unified dictionary.
	//
	// Calling GetResult clears the existing dictionary from the unifier so it
	// can be reused by calling Unify/UnifyAndTranspose again with new arrays.
	GetResult() (outType arrow.DataType, outDict arrow.Array, err error)
	// GetResultWithIndexType is like GetResult, but allows specifying the type
	// of the dictionary indexes rather than letting the unifier pick. If the
	// passed in index type isn't large enough to represent all of the dictionary
	// values, an error will be returned instead. The new unified dictionary
	// is returned.
	GetResultWithIndexType(indexType arrow.DataType) (arrow.Array, error)
	// Release should be called to clean up any allocated scratch memo-table used
	// for building the unified dictionary.
	Release()
}

type unifier struct {
	mem       memory.Allocator
	valueType arrow.DataType
	memoTable hashing.MemoTable
}

// NewDictionaryUnifier constructs and returns a new dictionary unifier for dictionaries
// of valueType, using the provided allocator for allocating the unified dictionary
// and the memotable used for building it.
//
// This will only work for non-nested types currently. a nested valueType or dictionary type
// will result in an error.
func ( memory.Allocator,  arrow.DataType) (DictionaryUnifier, error) {
	,  := createMemoTable(, )
	if  != nil {
		return nil, 
	}
	return &unifier{
		mem:       ,
		valueType: ,
		memoTable: ,
	}, nil
}

func ( *unifier) () {
	if ,  := .memoTable.(*hashing.BinaryMemoTable);  {
		.Release()
	}
}

func ( *unifier) ( arrow.Array) ( error) {
	if !arrow.TypeEqual(.valueType, .DataType()) {
		return fmt.Errorf("dictionary type different from unifier: %s, expected: %s", .DataType(), .valueType)
	}

	 := getvalFn()
	for  := 0;  < .Len(); ++ {
		if .IsNull() {
			.memoTable.GetOrInsertNull()
			continue
		}

		if _, _,  = .memoTable.GetOrInsert(());  != nil {
			return 
		}
	}
	return
}

func ( *unifier) ( arrow.Array) ( *memory.Buffer,  error) {
	if !arrow.TypeEqual(.valueType, .DataType()) {
		return nil, fmt.Errorf("dictionary type different from unifier: %s, expected: %s", .DataType(), .valueType)
	}

	 = memory.NewResizableBuffer(.mem)
	.Resize(arrow.Int32Traits.BytesRequired(.Len()))

	 := arrow.Int32Traits.CastFromBytes(.Bytes())
	 := getvalFn()
	for  := 0;  < .Len(); ++ {
		if .IsNull() {
			,  := .memoTable.GetOrInsertNull()
			[] = int32()
			continue
		}

		, ,  := .memoTable.GetOrInsert(())
		if  != nil {
			.Release()
			return nil, 
		}
		[] = int32()
	}
	return
}

func ( *unifier) () ( arrow.DataType,  arrow.Array,  error) {
	 := .memoTable.Size()
	var  arrow.DataType
	switch {
	case  <= math.MaxInt8:
		 = arrow.PrimitiveTypes.Int8
	case  <= math.MaxInt16:
		 = arrow.PrimitiveTypes.Int16
	case  <= math.MaxInt32:
		 = arrow.PrimitiveTypes.Int32
	default:
		 = arrow.PrimitiveTypes.Int64
	}
	 = &arrow.DictionaryType{IndexType: , ValueType: .valueType}

	,  := GetDictArrayData(.mem, .valueType, .memoTable, 0)
	if  != nil {
		return nil, nil, 
	}

	.memoTable.Reset()

	defer .Release()
	 = MakeFromData()
	return
}

func ( *unifier) ( arrow.DataType) (arrow.Array, error) {
	 := .memoTable.Size()
	var  bool
	switch .ID() {
	case arrow.UINT8:
		 =  > math.MaxUint8
	case arrow.INT8:
		 =  > math.MaxInt8
	case arrow.UINT16:
		 =  > math.MaxUint16
	case arrow.INT16:
		 =  > math.MaxInt16
	case arrow.UINT32:
		 = uint() > math.MaxUint32
	case arrow.INT32:
		 =  > math.MaxInt32
	case arrow.UINT64:
		 = uint64() > uint64(math.MaxUint64)
	case arrow.INT64:
	default:
		return nil, fmt.Errorf("arrow/array: invalid dictionary index type: %s, must be integral", )
	}
	if  {
		return nil, errors.New("arrow/array: cannot combine dictionaries. unified dictionary requires a larger index type")
	}

	,  := GetDictArrayData(.mem, .valueType, .memoTable, 0)
	if  != nil {
		return nil, 
	}

	.memoTable.Reset()

	defer .Release()
	return MakeFromData(), nil
}

type binaryUnifier struct {
	mem       memory.Allocator
	memoTable *hashing.BinaryMemoTable
}

// NewBinaryDictionaryUnifier constructs and returns a new dictionary unifier for dictionaries
// of binary values, using the provided allocator for allocating the unified dictionary
// and the memotable used for building it.
func ( memory.Allocator) DictionaryUnifier {
	return &binaryUnifier{
		mem:       ,
		memoTable: hashing.NewBinaryMemoTable(0, 0, NewBinaryBuilder(, arrow.BinaryTypes.Binary)),
	}
}

func ( *binaryUnifier) () {
	.memoTable.Release()
}

func ( *binaryUnifier) ( arrow.Array) ( error) {
	if !arrow.TypeEqual(arrow.BinaryTypes.Binary, .DataType()) {
		return fmt.Errorf("dictionary type different from unifier: %s, expected: %s", .DataType(), arrow.BinaryTypes.Binary)
	}

	 := .(*Binary)
	for  := 0;  < .Len(); ++ {
		if .IsNull() {
			.memoTable.GetOrInsertNull()
			continue
		}

		if _, _,  = .memoTable.GetOrInsertBytes(.Value());  != nil {
			return 
		}
	}
	return
}

func ( *binaryUnifier) ( arrow.Array) ( *memory.Buffer,  error) {
	if !arrow.TypeEqual(arrow.BinaryTypes.Binary, .DataType()) {
		return nil, fmt.Errorf("dictionary type different from unifier: %s, expected: %s", .DataType(), arrow.BinaryTypes.Binary)
	}

	 = memory.NewResizableBuffer(.mem)
	.Resize(arrow.Int32Traits.BytesRequired(.Len()))

	 := arrow.Int32Traits.CastFromBytes(.Bytes())
	 := .(*Binary)
	for  := 0;  < .Len(); ++ {
		if .IsNull() {
			,  := .memoTable.GetOrInsertNull()
			[] = int32()
			continue
		}

		, ,  := .memoTable.GetOrInsertBytes(.Value())
		if  != nil {
			.Release()
			return nil, 
		}
		[] = int32()
	}
	return
}

func ( *binaryUnifier) () ( arrow.DataType,  arrow.Array,  error) {
	 := .memoTable.Size()
	var  arrow.DataType
	switch {
	case  <= math.MaxInt8:
		 = arrow.PrimitiveTypes.Int8
	case  <= math.MaxInt16:
		 = arrow.PrimitiveTypes.Int16
	case  <= math.MaxInt32:
		 = arrow.PrimitiveTypes.Int32
	default:
		 = arrow.PrimitiveTypes.Int64
	}
	 = &arrow.DictionaryType{IndexType: , ValueType: arrow.BinaryTypes.Binary}

	,  := GetDictArrayData(.mem, arrow.BinaryTypes.Binary, .memoTable, 0)
	if  != nil {
		return nil, nil, 
	}

	.memoTable.Reset()

	defer .Release()
	 = MakeFromData()
	return
}

func ( *binaryUnifier) ( arrow.DataType) (arrow.Array, error) {
	 := .memoTable.Size()
	var  bool
	switch .ID() {
	case arrow.UINT8:
		 =  > math.MaxUint8
	case arrow.INT8:
		 =  > math.MaxInt8
	case arrow.UINT16:
		 =  > math.MaxUint16
	case arrow.INT16:
		 =  > math.MaxInt16
	case arrow.UINT32:
		 = uint() > math.MaxUint32
	case arrow.INT32:
		 =  > math.MaxInt32
	case arrow.UINT64:
		 = uint64() > uint64(math.MaxUint64)
	case arrow.INT64:
	default:
		return nil, fmt.Errorf("arrow/array: invalid dictionary index type: %s, must be integral", )
	}
	if  {
		return nil, errors.New("arrow/array: cannot combine dictionaries. unified dictionary requires a larger index type")
	}

	,  := GetDictArrayData(.mem, arrow.BinaryTypes.Binary, .memoTable, 0)
	if  != nil {
		return nil, 
	}

	.memoTable.Reset()

	defer .Release()
	return MakeFromData(), nil
}

func unifyRecursive( memory.Allocator,  arrow.DataType,  []*Data) ( bool,  error) {
	debug.Assert(len() != 0, "must provide non-zero length chunk slice")
	var  arrow.DataType

	if .ID() == arrow.EXTENSION {
		 = 
		 = .(arrow.ExtensionType).StorageType()
	}

	if ,  := .(arrow.NestedType);  {
		 := make([]*Data, len())
		for ,  := range .Fields() {
			for ,  := range  {
				[] = .childData[].(*Data)
			}

			,  := (, .Type, )
			if  != nil {
				return false, 
			}
			if  {
				// only when unification actually occurs
				for  := range  {
					[].childData[] = []
				}
				 = true
			}
		}
	}

	if .ID() == arrow.DICTIONARY {
		 := .(*arrow.DictionaryType)
		var (
			     DictionaryUnifier
			 arrow.Array
		)
		// unify any nested dictionaries first, but the unifier doesn't support
		// nested dictionaries yet so this would fail.
		,  = NewDictionaryUnifier(, .ValueType)
		if  != nil {
			return , 
		}
		defer .Release()
		 := make([]*memory.Buffer, len())
		for ,  := range  {
			debug.Assert(.dictionary != nil, "missing dictionary data for dictionary array")
			 := MakeFromData(.dictionary)
			defer .Release()
			if [],  = .UnifyAndTranspose();  != nil {
				return
			}
			defer [].Release()
		}

		if ,  = .GetResultWithIndexType(.IndexType);  != nil {
			return
		}
		defer .Release()

		for  := range  {
			,  := TransposeDictIndices(, [], , , .Data(), arrow.Int32Traits.CastFromBytes([].Bytes()))
			if  != nil {
				return , 
			}
			[].Release()
			[] = .(*Data)
			if  != nil {
				[].dtype = 
			}
		}
		 = true
	}

	return
}

// UnifyChunkedDicts takes a chunked array of dictionary type and will unify
// the dictionary across all of the chunks with the returned chunked array
// having all chunks share the same dictionary.
//
// The return from this *must* have Release called on it unless an error is returned
// in which case the *arrow.Chunked will be nil.
//
// If there is 1 or fewer chunks, then nothing is modified and this function will just
// call Retain on the passed in Chunked array (so Release can safely be called on it).
// The same is true if the type of the array is not a dictionary or if no changes are
// needed for all of the chunks to be using the same dictionary.
func ( memory.Allocator,  *arrow.Chunked) (*arrow.Chunked, error) {
	if len(.Chunks()) <= 1 {
		.Retain()
		return , nil
	}

	 := make([]*Data, len(.Chunks()))
	for ,  := range .Chunks() {
		.Data().Retain()
		[] = .Data().(*Data)
	}
	,  := unifyRecursive(, .DataType(), )
	if  != nil || ! {
		for ,  := range  {
			.Release()
		}
		if  == nil {
			.Retain()
		} else {
			 = nil
		}
		return , 
	}

	 := make([]arrow.Array, len())
	for ,  := range  {
		[] = MakeFromData()
		defer [].Release()
		.Release()
	}

	return arrow.NewChunked(.DataType(), ), nil
}

// UnifyTableDicts performs UnifyChunkedDicts on each column of the table so that
// any dictionary column will have the dictionaries of its chunks unified.
//
// The returned Table should always be Release'd unless a non-nil error was returned,
// in which case the table returned will be nil.
func ( memory.Allocator,  arrow.Table) (arrow.Table, error) {
	 := make([]arrow.Column, .NumCols())
	for  := 0;  < int(.NumCols()); ++ {
		,  := UnifyChunkedDicts(, .Column().Data())
		if  != nil {
			return nil, 
		}
		defer .Release()
		[] = *arrow.NewColumn(.Schema().Field(), )
		defer [].Release()
	}
	return NewTable(.Schema(), , .NumRows()), nil
}

type dictWrapper[ arrow.ValueType] struct {
	*Dictionary

	typedDict arrow.TypedArray[]
}

// NewDictWrapper creates a simple wrapper around a Dictionary array that provides
// a Value method which will use the underlying dictionary to return the value
// at the given index. This simplifies the interaction of a dictionary array to
// provide a typed interface as if it were a non-dictionary array.
func [ arrow.ValueType]( *Dictionary) (arrow.TypedArray[], error) {
	,  := .Dictionary().(arrow.TypedArray[])
	if ! {
		return nil, fmt.Errorf("arrow/array: dictionary type %s is not a typed array of %T", .Dictionary().DataType(), (*)(nil))
	}

	return &dictWrapper[]{
		Dictionary: ,
		typedDict:  ,
	}, nil
}

func ( *dictWrapper[]) ( int)  {
	return .typedDict.Value(.GetValueIndex())
}

var (
	_ arrow.Array = (*Dictionary)(nil)
	_ Builder     = (*dictionaryBuilder)(nil)
)