set.go

Documentation: k8s.io/utils/set

     1  /*
     2  Copyright 2023 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 set
    18  
    19  import (
    20  	"sort"
    21  )
    22  
    23  // Empty is public since it is used by some internal API objects for conversions between external
    24  // string arrays and internal sets, and conversion logic requires public types today.
    25  type Empty struct{}
    26  
    27  // Set is a set of the same type elements, implemented via map[ordered]struct{} for minimal memory consumption.
    28  type Set[E ordered] map[E]Empty
    29  
    30  // New creates a new set.
    31  func New[E ordered](items ...E) Set[E] {
    32  	ss := Set[E]{}
    33  	ss.Insert(items...)
    34  	return ss
    35  }
    36  
    37  // KeySet creates a Set[E] from a keys of a map[E](? extends interface{}).
    38  func KeySet[E ordered, A any](theMap map[E]A) Set[E] {
    39  	ret := Set[E]{}
    40  	for key := range theMap {
    41  		ret.Insert(key)
    42  	}
    43  	return ret
    44  }
    45  
    46  // Insert adds items to the set.
    47  func (s Set[E]) Insert(items ...E) Set[E] {
    48  	for _, item := range items {
    49  		s[item] = Empty{}
    50  	}
    51  	return s
    52  }
    53  
    54  // Delete removes all items from the set.
    55  func (s Set[E]) Delete(items ...E) Set[E] {
    56  	for _, item := range items {
    57  		delete(s, item)
    58  	}
    59  	return s
    60  }
    61  
    62  // Has returns true if and only if item is contained in the set.
    63  func (s Set[E]) Has(item E) bool {
    64  	_, contained := s[item]
    65  	return contained
    66  }
    67  
    68  // HasAll returns true if and only if all items are contained in the set.
    69  func (s Set[E]) HasAll(items ...E) bool {
    70  	for _, item := range items {
    71  		if !s.Has(item) {
    72  			return false
    73  		}
    74  	}
    75  	return true
    76  }
    77  
    78  // HasAny returns true if any items are contained in the set.
    79  func (s Set[E]) HasAny(items ...E) bool {
    80  	for _, item := range items {
    81  		if s.Has(item) {
    82  			return true
    83  		}
    84  	}
    85  	return false
    86  }
    87  
    88  // Union returns a new set which includes items in either s1 or s2.
    89  // For example:
    90  // s1 = {a1, a2}
    91  // s2 = {a3, a4}
    92  // s1.Union(s2) = {a1, a2, a3, a4}
    93  // s2.Union(s1) = {a1, a2, a3, a4}
    94  func (s Set[E]) Union(s2 Set[E]) Set[E] {
    95  	result := Set[E]{}
    96  	result.Insert(s.UnsortedList()...)
    97  	result.Insert(s2.UnsortedList()...)
    98  	return result
    99  }
   100  
   101  // Len returns the number of elements in the set.
   102  func (s Set[E]) Len() int {
   103  	return len(s)
   104  }
   105  
   106  // Intersection returns a new set which includes the item in BOTH s1 and s2
   107  // For example:
   108  // s1 = {a1, a2}
   109  // s2 = {a2, a3}
   110  // s1.Intersection(s2) = {a2}
   111  func (s Set[E]) Intersection(s2 Set[E]) Set[E] {
   112  	var walk, other Set[E]
   113  	result := Set[E]{}
   114  	if s.Len() < s2.Len() {
   115  		walk = s
   116  		other = s2
   117  	} else {
   118  		walk = s2
   119  		other = s
   120  	}
   121  	for key := range walk {
   122  		if other.Has(key) {
   123  			result.Insert(key)
   124  		}
   125  	}
   126  	return result
   127  }
   128  
   129  // IsSuperset returns true if and only if s1 is a superset of s2.
   130  func (s Set[E]) IsSuperset(s2 Set[E]) bool {
   131  	for item := range s2 {
   132  		if !s.Has(item) {
   133  			return false
   134  		}
   135  	}
   136  	return true
   137  }
   138  
   139  // Difference returns a set of objects that are not in s2
   140  // For example:
   141  // s1 = {a1, a2, a3}
   142  // s2 = {a1, a2, a4, a5}
   143  // s1.Difference(s2) = {a3}
   144  // s2.Difference(s1) = {a4, a5}
   145  func (s Set[E]) Difference(s2 Set[E]) Set[E] {
   146  	result := Set[E]{}
   147  	for key := range s {
   148  		if !s2.Has(key) {
   149  			result.Insert(key)
   150  		}
   151  	}
   152  	return result
   153  }
   154  
   155  // Equal returns true if and only if s1 is equal (as a set) to s2.
   156  // Two sets are equal if their membership is identical.
   157  func (s Set[E]) Equal(s2 Set[E]) bool {
   158  	return s.Len() == s2.Len() && s.IsSuperset(s2)
   159  }
   160  
   161  type sortableSlice[E ordered] []E
   162  
   163  func (s sortableSlice[E]) Len() int {
   164  	return len(s)
   165  }
   166  func (s sortableSlice[E]) Less(i, j int) bool { return s[i] < s[j] }
   167  func (s sortableSlice[E]) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   168  
   169  // SortedList returns the contents as a sorted slice.
   170  func (s Set[E]) SortedList() []E {
   171  	res := make(sortableSlice[E], 0, s.Len())
   172  	for key := range s {
   173  		res = append(res, key)
   174  	}
   175  	sort.Sort(res)
   176  	return res
   177  }
   178  
   179  // UnsortedList returns the slice with contents in random order.
   180  func (s Set[E]) UnsortedList() []E {
   181  	res := make([]E, 0, len(s))
   182  	for key := range s {
   183  		res = append(res, key)
   184  	}
   185  	return res
   186  }
   187  
   188  // PopAny returns a single element from the set.
   189  func (s Set[E]) PopAny() (E, bool) {
   190  	for key := range s {
   191  		s.Delete(key)
   192  		return key, true
   193  	}
   194  	var zeroValue E
   195  	return zeroValue, false
   196  }
   197  
   198  // Clone returns a new set which is a copy of the current set.
   199  func (s Set[T]) Clone() Set[T] {
   200  	result := make(Set[T], len(s))
   201  	for key := range s {
   202  		result.Insert(key)
   203  	}
   204  	return result
   205  }
   206  
   207  // SymmetricDifference returns a set of elements which are in either of the sets, but not in their intersection.
   208  // For example:
   209  // s1 = {a1, a2, a3}
   210  // s2 = {a1, a2, a4, a5}
   211  // s1.SymmetricDifference(s2) = {a3, a4, a5}
   212  // s2.SymmetricDifference(s1) = {a3, a4, a5}
   213  func (s Set[T]) SymmetricDifference(s2 Set[T]) Set[T] {
   214  	return s.Difference(s2).Union(s2.Difference(s))
   215  }
   216
View as plain text