git.kianting.info Git - clo/blob - src/libclo/breakLines.ts

   1 /**
   2  * Algorithms and functions for LineBreaking
   3  */
   4 import { join } from "path";
   5 import {BreakPoint, BoxesItem, HGlue, CharBox} from "./index.js";
   6 import { listenerCount } from "process";
   7 import { unwatchFile } from "fs";
   8 /**
   9  * Algorithms in LATEX-like language
  10  */
  11
  12 export class BreakLineAlgorithm {
  13
  14     lineCostStorage : number[][];
  15     totalCostAuxStorage : number[];
  16     prevNodes : number[];
  17
  18
  19
  20     constructor(){
  21         this.prevNodes = [];
  22         this.totalCostAuxStorage = [];
  23         this.lineCostStorage = [[]];
  24     }
  25
  26     /**check if a boeitem is BreakPoint Type */
  27     isBreakPoint (item : any) : item is BreakPoint{
  28         return (item as BreakPoint).newLined !== undefined;
  29     }
  30
  31     /**check if a boeitem is HGlue Type */
  32     isHGlue (item : any) : item is HGlue{
  33         return (item as HGlue).stretchFactor !== undefined;
  34     }
  35
  36
  37     /** measuring original advance width */
  38     origWidth(item : BoxesItem) : number{
  39         if (this.isBreakPoint(item)){
  40             return this.origWidth(item.original);
  41         }else if(Array.isArray(item)){
  42             return item.map((x)=>this.origWidth(x))
  43                 .reduce((acc, current) => acc + current,
  44                 0.0,)
  45         }else if(this.isHGlue(item)){
  46             return 0.0;
  47         }
  48         else{
  49             return item.width;
  50         }
  51     }
  52
  53     /**segement node of one paragraph into lines.
  54      * @args items: nodes of a line
  55      * @args linewidth: the line width
  56      * @returns segmented nodes into lines
  57     */
  58     segmentedNodes(items : BoxesItem[], lineWidth : number) : BoxesItem[][]{
  59
  60         let lineWidthFixed = lineWidth;
  61         this.totalCost(items ,lineWidthFixed);
  62         let nodeList = this.generateBreakLineNodeList();
  63         let res = [];
  64         let low = -1;
  65         let up = nodeList[0];
  66
  67         for(var i=0; i<nodeList.length; i++){
  68             res.push(items.slice(low+1, up+1));
  69             low = nodeList[i];
  70             up = nodeList[i+1];
  71
  72         }
  73
  74
  75         return res;
  76     }
  77
  78     /**genrate the list of point of breaking line. it returns a correct list ascending*/
  79     generateBreakLineNodeList() : number[]{
  80         let res : number[] = [];
  81         var pointer = this.prevNodes.length-1;
  82         while (this.prevNodes[pointer] !== undefined){
  83             res.push(pointer);
  84             pointer = this.prevNodes[pointer];
  85         }
  86         return res.reverse();
  87     }
  88
  89     /** measuring new-line triggered advance width */
  90     newLineWidth(item : BoxesItem) : number{
  91         if (this.isBreakPoint(item)){
  92             return this.origWidth(item.newLined);
  93         }else{
  94             // impossible to make a new line
  95             return Infinity;
  96         }
  97     }
  98     /**
  99      * check all the total cost of paragraphes of the segnemt
 100      */
 101     totalCost(items : BoxesItem[], lineWidth: number) : number{
 102         let lineWidthFixed = lineWidth * 0.75;
 103         let itemsLength = items.length;
 104         this.lineCostStorage = Array(itemsLength);
 105         this.prevNodes = Array(itemsLength).fill(null);
 106
 107
 108         for (var i=0; i<itemsLength; i++){
 109             this.lineCostStorage[i] = Array(itemsLength).fill(null);
 110         }
 111
 112         this.totalCostAuxStorage = Array(itemsLength).fill(null);
 113
 114         let a = Infinity;
 115         for(var k=itemsLength-2; this.lineCost(items, k+1,itemsLength-1, lineWidthFixed) < Infinity; k--){
 116
 117             let tmp = this.totalCostAux(items, k, lineWidthFixed);
 118
 119             if (a > tmp){
 120                 this.prevNodes[itemsLength-1] = k
 121                 a = tmp;
 122             }
 123
 124         }
 125         return a;
 126
 127     }
 128
 129     /**
 130      * check the total cost item[0..j].
 131      * @param items
 132      * @param i
 133      * @param lineWidth
 134      */
 135     totalCostAux(items : BoxesItem[], j : number, lineWidth: number): number{
 136
 137         if (this.totalCostAuxStorage[j] !== null){
 138             return this.totalCostAuxStorage[j];
 139         }
 140
 141         let rawLineCost = this.lineCost(items, 0, j, lineWidth);
 142         if (rawLineCost != Infinity){
 143             this.totalCostAuxStorage[j] = rawLineCost**3.0;
 144             return rawLineCost**3.0;
 145         }else{
 146             var returnCost = Infinity;
 147             for(var k=0; k<j; k++){
 148                 let tmp = this.totalCostAux(items, k, lineWidth) + this.lineCost(items, k+1,j, lineWidth)**3.0;
 149                 if (returnCost > tmp){
 150                     this.prevNodes[j] = k;
 151                     returnCost = tmp;
 152                 }
 153             }
 154             this.totalCostAuxStorage[j] = returnCost;
 155             return returnCost;
 156
 157         }
 158
 159
 160
 161     }
 162
 163
 164
 165     /**
 166      * check the line cost of a line containing items[i..j]
 167      * @param items items of box
 168      * @param i beginning (excluded)
 169      * @param j end of the line
 170      * @param lineWidth line width
 171      */
 172     lineCost(items : BoxesItem[], i : number, j : number, lineWidth: number) : number{
 173         if (this.lineCostStorage[i][j] !== null){
 174             console.log("AA")
 175             return this.lineCostStorage[i][j];
 176         }
 177
 178         if (!this.isBreakPoint(items[j])){
 179             this.lineCostStorage[i][j] = Infinity;
 180             return Infinity;
 181         }else{
 182             var tmpItemWidth = 0;
 183             for (var k = i; k<j; k++){
 184                 tmpItemWidth += this.origWidth(items[k]);
 185             }
 186
 187             tmpItemWidth += this.newLineWidth(items[j]);
 188
 189             if (tmpItemWidth > lineWidth){
 190                 this.lineCostStorage[i][j] = Infinity;
 191                 return Infinity;
 192             }else{
 193                 let returnValue = (lineWidth - tmpItemWidth);
 194                 this.lineCostStorage[i][j] = returnValue;
 195                 return returnValue;
 196             }
 197         }
 198
 199     }
 200
 201 }