(* Continuations 
   Course: COMP 302: Programming Languages and Paradigms
   Author: Brigitte Pientka 
*) 

(* Direct-style append 
   append: 'a list * 'a list -> 'a list 
*)
fun append(nil, k) = k
  | append(h::t, k) = h::(append(t,k))

(* Continuation-style append with the use
   of the continuation-style function 
   app_tr: 'a list * 'a list * ('a list -> 'a list) -> 'a list *)
fun app_tr (l1, l2) = 
  let
    fun app' (nil, l, c) = c l
      | app' (h::t, l, c) = 
      app' (t, l, (fn r => c (h::r)))
  in
    app' (l1, l2 , fn r => r)
  end




(* Traversing a tree and finding an element *)

datatype 'a tree = 
  Empty | Node of 'a tree * 'a * 'a tree


fun find(p, Empty) = NONE
  | find(p, Node(L, d, R)) = 
   if  (p d) then SOME(d) 
   else 
      (case find(p, L) of
	 NONE => find(p, R)
       | SOME(d') => SOME(d'))


fun find_tr(p, Empty, cont) = cont ()
  | find_tr(p, Node(L, d, R), cont) = 
  if (p d) then SOME(d)
    else find_tr(p, L, fn () => find_tr(p, R, cont))

fun find' (p,t) = 
  find_tr (p, t, fn () => NONE)

(* val l1 = Node (Node (Empty,3,Empty),5,Node (Empty,7,Empty))

   val t = Node(Node (Node (Empty,3,Empty),5,Node (Empty,7,Empty)), 
                Node(Empty, 15, Empty)) 
  

  val p = (fn x => x = 15)

    find_tr(p, t, fn () => NONE) 
--> find_tr(p, l1, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE))
                         ------ work we still may need to do on the right ---

--> find_tr(p, Node (Empty,3,Empty), fn () => find_tr(p, Node(E, 7, E), ....))

--> find_tr(p, Empty, fn () => find_tr(p, Empty, fn () => find_tr(p, Node(E, 7, E), ....))

--> (fn () => find_tr(p, Empty, fn () => find_tr(p, Node(E, 7, E), ....)) ()     *** pop the stack ! ***


--> find_tr(p, Node(E, 7, E), fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE))

--> find_tr(p, E, fn () => find_tr(p, Empty, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE))

    (***** pop the last element of the stack! ***)
--> (fn () => find_tr(p, Empty, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE))) ()

---> find_tr(p, Empty, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE))

--> (fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE)) ()

--> find_tr(p, Node(Empty, 15, Empty), fn () => NONE

--> SOME(15)

*)


fun findAll (p, Empty) = []
  | findAll (p, Node(L,d,R)) = 
  if (p d) then findAll(p,L)@[d]@findAll(p,R)
    else
      (case findAll(p,L) of
	 [] => findAll(p,R)
       | el' => (el')@[d]@findAll(p,R))


fun findAll' (p, Empty, sc) = sc []
  | findAll' (p, Node(L,d,R), sc) = 
  if (p d) then findAll' (p, L, fn el => findAll'(p,R, fn er => sc (el@(d::er))))
    else 
      findAll' (p, L, fn el => findAll' (p, R, fn er => sc (el@er)))


fun findEvery (p,T) = findAll'(p,T, fn el => case el of nil => NONE | _ => SOME(el))



fun findAll2 (p, Empty, sc) = sc []
  | findAll2 (p, Node(L,d,R), sc) = 
    findAll2 (p, L, 
 	     fn el => findAll2(p, R, 
	       (fn er => let val cl = if p d then el@(d::er) else el @ er
			in sc cl end)))
;

fun findEvery2 (p,T) = findAll2 (p,T, fn el =>  el)

val L = Node (Node (Empty, 2, Empty), 5, Node (Empty, 6, Empty));
val R = Node (Empty, 12, Empty);
val T = Node (Node (L, 7, Node (Empty, 8, Empty)), 11, R);

fun even x = (x mod 2) = 0 
fun odd x = (x mod 2) = 1 

val l = findEvery (even , T)
val l' = findEvery2 (even , T)
val r = findEvery (odd , T)
val r' = findEvery2 (odd , T)
(* ---------------------------------------------------------------------------- *)