package web
import (
"sort"
"strings"
)
// foldColumns fits a window's paths to limit columns. It starts from
// the top-level directories and splits the busiest column into its
// children while there is room, so the detail goes where the work was:
// a directory nobody touched stays one column, a hot one opens down
// toward its files. A folded directory is named with a trailing slash,
// as the index names the rows it folds itself. Each touch moves to its
// column; touches that land on the same (day, column, person) become
// one. The files at the top of the tree are one column, and
// directories with next to no work are gathered into one named (other),
// so the places go to where the work was: a directory with more
// children than there is room for opens into its heaviest and one more
// gathering the rest. It reports whether anything was folded.
func foldColumns(act activityOut, limit int) (activityOut, bool) {
names, colOf, folded := foldPlan(act, limit)
if !folded {
return act, false
}
type mark struct{ day, col, author, inherited int }
seen := map[mark]struct{}{}
touches := make([]activityTouch, 0, len(act.Touches))
for _, t := range act.Touches {
if t.Path < 0 || t.Path >= len(colOf) {
continue
}
m := mark{t.Day, colOf[t.Path], t.Author, t.Inherited}
if _, dup := seen[m]; dup {
continue
}
seen[m] = struct{}{}
t.Path = m.col
touches = append(touches, t)
}
act.Paths, act.Touches = names, touches
return act, true
}
// foldPlan is the fold itself: the column names and, for each path of
// the window, the column it falls in. A caller that needs the touches
// counted rather than merged (the strips size a mark by files) uses the
// plan; foldColumns applies it and merges.
func foldPlan(act activityOut, limit int) (names []string, colOf []int, folded bool) {
if len(act.Paths) <= limit || limit < 1 {
colOf = make([]int, len(act.Paths))
for i := range colOf {
colOf[i] = i
}
return act.Paths, colOf, false
}
parts := make([][]string, len(act.Paths))
for i, p := range act.Paths {
parts[i] = strings.Split(strings.TrimSuffix(p, "/"), "/")
}
weight := make([]int, len(act.Paths))
for _, t := range act.Touches {
if t.Path >= 0 && t.Path < len(weight) && t.Inherited == 0 {
weight[t.Path]++
}
}
// A column is a prefix of depth components and the paths under it;
// a path no deeper than its column's depth is the column itself. A
// column that gathers several others carries its own name.
type column struct {
depth int
members []int
weight int
name string
}
group := func(members []int, depth int) []column {
var out []column
at := map[string]int{}
for _, i := range members {
k := colKey(act.Paths[i], parts[i], depth)
c, ok := at[k]
if !ok {
c = len(out)
at[k] = c
out = append(out, column{depth: depth})
}
out[c].members = append(out[c].members, i)
out[c].weight += weight[i]
}
return out
}
// gather folds columns into one, as the index orders its paths.
gather := func(cols []column, name string) column {
g := column{name: name}
for _, c := range cols {
g.members = append(g.members, c.members...)
g.weight += c.weight
}
sort.Ints(g.members)
return g
}
// keepHeaviest leaves the n-1 heaviest columns as they are and
// gathers the rest into one named other, so a tree too wide gives
// way where the work was least.
keepHeaviest := func(cols []column, n int, other string) []column {
if len(cols) <= n {
return cols
}
by := make([]int, 0, len(cols))
var out, rest []column
for i, c := range cols {
if c.name == other {
rest = append(rest, c) // already gathered: gathers again
} else {
by = append(by, i)
}
}
sort.SliceStable(by, func(a, b int) bool { return cols[by[a]].weight > cols[by[b]].weight })
for rank, i := range by {
if rank < n-1 {
out = append(out, cols[i])
} else {
rest = append(rest, cols[i])
}
}
return append(out, gather(rest, other))
}
// gatherLight gathers the columns under 1% of the window's work into
// one named other: they would be strips with next to nothing in them,
// each costing a place a busy directory could open into.
total := 0
for _, w := range weight {
total += w
}
gatherLight := func(cols []column, other string) []column {
var out, rest []column
for _, c := range cols {
if c.weight*100 < total {
rest = append(rest, c)
} else {
out = append(out, c)
}
}
if len(rest) < 2 {
return cols
}
return append(out, gather(rest, other))
}
all := make([]int, len(act.Paths))
for i := range all {
all[i] = i
}
cols := group(all, 1)
// The files at the top of the tree are one column, not one each.
var root, dirs []column
for _, c := range cols {
if len(c.members) == 1 && len(parts[c.members[0]]) == 1 {
root = append(root, c)
} else {
dirs = append(dirs, c)
}
}
if len(root) > 1 {
cols = append(dirs, gather(root, "(root files)"))
}
cols = keepHeaviest(gatherLight(cols, "(other)"), limit, "(other)")
for {
// The busiest column that opens: into all its children when they
// fit, else into as many of the heaviest as there is room for and
// one gathering the rest.
room := limit - (len(cols) - 1)
byWeight := make([]int, len(cols))
for i := range byWeight {
byWeight[i] = i
}
sort.SliceStable(byWeight, func(a, b int) bool { return cols[byWeight[a]].weight > cols[byWeight[b]].weight })
best, bestKids := -1, []column(nil)
for _, c := range byWeight {
col := cols[c]
if col.name != "" || len(col.members) < 2 || col.weight == 0 {
continue
}
kids := group(col.members, col.depth+1)
for len(kids) == 1 && kids[0].depth < maxDepth(parts, kids[0].members) {
kids = group(kids[0].members, kids[0].depth+1)
}
if len(kids) < 2 {
continue
}
if len(kids) > room {
if room < 3 {
continue
}
dir := strings.Join(parts[kids[0].members[0]][:kids[0].depth-1], "/") + "/"
kids = keepHeaviest(gatherLight(kids, dir+"(other)"), room, dir+"(other)")
}
best, bestKids = c, kids
break
}
if best < 0 {
break
}
cols = append(cols[:best], append(bestKids, cols[best+1:]...)...)
}
// Order the columns as the index orders paths: by the first path in
// each, which keeps a directory's columns together.
sort.SliceStable(cols, func(a, b int) bool { return cols[a].members[0] < cols[b].members[0] })
colOf = make([]int, len(act.Paths))
for c, col := range cols {
first := col.members[0]
if col.name != "" {
names = append(names, col.name)
} else {
names = append(names, colKey(act.Paths[first], parts[first], col.depth))
}
for _, i := range col.members {
colOf[i] = c
}
}
return names, colOf, true
}
// colKey names path i's column at depth: the path itself when it is no
// deeper, else its first depth components as a directory.
func colKey(path string, parts []string, depth int) string {
if len(parts) <= depth {
return path
}
return strings.Join(parts[:depth], "/") + "/"
}
func maxDepth(parts [][]string, members []int) int {
d := 0
for _, i := range members {
d = max(d, len(parts[i]))
}
return d
}