core/sorting/sorting-docs.factor

   1 USING: sorting help.markup help.syntax kernel words math
   2 sequences ;
   3
   4 ARTICLE: "sequences-sorting" "Sorting and binary search"
   5 "Sorting and binary search combinators all take comparator quotations with stack effect " { $snippet "( elt1 elt2 -- n )" } " that order the two given elements and output a value whose sign denotes the result:"
   6 { $list
   7     { "positive - indicates that " { $snippet "elt1" } " follows " { $snippet "elt2" } }
   8     { "zero - indicates that " { $snippet "elt1" } " is ordered equivalently to " { $snippet "elt2" } }
   9     { "negative - indicates that " { $snippet "elt1" } " precedes " { $snippet "elt2" } }
  10 }
  11 "Sorting a sequence with a custom comparator:"
  12 { $subsection sort }
  13 "Sorting a sequence with common comparators:"
  14 { $subsection natural-sort }
  15 { $subsection sort-keys }
  16 { $subsection sort-values }
  17 "Binary search:"
  18 { $subsection binsearch }
  19 { $subsection binsearch* } ;
  20
  21 HELP: sort
  22 { $values { "seq" "a sequence" } { "quot" "a comparator quotation" } { "sortedseq" "a new sorted sequence" } }
  23 { $description "Sorts the elements into a new sequence of the same class as " { $snippet "seq" } "." } ;
  24
  25 HELP: sort-keys
  26 { $values { "seq" "an alist" } { "sortedseq" "a new sorted sequence" } }
  27 { $description "Sorts the elements comparing first elements of pairs using the " { $link <=> } " word." } ;
  28
  29 HELP: sort-values
  30 { $values { "seq" "an alist" } { "sortedseq" "a new sorted sequence" } }
  31 { $description "Sorts the elements comparing second elements of pairs using the " { $link <=> } " word." } ;
  32
  33 HELP: natural-sort
  34 { $values { "seq" "a sequence of real numbers" } { "sortedseq" "a new sorted sequence" } }
  35 { $description "Sorts a sequence of objects in natural order using the " { $link <=> } " word." } ;
  36
  37 HELP: sort-pair
  38 { $values { "a" object } { "b" object } { "c" object } { "d" object } }
  39 { $description "If " { $snippet "a" } " is greater than " { $snippet "b" } ", exchanges " { $snippet "a" } " with " { $snippet "b" } "." } ;
  40
  41 HELP: midpoint@
  42 { $values { "seq" "a sequence" } { "n" integer } }
  43 { $description "Outputs the index of the midpoint of " { $snippet "seq" } "." } ;
  44
  45 HELP: midpoint
  46 { $values { "seq" "a sequence" } { "elt" object } }
  47 { $description "Outputs the element at the midpoint of a sequence." } ;
  48
  49 HELP: partition
  50 { $values { "seq" "a sequence" } { "n" integer } { "slice" slice } }
  51 { $description "Outputs a slice of the first or second half of the sequence, respectively, depending on the integer's sign." } ;
  52
  53 HELP: binsearch
  54 { $values { "elt" object } { "seq" "a sorted sequence" } { "quot" "a comparator quotation" } { "i" "the index of the search result" } }
  55 { $description "Given a sequence that is sorted with respect to the " { $snippet "quot" } " comparator, searches for an element equal to " { $snippet "elt" } ", or failing that, the greatest element smaller than " { $snippet "elt" } ". Comparison is performed with " { $snippet "quot" } "."
  56 $nl
  57 "Outputs f if the sequence is empty. If the sequence has at least one element, this word always outputs a valid index." } ;
  58
  59 HELP: binsearch*
  60 { $values { "elt" object } { "seq" "a sorted sequence" } { "quot" "a comparator quotation" } { "result" "the search result" } }
  61 { $description "Variant of " { $link binsearch } " which outputs the found element rather than its index in the sequence."
  62 $nl
  63 "Outputs " { $link f } " if the sequence is empty. If the sequence has at least one element, this word always outputs a sequence element." } ;