1// Copyright ©2014 The Gonum Authors. 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 uid implements unique ID provision for graphs.
6package uid
7
8import (
9	"math"
10
11	"gonum.org/v1/gonum/graph/internal/set"
12)
13
14// Max is the maximum ID value.
15const Max = math.MaxInt64
16
17// Set implements available ID storage.
18type Set struct {
19	maxID      int64
20	used, free set.Int64s
21}
22
23// NewSet returns a new Set.
24func NewSet() *Set {
25	return &Set{maxID: -1, used: make(set.Int64s), free: make(set.Int64s)}
26}
27
28// NewID returns a new unique ID. The ID returned is not considered used
29// until passed in a call to use.
30func (s *Set) NewID() int64 {
31	for id := range s.free {
32		return id
33	}
34	if s.maxID != math.MaxInt64 {
35		return s.maxID + 1
36	}
37	for id := int64(0); id <= s.maxID; id++ {
38		if !s.used.Has(id) {
39			return id
40		}
41	}
42	panic("unreachable")
43}
44
45// Use adds the id to the used IDs in the Set.
46func (s *Set) Use(id int64) {
47	s.used.Add(id)
48	s.free.Remove(id)
49	if id > s.maxID {
50		s.maxID = id
51	}
52}
53
54// Release frees the id for reuse.
55func (s *Set) Release(id int64) {
56	s.free.Add(id)
57	s.used.Remove(id)
58}
59