container

type BiMap[K comparable, V comparable] interface {
	Map[K, V]

	// GetKey retrieves the key associated with the specified value.
	// Returns the key and true if the value was found, or the zero value of K
	// and false if the value was not present.
	GetKey(val V) (key K, found bool)

	// HasValue returns true if the map contains the value.
	HasValue(val V) bool

	// DeleteValue removes the key-value pair associated with the specified value.
	// Returns the key and true if the value was found and removed, false if the value was not present.
	DeleteValue(val V) (key K, found bool)
}

type Container[T any] interface {
	// Clear removes all elements from the container, resetting it to an empty state.
	Clear()

	// IsEmpty returns true if the container has no elements.
	IsEmpty() bool

	// Len returns the number of elements in the container.
	Len() int

	// String returns a string representation of the container's elements,
	// suitable for logging or debugging.
	String() string

	// ToSlice returns a slice containing all elements in the container.
	// The order of elements is implementation-dependent.
	ToSlice() []T
}

type Deque[T comparable] interface {
	Container[T]

	// PushFront adds an element to the front of the deque.
	PushFront(val T)

	// PushBack adds an element to the back of the deque.
	PushBack(val T)

	// PopFront removes and returns the front element of the deque.
	// Returns the element and true if the deque is non-empty,
	// or the zero value of T and false if the deque is empty.
	PopFront() (val T, ok bool)

	// PopBack removes and returns the back element of the deque.
	// Returns the element and true if the deque is non-empty,
	// or the zero value of T and false if the deque is empty.
	PopBack() (val T, ok bool)

	// Front returns the front element of the deque without removing it.
	// Returns the element and true if the deque is non-empty,
	// or the zero value of T and false if the deque is empty.
	Front() (val T, ok bool)

	// Back returns the back element of the deque without removing it.
	// Returns the element and true if the deque is non-empty,
	// or the zero value of T and false if the deque is empty.
	Back() (val T, ok bool)

	// Capacity returns the maximum number of elements the deque can hold,
	// or -1 if the capacity is unbounded (e.g., for linked-list implementations).
	Capacity() int

	// Get returns the element at the specified index, where 0 is the front.
	// Returns the element and true if the index is valid,
	// or the zero value of T and false if the index is out of bounds.
	Get(idx int) (val T, ok bool)

	// Set updates the element at the specified index, where 0 is the front.
	// Panics if the index is out of bounds.
	Set(idx int, val T)

	// Insert adds an element at the specified index, shifting subsequent elements.
	// Index 0 inserts at the front, and Len() inserts at the back.
	// Panics if the index is out of bounds (i.e., idx < 0 or idx > Len()).
	Insert(idx int, val T)

	// Remove removes the element at the specified index, shifting subsequent elements.
	// Panics if the index is out of bounds.
	Remove(idx int) (val T, ok bool)

	// Swap exchanges the elements at the specified indices.
	// Panics if either index is out of bounds.
	Swap(idx1, idx2 int)
}

type Map[K comparable, V any] interface {
	Container[V]

	// Put associates the specified value with the given key in the map.
	// If the key already exists, its value is updated with the new value.
	// If the key does not exist, a new key-value pair is added.
	Put(key K, val V)

	// Get retrieves the value associated with the specified key.
	// Returns the value and true if the key was found, or the zero value of V
	// and false if the key was not present.
	Get(key K) (val V, found bool)

	// Has returns true if the specified key is present in the map, false otherwise.
	Has(key K) bool

	// Delete removes the key-value pair associated with the specified key.
	// Returns the key, value, and true if the key was found and removed, false if the key was not present.
	Delete(key K) (val V, found bool)

	// Keys returns a slice containing all keys in the map.
	// The order of keys matches the map's ordering (e.g., sorted for tree maps).
	// Returns an empty slice if the map is empty.
	Keys() []K

	// Values returns a slice containing all values in the map.
	// The order of values corresponds to the order of keys in the map's ordering.
	// Returns an empty slice if the map is empty.
	Values() []V

	// Entries returns two slices containing all keys and values in the map,
	// respectively, in the map's ordering (e.g., sorted for tree maps).
	// The returned slices are of equal length, where the i-th element of the keys
	// slice corresponds to the i-th element of the values slice.
	// Returns empty slices if the map is empty.
	//
	// Example:
	//   keys, values := m.Entries()
	//   for i := 0; i < len(keys); i++ {
	//       fmt.Printf("Key: %v, Value: %v\n", keys[i], values[i])
	//   }
	Entries() (keys []K, vals []V)

	// Clone returns a clone of the map using the same implementation,
	// duplicating all keys and values.
	Clone() Map[K, V]
}

type OrderedBiMap[K comparable, V comparable] interface {
	OrderedMap[K, V]

	// GetKey retrieves the key associated with the specified value.
	// Returns the key and true if the value was found, or the zero value of K
	// and false if the value was not present.
	GetKey(val V) (key K, found bool)

	// HasValue returns true if the map contains the value.
	HasValue(val V) bool

	// DeleteValue removes the key-value pair associated with the specified value.
	// Returns the key and true if the value was found and removed, false if the value was not present.
	DeleteValue(val V) (key K, found bool)
}

type OrderedMap[K comparable, V any] interface {
	Map[K, V]

	// Begin returns the first key-value pair in the map's ordering.
	// For ordered implementations (e.g., tree maps), this is the smallest key
	// according to the map's comparison function.
	// Returns the key, value, and true if the map is non-empty, or zero values
	// and false if the map is empty.
	Begin() (key K, val V, ok bool)

	// End returns the last key-value pair in the map's ordering.
	// For ordered implementations, this is the largest key according to the
	// map's comparison function.
	// Returns the key, value, and true if the map is non-empty, or zero values
	// and false if the map is empty.
	End() (key K, val V, ok bool)

	// DeleteBegin removes and returns the first key-value pair in the map's ordering.
	// For ordered implementations, this removes the smallest key.
	// Returns the key, value, and true if the map was non-empty, or zero values
	// and false if the map was empty.
	DeleteBegin() (key K, val V, ok bool)

	// DeleteEnd removes and returns the last key-value pair in the map's ordering.
	// For ordered implementations, this removes the largest key.
	// Returns the key, value, and true if the map was non-empty, or zero values
	// and false if the map was empty.
	DeleteEnd() (key K, val V, ok bool)

	// Iter returns an iterator over the key-value pairs in the map.
	// The iterator yields pairs in the map's ordering (e.g., sorted for tree maps).
	// Suitable for range loops.
	//
	// Example:
	//   for key, value := range m.Iter() {
	//       fmt.Printf("Key: %v, Value: %v\n", key, value)
	//   }
	//
	// The iterator is safe for concurrent reads but not for concurrent writes
	// unless the implementation explicitly supports it.
	Iter() iter.Seq2[K, V]

	// RIter returns an iterator over the key-value pairs in the map.
	// The iterator yields pairs in the map's reverse ordering.
	// Suitable for range loops.
	//
	// Example:
	//   for key, value := range m.RIter() {
	//       fmt.Printf("Key: %v, Value: %v\n", key, value)
	//   }
	//
	// The iterator is safe for concurrent reads but not for concurrent writes
	// unless the implementation explicitly supports it.
	RIter() iter.Seq2[K, V]
}

type PQueue[T comparable, V cmp.Ordered] interface {
	Container[T]

	// Enqueue adds an element to the queue.
	Enqueue(val T, priority V)

	// Dequeue removes and returns the front element of the queue.
	// Returns the element and true if the queue is non-empty,
	// or the zero value of T and false if the queue is empty.
	Dequeue() (val T, priority V, ok bool)

	// Peek returns the front element of the queue without removing it.
	// Returns the element and true if the queue is non-empty,
	// or the zero value of T and false if the queue is empty.
	Peek() (val T, priority V, ok bool)
}

type Queue[T comparable] interface {
	Container[T]

	// Enqueue adds an element to the back of the queue.
	Enqueue(val T)

	// Dequeue removes and returns the front element of the queue.
	// Returns the element and true if the queue is non-empty,
	// or the zero value of T and false if the queue is empty.
	Dequeue() (val T, ok bool)

	// Peek returns the front element of the queue without removing it.
	// Returns the element and true if the queue is non-empty,
	// or the zero value of T and false if the queue is empty.
	Peek() (val T, ok bool)
}

type Set[T comparable] interface {
	Container[T]

	// Clone returns a clone of the set using the same
	// implementation, duplicating all keys.
	Clone() Set[T]

	// Add adds an element to the set. Returns whether
	// the item was added.
	Add(val T) bool

	// Append multiple elements to the set. Returns
	// the number of elements added.
	Append(val ...T) int

	// Remove removes a single element from the set.
	Remove(i T)

	// RemoveAll removes multiple elements from the set.
	RemoveAll(i ...T)

	// Pop removes and returns an arbitrary item from the set.
	Pop() (val T, ok bool)

	// ContainsOne returns whether the given item
	// is in the set.
	//
	// Contains may cause the argument to escape to the heap.
	// See: https://github.com/deckarep/golang-set/issues/118
	ContainsOne(val T) bool

	// Contains returns whether the given items
	// are all in the set.
	Contains(val ...T) bool

	// ContainsAny returns whether at least one of the
	// given items are in the set.
	ContainsAny(val ...T) bool

	// ContainsAnyElement returns whether at least one of the
	// given element are in the set.
	ContainsAnyElement(other Set[T]) bool

	// Equal determines if two sets are equal to each
	// other. If they have the same cardinality
	// and contain the same elements, they are
	// considered equal. The order in which
	// the elements were added is irrelevant.
	//
	// Note that the argument to Equal must be
	// of the same type as the receiver of the
	// method. Otherwise, Equal will panic.
	Equal(other Set[T]) bool

	// IsSubset determines if every element in this set is in
	// the other set.
	//
	// Note that the argument to IsSubset
	// must be of the same type as the receiver
	// of the method. Otherwise, IsSubset will panic.
	IsSubset(other Set[T]) bool

	// IsProperSubset determines if every element in this set is in
	// the other set but the two sets are not equal.
	//
	// Note that the argument to IsProperSubset
	// must be of the same type as the receiver
	// of the method. Otherwise, IsProperSubset will panic.
	IsProperSubset(other Set[T]) bool

	// IsSuperset determines if every element in the other set
	// is in this set.
	//
	// Note that the argument to IsSuperset
	// must be of the same type as the receiver
	// of the method. Otherwise, IsSuperset will panic.
	IsSuperset(other Set[T]) bool

	// IsProperSuperset determines if every element in the other set
	// is in this set but the two sets are not
	// equal.
	//
	// Note that the argument to IsSuperset
	// must be of the same type as the receiver
	// of the method. Otherwise, IsSuperset will
	// panic.
	IsProperSuperset(other Set[T]) bool

	// Union returns a new set with all elements in both sets.
	//
	// Note that the argument to Union must be of the
	// same type as the receiver of the method.
	// Otherwise, Union will panic.
	Union(other Set[T]) Set[T]

	// Intersect returns a new set containing only the elements
	// that exist only in both sets.
	//
	// Note that the argument to Intersect
	// must be of the same type as the receiver
	// of the method. Otherwise, Intersect will
	// panic.
	Intersect(other Set[T]) Set[T]

	// Difference returns the difference between this set
	// and other. The returned set will contain
	// all elements of this set that are not also
	// elements of other.
	//
	// Note that the argument to Difference
	// must be of the same type as the receiver
	// of the method. Otherwise, Difference will
	// panic.
	Difference(other Set[T]) Set[T]

	// SymmetricDifference returns a new set with all elements which are
	// in either this set or the other set but not in both.
	//
	// Note that the argument to SymmetricDifference
	// must be of the same type as the receiver
	// of the method. Otherwise, SymmetricDifference will
	// panic.
	SymmetricDifference(other Set[T]) Set[T]

	// Iter returns a channel of elements that you can
	// range over.
	Iter() iter.Seq[T]
}

type Stack[T comparable] interface {
	Container[T]

	// Push adds an element to the top of the stack.
	Push(val T)

	// Pop removes and returns the top element of the stack.
	// Returns the element and true if the stack is non-empty,
	// or the zero value of T and false if the stack is empty.
	Pop() (val T, ok bool)

	// Peek returns the top element of the stack without removing it.
	// Returns the element and true if the stack is non-empty,
	// or the zero value of T and false if the stack is empty.
	Peek() (val T, ok bool)
}