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

// This file defines a [Set] based on [Map].

import (
	
	
	
	
	
	

	
	
)

// Set[E] is a hash-table based set of elements of type E,
// using the hash function and key-equivalence relation specified
// at construction.
//
// A Set must be created with [NewSet].
// Neither a nil pointer nor the zero value are valid sets.
//
// Set values must not be copied; use [Set.Clone] instead.
//
// Do not use Set with a comparable element type E and its usual ==
// equivalence relation; instead, use Go's built-in map type.
// (If you need set operations such as Union and Intersection,
// use the helpers in the [golang.org/x/exp/collection/set] package.)
//
// Set should not be used with elements that are (or contain)
// floating-point numbers whose value may be NaN, as it may take
// shortcuts based on algebraic identities that assume e == e for any
// element e. For example, Intersects(s, s) returns true for any
// non-empty set, without inspecting the elements.
//
// For all binary operations on sets, like the set algebra methods
// [Set.Union], [Set.Intersection] and so on, the two sets must
// use the same key-equivalence relation.
type Set[ any] struct {
	m Map[, unit]
}

type unit = struct{}

// NewSet returns a new empty set that uses the specified hash
// function and key-equivalence relation.
func [ any]( maphash.Hasher[]) *Set[] {
	var  Set[]
	.m.init()
	return &
}

// Len returns the number of set elements.
func ( *Set[]) () int {
	return .m.Len()
}

// All returns an iterator over the elements of the set in unspecified order.
//
// It is safe to modify the set during iteration. As with the built-in
// set, if an element is removed during iteration, it will not be
// yielded by the iterator. If an element is added during iteration,
// it may or may not be yielded by the iterator.
func ( *Set[]) () iter.Seq[] {
	return .m.Keys()
}

// insertAll calls Insert for each element in the sequence.
// It reports whether the size changed.
func ( *Set[]) ( iter.Seq[]) bool {
	 := .m.len
	for  := range  {
		.m.Set(, unit{})
	}
	return .m.len > 
}

// DeleteFunc deletes each element e in the set for which del returns true.
// It reports whether the set changed.
func ( *Set[]) ( func() bool) bool {
	 := .m.len
	for  := range .All() {
		if () {
			.m.Delete()
		}
	}
	return .m.len < 
}

// Clone returns a new set with the same elements as s.
func ( *Set[]) () *Set[] {
	var  Set[]
	.m.cloneFrom(&.m)
	return &
}

// Delete removes the given element, if present.
// It reports whether the element was present.
func ( *Set[]) ( ) bool {
	,  := .m.Delete()
	return 
}

// Contains reports whether the set contains the specified element.
func ( *Set[]) ( ) bool {
	return .m.Contains()
}

// Insert adds the specified element to the set
// (if no equal element is present),
// and reports whether the set grew.
func ( *Set[]) ( ) bool {
	 := .Len()
	.m.Set(, unit{})
	return .Len() > 
}

// Clear removes all entries from the set.
func ( *Set[]) () {
	.m.Clear()
}

// containsAll reports whether set s contains all element of the sequence.
func ( *Set[]) ( iter.Seq[]) bool {
	_ = .m.len
	return iterfuncs.Every(, .Contains)
}

// Equal reports whether s and other contain the same elements.
func ( *Set[]) ( *Set[]) bool {
	return  ==  ||
		.Len() == .Len() && .containsAll(.All())
}

// -- set algebra --

// Union returns a new set containing all elements of s and other.
func ( *Set[]) ( *Set[]) *Set[] {
	 := .Clone() // panics if s is nil
	if  !=  {
		.UnionWith()
	}
	return 
}

// UnionWith adds all elements of other to s.
func ( *Set[]) ( *Set[]) {
	if  ==  {
		return
	}
	.insertAll(.All())
}

// Intersection returns a new set containing elements that are in both s and other.
func ( *Set[]) ( *Set[]) *Set[] {
	if  ==  {
		return .Clone() // s ∩ s = s
	}
	// Iterate over the smaller set for efficiency.
	if .Len() > .Len() {
		,  = , 
	}
	 := NewSet(.m.hasher)
	for  := range .All() {
		if .Contains() {
			.Insert()
		}
	}
	return 
}

// IntersectionWith removes any elements from s that are not in other.
func ( *Set[]) ( *Set[]) {
	if  ==  {
		return
	}
	for  := range .All() {
		if !.Contains() {
			.Delete()
		}
	}
}

// Difference returns a new set containing elements that are in s but not in other.
func ( *Set[]) ( *Set[]) *Set[] {
	_ = .m.len // panic if other is nil
	 := NewSet(.m.hasher)
	if  !=  {
		.diff(, )
	}
	return 
}

// DifferenceWith removes any elements from s that are in other.
func ( *Set[]) ( *Set[]) {
	_ = .m.len     // panic if s is nil
	_ = .m.len // panic if other is nil
	if  ==  {
		.Clear()
		return
	}
	for  := range .All() {
		.Delete()
	}
}

// SymmetricDifference returns a new set containing elements that are in either s or other, but not both.
func ( *Set[]) ( *Set[]) *Set[] {
	_ = .m.len // panic if other is nil
	 := NewSet(.m.hasher)
	if  !=  {
		.diff(, )
		.diff(, )
	}
	return 
}

// SymmetricDifferenceWith sets s to the symmetric difference of s and other.
func ( *Set[]) ( *Set[]) {
	_ = .m.len     // panic if s is nil
	_ = .m.len // panic if other is nil
	if  ==  {
		.Clear()
		return
	}
	for  := range .All() {
		if .Contains() {
			.Delete()
		} else {
			.Insert()
		}
	}
}

// diff adds to s the elements of from that are not in exclude.
func ( *Set[]) (,  *Set[]) {
	for  := range .All() {
		if !.Contains() {
			.Insert()
		}
	}
}

// Intersects reports whether s and other have any elements in common.
func ( *Set[]) ( *Set[]) bool {
	if  ==  {
		return .Len() > 0
	}
	if .Len() > .Len() {
		,  = , 
	}
	// Iterate over the smaller set (other).
	return iterfuncs.Some(.All(), .Contains)
}

// --

// String returns a string representation of the set's elements
// in an unspecified but deterministic order.
//
// Elements are printed as if by [fmt.Sprint].
func ( *Set[]) () string {
	var  strings.Builder
	.WriteByte('{')
	// Sort the entries by their shallow representation,
	// using the same logic as fmt.Sprint(map).
	 := slices.Collect(.All())
	slices.SortStableFunc(, func(,  ) int {
		return fmtsort.Compare(reflect.ValueOf(), reflect.ValueOf())
	})

	for ,  := range  {
		if  > 0 {
			.WriteString(", ")
		}
		fmt.Fprint(&, )
	}
	.WriteByte('}')
	return .String()
}