Subj : Re: stacking algorithm
To   : comp.programming
From : Jon Harrop
Date : Thu Aug 04 2005 01:37 am

nobiscuit wrote:
> I figure this has to be a pretty common problem.  I did a google search
> but didn't find anything.  Can anyone suggest an algorithm which is
> similar or does anyone have any cunning suggestions for an algorithm?

It isn't too cunning, but what about trying to insert each line in turn into
the current stack + one empty line?

Let's see. Here are some functions to test for intersection:

  let intersect (s1, e1) (s2, e2) = not (s1>=e2 || s2>=e1);;
  let intersects line lines = List.exists (intersect line) lines;;

Here is a function to insert a new line into a stack:

  let rec insert line = function
      [] -> [[line]]
    | lines :: stack ->
        if intersects line lines then
          lines :: insert line stack
        else
          (line :: lines) :: stack;;

Here are some functions to print a stack:

  let mem x (s, e) = if s<=x && x<e then true else false;;
  let range = List.fold_left (fun accu (_, e) -> max e accu) 0;;
  let string_of_lines lines =
    let aux x = List.fold_left ( || ) false (List.map (mem x) lines) in
    let l = Array.to_list (Array.init (range lines) aux) in
    String.concat "" (List.map (function true -> "x" | false -> " ") l);;
  let string_of_stack stack =
    String.concat "\n" (List.map string_of_lines stack);;

The stack is computed by folding our insert function over the lines,
accumulating the resulting stack:

  let random_line _ =
    (fun s -> (s, s+1+Random.int (40-s))) (Random.int 39);;
  let lines = Array.to_list (Array.init 30 random_line);;
  let stack = List.fold_right insert lines [];;
  print_endline (string_of_stack stack);;

The result is:

  xxxxxxxxxxxxxxxxxxx xxxxxx  xxxxxxx
          xxxxxxxxxxxxxxxxxxxxxxxxxxx
     xxxxxxxxxxxxx xxxxxxxxxxxxx    x
        xxxxxxxxxxxx  xxxxxxxxxxxxxx
           xxxxx        xxxxxxx
   xxxxxxxxx          xxxxx   xxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
                      xxxxxxxxxxxx
     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
    xxxxxxxxxxxxxxxxxxxxxxxxxxxx
                         xxxxxx
                    xxxxxx
                       xxxxxxxxxx
        xxxxxxxxxxxxxxxxxxxxx
            xxxxxxxxxxxxxxxxxx
            xxxxxxxxxxxxxxxxxxxx
                      xxxxxxx
                      xxxxxxxxxxxxx
                 xxxxxxxxxxxx

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.