core/sorting/sorting-docs.factor

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