internal/diff/lcs/labels.go

// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package lcs

import (
	"fmt"
)

// For each D, vec[D] has length D+1,
// and the label for (D, k) is stored in vec[D][(D+k)/2].
type label struct {
	vec [][]int
}

// Temporary checking DO NOT COMMIT true TO PRODUCTION CODE
const debug = false

// debugging. check that the (d,k) pair is valid
// (that is, -d<=k<=d and d+k even)
func checkDK(D, k int) {
	if k >= -D && k <= D && (D+k)%2 == 0 {
		return
	}
	panic(fmt.Sprintf("out of range, d=%d,k=%d", D, k))
}

func (t *label) set(D, k, x int) {
	if debug {
		checkDK(D, k)
	}
	for len(t.vec) <= D {
		t.vec = append(t.vec, nil)
	}
	if t.vec[D] == nil {
		t.vec[D] = make([]int, D+1)
	}
	t.vec[D][(D+k)/2] = x // known that D+k is even
}

func (t *label) get(d, k int) int {
	if debug {
		checkDK(d, k)
	}
	return int(t.vec[d][(d+k)/2])
}

func newtriang(limit int) label {
	if limit < 100 {
		// Preallocate if limit is not large.
		return label{vec: make([][]int, limit)}
	}
	return label{}
}