#!/bin/bash
#===============================================================================
# distributes any number of files into equal sized bins, where every 
# bin is a directory containg symlinks to the original files
#===============================================================================

# print to stderr
err() {
    echo >&2 "$@"
}

# create a new bucket and return its name
# output: bucket, next
next=0
newbucket() {
    while :; do
        local name="${format:0:$((${#format} - ${#next}))}$next"    # next filled with chars from format 
        bucket="$target"/$name; ((next++))
        [ -e "$bucket" ] && continue
        err "creating bucket $name as $bucket"
        mkdir -p "$bucket"
        break
    done
}

#===============================================================================

# check argument number
[ $# -lt 4 ] && { err "usage: binpack targetdir binsize binexponent findargs"; exit 1; }

# directory to create volumes in
target="${1%/}"; shift
[ ! -d "$target" ] && { err "target directory $target does not exist"; exit 1; }

# maximum volume size
maximum="$1"; shift

# get volume exponent
exponent="$1"; shift
case "$exponent" in
    g)  maximum=$((maximum * 1024 * 1024 * 1024));;
    m)  maximum=$((maximum * 1024 * 1024));;
    k)  maximum=$((maximum * 1024));;
    b)  ;;  # * 1
    *)  err "binexponent may be 'b', 'k', 'm' or 'g'"
        exit 1;;
esac

# volume format
format="0000"

# find files biggest first and distribute them
find "$@" -type f -printf "%s\t%p\n" | sort -rn |

# pack each file into the least filled bucket, or create a new bucket for the file
while IFS=$'\t' read -r size file; do
    # skip too large files
    [ $size -gt $maximum ] && {
        err "file $file is larger than maximum binsize"
        continue
    }

    # find the bucket with the most free space
    # this expects the target directory to contain only bucket directories
    bucket=$(
        du 2>/dev/null -L -bs "$target"/* | 
        sort -n | head -n 1 | sed 's/.*\t//'
    )
    
    # create a bucket when no bucket existed
    [ -z "$bucket" ] && newbucket
    
    # find out how much the bucket would be filled
    filled=$(du -L -bs "$bucket" | sed 's/^ *//;s/\t.*//')
    newfill=$((filled + size))
    
    # create a new bucket of the best one is too small
    [ $newfill -gt $maximum ] && newbucket
    
    # check whether moving the file is safe
    newfile="$bucket/$(basename "$file")"
    while [ -e "$newfile" ]; do 
        newfile="$newfile~" ### BÄH
    done
    #[ -e "$newfile" ] && {
    #   err "cannnot link file $file which collides with $newfile"
    #   continue
    #}
    
    # link the file, finally
    err "link file $file into bucket $bucket"
    ln -s "$file" "$bucket"
done