(module gvector mzscheme
  
  (provide
   (rename construct-gvector gvector)
   (rename gvector-size gvector-length)
   gvector?
   gvector-ref
   gvector-insert!
   gvector-set!
   gvector->list
   list->gvector
   gvector-fill!)
  
  (define-struct gvector (vec size))
  (define GROWTH-FACTOR 2)
  
  ; This library defines the type (gvector of X), which supports the operations listed.
  
  ; gvector : X ... -> (gvector of X)
  ; builds a gvector with all the given values in order as elements
  (define (construct-gvector . vals)
    (let ((vec (list->vector vals)))
      (make-gvector vec (vector-length vec))))
  
  ; gvector-ref : (gvector of X) Nat -> X
  ; extracts the given element from the given gvector
  (define (gvector-ref gvec idx)
    (if (valid-idx? gvec idx)
        (vector-ref (gvector-vec gvec) idx)
        (error 'gvector-ref "Invalid index")))
  
  ; valid-idx? : gvector TST -> bool
  ; determines whether the given number is a valid index for the given gvector
  (define (valid-idx? gvec idx)
    (and (number? idx)
         (exact? idx)
         (not (negative? idx))
         (< idx (gvector-size gvec))))

  ; grow! : gvector of X -> void
  ; updates the internal representation of the given gvector so that it
  ; now has memory for a factor of GROWTH-FACTOR more elements
  (define (grow! gvec)
    (let* ((oldvec (gvector-vec gvec))
           (oldsize (vector-length oldvec))
           (newvec (make-vector (max (* GROWTH-FACTOR oldsize) 1))))
      (let loop ((i 0))
        (if (< i oldsize)
            (begin
              (vector-set! newvec i (vector-ref oldvec i))
              (loop (add1 i)))
            (begin
              (set-gvector-vec! gvec newvec)
              (void))))))
  
  ; full? : gvector -> boolean
  ; determines whether the internal representation of the given gvector
  ; has used all available cells
  (define (full? gvec)
    (= (gvector-size gvec) (vector-length (gvector-vec gvec))))
  
  ; gvector-insert! : (gvector of X) X -> void
  ; SIDE EFFECT: places the given item at the end of the given gvector
  (define (gvector-insert! gvec item)
    (begin
      (if (full? gvec) (grow! gvec))
      (vector-set! (gvector-vec gvec) (gvector-size gvec) item)
      (set-gvector-size! gvec (add1 (gvector-size gvec)))
      (void)))
  
  ; gvector-set! : (gvector of X) Nat X -> void
  ; SIDE EFFECT: updates the cell indicated by the given natural number
  ; in the given gvector to be the given value
  (define (gvector-set! gvec idx item)
    (if (valid-idx? gvec idx)
        (vector-set! (gvector-vec gvec) idx item)
        (error 'gvector-set! "Invalid index")))
  
  ; gvector->list : gvector of X -> listof X
  ; gets a list consisting of all the elements in the gvector in order
  (define (gvector->list g)
    (let loop ((i 0))
      (cond
        [(= i (gvector-size g)) '()]
        [else (cons (vector-ref (gvector-vec g) i) (loop (add1 i)))])))
  
  ; list->gvector : listof X -> gvector of X
  ; produces a gvector with the elements of the given list in order
  (define (list->gvector l) (apply construct-gvector l))
  
  ; gvector-fill! : (gvector of X) X -> (gvector of X)
  ; updates all cells in the given gvector to be the given element. returns the gvector.
  (define (gvector-fill! g f) (begin (vector-fill! (gvector-vec g) f) g))
  
  
  )