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