1 // Copyright 2019 Google LLC. All Rights Reserved. 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 15 package ctpolicy 16 17 import ( 18 "fmt" 19 "math/rand" 20 ) 21 22 // weightedRandomSample picks an item from the weighted set and returns it. 23 // Follows weight distribution provided and ignores items whose weight is 0. 24 // If it's not possible (e.g. all items have 0 weights), returns error. 25 // Expects all weights to be non-negative, otherwise returns error. 26 func weightedRandomSample(weights map[string]float32) (string, error) { 27 var sum float32 28 for itemName, w := range weights { 29 if w < 0.0 { 30 return "", fmt.Errorf("weightedRandomSample got negative weight %v for item %v, all weights should be non-negative", w, itemName) 31 } 32 sum += w 33 } 34 r := rand.Float32() * sum 35 for itemName, w := range weights { 36 if w == 0.0 { 37 continue 38 } 39 r -= w 40 if r < 0.0 { 41 return itemName, nil 42 } 43 } 44 return "", fmt.Errorf("weightedRandomSample couldn't pick any item") 45 } 46