Skip to content

Commit bdcda9a

Browse files
jbduncankortschak
jbduncan
authored and
kortschak
committed
graph: use slices package for sorting and reversing slices
1 parent a9b228e commit bdcda9a

29 files changed

+225
-296
lines changed

‎graph/coloring/coloring.go

+2-1
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ package coloring
99

1010
import (
1111
"errors"
12+
"slices"
1213
"sort"
1314

1415
"golang.org/x/exp/rand"
@@ -31,7 +32,7 @@ func Sets(colors map[int64]int) map[int][]int64 {
3132
sets[c] = append(sets[c], id)
3233
}
3334
for _, s := range sets {
34-
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
35+
slices.Sort(s)
3536
}
3637
return sets
3738
}

‎graph/community/louvain_common.go

+2-2
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ package community
66

77
import (
88
"fmt"
9-
"sort"
9+
"slices"
1010

1111
"golang.org/x/exp/rand"
1212

@@ -347,7 +347,7 @@ func newSlice(s set.Ints[int]) *slice {
347347
for i := range s {
348348
elems = append(elems, i)
349349
}
350-
sort.Ints(elems)
350+
slices.Sort(elems)
351351
return &slice{elems: elems}
352352
}
353353

‎graph/community/louvain_directed.go

+2-2
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ package community
66

77
import (
88
"math"
9-
"sort"
9+
"slices"
1010

1111
"golang.org/x/exp/rand"
1212

@@ -617,7 +617,7 @@ func (l *directedLocalMover) deltaQ(n graph.Node) (deltaQ float64, dst int, src
617617
for i := range connected {
618618
candidates = append(candidates, i)
619619
}
620-
sort.Ints(candidates)
620+
slices.Sort(candidates)
621621

622622
// Calculate the highest modularity gain
623623
// from moving into another community and

‎graph/community/louvain_directed_multiplex_test.go

+1-2
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,6 @@ import (
99
"math"
1010
"reflect"
1111
"slices"
12-
"sort"
1312
"testing"
1413

1514
"golang.org/x/exp/rand"
@@ -609,7 +608,7 @@ func TestLouvainDirectedMultiplex(t *testing.T) {
609608
}
610609

611610
// Recovery of Q values is reversed.
612-
if slices.Reverse(qs); !sort.Float64sAreSorted(qs) {
611+
if slices.Reverse(qs); !slices.IsSorted(qs) {
613612
t.Errorf("Q values not monotonically increasing: %.5v", qs)
614613
}
615614
}

‎graph/community/louvain_directed_test.go

+1-2
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,6 @@ import (
88
"math"
99
"reflect"
1010
"slices"
11-
"sort"
1211
"testing"
1312

1413
"golang.org/x/exp/rand"
@@ -632,7 +631,7 @@ func testModularizeDirected(t *testing.T, test communityDirectedQTest, g graph.D
632631
}
633632

634633
// Recovery of Q values is reversed.
635-
if slices.Reverse(qs); !sort.Float64sAreSorted(qs) {
634+
if slices.Reverse(qs); !slices.IsSorted(qs) {
636635
t.Errorf("Q values not monotonically increasing: %.5v", qs)
637636
}
638637
}

‎graph/community/louvain_undirected.go

+2-2
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ package community
66

77
import (
88
"math"
9-
"sort"
9+
"slices"
1010

1111
"golang.org/x/exp/rand"
1212

@@ -554,7 +554,7 @@ func (l *undirectedLocalMover) deltaQ(n graph.Node) (deltaQ float64, dst int, sr
554554
for i := range connected {
555555
candidates = append(candidates, i)
556556
}
557-
sort.Ints(candidates)
557+
slices.Sort(candidates)
558558

559559
// Calculate the highest modularity gain
560560
// from moving into another community and

‎graph/community/louvain_undirected_multiplex_test.go

+1-2
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,6 @@ import (
99
"math"
1010
"reflect"
1111
"slices"
12-
"sort"
1312
"testing"
1413

1514
"golang.org/x/exp/rand"
@@ -578,7 +577,7 @@ func TestLouvainMultiplex(t *testing.T) {
578577
}
579578

580579
// Recovery of Q values is reversed.
581-
if slices.Reverse(qs); !sort.Float64sAreSorted(qs) {
580+
if slices.Reverse(qs); !slices.IsSorted(qs) {
582581
t.Errorf("Q values not monotonically increasing: %.5v", qs)
583582
}
584583
}

‎graph/community/louvain_undirected_test.go

+1-2
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,6 @@ import (
88
"math"
99
"reflect"
1010
"slices"
11-
"sort"
1211
"testing"
1312

1413
"golang.org/x/exp/rand"
@@ -695,7 +694,7 @@ func testModularizeUndirected(t *testing.T, test communityUndirectedQTest, g gra
695694
}
696695

697696
// Recovery of Q values is reversed.
698-
if slices.Reverse(qs); !sort.Float64sAreSorted(qs) {
697+
if slices.Reverse(qs); !slices.IsSorted(qs) {
699698
t.Errorf("Q values not monotonically increasing: %.5v", qs)
700699
}
701700
}

‎graph/encoding/graphql/decode_test.go

+2-2
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ import (
99
"errors"
1010
"fmt"
1111
"os/exec"
12-
"sort"
12+
"slices"
1313
"strconv"
1414
"strings"
1515
"testing"
@@ -211,7 +211,7 @@ func (a attributes) Attributes() []encoding.Attribute {
211211
for k := range a {
212212
keys = append(keys, k)
213213
}
214-
sort.Strings(keys)
214+
slices.Sort(keys)
215215
attr := make([]encoding.Attribute, 0, len(keys))
216216
for _, k := range keys {
217217
v := a[k]

‎graph/formats/rdf/debug.go

+2-2
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ package rdf
1010
import (
1111
"fmt"
1212
"os"
13-
"sort"
13+
"slices"
1414
"strings"
1515
"text/tabwriter"
1616
)
@@ -47,7 +47,7 @@ func (d debugger) logHashes(depth int, hashes map[string][]byte, size int) {
4747
keys[i] = k
4848
i++
4949
}
50-
sort.Strings(keys)
50+
slices.Sort(keys)
5151
w := tabwriter.NewWriter(os.Stderr, 0, 4, 8, ' ', 0)
5252
for _, k := range keys {
5353
fmt.Fprintf(w, prefix+"%s\t%0*x\n", k, 2*size, hashes[k])

‎graph/formats/rdf/graph_test.go

+3-3
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ package rdf_test
77
import (
88
"io"
99
"math"
10-
"sort"
10+
"slices"
1111
"strings"
1212
"testing"
1313

@@ -230,7 +230,7 @@ func TestRemoveStatement(t *testing.T) {
230230
for it.Next() {
231231
gotStatements = append(gotStatements, it.Statement().String())
232232
}
233-
sort.Strings(gotStatements)
233+
slices.Sort(gotStatements)
234234

235235
got := strings.TrimSpace(strings.Join(gotStatements, "\n"))
236236
want := strings.TrimSpace(test.want)
@@ -349,7 +349,7 @@ func TestRemoveTerm(t *testing.T) {
349349
for it.Next() {
350350
gotStatements = append(gotStatements, it.Statement().String())
351351
}
352-
sort.Strings(gotStatements)
352+
slices.Sort(gotStatements)
353353

354354
got := strings.TrimSpace(strings.Join(gotStatements, "\n"))
355355
want := strings.TrimSpace(test.want)

‎graph/formats/rdf/iso_canonical.go

+20-36
Original file line numberDiff line numberDiff line change
@@ -6,10 +6,14 @@ package rdf
66

77
import (
88
"bytes"
9+
"cmp"
910
"errors"
1011
"fmt"
1112
"hash"
13+
"slices"
1214
"sort"
15+
16+
"gonum.org/v1/gonum/internal/order"
1317
)
1418

1519
// See "Canonical Forms for Isomorphic and Equivalent RDF Graphs: Algorithms
@@ -53,7 +57,7 @@ func lexicalHashes(dst [][]byte, hashes map[string][]byte) {
5357
dst[i] = s
5458
i++
5559
}
56-
sort.Sort(lexical(dst))
60+
order.BySliceValues(dst)
5761
}
5862

5963
// IsoCanonicalHashes returns a mapping between the nodes of the RDF graph
@@ -185,7 +189,7 @@ func C14n(dst, src []*Statement, terms map[string]map[string]bool) ([]*Statement
185189
blanks[i] = h
186190
i++
187191
}
188-
sort.Strings(blanks)
192+
slices.Sort(blanks)
189193

190194
c14n := make(map[string]string)
191195
for i, b := range blanks {
@@ -218,7 +222,7 @@ func C14n(dst, src []*Statement, terms map[string]map[string]bool) ([]*Statement
218222
n.Object = Term{Value: translate(s.Object.Value, c14n)}
219223
n.Label = Term{Value: translate(s.Label.Value, c14n)}
220224
}
221-
sort.Sort(c14nStatements(dst))
225+
sortC14nStatements(dst)
222226

223227
return dst, nil
224228
}
@@ -230,33 +234,20 @@ func translate(term string, mapping map[string]string) string {
230234
return term
231235
}
232236

233-
type c14nStatements []*Statement
237+
func sortC14nStatements(statements []*Statement) {
238+
slices.SortFunc(statements, func(a, b *Statement) int {
239+
if n := cmp.Compare(a.Subject.Value, b.Subject.Value); n != 0 {
240+
return n
241+
}
234242

235-
func (s c14nStatements) Len() int { return len(s) }
236-
func (s c14nStatements) Less(i, j int) bool {
237-
si := s[i]
238-
sj := s[j]
239-
switch {
240-
case si.Subject.Value < sj.Subject.Value:
241-
return true
242-
case si.Subject.Value > sj.Subject.Value:
243-
return false
244-
}
245-
switch { // Always IRI.
246-
case si.Predicate.Value < sj.Predicate.Value:
247-
return true
248-
case si.Predicate.Value > sj.Predicate.Value:
249-
return false
250-
}
251-
switch {
252-
case si.Object.Value < sj.Object.Value:
253-
return true
254-
case si.Object.Value > sj.Object.Value:
255-
return false
256-
}
257-
return si.Label.Value < sj.Label.Value
243+
// Always IRI.
244+
if n := cmp.Compare(a.Predicate.Value, b.Predicate.Value); n != 0 {
245+
return n
246+
}
247+
248+
return cmp.Compare(a.Object.Value, b.Object.Value)
249+
})
258250
}
259-
func (s c14nStatements) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
260251

261252
// hashBNodes returns the hashed blank nodes of the graph described by statements
262253
// using the provided hash function. Hashes are initialised with zero.
@@ -497,20 +488,13 @@ func (b hashBag) add(term string, hash []byte) {
497488
// state and returns the hash.
498489
func (b hashBag) sum(term string) []byte {
499490
p := b.hashesFor[term]
500-
sort.Sort(lexical(p))
491+
order.BySliceValues(p)
501492
h := hashTuple(b.hash, p...)
502493
b.hashesFor[term] = b.hashesFor[term][:1]
503494
b.hashesFor[term][0] = h
504495
return h
505496
}
506497

507-
// lexical implements lexical sorting of [][]byte.
508-
type lexical [][]byte
509-
510-
func (b lexical) Len() int { return len(b) }
511-
func (b lexical) Less(i, j int) bool { return string(b[i]) < string(b[j]) }
512-
func (b lexical) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
513-
514498
// hashTuple returns the h hash of the concatenation of t.
515499
func hashTuple(h hash.Hash, t ...[]byte) []byte {
516500
h.Reset()

‎graph/formats/rdf/iso_canonical_example_test.go

+3-3
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ import (
99
"fmt"
1010
"log"
1111
"os"
12-
"sort"
12+
"slices"
1313
"strings"
1414
"text/tabwriter"
1515

@@ -76,7 +76,7 @@ _:greet <l:is> "hola"@es .
7676
blanks = append(blanks, k)
7777
}
7878
}
79-
sort.Strings(blanks)
79+
slices.Sort(blanks)
8080

8181
if len(blanks) == 0 {
8282
fmt.Println("No blank nodes.")
@@ -163,7 +163,7 @@ _:c1 <ex:r> _:d1 .
163163
blanks = append(blanks, k)
164164
}
165165
}
166-
sort.Strings(blanks)
166+
slices.Sort(blanks)
167167

168168
if len(blanks) == 0 {
169169
fmt.Println("No blank nodes.")

0 commit comments

Comments
 (0)