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