README
¶
Overview
Go ordered sets.
Features:
-
LinkedSet: ordered set with near-constant-time (O(1)) performance for inserting, deleting, and moving elements. Backed by a map and a doubly-linked list. -
SyncLinkedSet: concurrency-safeLinkedSet, slightly slower. -
SliceSet: slice-backed ordered set. Simpler and faster for small sets, extreme performance degradation for large sets. -
All implementations share a common interface.
-
Small with no dependencies.
See the documentation at https://godoc.org/github.com/mitranim/gord.
Example:
import "github.com/mitranim/gord"
set := gord.NewOrdSet()
// Note the order.
set.Add(20)
set.Add(10)
set.Add(30)
// Redundant and doesn't change the order.
set.Add(30)
set.Add(10)
set.Add(20)
set.Has(10) // true
set.Has(40) // false
set.Values() // []interface{}{20, 10, 30}
set.PopFirst() // 20
set.PopLast() // 30
set.Values() // []interface{}{10}
Known Limitations
-
Has room for performance optimizations.
-
LinkedSetandSyncLinkedSetdon't expose a way to iterate over elements without allocating a slice via.Values(). Can be rectified on demand.
License
Misc
I'm receptive to suggestions. If this library almost satisfies you but needs changes, open an issue or chat me up. Contacts: https://mitranim.com/#contacts
Documentation
¶
Overview ¶
Simple ordered sets. Several implementations are available:
• `LinkedSet`: ordered set with near-constant-time (O(1)) performance for inserting, deleting, and moving elements. Backed by a map and a doubly-linked list.
• `SyncLinkedSet`: concurrency-safe `LinkedSet`, slightly slower.
• `SliceSet`: slice-backed ordered set. Simpler and faster for small sets, extreme performance degradation for large sets.
Installation ¶
Simply import:
import "github.com/mitranim/gord" set := NewOrdSet()
Examples ¶
See the example below for `OrdSet` / `NewOrdSet`.
Index ¶
- type LinkedSet
- func (self *LinkedSet) Add(val interface{})
- func (self *LinkedSet) AddFirst(val interface{})
- func (self *LinkedSet) AddLast(val interface{})
- func (self *LinkedSet) Added(val interface{}) bool
- func (self *LinkedSet) AddedFirst(val interface{}) bool
- func (self *LinkedSet) AddedLast(val interface{}) bool
- func (self *LinkedSet) Delete(val interface{})
- func (self *LinkedSet) Deleted(val interface{}) bool
- func (self *LinkedSet) GoString() string
- func (self *LinkedSet) Has(val interface{}) bool
- func (self *LinkedSet) Len() int
- func (self *LinkedSet) PoppedFirst() (interface{}, bool)
- func (self *LinkedSet) PoppedLast() (interface{}, bool)
- func (self *LinkedSet) String() string
- func (self *LinkedSet) Values() []interface{}
- type OrdSet
- type Set
- type SliceSet
- func (self *SliceSet) Add(val interface{})
- func (self *SliceSet) AddFirst(val interface{})
- func (self *SliceSet) AddLast(val interface{})
- func (self *SliceSet) Added(val interface{}) bool
- func (self *SliceSet) AddedFirst(val interface{}) bool
- func (self *SliceSet) AddedLast(val interface{}) bool
- func (self *SliceSet) Delete(val interface{})
- func (self *SliceSet) Deleted(val interface{}) bool
- func (self *SliceSet) GoString() string
- func (self *SliceSet) Has(val interface{}) bool
- func (self *SliceSet) Len() int
- func (self *SliceSet) PoppedFirst() (interface{}, bool)
- func (self *SliceSet) PoppedLast() (interface{}, bool)
- func (self *SliceSet) String() string
- func (self *SliceSet) Values() []interface{}
- type StringerOrdSet
- type StringerSet
- type SyncLinkedSet
- func (self *SyncLinkedSet) Add(val interface{})
- func (self *SyncLinkedSet) AddFirst(val interface{})
- func (self *SyncLinkedSet) AddLast(val interface{})
- func (self *SyncLinkedSet) Added(val interface{}) bool
- func (self *SyncLinkedSet) AddedFirst(val interface{}) bool
- func (self *SyncLinkedSet) AddedLast(val interface{}) bool
- func (self *SyncLinkedSet) Delete(val interface{})
- func (self *SyncLinkedSet) Deleted(val interface{}) bool
- func (self *SyncLinkedSet) GoString() string
- func (self *SyncLinkedSet) Has(val interface{}) bool
- func (self *SyncLinkedSet) Len() int
- func (self *SyncLinkedSet) PoppedFirst() (interface{}, bool)
- func (self *SyncLinkedSet) PoppedLast() (interface{}, bool)
- func (self *SyncLinkedSet) String() string
- func (self *SyncLinkedSet) Values() []interface{}
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LinkedSet ¶
type LinkedSet struct {
// contains filtered or unexported fields
}
Ordered set. Satisfies the `OrdSet` interface. A zero value is ready to use, but should not be copied after the first mutation. Has near-constant-time (O(1)) performance for inserting, deleting, and moving elements.
Concurrency-unsafe; use `SyncLinkedSet` for concurrent access.
func NewLinkedSet ¶
func NewLinkedSet(vals ...interface{}) *LinkedSet
Constructs a new `LinkedSet` from the provided values, deduplicating them.
func (*LinkedSet) AddedFirst ¶
Satisfy `OrdSet`.
func (*LinkedSet) PoppedFirst ¶
Satisfy `OrdSet`.
func (*LinkedSet) PoppedLast ¶
Satisfy `OrdSet`.
type OrdSet ¶
type OrdSet interface {
Set
// Void version of `.AddedFirst`.
AddFirst(val interface{})
// If `set.Has(val)`, moves the value to the first position and returns `false`.
// If `!set.Has(val)`, prepends the value at the start and returns `true`.
AddedFirst(val interface{}) bool
// Void version of `.AddedLast`.
AddLast(val interface{})
// If `set.Has(val)`, moves the value to the last position and returns `false`.
// If `!set.Has(val)`, appends the value at the end and returns `true`.
AddedLast(val interface{}) bool
// There's no corresponding `.PopFirst` (without the boolean) to avoid the
// potential gotcha where the first value was `nil`, but the code would
// erroneously think that the set was empty.
PoppedFirst() (interface{}, bool)
// There's no corresponding `.PopLast` (without the boolean) to avoid the
// potential gotcha where the last value was `nil`, but the code would
// erroneously think that the set was empty.
PoppedLast() (interface{}, bool)
// Returns the set's values as a slice, in the same order. Allowed to return
// either `nil` or `[]interface{}{}`. Callers are expected to not care about
// the distinction, or the slice's capacity. Whether the callers are allowed
// to mutate the slice depends on the implementation of the backing type.
Values() []interface{}
}
Interface that describes an ordered set. Strict superset of `Set`. Satisfied by every type in this package.
Example ¶
set := NewOrdSet()
// Note the order.
fmt.Println(set.Added(20)) // true
fmt.Println(set.Added(10)) // true
fmt.Println(set.Added(30)) // true
// Redundant and doesn't change the order.
fmt.Println(set.Added(30)) // false
fmt.Println(set.Added(10)) // false
fmt.Println(set.Added(20)) // false
fmt.Println(set.Has(10)) // true
fmt.Println(set.Has(40)) // false
fmt.Println(set.Values()) // []interface{}{20, 10, 30}
fmt.Println(set.PoppedFirst()) // 20, true
fmt.Println(set.PoppedLast()) // 30, true
fmt.Println(set.Values()) // []interface{}{10}
Output: true true true false false false true false [20 10 30] 20 true 30 true [10]
type Set ¶
type Set interface {
// Current set size, replacement for `len(set)`.
Len() int
// Answers whether the value is in the set.
Has(val interface{}) bool
// Void version of `.Added`.
Add(val interface{})
// If `set.Has(val)`, has no effect and returns `false`.
// If `!set.Has(val)`, appends `val` to the end and returns `true`.
// In ordered sets (every type in this package), must not change the order.
Added(val interface{}) bool
// Void version of `.Deleted`.
Delete(val interface{})
// If `set.Has(val)`, deletes the value and returns `true`.
// If `!set.Has(val)`, does nothing and returns `false`.
Deleted(val interface{}) bool
}
Interface that describes an arbitrary set, but not necessarily an ordered set. Satisfied by every type in this package. See `OrdSet` for the full interface.
type SliceSet ¶
type SliceSet []interface{}
Ordered set implemented as a slice. Compared to `LinkedSet`, this is simpler and more efficient (memory and CPU wise) for small sets, but some operations have extreme performance degradation for large sets. Giving the exact values of "small" and "large" requires more testing; might depend on hardware.
There's no "concurrent" version of this type, mainly because it would have to sacrifice elegance. It may be added on demand.
func NewSliceSet ¶
func NewSliceSet(vals ...interface{}) *SliceSet
Constructs a new `SliceSet` from the provided values. Very similar to `SliceSet{}` or `&SliceSet{}`, but discards duplicates.
func (*SliceSet) AddedFirst ¶
Satisfy `OrdSet`.
func (*SliceSet) PoppedFirst ¶
Satisfy `OrdSet`.
func (*SliceSet) PoppedLast ¶
Satisfy `OrdSet`.
type StringerOrdSet ¶
type StringerOrdSet interface {
OrdSet
fmt.Stringer
fmt.GoStringer
}
Describes an ordered set with extra printing methods. Satisfied by every type in this package.
type StringerSet ¶
type StringerSet interface {
Set
fmt.Stringer
fmt.GoStringer
}
Describes a set with extra printing methods. Satisfied by every type in this package.
type SyncLinkedSet ¶
type SyncLinkedSet struct {
// contains filtered or unexported fields
}
Concurrency-safe, slightly slower version of `LinkedSet`. Satisfies the `OrdSet` interface. A zero value is ready to use, but should never be copied. Uses a mutex.
func NewSyncLinkedSet ¶
func NewSyncLinkedSet(vals ...interface{}) *SyncLinkedSet
Constructs a new `SyncLinkedSet` from the provided values, deduplicating them.
func (*SyncLinkedSet) Add ¶
func (self *SyncLinkedSet) Add(val interface{})
Concurrency-safe version of `LinkedSet.Add`.
func (*SyncLinkedSet) AddFirst ¶
func (self *SyncLinkedSet) AddFirst(val interface{})
Concurrency-safe version of `LinkedSet.AddFirst`.
func (*SyncLinkedSet) AddLast ¶
func (self *SyncLinkedSet) AddLast(val interface{})
Concurrency-safe version of `LinkedSet.AddLast`.
func (*SyncLinkedSet) Added ¶
func (self *SyncLinkedSet) Added(val interface{}) bool
Concurrency-safe version of `LinkedSet.Added`.
func (*SyncLinkedSet) AddedFirst ¶
func (self *SyncLinkedSet) AddedFirst(val interface{}) bool
Concurrency-safe version of `LinkedSet.AddedFirst`.
func (*SyncLinkedSet) AddedLast ¶
func (self *SyncLinkedSet) AddedLast(val interface{}) bool
Concurrency-safe version of `LinkedSet.AddedLast`.
func (*SyncLinkedSet) Delete ¶
func (self *SyncLinkedSet) Delete(val interface{})
Concurrency-safe version of `LinkedSet.Delete`.
func (*SyncLinkedSet) Deleted ¶
func (self *SyncLinkedSet) Deleted(val interface{}) bool
Concurrency-safe version of `LinkedSet.Deleted`.
func (*SyncLinkedSet) GoString ¶
func (self *SyncLinkedSet) GoString() string
Concurrency-safe version of `LinkedSet.GoString`.
func (*SyncLinkedSet) Has ¶
func (self *SyncLinkedSet) Has(val interface{}) bool
Concurrency-safe version of `LinkedSet.Has`.
func (*SyncLinkedSet) Len ¶
func (self *SyncLinkedSet) Len() int
Concurrency-safe version of `LinkedSet.Len`.
func (*SyncLinkedSet) PoppedFirst ¶
func (self *SyncLinkedSet) PoppedFirst() (interface{}, bool)
Concurrency-safe version of `LinkedSet.PoppedFirst`.
func (*SyncLinkedSet) PoppedLast ¶
func (self *SyncLinkedSet) PoppedLast() (interface{}, bool)
Concurrency-safe version of `LinkedSet.PoppedLast`.
func (*SyncLinkedSet) String ¶
func (self *SyncLinkedSet) String() string
Concurrency-safe version of `LinkedSet.String`.
func (*SyncLinkedSet) Values ¶
func (self *SyncLinkedSet) Values() []interface{}
Concurrency-safe version of `LinkedSet.Values`.
Source Files