vendor/golang.org/x/text/internal/stringset/set.go

   1 // Copyright 2016 The Go 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 stringset provides a way to represent a collection of strings
   6 // compactly.
   7 package stringset
   8
   9 import "sort"
  10
  11 // A Set holds a collection of strings that can be looked up by an index number.
  12 type Set struct {
  13         // These fields are exported to allow for code generation.
  14
  15         Data  string
  16         Index []uint16
  17 }
  18
  19 // Elem returns the string with index i. It panics if i is out of range.
  20 func (s *Set) Elem(i int) string {
  21         return s.Data[s.Index[i]:s.Index[i+1]]
  22 }
  23
  24 // Len returns the number of strings in the set.
  25 func (s *Set) Len() int {
  26         return len(s.Index) - 1
  27 }
  28
  29 // Search returns the index of the given string or -1 if it is not in the set.
  30 // The Set must have been created with strings in sorted order.
  31 func Search(s *Set, str string) int {
  32         // TODO: optimize this if it gets used a lot.
  33         n := len(s.Index) - 1
  34         p := sort.Search(n, func(i int) bool {
  35                 return s.Elem(i) >= str
  36         })
  37         if p == n || str != s.Elem(p) {
  38                 return -1
  39         }
  40         return p
  41 }
  42
  43 // A Builder constructs Sets.
  44 type Builder struct {
  45         set   Set
  46         index map[string]int
  47 }
  48
  49 // NewBuilder returns a new and initialized Builder.
  50 func NewBuilder() *Builder {
  51         return &Builder{
  52                 set: Set{
  53                         Index: []uint16{0},
  54                 },
  55                 index: map[string]int{},
  56         }
  57 }
  58
  59 // Set creates the set created so far.
  60 func (b *Builder) Set() Set {
  61         return b.set
  62 }
  63
  64 // Index returns the index for the given string, which must have been added
  65 // before.
  66 func (b *Builder) Index(s string) int {
  67         return b.index[s]
  68 }
  69
  70 // Add adds a string to the index. Strings that are added by a single Add will
  71 // be stored together, unless they match an existing string.
  72 func (b *Builder) Add(ss ...string) {
  73         // First check if the string already exists.
  74         for _, s := range ss {
  75                 if _, ok := b.index[s]; ok {
  76                         continue
  77                 }
  78                 b.index[s] = len(b.set.Index) - 1
  79                 b.set.Data += s
  80                 x := len(b.set.Data)
  81                 if x > 0xFFFF {
  82                         panic("Index too > 0xFFFF")
  83                 }
  84                 b.set.Index = append(b.set.Index, uint16(x))
  85         }
  86 }