#lang scribble/manual
@(require "helper.rkt")
@(require unstable/scribble)
@defmodule/this-package[physicists-queue]
@(require (for-label (planet krhari/pfds:1:0/physicists-queue)))

@;@(require "stream.ss")AP270301PF0Z945U
@(require scribble/eval)

@(define evaluate (make-base-eval))
@(evaluate '(require typed/racket))
@(evaluate '(require "physicists-queue.ss"))

@title[#:tag "phy-que"]{Physicist's Queue}

A Queue is nothing but a FIFO data structure. A Physicist's queue ia a
Amortized queues obtained by Physicist's method. Provides a amortized
running time of @bold{@italic{O(1)}} for @scheme[head], @scheme[tail]
and @scheme[enqueue] operations. Physicists's Queue uses lazy evaluation
and memoization to get this amortized running time.

@;section{Physicist's Queue Construction and Operations}
@defform[(Queue A)]{A physicist's queue of type @racket[A].}


@defproc[(queue [a A] ...) (Queue A)]{
Function @scheme[queue] creates a Physicist's Queue with the given inputs.

@examples[#:eval evaluate

(queue 1 2 3 4 5 6)
]

In the above example, the queue obtained will have 1 as its head element}


@defproc[(empty [t A]) (Queue A)]{
An empty queue.}

@defproc[(empty? [que (Queue A)]) Boolean]{
Function @scheme[empty?] checks if the given queue is empty or not.

@examples[#:eval evaluate

(empty? (queue 1 2 3 4 5 6))

(empty? (empty Integer))
]}


@defproc[(enqueue [a A] [que (Queue A)]) (Queue A)]{
Function @scheme[enqueue] takes an element and a queue and enqueues 
the given element into the queue. 
@examples[#:eval evaluate

(enqueue 10 (queue 1 2 3 4 5 6))
]

In the above example, enqueue adds the element 10 to 
@scheme[(queue 1 2 3 4 5 6)] and returns @scheme[(queue 1 2 3 4 5 6 10)].}

@defproc[(head [que (Queue A)]) A]{
Function @scheme[head] takes a queue and gives the first element in the
queue if its a non empty queue else throws an error. 
@examples[#:eval evaluate

(head (queue 1 2 3 4 5 6))
(head (empty Integer))
]}

@defproc[(tail [que (Queue A)]) (Queue A)]{
Function @scheme[tail] takes a queue and returns a queue with rest 
elements if its a non empty queue else throws an error. 
@examples[#:eval evaluate

(tail (queue 1 2 3 4 5 6))

(tail (empty Integer))
]

In the above example, @scheme[(tail (queue 1 2 3 4 5 6))], returns 
@scheme[(queue 2 3 4 5 6)].}


@defproc[(queue->list [que (Queue A)]) (Queue A)]{
Function @scheme[queue->list] takes a queue and returns a list of 
elements. The list will have head of the given queue as its first element.
If the given queue is empty, then it returns an empty list. 

@examples[#:eval evaluate

(queue->list (queue 10 2 34 4 15 6))

(queue->list (empty Integer))
]}


@;
@;subsection{list->queue}
@;Function @scheme[list->queue] takes a list and returns a queue of 
@;elements. The queue will be such that its head will have car of the list.

@;examples[#:eval evaluate

@;(list->queue (list 10 2 34 4 15 6))

@;]

@;In the above example, @scheme[(list->queue (list 10 2 34 4 15 6))], returns 
@;the queue @scheme[(queue 10 2 34 4 15 6)].
@;

@defproc[(map [func (A B ... B -> C)] 
              [que1 (Queue A)]
              [que2 (Queue B)] ...) (Queue A)]{
Function @scheme[map] is similar to @|racket-map| for lists.
@examples[#:eval evaluate

(queue->list (map add1 (queue 1 2 3 4 5 6)))

(queue->list (map * (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6)))
]}

@defproc[(fold [func (C A B ... B -> C)]
               [init C]
               [que1 (Queue A)]
               [que2 (Queue B)] ...) C]{
Function @scheme[fold] is similar to @|racket-foldl| or @|racket-foldr|
@margin-note{@scheme[fold] currently does not produce correct results when the 
             given function is non-commutative.}

@examples[#:eval evaluate

(fold + 0 (queue 1 2 3 4 5 6))

(fold * 1 (queue 1 2 3 4 5 6) (queue 1 2 3 4 5 6))
]}

@defproc[(filter [func (A -> Boolean)] [que (Queue A)]) (Queue A)]{
Function @scheme[filter] is similar to @|racket-filter|. 
@examples[#:eval evaluate

(define que (queue 1 2 3 4 5 6))

(queue->list (filter (λ: ([x : Integer]) (> x 5)) que))

(queue->list (filter (λ: ([x : Integer]) (< x 5)) que))

(queue->list (filter (λ: ([x : Integer]) (<= x 5)) que))
]}

@defproc[(remove [func (A -> Boolean)] [que (Queue A)]) (Queue A)]{
Function @scheme[remove] is similar to @|racket-filter| but @scheme[remove] removes the elements which match the predicate. 
@examples[#:eval evaluate

(queue->list (remove (λ: ([x : Integer]) (> x 5))
                     (queue 1 2 3 4 5 6)))

(queue->list (remove (λ: ([x : Integer]) (< x 5))
                     (queue 1 2 3 4 5 6)))

(queue->list (remove (λ: ([x : Integer]) (<= x 5))
                     (queue 1 2 3 4 5 6)))
]}


@defproc[(andmap [func (A B ... B -> Boolean)]
                 [que1 (Queue A)]
                 [que2 (Queue B)] ...) Boolean]{
Function @scheme[andmap] is similar to @|racket-andmap|.

@examples[#:eval evaluate

(andmap even? (queue 1 2 3 4 5 6))

(andmap odd? (queue 1 2 3 4 5 6))

(andmap positive? (queue 1 2 3 4 5 6))

(andmap negative? (queue -1 -2))
]}


@defproc[(ormap [func (A B ... B -> Boolean)]
                [que1 (Queue A)]
                [que2 (Queue B)] ...) Boolean]{
Function @scheme[ormap] is similar to @|racket-ormap|.

@examples[#:eval evaluate

(ormap even? (queue 1 2 3 4 5 6))

(ormap odd? (queue 1 2 3 4 5 6))

(ormap positive? (queue -1 -2 3 4 -5 6))

(ormap negative? (queue 1 -2))
]}

@defproc[(build-queue [size Natural]
                      [func (Natural -> A)])
                      (Queue A)]{
Function @scheme[build-queue] is similar to @|racket-build-list|.
@examples[#:eval evaluate

(queue->list (build-queue 5 (λ:([x : Integer]) (add1 x))))

(queue->list (build-queue 5 (λ:([x : Integer]) (* x x))))

]}

@defproc[(head+tail [que (Queue A)])
                    (Pair A (Queue A))]{
Function @scheme[head+tail] returns a pair containing the head and the tail of
the given queue.
@examples[#:eval evaluate

(head+tail (queue 1 2 3 4 5))

(head+tail (build-queue 5 (λ:([x : Integer]) (* x x))))

(head+tail (empty Integer))

]}

@(close-eval evaluate)