package cayley

// Mat2 is a 2×2 matrix [[a,b],[c,d]] over Z_P for SL(2).
// Determinant is not enforced by the type — caller must ensure det=1 for SL(2).
type Mat2 struct {
	A, B, C, D int64
}

// ID returns the identity matrix.
func ID() Mat2 { return Mat2{1, 0, 0, 1} }

// Mul returns m1 * m2 mod P.
func (m1 Mat2) Mul(m2 Mat2, P int64) Mat2 {
	return Mat2{
		A: mod((m1.A*m2.A+m1.B*m2.C)%P, P),
		B: mod((m1.A*m2.B+m1.B*m2.D)%P, P),
		C: mod((m1.C*m2.A+m1.D*m2.C)%P, P),
		D: mod((m1.C*m2.B+m1.D*m2.D)%P, P),
	}
}

// Eq reports whether m1 == m2.
func (m1 Mat2) Eq(m2 Mat2) bool {
	return mod(m1.A, 1<<60) == mod(m2.A, 1<<60) &&
		mod(m1.B, 1<<60) == mod(m2.B, 1<<60) &&
		mod(m1.C, 1<<60) == mod(m2.C, 1<<60) &&
		mod(m1.D, 1<<60) == mod(m2.D, 1<<60)
}

// Det returns det(m) mod P.
func (m Mat2) Det(P int64) int64 {
	return mod((m.A*m.D-m.B*m.C)%P, P)
}

// Inv returns m^{-1} mod P (for SL(2)).
func (m Mat2) Inv(P int64) Mat2 {
	return Mat2{
		A: mod(m.D, P),
		B: mod(-m.B, P),
		C: mod(-m.C, P),
		D: mod(m.A, P),
	}
}

func mod(x, P int64) int64 {
	x = x % P
	if x < 0 {
		x += P
	}
	return x
}

// Standard generators of SL(2): g0 = [[1,1],[0,1]], g1 = [[1,0],[1,1]].
var (
	StdG0  = Mat2{1, 1, 0, 1}
	StdG1  = Mat2{1, 0, 1, 1}
	StdG0I = Mat2{1, -1, 0, 1} // g0^{-1}
	StdG1I = Mat2{1, 0, -1, 1} // g1^{-1}
)

// GeneratorSet holds a set of generators (as matrices) for the Cayley graph.
type GeneratorSet struct {
	Gens  []Mat2 // b generators (each with an inverse implied)
	P     int64
	Names []string // optional names
}

// StandardGens returns the 4 standard SL(2) generators with their inverses.
func StandardGens(P int64) *GeneratorSet {
	return &GeneratorSet{
		Gens: []Mat2{
			modMat2(StdG0, P),
			modMat2(StdG1, P),
			modMat2(StdG0I, P),
			modMat2(StdG1I, P),
		},
		P:     P,
		Names: []string{"g0", "g1", "g0i", "g1i"},
	}
}

// Walk returns the group element reached by walking the path from start.
func (gs *GeneratorSet) Walk(start Mat2, path []int8) Mat2 {
	m := start
	for _, idx := range path {
		m = m.Mul(gs.Gens[idx], gs.P)
	}
	return m
}

// PathToBytes encodes a path as a byte slice. Each step takes 1 byte (index 0..b-1).
func PathToBytes(path []int8) []byte {
	b := make([]byte, len(path))
	for i, idx := range path {
		b[i] = byte(idx)
	}
	return b
}

// BytesToPath decodes a byte slice to a path.
func BytesToPath(b []byte) []int8 {
	path := make([]int8, len(b))
	for i, v := range b {
		path[i] = int8(v)
	}
	return path
}

// Norm returns the path length.
func Norm(path []int8) int { return len(path) }

func modMat2(m Mat2, P int64) Mat2 {
	return Mat2{mod(m.A, P), mod(m.B, P), mod(m.C, P), mod(m.D, P)}
}