Luna Flow
简体中文

mutable/sparse API

Luna-Flow/luna-poly/mutable/sparse 提供可变的 SparsePolynomial[A]：与 immut/sparse 一样，是从 ExponentVector 到非零系数的有序映射，其方法以对数时间原地更新该映射。

该类型由 mutable 门面包重新导出为 @mutable.SparsePolynomial，示例中使用的就是它。“同 immut”指与 immut/sparse API 的语义、约束和代价相同。可变模型见 mutable/sparse 设计。

类型

SparsePolynomial

从指数向量到非零系数的可变映射，按单项式序升序迭代。

type SparsePolynomial[A] derive(@debug.Debug)
pub impl[A : Eq] Eq for SparsePolynomial[A]
pub impl[A] @luna-generic.Zero for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + @luna-generic.One] @luna-generic.One for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] Add for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Neg] Sub for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul] Mul for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.Zero + Neg] Neg for SparsePolynomial[A]
pub impl[A : Show + @luna-generic.Zero] Show for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] @arithmetic.PowNatChecked for SparsePolynomial[A]
pub impl[A] @core.Clearable for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] @core.Copyable for SparsePolynomial[A]
pub impl[A] @core.HasArity for SparsePolynomial[A]
pub impl[A] @core.HasShape for SparsePolynomial[A]
pub impl[A] @core.HasTermCount for SparsePolynomial[A]
pub impl[A] @core.HasTotalDegree for SparsePolynomial[A]
pub impl[A] @core.IsZero for SparsePolynomial[A]
pub impl[A] @core.MultivariatePolynomial for SparsePolynomial[A]
pub impl[A : Eq + @luna-generic.AddMonoid] @core.MutablePolynomial for SparsePolynomial[A]

这里 Copyable 和 MutablePolynomial 要求系数满足 Eq + AddMonoid，因为 copy 通过 from_terms 重建映射。

构造与转换

SparsePolynomial::new, SparsePolynomial::zero, SparsePolynomial::one, SparsePolynomial::from_terms, SparsePolynomial::from_array

构造多项式，同 immut。

pub fn[A] SparsePolynomial::new() -> Self[A]
pub fn[A] SparsePolynomial::zero() -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + @luna-generic.One] SparsePolynomial::one() -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::from_terms(Array[(@core.ExponentVector, A)]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::from_array(Array[(Array[UInt], A)]) -> Self[A]

SparsePolynomial::from_immut, SparsePolynomial::to_immut

与不可变类型互相转换；两者都会构建新的映射。

pub fn[A] SparsePolynomial::from_immut(@Luna-Flow/luna-poly/immut/sparse.SparsePolynomial[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::to_immut(Self[A]) -> @Luna-Flow/luna-poly/immut/sparse.SparsePolynomial[A]

SparsePolynomial::copy

返回一个独立副本（也即 Copyable::copy），O(mlog⁡m)O(m \log m)。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::copy(Self[A]) -> Self[A]

查询

SparsePolynomial::get, SparsePolynomial::get_checked, SparsePolynomial::to_terms, SparsePolynomial::size, SparsePolynomial::term_count, SparsePolynomial::is_empty, SparsePolynomial::is_zero, SparsePolynomial::arity, SparsePolynomial::total_degree, SparsePolynomial::shape

同 immut：get 是 O(log⁡m)O(\log m) 的查找，对不存在的（零）项返回 None；to_terms 返回按升序排列的新数组。

pub fn[A] SparsePolynomial::get(Self[A], @core.ExponentVector) -> A?
pub fn[A] SparsePolynomial::get_checked(Self[A], @core.ExponentVector) -> A?
pub fn[A] SparsePolynomial::to_terms(Self[A]) -> Array[(@core.ExponentVector, A)]
pub fn[A] SparsePolynomial::size(Self[A]) -> Int
pub fn[A] SparsePolynomial::term_count(Self[A]) -> Int
pub fn[A] SparsePolynomial::is_empty(Self[A]) -> Bool
pub fn[A] SparsePolynomial::is_zero(Self[A]) -> Bool
pub fn[A] SparsePolynomial::arity(Self[A]) -> Int
pub fn[A] SparsePolynomial::total_degree(Self[A]) -> UInt?
pub fn[A] SparsePolynomial::shape(Self[A]) -> @core.PolynomialShape

修改

SparsePolynomial::set_coefficient

设置 xαx^\alpha 的系数；设为零会删除该键。O(log⁡m)O(\log m)。

pub fn[A : Eq + @luna-generic.Zero] SparsePolynomial::set_coefficient(Self[A], @core.ExponentVector, A) -> Unit

SparsePolynomial::add_term_inplace

加上 c xαc\,x^\alpha：插入新键，或加到已有系数上，并在和为零时删除该键。cc 为零时不做任何事。O(log⁡m)O(\log m)。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add_term_inplace(Self[A], @core.ExponentVector, A) -> Unit

SparsePolynomial::add_inplace

用 add_term_inplace 逐项加上 other 的每一项，O(nlog⁡(m+n))O(n \log(m + n))。p.add_inplace(p) 使 p 加倍。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add_inplace(Self[A], Self[A]) -> Unit

SparsePolynomial::mul_inplace

将内容替换为 self * other；乘积先算出，因此 p.mul_inplace(p) 得到 p 的平方。

pub fn[A : Eq + @luna-generic.AddMonoid + Mul] SparsePolynomial::mul_inplace(Self[A], Self[A]) -> Unit

SparsePolynomial::scale_inplace

将内容替换为 c xγ⋅pc\,x^\gamma \cdot p。

pub fn[A : Eq + @luna-generic.Zero + Mul] SparsePolynomial::scale_inplace(Self[A], @core.ExponentVector, A) -> Unit

SparsePolynomial::clear

删除所有项（也即 Clearable::clear）。

pub fn[A] SparsePolynomial::clear(Self[A]) -> Unit
test "mutation" {
  let x = @mutable.ExponentVector::from_array([1U])
  let p : @mutable.SparsePolynomial[Int] = @mutable.SparsePolynomial::new()
  p.set_coefficient(x, 3)
  p.add_term_inplace(x, -1)
  debug_inspect(p.get(x), content="Some(2)")
  p.add_term_inplace(@mutable.ExponentVector::one(), 5)
  p.add_inplace(p)
  inspect(p, content="10 + 4 * x")
  p.set_coefficient(x, 0)
  inspect(p, content="10")
  p.clear()
  assert_true(p.is_empty())
}

非修改操作

SparsePolynomial::add, SparsePolynomial::sub, SparsePolynomial::mul, SparsePolynomial::neg, SparsePolynomial::scale, SparsePolynomial::pow

运算符和算术方法，返回新多项式，同 immut。+ 复制接收者并调用 add_inplace。

pub fn[A : Eq + @luna-generic.AddMonoid] SparsePolynomial::add(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Neg] SparsePolynomial::sub(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Mul] SparsePolynomial::mul(Self[A], Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Neg] SparsePolynomial::neg(Self[A]) -> Self[A]
pub fn[A : Eq + @luna-generic.Zero + Mul] SparsePolynomial::scale(Self[A], @core.ExponentVector, A) -> Self[A]
pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::pow(Self[A], UInt) -> Self[A]

SparsePolynomial::eval, SparsePolynomial::eval_checked, SparsePolynomial::equal, SparsePolynomial::to_string, SparsePolynomial::ops

求值、相等、打印以及 MultivariateOps 记录，同 immut。

pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::eval(Self[A], Array[A]) -> A
pub fn[A : @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::eval_checked(Self[A], Array[A]) -> A?
pub fn[A : Eq] SparsePolynomial::equal(Self[A], Self[A]) -> Bool
pub fn[A : Show + @luna-generic.Zero] SparsePolynomial::to_string(Self[A]) -> String
pub fn[A : Eq + @luna-generic.AddMonoid + Mul + @luna-generic.One] SparsePolynomial::ops() -> @core.MultivariateOps[Self[A], A]
test "non-mutating" {
  let p = @mutable.SparsePolynomial::from_array([([1U], 1), ([], 1)])
  let q = p * p
  inspect(q, content="1 + 2 * x + 1 * x^2")
  inspect(p, content="1 + 1 * x")
  inspect(q.eval([2]), content="9")
}

已弃用

为源码兼容而保留的隐藏方法形式：

已弃用替代方案
p.not_equal(q)p != q
p.output(logger)to_string 或字符串插值
p.to_repr()Repr(p) 或 debug_inspect
p.pow_nat_checked(e, ctx)@arithmetic.PowNatChecked::pow_nat_checked(p, e, ctx) 或 p.pow(e)