home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / ipl / progs / bfd.icn < prev    next >
Text File  |  2000-07-29  |  3KB  |  121 lines
  1. ############################################################################
  2. #
  3. #    File:     bfd.icn
  4. #
  5. #    Subject:  Program to compute best-fit-descending bin packing
  6. #
  7. #    Author:   Gregg M. Townsend
  8. #
  9. #    Date:     December 4, 1996
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #
  17. #  Usage:  bpack binsize [options] [file]
  18. #
  19. #  Input:  one entry per line, size in decimal followed by anything else
  20. #       (anything else presumably being a file name or something)
  21. #
  22. #  Output: all the input lines, unchanged but reordered,
  23. #       with an empty line before each bin and a total afterward
  24. #
  25. #  Options:
  26. #    -t    don't output anything except unannotated totals
  27. #    -n    don't output anything except the *number* of bins
  28. #    -b i    don't output anything except the details from bin i
  29. #
  30. ############################################################################
  31. #
  32. #  Links:  options
  33. #
  34. ############################################################################
  35.  
  36. #  possible options to add later: optional quantization and padding values
  37. #    (e.g. to use with tar(1) you'd need it to round up to the next
  38. #    128 bytes and add 128 bytes for each file header -- or whatever)
  39.  
  40.  
  41. link options
  42.  
  43. record obj(size,detail)
  44.  
  45. global opts, binsize
  46.  
  47. procedure main(args)
  48.    local ifile, line, n, d
  49.    local objlist, bins, o, b
  50.  
  51.    opts := options(args, "tnb+")
  52.  
  53.    binsize := integer(args[1]) | stop("usage: ", &progname, " binsize")
  54.  
  55.    if *args > 1 then
  56.       ifile := open(args[2]) | stop("can't open ", args[2])
  57.    else
  58.       ifile := &input
  59.  
  60.    objlist := []
  61.    while line := read(ifile) do line ? {
  62.       tab(many(' \t'))
  63.       n := integer(tab(many(&digits))) | next
  64.       tab(many(' \t'))
  65.       d := trim(tab(0), ' \t')
  66.       put(objlist, obj(n, d))
  67.       }
  68.  
  69.    objlist := sortf(objlist, 1)
  70.  
  71.    bins := []
  72.    while o := pull(objlist) do {
  73.       n := bestfit(bins, o.size)
  74.       put(bins[n].detail, o)
  75.       bins[n].size +:= o.size
  76.    }
  77.  
  78.    if \opts["n"] then {
  79.       write(*bins)
  80.       return
  81.    }
  82.  
  83.    if \opts["t"] then {
  84.       every write((!bins).size)
  85.       return
  86.    }
  87.  
  88.    if n := \opts["b"] then {
  89.        b := bins[n] | stop("no bin ", n, "; only " *bins, " bins")
  90.        every write((!b.detail).detail)
  91.        return
  92.    }
  93.  
  94.    while b := get(bins) do {
  95.       write()
  96.       while o := get(b.detail) do
  97.          write(right(o.size, 12), "\t", o.detail)
  98.       write(right(b.size, 12), "\t--total--")
  99.       }
  100. end
  101.  
  102. procedure bestfit(bins, sz)
  103.    local b, i, n, d, best
  104.  
  105.    every i := 1 to *bins do {
  106.       b := bins[i]
  107.       d := binsize - b.size - sz
  108.       if d < 0 | d > \best then
  109.      next
  110.       best := d
  111.       n := i
  112.       }
  113.  
  114.    if \n then
  115.       return n
  116.    else {
  117.       put(bins, obj(0, []))
  118.       return *bins
  119.       }
  120. end
  121.