Commits

Joby Poriyath committed be9d593

stack implementation using array

  • Participants
  • Parent commits f43b8ba

Comments (0)

Files changed (12)

+#load "unix.cma";;
 #directory "_build";;
 #load "util.cmo";;
-#load "unix.cma";;
+#load "misc.cmo";;
+
 ocamlbuild -classic-display -lib unix echo.native
 ocamlbuild -classic-display main.byte
 ocamlbuild -classic-display main.native
+ocamlbuild -classic-display -lib unix find.byte
+ocamlbuild -classic-display -lib unix find.native
+ocamlbuild -classic-display test_stk.byte
+ocamlbuild -classic-display test_stk.native
 
+open Unix
+
+(* 
+   The funtion call 
+   
+   find handler action follow depths roots
+
+   traverses the file hierarchy starting from roots specified in the list __roots__ (absolute or
+   relative to the current working directory of the process when the call is made) up to a
+   maximum of depth __depth__ and follow the symbolic links if flag __follow__ is set.
+   The paths found under root r include r as a prefix. Each found path p is given to the function
+   __action__ along with the data returned by Unix.lstat p (or Unix.stat p if follow is true). 
+   The function __action__ returns a boolean indicating, for directories, whether the search 
+   should continue for its contents (true) or not (false).
+
+   The __handler__ function reports traversal errors of type Unix.error. Whenever an error occurs
+   the arguments of the exception are given to the __handler__ function and the traversal continues.
+   However, when an exception is raised by function __action__ or the __handler__ themselves, we
+   immediately stop the traversal and let it propogate to the caller.
+*)
+
+exception Hidden of exn
+
+let hide_exn f x = try f x with exn -> raise (Hidden exn)
+let reveal_exn f x = try f x with Hidden exn -> raise exn
+
+let find on_error on_path follow depth roots =
+  let rec find_rec depth visiting filename =
+    try
+      let infos = (if follow then stat else lstat) filename in
+      let continue = hide_exn (on_path filename) infos in
+      let id = infos.st_dev, infos.st_ino in
+      if infos.st_kind = S_DIR && depth > 0 && continue && (not (List.mem id visiting))
+      then 
+        let process_child child = 
+          if (child <> Filename.current_dir_name &&
+                child <> Filename.parent_dir_name)
+          then 
+            let child_name = Filename.concat filename child in
+            let visiting = id :: visiting in
+            find_rec (depth - 1) visiting child_name in
+        Misc.iter_dir process_child filename
+    with Unix_error (e, b, c) -> hide_exn on_error (e, b, c) in
+  reveal_exn (List.iter (find_rec depth [])) roots
+          
+    
+let main () =
+  let follow = ref false in
+  let max_depth = ref max_int in
+  let roots = ref [] in
+  let usage_string = 
+    ("Usage: " ^ Sys.argv.(0) ^ " [options...] [files...]") in
+  let opt_list = [
+    "-maxdepth", Arg.Int ((:=) max_depth), "max depth search";
+    "-follow", Arg.Set follow, "follow symbolic links"] in
+  Arg.parse opt_list (fun f -> roots := f :: !roots) usage_string;
+  let action p infos = print_endline p; true in
+  let errors = ref false in
+  let on_error (e, b, c) = 
+    errors := true; prerr_endline (c ^ ": " ^ Unix.error_message e) in
+  find on_error action !follow !max_depth
+    (if !roots = [] 
+     then [Filename.current_dir_name]
+     else List.rev !roots);
+  if !errors then exit 1
+
+let _ = Unix.handle_unix_error main ()
+val find : 
+  (Unix.error * string * string -> unit) ->
+  (string -> Unix.stats -> bool) ->
+  bool ->
+  int -> 
+  string list ->
+  unit
 let try_finalize f x finally y = 
   try f x 
   with exn -> ignore (finally y); raise exn
+
+let iter_dir f dirname = 
+  let d = Unix.opendir dirname in
+  try
+    while true do
+      ignore (f (Unix.readdir d))
+    done
+  with End_of_file -> Unix.closedir d
 val handle_unix_error : ('a -> 'b) -> 'a -> 'b
 val try_finalize : ('a -> 'b) -> 'a -> ('c -> 'd) -> 'c -> 'b
 val restart_on_EINTR : ('a -> 'b) -> 'a -> 'b
+val iter_dir : (string -> 'a) -> string -> unit
-type 'a t = {mutable c : 'a list}
-exception Stk_empty
-  
-let create () = {c = []}
-
-let push e st = st.c <- e :: st.c
+type 'a t = {mutable c : 'a array;
+             mutable sp: int}
 
-let pop st = match st.c with
-  | hd :: tl -> st.c <- tl; hd
-  | [] -> raise Stk_empty
+exception Stack_empty
 
-let iter f st = List.iter f st.c
+let create () = {c = [||]; sp = 0}
 
-let length st = List.length st.c
+let resize_array st a =
+  let new_size =
+    let len = Array.length st.c in
+    if len > 0 then 2 * len else 1 
+  in
+  let new_array = Array.make new_size a in
+  Array.blit st.c 0 new_array 0 (Array.length st.c);
+  st.c <- new_array
     
-let is_empty st = (st.c = [])
+let push st a = 
+  if Array.length st.c = st.sp then resize_array st a else ();
+  st.c.(st.sp) <- a;
+  st.sp <- st.sp + 1
+
+let shrink st =
+  let len = Array.length st.c in
+  if len <= 1
+  then st.c <- [||]
+  else 
+    let new_array = Array.make (len / 2) st.c.(0) in
+    Array.blit st.c 0 new_array 0 st.sp;
+    st.c <- new_array
+  
+let pop st = 
+  if st.sp = 0 
+  then raise Stack_empty
+  else
+    st.sp <- st.sp - 1;
+    let e = st.c.(st.sp) in
+    if Array.length st.c >= (3 * st.sp) 
+    then shrink st
+    else ();
+    e
+
+let is_empty st = (st.sp = 0)
+
+let iter f st =
+  for i = (st.sp - 1) downto 0
+  do
+    f st.c.(i)
+  done
 type 'a t
-
-exception Stk_empty
-
+exception Stack_empty
 val create : unit -> 'a t
-val push : 'a -> 'a t -> unit
+val push : 'a t -> 'a -> unit
 val pop : 'a t -> 'a
-val length : 'a t -> int
+val is_empty : 'a t -> bool
 val iter : ('a -> unit) -> 'a t -> unit
+push 1
+push 2
+push 3
+pop
+pop
+let main () =
+  let st = Stk.create () in
+  let rec loop () =
+    match Util.read_line () with
+      | None -> ()
+      | Some line -> 
+        begin
+          let args = Array.of_list (Util.split line) in
+          match args.(0) with
+            | "push" -> Stk.push st (int_of_string args.(1)); loop ()
+            | "pop" -> 
+              begin
+                try 
+                  print_endline (string_of_int (Stk.pop st)) ; loop ()
+                with Stk.Stack_empty -> loop ()
+              end
+            | cmd -> ignore(failwith ("invalid argument " ^ cmd))
+        end
+  in
+  loop ()
+
+let _ = main ()             
   match Random.bool () with
     | true -> Random.int n
     | false -> -1 * (Random.int n)
+      
+let rec read_line () =
+  try 
+    let line = String.trim (input_line stdin) in
+    if line = "" then read_line () 
+    else if startswith line "#" 
+    then read_line ()
+    else Some line
+  with End_of_file -> None 
+
 
 let _ = Random.self_init ()
 
 val range : int -> int list
 val binary_search : 'a array -> 'a -> int
 val time_it : ('a -> 'b) -> 'a -> float * 'b
+val read_line : unit -> string option
 val random_int : int -> int