2k: Queue Logic

++to

Queue operations

Container arm for queue operation arms. The contained arms inherit a, its sample queue.

Accepts

a is a tree.

Source

    ++  to
      |_  a=(tree)

Discussion

tree is the generic tree-shape mold. Maps, sets, and queues all share that shape, but they put their elements in different places and have different interfaces. to is the interface core for qeu; it's not generic across all the different containers that use tree.


++bal:to

Balance

Vertically rebalances queue a.

Accepts

a is a queue.

Produces

A queue.

Source

  ++  bal
    |-  ^+  a
    ?~  a  ~
    ?.  |(?=(~ l.a) (mor n.a n.l.a))
      $(a l.a(r $(a a(l r.l.a))))
    ?.  |(?=(~ r.a) (mor n.a n.r.a))
      $(a r.a(l $(a a(r l.r.a))))
    a

Examples

    > `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~]
    {"a" "b" "c" "d" "e" "f" "g"}

    > `*`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~]
    [[97 0] 0 [98 0] 0 [99 0] 0 [100 0] 0 [101 0] 0 [102 0] 0 [103 0] 0 0]

    > ~(bal to `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~])
    [n=[i='d' t=""] l={"a" "b" "c"} r={"e" "f" "g"}]

    > `*`~(bal to `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~])
    [[100 0] [[99 0] [[98 0] [[97 0] 0 0] 0] 0] [101 0] 0 [102 0] 0 [103 0] 0 0]

++dep:to

Maximum Depth

Produces the maximum depth of leaves (r.a and l.a) in queue a.

Accepts

a is a queue.

Produces

An atom.

Source

  ++  dep                                               ::  max depth of queue
    |-  ^-  @
    ?~  a  0
    +((max $(a l.a) $(a r.a)))

Examples

    > =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 7 ~])
    > ~(dep to a)
    4

    > =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 ~])
    > ~(dep to a)
    3

    > =a (~(gas to `(qeu @)`~) `(list @)`[1 2 ~])
    > ~(dep to a)
    2

    > ~(dep to `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~])
    7

    > ~(dep to ~(bal to `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~]))
    4

++gas:to

Push list

Push all elements of list b into the queue a.

Accepts

a is a queue.

b is a list.

Produces

A queue.

Source

  ++  gas                                               ::  insert list to que
    |=  b=(list _?>(?=(^ a) n.a))
    |-  ^+  a
    ?~(b a $(b t.b, a (put i.b)))

Examples

    > `(qeu)`(~(gas to `(qeu @)`~) [1 2 3 ~])
    {3 2 1}

    > =a (~(gas to `(qeu @)`~) [1 2 3 ~])
    > =b [4 5 6 ~]
    > `(qeu)`(~(gas to a) b)
    {6 5 4 3 2 1}

++get:to

Head-tail pair

Produces the head and tail queue of a.

Accepts

a is a queue.

Produces

A cell of the last element in a along with the rest of queue a.

Source

  ++  get                                               ::  head-rest pair
    |-  ^+  ?>(?=(^ a) [p=n.a q=*(tree _n.a)])
    ?~  a
      !!
    ?~  r.a
      [n.a l.a]
    =+  b=$(a r.a)
    :-  p.b
    ?:  |(?=(~ q.b) (mor n.a n.q.b))
      a(r q.b)
    a(n n.q.b, l a(r l.q.b), r r.q.b)

Examples

    > =s (~(gas to *(tree @)) `(list @)`~[1 2 3])
    > ~(get to s)
    [n=2 l={3} r={1}]

    > ~(get to ~)
    ! exit

++nap:to

Remove head

Removes the head of queue a, producing the resulting queue.

Accepts

a is a queue.

Produces

A queue.

Source

  ++  nap                                               ::  removes root
    ?>  ?=(^ a)
    ?:  =(~ l.a)  r.a
    =+  b=get(a l.a)
    bal(n.a p.b, l.a q.b)

Examples

    > =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 ~])
    > -.a
    n=6

    > =b ~(nap to a)
    > -.b
    n=2

    > a
    [n=6 l={} r={5 4 3 2 1}]

    > b
    [n=2 l=[n=4 l={5} r={3}] r=[n=1 l={} r={}]]

    > `(qeu)`b
    {5 4 3 2 1}

    > `(qeu)`a
    {6 5 4 3 2 1}

++nip:to

Removes the root of queue a, producing the resulting queue.

Accepts

a is a queue.

Produces

A queue.

Source

  ++  nip                                               ::  removes root
    |-  ^+  a
    ?~  a  ~
    ?~  l.a  r.a
    ?~  r.a  l.a
    ?:  (mor n.l.a n.r.a)
      l.a(r $(l.a r.l.a))
    r.a(l $(r.a l.r.a))

Examples

    > =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 ~])
    > a
    [n=6 l={} r={5 4 3 2 1}]

    > ~(nip to a)
    [n=2 l=[n=4 l={5} r={3}] r=[n=1 l={} r={}]]

++put:to

Insert

Accept any noun b and adds to queue a as the head, producing the resulting queue.

Accepts

a is a queue.

b is any noun.

Produces

A queue.

Source

  ++  put                                               ::  insert new tail
    |*  b=*
    |-  ^+  a
    ?~  a
      [b ~ ~]
    bal(l.a $(a l.a))

Examples

    > =a (~(gas to `(qeu @)`~) `(list @)`[3 1 2 4 5 6 ~])
    > `(qeu)`(~(put to a) 7)
    {7 6 5 4 2 1 3}

++tap:to

Queue to list

Produces queue a as a list from front to back.

Accepts

a is a queue.

Produces

A list.

Source

  ++  tap                                               ::  adds list to end
    =+  b=`(list _?>(?=(^ a) n.a))`~
    |-  ^+  b
    =+  0                                               ::  hack for jet match
    ?~  a
      b
    $(a r.a, b [n.a $(a l.a)])

Examples

    > =a (~(gas to `(qeu @)`~) [3 1 2 4 5 6 ~])
    > `*`a
    [6 0 2 [4 [5 0 0] 0] 1 0 3 0 0]
    > ~(tap to a)
    ~[3 1 2 4 5 6]

++top:to

Produce head

Produces the head of queue a as a unit.

Accepts

a is a queue.

Produces

A unit.

Source

  ++  top                                               ::  produces head
    |-  ^-  (unit _?>(?=(^ a) n.a))
    ?~  a  ~
    ?~(r.a [~ n.a] $(a r.a))
  --

Examples

    > =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 ~])
    > ~(top to a)
    [~ u=1]

Discussion

An empty queue has no head.