sets.go

Documentation: github.com/benbjohnson/immutable

     1  package immutable
     2  
     3  // Set represents a collection of unique values. The set uses a Hasher
     4  // to generate hashes and check for equality of key values.
     5  //
     6  // Internally, the Set stores values as keys of a Map[T,struct{}]
     7  type Set[T any] struct {
     8  	m *Map[T, struct{}]
     9  }
    10  
    11  // NewSet returns a new instance of Set.
    12  //
    13  // If hasher is nil, a default hasher implementation will automatically be chosen based on the first key added.
    14  // Default hasher implementations only exist for int, string, and byte slice types.
    15  // NewSet can also take some initial values as varargs.
    16  func NewSet[T any](hasher Hasher[T], values ...T) Set[T] {
    17  	m := NewMap[T, struct{}](hasher)
    18  	for _, value := range values {
    19  		m = m.set(value, struct{}{}, true)
    20  	}
    21  	return Set[T]{m}
    22  }
    23  
    24  // Add returns a set containing the new value.
    25  //
    26  // This function will return a new set even if the set already contains the value.
    27  func (s Set[T]) Add(value T) Set[T] {
    28  	return Set[T]{s.m.Set(value, struct{}{})}
    29  }
    30  
    31  // Delete returns a set with the given key removed.
    32  func (s Set[T]) Delete(value T) Set[T] {
    33  	return Set[T]{s.m.Delete(value)}
    34  }
    35  
    36  // Has returns true when the set contains the given value
    37  func (s Set[T]) Has(val T) bool {
    38  	_, ok := s.m.Get(val)
    39  	return ok
    40  }
    41  
    42  // Len returns the number of elements in the underlying map.
    43  func (s Set[K]) Len() int {
    44  	return s.m.Len()
    45  }
    46  
    47  // Items returns a slice of the items inside the set
    48  func (s Set[T]) Items() []T {
    49  	r := make([]T, 0, s.Len())
    50  	itr := s.Iterator()
    51  	for !itr.Done() {
    52  		v, _ := itr.Next()
    53  		r = append(r, v)
    54  	}
    55  	return r
    56  }
    57  
    58  // Iterator returns a new iterator for this set positioned at the first value.
    59  func (s Set[T]) Iterator() *SetIterator[T] {
    60  	itr := &SetIterator[T]{mi: s.m.Iterator()}
    61  	itr.mi.First()
    62  	return itr
    63  }
    64  
    65  // SetIterator represents an iterator over a set.
    66  // Iteration can occur in natural or reverse order based on use of Next() or Prev().
    67  type SetIterator[T any] struct {
    68  	mi *MapIterator[T, struct{}]
    69  }
    70  
    71  // Done returns true if no more values remain in the iterator.
    72  func (itr *SetIterator[T]) Done() bool {
    73  	return itr.mi.Done()
    74  }
    75  
    76  // First moves the iterator to the first value.
    77  func (itr *SetIterator[T]) First() {
    78  	itr.mi.First()
    79  }
    80  
    81  // Next moves the iterator to the next value.
    82  func (itr *SetIterator[T]) Next() (val T, ok bool) {
    83  	val, _, ok = itr.mi.Next()
    84  	return
    85  }
    86  
    87  type SetBuilder[T any] struct {
    88  	s Set[T]
    89  }
    90  
    91  func NewSetBuilder[T any](hasher Hasher[T]) *SetBuilder[T] {
    92  	return &SetBuilder[T]{s: NewSet(hasher)}
    93  }
    94  
    95  func (s SetBuilder[T]) Set(val T) {
    96  	s.s.m = s.s.m.set(val, struct{}{}, true)
    97  }
    98  
    99  func (s SetBuilder[T]) Delete(val T) {
   100  	s.s.m = s.s.m.delete(val, true)
   101  }
   102  
   103  func (s SetBuilder[T]) Has(val T) bool {
   104  	return s.s.Has(val)
   105  }
   106  
   107  func (s SetBuilder[T]) Len() int {
   108  	return s.s.Len()
   109  }
   110  
   111  type SortedSet[T any] struct {
   112  	m *SortedMap[T, struct{}]
   113  }
   114  
   115  // NewSortedSet returns a new instance of SortedSet.
   116  //
   117  // If comparer is nil then
   118  // a default comparer is set after the first key is inserted. Default comparers
   119  // exist for int, string, and byte slice keys.
   120  // NewSortedSet can also take some initial values as varargs.
   121  func NewSortedSet[T any](comparer Comparer[T], values ...T) SortedSet[T] {
   122  	m := NewSortedMap[T, struct{}](comparer)
   123  	for _, value := range values {
   124  		m = m.set(value, struct{}{}, true)
   125  	}
   126  	return SortedSet[T]{m}
   127  }
   128  
   129  // Add returns a set containing the new value.
   130  //
   131  // This function will return a new set even if the set already contains the value.
   132  func (s SortedSet[T]) Add(value T) SortedSet[T] {
   133  	return SortedSet[T]{s.m.Set(value, struct{}{})}
   134  }
   135  
   136  // Delete returns a set with the given key removed.
   137  func (s SortedSet[T]) Delete(value T) SortedSet[T] {
   138  	return SortedSet[T]{s.m.Delete(value)}
   139  }
   140  
   141  // Has returns true when the set contains the given value
   142  func (s SortedSet[T]) Has(val T) bool {
   143  	_, ok := s.m.Get(val)
   144  	return ok
   145  }
   146  
   147  // Len returns the number of elements in the underlying map.
   148  func (s SortedSet[K]) Len() int {
   149  	return s.m.Len()
   150  }
   151  
   152  // Items returns a slice of the items inside the set
   153  func (s SortedSet[T]) Items() []T {
   154  	r := make([]T, 0, s.Len())
   155  	itr := s.Iterator()
   156  	for !itr.Done() {
   157  		v, _ := itr.Next()
   158  		r = append(r, v)
   159  	}
   160  	return r
   161  }
   162  
   163  // Iterator returns a new iterator for this set positioned at the first value.
   164  func (s SortedSet[T]) Iterator() *SortedSetIterator[T] {
   165  	itr := &SortedSetIterator[T]{mi: s.m.Iterator()}
   166  	itr.mi.First()
   167  	return itr
   168  }
   169  
   170  // SortedSetIterator represents an iterator over a sorted set.
   171  // Iteration can occur in natural or reverse order based on use of Next() or Prev().
   172  type SortedSetIterator[T any] struct {
   173  	mi *SortedMapIterator[T, struct{}]
   174  }
   175  
   176  // Done returns true if no more values remain in the iterator.
   177  func (itr *SortedSetIterator[T]) Done() bool {
   178  	return itr.mi.Done()
   179  }
   180  
   181  // First moves the iterator to the first value.
   182  func (itr *SortedSetIterator[T]) First() {
   183  	itr.mi.First()
   184  }
   185  
   186  // Last moves the iterator to the last value.
   187  func (itr *SortedSetIterator[T]) Last() {
   188  	itr.mi.Last()
   189  }
   190  
   191  // Next moves the iterator to the next value.
   192  func (itr *SortedSetIterator[T]) Next() (val T, ok bool) {
   193  	val, _, ok = itr.mi.Next()
   194  	return
   195  }
   196  
   197  // Next moves the iterator to the previous value.
   198  func (itr *SortedSetIterator[T]) Prev() (val T, ok bool) {
   199  	val, _, ok = itr.mi.Prev()
   200  	return
   201  }
   202  
   203  // Next moves the iterator to the given value.
   204  //
   205  // If the value does not exist then the next value is used. If no more keys exist
   206  // then the iterator is marked as done.
   207  func (itr *SortedSetIterator[T]) Seek(val T) {
   208  	itr.mi.Seek(val)
   209  }
   210  
   211  type SortedSetBuilder[T any] struct {
   212  	s SortedSet[T]
   213  }
   214  
   215  func NewSortedSetBuilder[T any](comparer Comparer[T]) *SortedSetBuilder[T] {
   216  	return &SortedSetBuilder[T]{s: NewSortedSet(comparer)}
   217  }
   218  
   219  func (s SortedSetBuilder[T]) Set(val T) {
   220  	s.s.m = s.s.m.set(val, struct{}{}, true)
   221  }
   222  
   223  func (s SortedSetBuilder[T]) Delete(val T) {
   224  	s.s.m = s.s.m.delete(val, true)
   225  }
   226  
   227  func (s SortedSetBuilder[T]) Has(val T) bool {
   228  	return s.s.Has(val)
   229  }
   230  
   231  func (s SortedSetBuilder[T]) Len() int {
   232  	return s.s.Len()
   233  }
   234
View as plain text