package main

import "math"

// tiered is the stepped-merge / tiering policy used by ampsim: when level i
// holds T runs they are merged into one run appended to level i+1. With
// lazy set, the last level is kept as a single run (Dostoevsky's lazy
// leveling): the T runs of level last-1 are merged together with it.
type tiered struct {
	mem     memtable
	levels  [][]*run // each level newest run first
	T       int
	last    int
	lazy    bool
	written []int64
	meter
}

// Level 0 here holds memtable-sized runs, i.e. Dostoevsky's level 1.
// Tiered keeps ampsim's depth, ceil(log_T(N/buffer)) + 1 levels. Lazy
// leveling uses Dostoevsky's L = ceil(log_T(N/buffer * (T-1)/T)) levels so
// that the last level is the one holding almost all data.
func newTiered(T int, lazy bool) *tiered {
	ratio := float64(*nKeys) / float64(memCap())
	last := int(math.Ceil(math.Log(ratio) / math.Log(float64(T))))
	if lazy {
		last = int(math.Ceil(math.Log(ratio*float64(T-1)/float64(T))/math.Log(float64(T)))) - 1
	}
	return &tiered{
		mem:     newMemtable(),
		levels:  make([][]*run, last+1),
		T:       T,
		last:    last,
		lazy:    lazy,
		written: make([]int64, last+1),
	}
}

func (t *tiered) put(k uint32) {
	if !t.mem.put(k) {
		return
	}
	keys := t.mem.drain()
	t.written[0] += int64(len(keys))
	t.flush(int64(len(keys)))
	t.levels[0] = append([]*run{newRun(keys)}, t.levels[0]...)
	for i := 0; i <= t.last && len(t.levels[i]) >= t.T; i++ {
		inputs := t.levels[i]
		dst := i + 1
		if i == t.last {
			dst = i
		} else if t.lazy && dst == t.last {
			inputs = append(inputs, t.levels[t.last]...)
		}
		merged := mergeAll(inputs)
		t.written[dst] += int64(len(merged))
		t.compaction(entries(inputs), int64(len(merged)))
		out := newRun(merged)
		t.levels[i] = nil
		if dst == i || (t.lazy && dst == t.last) {
			t.levels[dst] = []*run{out}
		} else {
			t.levels[dst] = append([]*run{out}, t.levels[dst]...)
		}
	}
	t.sample()
	t.sampleRuns(t.groups())
}

func (t *tiered) candidates(k uint32) []*run {
	var out []*run
	for _, lv := range t.levels {
		for _, r := range lv {
			if r.min <= k && k <= r.max {
				out = append(out, r)
			}
		}
	}
	return out
}

func (t *tiered) groups() [][]*run {
	var g [][]*run
	for _, lv := range t.levels {
		for _, r := range lv {
			g = append(g, []*run{r})
		}
	}
	return g
}