issue72090.go

     1  // build
     2  
     3  // Copyright 2025 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package main
     8  
     9  import (
    10  	"iter"
    11  )
    12  
    13  type leafSet map[rune]struct{}
    14  
    15  type branchMap map[rune]*node
    16  
    17  func (bm branchMap) findOrCreateBranch(r rune) *node {
    18  	if _, ok := bm[r]; !ok {
    19  		bm[r] = newNode()
    20  	}
    21  	return bm[r]
    22  }
    23  
    24  func (bm branchMap) allSuffixes() iter.Seq[string] {
    25  	return func(yield func(string) bool) {
    26  		for r, n := range bm {
    27  			for s := range n.allStrings() {
    28  				if !yield(string(r) + s) {
    29  					return
    30  				}
    31  			}
    32  		}
    33  	}
    34  }
    35  
    36  type node struct {
    37  	leafSet
    38  	branchMap
    39  }
    40  
    41  func newNode() *node {
    42  	return &node{make(leafSet), make(branchMap)}
    43  }
    44  
    45  func (n *node) add(s []rune) {
    46  	switch len(s) {
    47  	case 0:
    48  		return
    49  	case 1:
    50  		n.leafSet[s[0]] = struct{}{}
    51  	default:
    52  		n.branchMap.findOrCreateBranch(s[0]).add(s[1:])
    53  	}
    54  }
    55  
    56  func (n *node) addString(s string) {
    57  	n.add([]rune(s))
    58  }
    59  
    60  func (n *node) allStrings() iter.Seq[string] {
    61  	return func(yield func(string) bool) {
    62  		for s := range n.leafSet {
    63  			if !yield(string(s)) {
    64  				return
    65  			}
    66  		}
    67  		for r, n := range n.branchMap {
    68  			for s := range n.allSuffixes() {
    69  				if !yield(string(r) + s) {
    70  					return
    71  				}
    72  			}
    73  		}
    74  	}
    75  }
    76  
    77  func main() {
    78  	root := newNode()
    79  	for _, s := range []string{"foo", "bar", "baz", "a", "b", "c", "hello", "world"} {
    80  		root.addString(s)
    81  	}
    82  	for s := range root.allStrings() {
    83  		println(s)
    84  	}
    85  }
    86
View as plain text