...
Run Format

Source file src/sort/sort_test.go

Documentation: sort

     1  // Copyright 2009 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 sort_test
     6  
     7  import (
     8  	"fmt"
     9  	"internal/testenv"
    10  	"math"
    11  	"math/rand"
    12  	. "sort"
    13  	"strconv"
    14  	stringspkg "strings"
    15  	"testing"
    16  )
    17  
    18  var ints = [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
    19  var float64s = [...]float64{74.3, 59.0, math.Inf(1), 238.2, -784.0, 2.3, math.NaN(), math.NaN(), math.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8}
    20  var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
    21  
    22  func TestSortIntSlice(t *testing.T) {
    23  	data := ints
    24  	a := IntSlice(data[0:])
    25  	Sort(a)
    26  	if !IsSorted(a) {
    27  		t.Errorf("sorted %v", ints)
    28  		t.Errorf("   got %v", data)
    29  	}
    30  }
    31  
    32  func TestSortFloat64Slice(t *testing.T) {
    33  	data := float64s
    34  	a := Float64Slice(data[0:])
    35  	Sort(a)
    36  	if !IsSorted(a) {
    37  		t.Errorf("sorted %v", float64s)
    38  		t.Errorf("   got %v", data)
    39  	}
    40  }
    41  
    42  func TestSortStringSlice(t *testing.T) {
    43  	data := strings
    44  	a := StringSlice(data[0:])
    45  	Sort(a)
    46  	if !IsSorted(a) {
    47  		t.Errorf("sorted %v", strings)
    48  		t.Errorf("   got %v", data)
    49  	}
    50  }
    51  
    52  func TestInts(t *testing.T) {
    53  	data := ints
    54  	Ints(data[0:])
    55  	if !IntsAreSorted(data[0:]) {
    56  		t.Errorf("sorted %v", ints)
    57  		t.Errorf("   got %v", data)
    58  	}
    59  }
    60  
    61  func TestFloat64s(t *testing.T) {
    62  	data := float64s
    63  	Float64s(data[0:])
    64  	if !Float64sAreSorted(data[0:]) {
    65  		t.Errorf("sorted %v", float64s)
    66  		t.Errorf("   got %v", data)
    67  	}
    68  }
    69  
    70  func TestStrings(t *testing.T) {
    71  	data := strings
    72  	Strings(data[0:])
    73  	if !StringsAreSorted(data[0:]) {
    74  		t.Errorf("sorted %v", strings)
    75  		t.Errorf("   got %v", data)
    76  	}
    77  }
    78  
    79  func TestSlice(t *testing.T) {
    80  	data := strings
    81  	Slice(data[:], func(i, j int) bool {
    82  		return data[i] < data[j]
    83  	})
    84  	if !SliceIsSorted(data[:], func(i, j int) bool { return data[i] < data[j] }) {
    85  		t.Errorf("sorted %v", strings)
    86  		t.Errorf("   got %v", data)
    87  	}
    88  }
    89  
    90  func TestSortLarge_Random(t *testing.T) {
    91  	n := 1000000
    92  	if testing.Short() {
    93  		n /= 100
    94  	}
    95  	data := make([]int, n)
    96  	for i := 0; i < len(data); i++ {
    97  		data[i] = rand.Intn(100)
    98  	}
    99  	if IntsAreSorted(data) {
   100  		t.Fatalf("terrible rand.rand")
   101  	}
   102  	Ints(data)
   103  	if !IntsAreSorted(data) {
   104  		t.Errorf("sort didn't sort - 1M ints")
   105  	}
   106  }
   107  
   108  func TestReverseSortIntSlice(t *testing.T) {
   109  	data := ints
   110  	data1 := ints
   111  	a := IntSlice(data[0:])
   112  	Sort(a)
   113  	r := IntSlice(data1[0:])
   114  	Sort(Reverse(r))
   115  	for i := 0; i < len(data); i++ {
   116  		if a[i] != r[len(data)-1-i] {
   117  			t.Errorf("reverse sort didn't sort")
   118  		}
   119  		if i > len(data)/2 {
   120  			break
   121  		}
   122  	}
   123  }
   124  
   125  type nonDeterministicTestingData struct {
   126  	r *rand.Rand
   127  }
   128  
   129  func (t *nonDeterministicTestingData) Len() int {
   130  	return 500
   131  }
   132  func (t *nonDeterministicTestingData) Less(i, j int) bool {
   133  	if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
   134  		panic("nondeterministic comparison out of bounds")
   135  	}
   136  	return t.r.Float32() < 0.5
   137  }
   138  func (t *nonDeterministicTestingData) Swap(i, j int) {
   139  	if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
   140  		panic("nondeterministic comparison out of bounds")
   141  	}
   142  }
   143  
   144  func TestNonDeterministicComparison(t *testing.T) {
   145  	// Ensure that sort.Sort does not panic when Less returns inconsistent results.
   146  	// See https://golang.org/issue/14377.
   147  	defer func() {
   148  		if r := recover(); r != nil {
   149  			t.Error(r)
   150  		}
   151  	}()
   152  
   153  	td := &nonDeterministicTestingData{
   154  		r: rand.New(rand.NewSource(0)),
   155  	}
   156  
   157  	for i := 0; i < 10; i++ {
   158  		Sort(td)
   159  	}
   160  }
   161  
   162  func BenchmarkSortString1K(b *testing.B) {
   163  	b.StopTimer()
   164  	unsorted := make([]string, 1<<10)
   165  	for i := range unsorted {
   166  		unsorted[i] = strconv.Itoa(i ^ 0x2cc)
   167  	}
   168  	data := make([]string, len(unsorted))
   169  
   170  	for i := 0; i < b.N; i++ {
   171  		copy(data, unsorted)
   172  		b.StartTimer()
   173  		Strings(data)
   174  		b.StopTimer()
   175  	}
   176  }
   177  
   178  func BenchmarkSortString1K_Slice(b *testing.B) {
   179  	b.StopTimer()
   180  	unsorted := make([]string, 1<<10)
   181  	for i := range unsorted {
   182  		unsorted[i] = strconv.Itoa(i ^ 0x2cc)
   183  	}
   184  	data := make([]string, len(unsorted))
   185  
   186  	for i := 0; i < b.N; i++ {
   187  		copy(data, unsorted)
   188  		b.StartTimer()
   189  		Slice(data, func(i, j int) bool { return data[i] < data[j] })
   190  		b.StopTimer()
   191  	}
   192  }
   193  
   194  func BenchmarkStableString1K(b *testing.B) {
   195  	b.StopTimer()
   196  	unsorted := make([]string, 1<<10)
   197  	for i := range unsorted {
   198  		unsorted[i] = strconv.Itoa(i ^ 0x2cc)
   199  	}
   200  	data := make([]string, len(unsorted))
   201  
   202  	for i := 0; i < b.N; i++ {
   203  		copy(data, unsorted)
   204  		b.StartTimer()
   205  		Stable(StringSlice(data))
   206  		b.StopTimer()
   207  	}
   208  }
   209  
   210  func BenchmarkSortInt1K(b *testing.B) {
   211  	b.StopTimer()
   212  	for i := 0; i < b.N; i++ {
   213  		data := make([]int, 1<<10)
   214  		for i := 0; i < len(data); i++ {
   215  			data[i] = i ^ 0x2cc
   216  		}
   217  		b.StartTimer()
   218  		Ints(data)
   219  		b.StopTimer()
   220  	}
   221  }
   222  
   223  func BenchmarkStableInt1K(b *testing.B) {
   224  	b.StopTimer()
   225  	unsorted := make([]int, 1<<10)
   226  	for i := range unsorted {
   227  		unsorted[i] = i ^ 0x2cc
   228  	}
   229  	data := make([]int, len(unsorted))
   230  	for i := 0; i < b.N; i++ {
   231  		copy(data, unsorted)
   232  		b.StartTimer()
   233  		Stable(IntSlice(data))
   234  		b.StopTimer()
   235  	}
   236  }
   237  
   238  func BenchmarkStableInt1K_Slice(b *testing.B) {
   239  	b.StopTimer()
   240  	unsorted := make([]int, 1<<10)
   241  	for i := range unsorted {
   242  		unsorted[i] = i ^ 0x2cc
   243  	}
   244  	data := make([]int, len(unsorted))
   245  	for i := 0; i < b.N; i++ {
   246  		copy(data, unsorted)
   247  		b.StartTimer()
   248  		SliceStable(data, func(i, j int) bool { return data[i] < data[j] })
   249  		b.StopTimer()
   250  	}
   251  }
   252  
   253  func BenchmarkSortInt64K(b *testing.B) {
   254  	b.StopTimer()
   255  	for i := 0; i < b.N; i++ {
   256  		data := make([]int, 1<<16)
   257  		for i := 0; i < len(data); i++ {
   258  			data[i] = i ^ 0xcccc
   259  		}
   260  		b.StartTimer()
   261  		Ints(data)
   262  		b.StopTimer()
   263  	}
   264  }
   265  
   266  func BenchmarkSortInt64K_Slice(b *testing.B) {
   267  	b.StopTimer()
   268  	for i := 0; i < b.N; i++ {
   269  		data := make([]int, 1<<16)
   270  		for i := 0; i < len(data); i++ {
   271  			data[i] = i ^ 0xcccc
   272  		}
   273  		b.StartTimer()
   274  		Slice(data, func(i, j int) bool { return data[i] < data[j] })
   275  		b.StopTimer()
   276  	}
   277  }
   278  
   279  func BenchmarkStableInt64K(b *testing.B) {
   280  	b.StopTimer()
   281  	for i := 0; i < b.N; i++ {
   282  		data := make([]int, 1<<16)
   283  		for i := 0; i < len(data); i++ {
   284  			data[i] = i ^ 0xcccc
   285  		}
   286  		b.StartTimer()
   287  		Stable(IntSlice(data))
   288  		b.StopTimer()
   289  	}
   290  }
   291  
   292  const (
   293  	_Sawtooth = iota
   294  	_Rand
   295  	_Stagger
   296  	_Plateau
   297  	_Shuffle
   298  	_NDist
   299  )
   300  
   301  const (
   302  	_Copy = iota
   303  	_Reverse
   304  	_ReverseFirstHalf
   305  	_ReverseSecondHalf
   306  	_Sorted
   307  	_Dither
   308  	_NMode
   309  )
   310  
   311  type testingData struct {
   312  	desc        string
   313  	t           *testing.T
   314  	data        []int
   315  	maxswap     int // number of swaps allowed
   316  	ncmp, nswap int
   317  }
   318  
   319  func (d *testingData) Len() int { return len(d.data) }
   320  func (d *testingData) Less(i, j int) bool {
   321  	d.ncmp++
   322  	return d.data[i] < d.data[j]
   323  }
   324  func (d *testingData) Swap(i, j int) {
   325  	if d.nswap >= d.maxswap {
   326  		d.t.Errorf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
   327  		d.t.FailNow()
   328  	}
   329  	d.nswap++
   330  	d.data[i], d.data[j] = d.data[j], d.data[i]
   331  }
   332  
   333  func min(a, b int) int {
   334  	if a < b {
   335  		return a
   336  	}
   337  	return b
   338  }
   339  
   340  func lg(n int) int {
   341  	i := 0
   342  	for 1<<uint(i) < n {
   343  		i++
   344  	}
   345  	return i
   346  }
   347  
   348  func testBentleyMcIlroy(t *testing.T, sort func(Interface), maxswap func(int) int) {
   349  	sizes := []int{100, 1023, 1024, 1025}
   350  	if testing.Short() {
   351  		sizes = []int{100, 127, 128, 129}
   352  	}
   353  	dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
   354  	modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
   355  	var tmp1, tmp2 [1025]int
   356  	for _, n := range sizes {
   357  		for m := 1; m < 2*n; m *= 2 {
   358  			for dist := 0; dist < _NDist; dist++ {
   359  				j := 0
   360  				k := 1
   361  				data := tmp1[0:n]
   362  				for i := 0; i < n; i++ {
   363  					switch dist {
   364  					case _Sawtooth:
   365  						data[i] = i % m
   366  					case _Rand:
   367  						data[i] = rand.Intn(m)
   368  					case _Stagger:
   369  						data[i] = (i*m + i) % n
   370  					case _Plateau:
   371  						data[i] = min(i, m)
   372  					case _Shuffle:
   373  						if rand.Intn(m) != 0 {
   374  							j += 2
   375  							data[i] = j
   376  						} else {
   377  							k += 2
   378  							data[i] = k
   379  						}
   380  					}
   381  				}
   382  
   383  				mdata := tmp2[0:n]
   384  				for mode := 0; mode < _NMode; mode++ {
   385  					switch mode {
   386  					case _Copy:
   387  						for i := 0; i < n; i++ {
   388  							mdata[i] = data[i]
   389  						}
   390  					case _Reverse:
   391  						for i := 0; i < n; i++ {
   392  							mdata[i] = data[n-i-1]
   393  						}
   394  					case _ReverseFirstHalf:
   395  						for i := 0; i < n/2; i++ {
   396  							mdata[i] = data[n/2-i-1]
   397  						}
   398  						for i := n / 2; i < n; i++ {
   399  							mdata[i] = data[i]
   400  						}
   401  					case _ReverseSecondHalf:
   402  						for i := 0; i < n/2; i++ {
   403  							mdata[i] = data[i]
   404  						}
   405  						for i := n / 2; i < n; i++ {
   406  							mdata[i] = data[n-(i-n/2)-1]
   407  						}
   408  					case _Sorted:
   409  						for i := 0; i < n; i++ {
   410  							mdata[i] = data[i]
   411  						}
   412  						// Ints is known to be correct
   413  						// because mode Sort runs after mode _Copy.
   414  						Ints(mdata)
   415  					case _Dither:
   416  						for i := 0; i < n; i++ {
   417  							mdata[i] = data[i] + i%5
   418  						}
   419  					}
   420  
   421  					desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
   422  					d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: maxswap(n)}
   423  					sort(d)
   424  					// Uncomment if you are trying to improve the number of compares/swaps.
   425  					//t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap)
   426  
   427  					// If we were testing C qsort, we'd have to make a copy
   428  					// of the slice and sort it ourselves and then compare
   429  					// x against it, to ensure that qsort was only permuting
   430  					// the data, not (for example) overwriting it with zeros.
   431  					//
   432  					// In go, we don't have to be so paranoid: since the only
   433  					// mutating method Sort can call is TestingData.swap,
   434  					// it suffices here just to check that the final slice is sorted.
   435  					if !IntsAreSorted(mdata) {
   436  						t.Errorf("%s: ints not sorted", desc)
   437  						t.Errorf("\t%v", mdata)
   438  						t.FailNow()
   439  					}
   440  				}
   441  			}
   442  		}
   443  	}
   444  }
   445  
   446  func TestSortBM(t *testing.T) {
   447  	testBentleyMcIlroy(t, Sort, func(n int) int { return n * lg(n) * 12 / 10 })
   448  }
   449  
   450  func TestHeapsortBM(t *testing.T) {
   451  	testBentleyMcIlroy(t, Heapsort, func(n int) int { return n * lg(n) * 12 / 10 })
   452  }
   453  
   454  func TestStableBM(t *testing.T) {
   455  	testBentleyMcIlroy(t, Stable, func(n int) int { return n * lg(n) * lg(n) / 3 })
   456  }
   457  
   458  // This is based on the "antiquicksort" implementation by M. Douglas McIlroy.
   459  // See https://www.cs.dartmouth.edu/~doug/mdmspe.pdf for more info.
   460  type adversaryTestingData struct {
   461  	t         *testing.T
   462  	data      []int // item values, initialized to special gas value and changed by Less
   463  	maxcmp    int   // number of comparisons allowed
   464  	ncmp      int   // number of comparisons (calls to Less)
   465  	nsolid    int   // number of elements that have been set to non-gas values
   466  	candidate int   // guess at current pivot
   467  	gas       int   // special value for unset elements, higher than everything else
   468  }
   469  
   470  func (d *adversaryTestingData) Len() int { return len(d.data) }
   471  
   472  func (d *adversaryTestingData) Less(i, j int) bool {
   473  	if d.ncmp >= d.maxcmp {
   474  		d.t.Fatalf("used %d comparisons sorting adversary data with size %d", d.ncmp, len(d.data))
   475  	}
   476  	d.ncmp++
   477  
   478  	if d.data[i] == d.gas && d.data[j] == d.gas {
   479  		if i == d.candidate {
   480  			// freeze i
   481  			d.data[i] = d.nsolid
   482  			d.nsolid++
   483  		} else {
   484  			// freeze j
   485  			d.data[j] = d.nsolid
   486  			d.nsolid++
   487  		}
   488  	}
   489  
   490  	if d.data[i] == d.gas {
   491  		d.candidate = i
   492  	} else if d.data[j] == d.gas {
   493  		d.candidate = j
   494  	}
   495  
   496  	return d.data[i] < d.data[j]
   497  }
   498  
   499  func (d *adversaryTestingData) Swap(i, j int) {
   500  	d.data[i], d.data[j] = d.data[j], d.data[i]
   501  }
   502  
   503  func newAdversaryTestingData(t *testing.T, size int, maxcmp int) *adversaryTestingData {
   504  	gas := size - 1
   505  	data := make([]int, size)
   506  	for i := 0; i < size; i++ {
   507  		data[i] = gas
   508  	}
   509  	return &adversaryTestingData{t: t, data: data, maxcmp: maxcmp, gas: gas}
   510  }
   511  
   512  func TestAdversary(t *testing.T) {
   513  	const size = 10000            // large enough to distinguish between O(n^2) and O(n*log(n))
   514  	maxcmp := size * lg(size) * 4 // the factor 4 was found by trial and error
   515  	d := newAdversaryTestingData(t, size, maxcmp)
   516  	Sort(d) // This should degenerate to heapsort.
   517  	// Check data is fully populated and sorted.
   518  	for i, v := range d.data {
   519  		if v != i {
   520  			t.Errorf("adversary data not fully sorted")
   521  			t.FailNow()
   522  		}
   523  	}
   524  }
   525  
   526  func TestStableInts(t *testing.T) {
   527  	data := ints
   528  	Stable(IntSlice(data[0:]))
   529  	if !IntsAreSorted(data[0:]) {
   530  		t.Errorf("nsorted %v\n   got %v", ints, data)
   531  	}
   532  }
   533  
   534  type intPairs []struct {
   535  	a, b int
   536  }
   537  
   538  // IntPairs compare on a only.
   539  func (d intPairs) Len() int           { return len(d) }
   540  func (d intPairs) Less(i, j int) bool { return d[i].a < d[j].a }
   541  func (d intPairs) Swap(i, j int)      { d[i], d[j] = d[j], d[i] }
   542  
   543  // Record initial order in B.
   544  func (d intPairs) initB() {
   545  	for i := range d {
   546  		d[i].b = i
   547  	}
   548  }
   549  
   550  // InOrder checks if a-equal elements were not reordered.
   551  func (d intPairs) inOrder() bool {
   552  	lastA, lastB := -1, 0
   553  	for i := 0; i < len(d); i++ {
   554  		if lastA != d[i].a {
   555  			lastA = d[i].a
   556  			lastB = d[i].b
   557  			continue
   558  		}
   559  		if d[i].b <= lastB {
   560  			return false
   561  		}
   562  		lastB = d[i].b
   563  	}
   564  	return true
   565  }
   566  
   567  func TestStability(t *testing.T) {
   568  	n, m := 100000, 1000
   569  	if testing.Short() {
   570  		n, m = 1000, 100
   571  	}
   572  	data := make(intPairs, n)
   573  
   574  	// random distribution
   575  	for i := 0; i < len(data); i++ {
   576  		data[i].a = rand.Intn(m)
   577  	}
   578  	if IsSorted(data) {
   579  		t.Fatalf("terrible rand.rand")
   580  	}
   581  	data.initB()
   582  	Stable(data)
   583  	if !IsSorted(data) {
   584  		t.Errorf("Stable didn't sort %d ints", n)
   585  	}
   586  	if !data.inOrder() {
   587  		t.Errorf("Stable wasn't stable on %d ints", n)
   588  	}
   589  
   590  	// already sorted
   591  	data.initB()
   592  	Stable(data)
   593  	if !IsSorted(data) {
   594  		t.Errorf("Stable shuffled sorted %d ints (order)", n)
   595  	}
   596  	if !data.inOrder() {
   597  		t.Errorf("Stable shuffled sorted %d ints (stability)", n)
   598  	}
   599  
   600  	// sorted reversed
   601  	for i := 0; i < len(data); i++ {
   602  		data[i].a = len(data) - i
   603  	}
   604  	data.initB()
   605  	Stable(data)
   606  	if !IsSorted(data) {
   607  		t.Errorf("Stable didn't sort %d ints", n)
   608  	}
   609  	if !data.inOrder() {
   610  		t.Errorf("Stable wasn't stable on %d ints", n)
   611  	}
   612  }
   613  
   614  var countOpsSizes = []int{1e2, 3e2, 1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6}
   615  
   616  func countOps(t *testing.T, algo func(Interface), name string) {
   617  	sizes := countOpsSizes
   618  	if testing.Short() {
   619  		sizes = sizes[:5]
   620  	}
   621  	if !testing.Verbose() {
   622  		t.Skip("Counting skipped as non-verbose mode.")
   623  	}
   624  	for _, n := range sizes {
   625  		td := testingData{
   626  			desc:    name,
   627  			t:       t,
   628  			data:    make([]int, n),
   629  			maxswap: 1<<31 - 1,
   630  		}
   631  		for i := 0; i < n; i++ {
   632  			td.data[i] = rand.Intn(n / 5)
   633  		}
   634  		algo(&td)
   635  		t.Logf("%s %8d elements: %11d Swap, %10d Less", name, n, td.nswap, td.ncmp)
   636  	}
   637  }
   638  
   639  func TestCountStableOps(t *testing.T) { countOps(t, Stable, "Stable") }
   640  func TestCountSortOps(t *testing.T)   { countOps(t, Sort, "Sort  ") }
   641  
   642  func bench(b *testing.B, size int, algo func(Interface), name string) {
   643  	if stringspkg.HasSuffix(testenv.Builder(), "-race") && size > 1e4 {
   644  		b.Skip("skipping slow benchmark on race builder")
   645  	}
   646  	b.StopTimer()
   647  	data := make(intPairs, size)
   648  	x := ^uint32(0)
   649  	for i := 0; i < b.N; i++ {
   650  		for n := size - 3; n <= size+3; n++ {
   651  			for i := 0; i < len(data); i++ {
   652  				x += x
   653  				x ^= 1
   654  				if int32(x) < 0 {
   655  					x ^= 0x88888eef
   656  				}
   657  				data[i].a = int(x % uint32(n/5))
   658  			}
   659  			data.initB()
   660  			b.StartTimer()
   661  			algo(data)
   662  			b.StopTimer()
   663  			if !IsSorted(data) {
   664  				b.Errorf("%s did not sort %d ints", name, n)
   665  			}
   666  			if name == "Stable" && !data.inOrder() {
   667  				b.Errorf("%s unstable on %d ints", name, n)
   668  			}
   669  		}
   670  	}
   671  }
   672  
   673  func BenchmarkSort1e2(b *testing.B)   { bench(b, 1e2, Sort, "Sort") }
   674  func BenchmarkStable1e2(b *testing.B) { bench(b, 1e2, Stable, "Stable") }
   675  func BenchmarkSort1e4(b *testing.B)   { bench(b, 1e4, Sort, "Sort") }
   676  func BenchmarkStable1e4(b *testing.B) { bench(b, 1e4, Stable, "Stable") }
   677  func BenchmarkSort1e6(b *testing.B)   { bench(b, 1e6, Sort, "Sort") }
   678  func BenchmarkStable1e6(b *testing.B) { bench(b, 1e6, Stable, "Stable") }
   679  

View as plain text