taldir

Directory service to resolve wallet mailboxes by messenger addresses
Log | Files | Refs | Submodules | README | LICENSE

set.go (2083B)

      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 }