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     segmentedNodes(items : BoxesItem[], lineWidth : number) : BoxesItem[][]{
  54
  55         let lineWidthFixed = lineWidth;
  56         this.totalCost(items ,lineWidthFixed);
  57         let nodeList = this.generateBreakLineNodeList();
  58         let res = [];
  59         let low = -1;
  60         let up = nodeList[0];
  61
  62         for(var i=0; i<nodeList.length; i++){
  63             res.push(items.slice(low+1, up+1));
  64             low = nodeList[i];
  65             up = nodeList[i+1];
  66
  67         }
  68
  69
  70         return res;
  71     }
  72
  73     /**genrate the list of point of breaking line. it returns a correct list ascending*/
  74     generateBreakLineNodeList() : number[]{
  75         let res : number[] = [];
  76         var pointer = this.prevNodes.length-1;
  77         while (this.prevNodes[pointer] !== undefined){
  78             res.push(pointer);
  79             pointer = this.prevNodes[pointer];
  80         }
  81         return res.reverse();
  82     }
  83
  84     /** measuring new-line triggered advance width */
  85     newLineWidth(item : BoxesItem) : number{
  86         if (this.isBreakPoint(item)){
  87             return this.origWidth(item.newLined);
  88         }else{
  89             // impossible to make a new line
  90             return Infinity;
  91         }
  92     }
  93     /**
  94      * check all the total cost of paragraphes of the segnemt
  95      */
  96     totalCost(items : BoxesItem[], lineWidth: number) : number{
  97         let lineWidthFixed = lineWidth * 0.75;
  98         let itemsLength = items.length;
  99         this.lineCostStorage = Array(itemsLength);
 100         this.prevNodes = Array(itemsLength).fill(null);
 101
 102
 103         for (var i=0; i<itemsLength; i++){
 104             this.lineCostStorage[i] = Array(itemsLength).fill(null);
 105         }
 106
 107         this.totalCostAuxStorage = Array(itemsLength).fill(null);
 108
 109         let a = Infinity;
 110         for(var k=itemsLength-2; this.lineCost(items, k+1,itemsLength-1, lineWidthFixed) < Infinity; k--){
 111
 112             let tmp = this.totalCostAux(items, k, lineWidthFixed);
 113
 114             if (a > tmp){
 115                 this.prevNodes[itemsLength-1] = k
 116                 a = tmp;
 117             }
 118
 119         }
 120         return a;
 121
 122     }
 123
 124     /**
 125      * check the total cost item[0..j].
 126      * @param items
 127      * @param i
 128      * @param lineWidth
 129      */
 130     totalCostAux(items : BoxesItem[], j : number, lineWidth: number): number{
 131
 132         if (this.totalCostAuxStorage[j] !== null){
 133             return this.totalCostAuxStorage[j];
 134         }
 135
 136         let rawLineCost = this.lineCost(items, 0, j, lineWidth);
 137         if (rawLineCost != Infinity){
 138             this.totalCostAuxStorage[j] = rawLineCost**3.0;
 139             return rawLineCost**3.0;
 140         }else{
 141             var returnCost = Infinity;
 142             for(var k=0; k<j; k++){
 143                 let tmp = this.totalCostAux(items, k, lineWidth) + this.lineCost(items, k+1,j, lineWidth)**3.0;
 144                 if (returnCost > tmp){
 145                     this.prevNodes[j] = k;
 146                     returnCost = tmp;
 147                 }
 148             }
 149             this.totalCostAuxStorage[j] = returnCost;
 150             return returnCost;
 151
 152         }
 153
 154
 155
 156     }
 157
 158
 159
 160     /**
 161      * check the line cost of a line containing items[i..j]
 162      * @param items items of box
 163      * @param i beginning (excluded)
 164      * @param j end of the line
 165      * @param lineWidth line width
 166      */
 167     lineCost(items : BoxesItem[], i : number, j : number, lineWidth: number) : number{
 168         if (this.lineCostStorage[i][j] !== null){
 169             console.log("AA")
 170             return this.lineCostStorage[i][j];
 171         }
 172
 173         if (!this.isBreakPoint(items[j])){
 174             this.lineCostStorage[i][j] = Infinity;
 175             return Infinity;
 176         }else{
 177             var tmpItemWidth = 0;
 178             for (var k = i; k<j; k++){
 179                 tmpItemWidth += this.origWidth(items[k]);
 180             }
 181
 182             tmpItemWidth += this.newLineWidth(items[j]);
 183
 184             if (tmpItemWidth > lineWidth){
 185                 this.lineCostStorage[i][j] = Infinity;
 186                 return Infinity;
 187             }else{
 188                 let returnValue = (lineWidth - tmpItemWidth);
 189                 this.lineCostStorage[i][j] = returnValue;
 190                 return returnValue;
 191             }
 192         }
 193
 194     }
 195
 196 }