This file is indexed.

/usr/share/doc/cedar-backup2-doc/interface/CedarBackup2.knapsack-module.html is in cedar-backup2-doc 2.26.5-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
          "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <title>CedarBackup2.knapsack</title>
  <link rel="stylesheet" href="epydoc.css" type="text/css" />
  <script type="text/javascript" src="epydoc.js"></script>
</head>

<body bgcolor="white" text="black" link="blue" vlink="#204080"
      alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="CedarBackup2-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            ><a class="navbar" target="_top" href="https://bitbucket.org/cedarsolutions/cedar-backup2">CedarBackup2</a></th>
          </tr></table></th>
  </tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
  <tr valign="top">
    <td width="100%">
      <span class="breadcrumbs">
        <a href="CedarBackup2-module.html">Package&nbsp;CedarBackup2</a> ::
        Module&nbsp;knapsack
      </span>
    </td>
    <td>
      <table cellpadding="0" cellspacing="0">
        <!-- hide/show private -->
        <tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink"
    onclick="toggle_private();">hide&nbsp;private</a>]</span></td></tr>
        <tr><td align="right"><span class="options"
            >[<a href="frames.html" target="_top">frames</a
            >]&nbsp;|&nbsp;<a href="CedarBackup2.knapsack-module.html"
            target="_top">no&nbsp;frames</a>]</span></td></tr>
      </table>
    </td>
  </tr>
</table>
<!-- ==================== MODULE DESCRIPTION ==================== -->
<h1 class="epydoc">Module knapsack</h1><p class="nomargin-top"><span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html">source&nbsp;code</a></span></p>
<p>Provides the implementation for various knapsack algorithms.</p>
  <p>Knapsack algorithms are &quot;fit&quot; algorithms, used to take a set
  of &quot;things&quot; and decide on the optimal way to fit them into some
  container.  The focus of this code is to fit files onto a disc, although 
  the interface (in terms of item, item size and capacity size, with no 
  units) is generic enough that it can be applied to items other than 
  files.</p>
  <p>All of the algorithms implemented below assume that 
  &quot;optimal&quot; means &quot;use up as much of the disc's capacity as 
  possible&quot;, but each produces slightly different results.  For 
  instance, the best fit and first fit algorithms tend to include fewer 
  files than the worst fit and alternate fit algorithms, even if they use 
  the disc space more efficiently.</p>
  <p>Usually, for a given set of circumstances, it will be obvious to a 
  human which algorithm is the right one to use, based on trade-offs 
  between number of files included and ideal space utilization.  It's a 
  little more difficult to do this programmatically.  For Cedar Backup's 
  purposes (i.e. trying to fit a small number of collect-directory tarfiles
  onto a disc), worst-fit is probably the best choice if the goal is to 
  include as many of the collect directories as possible.</p>

<hr />
<div class="fields">      <p><strong>Author:</strong>
        Kenneth J. Pronovici &lt;pronovic@ieee.org&gt;
      </p>
</div><!-- ==================== FUNCTIONS ==================== -->
<a name="section-Functions"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td colspan="2" class="table-header">
    <table border="0" cellpadding="0" cellspacing="0" width="100%">
      <tr valign="top">
        <td align="left"><span class="table-header">Functions</span></td>
        <td align="right" valign="top"
         ><span class="options">[<a href="#section-Functions"
         class="privatelink" onclick="toggle_private();"
         >hide private</a>]</span></td>
      </tr>
    </table>
  </td>
</tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="CedarBackup2.knapsack-module.html#firstFit" class="summary-sig-name">firstFit</a>(<span class="summary-sig-arg">items</span>,
        <span class="summary-sig-arg">capacity</span>)</span><br />
      Implements the first-fit knapsack algorithm.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#firstFit">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="CedarBackup2.knapsack-module.html#bestFit" class="summary-sig-name">bestFit</a>(<span class="summary-sig-arg">items</span>,
        <span class="summary-sig-arg">capacity</span>)</span><br />
      Implements the best-fit knapsack algorithm.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#bestFit">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="CedarBackup2.knapsack-module.html#worstFit" class="summary-sig-name">worstFit</a>(<span class="summary-sig-arg">items</span>,
        <span class="summary-sig-arg">capacity</span>)</span><br />
      Implements the worst-fit knapsack algorithm.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#worstFit">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="CedarBackup2.knapsack-module.html#alternateFit" class="summary-sig-name">alternateFit</a>(<span class="summary-sig-arg">items</span>,
        <span class="summary-sig-arg">capacity</span>)</span><br />
      Implements the alternate-fit knapsack algorithm.</td>
          <td align="right" valign="top">
            <span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#alternateFit">source&nbsp;code</a></span>
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
</table>
<!-- ==================== VARIABLES ==================== -->
<a name="section-Variables"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td colspan="2" class="table-header">
    <table border="0" cellpadding="0" cellspacing="0" width="100%">
      <tr valign="top">
        <td align="left"><span class="table-header">Variables</span></td>
        <td align="right" valign="top"
         ><span class="options">[<a href="#section-Variables"
         class="privatelink" onclick="toggle_private();"
         >hide private</a>]</span></td>
      </tr>
    </table>
  </td>
</tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
        <a name="__package__"></a><span class="summary-name">__package__</span> = <code title="None">None</code><br />
      hash(x)
    </td>
  </tr>
</table>
<!-- ==================== FUNCTION DETAILS ==================== -->
<a name="section-FunctionDetails"></a>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td colspan="2" class="table-header">
    <table border="0" cellpadding="0" cellspacing="0" width="100%">
      <tr valign="top">
        <td align="left"><span class="table-header">Function Details</span></td>
        <td align="right" valign="top"
         ><span class="options">[<a href="#section-FunctionDetails"
         class="privatelink" onclick="toggle_private();"
         >hide private</a>]</span></td>
      </tr>
    </table>
  </td>
</tr>
</table>
<a name="firstFit"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">firstFit</span>(<span class="sig-arg">items</span>,
        <span class="sig-arg">capacity</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#firstFit">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <p>Implements the first-fit knapsack algorithm.</p>
  <p>The first-fit algorithm proceeds through an unsorted list of items 
  until running out of items or meeting capacity exactly.  If capacity is 
  exceeded, the item that caused capacity to be exceeded is thrown away and
  the next one is tried.  This algorithm generally performs more poorly 
  than the other algorithms both in terms of capacity utilization and item 
  utilization, but can be as much as an order of magnitude faster on large 
  lists of items because it doesn't require any sorting.</p>
  <p>The &quot;size&quot; values in the items and capacity arguments must 
  be comparable, but they are unitless from the perspective of this 
  function.  Zero-sized items and capacity are considered degenerate cases.
  If capacity is zero, no items fit, period, even if the items list 
  contains zero-sized items.</p>
  <p>The dictionary is indexed by its key, and then includes its key.  This
  seems kind of strange on first glance.  It works this way to facilitate 
  easy sorting of the list on key if needed.</p>
  <p>The function assumes that the list of items may be used destructively,
  if needed.  This avoids the overhead of having the function make a copy 
  of the list, if this is not required.  Callers should pass 
  <code>items.copy()</code> if they do not want their version of the list 
  modified.</p>
  <p>The function returns a list of chosen items and the unitless amount of
  capacity used by the items.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>items</code></strong> (dictionary, keyed on item, of <code>(item, size)</code> tuples, 
          item as string and size as integer) - Items to operate on</li>
        <li><strong class="pname"><code>capacity</code></strong> (integer) - Capacity of container to fit to</li>
    </ul></dd>
    <dt>Returns:</dt>
        <dd>Tuple <code>(items, used)</code> as described above</dd>
  </dl>
</td></tr></table>
</div>
<a name="bestFit"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">bestFit</span>(<span class="sig-arg">items</span>,
        <span class="sig-arg">capacity</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#bestFit">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <p>Implements the best-fit knapsack algorithm.</p>
  <p>The best-fit algorithm proceeds through a sorted list of items (sorted
  from largest to smallest) until running out of items or meeting capacity 
  exactly. If capacity is exceeded, the item that caused capacity to be 
  exceeded is thrown away and the next one is tried.  The algorithm 
  effectively includes the minimum number of items possible in its search 
  for optimal capacity utilization.  For large lists of mixed-size items, 
  it's not ususual to see the algorithm achieve 100% capacity utilization 
  by including fewer than 1% of the items.  Probably because it often has 
  to look at fewer of the items before completing, it tends to be a little 
  faster than the worst-fit or alternate-fit algorithms.</p>
  <p>The &quot;size&quot; values in the items and capacity arguments must 
  be comparable, but they are unitless from the perspective of this 
  function.  Zero-sized items and capacity are considered degenerate cases.
  If capacity is zero, no items fit, period, even if the items list 
  contains zero-sized items.</p>
  <p>The dictionary is indexed by its key, and then includes its key.  This
  seems kind of strange on first glance.  It works this way to facilitate 
  easy sorting of the list on key if needed.</p>
  <p>The function assumes that the list of items may be used destructively,
  if needed.  This avoids the overhead of having the function make a copy 
  of the list, if this is not required.  Callers should pass 
  <code>items.copy()</code> if they do not want their version of the list 
  modified.</p>
  <p>The function returns a list of chosen items and the unitless amount of
  capacity used by the items.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>items</code></strong> (dictionary, keyed on item, of <code>(item, size)</code> tuples, 
          item as string and size as integer) - Items to operate on</li>
        <li><strong class="pname"><code>capacity</code></strong> (integer) - Capacity of container to fit to</li>
    </ul></dd>
    <dt>Returns:</dt>
        <dd>Tuple <code>(items, used)</code> as described above</dd>
  </dl>
</td></tr></table>
</div>
<a name="worstFit"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">worstFit</span>(<span class="sig-arg">items</span>,
        <span class="sig-arg">capacity</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#worstFit">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <p>Implements the worst-fit knapsack algorithm.</p>
  <p>The worst-fit algorithm proceeds through an a sorted list of items 
  (sorted from smallest to largest) until running out of items or meeting 
  capacity exactly.  If capacity is exceeded, the item that caused capacity
  to be exceeded is thrown away and the next one is tried.  The algorithm 
  effectively includes the maximum number of items possible in its search 
  for optimal capacity utilization.  It tends to be somewhat slower than 
  either the best-fit or alternate-fit algorithm, probably because on 
  average it has to look at more items before completing.</p>
  <p>The &quot;size&quot; values in the items and capacity arguments must 
  be comparable, but they are unitless from the perspective of this 
  function.  Zero-sized items and capacity are considered degenerate cases.
  If capacity is zero, no items fit, period, even if the items list 
  contains zero-sized items.</p>
  <p>The dictionary is indexed by its key, and then includes its key.  This
  seems kind of strange on first glance.  It works this way to facilitate 
  easy sorting of the list on key if needed.</p>
  <p>The function assumes that the list of items may be used destructively,
  if needed.  This avoids the overhead of having the function make a copy 
  of the list, if this is not required.  Callers should pass 
  <code>items.copy()</code> if they do not want their version of the list 
  modified.</p>
  <p>The function returns a list of chosen items and the unitless amount of
  capacity used by the items.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>items</code></strong> (dictionary, keyed on item, of <code>(item, size)</code> tuples, 
          item as string and size as integer) - Items to operate on</li>
        <li><strong class="pname"><code>capacity</code></strong> (integer) - Capacity of container to fit to</li>
    </ul></dd>
    <dt>Returns:</dt>
        <dd>Tuple <code>(items, used)</code> as described above</dd>
  </dl>
</td></tr></table>
</div>
<a name="alternateFit"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">alternateFit</span>(<span class="sig-arg">items</span>,
        <span class="sig-arg">capacity</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    ><span class="codelink"><a href="CedarBackup2.knapsack-pysrc.html#alternateFit">source&nbsp;code</a></span>&nbsp;
    </td>
  </tr></table>
  
  <p>Implements the alternate-fit knapsack algorithm.</p>
  <p>This algorithm (which I'm calling &quot;alternate-fit&quot; as in 
  &quot;alternate from one to the other&quot;) tries to balance small and 
  large items to achieve better end-of-disk performance.  Instead of just 
  working one direction through a list, it alternately works from the start
  and end of a sorted list (sorted from smallest to largest), throwing away
  any item which causes capacity to be exceeded.  The algorithm tends to be
  slower than the best-fit and first-fit algorithms, and slightly faster 
  than the worst-fit algorithm, probably because of the number of items it 
  considers on average before completing.  It often achieves slightly 
  better capacity utilization than the worst-fit algorithm, while including
  slighly fewer items.</p>
  <p>The &quot;size&quot; values in the items and capacity arguments must 
  be comparable, but they are unitless from the perspective of this 
  function.  Zero-sized items and capacity are considered degenerate cases.
  If capacity is zero, no items fit, period, even if the items list 
  contains zero-sized items.</p>
  <p>The dictionary is indexed by its key, and then includes its key.  This
  seems kind of strange on first glance.  It works this way to facilitate 
  easy sorting of the list on key if needed.</p>
  <p>The function assumes that the list of items may be used destructively,
  if needed.  This avoids the overhead of having the function make a copy 
  of the list, if this is not required.  Callers should pass 
  <code>items.copy()</code> if they do not want their version of the list 
  modified.</p>
  <p>The function returns a list of chosen items and the unitless amount of
  capacity used by the items.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>items</code></strong> (dictionary, keyed on item, of <code>(item, size)</code> tuples, 
          item as string and size as integer) - Items to operate on</li>
        <li><strong class="pname"><code>capacity</code></strong> (integer) - Capacity of container to fit to</li>
    </ul></dd>
    <dt>Returns:</dt>
        <dd>Tuple <code>(items, used)</code> as described above</dd>
  </dl>
</td></tr></table>
</div>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="CedarBackup2-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            ><a class="navbar" target="_top" href="https://bitbucket.org/cedarsolutions/cedar-backup2">CedarBackup2</a></th>
          </tr></table></th>
  </tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
  <tr>
    <td align="left" class="footer">
    Generated by Epydoc 3.0.1
    </td>
    <td align="right" class="footer">
      <a target="mainFrame" href="http://epydoc.sourceforge.net"
        >http://epydoc.sourceforge.net</a>
    </td>
  </tr>
</table>

<script type="text/javascript">
  <!--
  // Private objects are initially displayed (because if
  // javascript is turned off then we want them to be
  // visible); but by default, we want to hide them.  So hide
  // them unless we have a cookie that says to show them.
  checkCookie();
  // -->
</script>
</body>
</html>