set.go

Documentation: k8s.io/apimachinery/pkg/util/sets

     1  /*
     2  Copyright 2022 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package sets
    18  
    19  import (
    20  	"cmp"
    21  	"sort"
    22  )
    23  
    24  // Set is a set of the same type elements, implemented via map[comparable]struct{} for minimal memory consumption.
    25  type Set[T comparable] map[T]Empty
    26  
    27  // cast transforms specified set to generic Set[T].
    28  func cast[T comparable](s map[T]Empty) Set[T] { return s }
    29  
    30  // New creates a Set from a list of values.
    31  // NOTE: type param must be explicitly instantiated if given items are empty.
    32  func New[T comparable](items ...T) Set[T] {
    33  	ss := make(Set[T], len(items))
    34  	ss.Insert(items...)
    35  	return ss
    36  }
    37  
    38  // KeySet creates a Set from a keys of a map[comparable](? extends interface{}).
    39  // If the value passed in is not actually a map, this will panic.
    40  func KeySet[T comparable, V any](theMap map[T]V) Set[T] {
    41  	ret := make(Set[T], len(theMap))
    42  	for keyValue := range theMap {
    43  		ret.Insert(keyValue)
    44  	}
    45  	return ret
    46  }
    47  
    48  // Insert adds items to the set.
    49  func (s Set[T]) Insert(items ...T) Set[T] {
    50  	for _, item := range items {
    51  		s[item] = Empty{}
    52  	}
    53  	return s
    54  }
    55  
    56  func Insert[T comparable](set Set[T], items ...T) Set[T] {
    57  	return set.Insert(items...)
    58  }
    59  
    60  // Delete removes all items from the set.
    61  func (s Set[T]) Delete(items ...T) Set[T] {
    62  	for _, item := range items {
    63  		delete(s, item)
    64  	}
    65  	return s
    66  }
    67  
    68  // Clear empties the set.
    69  // It is preferable to replace the set with a newly constructed set,
    70  // but not all callers can do that (when there are other references to the map).
    71  // In some cases the set *won't* be fully cleared, e.g. a Set[float32] containing NaN
    72  // can't be cleared because NaN can't be removed.
    73  // For sets containing items of a type that is reflexive for ==,
    74  // this is optimized to a single call to runtime.mapclear().
    75  func (s Set[T]) Clear() Set[T] {
    76  	for key := range s {
    77  		delete(s, key)
    78  	}
    79  	return s
    80  }
    81  
    82  // Has returns true if and only if item is contained in the set.
    83  func (s Set[T]) Has(item T) bool {
    84  	_, contained := s[item]
    85  	return contained
    86  }
    87  
    88  // HasAll returns true if and only if all items are contained in the set.
    89  func (s Set[T]) HasAll(items ...T) bool {
    90  	for _, item := range items {
    91  		if !s.Has(item) {
    92  			return false
    93  		}
    94  	}
    95  	return true
    96  }
    97  
    98  // HasAny returns true if any items are contained in the set.
    99  func (s Set[T]) HasAny(items ...T) bool {
   100  	for _, item := range items {
   101  		if s.Has(item) {
   102  			return true
   103  		}
   104  	}
   105  	return false
   106  }
   107  
   108  // Clone returns a new set which is a copy of the current set.
   109  func (s Set[T]) Clone() Set[T] {
   110  	result := make(Set[T], len(s))
   111  	for key := range s {
   112  		result.Insert(key)
   113  	}
   114  	return result
   115  }
   116  
   117  // Difference returns a set of objects that are not in s2.
   118  // For example:
   119  // s1 = {a1, a2, a3}
   120  // s2 = {a1, a2, a4, a5}
   121  // s1.Difference(s2) = {a3}
   122  // s2.Difference(s1) = {a4, a5}
   123  func (s1 Set[T]) Difference(s2 Set[T]) Set[T] {
   124  	result := New[T]()
   125  	for key := range s1 {
   126  		if !s2.Has(key) {
   127  			result.Insert(key)
   128  		}
   129  	}
   130  	return result
   131  }
   132  
   133  // SymmetricDifference returns a set of elements which are in either of the sets, but not in their intersection.
   134  // For example:
   135  // s1 = {a1, a2, a3}
   136  // s2 = {a1, a2, a4, a5}
   137  // s1.SymmetricDifference(s2) = {a3, a4, a5}
   138  // s2.SymmetricDifference(s1) = {a3, a4, a5}
   139  func (s1 Set[T]) SymmetricDifference(s2 Set[T]) Set[T] {
   140  	return s1.Difference(s2).Union(s2.Difference(s1))
   141  }
   142  
   143  // Union returns a new set which includes items in either s1 or s2.
   144  // For example:
   145  // s1 = {a1, a2}
   146  // s2 = {a3, a4}
   147  // s1.Union(s2) = {a1, a2, a3, a4}
   148  // s2.Union(s1) = {a1, a2, a3, a4}
   149  func (s1 Set[T]) Union(s2 Set[T]) Set[T] {
   150  	result := s1.Clone()
   151  	for key := range s2 {
   152  		result.Insert(key)
   153  	}
   154  	return result
   155  }
   156  
   157  // Intersection returns a new set which includes the item in BOTH s1 and s2
   158  // For example:
   159  // s1 = {a1, a2}
   160  // s2 = {a2, a3}
   161  // s1.Intersection(s2) = {a2}
   162  func (s1 Set[T]) Intersection(s2 Set[T]) Set[T] {
   163  	var walk, other Set[T]
   164  	result := New[T]()
   165  	if s1.Len() < s2.Len() {
   166  		walk = s1
   167  		other = s2
   168  	} else {
   169  		walk = s2
   170  		other = s1
   171  	}
   172  	for key := range walk {
   173  		if other.Has(key) {
   174  			result.Insert(key)
   175  		}
   176  	}
   177  	return result
   178  }
   179  
   180  // IsSuperset returns true if and only if s1 is a superset of s2.
   181  func (s1 Set[T]) IsSuperset(s2 Set[T]) bool {
   182  	for item := range s2 {
   183  		if !s1.Has(item) {
   184  			return false
   185  		}
   186  	}
   187  	return true
   188  }
   189  
   190  // Equal returns true if and only if s1 is equal (as a set) to s2.
   191  // Two sets are equal if their membership is identical.
   192  // (In practice, this means same elements, order doesn't matter)
   193  func (s1 Set[T]) Equal(s2 Set[T]) bool {
   194  	return len(s1) == len(s2) && s1.IsSuperset(s2)
   195  }
   196  
   197  type sortableSliceOfGeneric[T cmp.Ordered] []T
   198  
   199  func (g sortableSliceOfGeneric[T]) Len() int           { return len(g) }
   200  func (g sortableSliceOfGeneric[T]) Less(i, j int) bool { return less[T](g[i], g[j]) }
   201  func (g sortableSliceOfGeneric[T]) Swap(i, j int)      { g[i], g[j] = g[j], g[i] }
   202  
   203  // List returns the contents as a sorted T slice.
   204  //
   205  // This is a separate function and not a method because not all types supported
   206  // by Generic are ordered and only those can be sorted.
   207  func List[T cmp.Ordered](s Set[T]) []T {
   208  	res := make(sortableSliceOfGeneric[T], 0, len(s))
   209  	for key := range s {
   210  		res = append(res, key)
   211  	}
   212  	sort.Sort(res)
   213  	return res
   214  }
   215  
   216  // UnsortedList returns the slice with contents in random order.
   217  func (s Set[T]) UnsortedList() []T {
   218  	res := make([]T, 0, len(s))
   219  	for key := range s {
   220  		res = append(res, key)
   221  	}
   222  	return res
   223  }
   224  
   225  // PopAny returns a single element from the set.
   226  func (s Set[T]) PopAny() (T, bool) {
   227  	for key := range s {
   228  		s.Delete(key)
   229  		return key, true
   230  	}
   231  	var zeroValue T
   232  	return zeroValue, false
   233  }
   234  
   235  // Len returns the size of the set.
   236  func (s Set[T]) Len() int {
   237  	return len(s)
   238  }
   239  
   240  func less[T cmp.Ordered](lhs, rhs T) bool {
   241  	return lhs < rhs
   242  }
   243
View as plain text