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