// Intrinsics used by code from paper 13:
// _Searching for linear codes with large minimum distance_, by Markus Grassl

// Section 2: Computing the minimum weight
// Subsection 2.1: General linear codes

intrinsic WorkFactor(F::FldFin, n::RngIntElt, k::RngIntElt,
                          d::RngIntElt, ranks::[RngIntElt]) -> RngIntElt
{
 Computes the max. number of codewords considered in Magma's
 algorithm to compute the minimum weight of  linear codes.
}
  w := 0;
  repeat
    w +:= 1;
    lb := &+[ w + 1 - (k - x) : x in ranks | w + x - k ge 0 ];
  until lb ge Minimum(d, n - k + 1) or w ge k;
  w0 := w;
  vprintf Code: "maximal weight: %o\n", w0;
  ranks_used := [ x : x in ranks | x ge k - w0 ];
  vprintf Code: "relative ranks used: %o\n", ranks_used;
  work := 0;
  for w := 1 to w0 do
    work +:= #ranks_used*Binomial(k, w)*(#F - 1)^(w - 1);
    lb := &+[ w + 1 - (k - x) : x in ranks_used | x ge k - w ];
    vprintf Code: "w=%o: lower bound: %o, count: %o=2^%o\n",
                   w, lb, work, Ilog2(work);
  end for;
  return work;
end intrinsic;

// Subsection 2.2: Cyclic codes

intrinsic CyclicWorkFactor(F::FldFin, n::RngIntElt, k::RngIntElt,
                                                    d::RngIntElt) -> RngIntElt
{
 Computes the max. number of codewords considered in Magma's
 algorithm to compute the minimum weight of a cyclic code.
}
  w0 := Floor(d*k/n);
  vprintf Code: "maximal weight: %o\n", w0;
  work := 0;
  w := 0;
  lb := 1;
  repeat
    w +:= 1;
    work +:= Binomial(k, w)*(#F - 1)^(w - 1);
    lb := Ceiling(n/k*(w + 1));
    vprintf Code: "w=%o: lower bound: %o, count: %o=2^%o\n",
                   w, lb, work, Ilog2(work);
  until lb ge Minimum(d, n - k + 1) or w ge k;
  return work;
end intrinsic;

// Subsection 2.3: The MacWilliams transform

intrinsic new_MinimumWeight(C::Code) -> RngIntElt
{
 Computes the minimum distance of the code either by Magma's
 internal algorithm or via the weight distribution
}
  F := Alphabet(C);
  n := Length(C);
  k := Dimension(C);
  if not assigned C`MinimumWeight then
    work_wd := #F^Minimum(k, n - k);
    if IsCyclic(C) then
      work := CyclicWorkFactor(F, n, k, n - k + 1);
    else
      ranks := [ k : i in [1..n-k-1 by k] ] cat [ n mod k ];
      work := WorkFactor(F, n, k, n - k + 1, ranks);
    end if;
    if work_wd lt work then
      vprint Code: "using the weight distribution";
      wd := WeightDistribution(C);
    end if;
  end if;
  return MinimumWeight(C);
end intrinsic;


// Section 4: Searching for good codes
// Subsection 4.1: Cyclic codes

intrinsic AllCyclicCodes(F::FldFin, n::RngIntElt) -> SetEnum
{
 Returns the set of all cyclic codes of  length n over F
}
  P := PolynomialRing(F);
  L_f := { f[1] : f in Factorisation(P.1^n - 1) };
  if #L_f gt 16 then
    printf "WARNING: there are 2^%o codes\n", #L_f;
  end if;
  L_c := { CyclicCode(n, &*y) : y in Subsets(L_f) };
  return L_c;
end intrinsic;

intrinsic CyclicSubcodes(C::Code) -> SetEnum
{
 Returns the set of all maximal proper cyclic subcodes of C
}
  if Dimension(C) eq 0 then
    return {};
  else
    n := Length(C);
    g := GeneratorPolynomial(C);
    g0 := Parent(g).1^n - 1;
    g1 := g0 div g;
    L_c := { CyclicCode(n, g*f[1]) : f in Factorisation(g1) };
    return L_c;
  end if;
end intrinsic;

intrinsic CyclicSupercodes(C::Code) -> SetEnum
{
 Returns the set of all cyclic codes for which C is a maximal proper subcode
}
  n := Length(C);
  if Dimension(C) eq n then
    return {};
  else
    g := GeneratorPolynomial(C);
    L_c := { CyclicCode(n, g div f[1]) : f in Factorisation(g) };
    return L_c;
  end if;
end intrinsic;

// Subsection 4.2: Other techniques

intrinsic TestConstructionY1(C::Code, w::RngIntElt) -> Code
{
 Searches for a non-zero codeword of weight
 at most w in the dual code of C. If such a word
 exists, Construction Y1 is applied to C, else
 the code C is returned.
}
  D := Dual(C);
  if VerifyMinimumWeightUpperBound(D,w) then
    v := D`MinimumWeightUpperBoundWord;
    C1 := ShortenCode(C, Support(v));
  else
    C1 := C;
  end if;
  return C1;
end intrinsic;