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

@(require scribble/eval)

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

@title[#:tag "bral"]{Binary Random Access List}

Random Access Lists are list data structures that provide array-like lookup 
and update operations. They have been implemented as a framework of binary 
numerical representation using complete binary leaf trees. It has a worst 
case running time of @bold{@italic{O(log(n))}} for the operations
@scheme[cons], @scheme[first], @scheme[rest], @scheme[list-ref] and
@scheme[list-set].

@defform[(List A)]{A binary random access list of type @racket[A].}

@defproc[(list [a A] ...) (List A)]{
Function @scheme[list] creates a Binary Random Access List with the given 
inputs.
@examples[#:eval evaluate

(list 1 2 3 4 5 6)
]

In the above example, @scheme[(list 1 2 3 4 5 6)] gives a Binary Random 
Access List which is similar to lists but comes with efficient list-ref and 
list-set operations.}

@defthing[empty (List Nothing)]{
A empty random access list}

@defproc[(empty? [ral (List A)]) Boolean]{
Function @scheme[empty?] takes a Binary Random Access List checks if the 
given list is empty.   
@examples[#:eval evaluate

(empty? (list 1 2 3))

(empty? empty)
]}

@defproc[(cons [a A] [ral (List A)]) (List A)]{
Function @scheme[cons] takes an element and a list and adds the given 
element to the front of the given list.   
@examples[#:eval evaluate

(cons 10 (list 5 3 5 6))
]

In the above example, @scheme[(cons 10 (list 5 3 5 6))] returns 
@scheme[(list 10 5 3 5 6)].
}

@defproc[(first [ral (List A)]) A]{
Function @scheme[first] takes a list and returns the first element
of the given list if its not empty else throws an error.   
@examples[#:eval evaluate

(first (list 5 3 5 6))

(first empty)
]}



@defproc[(rest [ral (List A)]) (List A)]{
Function @scheme[rest] takes a list and returns the given list but
without its first element if the given list is not empty. If it is empty,
@scheme[rest] throws an error
@examples[#:eval evaluate

(rest (list 1 2 3 4 5 6))

(rest empty)
]

In the above example, @scheme[(rest ral)] returns the rest of the given 
list, @scheme[(list 2 3 4 5 6)].
}

@defproc[(list-ref [ral (List A)] [index Integer]) A]{
Function @scheme[list-ref] takes an integer(say n) and a list and gives
the nth element of the given list. If the given n is larger than the size 
of the list, @scheme[list-ref] throws an error.
  
@examples[#:eval evaluate

(list-ref (list 12 5 3 2 15 23) 4)

(list-ref (list 12 5 3 2 15 23) 10)

]}


@defproc[(list-set [ral (List A)] [index Integer] [newval A]) (List A)]{
Function @scheme[list-set] takes an integer(say n), list and a new
element. And updates the nth element of the list with the new element.

  
@examples[#:eval evaluate

(list-set (list 1 2 3 4 5 6) 2 10)

(list-set (list 1 2 3 4 5 6) 10 15)
]

In the above example, @scheme[(list-set (list 1 2 3 4 5 6) 2 10)] returns 
@scheme[(list 1 2 10 4 5 6)] and 
@scheme[(list-set (list 1 2 3 4 5 6) 10 15)] throws an error.
}

@defproc[(->list [ral (List A)]) (Listof A)]{
Function @scheme[->list] takes a list and returns a list
of elements which are in the same order as in the list.   
@examples[#:eval evaluate

(define ral (list 1 2 3 4 5 6))

(->list ral)
]

In the above example, @scheme[(->list ral)] returns
@scheme[(list 1 2 3 4 5 6)].
}

@defproc[(drop [ral (List A)] [num Integer]) (List A)]{
Function @scheme[drop] takes a list and an integer(say n) and drops 
the first n elements of the input list and returns the rest of the list. 
  
@examples[#:eval evaluate

(drop 3 (list 1 2 3 4 5 6))

(drop 10 (list 1 2 3 4 5 6))
]

In the above example, @scheme[(drop 3 (list 1 2 3 4 5 6))] returns the 
list @scheme[(list 4 5 6)]. @scheme[(drop 10 (list 1 2 3 4 5 6))]
throws an error since 10 is larger than the number of 
elements in the list.
}


@defproc[(list-length [ral (List A)]) Integer]{
Function @scheme[list-length] takes a list and gives the number of 
elements in in the given list. 

@examples[#:eval evaluate

(list-length (list 1 2 3 4 5 6))

(list-length empty)
]}

@defproc[(reverse [list (List A)]) (List A)]{
Function @scheme[reverse] takes a list and returns a reversed list. 

@examples[#:eval evaluate

(->list (reverse (list 1 2 3 4 5 6)))
]}


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

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

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

In the above example, @scheme[(map add1 (list 1 2 3 4 5 6))] adds 1 to
each element of the given list and returns @scheme[(list 2 3 4 5 6 7)].
@scheme[(map * (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))] multiplies
corresponding elements in the two lists
and returns the list @scheme[(list 1 4 9 16 25 36)].}


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

@examples[#:eval evaluate

(foldl + 0 (list 1 2 3 4 5 6))

(foldl * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))
]}


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

@examples[#:eval evaluate

(foldr + 0 (list 1 2 3 4 5 6))

(foldr * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))
]}

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

(define lst (list 1 2 3 4 5 6))

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

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

(->list (filter (λ:([x : Integer]) (<= x 4)) lst))
]}

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

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

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

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

@(close-eval evaluate)