}
{ $description "Compares two objects using a chain of intrinsic linear orders such that if two objects are " { $link +eq+ } ", then the next comparator is tried. The comparators are slot-name/comparator pairs." } ;
-HELP: sort-by-slots
+HELP: sort-by
{ $values
{ "seq" sequence } { "sort-specs" "a sequence of accessors ending with a comparator" }
{ "seq'" sequence }
}
} ;
-HELP: split-by-slots
-{ $values
- { "accessor-seqs" "a sequence of sequences of tuple accessors" }
- { "quot" quotation }
-}
-{ $description "Splits a sequence of tuples into a sequence of slices of tuples that have the same values in all slots in the accessor sequence. This word is only useful for splitting a sorted sequence, but is more efficient than partitioning in such a case." } ;
-
-HELP: sort-by
-{ $values
- { "seq" sequence } { "sort-seq" "a sequence of comparators" }
- { "seq'" sequence }
-}
-{ $description "Sorts a sequence by comparing elements by comparators, using subsequent comparators when there is a tie." } ;
-
ARTICLE: "sorting.slots" "Sorting by slots"
"The " { $vocab-link "sorting.slots" } " vocabulary can sort tuples by slot in ascending or descending order, using subsequent slots as tie-breakers." $nl
"Comparing two objects by a sequence of slots:"
{ $subsection compare-slots }
"Sorting a sequence of tuples by a slot/comparator pairs:"
-{ $subsection sort-by-slots }
-"Sorting a sequence by a sequence of comparators:"
-{ $subsection sort-by } ;
+{ $subsection sort-by }
+{ $subsection sort-keys-by }
+{ $subsection sort-values-by } ;
ABOUT: "sorting.slots"
T{ sort-test f 1 1 11 }
T{ sort-test f 2 5 3 }
T{ sort-test f 2 5 2 }
- } { { a>> <=> } { b>> >=< } { c>> <=> } } sort-by-slots
+ } { { a>> <=> } { b>> >=< } { c>> <=> } } sort-by
] unit-test
[
T{ sort-test f 1 1 11 }
T{ sort-test f 2 5 3 }
T{ sort-test f 2 5 2 }
- } { { a>> human<=> } { b>> human>=< } { c>> <=> } } sort-by-slots
+ } { { a>> human<=> } { b>> human>=< } { c>> <=> } } sort-by
] unit-test
-[
- {
- {
- T{ sort-test { a 1 } { b 1 } { c 10 } }
- T{ sort-test { a 1 } { b 1 } { c 11 } }
- }
- { T{ sort-test { a 1 } { b 3 } { c 9 } } }
- {
- T{ sort-test { a 2 } { b 5 } { c 3 } }
- T{ sort-test { a 2 } { b 5 } { c 2 } }
- }
- }
-] [
- {
- T{ sort-test f 1 3 9 }
- T{ sort-test f 1 1 10 }
- T{ sort-test f 1 1 11 }
- T{ sort-test f 2 5 3 }
- T{ sort-test f 2 5 2 }
- }
- { { a>> human<=> } { b>> <=> } } [ sort-by-slots ] keep
- [ but-last-slice ] map split-by-slots [ >array ] map
-] unit-test
-
-: split-test ( seq -- seq' )
- { { a>> } { b>> } } split-by-slots ;
-
-[ split-test ] must-infer
-
[ { } ]
-[ { } { { a>> <=> } { b>> >=< } { c>> <=> } } sort-by-slots ] unit-test
+[ { } { { a>> <=> } { b>> >=< } { c>> <=> } } sort-by ] unit-test
[ { } ]
-[ { } { } sort-by-slots ] unit-test
+[ { } { } sort-by ] unit-test
[
{
T{ sort-test f 6 f f T{ tuple2 f 3 } }
T{ sort-test f 5 f f T{ tuple2 f 3 } }
T{ sort-test f 6 f f T{ tuple2 f 2 } }
- } { { tuple2>> d>> <=> } { a>> <=> } } sort-by-slots
-] unit-test
-
-[
- {
- {
- T{ sort-test
- { a 6 }
- { tuple2 T{ tuple2 { d 1 } } }
- }
- }
- {
- T{ sort-test
- { a 6 }
- { tuple2 T{ tuple2 { d 2 } } }
- }
- }
- {
- T{ sort-test
- { a 5 }
- { tuple2 T{ tuple2 { d 3 } } }
- }
- }
- {
- T{ sort-test
- { a 6 }
- { tuple2 T{ tuple2 { d 3 } } }
- }
- T{ sort-test
- { a 6 }
- { tuple2 T{ tuple2 { d 3 } } }
- }
- }
- {
- T{ sort-test
- { a 5 }
- { tuple2 T{ tuple2 { d 4 } } }
- }
- }
- }
-] [
- {
- T{ sort-test { a 6 } { tuple2 T{ tuple2 { d 1 } } } }
- T{ sort-test { a 6 } { tuple2 T{ tuple2 { d 2 } } } }
- T{ sort-test { a 5 } { tuple2 T{ tuple2 { d 3 } } } }
- T{ sort-test { a 6 } { tuple2 T{ tuple2 { d 3 } } } }
- T{ sort-test { a 6 } { tuple2 T{ tuple2 { d 3 } } } }
- T{ sort-test { a 5 } { tuple2 T{ tuple2 { d 4 } } } }
- } { { tuple2>> d>> } { a>> } } split-by-slots [ >array ] map
+ } { { tuple2>> d>> <=> } { a>> <=> } } sort-by
] unit-test
! Copyright (C) 2009 Slava Pestov, Doug Coleman.
! See http://factorcode.org/license.txt for BSD license.
-USING: combinators.short-circuit fry kernel macros math.order
-sequences words sorting sequences.deep assocs splitting.monotonic
-math ;
+USING: arrays fry kernel math.order sequences sorting ;
IN: sorting.slots
-<PRIVATE
+: execute-comparator ( obj1 obj2 word -- <=>/f )
+ execute( obj1 obj2 -- <=> ) dup +eq+ eq? [ drop f ] when ;
-: short-circuit-comparator ( obj1 obj2 word -- comparator/? )
- execute( obj1 obj2 -- obj3 )
- dup +eq+ eq? [ drop f ] when ;
+: execute-accessor ( obj1 obj2 word -- obj1' obj2' )
+ '[ _ execute( tuple -- value ) ] bi@ ;
-: slot-comparator ( seq -- quot )
- unclip-last-slice [
- [
- '[ [ _ execute( tuple -- value ) ] bi@ ]
- ] map concat
- ] [
- '[ _ call( obj1 obj2 -- obj3 obj4 ) _ short-circuit-comparator ]
- ] bi* ;
-
-PRIVATE>
-
-MACRO: compare-slots ( sort-specs -- quot )
+: compare-slots ( obj1 obj2 sort-specs -- <=> )
#! sort-spec: { accessors comparator }
- [ slot-comparator ] map '[ _ 2|| +eq+ or ] ;
-
-: sort-by-slots ( seq sort-specs -- seq' )
- '[ _ compare-slots ] sort ;
-
-MACRO: compare-seq ( seq -- quot )
- [ '[ _ short-circuit-comparator ] ] map '[ _ 2|| +eq+ or ] ;
+ [
+ dup array? [
+ unclip-last-slice
+ [ [ execute-accessor ] each ] dip
+ ] when execute-comparator
+ ] with with map-find drop +eq+ or ;
-: sort-by ( seq sort-seq -- seq' )
- '[ _ compare-seq ] sort ;
+: sort-by-with ( seq sort-specs quot -- seq' )
+ swap '[ _ bi@ _ compare-slots ] sort ; inline
-: sort-keys-by ( seq sort-seq -- seq' )
- '[ [ first ] bi@ _ compare-seq ] sort ;
+: sort-by ( seq sort-specs -- seq' ) [ ] sort-by-with ;
-: sort-values-by ( seq sort-seq -- seq' )
- '[ [ second ] bi@ _ compare-seq ] sort ;
+: sort-keys-by ( seq sort-seq -- seq' ) [ first ] sort-by-with ;
-MACRO: split-by-slots ( accessor-seqs -- quot )
- [ [ '[ [ _ execute( tuple -- value ) ] bi@ ] ] map concat
- [ = ] compose ] map
- '[ [ _ 2&& ] slice monotonic-slice ] ;
+: sort-values-by ( seq sort-seq -- seq' ) [ second ] sort-by-with ;
projects / factor.git / commitdiff