1// Copyright 2022 The Go Authors. All rights reserved.
 2// Use of this source code is governed by a BSD-style
 3// license that can be found in the LICENSE file.
 4
 5package lcs
 6
 7import (
 8	"fmt"
 9)
10
11// For each D, vec[D] has length D+1,
12// and the label for (D, k) is stored in vec[D][(D+k)/2].
13type label struct {
14	vec [][]int
15}
16
17// Temporary checking DO NOT COMMIT true TO PRODUCTION CODE
18const debug = false
19
20// debugging. check that the (d,k) pair is valid
21// (that is, -d<=k<=d and d+k even)
22func checkDK(D, k int) {
23	if k >= -D && k <= D && (D+k)%2 == 0 {
24		return
25	}
26	panic(fmt.Sprintf("out of range, d=%d,k=%d", D, k))
27}
28
29func (t *label) set(D, k, x int) {
30	if debug {
31		checkDK(D, k)
32	}
33	for len(t.vec) <= D {
34		t.vec = append(t.vec, nil)
35	}
36	if t.vec[D] == nil {
37		t.vec[D] = make([]int, D+1)
38	}
39	t.vec[D][(D+k)/2] = x // known that D+k is even
40}
41
42func (t *label) get(d, k int) int {
43	if debug {
44		checkDK(d, k)
45	}
46	return int(t.vec[d][(d+k)/2])
47}
48
49func newtriang(limit int) label {
50	if limit < 100 {
51		// Preallocate if limit is not large.
52		return label{vec: make([][]int, limit)}
53	}
54	return label{}
55}