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} 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         this.totalCost(items ,lineWidth);
  55         let nodeList = this.generateBreakLineNodeList();
  56         console.log("~~~", nodeList);
  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
  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(undefined);
 102         }
 103
 104         this.totalCostAuxStorage = Array(itemsLength).fill(undefined);
 105         console.log("===", itemsLength);
 106         let a = this.totalCostAux(items, itemsLength-1, lineWidth);
 107         console.log(this.lineCostStorage);
 108         return a;
 109
 110     }
 111
 112     /**
 113      * check the total cost item[0..j].
 114      * @param items
 115      * @param i
 116      * @param lineWidth
 117      */
 118     totalCostAux(items : BoxesItem[], j : number, lineWidth: number): number{
 119
 120         if (this.totalCostAuxStorage[j] !== undefined){
 121             return this.totalCostAuxStorage[j];
 122         }
 123
 124         let rawLineCost = this.lineCost(items, 0, j, lineWidth);
 125         if (rawLineCost != Infinity){
 126             this.totalCostAuxStorage[j] = rawLineCost;
 127             return rawLineCost;
 128         }else{
 129             var returnCost = Infinity;
 130             for(var k=0; k<j; k++){
 131                 let tmp = this.totalCostAux(items, k, lineWidth) + this.lineCost(items, k+1,j, lineWidth);
 132                 if (returnCost > tmp){
 133                     this.prevNodes[j] = k;
 134                     returnCost = tmp;
 135                 }
 136             }
 137             this.totalCostAuxStorage[j] = returnCost;
 138             return returnCost;
 139
 140         }
 141
 142
 143         return returnCost;
 144
 145     }
 146
 147
 148
 149     /**
 150      * check the line cost of a line containing items[i..j]
 151      * @param items items of box
 152      * @param i beginning (excluded)
 153      * @param j end of the line
 154      * @param lineWidth line width
 155      */
 156     lineCost(items : BoxesItem[], i : number, j : number, lineWidth: number) : number{
 157         if (this.lineCostStorage[i] !== undefined && this.lineCostStorage[i][j] !== undefined){
 158             return this.lineCostStorage[i][j];
 159         }
 160
 161         if (!this.isBreakPoint(items[j])){
 162             this.lineCostStorage[i][j] = Infinity;
 163             return Infinity;
 164         }else{
 165             var tmpItemWidth = 0;
 166             for (var k = i; k<j; k++){
 167                 tmpItemWidth += this.origWidth(items[k]);
 168             }
 169
 170             tmpItemWidth += this.newLineWidth(items[j]);
 171
 172             if (tmpItemWidth > lineWidth){
 173                 this.lineCostStorage[i][j] = Infinity;
 174                 return Infinity;
 175             }else{
 176                 let returnValue = (lineWidth - tmpItemWidth)**3.0;
 177                 this.lineCostStorage[i][j] = returnValue;
 178                 return returnValue;
 179             }
 180         }
 181
 182     }
 183
 184 }