1// Copyright (c) 2015, Emir Pasic. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package linkedhashset is a set that preserves insertion-order. 6// 7// It is backed by a hash table to store values and doubly-linked list to store ordering. 8// 9// Note that insertion-order is not affected if an element is re-inserted into the set. 10// 11// Structure is not thread safe. 12// 13// References: http://en.wikipedia.org/wiki/Set_%28abstract_data_type%29 14package linkedhashset 15 16import ( 17 "fmt" 18 "github.com/emirpasic/gods/lists/doublylinkedlist" 19 "github.com/emirpasic/gods/sets" 20 "strings" 21) 22 23func assertSetImplementation() { 24 var _ sets.Set = (*Set)(nil) 25} 26 27// Set holds elements in go's native map 28type Set struct { 29 table map[interface{}]struct{} 30 ordering *doublylinkedlist.List 31} 32 33var itemExists = struct{}{} 34 35// New instantiates a new empty set and adds the passed values, if any, to the set 36func New(values ...interface{}) *Set { 37 set := &Set{ 38 table: make(map[interface{}]struct{}), 39 ordering: doublylinkedlist.New(), 40 } 41 if len(values) > 0 { 42 set.Add(values...) 43 } 44 return set 45} 46 47// Add adds the items (one or more) to the set. 48// Note that insertion-order is not affected if an element is re-inserted into the set. 49func (set *Set) Add(items ...interface{}) { 50 for _, item := range items { 51 if _, contains := set.table[item]; !contains { 52 set.table[item] = itemExists 53 set.ordering.Append(item) 54 } 55 } 56} 57 58// Remove removes the items (one or more) from the set. 59// Slow operation, worst-case O(n^2). 60func (set *Set) Remove(items ...interface{}) { 61 for _, item := range items { 62 if _, contains := set.table[item]; contains { 63 delete(set.table, item) 64 index := set.ordering.IndexOf(item) 65 set.ordering.Remove(index) 66 } 67 } 68} 69 70// Contains check if items (one or more) are present in the set. 71// All items have to be present in the set for the method to return true. 72// Returns true if no arguments are passed at all, i.e. set is always superset of empty set. 73func (set *Set) Contains(items ...interface{}) bool { 74 for _, item := range items { 75 if _, contains := set.table[item]; !contains { 76 return false 77 } 78 } 79 return true 80} 81 82// Empty returns true if set does not contain any elements. 83func (set *Set) Empty() bool { 84 return set.Size() == 0 85} 86 87// Size returns number of elements within the set. 88func (set *Set) Size() int { 89 return set.ordering.Size() 90} 91 92// Clear clears all values in the set. 93func (set *Set) Clear() { 94 set.table = make(map[interface{}]struct{}) 95 set.ordering.Clear() 96} 97 98// Values returns all items in the set. 99func (set *Set) Values() []interface{} { 100 values := make([]interface{}, set.Size()) 101 it := set.Iterator() 102 for it.Next() { 103 values[it.Index()] = it.Value() 104 } 105 return values 106} 107 108// String returns a string representation of container 109func (set *Set) String() string { 110 str := "LinkedHashSet\n" 111 items := []string{} 112 it := set.Iterator() 113 for it.Next() { 114 items = append(items, fmt.Sprintf("%v", it.Value())) 115 } 116 str += strings.Join(items, ", ") 117 return str 118} 119