knapfake 2

Much faster than the previous version, specially with long tasks.


knapfake 2.0

Somebody asked at for a script which would take a bunch of files, then divide them in folders of a maximum size (useful to burn CDs, etc.). I was also looking for such tool, so I tried to write my own. The user mentioned "knapsack". I'm not sure this is related to the knapsack problem, and absolutelly sure this wouldn't be a nice implementation of such algorithm, so I called this one "knapfake".

As I understand it, the perfect algorithm would check any file against any file, creating the perfect combination to fit the maximum allowed size in different containers. "knapfake" does not work so, and most probably someone with a strong mathematical background should create SUCH script. Meanwhile, you can use this one, which:

a) Creates a list of sizes and names of folders/files (any item within "inputFolder")
b) Sorts such list in decreasing order
c) Attempts to fit each item within the first "virtual folder" of a maximum size
d) If it does exceed the maximum size, it attempts the same operation in the second "virtual folder", if it does exist. Otherwise, it creates a new folder and places the item within such "new virtual folder"
e) When all items are virtually distributed, they are moved to sub-folders within "outputFolder"
f) If any item has a size greater than the maximum allowed one, it is placed in a "badItems" list --> implement yourself the actions to be executed with such list

You must CONFIGURE the value "maxMB" (by default 690 -MB-)
You must define manually or programatically both "inputFolder" (the folder containing lots of items to be sub-divided into folders of maxMB size) and "outputFolder" (the folder where the new sub-folders will be created, and items moved within)


Pescados Software - 19, october, 2004

knapfake 2.0, 17, march, 2005 --> optimized for speed


set maxMB to 690
set maxbytes to maxMB * (1024 ^ 2)

set inputFolder to (choose folder with prompt "Choose the folder where items to be sub-divided are located currently")
set outputFolder to (choose folder with prompt "Choose the folder where I should locate the items in different folders of max-sixe " & maxMB & " MB")

tell application "Finder"
	set ts to size of items of inputFolder
	set ns to name of items of inputFolder
end tell

--> acellerators
property folders : missing value
property excludedItems : missing value
property badItems : missing value
property mixedList : missing value

set mixedList to sortListOfLists(mixLists(ts, ns), 1) --> I'm not sure "sortLists" is relevant in this algorithm (???)

set folders to {{0}} --> a list with an "empty folder" sized 0
set excludedItems to {} --> items shifted from mixedList
set badItems to {} --> items whose size is higher than "maxbytes"

repeat with i from (count mixedList) to 1 by -1
	if i is not in my excludedItems and i is not in my badItems then --> process this item
		set itemSize to my mixedList's item i's item 1
		if itemSize > maxbytes then
			set my badItems's end to i
		else --> try to add item to current "folder"
			set itemWasAddedToAnExistingFolder to false
			repeat with x from 1 to count my folders --> folders's item x is {{size,name},{size,name},...}, Try to add this item to an existing folder
				set folderSum to item 1 of my folders's item x --> first item is the allways the sum of the contents
				if (itemSize + folderSum) < maxbytes then --> add item to this "folder"
					set end of my folders's item x to my mixedList's item i --> add to "folder"
					set item 1 of my folders's item x to (item 1 of my folders's item x) + itemSize --> sum its size
					set itemWasAddedToAnExistingFolder to true
					exit repeat
				end if
			end repeat
			if not itemWasAddedToAnExistingFolder then
				set end of my folders to {itemSize, my mixedList's item i} --> add to a new "folder"
			end if
			set end of my excludedItems to i --> item is now inside a "folder", so exclude it from "mixedList"
		end if
	end if
end repeat

property ftm : missing value
--> distribute stuff
repeat with i from 1 to count my folders --> "folders" is now a list of {{TOTALSIZE,{size, name}, {size, name}}, {TOTALSIZE,{size, name}, {size, name}}}
	set currentFolder to rest of my folders's item i --> exclude "TOTALSIZE": {{size, name}, {size, name}}
	--> create a folder with a dummy sequential name, where we will place "files" in this "folder"
	set newFolder to ((outputFolder as text) & "dummy" & i)
	do shell script "mkdir -p " & quoted form of POSIX path of newFolder
	set ftm to {} --> create list of files to be moved
	repeat with singleFile in currentFolder
		set end of my ftm to alias ((inputFolder as text) & item 2 of singleFile)
	end repeat
	--> move items
	tell application "Finder" to move ftm to alias newFolder replacing yes
end repeat

beep 2

to sumFolder(l) --> l is a list as {{size,name},{size,name}}
	script a
		property x : l
	end script
	set |sum| to 0
	repeat with i from 1 to count a's x
		set |sum| to |sum| + (a's x's item i's item 1)
	end repeat
end sumFolder

to mixLists(a, b)
	script foo
		property x : a
		property y : b
		property nl : {}
	end script
	repeat with i from 1 to count foo's x
		set foo's nl's end to {foo's x's item i, foo's y's item i}
	end repeat
	foo's nl
end mixLists

to sortListOfLists(lst, fld)
	script a
		property l1 : lst
		property l2 : {l1's item 1}
	end script
	repeat with i from 1 to count lst
		set f to a's l1's item i's item fld
		considering case
			if f < a's l2's item 1's item fld then
				set beginning of a's l2 to a's l1's item i
			else if f > a's l2's item -1's item fld then
				set end of a's l2 to a's l1's item i
			else --> loop
				repeat with x from 1 to count lst
						if f > a's l2's item x's item fld and f < a's l2's item (x + 1)'s item fld then
							set a's l2 to (a's l2's items 1 thru x) & {(a's l1's item i)} & (a's l2's items (x + 1) thru -1)
							exit repeat
						end if
					end try
				end repeat
			end if
		end considering
	end repeat
	return a's l2
end sortListOfLists