; Random-Access List - an immutable random-access list implementation
;
; Functions:
;   Inspectors:
;     (ra-list? value)     is value a ra-list? (#f if it is not a ra-list)
;     (ra-empty? value)    is value the empty ra-list?  (#f if it is not an empty ra-list)
;     (ra-length list)     the length of the list better than O(1)
;
;   List operations
;     (ra-cons value list) return a new list with value at its head and list as its tail
;     (ra-car list)        return the head of the list
;     (ra-cdr list)        return the tail of the list
;
;   Array operations
;     (ra-list-ref list i) access the ith element of the list
;
;   Creation
;     (ra-empty)           return the empty ra-list
;     (ra-list value ...)  unrestricted lambda returns a ra-list containing all arguments
;
;   Utility
;     (ra->list ralist)  returns a list with the same elements as the given ra-list
;     (list->ra list)    returns a ra-list with the same elements as the given list
;
; Author:
;   Jeff Walker
;   jwalker(at)cs.oberlin.edu
;
; Version:
;   01.20.2002  jwalker - removed list length field. Updated related functions. (ra-list? (ra-empty)) => #t now.
;   08.08.2001  jwalker - added comments, renamed for clarity, removed ra-list-update!
;   11.12.2000  jwalker
;

;The basic structure, no not directly access.
(define-struct naryTree (value size sib child))
(define emptyNaryTree (make-naryTree () 0 () ()))
(define createNaryTree
  (lambda (value sib child)
    (make-naryTree value (+ (ra-length child) 1) sib child)))

;Inspectors
(define ra-list?
  (lambda (list)
    (cond
      ((naryTree? list) #t)
      ((ra-empty? list) #t)
      (else #f))))

(define ra-empty?
  (lambda (list)
    (eq? list emptyNaryTree)))

(define ra-length
  (lambda (list)
    (letrec ((helper
              (lambda (list)
                (if (ra-empty? list)
                    0
                    (+ (naryTree-size list) (helper (naryTree-sib list)))))))
      (cond
        [(not (ra-list? list)) (error 'not-ra-list "ra-length: param not a ra-list")]
        [else (helper list)]))))

;Used only internally
(define ra-size
  (lambda (list)
    (cond
      [(not (ra-list? list)) (error 'not-ra-list "ra-size: param not a ra-list")]
      [else (naryTree-size list)])))

;List operations
(define ra-car
  (lambda (list)
    (cond
      [(not (ra-list? list)) (error 'not-ra-list "ra-car: param not a ra-list")]
      [(ra-empty? list) (error 'empty-list "ra-car: param empty")]
      [else (naryTree-value list)])))

(define ra-cons
  (lambda (value list)
    (cond
      [(not (ra-list? list)) (error 'not-ra-list "ra-car: param not a ra-list")]
      [(or (ra-empty? list)
           ;(ra-empty? (naryTree-sib list))
           (not (= (naryTree-size list) (naryTree-size (naryTree-sib list)))))
       (createNaryTree value list (ra-empty))]
      [else (let* ((v1 (naryTree-value list))
                   (child1 (naryTree-child list))
                   (list2 (naryTree-sib list))
                   (v2 (naryTree-value list2))
                   (child2 (naryTree-child list2))
                   (rest (naryTree-sib list2)))
              (createNaryTree value 
                              rest  ;Sibling is old rest of rest
                              (createNaryTree v1 (createNaryTree v2 (ra-empty) child2) child1) ;child remaking two children.
                              ))])))

(define ra-cdr
  (lambda (list)
    (cond
      [(not (ra-list? list)) (error 'not-ra-list "ra-cdr: param not a ra-list")]
      [(ra-empty? list) (error 'empty-list "ra-cdr: param is empty ra-list")]
      [(= 1 (ra-size list)) (naryTree-sib list)]
      [else (let* ((child1 (naryTree-child list))
                   (v1 (naryTree-value child1))
                   (child2 (naryTree-sib child1))
                   (v2 (naryTree-value child2)))
              (createNaryTree v1 (createNaryTree v2 (naryTree-sib list) (naryTree-child child2)) (naryTree-child child1)))])))

;Array operations
(define ra-list-ref
  (lambda (list i)
    (cond
      [(not (ra-list? list)) (error 'not-ra-list "ra-list-ref: param not a ra-list")]
      [(ra-empty? list) (error 'index-out-of-bound "ra-list: index out of bounds")]
      [(= 0 i) (ra-car list)]
      [(<= (ra-size list) i) (ra-list-ref (naryTree-sib list) (- i (ra-size list)))]
      [else (ra-list-ref (naryTree-child list) (- i 1))])))

;Creation
(define ra-empty
  (lambda ()
    emptyNaryTree))

(define ra-list
  (lambda list
    (list->ra list)))

;Utility
(define ra->list
  (lambda (list)
    (if (ra-empty? list)
        '()
        (cons (ra-car list) (ra-to-list (ra-cdr list))))))

(define list->ra
  (lambda (list)
    (if (null? list)
        (ra-empty)
        (ra-cons (car list) (list-to-ra (cdr list))))))