basis/persistent/deques/deques-docs.factor

   1 ! Copyright (C) 2008 Daniel Ehrenberg
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: help.markup help.syntax kernel sequences ;
   4 IN: persistent.deques
   5
   6 ARTICLE: "persistent.deques" "Persistent deques"
   7 "A deque is a data structure that can be used as both a queue and a stack. That is, there are two ends, the front and the back, and values can be pushed onto and popped off of both ends. These operations take O(1) amortized time and space in a normal usage pattern."
   8 $nl
   9 "This vocabulary provides a deque implementation which is persistent and purely functional: old versions of deques are not modified by operations. Instead, each push and pop operation creates a new deque based off the old one."
  10 $nl
  11 "The class of persistent deques:"
  12 { $subsections deque }
  13 "To create a deque:"
  14 { $subsections
  15     <deque>
  16     sequence>deque
  17 }
  18 "To test if a deque is empty:"
  19 { $subsections deque-empty? }
  20 "To manipulate deques:"
  21 { $subsections
  22     push-front
  23     push-back
  24     pop-front
  25     pop-back
  26     deque>sequence
  27 } ;
  28
  29 HELP: deque
  30 { $class-description "This is the class of persistent (functional) double-ended queues. All deque operations can be done in O(1) amortized time for single-threaded access while maintaining the old version. For more information, see " { $link "persistent.deques" } "." } ;
  31
  32 HELP: <deque>
  33 { $values { "deque" "an empty deque" } }
  34 { $description "Creates an empty deque." } ;
  35
  36 HELP: sequence>deque
  37 { $values { "sequence" sequence } { "deque" deque } }
  38 { $description "Given a sequence, creates a deque containing those elements in the order such that the beginning of the sequence is on the front and the end is on the back." } ;
  39
  40 HELP: deque>sequence
  41 { $values { "deque" deque } { "sequence" sequence } }
  42 { $description "Given a deque, creates a sequence containing those elements, such that the front side of the deque is the beginning of the sequence." } ;
  43
  44 HELP: deque-empty?
  45 { $values { "deque" deque } { "?" "t/f" } }
  46 { $description "Returns true if the deque is empty. This takes constant time." } ;
  47
  48 HELP: push-front
  49 { $values { "deque" deque } { "item" object } { "newdeque" deque } }
  50 { $description "Creates a new deque with the given object pushed onto the front side. This takes constant time." } ;
  51
  52 HELP: push-back
  53 { $values { "deque" deque } { "item" object } { "newdeque" deque } }
  54 { $description "Creates a new deque with the given object pushed onto the back side. This takes constant time." } ;
  55
  56 HELP: pop-front
  57 { $values { "deque" object } { "item" object } { "newdeque" deque } }
  58 { $description "Creates a new deque with the frontmost item removed. This takes amortized constant time with single-threaded access." } ;
  59
  60 HELP: pop-back
  61 { $values { "deque" object } { "item" object } { "newdeque" deque } }
  62 { $description "Creates a new deque with the backmost item removed. This takes amortized constant time with single-threaded access." } ;