;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                           LLIST
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define llist (make-record-type "llist" '(head tail)))
(define make-llist (record-constructor llist '(head tail)))

(define llist? (record-predicate llist))

(define empty nil)

(define (empty? l)
  (not l))

(define l (make-llist 3
		      (make-llist 7
				  (make-llist 9
					      (make-llist 11 empty)))))

(define head (record-accessor llist 'head))
(define tail (record-accessor llist 'tail))

(define head! (record-modifier llist 'head)); delivers #<unspecified>
(define tail! (record-modifier llist 'tail)); delivers #<unspecified>

;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(define (printl l)
  (cond ((empty? l) (newline))
	(t (display (head l))
	   (display " ")
	   (printl (tail l)))))

(define (find e l p)
  (cond ((empty? l) #f)
	((or (p e (head l))
	     (find e (tail l))))))

(define (nth n l)
  (cond ((= 1 n) (head l))
	((empty? l) empty)
	(t (nth (- n 1) (tail l)))))

;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(define (insert e l p)   ; constructive insert
  (cond ((empty? l) (make-llist e empty))                  ; (1)
	((p e (head l)) (make-llist e l))                  ; (2)
	(t (make-llist (head l) (insert e (tail l) p)))))  ; (3)
;;;
;;; example (define x (insert 5 l <))
;;; example (define y (insert 100 empty <))
;;;
;;; (1) If the list is empty then make a list with e as first cell
;;; (2) if e should be 1st element in the list, make a list with
;;;     e as first element, and l as the tail
;;; (3) otherwise make a list that has (head l) as the head of the list
;;;     and the insertion of e into the tail of l as the tail of the list
;;;
;;; NOTE: a new list structure is created, but contents (head l) are
;;;       retained.
;;;
;;; NOTE: use of predicate p allows the abstract data type llist
;;;       to be generic, such that we can have lists of strings,
;;;       of people, of small fluffy animals, etc
;;;       Just use the approriate predicate p
;;;       This is sometimes referred to as POLYMORPHISM
;;;       Generally speaking, an object is POLYMORPHIC if it can be regarded
;;;       as having multiple types
;;;


(define (insert! e l p) ; destructive insert (mutation)
  (cond ((empty? l) (make-llist e empty))                    ; (1)
	((p e (head l)) (make-llist e l))                    ; (2)
	((empty? (tail l)) (tail! l (make-llist e empty)))   ; (3)
	((p e (head (tail l)))                               ; (4)
	 (let ((x (make-llist e (tail l))))                  ; (5)
	   (tail! l x) l))                                   ; (6)
	(t (insert! e (tail l) p))))                         ; (7)
;;;
;;; Lines 5 & 6 is where insertion takes place, 
;;; Line 7 is where we traverse down the list (recusrively)
;;; Trick is in line 3, where tail of list is empty
;;; 
;;; NOTE: that insert! routine always hang in there on a 
;;; non-empty cell, so must look into the future (ie. next cell)
;;;

;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(define (delete e l p)
  (cond ((empty? l) l)                                    ; (1)
	((p e (head l)) (tail l))                         ; (2)
	(t (make-llist (head l) (delete e (tail l) p))))) ; (3)
;;;
;;; Example (printl (delete 7 l =))
;;;
;;; Creates a new list structure, reusing contents.
;;;
;;; Similar to insert, and we might assume that predicate p is =
;;; (1) deleting e from empty list
;;; (2) delete from head of list, deliver tail
;;; (3) otherwise make a list that has the head of l with e deleted
;;;     from the tail
;;;

(define (delete! e l p) ; destructive delete
  (cond ((empty? l) l)                                       ; (1)
	((p e (head l)) (tail l))                            ; (2)
	((empty? (tail l)) l)                                ; (3)
	((p e (head (tail l)))                               ; (4)
	 (tail! l(tail (tail l))))                           ; (5)
	(t (delete! e (tail l) p))))                         ; (6)
;;;
;;; (1) empty list
;;; (2) delete first element in list
;;; (3) is tail empty?
;;; (4) tail is not empty and next element to be deleted
;;; (5) then let the tail of l be the tail of the tail of l!!
;;; (6) none of the above, so try and delete from rest of list
;;; 
;;; NOTE: line (2) can only be performed first call
;;;

(define (delete2! e l p) '?)
(define (append! l1 l2) '?)
(define (merge! l1 l2 p) '?)

;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
		   
;;;
;;; EXERCISES (not compulsory)
;;;
;;; Now write functions for the following
;;; (append! l1 l2)
;;; (merge! l1 l2 p)
;;; (reverse list)
;;; 
;;;
;;; More advanced:
;;; define new ADT's for dlist, where a dlist is like a llist
;;; except each element has a pointer to the previous element
;;; as well as the next, ie. a doubly linked list
;;;
;;; (define dlist (make-record-type "dlist" '(prev head tail)))
;;;
;;; redo all of above except use dlist rather than llist
;;;