1 """
   2 DVD Split, by Marcelo Barros (marcelobarrosalmeida(at)gmail.com)
   3 
   4 March/17/2016 - modifications for python 3, removing psyco dependence (obsolete)
   5 Sept/13/2005 - original version
   6 $Id: dvdsplit.py,v 1.1 2005/09/13 14:54:36 barros Exp $
   7 """
   8 import random
   9 import math
  10 import os
  11 import sys
  12 from optparse import OptionParser
  13 #import psyco
  14 
  15 def currentSize(files, selected):
  16     """
  17     Calculate the size of the current selection.
  18     
  19     Parameters:
  20     - files: list with file sizes
  21     - selected: list with 1 or -1, indicating if the file was selected or not
  22 
  23     Returns:
  24     - the current selection size
  25     """
  26     sz = 0
  27     for i in range(len(files)):
  28         if(selected[i] > 0):
  29             sz = sz + files[i]
  30     return sz
  31 
  32 def energyFun(files,selected,dvdsz):
  33     """
  34     Energy function used. In this case is:
  35     f(x) = |current_size - dvdsize |
  36 
  37     Parameters:
  38     - files: list with file sizes
  39     - selected: list with 1 or -1, indicating if the file was selected or not
  40     - dvdsz: dvd size
  41 
  42     Returns:
  43     - energy function value for the current selection
  44     """
  45     energ = 0
  46     for i in range(len(files)):
  47         if selected[i] > 0:
  48             energ = energ + files[i]
  49     energ = abs(energ - dvdsz)
  50     return energ
  51 
  52 def dvdInitialGuess(files,selected,dvdsz):
  53     """
  54     Just provide an initial random guess to the algorithm
  55 
  56     Parameters:
  57     - files: list with file sizes
  58     - selected: list with 1 or -1, indicating if the file was selected or not
  59     - dvdsz: dvd size    
  60     """
  61     l = len(files)
  62     idx = range(l)
  63     idx = random.sample(idx,l)
  64 
  65     t = 0
  66     for i in range(l):
  67         j = idx[i]
  68         t = t + files[j]
  69         selected[j] = 1
  70         if t >= dvdsz:
  71             break
  72     
  73 def dvdSplit(files,dvdsz,slack=50,itermax=3000,beta=0.005):
  74     """
  75     Given a list with file sizes, the dvd size and the acceptable slack
  76     this routine gives a subset that fits in one dvd.  
  77 
  78     Parameters:
  79     - files: list with file sizes
  80     - dvdsz: dvd size (single side)
  81     - slack: maximum acceptable error when calculating the selection
  82     - itermax: maximum number of iteration (default=2000)
  83     - beta: sigmoid parameter (default 0.005, empirically determined)
  84 
  85     Returns:
  86     - indexes of selected files: [ idx1, idx2, ..., idxn ]
  87     - indexes of not selected files: [ idx1, idx2, ..., idxn ]
  88     - current selection size
  89     - iteration used to calculate
  90     """
  91     running = True
  92     iter = 0
  93     numfiles = len(files)
  94     selected = [-1 for x in range(numfiles)]
  95     dvdInitialGuess(files,selected,dvdsz)
  96     
  97     sz = currentSize(files,selected) # maximum size must be greather than dvdsize
  98 
  99     if(sz > dvdsz):
 100         while(running and iter < itermax):
 101             # current energy 
 102             e1 = energyFun(files,selected,dvdsz)
 103             # change state for random node
 104             n = random.randint(0,numfiles-1)
 105             selected[n] = -selected[n]
 106             # new energy
 107             e2 = energyFun(files,selected,dvdsz)
 108             # evaluate the change against sigmoid and accept it or not
 109             # according to a uniform probability
 110             sig = (1/( 1 + math.exp(beta*(e2-e1))))
 111             if sig < random.uniform(0,1):
 112                 selected[n] = -selected[n] # state not accepted
 113             sz = currentSize(files,selected)
 114             # testing exit condition: (dvdsz - slack) < currentSize < dvdsz
 115             if ( (sz >= (dvdsz - slack)) and (sz < dvdsz) ):
 116                 running = False
 117             iter = iter + 1
 118         
 119     sel = []
 120     notsel = []
 121     for i in range(numfiles):
 122         if selected[i] > 0:
 123             sel.append(i)
 124         else:
 125             notsel.append(i)
 126     #print "Solution found in %d iterations. Compilation size is %d (%d files)" % (iter,sz,len(sel))
 127     return sel,notsel,sz,iter
 128 
 129 def dvdsSplit(files,dvdsz,slack=50,itermax=3000,beta=0.005):
 130     """
 131     Given a list with file sizes, the dvd size and the acceptable slack
 132     this routine distributes the selection over several dvs.
 133 
 134     Parameters:
 135     - files: list with file sizes
 136     - dvdsz: dvd size (single side)
 137     - slack: maximum acceptable error when calculating the selection (default=50)
 138     - itermax: maximum number of iteration (default=2000)
 139     - beta: sigmoid parameter (default 0.005, empirically determined)
 140 
 141     Returns:
 142     - indexes of selected files per dvds:
 143       [ [idx1, idx2, ..., idxn], [idx1, idx2, ..., idxm], ..., [idx1, idx2, ..., idxk] ]
 144     - compilation sizes: [ size1, size2, ..., sizen ]      
 145     """
 146     # first create a dictionary with all file sizes indexed. Files choosen
 147     # by dvdSplit will be removed from this dictionary until it becomes empty
 148     filesdic = dict()
 149     n = len(files)
 150     for i in range(n):
 151         filesdic[i] = files[i]
 152     dvds = []
 153     sz = []
 154     running = True
 155     r = 1
 156     while(running):    
 157         v = list(filesdic.values())
 158         k = list(filesdic.keys())
 159         print("Starting DVD %02d [%3.2f%% completed]" % (r,100-100*len(v)/n))
 160         maxtries = 50
 161         while(True):
 162             sel,ns,dsz,iter = dvdSplit(v,dvdsz,slack,itermax,beta)
 163             if dsz < dvdsz:
 164                 break;
 165             maxtries = maxtries - 1
 166             if(maxtries == 0):
 167                 print("Could not find a good solution for DVD %d in 50 attempts. Try again, please." % (r))
 168                 sys.exit(1)
 169         # getting indexes
 170         r = r + 1
 171         d = []
 172         for s in sel: 
 173             d.append(k[s])
 174             del filesdic[k[s]]
 175         # saving dvd compilation
 176         dvds.append(d)
 177         sz.append(dsz)
 178         if len(ns) == 0:
 179             running = False
 180 
 181     return dvds, sz
 182 
 183 def dvdConsistency(filenames,filesizes,dvdsz):
 184     """
 185     Consistency checks.
 186 
 187     Parameters:
 188     - filenames: file names dict
 189     - filesizes: file sizes dict
 190     - dvds: dvd size
 191     """
 192     # look for any file bigger than dvd side
 193     for i in filesizes:
 194         if filesizes[i] >= dvdsz:
 195             print("Size %d is bigger than dvd size %d" % (filesizes[i],dvdsz))
 196             sys.exit(1)
 197 
 198 def printDvdLayout(filesizes,filenames,dvdsz,dvds,s):
 199     """
 200     Print results
 201     """
 202     i = 0
 203     n = len(dvds)    
 204     tts = []
 205     print("\nSummary:")
 206     for dvd in dvds:
 207         tt = []
 208         i = i + 1
 209         for track in dvd:
 210             tt.append(filesizes[track])
 211         tts.append(sum(tt))
 212         print("[DVD %d/%d, SIZE %dMBs, USAGE %2.2f%%]" % (i,n,tts[i-1],100.0*tts[i-1]/dvdsz))
 213             
 214     i = 0
 215     print("\nFile seletion per DVD:")
 216     for dvd in dvds:
 217         i = i + 1
 218         print("[DVD %d/%d, SIZE %dMBs]" % (i,n,tts[i-1]))
 219         for track in dvd:
 220             files = filenames[track].split(',')
 221             files.sort()
 222             for f in files:
 223                 print("\t%s" % (f))
 224         
 225 def buildDvds(basedir,dvdsz,slack):
 226     """
 227     Get the files list and call optimization routines
 228     """
 229     filelist = os.listdir(basedir)
 230     filenames = dict()
 231     filesizes = dict()
 232     i = 0
 233     print("\nFiles at base directory %s (DVD size = %d, slack = %d)" % (basedir,dvdsz,slack))
 234     for f in filelist:
 235         filename = basedir+f
 236         if os.path.isfile(filename):
 237             filenames[i] = f
 238             # in MB, rounded up
 239             filesizes[i] = int(os.path.getsize(filename)/1024.0**2 + 1)
 240             print("[%5.2fMB ] %s" % (filesizes[i],filenames[i]))
 241             i = i + 1
 242 
 243     print("\nChecking consistency ...")
 244     dvdConsistency(filenames,filesizes,dvdsz)
 245     dvds, s = dvdsSplit(list(filesizes.values()),dvdsz,slack)
 246     printDvdLayout(filesizes,filenames,dvdsz,dvds,s)
 247 
 248 def main():
 249 
 250     usage = "Usage: %prog [options]"
 251     cmdline = OptionParser(usage)
 252     cmdline.add_option("-d", "--dir",  action="store", dest="basedir", type="string", default=".",    metavar="DIR",      help="Directory where files are stored")
 253     cmdline.add_option("-s", "--size", action="store", dest="dvdsz",   type="int",    default="4500", metavar="SIZE",     help="DVD size (MB)")
 254     cmdline.add_option("-l", "--slack",action="store", dest="slack",   type="int",    default="50",   metavar="SLACK",    help="Maximum acceptable error (MB)")
 255     
 256     (options, args) = cmdline.parse_args()
 257 
 258     if(os.path.isdir(options.basedir) == False):
 259         print("%s is not a valid directory" %(options.basedir))
 260         sys.exit(1)
 261 
 262     options.basedir.strip()
 263     basedir = os.path.normpath(options.basedir)
 264     if(os.path.isdir("c:\\")):
 265         basedir = basedir + "\\"
 266     else:
 267         basedir = basedir + "//"
 268 
 269     #buildDvdsPrx = psyco.proxy(buildDvds)
 270     #buildDvdsPrx(basedir,int(options.dvdsz),int(options.slack))
 271     buildDvds(basedir,int(options.dvdsz),int(options.slack))
 272     
 273 if __name__ == "__main__":
 274 
 275     main()