basis/persistent/deques/deques.factor

   1 ! Copyright (C) 2008 Daniel Ehrenberg
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel accessors math lists sequences combinators.short-circuit ;
   4 IN: persistent.deques
   5
   6 ! Amortized O(1) push/pop on both ends for single-threaded access
   7 ! In a pathological case, if there are m modified versions from the
   8 !   same source, it could take O(m) amortized time per update.
   9
  10 <PRIVATE
  11 : split-reverse ( list -- back-reversed front )
  12     dup llength 2/ lcut lreverse swap ;
  13 PRIVATE>
  14
  15 TUPLE: deque { front read-only } { back read-only } ;
  16 : <deque> ( -- deque )
  17     T{ deque f +nil+ +nil+ } ;
  18
  19 <PRIVATE
  20 : flip ( deque -- newdeque )
  21     [ back>> ] [ front>> ] bi deque boa ;
  22
  23 : flipped ( deque quot -- newdeque )
  24     [ flip ] dip call flip ; inline
  25 PRIVATE>
  26
  27 : deque-empty? ( deque -- ? )
  28     { [ front>> nil? ] [ back>> nil? ] } 1&& ;
  29
  30 <PRIVATE
  31 : push ( item deque -- newdeque )
  32     [ front>> cons ] [ back>> ] bi deque boa ; inline
  33 PRIVATE>
  34
  35 : push-front ( deque item -- newdeque )
  36     swap push ;
  37
  38 : push-back ( deque item -- newdeque )
  39     swap [ push ] flipped ;
  40
  41 <PRIVATE
  42 : remove ( deque -- item newdeque )
  43     [ front>> car ] [ [ front>> cdr ] [ back>> ] bi deque boa ] bi ; inline
  44
  45 : transfer ( deque -- item newdeque )
  46     back>> dup nil?
  47     [ "Popping from an empty deque" throw ]
  48     [ split-reverse deque boa remove ] if ; inline
  49
  50 : pop ( deque -- item newdeque )
  51     dup front>> nil? [ transfer ] [ remove ] if ; inline
  52 PRIVATE>
  53
  54 : pop-front ( deque -- item newdeque )
  55     pop ;
  56
  57 : pop-back ( deque -- item newdeque )
  58     [ pop ] flipped ;
  59
  60 : peek-front ( deque -- item )
  61     pop-front drop ;
  62
  63 : peek-back ( deque -- item )
  64     pop-back drop ;
  65
  66 : sequence>deque ( sequence -- deque )
  67     <deque> [ push-back ] reduce ;
  68
  69 : deque>sequence ( deque -- sequence )
  70     [ dup deque-empty? not ] [ pop-front swap ] produce nip ;