#lang racket
(provide ins_beg)

(define (ins_beg el lst)
  (cons el lst)
)

(provide ins_end)

(define (ins_end el lst)
  (append lst (list el))
  )

(provide count_top_level)

(define (count_top_level li)
  (length li)
  )

(provide count_instances)

(define (count_instances el lst)
  (if (null? lst)
      0
      (if (equal? (car lst) el)
          (+ 1 (count_instances el (cdr lst)))
          (count_instances el (cdr lst))
          )
      )
  )

(provide count_instances_tr)
(provide count_tr)

(define (count_instances_tr el lst)
  (count_tr el lst 0)
  )

(define (count_tr el lst total)
  (if (null? lst)
      total
      (if (equal? (car lst) el)
          (count_tr el (cdr lst) (+ 1 total))
          (count_tr el (cdr lst) total)
          )
      )
  )

(provide count_instances_deep)
(provide count_deep)

(define (count_instances_deep el lst)
  (count_deep el lst 0)
  )

(define (count_deep el lst total)
  (if (null? lst)
      total
      (begin
      (when (list? (car lst))
          (set! total (+ total (count_instances_deep el (car lst))))
          )
      (if (equal? (car lst) el)
          (count_deep el (cdr lst) (+ 1 total))
          (count_deep el (cdr lst) total)
          )
      )
      )
  )

; A list without the last element
; Essentially the opposite of cdr
(define (rdc lst)
  (reverse (cdr (reverse lst)))
  )

; Function reate new empty tree with a given value as its root
(define (Tree value)
  (list '() value '())
  )

; Begin with an empty tree
(define root '())

; Helper function for insert_tree
; Let the root equal the new tree with the inserted value
(define (insert value)
  (set! root (insert_tree value root))
  )

; Insert new value into the tree
(define (insert_tree value tree)
  (if (null? tree)
      ; If the tree is empty make a new tree with the given value as its root
      (Tree value)
      ; Else check whether the given value is less than the root
      (if (< value (cadr tree))
          ; If the given value is less than the current root:
          (if (null? (car tree))
              ; If the left subtree is empty, create a new left subtree with its given value
              (cons (Tree value) (cdr tree))
              ; Else recursively call insert_tree on the left subtree and add the result of that the new left subtree
              (cons (insert_tree value (car tree)) (cdr tree))
              )
          ; Else the given value is greater than the current root:
          (if (null? (caddr tree))
              ; If the right subtree is empty, create a new right subtree with its given value
              (append (rdc tree) (list (Tree value)))
              ; Else recursively call insert_tree on the right subtree and add the result of that the new right subtree
              (append (rdc tree) (list (insert_tree value (caddr tree))))
              )
          )
      )
  )

; Helper function for inorder_traversal
(define (traverse)
  (begin
    (printf "Beginning inorder traversal...\n")
    (inorder_traversal root)
    )
  )

; Traverses a given tree
(define (inorder_traversal tree)
  (when (not (null? tree))
    ; When the tree isn't empty
      (begin
        ; Traverse left subtree
        (inorder_traversal (car tree))
        ; Print value
        (printf "~a " (cadr tree))
        ; Traverse right subtree
        (inorder_traversal (caddr tree))
        )
    )
  )

; Global variable to check if item is found
(define found #f)
; Helper function for search_tree
(define (search item tree)
  ; Set found to false each time something is searched
  (set! found #f)
  (begin
    ; Search tree for item
    (search_tree item tree)
    ; Display value of global variable found
    (display found)
    )
  )

; Recursively search given tree for a given item
(define (search_tree item tree)
  ; If given tree is not empty
  (when (not (null? tree))
    (if (equal? item (cadr tree))
        ; If value of current tree is equal to the item being searched for, set global variable found to true
        (set! found #t)
        ; Else search left and right subtrees
        (begin
          (search_tree item (car tree))
          (search_tree item (caddr tree))
          )
        )
    )
  )

; Inserts given list into binary search tree
(define (insert_list lst)
  ; Checks that list is not empty
  (when (not (null? lst))
    ; Adds first item to binary tree and recurses using the remaining list
    (begin
      (insert (car lst))
      (insert_list (cdr lst))
    )
    )
  )

;(insert_list '(8 4 2 6 12 14 10))

; Insert list into tree and then traverse it inorder
(define (sort lst)
  (set! root '())
  (begin
    (insert_list lst)
    (traverse)
    )
  )