// Copyright 2023 ChainSafe Systems (ON)
// SPDX-License-Identifier: LGPL-3.0-only

package grandpa

import (
	"errors"
	"fmt"

	"slices"

	shareddata "github.com/ChainSafe/gossamer/internal/client/consensus/common/shared-data"
	pgrandpa "github.com/ChainSafe/gossamer/internal/primitives/consensus/grandpa"
	forktree "github.com/ChainSafe/gossamer/internal/utils/fork-tree"
	grandpa "github.com/ChainSafe/gossamer/pkg/finality-grandpa"
	"golang.org/x/exp/constraints"
)

var (
	errInvalidAuthoritySet = errors.New("invalid authority set, either empty or with" +
		" an authority weight set to 0")
	errDuplicateAuthoritySetChanges             = errors.New("duplicate authority set HashNumber")
	errMultiplePendingForcedAuthoritySetChanges = errors.New("multiple pending forced authority set " +
		"changes are not allowed")
	errForcedAuthoritySetChangeDependencyUnsatisfied = errors.New("a pending forced authority set HashNumber " +
		"could not be applied since it must be applied after the pending standard HashNumber")
	errForkTree             = errors.New("invalid operation in the pending HashNumber tree")
	errInvalidAuthorityList = errors.New("invalid authority list")
)

// IsDescendentOf is the function definition to determine if target is a descendant of base
type IsDescendentOf[H comparable] func(base, target H) (bool, error)

// setIDNumber represents the set id and block number of an authority set HashNumber
type setIDNumber[N constraints.Unsigned] struct {
	SetID       uint64
	BlockNumber N
}

// HashNumber is a generic representation of hash and number
type HashNumber[H, N any] struct {
	Hash   H
	Number N
}

// appliedChanges represents the median and new set when a forced change has occurred
type appliedChanges[H comparable, N constraints.Unsigned] struct {
	median N
	set    AuthoritySet[H, N]
}

// status of the set after changes were applied.
type status[H comparable, N constraints.Unsigned] struct {
	// Whether internal changes were made.
	Changed bool
	// Not nil when underlying authority set has changed, containing the
	// block where that set changed.
	NewSetBlock *HashNumber[H, N]
}

// SharedAuthoritySet A shared authority set
type SharedAuthoritySet[H comparable, N constraints.Unsigned] struct {
	inner shareddata.SharedData[AuthoritySet[H, N]]
}

// Get the current set ID. This is incremented every time the set changes.
func (sas *SharedAuthoritySet[H, N]) SetID() uint64 {
	authSet := sas.inner.Data()
	return authSet.SetID
}

// CurrentAuthorities will get the current authorities and their weights (for the current set ID).
func (sas *SharedAuthoritySet[H, N]) CurrentAuthorities() grandpa.VoterSet[pgrandpa.AuthorityID] {
	authSet := sas.inner.Data()
	idWeights := make([]grandpa.IDWeight[pgrandpa.AuthorityID], len(authSet.CurrentAuthorities))
	for i, auth := range authSet.CurrentAuthorities {
		idWeights[i] = grandpa.IDWeight[pgrandpa.AuthorityID]{
			ID:     auth.AuthorityID,
			Weight: uint64(auth.AuthorityWeight),
		}
	}
	voterSet := grandpa.NewVoterSet[pgrandpa.AuthorityID](idWeights)
	if voterSet == nil {
		panic("CurrentAuthorities is non-empty and weights are non-zero; constructor and all" +
			" mutating operations on AuthoritySet ensure this.")
	}
	return *voterSet
}

// Current Get the current set id and a reference to the current authority set.
func (sas *SharedAuthoritySet[H, N]) Current() (uint64, pgrandpa.AuthorityList) {
	authSet := sas.inner.Data()
	return authSet.current()
}

func (sas *SharedAuthoritySet[H, N]) revert() { //nolint //skipcq: SCC-U1000
	authSet := sas.inner.Data()
	authSet.revert()
}

func (sas *SharedAuthoritySet[H, N]) nextChange(bestHash H, //nolint //skipcq: SCC-U1000
	isDescendentOf IsDescendentOf[H]) (*HashNumber[H, N], error) {
	authSet := sas.inner.Data()
	return authSet.nextChange(bestHash, isDescendentOf)
}

func (sas *SharedAuthoritySet[H, N]) addStandardChange(pending PendingChange[H, N], //nolint //skipcq: SCC-U1000
	isDescendentOf IsDescendentOf[H]) error {
	authSet := sas.inner.Data()
	return authSet.addStandardChange(pending, isDescendentOf)
}

func (sas *SharedAuthoritySet[H, N]) addForcedChange(pending PendingChange[H, N], //nolint //skipcq: SCC-U1000
	isDescendentOf IsDescendentOf[H]) error {
	authSet := sas.inner.Data()
	return authSet.addForcedChange(pending, isDescendentOf)
}

func (sas *SharedAuthoritySet[H, N]) addPendingChange(pending PendingChange[H, N], //nolint //skipcq: SCC-U1000
	isDescendentOf IsDescendentOf[H]) error {
	authSet := sas.inner.Data()
	return authSet.addPendingChange(pending, isDescendentOf)
}

// PendingChanges inspects pending changes. Standard pending changes are iterated first, and the changes in the roots
// are traversed in pre-order, afterwards all forced changes are iterated.
func (sas *SharedAuthoritySet[H, N]) PendingChanges() []PendingChange[H, N] {
	authSet := sas.inner.Data()
	return authSet.pendingChanges()
}

// currentLimit will get the earliest limit-block number, if any. If there are pending changes across different forks,
// this method will return the earliest effective number (across the different branches) that is higher or equal to the
// given min number.
//
// Only standard changes are taken into account for the current limit, since any existing forced change should preclude
// the voter from voting.
func (sas *SharedAuthoritySet[H, N]) currentLimit(min N) (limit *N) {
	authSet := sas.inner.Data()
	return authSet.currentLimit(min)
}

func (sas *SharedAuthoritySet[H, N]) applyForcedChanges( //nolint:unused
	bestHash H,
	bestNumber N,
	isDescendentOf IsDescendentOf[H],
	initialSync bool,
	// TODO: telemtry,
) (newSet *appliedChanges[H, N], err error) {
	authSet := sas.inner.Data()
	return authSet.applyForcedChanges(bestHash, bestNumber, isDescendentOf, initialSync)
}

// applyStandardChanges will apply or prune any pending transitions based on a finality trigger. This method ensures
// that if there are multiple changes in the same branch, finalising this block won't finalise past multiple
// transitions (i.e. transitions must be finalised in-order). The given function isDescendentOf should return true if
// the second hash (target) is a descendent of the first hash (base).
//
// When the set has changed, the return value will be a status type where newSetBlockInfo is the canonical block where
// the set last changed (i.e. the given hash and number).
func (sas *SharedAuthoritySet[H, N]) applyStandardChanges( //nolint: unused
	finalisedHash H,
	finalisedNumber N,
	isDescendentOf IsDescendentOf[H],
	initialSync bool,
	// TODO: telemetry,
) (status[H, N], error) {
	authSet := sas.inner.Data()
	return authSet.applyStandardChanges(finalisedHash, finalisedNumber, isDescendentOf, initialSync)
}

// EnactsStandardChange Check whether the given finalised block number enacts any standard authority set change
// (without triggering it), ensuring that if there are multiple changes in the same branch, finalising this block won't
// finalise past multiple transitions (i.e. transitions must be finalised in-order). Returns *true if the block being
// finalised enacts a change that can be immediately applied, *false if the block being finalised enacts a change but
// it cannot be applied yet since there are other dependent changes, and nil if no change is enacted. The given
// function isDescendentOf should return true if the second hash (target) is a descendent of the first hash (base).
func (sas *SharedAuthoritySet[H, N]) EnactsStandardChange(finalisedHash H,
	finalisedNumber N,
	isDescendentOf IsDescendentOf[H]) (*bool, error) {
	authSet := sas.inner.Data()
	return authSet.EnactsStandardChange(finalisedHash, finalisedNumber, isDescendentOf)
}

// AuthoritySet A set of authorities.
type AuthoritySet[H comparable, N constraints.Unsigned] struct {
	// The current active authorities.
	CurrentAuthorities pgrandpa.AuthorityList
	// The current set id.
	SetID uint64
	// Tree of pending standard changes across forks. Standard changes are
	// enacted on finality and must be enacted (i.e. finalised) in-order across
	// a given branch
	PendingStandardChanges forktree.ForkTree[H, N, PendingChange[H, N]]
	// Pending forced changes across different forks (at most one per fork).
	// Forced changes are enacted on block depth (not finality), for this
	// reason only one forced HashNumber should exist per fork. When trying to
	// apply forced changes we keep track of any pending standard changes that
	// they may depend on, this is done by making sure that any pending HashNumber
	// that is an ancestor of the forced changed and its effective block number
	// is lower than the last finalised block (as signalled in the forced
	// HashNumber) must be applied beforehand.
	PendingForcedChanges []PendingChange[H, N]
	// Track at which blocks the set id changed. This is useful when we need to prove finality for
	// a given block since we can figure out what set the block belongs to and when the set
	// started/ended.
	AuthoritySetChanges AuthoritySetChanges[N]
}

// invalidAuthorityList authority sets must be non-empty and all weights must be greater than 0
func invalidAuthorityList(authorities pgrandpa.AuthorityList) bool { //skipcq:  RVV-B0001
	if len(authorities) == 0 {
		return true
	}

	for _, authority := range authorities {
		if authority.AuthorityWeight == 0 {
			return true
		}
	}
	return false
}

// NewGenesisAuthoritySet constructs a genesis set with given authorities.
func NewGenesisAuthoritySet[H comparable, N constraints.Unsigned](
	initial pgrandpa.AuthorityList,
) (authSet *AuthoritySet[H, N], err error) {
	if invalidAuthorityList(initial) {
		return nil, errInvalidAuthorityList
	}

	return &AuthoritySet[H, N]{
		CurrentAuthorities: initial,
	}, nil
}

// NewAuthoritySet creates a new AuthoritySet
func NewAuthoritySet[H comparable, N constraints.Unsigned](
	authorities pgrandpa.AuthorityList,
	setID uint64,
	pendingStandardChanges forktree.ForkTree[H, N, PendingChange[H, N]],
	pendingForcedChanges []PendingChange[H, N],
	authoritySetChanges AuthoritySetChanges[N],
) (authSet *AuthoritySet[H, N], err error) {
	if invalidAuthorityList(authorities) {
		return nil, errInvalidAuthorityList
	}

	return &AuthoritySet[H, N]{
		CurrentAuthorities:     authorities,
		SetID:                  setID,
		PendingStandardChanges: pendingStandardChanges,
		PendingForcedChanges:   pendingForcedChanges,
		AuthoritySetChanges:    authoritySetChanges,
	}, nil
}

// Clone creates a copy of the AuthoritySet.
func (authSet *AuthoritySet[H, N]) Clone() AuthoritySet[H, N] {
	return AuthoritySet[H, N]{
		CurrentAuthorities:     slices.Clone(authSet.CurrentAuthorities),
		SetID:                  authSet.SetID,
		PendingStandardChanges: authSet.PendingStandardChanges.Clone(),
		PendingForcedChanges:   slices.Clone(authSet.PendingForcedChanges),
		AuthoritySetChanges:    slices.Clone(authSet.AuthoritySetChanges),
	}
}

// current retrieves the current set id and a reference to the current authority set.
func (authSet *AuthoritySet[H, N]) current() (uint64, pgrandpa.AuthorityList) {
	return authSet.SetID, authSet.CurrentAuthorities
}

// Revert to a specified block given its `hash` and `number`.
// This removes all the authority set changes that were announced after
// the revert point.
// Revert point is identified by `number` and `hash`.
func (authSet *AuthoritySet[H, N]) revert() { //nolint //skipcq: SCC-U1000 //skipcq:  RVV-B0001
	panic("AuthoritySet.revert not implemented yet")
}

// Returns the block hash and height at which the next pending HashNumber in
// the given chain (i.e. it includes `bestHash`) was signalled, nil if
// there are no pending changes for the given chain.
func (authSet *AuthoritySet[H, N]) nextChange(bestHash H, //skipcq:  RVV-B0001
	isDescendentOf IsDescendentOf[H]) (*HashNumber[H, N], error) {
	var forced *HashNumber[H, N]
	for _, c := range authSet.PendingForcedChanges {
		isDesc, err := isDescendentOf(c.CanonHash, bestHash)
		if err != nil {
			return nil, err
		}
		if !isDesc {
			continue
		}
		forced = &HashNumber[H, N]{
			Hash:   c.CanonHash,
			Number: c.CanonHeight,
		}
		break
	}

	var standard *HashNumber[H, N]
	for _, changeNode := range authSet.PendingStandardChanges.Roots() {
		c := changeNode.Data
		isDesc, err := isDescendentOf(c.CanonHash, bestHash)
		if err != nil {
			return nil, err
		}
		if !isDesc {
			continue
		}
		standard = &HashNumber[H, N]{
			Hash:   c.CanonHash,
			Number: c.CanonHeight,
		}
		break
	}

	switch {
	case standard != nil && forced != nil:
		if forced.Number < standard.Number {
			return forced, nil
		}
		return standard, nil
	case forced != nil:
		return forced, nil
	case standard != nil:
		return standard, nil
	default:
		return nil, nil
	}
}

func (authSet *AuthoritySet[H, N]) addStandardChange(
	pending PendingChange[H, N],
	isDescendentOf IsDescendentOf[H]) error {
	hash := pending.CanonHash
	number := pending.CanonHeight

	logger.Debugf(
		"inserting potential standard set HashNumber signalled at block %d (delayed by %d blocks).",
		number, pending.Delay,
	)

	_, err := authSet.PendingStandardChanges.Import(hash, number, pending, isDescendentOf)
	if err != nil {
		return err
	}

	logger.Debugf(
		"There are now %d alternatives for the next pending standard HashNumber (roots), "+
			"and a total of %d pending standard changes (across all forks)",
		len(authSet.PendingStandardChanges.Roots()),
		len(slices.Collect(authSet.PendingStandardChanges.Iter())),
	)

	return nil
}

func (pc PendingChange[H, N]) GreaterThan(other PendingChange[H, N]) bool {
	effectiveNumberGreaterThan := pc.EffectiveNumber() > other.EffectiveNumber()
	cannonHeighGreaterThan := pc.EffectiveNumber() == other.EffectiveNumber() &&
		pc.CanonHeight > other.CanonHeight

	return effectiveNumberGreaterThan || cannonHeighGreaterThan
}

func (pc PendingChange[H, N]) LessThan(other PendingChange[H, N]) bool {
	effectiveNumberLessThan := pc.EffectiveNumber() < other.EffectiveNumber()
	cannonHeighLessThan := pc.EffectiveNumber() == other.EffectiveNumber() &&
		pc.CanonHeight < other.CanonHeight

	return effectiveNumberLessThan || cannonHeighLessThan
}

func (authSet *AuthoritySet[H, N]) addForcedChange(
	pending PendingChange[H, N],
	isDescendentOf IsDescendentOf[H]) error {
	for _, change := range authSet.PendingForcedChanges {
		if change.CanonHash == pending.CanonHash {
			return errDuplicateAuthoritySetChanges
		}

		isDescendent, err := isDescendentOf(change.CanonHash, pending.CanonHash)
		if err != nil {
			return fmt.Errorf("addForcedChange: checking isDescendentOf: %w", err)
		}

		if isDescendent {
			return errMultiplePendingForcedAuthoritySetChanges
		}
	}

	// Changes are inserted in ascending order
	idx, _ := slices.BinarySearchFunc(
		authSet.PendingForcedChanges,
		pending,
		func(change, toInsert PendingChange[H, N]) int {
			switch {
			case toInsert.LessThan(change):
				return 1
			case toInsert.GreaterThan(change):
				return -1
			default:
				return 0
			}
		},
	)

	logger.Debugf(
		"inserting potential forced set HashNumber at block number %d (delayed by %d blocks).",
		pending.CanonHeight, pending.Delay,
	)

	// Insert HashNumber at index
	if len(authSet.PendingForcedChanges) == idx {
		authSet.PendingForcedChanges = append(authSet.PendingForcedChanges, pending)
	} else if len(authSet.PendingForcedChanges) > idx {
		authSet.PendingForcedChanges = append(
			authSet.PendingForcedChanges[:idx+1], authSet.PendingForcedChanges[idx:]...)
		authSet.PendingForcedChanges[idx] = pending
	} else {
		panic("invalid insertion into pending forced changes")
	}

	logger.Debugf(
		"there are now %d pending forced changes",
		len(authSet.PendingForcedChanges),
	)

	return nil
}

// addPendingChange will note an upcoming pending transition. Multiple pending standard changes
// on the same branch can be added as long as they don't overlap. Forced
// changes are restricted to one per fork. This method assumes that changes
// on the same branch will be added in-order. The given function
// `isDescendentOf` should return `true` if the second hash (target) is a
// descendent of the first hash (base).
func (authSet *AuthoritySet[H, N]) addPendingChange(
	pending PendingChange[H, N],
	isDescendentOf IsDescendentOf[H]) error {
	if invalidAuthorityList(pending.NextAuthorities) {
		return errInvalidAuthoritySet
	}

	switch pending.DelayKind.(type) {
	case delayKindFinalized:
		return authSet.addStandardChange(pending, isDescendentOf)
	case delayKindBest[N]:
		return authSet.addForcedChange(pending, isDescendentOf)
	default:
		panic("DelayKind is invalid type")
	}
}

// pendingChanges will inspect pending changes. Standard pending changes are iterated first, and the changes in the
// roots are traversed in pre-order, afterwards all forced changes are iterated.
func (authSet *AuthoritySet[H, N]) pendingChanges() []PendingChange[H, N] { //skipcq:  RVV-B0001
	// get everything from standard HashNumber roots
	var changes []PendingChange[H, N]
	for change := range authSet.PendingStandardChanges.Iter() {
		changes = append(changes, change.Data)
	}

	// append forced changes
	changes = append(changes, authSet.PendingForcedChanges...)

	return changes
}

// currentLimit gets the earliest limit-block number, if any. If there are pending changes across different forks, this
// method will return the earliest effective number (across the different branches) that is higher or equal to the
// given min number.
//
// Only standard changes are taken into account for the current limit, since any existing forced HashNumber should
// preclude the voter from voting.
func (authSet *AuthoritySet[H, N]) currentLimit(min N) (limit *N) {
	roots := authSet.PendingStandardChanges.Roots()
	for i := 0; i < len(roots); i++ {
		effectiveNumber := roots[i].Data.EffectiveNumber()
		if effectiveNumber >= min {
			if limit == nil {
				limit = &effectiveNumber
			} else if effectiveNumber < *limit {
				limit = &effectiveNumber
			}
		}
	}
	return limit
}

// ApplyForcedChanges applies or prunes any pending transitions based on a best-block trigger.
//
// Returns a pointer to the median and new_set when a forced HashNumber has occurred. The median represents the median
// last finalised block at the time the HashNumber was signalled, and it should be used as the canon block when
// starting the new grandpa voter. Only alters the internal state in this case.
//
// These transitions are always forced and do not lead to justifications which light clients can follow.
//
// Forced changes can only be applied after all pending standard changes that it depends on have been applied. If any
// pending standard HashNumber exists that is an ancestor of a given forced changed and which effective block number
// is lower than the last finalised block (as defined by the forced HashNumber), then the forced HashNumber cannot be
// applied. An error will be returned in that case which will prevent block import.
func (authSet *AuthoritySet[H, N]) applyForcedChanges(bestHash H, //skipcq:  RVV-B0001
	bestNumber N,
	isDescendentOf IsDescendentOf[H],
	initialSync bool,
	// TODO: telemetry
) (newSet *appliedChanges[H, N], err error) {

	for _, change := range authSet.PendingForcedChanges {
		effectiveNumber := change.EffectiveNumber()
		if effectiveNumber != bestNumber {
			continue
		}
		// check if the given best block is in the same branch as the block that signalled the HashNumber.
		isDesc, err := isDescendentOf(change.CanonHash, bestHash)
		// Avoid case where err is returned because canonHash == bestHash
		if change.CanonHash != bestHash && err != nil {
			return nil, err
		}
		if change.CanonHash == bestHash || isDesc {
			switch delayKindType := change.DelayKind.(type) {
			case delayKindBest[N]:
				medianLastFinalized := delayKindType.MedianLastFinalized
				roots := authSet.PendingStandardChanges.Roots()
				for _, standardChangeNode := range roots {
					standardChange := standardChangeNode.Data

					isDescStandard, err := isDescendentOf(standardChange.CanonHash, change.CanonHash)
					if err != nil {
						return nil, err
					}
					if standardChange.EffectiveNumber() <= medianLastFinalized && isDescStandard {
						logger.Infof(
							"Not applying authority set HashNumber forced at block %d, "+
								"due to pending standard HashNumber at block %d",
							change.CanonHeight, standardChange.EffectiveNumber())
						return nil, errForcedAuthoritySetChangeDependencyUnsatisfied
					}
				}

				// apply this change: make the set canonical
				l := logger.Infof
				if initialSync {
					l = logger.Debugf
				}
				l("👴 Applying authority set change forced at block #%d", change.CanonHeight)

				// TODO telemetry

				authSetChanges := authSet.AuthoritySetChanges
				authSetChanges.append(authSet.SetID, medianLastFinalized)
				newSet = &appliedChanges[H, N]{
					medianLastFinalized,
					AuthoritySet[H, N]{
						CurrentAuthorities:     change.NextAuthorities,
						SetID:                  authSet.SetID + 1,
						PendingStandardChanges: forktree.NewForkTree[H, N, PendingChange[H, N]](), // new set, new changes
						PendingForcedChanges:   []PendingChange[H, N]{},
						AuthoritySetChanges:    authSetChanges,
					},
				}
				return newSet, nil
			default:
				panic("pending_forced_changes only contains forced changes; forced changes have delay kind Best")
			}
		}
	}

	return newSet, nil
}

// applyStandardChanges applies or prunes any pending transitions based on a finality trigger. This method ensures that
// if there are multiple changes in the same branch, finalising this block won't finalise past multiple transitions
// (i.e. transitions must be finalised in-order). The given function `isDescendentOf` should return `true` if the
// second hash (target) is a descendent of the first hash (base).
//
// When the set has changed, the return value will be a status type where newSetBlock is the canonical block where the
// set last changed (i.e. the given hash and number).
func (authSet *AuthoritySet[H, N]) applyStandardChanges( //skipcq:  RVV-B0001
	finalisedHash H,
	finalisedNumber N,
	isDescendentOf IsDescendentOf[H],
	initialSync bool,
) (status[H, N], error) {
	// TODO telemetry here is just a place holder, replace with real

	status := status[H, N]{}
	finalisationResult, err := authSet.PendingStandardChanges.FinalizeWithDescendentIf(finalisedHash,
		finalisedNumber,
		isDescendentOf,
		func(change PendingChange[H, N]) bool {
			return change.EffectiveNumber() <= finalisedNumber
		})
	if err != nil {
		return status, err
	}

	switch val := finalisationResult.(type) {
	case forktree.FinalizationResultUnchanged:
		return status, nil
	case forktree.FinalizationResultChanged[PendingChange[H, N]]:
		change := val
		// Changed Case
		status.Changed = true

		// Flush pending forced changes to re add
		pendingForcedChanges := authSet.PendingForcedChanges
		authSet.PendingForcedChanges = []PendingChange[H, N]{}

		// we will keep all forced changes for any later blocks and that are a descendent of the finalised block
		// (i.e. they are part of this branch).
		for _, forcedChange := range pendingForcedChanges {
			isDesc, err := isDescendentOf(finalisedHash, forcedChange.CanonHash)
			if err != nil {
				return status, err
			}
			if forcedChange.EffectiveNumber() > finalisedNumber && isDesc {
				authSet.PendingForcedChanges = append(authSet.PendingForcedChanges, forcedChange)
			}
		}

		if change.Value != nil {
			var level func(format string, args ...interface{}) = logger.Debugf
			if initialSync {
				level = logger.Infof
			}
			level("👴 Applying authority set scheduled at block #%d", change.Value.CanonHeight)

			// TODO add telemetry

			// Store the setID together with the last block_number for the set
			authSet.AuthoritySetChanges.append(authSet.SetID, finalisedNumber)
			authSet.CurrentAuthorities = change.Value.NextAuthorities
			authSet.SetID++

			status.NewSetBlock = &HashNumber[H, N]{
				Hash:   finalisedHash,
				Number: finalisedNumber,
			}
		}

		return status, nil
	default:
		panic("invalid type for FinalizationResult")
	}
}

// EnactsStandardChange checks whether the given finalised block number enacts any standard authority set HashNumber
// (without triggering it), ensuring that if there are multiple changes in the same branch, finalising this block won't
// finalise past multiple transitions (i.e. transitions must be finalised in-order). Returns *true if the block being
// finalised enacts a HashNumber that can be immediately applied, *false if the block being finalised enacts a
// HashNumber but it cannot be applied yet since there are other dependent changes, and nil if no HashNumber is
// enacted. The given function `isDescendentOf` should return `true` if the second hash (target) is a descendent of the
// first hash (base).
func (authSet *AuthoritySet[H, N]) EnactsStandardChange( //skipcq:  RVV-B0001
	finalisedHash H, finalisedNumber N, isDescendentOf IsDescendentOf[H]) (*bool, error) {
	applied, err := authSet.PendingStandardChanges.FinalizesAnyWithDescendentIf(finalisedHash,
		finalisedNumber,
		isDescendentOf,
		func(change PendingChange[H, N]) bool {
			return change.EffectiveNumber() == finalisedNumber
		})
	if err != nil {
		return nil, fmt.Errorf("%w: %v", errForkTree, err)
	}
	return applied, nil
}

// delayKind are the kinds of delays for pending changes.
type delayKind interface {
	isDelayKind()
}
type delayKindTypes[N constraints.Unsigned] interface {
	delayKindFinalized | delayKindBest[N]
}

// delayKind struct to represent delayedKinds
type delayKindVDT struct {
	inner interface{}
}

func newDelayKind[N constraints.Unsigned, T delayKindTypes[N]](val T) delayKindVDT {
	return delayKindVDT{
		inner: val,
	}
}

// Finalized Depth in finalised chain.
type delayKindFinalized struct{}

func (delayKindFinalized) isDelayKind() {}

// Best depth in best chain. The median last finalised block is calculated at the time the
// HashNumber was signalled.
type delayKindBest[N constraints.Unsigned] struct {
	MedianLastFinalized N
}

func (delayKindBest[N]) isDelayKind() {}

// PendingChange is a pending HashNumber to the authority set.
//
// This will be applied when the announcing block is at some depth within the finalised or unfinalised chain.
type PendingChange[H comparable, N constraints.Unsigned] struct {
	// The new authorities and weights to apply.
	NextAuthorities pgrandpa.AuthorityList
	// How deep in the chain the announcing block must be before the HashNumber is applied.
	Delay N
	// The announcing block's height.
	CanonHeight N
	// The announcing block's hash.
	CanonHash H
	// The Delay kind.
	DelayKind delayKind
}

// EffectiveNumber Returns the effective number this HashNumber will be applied at.
func (pc *PendingChange[H, N]) EffectiveNumber() N {
	return pc.CanonHeight + pc.Delay
}

// AuthoritySetChanges Tracks historical authority set changes. We store the block numbers for the last block of each
// authority set, once they have been finalised. These blocks are guaranteed to have a justification unless they were
// triggered by a forced HashNumber.
type AuthoritySetChanges[N constraints.Unsigned] []setIDNumber[N]

// append an setIDNumber to AuthoritySetChanges
func (asc *AuthoritySetChanges[N]) append(setID uint64, blockNumber N) {
	*asc = append(*asc, setIDNumber[N]{
		SetID:       setID,
		BlockNumber: blockNumber,
	})
}

type authoritySetChangeID any

type authoritySetChangeIDs[N constraints.Unsigned] interface {
	authoritySetChangeIDLatest | authoritySetChangeIDSet[N] | authoritySetChangeIDUnknown
}

func newAuthoritySetID[N constraints.Unsigned, ID authoritySetChangeIDs[N]](authSetChangeID ID) authoritySetChangeID {
	return authoritySetChangeID(authSetChangeID)
}

type authoritySetChangeIDLatest struct{}

type authoritySetChangeIDSet[N constraints.Unsigned] struct {
	inner setIDNumber[N]
}

type authoritySetChangeIDUnknown struct{}

// Three states that can be returned: Latest, Set (tuple), Unknown
func (asc *AuthoritySetChanges[N]) getSetID(blockNumber N) (authoritySetChangeID, error) {
	if asc == nil {
		return nil, fmt.Errorf("getSetID: authSetChanges is nil")
	}
	authSet := *asc
	last := authSet[len(authSet)-1]
	if last.BlockNumber < blockNumber {
		return newAuthoritySetID[N](authoritySetChangeIDLatest{}), nil
	}

	idx, _ := slices.BinarySearchFunc(
		authSet,
		blockNumber,
		func(a setIDNumber[N], b N) int {
			switch {
			case a.BlockNumber == b:
				return 0
			case a.BlockNumber > b:
				return 1
			case a.BlockNumber < b:
				return -1
			default:
				panic("invalid return in binary search")
			}
		},
	)
	if idx < len(authSet) {
		authChange := authSet[idx]

		// if this is the first index but not the first set id then we are missing data.
		if idx == 0 && authChange.SetID != 0 {
			return newAuthoritySetID[N](authoritySetChangeIDUnknown{}), nil
		}

		return newAuthoritySetID[N](authoritySetChangeIDSet[N]{
			authChange,
		}), nil
	}

	return newAuthoritySetID[N](authoritySetChangeIDUnknown{}), nil
}

func (asc *AuthoritySetChanges[N]) insert(blockNumber N) {
	var idx int
	if asc == nil {
		panic("authority set changes must be initialised")
	} else {
		idx, _ = slices.BinarySearchFunc(
			*asc,
			blockNumber,
			func(a setIDNumber[N], b N) int {
				switch {
				case a.BlockNumber == b:
					return 0
				case a.BlockNumber > b:
					return 1
				case a.BlockNumber < b:
					return -1
				default:
					panic("invalid return in binary search")
				}
			},
		)
	}

	set := *asc

	var setID uint64
	if idx == 0 {
		setID = 0
	} else {
		setID = set[idx-1].SetID + 1
	}

	if idx != len(set) && set[idx].SetID == setID {
		panic("inserting authority set HashNumber")
	}

	change := setIDNumber[N]{
		SetID:       setID,
		BlockNumber: blockNumber,
	}

	// Insert HashNumber at index
	if len(set) <= idx {
		set = append(set, change)
	} else {
		set = append(set[:idx+1], set[idx:]...)
		set[idx] = change
	}
	*asc = set
}

// IterFrom This logic is used in warp sync proof
func (asc *AuthoritySetChanges[N]) IterFrom(blockNumber N) *AuthoritySetChanges[N] {
	if asc == nil {
		return nil
	}
	authSet := *asc

	idx, found := slices.BinarySearchFunc(
		*asc,
		blockNumber,
		func(a setIDNumber[N], b N) int {
			switch {
			case a.BlockNumber == b:
				return 0
			case a.BlockNumber > b:
				return 1
			case a.BlockNumber < b:
				return -1
			default:
				panic("invalid return in binary search")
			}
		},
	)
	if found {
		// if there was a HashNumber at the given block number then we should start on the next index since we want to
		// exclude the current block number
		idx += 1
	}

	if idx < len(*asc) {
		authChange := authSet[idx]

		// if this is the first index but not the first set id then we are missing data.
		if idx == 0 && authChange.SetID != 0 {
			return nil
		}
	}

	iterChanges := authSet[idx:]
	return &iterChanges
}
