sort.go

Documentation: cuelang.org/go/pkg/list

     1  // Copyright 2018 The CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  // Copyright 2018 The Go Authors. All rights reserved.
    16  // Use of this source code is governed by a BSD-style
    17  // license that can be found in the LICENSE file.
    18  
    19  package list
    20  
    21  import (
    22  	"sort"
    23  
    24  	"cuelang.org/go/cue"
    25  	"cuelang.org/go/internal/core/adt"
    26  	"cuelang.org/go/internal/types"
    27  )
    28  
    29  // valueSorter defines a sort.Interface; implemented in cue/builtinutil.go.
    30  type valueSorter struct {
    31  	ctx *adt.OpContext
    32  	a   []cue.Value
    33  	err error
    34  
    35  	cmp  *adt.Vertex
    36  	less *adt.Vertex
    37  	x    *adt.Vertex
    38  	y    *adt.Vertex
    39  }
    40  
    41  func (s *valueSorter) ret() ([]cue.Value, error) {
    42  	if s.err != nil {
    43  		return nil, s.err
    44  	}
    45  	// The input slice is already a copy and that we can modify it safely.
    46  	return s.a, nil
    47  }
    48  
    49  func (s *valueSorter) Len() int      { return len(s.a) }
    50  func (s *valueSorter) Swap(i, j int) { s.a[i], s.a[j] = s.a[j], s.a[i] }
    51  func (s *valueSorter) Less(i, j int) bool {
    52  	if s.err != nil {
    53  		return false
    54  	}
    55  	var x, y types.Value
    56  	s.a[i].Core(&x)
    57  	s.a[j].Core(&y)
    58  
    59  	// Save the state of all relevant arcs and restore later for the
    60  	// next comparison.
    61  	saveCmp := *s.cmp
    62  	saveLess := *s.less
    63  	saveX := *s.x
    64  	saveY := *s.y
    65  
    66  	for _, c := range x.V.Conjuncts {
    67  		s.x.AddConjunct(c)
    68  	}
    69  	for _, c := range y.V.Conjuncts {
    70  		s.y.AddConjunct(c)
    71  	}
    72  
    73  	// TODO(perf): if we can determine that the comparator values for
    74  	// x and y are idempotent (no arcs and a basevalue being top or
    75  	// a struct or list marker), then we do not need to reevaluate the input.
    76  	// In that case, we can use the below code instead of the above two loops
    77  	// setting the conjuncts. This may improve performance significantly.
    78  	//
    79  	// s.x.BaseValue = x.V.BaseValue
    80  	// s.x.Arcs = x.V.Arcs
    81  	// s.y.BaseValue = y.V.BaseValue
    82  	// s.y.Arcs = y.V.Arcs
    83  
    84  	s.less.Finalize(s.ctx)
    85  	isLess := s.ctx.BoolValue(s.less)
    86  	if b := s.less.Err(s.ctx); b != nil && s.err == nil {
    87  		s.err = b.Err
    88  		return true
    89  	}
    90  
    91  	*s.less = saveLess
    92  	*s.cmp = saveCmp
    93  	*s.x = saveX
    94  	*s.y = saveY
    95  
    96  	return isLess
    97  }
    98  
    99  var less = cue.ParsePath("less")
   100  
   101  func makeValueSorter(list []cue.Value, cmp cue.Value) (s valueSorter) {
   102  	if v := cmp.LookupPath(less); !v.Exists() {
   103  		return valueSorter{err: v.Err()}
   104  	}
   105  
   106  	var v types.Value
   107  	cmp.Core(&v)
   108  	ctx := adt.NewContext(v.R, v.V)
   109  
   110  	n := &adt.Vertex{
   111  		Label:     v.V.Label,
   112  		Parent:    v.V.Parent,
   113  		Conjuncts: v.V.Conjuncts,
   114  	}
   115  	n.CompleteArcs(ctx)
   116  
   117  	s = valueSorter{
   118  		a:    list,
   119  		ctx:  ctx,
   120  		cmp:  n,
   121  		less: getArc(ctx, n, "less"),
   122  		x:    getArc(ctx, n, "x"),
   123  		y:    getArc(ctx, n, "y"),
   124  	}
   125  
   126  	// TODO(perf): see comment in the Less method. If we can determine
   127  	// the conjuncts for x and y are idempotent, we can pre finalize here and
   128  	// ignore the values in the Less method.
   129  	// s.x.UpdateStatus(adt.Finalized)
   130  	// s.y.UpdateStatus(adt.Finalized)
   131  
   132  	return s
   133  }
   134  
   135  // Sort sorts data while keeping the original order of equal elements.
   136  // It does O(n*log(n)) comparisons.
   137  //
   138  // cmp is a struct of the form {T: _, x: T, y: T, less: bool}, where
   139  // less should reflect x < y.
   140  //
   141  // Example:
   142  //
   143  //	Sort([2, 3, 1], list.Ascending)
   144  //
   145  //	Sort([{a: 2}, {a: 3}, {a: 1}], {x: {}, y: {}, less: x.a < y.a})
   146  func Sort(list []cue.Value, cmp cue.Value) (sorted []cue.Value, err error) {
   147  	s := makeValueSorter(list, cmp)
   148  
   149  	// The input slice is already a copy and that we can modify it safely.
   150  	sort.Stable(&s)
   151  	return s.ret()
   152  }
   153  
   154  func getArc(ctx *adt.OpContext, v *adt.Vertex, s string) *adt.Vertex {
   155  	f := ctx.StringLabel(s)
   156  	arc, _ := v.GetArc(ctx, f, 0)
   157  	return arc
   158  }
   159  
   160  // Deprecated: use Sort, which is always stable
   161  func SortStable(list []cue.Value, cmp cue.Value) (sorted []cue.Value, err error) {
   162  	s := makeValueSorter(list, cmp)
   163  	sort.Stable(&s)
   164  	return s.ret()
   165  }
   166  
   167  // Strings sorts a list of strings in increasing order.
   168  func SortStrings(a []string) []string {
   169  	sort.Strings(a)
   170  	return a
   171  }
   172  
   173  // IsSorted tests whether a list is sorted.
   174  //
   175  // See Sort for an example comparator.
   176  func IsSorted(list []cue.Value, cmp cue.Value) bool {
   177  	s := makeValueSorter(list, cmp)
   178  	return sort.IsSorted(&s)
   179  }
   180  
   181  // IsSortedStrings tests whether a list is a sorted lists of strings.
   182  func IsSortedStrings(a []string) bool {
   183  	return sort.StringsAreSorted(a)
   184  }
   185
View as plain text