solexafiller.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

type (
	name_size_pair struct {
		name string
		size uint64
	}
	jbod    = name_size_pair
	proj    = name_size_pair
	mapping []uint64
)

func new_name_size_pair(data string) name_size_pair {
	var s uint64

	d := strings.Split(data, ",")

	if len(d) != 2 {
		panic("wrong file format!")
	}

	s, e := strconv.ParseUint(d[1], 10, 64)
	if e != nil {
		panic("wrong format for size!\n" + e.Error())
	}

	return name_size_pair{d[0], s}
}

func read_data(sc *bufio.Scanner) ([]jbod, []proj) {
	var (
		js []jbod
		ps []proj
	)

	for sc.Scan() {
		da := strings.Split(sc.Text(), ":")
		if len(da) != 2 {
			panic("wrong file format!")
		}

		js = append(js, new_name_size_pair(da[0]))

		for _, p := range strings.Split(da[1], ";") {
			if p == "" {
				continue
			}
			ps = append(ps, new_name_size_pair(p))
		}
	}

	if er := sc.Err(); er != nil {
		panic(er)
	}

	return js, ps
}

func write_data(m mapping, js []jbod, ps []proj) {
	var p []string

	for i := 0; i < len(js); i++ {
		fmt.Printf("%s,%d:", js[i].name, js[i].size)
		p = p[:0]
		for k, j := range m {
			if j == uint64(i) {
				p = append(p, fmt.Sprintf("%s,%d", ps[k].name, ps[k].size))
			}
		}
		fmt.Println(strings.Join(p, ";"))
	}
}

func first_fit_decreasing(js []jbod, ps []proj) mapping {
	var (
		m mapping  = make([]uint64, len(ps))
		c []uint64 = make([]uint64, len(js))
	)

	sort.Slice(ps, func(i, j int) bool {
		return ps[i].size > ps[j].size
	})

	sort.Slice(js, func(i, j int) bool {
		return js[i].size < js[j].size
	})

	for i := 0; i < len(ps); i++ {
		for j := 0; j < len(js); j++ {
			c[j] += ps[i].size
			if c[j] <= js[j].size {
				m[i] = uint64(j)
				break
			}
			c[j] -= ps[i].size
			if j + 1 == len(js) && i + 1 == len(ps) {
				m = make([]uint64, len(js))
			}
		}
	}

	return m
}

func main() {
	var (
		js []jbod
		ps []proj
	)

	stat, _ := os.Stdin.Stat()
	if stat.Mode()&os.ModeCharDevice == 0 {
		js, ps = read_data(bufio.NewScanner(os.Stdin))
	} else {
		panic("no input")
	}

	m := first_fit_decreasing(js, ps)
	write_data(m, js, ps)
}