set.go

Documentation: golang.org/x/text/internal/stringset

     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  }
    87
View as plain text