First Post

The point of this blog is just to get me to write some code every day. If I miss a few days I will try to make several posts. Probably this blog will not be much fun to read regularly, but posting it publicly gives some sense of accountability.

It'll be in Lisp, Ocaml, or whatever I feel like learning.

Today's code is an ocaml priority queue. I might improve it a bit for the next couple of days.

(* This is just a placeholder for real tasks. *)
type task = Task

type priority_queue = {mutable tasklist: (task * float) option array; mutable next: int}

let new_priority_queue = {tasklist = Array.make 2 None; next = 1}

let rec sift_up place pq =
  if (place > 1) then match (pq.tasklist.(place), pq.tasklist.(place/2)) with
      (None, p) -> ()
    | (Some (t1,f1), Some (t2,f2)) when f1 <= f2 -> ()
    | (Some (t1,f1), Some (t2,f2)) when f1 > f2 ->
        pq.tasklist.(place)   <- Some (t2, f2);
        pq.tasklist.(place/2) <- Some (t1, f1);
        sift_up (place/2) pq;
    | (q, r) -> raise (Invalid_argument "sift_up");;

let double_size pq =
  pq.tasklist <- Array.append pq.tasklist (Array.make (Array.length pq.tasklist) None);;

let push_item item priority pq =
  (if not (pq.next < Array.length pq.tasklist) then double_size pq);
  pq.tasklist.(pq.next) <- Some (item, priority);
  sift_up pq.next pq;
  pq.next <- (pq.next + 1);;

let rec sift_down place pq =
  if place*2 < Array.length pq.tasklist then
    if place*2+1 < pq.next then
      let (largervalue,largerplace) =
        (match (pq.tasklist.(place*2), pq.tasklist.(place*2+1)) with
            (Some (t1,f1), Some (t2,f2)) when f1 < f2 -> (f2,place*2+1)
          | (Some (t1,f1), Some (t2,f2))              -> (f1,place*2)
          | _ -> raise (Invalid_argument "sift_down") )
        in
          match pq.tasklist.(place) with
              Some (t,f) when f < largervalue ->
                (pq.tasklist.(place) <- pq.tasklist.(largerplace);
                pq.tasklist.(largerplace) <- Some (t,f);
                sift_down largerplace pq )
            | Some (t,f) -> ()
            | _ -> raise (Invalid_argument "sift_down")
    else if place*2 < pq.next then
      match pq.tasklist.(place) with
          Some (t,f) when f < (match pq.tasklist.(place*2) with Some (t,f) -> f | _ -> 0.0) ->
            (pq.tasklist.(place) <- pq.tasklist.(place*2);
            pq.tasklist.(place*2) <- Some (t,f) )
        | Some (t,f) -> ()
        | _ -> raise (Invalid_argument "sift_down");;


let pop_item pq =
  let result = pq.tasklist.(1) in
    pq.tasklist.(1) <- pq.tasklist.(pq.next-1);
    pq.tasklist.(pq.next-1) <- None;
    if pq.next > 1 then pq.next <- pq.next-1;
    sift_down 1 pq;
    result;;