/usr/share/mozart/doc/fst/node4.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>4 Packing Files onto Disks</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node3.html#fset.examples.hamming"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node5.html#fset.examples.crew">Next >></A></TD></TR></TABLE><DIV id="fset.examples.binpacking"><H1><A name="fset.examples.binpacking">4 Packing Files onto Disks</A></H1><P class="margin">Problem Specification</P><P> Suppose, you want to copy a set of files from your hard-disk onto as few as possible diskettes of a given size, e. g. onto common 1.44 MB diskettes. In case your files do not fit on a single diskette, it might become quite tricky to figure out the minimal number of needed diskettes and how to partition the files. </P><P class="margin">Model</P><P> A diskette is modeled by a set <IMG alt="s_i" src="latex52.png">. All sets <IMG alt="s_i" src="latex52.png"> form a partition of the set of all files <IMG alt="s_{all files}" src="latex53.png">, i. e., all <IMG alt="s_i" src="latex52.png"> are pairwise disjoint and their union is <IMG alt="s_{all files}" src="latex53.png">. The sizes of all files contained in a set is summed up and compared with the fixed capacity of the diskette. </P><P class="margin">Distribution Strategy</P><P> The distribution is two-dimensional. </P><UL><LI><P>Distribute the number of diskettes starting from the minimal number possible. The minimal number is the ceiling of dividing the sum of all file sizes by the diskette size. </P></LI><LI><P>Distribute the files over the sets representing the individual diskettes. </P></LI></UL><P> The distribution over the files could be refined by taking the size of the actual file into account. This is subject to experimentation by the reader. </P><P class="margin">Solver</P><P> The function <CODE>SpreadFiles</CODE> returns a solver configured according to the actual values of the formal arguments <CODE>Files</CODE> and <CODE>DiskCap</CODE>. The returned solver's root variable <CODE>Disks</CODE> contains the set of diskettes of size <CODE>DiskCap</CODE> needed to store all files in <CODE>Files</CODE> and specifies what files have to be stored on which diskette. </P><P>The argument <CODE>Files</CODE> holds a list of individual files, where each file is represented by a record with label <CODE>file</CODE> and the features <CODE>name</CODE> and <CODE>size</CODE>. The argument <CODE>DiskCap</CODE> is an integer. The variable <CODE>FileSizes</CODE> holds a list of all files sizes and <CODE>Size</CODE> stores the sum all elements in <CODE>FileSizes</CODE>. The lower bound of the number of diskettes is held in <CODE>LB</CODE>. The finite domain <CODE>NbDisks</CODE> is used to distribute over the number of diskettes. Each file in <CODE>Files</CODE> is represented by an integer in ascending order starting from 1. These integers are stored in <CODE>AllFiles</CODE>. Finally, the sets representing the individual diskettes are held in <CODE>Ds</CODE>. </P><P> First, the number of diskettes is distributed starting from <CODE>LB</CODE>. Then, <CODE>Ds</CODE> is initialized to sets containing maximal all files. Next, the constraint that all elements of <CODE>Ds</CODE> are a partition of the set of all files is imposed. Finally, the maximum capacity of all diskettes is limited to <CODE>DiskCap</CODE> by imposing for all elements of <CODE>Ds</CODE> the constraint that the sum of the size of all their elements is less or equal to <CODE>DiskCap</CODE>. The implementation uses <CODE>FS<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>areIn</CODE> to associate the containment of individual elements of sets to 0/1 variables. These 0/1 variable are passed to <CODE>FD<SPAN class="keyword">.</SPAN>sumC</CODE> to ensure that a diskettes capacity is not exceeded. Distribution over <CODE>Ds</CODE> tries to locate file onto diskettes. </P><P class="margin">Particularities</P><P> The solver represents internally individual file as integers since finite set constraints in Oz can only deal with non-negative integers. To make the produced solution readable to humans, a diskette is represented as record where the features are the files to be stored on that diskette. Such a record is constructed by imposing a feature constraint onto each element of <CODE>Disks</CODE>. Then the actual features representing the filenames are added successively by mapping the elements of the set representing the diskettes to their names. Every feature refers to the size of the file it represents. Finally, the feature constraint becomes a record by constraining its arity's width to the number of features. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">SpreadFiles</SPAN> Files DiskCap}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Disks}<BR> FileSizes = {Map Files <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> F} F<SPAN class="keyword">.</SPAN>size <SPAN class="keyword">end</SPAN>}<BR> Size = {FoldL FileSizes Number<SPAN class="keyword">.</SPAN><SPAN class="string">'+'</SPAN> 0}<BR> LB = Size <SPAN class="keyword">div</SPAN> DiskCap <SPAN class="keyword">+</SPAN> <BR> <SPAN class="keyword">if</SPAN> Size <SPAN class="keyword">mod</SPAN> DiskCap<SPAN class="keyword">==</SPAN>0 <SPAN class="keyword">then</SPAN> 0 <SPAN class="keyword">else</SPAN> 1 <SPAN class="keyword">end</SPAN> <BR> NbDisks = {FD<SPAN class="keyword">.</SPAN>int LB<SPAN class="keyword">#</SPAN>FD<SPAN class="keyword">.</SPAN>sup}<BR> AllFiles = {List<SPAN class="keyword">.</SPAN>number 1 {Length Files} 1} <BR> Ds<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>distribute naive [NbDisks]} <BR> <BR> {FS<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>list<SPAN class="keyword">.</SPAN>upperBound NbDisks AllFiles Ds}<BR> <BR> {FS<SPAN class="keyword">.</SPAN>partition Ds {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make AllFiles}}<BR> <BR> {ForAll Ds <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> D} BL <SPAN class="keyword">in</SPAN> <BR> {FS<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>areIn AllFiles D BL} <BR> {FD<SPAN class="keyword">.</SPAN>sumC FileSizes BL <SPAN class="string">'=<:'</SPAN> DiskCap} <BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> {FS<SPAN class="keyword">.</SPAN>distribute naive Ds}<BR> <BR> Disks = {Map Ds<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> D}<BR> Disk = {RecordC<SPAN class="keyword">.</SPAN>tell diskette}<BR> <SPAN class="keyword">in</SPAN> <BR> {ForAll {FS<SPAN class="keyword">.</SPAN>monitorIn D}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> E}<BR> F = {Nth Files E}<BR> <SPAN class="keyword">in</SPAN> <BR> Disk^(F<SPAN class="keyword">.</SPAN>name) = F<SPAN class="keyword">.</SPAN>size<BR> <SPAN class="keyword">end</SPAN>}<BR> {RecordC<SPAN class="keyword">.</SPAN>width Disk} = {FS<SPAN class="keyword">.</SPAN>card D}<BR> Disk<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR></PRE></BLOCKQUOTE><P> </P><P>Invoking the solver by </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">declare</SPAN> Disks = <BR>{SearchOne {SpreadFiles [file(name:a size:360) <BR> file(name:b size:850)<BR> file(name:c size:630) <BR> file(name:d size:70)<BR> file(name:e size:700) <BR> file(name:f size:210)]<BR> 1440}}</CODE></BLOCKQUOTE><P> produces the following result: </P><BLOCKQUOTE class="code"><CODE>[[diskette(a:360 b:850 f:210) diskette(c:630 d:70 e:700)]]</CODE></BLOCKQUOTE><P> The input data for this solver can be easily obtained from the respective operating system by using the module <CODE>OS</CODE> (see <A href="../system/node56.html#chapter.os">Chapter 21 of ``System Modules''</A> for details]. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node3.html#fset.examples.hamming"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node5.html#fset.examples.crew">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|