wrap_test.go

     1  // Copyright 2022 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 comment
     6  
     7  import (
     8  	"flag"
     9  	"fmt"
    10  	"math/rand"
    11  	"testing"
    12  	"time"
    13  	"unicode/utf8"
    14  )
    15  
    16  var wrapSeed = flag.Int64("wrapseed", 0, "use `seed` for wrap test (default auto-seeds)")
    17  
    18  func TestWrap(t *testing.T) {
    19  	if *wrapSeed == 0 {
    20  		*wrapSeed = time.Now().UnixNano()
    21  	}
    22  	t.Logf("-wrapseed=%#x\n", *wrapSeed)
    23  	r := rand.New(rand.NewSource(*wrapSeed))
    24  
    25  	// Generate words of random length.
    26  	s := "1234567890αβcdefghijklmnopqrstuvwxyz"
    27  	sN := utf8.RuneCountInString(s)
    28  	var words []string
    29  	for i := 0; i < 100; i++ {
    30  		n := 1 + r.Intn(sN-1)
    31  		if n >= 12 {
    32  			n++ // extra byte for β
    33  		}
    34  		if n >= 11 {
    35  			n++ // extra byte for α
    36  		}
    37  		words = append(words, s[:n])
    38  	}
    39  
    40  	for n := 1; n <= len(words) && !t.Failed(); n++ {
    41  		t.Run(fmt.Sprint("n=", n), func(t *testing.T) {
    42  			words := words[:n]
    43  			t.Logf("words: %v", words)
    44  			for max := 1; max < 100 && !t.Failed(); max++ {
    45  				t.Run(fmt.Sprint("max=", max), func(t *testing.T) {
    46  					seq := wrap(words, max)
    47  
    48  					// Compute score for seq.
    49  					start := 0
    50  					score := int64(0)
    51  					if len(seq) == 0 {
    52  						t.Fatalf("wrap seq is empty")
    53  					}
    54  					if seq[0] != 0 {
    55  						t.Fatalf("wrap seq does not start with 0")
    56  					}
    57  					for _, n := range seq[1:] {
    58  						if n <= start {
    59  							t.Fatalf("wrap seq is non-increasing: %v", seq)
    60  						}
    61  						if n > len(words) {
    62  							t.Fatalf("wrap seq contains %d > %d: %v", n, len(words), seq)
    63  						}
    64  						size := -1
    65  						for _, s := range words[start:n] {
    66  							size += 1 + utf8.RuneCountInString(s)
    67  						}
    68  						if n-start == 1 && size >= max {
    69  							// no score
    70  						} else if size > max {
    71  							t.Fatalf("wrap used overlong line %d:%d: %v", start, n, words[start:n])
    72  						} else if n != len(words) {
    73  							score += int64(max-size)*int64(max-size) + wrapPenalty(words[n-1])
    74  						}
    75  						start = n
    76  					}
    77  					if start != len(words) {
    78  						t.Fatalf("wrap seq does not use all words (%d < %d): %v", start, len(words), seq)
    79  					}
    80  
    81  					// Check that score matches slow reference implementation.
    82  					slowSeq, slowScore := wrapSlow(words, max)
    83  					if score != slowScore {
    84  						t.Fatalf("wrap score = %d != wrapSlow score %d\nwrap: %v\nslow: %v", score, slowScore, seq, slowSeq)
    85  					}
    86  				})
    87  			}
    88  		})
    89  	}
    90  }
    91  
    92  // wrapSlow is an O(n²) reference implementation for wrap.
    93  // It returns a minimal-score sequence along with the score.
    94  // It is OK if wrap returns a different sequence as long as that
    95  // sequence has the same score.
    96  func wrapSlow(words []string, max int) (seq []int, score int64) {
    97  	// Quadratic dynamic programming algorithm for line wrapping problem.
    98  	// best[i] tracks the best score possible for words[:i],
    99  	// assuming that for i < len(words) the line breaks after those words.
   100  	// bestleft[i] tracks the previous line break for best[i].
   101  	best := make([]int64, len(words)+1)
   102  	bestleft := make([]int, len(words)+1)
   103  	best[0] = 0
   104  	for i, w := range words {
   105  		if utf8.RuneCountInString(w) >= max {
   106  			// Overlong word must appear on line by itself. No effect on score.
   107  			best[i+1] = best[i]
   108  			continue
   109  		}
   110  		best[i+1] = 1e18
   111  		p := wrapPenalty(w)
   112  		n := -1
   113  		for j := i; j >= 0; j-- {
   114  			n += 1 + utf8.RuneCountInString(words[j])
   115  			if n > max {
   116  				break
   117  			}
   118  			line := int64(n-max)*int64(n-max) + p
   119  			if i == len(words)-1 {
   120  				line = 0 // no score for final line being too short
   121  			}
   122  			s := best[j] + line
   123  			if best[i+1] > s {
   124  				best[i+1] = s
   125  				bestleft[i+1] = j
   126  			}
   127  		}
   128  	}
   129  
   130  	// Recover least weight sequence from bestleft.
   131  	n := 1
   132  	for m := len(words); m > 0; m = bestleft[m] {
   133  		n++
   134  	}
   135  	seq = make([]int, n)
   136  	for m := len(words); m > 0; m = bestleft[m] {
   137  		n--
   138  		seq[n] = m
   139  	}
   140  	return seq, best[len(words)]
   141  }
   142
View as plain text