;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                                 ALIST           
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define alist (make-record-type "alist" '(size array first free)))
(define create-alist (record-constructor alist '(size array first free)))

(define (make-alist n)
  (let ((a (make-array (list (+ n 1) 2) nil)))
    (do ((i 1 (+ i 1)))
	((= i n))
      (array-set! a (list i 1) (+ i 1)))
    (array-set! a (list n 1) 0)
    (create-alist n a 0 1)))
;;;
;;; so it runs from 1 to n
;;; an alist is essentially a 2 dimensional array
;;; (array-ref (array l) (list i 0)) is the data
;;; (array-ref (array l) (list i 1)) points to next element in alist
;;; NOTE that (= 0 (array-ref (array l) (list i 1))) means nil
;;;
;;; (free alist) points to first free entry in the alist
;;; and all free items are linked together
;;;

(define alist? (record-predicate alist))

(define size (record-accessor alist 'size))
(define array (record-accessor alist 'array))
(define first (record-accessor alist 'first))
(define free (record-accessor alist 'free))

(define first! (record-modifier alist 'first))
(define free! (record-modifier alist 'free))

(define (empty? l)
  (= 0 (first l)))

(define (head n l)
  (array-ref (array l) (list n 0)))
;;;
;;; get the data at position n
;;;

(define (head! n l v)
  (array-set! (array l) (list n 0) v))
;;;
;;; set the data in position n
;;;

(define (next n l)
  (array-ref (array l) (list n 1)))
;;;
;;; the next element after n
;;;

(define (next! n l v)
  (array-set! (array l) (list n 1) v))
;;;
;;; set the next element after n to be v
;;;
   
(define (print l)
  (cond ((empty? l) (display "nil"))
	(t (display "( ")
	   (do ((i (first l) (next i l)))
	       ((= 0 i))
	       (display (head i l)) (display " "))
	   (display ")")))
  (newline))

(define (create-element l)
  (let ((i (free l)))
    (free! l (next i l))
    (next! i l 0) ; tail of n points to ground 
    i))
;;;
;;; take an element of the free list and downdate the free list
;;;

(define (free-element i l)
  (next! i l (free l))
  (free! l i))
;;;
;;; push element i onto the free list
;;;

(define (insert! e l p)
  (let ((new (create-element l)))
    (head! new l e)
    (cond ((empty? l) (first! l new))
	  ((p e (head (first l) l))
	   (next! new l (first l))
	   (first! l new))
	  (t (let ((prev (do ((i (first l) (next i l)))
			     ((or (= 0 (next i l))
				  (p e (head (next i l) l))) i)
			   (display i))))
	       (next! new l (next prev l))
	       (next! prev l new))))))
;;;
;;; Compare with insert! in llist.scm
;;; Essentially the same
;;;
		


;;;
;;; EXERCISES
;;;
;;; (delete! e l p)
;;; (full? l) ; is there any free space remaining
;;; (sound? l) ; make sure that structure is sound
;;;              what tests do you think you could carry out?
;;;