code128.ts

/* eslint-disable @typescript-eslint/no-non-null-assertion */
// https://github.com/graphicore/librebarcode/blob/e44a85e71bd40564fbd1e88b215c619f6be85858/app/lib/code128Encoder/encoder.mjs

const data: [number, string, string, string, string | string[]][] = [
    // the unicode chars are from:
    //   www.idautomation.com/barcode-fonts/code.128/user-manual.html
    //   http://www.jtbarton.com/Barcodes/Code128.aspx
    // checksum value, pattern, canonical id/name (based on Code Set B)
    // (name of the glyph in the font?), [unicode chars], textbelow_flag_or_charcodes
    [0, " ", " ", "00", [" ", "Â"]],
    [1, "!", "!", "01", "!"],
    [2, '"', '"', "02", '"'],
    [3, "#", "#", "03", "#"],
    [4, "$", "$", "04", "$"],
    [5, "%", "%", "05", "%"],
    [6, "&", "&", "06", "&"],
    [7, "'", "'", "07", "'"],
    [8, "(", "(", "08", "("],
    [9, ")", ")", "09", ")"],
    [10, "*", "*", "10", "*"],
    [11, "+", "+", "11", "+"],
    [12, ",", ",", "12", ","],
    [13, "-", "-", "13", "-"],
    [14, ".", ".", "14", "."],
    [15, "/", "/", "15", "/"],
    [16, "0", "0", "16", "0"],
    [17, "1", "1", "17", "1"],
    [18, "2", "2", "18", "2"],
    [19, "3", "3", "19", "3"],
    [20, "4", "4", "20", "4"],
    [21, "5", "5", "21", "5"],
    [22, "6", "6", "22", "6"],
    [23, "7", "7", "23", "7"],
    [24, "8", "8", "24", "8"],
    [25, "9", "9", "25", "9"],
    [26, ":", ":", "26", ":"],
    [27, ";", ";", "27", ";"],
    [28, "<", "<", "28", "<"],
    [29, "=", "=", "29", "="],
    [30, ">", ">", "30", ">"],
    [31, "?", "?", "31", "?"],
    [32, "@", "@", "32", "@"],
    [33, "A", "A", "33", "A"],
    [34, "B", "B", "34", "B"],
    [35, "C", "C", "35", "C"],
    [36, "D", "D", "36", "D"],
    [37, "E", "E", "37", "E"],
    [38, "F", "F", "38", "F"],
    [39, "G", "G", "39", "G"],
    [40, "H", "H", "40", "H"],
    [41, "I", "I", "41", "I"],
    [42, "J", "J", "42", "J"],
    [43, "K", "K", "43", "K"],
    [44, "L", "L", "44", "L"],
    [45, "M", "M", "45", "M"],
    [46, "N", "N", "46", "N"],
    [47, "O", "O", "47", "O"],
    [48, "P", "P", "48", "P"],
    [49, "Q", "Q", "49", "Q"],
    [50, "R", "R", "50", "R"],
    [51, "S", "S", "51", "S"],
    [52, "T", "T", "52", "T"],
    [53, "U", "U", "53", "U"],
    [54, "V", "V", "54", "V"],
    [55, "W", "W", "55", "W"],
    [56, "X", "X", "56", "X"],
    [57, "Y", "Y", "57", "Y"],
    [58, "Z", "Z", "58", "Z"],
    [59, "[", "[", "59", "["],
    [60, "\\", "\\", "60", "\\"],
    [61, "]", "]", "61", "]"],
    [62, "^", "^", "62", "^"],
    [63, "_", "_", "63", "_"],
    [64, "NUL", "`", "64", "`"],
    [65, "SOH", "a", "65", "a"],
    [66, "STX", "b", "66", "b"],
    [67, "ETX", "c", "67", "c"],
    [68, "EOT", "d", "68", "d"],
    [69, "ENQ", "e", "69", "e"],
    [70, "ACK", "f", "70", "f"],
    [71, "BEL", "g", "71", "g"],
    [72, "BS", "h", "72", "h"],
    [73, "HT", "i", "73", "i"],
    [74, "LF", "j", "74", "j"],
    [75, "VT", "k", "75", "k"],
    [76, "FF", "l", "76", "l"],
    [77, "CR", "m", "77", "m"],
    [78, "SO", "n", "78", "n"],
    [79, "SI", "o", "79", "o"],
    [80, "DLE", "p", "80", "p"],
    [81, "DC1", "q", "81", "q"],
    [82, "DC2", "r", "82", "r"],
    [83, "DC3", "s", "83", "s"],
    [84, "DC4", "t", "84", "t"],
    [85, "NAK", "u", "85", "u"],
    [86, "SYN", "v", "86", "v"],
    [87, "ETB", "w", "87", "w"],
    [88, "CAN", "x", "88", "x"],
    [89, "EM", "y", "89", "y"],
    [90, "SUB", "z", "90", "z"],
    [91, "ESC", "{", "91", "{"],
    [92, "FS", "|", "92", "|"],
    [93, "GS", "}", "93", "}"],
    [94, "RS", "~", "94", "~"],
    [95, "US", "DEL", "95", "Ã"],
    [96, "FNC 3", "FNC 3", "96", "Ä"],
    [97, "FNC 2", "FNC 2", "97", "Å"],
    [98, "Shift B", "Shift A", "98", "Æ"],
    [99, "Code C", "Code C", "99", "Ç"],
    [100, "Code B", "FNC 4", "Code B", "È"],
    [101, "FNC 4", "Code A", "Code A", "É"],
    [102, "FNC 1", "FNC 1", "FNC 1", "Ê"],
    [103, "Start Code A", "Start Code A", "Start Code A", "Ë"],
    [104, "Start Code B", "Start Code B", "Start Code B", "Ì"],
    [105, "Start Code C", "Start Code C", "Start Code C", "Í"],
  ],
  stopChar = "Î";

class CodeSymbol {
  constructor(
    public value: string,
    public checksumValue: number,
    public code: CodeSet,
    public switchedCode: CodeSet | null,
    public char: string,
    public isCtrl: boolean,
  ) {
    this.weight = this.calculateWeight(isCtrl, value);
    this.isShift = new Set(["Shift B", "Shift A"]).has(value);
    this.isSwitch = !!switchedCode;
  }

  weight: number;
  isShift: boolean;
  isSwitch: boolean;

  toString() {
    return `<Code ${this.code.name}: ${this.value}>`;
  }

  private calculateWeight(isCtrl: boolean, value: string) {
    return 1 - (isCtrl ? 0 : value.length);
  }
}

class CodeSet {
  private _values = new Map<
    string,
    [number, string, string, string, string | string[]]
  >();
  private _symbols = new Map<string, CodeSymbol>();
  private _byIndex: string[] = [];
  private _switchSymbols?: CodeSymbol[];

  constructor(
    public name: string,
    data: [number, string, string, string, string | string[]][],
    public stopChar: string,
  ) {
    let column: 1 | 2 | 3 = 1;
    switch (this.name) {
      case "A":
        column = 1;
        break;
      case "B":
        column = 2;
        break;
      case "C":
        column = 3;
        break;
    }
    for (let i = 0, l = data.length; i < l; i++) {
      this._values.set(data[i][column], data[i]);
      this._byIndex[i] = data[i][column];
    }
  }

  getByIndex(index: number) {
    return this.get(this._byIndex[index]);
  }

  get switchSymbols() {
    if (!this._switchSymbols) {
      this._switchSymbols = [
        this.get("Code A"),
        this.get("Code B"),
        this.get("Code C"),
        this.get("Shift A"),
        this.get("Shift B"),
      ].filter((s) => !!s) as CodeSymbol[];
    }
    return this._switchSymbols;
  }

  get(value: string) {
    if (!this._values.has(value)) return null;

    let symbol = this._symbols.get(value);
    if (!symbol) {
      const data = this._values.get(value)!;
      const checksumValue = data[0] as number;
      const char = Array.isArray(data[data.length - 1])
        ? (data[data.length - 1] as string[])[0]
        : data[data.length - 1];
      let switchedCode: CodeSet | null = null;

      switch (value) {
        case "Shift A":
        case "Start Code A":
        case "Code A":
          switchedCode = codeSetA;
          break;
        case "Shift B":
        case "Start Code B":
        case "Code B":
          switchedCode = codeSetB;
          break;
        case "Start Code C":
        case "Code C":
          switchedCode = codeSetC;
          break;
      }

      const isCtrl =
        this.name === "A"
          ? checksumValue >= 64
          : this.name === "B"
            ? checksumValue >= 95
            : checksumValue >= 100;

      symbol = new CodeSymbol(
        value,
        checksumValue,
        this,
        switchedCode,
        char as string,
        isCtrl,
      );
      this._symbols.set(value, symbol);
    }
    return symbol;
  }
}

const codeSetA = new CodeSet("A", data, stopChar);
const codeSetB = new CodeSet("B", data, stopChar);
const codeSetC = new CodeSet("C", data, stopChar);
const startCodeA = codeSetA.get("Start Code A")!;
const startCodeB = codeSetB.get("Start Code B")!;
const startCodeC = codeSetC.get("Start Code C")!;

function _addPaths(weight2Paths: Map<number, Encoding[]>, paths: Encoding[]) {
  for (const encoded of paths) {
    const equalWeightPaths = weight2Paths.get(encoded.weight) || [];
    equalWeightPaths.push(encoded);
    weight2Paths.set(encoded.weight, equalWeightPaths);
  }
}

function findSolutions(value: string) {
  const weight2Paths = new Map<number, Encoding[]>();
  _addPaths(weight2Paths, [
    new Encoding([startCodeB]),
    new Encoding([startCodeA]),
    new Encoding([startCodeC]),
  ]);

  const explored = new Map<string, Set<CodeSymbol>>();
  let lightest: number | undefined;

  while (weight2Paths.size) {
    const weights = Array.from(weight2Paths.keys());
    lightest = Math.min(...weights);
    if (lightest === undefined) break;

    const lightestPaths = weight2Paths.get(lightest)!;
    weight2Paths.delete(lightest);

    for (const encoded of lightestPaths) {
      const [solution, intermediates] = nextStep(explored, value, encoded);
      if (solution) return solution;
      _addPaths(weight2Paths, intermediates);
    }
  }
  return null;
}

class Encoding {
  weight: number;
  value: string;
  symbols: readonly CodeSymbol[];

  constructor(symbols: CodeSymbol[], _value?: string, _weight?: number) {
    this.symbols = Object.freeze(symbols);
    this.value =
      _value || symbols.map((s) => (s.isCtrl ? "" : s.value)).join("");
    this.weight = _weight || this.value.length + symbolsWeightChange(symbols);
  }

  addSymbol(symbol: CodeSymbol) {
    const symbols = [...this.symbols, symbol];
    const newValue = this.value + (symbol.isCtrl ? "" : symbol.value);
    const oldSymbolsChange = this.weight - this.value.length;
    return new Encoding(
      symbols,
      newValue,
      newValue.length + oldSymbolsChange + symbol.weight,
    );
  }

  toString() {
    return this.symbols.join(" ");
  }

  get lastSymbol() {
    if (!this.symbols.length) throw new Error("There are no symbols yet");
    return this.symbols[this.symbols.length - 1];
  }

  get currentCode() {
    if (
      this.symbols.length >= 3 &&
      this.symbols[this.symbols.length - 2].isShift
    ) {
      return this.symbols[this.symbols.length - 2].code;
    }
    return this.lastSymbol.switchedCode!;
  }

  get chars() {
    if (!this._chars) {
      const allChars = this.symbols.map((s) => s.char);
      allChars.push(this._getCheckSumSymbol().char, this.currentCode.stopChar);
      this._chars = allChars.join("");
    }
    return this._chars;
  }

  private _chars?: string;

  private _calculateChecksum() {
    return (
      this.symbols.reduce(
        (sum, symbol, i) => sum + (i === 0 ? 1 : i) * symbol.checksumValue,
        0,
      ) % 103
    );
  }

  private _getCheckSumSymbol() {
    const checkSum = this._calculateChecksum();
    return this.currentCode.getByIndex(checkSum)!;
  }
}

function nextStep(
  explored: Map<string, Set<CodeSymbol>>,
  value: string,
  encoded: Encoding,
): [Encoding | null, Encoding[]] {
  const intermediates: Encoding[] = [];
  const code = encoded.currentCode;
  const symbolValue = value.slice(
    encoded.value.length,
    encoded.value.length + (encoded.currentCode === codeSetC ? 2 : 1),
  );
  const symbol = code.get(symbolValue);
  const nextSymbols: CodeSymbol[] = symbol ? [symbol] : [];

  const exploredKey = `${encoded.currentCode.name}::${encoded.value}`;
  const exploredSet = explored.get(exploredKey) || new Set<CodeSymbol>();
  explored.set(exploredKey, exploredSet);

  if (!encoded.lastSymbol.isSwitch) {
    nextSymbols.push(...code.switchSymbols);
  }

  for (const symbol of nextSymbols) {
    if (exploredSet.has(symbol)) continue;
    exploredSet.add(symbol);
    const newEncoded = encoded.addSymbol(symbol);
    if (newEncoded.value === value) return [newEncoded, []];
    intermediates.push(newEncoded);
  }
  return [null, intermediates];
}

function symbolsWeightChange(symbols: CodeSymbol[]) {
  return symbols.reduce((reduction, symbol) => reduction + symbol.weight, 0);
}

export default function encode(value: string) {
  const result = findSolutions(value);
  return result?.chars || result;
}