collections

type Collection[T any] interface {
	// Size returns the number of elements.
	Size() int
	// IsEmpty reports whether the collection contains no elements.
	IsEmpty() bool
	// IsNotEmpty reports whether the collection contains at least one element.
	IsNotEmpty() bool
	// Clear removes all elements from the collection.
	Clear()
	// ToSlice returns a snapshot slice of all elements.
	// The order depends on the concrete implementation.
	ToSlice() []T
	// String returns a string representation of the collection.
	String() string
}

type Comparator[T any] func(a, b T) int

type ConcurrentMap[K, V any] interface {
	Map[K, V]

	// GetOrCompute atomically returns existing value or computes and stores a new one.
	// ATOMIC: This is a single atomic operation.
	// Returns (value, true) if computed (key was absent).
	GetOrCompute(key K, compute func() V) (V, bool)

	// RemoveAndGet atomically removes and returns the value for key.
	// ATOMIC: This is a single atomic operation.
	RemoveAndGet(key K) (V, bool)

	// CompareAndSwap replaces value if current equals old.
	// BEST-EFFORT: Atomic in ConcurrentHashMap; may race in ConcurrentSkipMap.
	CompareAndSwap(key K, old, new V, eq Equaler[V]) bool

	// CompareAndDelete deletes entry if current value equals provided.
	// BEST-EFFORT: Atomic in ConcurrentHashMap; may race in ConcurrentSkipMap.
	CompareAndDelete(key K, value V, eq Equaler[V]) bool
}

type ConcurrentSet[T any] interface {
	Set[T]

	// AddIfAbsent atomically inserts element only if currently absent.
	// ATOMIC: This is a single atomic operation.
	// Returns true if the element was added.
	AddIfAbsent(element T) bool

	// RemoveAndGet atomically removes and returns the element if present.
	// ATOMIC: This is a single atomic operation.
	RemoveAndGet(element T) (T, bool)
}

type ConcurrentSortedMap[K, V any] interface {
	SortedMap[K, V]
	ConcurrentMap[K, V]
}

type ConcurrentSortedSet[T any] interface {
	SortedSet[T]
	ConcurrentSet[T]
}

type Deque[T any] interface {
	// Size returns the number of elements.
	Size() int
	// IsEmpty reports whether the deque is empty.
	IsEmpty() bool
	// IsNotEmpty reports whether the deque contains at least one element.
	IsNotEmpty() bool
	// Clear removes all elements.
	Clear()
	// String returns a string representation.
	String() string

	// --- Front Operations ---
	// PushFront adds an element to the front.
	PushFront(element T)
	// PopFront removes and returns the front element, or (zero, false) if empty.
	PopFront() (T, bool)
	// PeekFront returns the front element without removing it, or (zero, false) if empty.
	PeekFront() (T, bool)

	// --- Back Operations ---
	// PushBack adds an element to the back.
	PushBack(element T)
	// PopBack removes and returns the back element, or (zero, false) if empty.
	PopBack() (T, bool)
	// PeekBack returns the back element without removing it, or (zero, false) if empty.
	PeekBack() (T, bool)

	// ToSlice returns elements from front to back.
	ToSlice() []T
	// Seq returns a sequence from front to back.
	Seq() iter.Seq[T]
	// Reversed returns a sequence from back to front.
	Reversed() iter.Seq[T]
}

type Entry[K, V any] struct {
	Key   K
	Value V
}

type Equaler[T any] func(a, b T) bool

type GoMapView[K comparable, V any] interface {
	// ToGoMap returns a standard Go map[K]V snapshot.
	ToGoMap() map[K]V
}

type Iterable[T any] interface {
	// Seq returns a sequence for use with for-range:
	//   for v := range c.Seq() { ... }
	Seq() iter.Seq[T]
	// ForEach applies action to each element.
	// Iteration stops early if action returns false.
	ForEach(action func(element T) bool)
}

type List[T any] interface {
	Collection[T]
	Iterable[T]

	// --- Positional Access ---
	// Get returns the element at index, or (zero, false) if out of bounds.
	Get(index int) (T, bool)
	// Set replaces the element at index. Returns (oldValue, true) if successful.
	Set(index int, element T) (T, bool)
	// First returns the first element, or (zero, false) if empty.
	First() (T, bool)
	// Last returns the last element, or (zero, false) if empty.
	Last() (T, bool)

	// --- Modification ---
	// Add appends the element to the end.
	Add(element T)
	// AddAll appends all elements to the end.
	AddAll(elements ...T)
	// AddSeq appends all elements from the sequence.
	AddSeq(seq iter.Seq[T])
	// Insert inserts the element at index, shifting subsequent elements right.
	// Returns false if index is out of bounds.
	Insert(index int, element T) bool
	// InsertAll inserts all elements at index, shifting subsequent elements right.
	InsertAll(index int, elements ...T) bool
	// RemoveAt removes the element at index. Returns (removed, true) if successful.
	RemoveAt(index int) (T, bool)
	// Remove removes the first occurrence of element. Returns true if removed.
	Remove(element T, eq Equaler[T]) bool
	// RemoveFirst removes and returns the first element.
	RemoveFirst() (T, bool)
	// RemoveLast removes and returns the last element.
	RemoveLast() (T, bool)
	// RemoveFunc removes all elements satisfying predicate. Returns count removed.
	RemoveFunc(predicate func(element T) bool) int
	// RetainFunc keeps only elements satisfying predicate. Returns count removed.
	RetainFunc(predicate func(element T) bool) int

	// --- Search ---
	// IndexOf returns the index of the first occurrence, or -1.
	IndexOf(element T, eq Equaler[T]) int
	// LastIndexOf returns the index of the last occurrence, or -1.
	LastIndexOf(element T, eq Equaler[T]) int
	// Contains reports whether element exists using eq for comparison.
	Contains(element T, eq Equaler[T]) bool
	// Find returns the first element satisfying predicate, or (zero, false).
	Find(predicate func(element T) bool) (T, bool)
	// FindIndex returns the index of the first element satisfying predicate, or -1.
	FindIndex(predicate func(element T) bool) int

	// --- Views ---
	// SubList returns a new list containing elements in [from, to).
	SubList(from, to int) List[T]
	// Reversed returns a sequence iterating in reverse order.
	Reversed() iter.Seq[T]

	// --- Transformations ---
	// Clone returns a shallow copy.
	Clone() List[T]
	// Filter returns a new list of elements satisfying predicate.
	Filter(predicate func(element T) bool) List[T]
	// Sort sorts elements in place using the comparator.
	Sort(cmp Comparator[T])

	// --- Aggregation ---
	// Any returns true if at least one element satisfies predicate.
	Any(predicate func(element T) bool) bool
	// Every returns true if all elements satisfy predicate.
	Every(predicate func(element T) bool) bool
}

type Map[K, V any] interface {
	// --- Basic Info ---
	// Size returns the number of entries.
	Size() int
	// IsEmpty reports whether the map has no entries.
	IsEmpty() bool
	// IsNotEmpty reports whether the map contains at least one entry.
	IsNotEmpty() bool
	// Clear removes all entries.
	Clear()
	// String returns a string representation.
	String() string

	// --- Basic Operations ---
	// Put associates value with key. Returns (oldValue, true) if key existed.
	Put(key K, value V) (V, bool)
	// PutIfAbsent stores value only if key is absent. Returns (existingOrNew, inserted).
	PutIfAbsent(key K, value V) (V, bool)
	// PutAll copies all entries from other into this map.
	PutAll(other Map[K, V])
	// PutSeq copies entries from a sequence. Returns number of keys changed.
	PutSeq(seq iter.Seq2[K, V]) int
	// Get returns (value, true) if key present; otherwise (zero, false).
	Get(key K) (V, bool)
	// GetOrDefault returns value for key or defaultValue if absent.
	GetOrDefault(key K, defaultValue V) V
	// Remove deletes key. Returns (oldValue, true) if key existed.
	Remove(key K) (V, bool)
	// RemoveIf deletes only if (key, value) matches. Returns true if removed.
	RemoveIf(key K, value V, eq Equaler[V]) bool

	// --- Query ---
	// ContainsKey reports whether key exists.
	ContainsKey(key K) bool
	// ContainsValue reports whether value exists (O(n)).
	ContainsValue(value V, eq Equaler[V]) bool

	// --- Bulk Operations ---
	// RemoveAll removes all specified keys. Returns count removed.
	RemoveAll(keys ...K) int
	// RemoveSeq removes keys from the sequence. Returns count removed.
	RemoveSeq(seq iter.Seq[K]) int
	// RemoveFunc removes entries where predicate returns true. Returns count removed.
	RemoveFunc(predicate func(key K, value V) bool) int

	// --- Compute Operations ---
	// Compute recomputes mapping for key.
	// If keep==false, the key is removed.
	Compute(key K, remapping func(key K, oldValue V, exists bool) (newValue V, keep bool)) (V, bool)
	// ComputeIfAbsent computes and stores value if key is absent.
	ComputeIfAbsent(key K, mapping func(key K) V) V
	// ComputeIfPresent recomputes value if key is present. If keep==false, removes key.
	ComputeIfPresent(key K, remapping func(key K, oldValue V) (newValue V, keep bool)) (V, bool)
	// Merge merges value with existing. If keep==false, removes key.
	Merge(key K, value V, remapping func(oldValue, newValue V) (mergedValue V, keep bool)) (V, bool)

	// --- Replace Operations ---
	// Replace sets value only if key is present. Returns (oldValue, true) if replaced.
	Replace(key K, value V) (V, bool)
	// ReplaceIf replaces only if current value equals oldValue. Returns true if replaced.
	ReplaceIf(key K, oldValue, newValue V, eq Equaler[V]) bool
	// ReplaceAll replaces each value with function(key, value).
	ReplaceAll(function func(key K, value V) V)

	// --- Views ---
	// Keys returns all keys as a slice.
	Keys() []K
	// Values returns all values as a slice.
	Values() []V
	// Entries returns all entries as a slice.
	Entries() []Entry[K, V]

	// --- Iteration ---
	// ForEach iterates over entries. Stops early if action returns false.
	ForEach(action func(key K, value V) bool)
	// Seq returns a sequence of (key, value) pairs.
	Seq() iter.Seq2[K, V]
	// SeqKeys returns a sequence of keys.
	SeqKeys() iter.Seq[K]
	// SeqValues returns a sequence of values.
	SeqValues() iter.Seq[V]

	// --- Transformations ---
	// Clone returns a shallow copy.
	Clone() Map[K, V]
	// Filter returns a new map with entries satisfying predicate.
	Filter(predicate func(key K, value V) bool) Map[K, V]

	// --- Comparison ---
	// Equals reports whether both maps contain the same entries.
	Equals(other Map[K, V], valueEq Equaler[V]) bool
}

type Ordered = cmp.Ordered

type PriorityQueue[T any] interface {
	// Size returns the number of elements.
	Size() int
	// IsEmpty reports whether the queue is empty.
	IsEmpty() bool
	// IsNotEmpty reports whether the queue contains at least one element.
	IsNotEmpty() bool
	// Clear removes all elements.
	Clear()
	// String returns a string representation.
	String() string

	// Push adds an element to the queue. O(log n).
	Push(element T)
	// PushAll adds all elements to the queue.
	PushAll(elements ...T)
	// Pop removes and returns the highest-priority element, or (zero, false) if empty. O(log n).
	Pop() (T, bool)
	// Peek returns the highest-priority element without removing it, or (zero, false) if empty. O(1).
	Peek() (T, bool)

	// ToSlice returns elements in heap order (not sorted).
	ToSlice() []T
	// ToSortedSlice returns elements in priority order (sorted).
	ToSortedSlice() []T
	// Seq returns a sequence in heap order (not sorted).
	Seq() iter.Seq[T]
}

type Queue[T any] interface {
	// Size returns the number of elements.
	Size() int
	// IsEmpty reports whether the queue is empty.
	IsEmpty() bool
	// IsNotEmpty reports whether the queue contains at least one element.
	IsNotEmpty() bool
	// Clear removes all elements.
	Clear()
	// String returns a string representation.
	String() string

	// Enqueue adds an element to the back of the queue.
	Enqueue(element T)
	// EnqueueAll adds all elements to the back.
	EnqueueAll(elements ...T)
	// Dequeue removes and returns the front element, or (zero, false) if empty.
	Dequeue() (T, bool)
	// Peek returns the front element without removing it, or (zero, false) if empty.
	Peek() (T, bool)

	// ToSlice returns elements from front to back.
	ToSlice() []T
	// Seq returns a sequence from front to back (FIFO order).
	Seq() iter.Seq[T]
}

type Set[T any] interface {
	Collection[T]
	Iterable[T]

	// --- Modification ---
	// Add inserts the element if absent. Returns true if the set changed.
	Add(element T) bool
	// AddAll inserts all given elements. Returns the number of elements added.
	AddAll(elements ...T) int
	// AddSeq inserts all elements from the sequence. Returns the number added.
	AddSeq(seq iter.Seq[T]) int
	// Remove deletes the element if present. Returns true if removed.
	Remove(element T) bool
	// RemoveAll deletes all given elements. Returns the number removed.
	RemoveAll(elements ...T) int
	// RemoveSeq removes all elements from the sequence. Returns the number removed.
	RemoveSeq(seq iter.Seq[T]) int
	// RemoveFunc removes elements satisfying predicate. Returns count removed.
	RemoveFunc(predicate func(element T) bool) int
	// RetainFunc keeps only elements satisfying predicate. Returns count removed.
	RetainFunc(predicate func(element T) bool) int
	// Pop removes and returns an arbitrary element. Returns (zero, false) if empty.
	Pop() (T, bool)

	// --- Query ---
	// Contains reports whether element exists in the set.
	Contains(element T) bool
	// ContainsAll reports whether all elements exist in the set.
	ContainsAll(elements ...T) bool
	// ContainsAny reports whether any of the elements exist in the set.
	ContainsAny(elements ...T) bool

	// --- Set Algebra ---
	// Union returns a new set: s ∪ other.
	Union(other Set[T]) Set[T]
	// Intersection returns a new set: s ∩ other.
	Intersection(other Set[T]) Set[T]
	// Difference returns a new set: s - other.
	Difference(other Set[T]) Set[T]
	// SymmetricDifference returns a new set: (s - other) ∪ (other - s).
	SymmetricDifference(other Set[T]) Set[T]

	// --- Relations ---
	// IsSubsetOf reports whether all elements of s are in other.
	IsSubsetOf(other Set[T]) bool
	// IsSupersetOf reports whether s contains all elements of other.
	IsSupersetOf(other Set[T]) bool
	// IsProperSubsetOf reports whether s ⊂ other (subset but not equal).
	IsProperSubsetOf(other Set[T]) bool
	// IsProperSupersetOf reports whether s ⊃ other (superset but not equal).
	IsProperSupersetOf(other Set[T]) bool
	// IsDisjoint reports whether s and other have no elements in common.
	IsDisjoint(other Set[T]) bool
	// Equals reports whether s and other contain exactly the same elements.
	Equals(other Set[T]) bool

	// --- Transformations ---
	// Clone returns a shallow copy.
	Clone() Set[T]
	// Filter returns a new set of elements that satisfy predicate.
	Filter(predicate func(element T) bool) Set[T]

	// --- Search ---
	// Find returns the first element satisfying predicate, or (zero, false).
	Find(predicate func(element T) bool) (T, bool)
	// Any returns true if at least one element satisfies predicate.
	Any(predicate func(element T) bool) bool
	// Every returns true if all elements satisfy predicate (true for empty set).
	Every(predicate func(element T) bool) bool
}

type SortedMap[K, V any] interface {
	Map[K, V]

	// --- Extremes ---
	// FirstKey returns the smallest key, or (zero, false) if empty.
	FirstKey() (K, bool)
	// LastKey returns the largest key, or (zero, false) if empty.
	LastKey() (K, bool)
	// FirstEntry returns the entry with the smallest key.
	FirstEntry() (Entry[K, V], bool)
	// LastEntry returns the entry with the largest key.
	LastEntry() (Entry[K, V], bool)
	// PopFirst removes and returns the smallest-key entry.
	PopFirst() (Entry[K, V], bool)
	// PopLast removes and returns the largest-key entry.
	PopLast() (Entry[K, V], bool)

	// --- Navigation ---
	// FloorKey returns the greatest key <= k, or (zero, false).
	FloorKey(k K) (K, bool)
	// CeilingKey returns the smallest key >= k, or (zero, false).
	CeilingKey(k K) (K, bool)
	// LowerKey returns the greatest key < k, or (zero, false).
	LowerKey(k K) (K, bool)
	// HigherKey returns the smallest key > k, or (zero, false).
	HigherKey(k K) (K, bool)
	// FloorEntry returns entry with greatest key <= k.
	FloorEntry(k K) (Entry[K, V], bool)
	// CeilingEntry returns entry with smallest key >= k.
	CeilingEntry(k K) (Entry[K, V], bool)
	// LowerEntry returns entry with greatest key < k.
	LowerEntry(k K) (Entry[K, V], bool)
	// HigherEntry returns entry with smallest key > k.
	HigherEntry(k K) (Entry[K, V], bool)

	// --- Range Iteration ---
	// Range iterates entries with keys in [from, to] ascending.
	// If from > to, no elements are visited.
	Range(from, to K, action func(key K, value V) bool)
	// RangeSeq returns a sequence for entries with keys in [from, to] ascending.
	// If from > to, returns an empty sequence.
	RangeSeq(from, to K) iter.Seq2[K, V]
	// RangeFrom iterates entries with keys >= from.
	RangeFrom(from K, action func(key K, value V) bool)
	// RangeTo iterates entries with keys <= to.
	RangeTo(to K, action func(key K, value V) bool)

	// --- Ordered Iteration ---
	// Ascend iterates all entries in ascending key order.
	Ascend(action func(key K, value V) bool)
	// Descend iterates all entries in descending key order.
	Descend(action func(key K, value V) bool)
	// AscendFrom iterates entries with keys >= pivot ascending.
	AscendFrom(pivot K, action func(key K, value V) bool)
	// DescendFrom iterates entries with keys <= pivot descending.
	DescendFrom(pivot K, action func(key K, value V) bool)
	// Reversed returns a sequence iterating in descending key order.
	Reversed() iter.Seq2[K, V]

	// --- Views ---
	// SubMap returns entries with keys in [from, to].
	SubMap(from, to K) SortedMap[K, V]
	// HeadMap returns entries with keys < to (or <= if inclusive).
	HeadMap(to K, inclusive bool) SortedMap[K, V]
	// TailMap returns entries with keys > from (or >= if inclusive).
	TailMap(from K, inclusive bool) SortedMap[K, V]

	// --- Rank Operations ---
	// RankOfKey returns the 0-based rank of key, or -1 if not present.
	RankOfKey(key K) int
	// GetByRank returns the entry at rank, or (Entry{}, false).
	GetByRank(rank int) (Entry[K, V], bool)

	// --- Sorted Clone ---
	// CloneSorted returns a shallow copy as SortedMap.
	CloneSorted() SortedMap[K, V]
}

type SortedSet[T any] interface {
	Set[T]

	// --- Extremes ---
	// First returns the smallest element, or (zero, false) if empty.
	First() (T, bool)
	// Last returns the largest element, or (zero, false) if empty.
	Last() (T, bool)
	// Min is an alias of First for compatibility with other libraries.
	Min() (T, bool)
	// Max is an alias of Last for compatibility with other libraries.
	Max() (T, bool)
	// PopFirst removes and returns the smallest element.
	PopFirst() (T, bool)
	// PopLast removes and returns the largest element.
	PopLast() (T, bool)

	// --- Navigation ---
	// Floor returns the greatest element <= x, or (zero, false).
	Floor(x T) (T, bool)
	// Ceiling returns the smallest element >= x, or (zero, false).
	Ceiling(x T) (T, bool)
	// Lower returns the greatest element < x, or (zero, false).
	Lower(x T) (T, bool)
	// Higher returns the smallest element > x, or (zero, false).
	Higher(x T) (T, bool)

	// --- Range Iteration ---
	// Range iterates elements in [from, to] ascending.
	// If from > to, no elements are visited.
	Range(from, to T, action func(element T) bool)
	// RangeSeq returns a sequence for elements in [from, to] ascending.
	// If from > to, returns an empty sequence.
	RangeSeq(from, to T) iter.Seq[T]

	// --- Ordered Iteration ---
	// Ascend iterates all elements in ascending order.
	Ascend(action func(element T) bool)
	// Descend iterates all elements in descending order.
	Descend(action func(element T) bool)
	// AscendFrom iterates elements >= pivot in ascending order.
	AscendFrom(pivot T, action func(element T) bool)
	// DescendFrom iterates elements <= pivot in descending order.
	DescendFrom(pivot T, action func(element T) bool)
	// Reversed returns a descending sequence for for-range.
	Reversed() iter.Seq[T]

	// --- Views ---
	// SubSet returns a new set containing elements in [from, to].
	SubSet(from, to T) SortedSet[T]
	// HeadSet returns elements < to (or <= if inclusive).
	HeadSet(to T, inclusive bool) SortedSet[T]
	// TailSet returns elements > from (or >= if inclusive).
	TailSet(from T, inclusive bool) SortedSet[T]

	// --- Rank Operations ---
	// Rank returns the 0-based rank of x, or -1 if not present.
	Rank(x T) int
	// GetByRank returns the element at 0-based rank, or (zero, false).
	GetByRank(rank int) (T, bool)

	// --- Sorted Clone ---
	// CloneSorted returns a shallow copy as SortedSet.
	CloneSorted() SortedSet[T]
}

type Stack[T any] interface {
	// Size returns the number of elements.
	Size() int
	// IsEmpty reports whether the stack is empty.
	IsEmpty() bool
	// IsNotEmpty reports whether the stack contains at least one element.
	IsNotEmpty() bool
	// Clear removes all elements.
	Clear()
	// String returns a string representation.
	String() string

	// Push adds an element to the top of the stack.
	Push(element T)
	// PushAll adds all elements to the top (last element becomes top).
	PushAll(elements ...T)
	// Pop removes and returns the top element, or (zero, false) if empty.
	Pop() (T, bool)
	// Peek returns the top element without removing it, or (zero, false) if empty.
	Peek() (T, bool)

	// ToSlice returns elements from bottom to top.
	ToSlice() []T
	// Seq returns a sequence from top to bottom (LIFO order).
	Seq() iter.Seq[T]
}