basis/persistent/deques/deques-docs.factor

   1 ! Copyright (C) 2008 Daniel Ehrenberg
   2 ! See http://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 { $subsection deque }
  13 "To create a deque:"
  14 { $subsection <deque> }
  15 { $subsection sequence>deque }
  16 "To test if a deque is empty:"
  17 { $subsection deque-empty? }
  18 "To manipulate deques:"
  19 { $subsection push-front }
  20 { $subsection push-back }
  21 { $subsection pop-front }
  22 { $subsection pop-back }
  23 { $subsection deque>sequence } ;
  24
  25 HELP: deque
  26 { $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" } "." } ;
  27
  28 HELP: <deque>
  29 { $values { "deque" "an empty deque" } }
  30 { $description "Creates an empty deque." } ;
  31
  32 HELP: sequence>deque
  33 { $values { "sequence" sequence } { "deque" deque } }
  34 { $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." } ;
  35
  36 HELP: deque>sequence
  37 { $values { "deque" deque } { "sequence" sequence } }
  38 { $description "Given a deque, creates a sequence containing those elements, such that the front side of the deque is the beginning of the sequence." } ;
  39
  40 HELP: deque-empty?
  41 { $values { "deque" deque } { "?" "t/f" } }
  42 { $description "Returns true if the deque is empty. This takes constant time." } ;
  43
  44 HELP: push-front
  45 { $values { "deque" deque } { "item" object } { "newdeque" deque } }
  46 { $description "Creates a new deque with the given object pushed onto the front side. This takes constant time." } ;
  47
  48 HELP: push-back
  49 { $values { "deque" deque } { "item" object } { "newdeque" deque } }
  50 { $description "Creates a new deque with the given object pushed onto the back side. This takes constant time." } ;
  51
  52 HELP: pop-front
  53 { $values { "deque" object } { "item" object } { "newdeque" deque } }
  54 { $description "Creates a new deque with the frontmost item removed. This takes amortized constant time with single-threaded access." } ;
  55
  56 HELP: pop-back
  57 { $values { "deque" object } { "item" object } { "newdeque" deque } }
  58 { $description "Creates a new deque with the backmost item removed. This takes amortized constant time with single-threaded access." } ;