(define-syntax import
    (syntax-rules ()
        ((_ module) (require (lib module)))
        ((_ m1 m2 ...)
            (begin
                (import m1)
                (import m2 ...)
            )
        )
    )
)

(import "string.ss" "math.ss" "awk.ss" "quasistring.ss")


(define debug (lambda (x) (begin (display x) (display "\n") x)))    ; print x and return it unmodified
(define % remainder)
(define ** expt)
(define ~ bitwise-not)
(define ^ bitwise-xor)
(define & bitwise-and)
(define None '())
(define null None)
(define nil null)
(define == =)
(define !=
    (lambda L
        (not (apply = L))
    )
)

(define bitwise-or
    ; a|b == ~((~a)&(~b))
    (lambda L
        (if (> (length L) 2)
            (apply bitwise-or
                (cons 
                    (bitwise-or (car L) (cadr L)) 
                    (cddr L)
                )
            )
            (bitwise-not
                (bitwise-and
                    (bitwise-not (car L))
                    (bitwise-not (cadr L))
                )
            )
        )
    )
)
(define || bitwise-or)

(define (ceqr symbol val)
    ; "let" for one variable -- C's "assign and return value" operator
    (eval (qs "(define $symbol val)"))
    val
)

(define (range3 bottom top step)
    (if (> (- top step) bottom)
        (cons bottom (range3 (+ bottom step) top step))
        (cons bottom '())
    )
)

(define range
    (lambda L
        (if (> (length L) 0)
            (if (> (length L) 1)
                (if (> (length L) 2)
                    (range3 (car L) (cadr L) (caddr L))
                    (range3 (car L) (cadr L) 1)
                )
                (range3 0 (car L) 1)
            )
            (range3 0 10 1)
        )
    )
)

(define list=
    (lambda Ls
        (if (> (length Ls) 2)
            (and
                (list= (car Ls) (cadr Ls))
                (apply list=
                    (cons
                        (cadr Ls)
                        (cddr Ls)
                    )
                )
            )
            (if (= (length (car Ls)) (length (cadr Ls)))
                (if (> (length (car Ls)) 1)
                    (and
                        (eq?
                            (car (car Ls))
                            (car (cadr Ls))
                        )
                        (list=
                            (cdr (car Ls))
                            (cdr (cadr Ls))
                        )
                    )
                    (eq? (car (car Ls)) (car (cadr Ls)))
                )
                #f
            )
        )
    )
)

(define (type x)
    ; use this with symbol=? to test the type of an argument
    ; returns a symbol name of the type of x
    (cond
        ((number? x) 'number)
        ((list? x) 'list)
        ((string? x) 'string)
        ((symbol? x) 'symbol)
        ((boolean? x) 'boolean)
        ((procedure? x) 'procedure)
        (else x)
    )
)

(define (reduce f L)
    ; takes a procedure [which in turn takes 2 arguments] and a list of anything
    ; returns... well, uh, (reduce + (list 1 2 3 4 5)) => (+ (+ (+ (+ 1 2) 3) 4) 5) == ((((1+2)+3)+4)+5)
    (if (> (length L) 0)
        (if (> (length L) 1)
            (if (> (length L) 2)
                (f (reduce f (cdr L)) (car L))
                (f (car L) (car (cdr L)))
            )
            (car L)
        )
        '()
    )
)

(define (append a b)
    (if (null? a)
        (if (list? b)
            b
            (cons b '())
        )
        (cons
            (car a)
            (append
                (cdr a)
                b
            )
        )
    )
)

(define list+
    (lambda Ls
        (reduce append Ls)
    )
)

(define str+
    (lambda Ss
        (if (> (length Ss) 2)
            (apply str+
                (cons
                    (str+ (car Ss) (cadr Ss))
                    (cddr Ss)
                )
            )
            (list->string
                (cat
                    (string->list (car Ss)) 
                    (string->list (cadr Ss))
                )
            )
        )
    )
)

(define (list* L n)
    (if (> n 1)
        (list+ L (list* L (- n 1)))
        L
    )
)

(define (str* s n)
    (if (> n 1)
        (str+ L (str* s (- n 1)))
        s
    )
)

(define-syntax pprint
    (syntax-rules ()
        ((_ e1) (begin (display e1) (newline)))
        ((_ e1 e2 ...) (begin (display e1) (newline) (pprint e2 ...)))
    )
)

(define (n-th L n)
    ; gets the n-th element of L [zero-based]
    (if (> n 0)
        (n-th (cdr L) (- n 1))
        (car L)
    )
)

(define index
    ; (index (range) 5) == 5
    (lambda args
        (let ((L (car args)) (obj (cadr args)))
            (if (> (length args) 2)
                (if (> (length L) 0)
                    (if (eq? (car L) obj)
                        (caddr args)
                        (if (> (length L) 1)
                            (index (cdr L) obj (+ (caddr args) 1))
                            -1
                        )
                    )
                    -1
                )
                (index L obj 0)
            )
        )
    )
)

(define (random-select L)
    (n-th
        L
        (random (- (length L) 1))
    )
)

(define (in e L)
    (if (> (length L) 0)
        (if (eq? (car L) e)
            #t
            (in e (cdr L))
        )
        #f
    )
)

(define zip
    ; (zip '(1 2) '(3 4)) => '((1 3) (2 4))
    (lambda L
        (cons (map car L)
            (if (> (length (car L)) 1)
                (apply zip (map cdr L))
                '()
            )
        )
    )
)

(define (last L) (n-th L (- (length L) 1)))

(define (gcd a b)
    ; gcd: number number ->  number
    ; to find the gcd of two numbers (Euclid's Algorithm)
    (define r (remainder a b))
    (if (= r 0)
        b
        (gcd b r)
    )
)
(define gcf gcd)

(define slice
    ; pythonic list slicing
    ; (slice (range)) == (range)
    ; (slice '(1 2 3 4 5 6) 4) == '(1 2 3 4)
    ; (slice '(1 2 3 4 5 6) 3 5) == '(4 5)
    ; (slice (range 1 10) 1 7 2) == '(2 4 6)
    ; (slice (range 1 10) (range 1 7 2)) == '(2 4 6)
    ; (slice (range) "i don't like errors") == (range)
    (lambda args
        (cond
            ((= (length args) 1) (car args))
            ((= (length args) 2)
                (cond
                    ((number? (cadr args))
                        (if (> (cadr args) 0)
                            (cons
                                (caar args)
                                (slice
                                    (cdar args)
                                    (- (cadr args) 1)
                                )
                            )
                            '()
                        )
                    )
                    ((list? (cadr args))
                        (if (> (length (cadr args)) 0)
                            (cons
                                (n-th (car args) (car (cadr args)))
                                (slice (car args) (cdadr args))    ; RECURSION HERE
                            )
                            '()
                        )
                    )
                    (else (car args))
                )
            )
            ((> (length args) 2)
                (slice
                    (car args)
                    (debug (apply range (cdr args)))
                )
            )
        )
    )
)


; pythonic any and all -- because "and" and "or" aren't really functions
(define (any L)
    (if (> (length L) 1)
        (if (car L)
            #t
            (any (cdr L))
        )
        (car L)
    )
)

(define (all L)
    (if (> (length L) 1)
        (if (not (car L))
            #f
            (all (cdr L))
        )
        (car L)
    )
)

; well, now they are :-)
(define and
    (lambda L
        (all L)
    )
)

(define or
    (lambda L
        (any L)
    )
)


(define (depth L)
    (if (= (length L) 0)
        0
        (apply max
            (map
                (lambda (elem)
                    (if (list? elem)
                        (+ (depth elem) 1)
                        1
                    )
                )
                L
            )
        )
    )
)

(define (flatten L)
    ; UNORDERED
    (if (= (depth L) 1)
        L
        (apply list+
            (map
                (lambda (e)
                    (if (list? e)
                        (flatten e)
                        (cons e '())
                    )
                )
                L
            )
        )
    )
)
;(flatten '(1 (2 3) ((4 5) 6) (((7 8) 9) 10)))

(define no-dups
    ; removes duplicate entries from first argument list.
    (lambda args    ; 1 or 2 lists
        (if (= (length args) 1)
            (no-dups (car args) '())
            (if (= (length (car args)) 0)
                (cadr args)
                (no-dups (cdar args) 
                    (if (in (caar args) (cadr args))
                        (cadr args)
                        (cons (caar args) (cadr args))
                    )
                )
            )
        )
    )
)

(define (power x)
    (if (null? x)
        (list x)
        (append
            (power (cdr x))
            (map
                (lambda (L)
                    (cons (car x) L)
                )
                (power (cdr x))
            )
        )
    )
)

; DICT
(define dict
    ; list of cons cells -- (key . value)
    (lambda L
        (if (> (length L) 1)
            (dict L)
            L    ; XXX what do i want to do here?
        )
    )
)

(define (dict-set d k v)
    (if (dict-contains k)
        (if (eq? (caar d) k)
            (cons
                (cons k v)
                (cdr d)
            )
            (cons
                (caar d)
                (dict-set (cdr d) k v)
            )
        )
        (cons (cons k v) d)
    )												
)

(define (dict-get d k)
    ; iterative -- NOT HASH MAP
    (if (eq? k (caar d))
        (cdar d)
        (dict-get (cdr d) k)
    )
)

(define (dict-contains d k)
    (cond
        ((null? d) #f)
        ((= (length d) 1) (eq? (caar d) k))
        (else
            (if (eq? (caar d) k)
                #t
                (dict-contains (cdr d) k)
            )
        )
    )
)

(define (dict-keys d)
    (if (null? d)
        d
        (cons
            (caar d)
            (dict-keys (cdr d))
        )
    )
)

(define (dict-values d)
    (if (null? d)
        d
        (cons
            (cdar d)
            (dict-values (cdr d))
        )
    )
)

(define (dict-merge a b)
    (if (null? b)
        a
        (dict-merge
            (dict-set a (caar b) (cdar b))
            (cdr b)
        )
    )
)
; DICT

(define assert
    (lambda args
        (if (car args)
            (car args)
            (error
                (if (> (length args) 1)
                    (cadr args)
                    "AssertionError"
                )
            )
        )
    )
)