8 // OrderedSet is a set with limited capacity.
9 // Items are evicted according to their insertion order.
10 type OrderedSet struct {
12 set map[interface{}]struct{}
20 // NewOrderedSet creates an ordered set with given capacity
21 func NewOrderedSet(capacity int) (*OrderedSet, error) {
23 return nil, errors.New("capacity must be a positive integer")
28 set: map[interface{}]struct{}{},
29 queue: make([]interface{}, capacity),
34 // Add inserts items into the set.
35 // If capacity is reached, oldest items are evicted
36 func (os *OrderedSet) Add(items ...interface{}) {
38 defer os.lock.Unlock()
40 for _, item := range items {
41 if _, ok := os.set[item]; ok {
45 next := (os.end + 1) % os.capacity
46 if os.end != -1 && next == os.start {
47 delete(os.set, os.queue[os.start])
48 os.start = (os.start + 1) % os.capacity
51 os.queue[os.end] = item
52 os.set[item] = struct{}{}
56 // Has checks if certain items exists in the set
57 func (os *OrderedSet) Has(item interface{}) bool {
59 defer os.lock.RUnlock()
65 // Size returns the size of the set
66 func (os *OrderedSet) Size() int {
68 defer os.lock.RUnlock()