;;Exercise 4

(define-struct page [title content])

; A Wiki is a [List-of Page]
; A Page is a (make-page Symbol [List-of Symbol])
; INTERPRETATION: An individual page contains a title and a
; list of links to other pages (represented by their titles).

(define P0 (make-page 'dead-end '()))

(define PA (make-page 'a (list 'b)))
(define PB (make-page 'b (list 'c)))
(define PC (make-page 'c (list 'd)))
(define PD (make-page 'd (list 'a)))
(define PD2 (make-page 'd '()))

(define P1 (make-page 'a (list 'b 'c)))
(define P2 (make-page 'b (list 'd )))
(define P3 (make-page 'c (list 'b 'a)))
(define P4 (make-page 'd '()))

(define W0 '())
(define W1 (list P0))
(define W2 (list PA PB PC PD))
(define W3 (list P1 P2 P3 P4))
(define W4 (list PA PB PC PD2))

;;Checks if a cycle exists in a given Wiki
;; cycle? : Wiki -> Boolean
(check-expect (cycle? W0) #false)
(check-expect (cycle? W1) #false)
(check-expect (cycle? W2) #true)
(check-expect (cycle? W3) #true)
(check-expect (cycle? W4) #false)

(define PAGE-1 (make-page 'A (list 'B 'C)))
(define PAGE-2 (make-page 'B (list 'A)))
(define PAGE-3 (make-page 'C '()))
(define PAGE-4 (make-page 'D '()))
(define PAGE-5 (make-page 'B '()))
(define PAGE-6 (make-page 'C (list 'D)))
(define PAGE-7 (make-page 'B '()))
(define PAGE-8 (make-page 'C (list 'D 'A)))
(define PAGE-9 (make-page 'B (list 'D)))
(define PAGE-10 (make-page 'C (list 'A)))
(define PAGE-11 (make-page 'A (list 'A 'B 'C 'E 'T)))
(define PAGE-12 (make-page 'B (list 'B 'C 'D 'F)))
(define PAGE-13 (make-page 'C (list 'D 'E 'F 'T 'R)))
(define PAGE-14 (make-page 'D (list 'A 'B 'F)))

(define WIKI-1 (list PAGE-1 PAGE-2 PAGE-3 PAGE-4))
(define WIKI-2 (list PAGE-1 PAGE-5 PAGE-6 PAGE-4))
(define WIKI-3 (list PAGE-1 PAGE-7 PAGE-8 PAGE-4))
(define WIKI-4 (list PAGE-1 PAGE-9 PAGE-10 PAGE-4))
(define WIKI-5 (list PAGE-11 PAGE-12 PAGE-13 PAGE-14))

(check-expect (cycle? '()) #false)
(check-expect (cycle? (list PAGE-1)) #false)
(check-expect (cycle? (list (make-page 'A (list 'B 'A)))) #true)
(check-expect (cycle? WIKI-1) #true)
(check-expect (cycle? WIKI-2) #false)
(check-expect (cycle? WIKI-3) #true)
(check-expect (cycle? WIKI-4) #true)
(check-expect (cycle? WIKI-5) #true)

(define (cycle? w)
  (local ((define (page-connected? p)
           (connected? (page-title p) (page-title p) w)))

  (ormap page-connected? w)))

;; Page Page Wiki -> Boolean
(define (connected? from to W)
  (local (;;Page Wiki -> [List-of Symbol]
          ;;Gets list of out-links from certain page in wiki
          (define (lookup p W)
            (cond
              [(empty? W) '()]
              [(cons? W)
               (if (symbol=? (page-title (first W)) p)
                   (page-content (first W))
                   (lookup p (rest W)))]))

          (define from-links (lookup from W))

          (define is-to-in-links (member? to from-links))
          ;; Symbol -> Boolean
          (define (redefine-connected new-from)
            (if (symbol=? from new-from)
                #false
                (connected? new-from to (remove-out-links W new-from)))))
    (if is-to-in-links
        #true
        (ormap redefine-connected from-links))))

;;Wiki Symbol -> Wiki
(define (remove-out-links w s)
  (local (;;Symbol -> Boolean
          (define (should-keep? out-link)
            (not (symbol=? out-link s)))
          ;;Page -> Page
          (define (filter-out-links p)
            (make-page (page-title p) (filter should-keep? (page-content p)))))
    (map filter-out-links w)))

;;Exercise 5

(define-struct node [left right])
; A TreeOutline is one of
; - 'leaf
; - (make-node TreeOutline TreeOutline)


(define TREE1 'leaf)
(define TREE2 (make-node 'leaf 'leaf))
(define TREE3 (make-node (make-node 'leaf 'leaf) 'leaf))
(define TREE4 (make-node (make-node 'leaf 'leaf)
                         (make-node (make-node 'leaf
                                               (make-node 'leaf 'leaf))
                                    'leaf)))

(check-expect (all-trees-of-size 0) (list 'leaf))
(check-expect (all-trees-of-size 1) (list (make-node 'leaf 'leaf)))
(check-expect (all-trees-of-size 2) (list (make-node 'leaf (make-node 'leaf 'leaf))
                                          (make-node (make-node 'leaf 'leaf) 'leaf)))
(check-expect (all-trees-of-size 3) (list
                                     (make-node 'leaf (make-node 'leaf (make-node 'leaf 'leaf)));; 0-2
                                     (make-node 'leaf (make-node (make-node 'leaf 'leaf) 'leaf));; 0-2
                                     (make-node (make-node 'leaf 'leaf) (make-node 'leaf 'leaf));; 1-1
                                     (make-node (make-node 'leaf (make-node 'leaf 'leaf)) 'leaf);; 2-0
                                     (make-node (make-node (make-node 'leaf 'leaf) 'leaf) 'leaf)));2-0

(check-expect (length (all-trees-of-size 4)) 14)
(check-expect (length (all-trees-of-size 5)) 42)
(check-expect (length (all-trees-of-size 6)) 132)

;;Natural -> [List-of TreeOutline]
(define (all-trees-of-size n)
  (cond
    [(= n 0) (list 'leaf)]
    [else
     (local [(define LEFT (build-list n all-trees-of-size))
             (define RIGHT (reverse LEFT))]
       (foldr append '() (map merge-treeoutlines LEFT RIGHT)))]))

;; [List-of TreeOutline] [List-of TreeOutline] -> [List-of TreeOutline]
;;Merges two [List-of TreeOutline] into one by taking the "cross product" of the them.
;;They are combined by (make-node TreeOutline TreeOutline)
(check-expect (merge-treeoutlines '() '()) '())
(check-expect (merge-treeoutlines '() (list 'leaf)) '())
(check-expect (merge-treeoutlines (list 'leaf) '()) '())
(check-expect (merge-treeoutlines (list 'leaf) (list 'leaf)) (list (make-node 'leaf 'leaf)))
(check-expect (merge-treeoutlines (list (make-node 'leaf 'leaf))
                                  (list (make-node 'leaf (make-node 'leaf 'leaf))
                                        (make-node (make-node 'leaf 'leaf) 'leaf)))
              (list
               (make-node (make-node 'leaf 'leaf) (make-node 'leaf (make-node 'leaf 'leaf)))  ;; 1-2
               (make-node (make-node 'leaf 'leaf) (make-node (make-node 'leaf 'leaf) 'leaf))));; 1-2

(define (merge-treeoutlines aloto1 aloto2)
  (local (;;Combines given TreeOutlone from map to given [List-of TreeOutline]
          ;;It combines each with (make-node TreeOutline TreeOutline).
          ;;TreeOutline -> [List-of TreeOutline]
          (define (combine map-ato)
            (merge-treeoutline aloto1 map-ato)))
    (foldr append '() (map combine aloto2))))

;;[List-of TreeOutline] TreeOutline -> [List-of TreeOutline]
;;Merges a [List-of TreeOutline] with TreeOutline by adding a node
;;to the "top". It used (make-node TreeOutline TreeOutline)

(check-expect (merge-treeoutline '() 'leaf) '())
(check-expect (merge-treeoutline (list (make-node 'leaf (make-node 'leaf 'leaf))
                                       (make-node (make-node 'leaf 'leaf) 'leaf )) 'leaf)
              (list
               (make-node (make-node 'leaf (make-node 'leaf 'leaf)) 'leaf)  ;; 2-0
               (make-node (make-node (make-node 'leaf 'leaf) 'leaf) 'leaf)));; 2-0
(define (merge-treeoutline aloto ato)
  (local (;;Combines given TreeOutline with TreeOutline from map
          ;;TreeOutline -> TreeOutline
          (define (combine map-ato)
            (make-node map-ato ato)))
    (map combine aloto)))