]>
Commit | Line | Data |
---|---|---|
bae9f6d2 JC |
1 | package dag |
2 | ||
3 | import ( | |
4 | "sync" | |
5 | ) | |
6 | ||
7 | // Set is a set data structure. | |
8 | type Set struct { | |
9 | m map[interface{}]interface{} | |
10 | once sync.Once | |
11 | } | |
12 | ||
13 | // Hashable is the interface used by set to get the hash code of a value. | |
14 | // If this isn't given, then the value of the item being added to the set | |
15 | // itself is used as the comparison value. | |
16 | type Hashable interface { | |
17 | Hashcode() interface{} | |
18 | } | |
19 | ||
20 | // hashcode returns the hashcode used for set elements. | |
21 | func hashcode(v interface{}) interface{} { | |
22 | if h, ok := v.(Hashable); ok { | |
23 | return h.Hashcode() | |
24 | } | |
25 | ||
26 | return v | |
27 | } | |
28 | ||
29 | // Add adds an item to the set | |
30 | func (s *Set) Add(v interface{}) { | |
31 | s.once.Do(s.init) | |
32 | s.m[hashcode(v)] = v | |
33 | } | |
34 | ||
35 | // Delete removes an item from the set. | |
36 | func (s *Set) Delete(v interface{}) { | |
37 | s.once.Do(s.init) | |
38 | delete(s.m, hashcode(v)) | |
39 | } | |
40 | ||
41 | // Include returns true/false of whether a value is in the set. | |
42 | func (s *Set) Include(v interface{}) bool { | |
43 | s.once.Do(s.init) | |
44 | _, ok := s.m[hashcode(v)] | |
45 | return ok | |
46 | } | |
47 | ||
48 | // Intersection computes the set intersection with other. | |
49 | func (s *Set) Intersection(other *Set) *Set { | |
50 | result := new(Set) | |
51 | if s == nil { | |
52 | return result | |
53 | } | |
54 | if other != nil { | |
55 | for _, v := range s.m { | |
56 | if other.Include(v) { | |
57 | result.Add(v) | |
58 | } | |
59 | } | |
60 | } | |
61 | ||
62 | return result | |
63 | } | |
64 | ||
65 | // Difference returns a set with the elements that s has but | |
66 | // other doesn't. | |
67 | func (s *Set) Difference(other *Set) *Set { | |
68 | result := new(Set) | |
69 | if s != nil { | |
70 | for k, v := range s.m { | |
71 | var ok bool | |
72 | if other != nil { | |
73 | _, ok = other.m[k] | |
74 | } | |
75 | if !ok { | |
76 | result.Add(v) | |
77 | } | |
78 | } | |
79 | } | |
80 | ||
81 | return result | |
82 | } | |
83 | ||
84 | // Len is the number of items in the set. | |
85 | func (s *Set) Len() int { | |
86 | if s == nil { | |
87 | return 0 | |
88 | } | |
89 | ||
90 | return len(s.m) | |
91 | } | |
92 | ||
93 | // List returns the list of set elements. | |
94 | func (s *Set) List() []interface{} { | |
95 | if s == nil { | |
96 | return nil | |
97 | } | |
98 | ||
99 | r := make([]interface{}, 0, len(s.m)) | |
100 | for _, v := range s.m { | |
101 | r = append(r, v) | |
102 | } | |
103 | ||
104 | return r | |
105 | } | |
106 | ||
107 | func (s *Set) init() { | |
108 | s.m = make(map[interface{}]interface{}) | |
109 | } |