;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;                               VLIST
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define vlist (make-record-type "vlist" '(size vect end)))
(define create-vlist (record-constructor vlist '(size vect end)))
(define make-vlist
  (lambda (n)
    (create-vlist n (make-vector (+ n 1)) 0))); so it runs from 1 to n
;;;
;;; The list is essentially composed of a vector, and has associated info
;;; in particular a size, and a pointer to the last element of the list (end)
;;;

(define vlist? (record-predicate vlist))

(define size (record-accessor vlist 'size))
(define vect (record-accessor vlist 'vect))
(define end  (record-accessor vlist 'end))

(define end! (record-modifier vlist 'end))

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

(define l (make-vlist 20))
;;;
;;; Make me a vlist of 20 elements
;;;

(define (print l)
  (cond ((empty? l) (newline))
	(t (do ((i 1 (+ i 1)))
	       ((> i (end l)))
	     (display (vector-ref (vect l) i)) (display " "))
	   (newline))))

(define (right-shift v pos n); move array element at position i to i+1
		             ;for i = n-1 down to pos
  (do ((i n (- i 1)))
      ((= i pos))
    (vector-set! v i (vector-ref v (- i 1)))))
;;;
;;; Given a vector v, of n elements, and an element at position pos
;;; shift elements right one position from position pos.
;;; Think of inserting a card in a deck
;;; NOTE: very easy to screw this one up and end with
;;;       multiple copies of an array element (I know, I've done it)
;;;

(define (find e l p)
  (cond ((empty? l) (+ (end l) 1))                            ;(1)
	(t (do ((pos 1 (+ i pos)))                            ;(2)
	       ((or (> pos (end l))                           ;(3)
		    (p e (vector-ref (vect l) pos))) pos))))) ;(4)
;;;
;;; Find the position of the element in (vect l) that satisfies
;;; (p e (vector-ref (vect l) pos)). 
;;; If not satisfied then  pos = end+1
;;; This then gives position of element to be deleted, or to be inserted at.
;;;

(define (insert! e l p)
  (let ((v (vect l)))
    (cond ((empty? l) (vector-set! v 1 e))                            ; (1)
	  (t (let ((pos (find e l p)))                                ; (2)
	       (cond ((<= pos (end l))                                ; (3)
		      (right-shift v pos (+ 1 (end l)))))             ; (4)
	       (vector-set! v pos e))))                               ; (5)
    (end! l (+ 1 (end l)))))                                          ; (6)
;;;
;;; (1) list is empty, so first element of vector becomes e
;;; (2) find position that satisfies (p e (vector-ref v i))
;;;     and call it pos
;;; (3) if we are inserting it somewhere in the list other than beyond
;;;     the end, then make space by shifting contents right (4)
;;; (5) update the vector element at position pos to become e
;;; (6) this line is done unconditionally for all situations.
;;;     The end of the list is incremented
;;;
;;; NOTE: If all insertions are at the front of the list,
;;; what is the cost of an insertion?
;;;

(define (left-shift v pos n) ; move array element at position i+1 to i
		             ; for i = pos to n-1
  (do ((i pos (+ i 1)))
      ((= i n) v)
    (vector-set! v i (vector-ref v (+ i 1)))))
;;;
;;; Symmetric to right-shift
;;; Again easy to screw up and end up copying elements
;;;


(define (delete! e l p)
  (cond ((not (empty? l))                             ; (1)
	 (let ((pos (find e l p)))                    ; (2)
	   (cond ((<=  pos (end l))                   ; (3)
		  (left-shift (vect l) pos (end l))   ; (4)
		  (end! l (- (end l) 1))))))))        ; (5)
;;;
;;; (1) assuming the list is not empty
;;; (2) find the position of element to be deleted
;;; (3) if it was found (ie pos <= end)
;;; (4) shift left from that position and
;;; (5) decrement end of list
;;;

;;;
;;; EXERCISES (not compulsory)
;;; write the following functions for vlist
;;; (append! l1 l2)
;;; (merge! l1 l2 p)
;;;
;;; NOTE there are no tests to determine if we are about to overfill
;;; the vector. Modify above to make safe.
;;;
;;; Advanced Exercise
;;; Think of a "lazy" list, where we only do things when absolutely 
;;; necessary. For example when an item is deleted we mark it as deleted
;;; Discuss this from the point of view of cost and benefits.
;;; How might you exploit deletions during insertions?
;;;