; A file is a symbol.

; file? : any -> boolean
; predicate for files
(defile (file? any)
  (symbol? any))

; A directory is a structure
;   (make-dir name contents)
; where name is a symbol, and contents is a l-o-f-d.
(define-struct dir (name contents))

; A list-of-files-and-directories (l-o-f-d) is one of
; - empty
; - (cons f lofd)
;   where f is a file, and lofd is a l-o-f-d
; - (cons d lofd)
;   where d is a directory, and lofd is a l-o-f-d.

;;;;;;;;;;;;;;;;;;;;;;;;
; Templates

;(define (dir-fn a-dir)
;  ...(dir-name a-dir)...
;  ...(lofd-fn (dir-contents a-dir))...)

;(define (lofd-fn a-lofd)
;  (cond
;    [(empty? a-lofd)
;     ...]
;    [(file? (first a-lofd))
;     ...(first a-lofd)...(lofd-fn (rest a-lofd))...]
;    [(dir? (first a-lofd))
;     ...(dir-fn (first a-lofd))...(lofd-fn (rest a-lofd))...]))


;;;;;;;;;;;;;;;;;;;;;;;;

; find? : directory file -> boolean
; returns whether the given file is in the directory or one of its subdirs
(define (find? a-dir a-file)
  (find-lofd? (dir-contents a-dir) a-file))

; find-lofd? : l-o-f-d file -> boolean
; returns whether the given file is in the l-o-f-d or one of its subdirs
(define (find-lofd? a-lofd a-file)
  (cond
    [(empty? a-lofd)
     false]
    [(file? (first a-lofd))
     (or (symbol=? (first a-lofd) a-file)
	 (find-lofd? (rest a-lofd) a-file))]
    [(dir? (first a-lofd))
     (or (find? (first a-lofd) a-file)
	 (find-lofd? (rest lofd) a-file))]))

;;;;;;;;;;;;;;;;;;;;;;;;

; flatten-dir-once : directory symbol -> (directory or l-o-d-f)
; removes the named subdirectory, moving its contents up one level
(define (flatten-dir-once a-dir name)
  (cond
    [(symbol=? (dir-name a-dir) name)
     (dir-contents a-dir)]
    [else
     (make-dir (dir-name a-dir)
               (flatten-dir-once-in-lodf (dir-contents a-dir) name))]))

; flatten-dir-once-in-lodf : l-o-d-f symbol -> l-o-d-f
; removes the named subdirectory, moving its contents up one level
(define (flatten-dir-once-in-lodf a-lodf name)
  (cond
    [(empty? a-lodf)        empty]
    [(file? (first a-lodf)) (cons (first a-lodf)
				  (flatten-dir-once-in-lodf (rest a-lodf) name))]
    [(dir? (first a-lodf))  (flatten-helper
			      (flatten-dir-once (first a-lodf) name)
			      (flatten-dir-once-in-lodf (rest a-lodf) name))]))

; flatten-helper : (directory or l-o-d-f) l-o-d-f -> l-o-d-f
; combines (an item or list) and a list into a new list
(define (flatten-helper a-dir-or-lodf a-lodf)
  (cond [(dir? a-dir-or-lodf) (cons a-dir-or-lodf a-lodf)]
	[else                 (append a-dir-or-lodf a-lodf)]))

;;;;;;;;;;;;;;;;;;;;;;;;

; any-duplicate-names? : directory -> boolean
; Returns whether any directory directly or indirectly contains
; another directory or file of the same name.  It does NOT check
; for duplicated names in separate branches of the tree.
(define (any-duplicate-names? a-dir)
  (or (find? (dir-contents a-dir) (dir-name a-dir))
      (any-duplicate-names-lofd? (dir-contents a-dir))))

; any-duplicate-names-lofd? : l-o-f-d -> boolean
; Returns whether any directory in the list directly or indirectly contains
; another directory or file of the same name.  It does NOT check
; for duplicated names in separate branches of the tree.
(define (any-duplicate-names-lofd? a-lofd)
  (cond
    [(empty? a-lofd)
     false]
    [(file? (first a-lofd))
     false]
    [(dir? (first a-lofd))
     (or (any-duplicate-names? (first a-lofd))
	 (any-duplicate-names-lofd? (rest a-lofd)))]))