1//  Copyright (c) 2017 Couchbase, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// 		http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package regexp
16
17type sparseSet struct {
18	dense  []uint
19	sparse []uint
20	size   uint
21}
22
23func newSparseSet(size uint) *sparseSet {
24	return &sparseSet{
25		dense:  make([]uint, size),
26		sparse: make([]uint, size),
27		size:   0,
28	}
29}
30
31func (s *sparseSet) Len() int {
32	return int(s.size)
33}
34
35func (s *sparseSet) Add(ip uint) uint {
36	i := s.size
37	s.dense[i] = ip
38	s.sparse[ip] = i
39	s.size++
40	return i
41}
42
43func (s *sparseSet) Get(i uint) uint {
44	return s.dense[i]
45}
46
47func (s *sparseSet) Contains(ip uint) bool {
48	i := s.sparse[ip]
49	return i < s.size && s.dense[i] == ip
50}
51
52func (s *sparseSet) Clear() {
53	s.size = 0
54}
55