// Copyright 2026 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package types2

import "sort"

// A trie[V] maps keys to values V, similar to a map.
// A key is a list of integers; two keys collide if one of them is a prefix of the other.
// For instance, [1, 2] and [1, 2, 3] collide, but [1, 2, 3] and [1, 2, 4] do not.
// If all keys have length 1, a trie degenerates into an ordinary map[int]V.
type trie[V any] map[int]any // map value is either trie[V] (non-leaf node), or V (leaf node)

// insert inserts a value with a key into the trie; key must not be empty.
// If key doesn't collide with any other key in the trie, insert succeeds
// and returns (val, 0). Otherwise, insert fails and returns (alt, n) where
// alt is an unspecified but deterministically chosen value with a colliding
// key and n is the length > 0 of the common key prefix. The trie is not
// changed in this case.
func (tr trie[V]) insert(key []int, val V) (V, int) {
	// A key serves as the path from the trie root to its corresponding value.
	for l, index := range key {
		if v, exists := tr[index]; exists {
			// An entry already exists for this index; check its type to determine collision.
			switch v := v.(type) {
			case trie[V]:
				// Path continues.
				// Must check this case first in case V is any which would act as catch-all.
				tr = v
			case V:
				// Collision: An existing key ends here.
				// This means the existing key is a prefix of (or exactly equal to) key.
				return v, l + 1
			case nil:
				// Handle esoteric case where V is any and val is nil.
				var zero V
				return zero, l + 1
			default:
				panic("trie.insert: invalid entry")
			}
		} else {
			// Path doesn't exist yet, we need to build it.
			if l == len(key)-1 {
				// No prefix collision detected; insert val as a new leaf node.
				tr[index] = val
				return val, 0
			}
			node := make(trie[V])
			tr[index] = node
