path: root/dw/textblock_linebreaking.cc

#include "textblock.hh"
#include "../lout/msg.h"
#include "../lout/misc.hh"

#include <stdio.h>
#include <math.h>

using namespace lout;

namespace dw {

int Textblock::BadnessAndPenalty::badnessInfinities ()
{
   switch (badnessState) {
   case TOO_LOOSE:
   case TOO_TIGHT:
      return 1;

   case BADNESS_VALUE:
      return 0;
   }

   // compiler happiness
   lout::misc::assertNotReached ();
   return 0;
}

int Textblock::BadnessAndPenalty::penaltyInfinities ()
{
   switch (penaltyState) {
   case FORCE_BREAK:
      return -1;

   case PROHIBIT_BREAK:
      return 1;

   case PENALTY_VALUE:
      return 0;
   }

   // compiler happiness
   lout::misc::assertNotReached ();
   return 0;
}

int Textblock::BadnessAndPenalty::badnessValue ()
{
   return badnessState == BADNESS_VALUE ? badness : 0;
}

int Textblock::BadnessAndPenalty::penaltyValue ()
{
   return penaltyState == PENALTY_VALUE ? penalty : 0;
}

void Textblock::BadnessAndPenalty::calcBadness (int totalWidth, int idealWidth,
                                                int totalStretchability,
                                                int totalShrinkability)
{
   this->totalWidth = totalWidth;
   this->idealWidth = idealWidth;
   this->totalStretchability = totalStretchability;
   this->totalShrinkability = totalShrinkability;

   if (totalWidth == idealWidth) {
      badnessState = BADNESS_VALUE;
      badness = 0;
   } else if (totalWidth < idealWidth) {
      if (totalStretchability == 0)
         badnessState = TOO_LOOSE;
      else {
         int ratio = 100 * (idealWidth - totalWidth) / totalStretchability;
         if (ratio > 1024)
            badnessState = TOO_LOOSE;
         else {
            badnessState = BADNESS_VALUE;
            badness = ratio * ratio * ratio;
         }
      }
   } else { // if (word->totalWidth > availWidth)
      if (totalShrinkability == 0)
         badnessState = TOO_TIGHT;
      else {
         // Important: ratio is positive here.
         int ratio = 100 * (totalWidth - idealWidth) / totalShrinkability;
         if (ratio >= 100)
            badnessState = TOO_TIGHT;
         else {
            badnessState = BADNESS_VALUE;
            badness = ratio * ratio * ratio;
         }
      }
   }
}

void Textblock::BadnessAndPenalty::setPenalty (int penalty)
{
   this->penalty = penalty;
   penaltyState = PENALTY_VALUE;
}

void Textblock::BadnessAndPenalty::setPenaltyProhibitBreak ()
{
   penaltyState = PROHIBIT_BREAK;
}

void Textblock::BadnessAndPenalty::setPenaltyForceBreak ()
{
   penaltyState = FORCE_BREAK;
}

bool Textblock::BadnessAndPenalty::lineTooTight ()
{
   return badnessState == TOO_TIGHT;
}

bool Textblock::BadnessAndPenalty::lineMustBeBroken ()
{
   return penaltyState == FORCE_BREAK;
}

bool Textblock::BadnessAndPenalty::lineCanBeBroken ()
{
   return penaltyState != PROHIBIT_BREAK;
}

int Textblock::BadnessAndPenalty::compareTo (BadnessAndPenalty *other)
{
   int thisNumInfinities = badnessInfinities () + penaltyInfinities ();
   int otherNumInfinities =
      other->badnessInfinities () + other->penaltyInfinities ();
   int thisValue = badnessValue () + penaltyValue ();
   int otherValue = other->badnessValue () + other->penaltyValue ();

   if (thisNumInfinities == otherNumInfinities)
      return thisValue - otherValue;
   else
      return thisNumInfinities - otherNumInfinities;
}

void Textblock::BadnessAndPenalty::print ()
{
   switch (badnessState) {
   case TOO_LOOSE:
      PRINTF ("loose");
      break;

   case TOO_TIGHT:
      PRINTF ("tight");
      break;

   case BADNESS_VALUE:
      PRINTF ("%d", badness);
      break;
   }

   PRINTF (" [%d + %d - %d vs. %d] + ", totalWidth, totalStretchability,
           totalShrinkability, idealWidth);

   switch (penaltyState) {
   case FORCE_BREAK:
      PRINTF ("-inf");
      break;

   case PROHIBIT_BREAK:
      PRINTF ("inf");
      break;

   case PENALTY_VALUE:
      PRINTF ("%d", penalty);
      break;
   }
}

/*
 * ...
 *
 * diff ...
 */
void Textblock::justifyLine (Line *line, int diff)
{
   /* To avoid rounding errors, the calculation is based on accumulated
    * values. */

   if (diff > 0) {
      int stretchabilitySum = 0;
      for (int i = line->firstWord; i < line->lastWord; i++)
         stretchabilitySum += words->getRef(i)->stretchability;

      if (stretchabilitySum > 0) {
         int stretchabilityCum = 0;
         int spaceDiffCum = 0;
         for (int i = line->firstWord; i < line->lastWord; i++) {
            Word *word = words->getRef (i);
            stretchabilityCum += word->stretchability;
            int spaceDiff =
               stretchabilityCum * diff / stretchabilitySum - spaceDiffCum;
            spaceDiffCum += spaceDiff;

            PRINTF ("         %d (of %d): diff = %d\n", i, words->size (),
                    spaceDiff);

            word->effSpace = word->origSpace + spaceDiff;
         }
      }
   } else if (diff < 0) {
      int shrinkabilitySum = 0;
      for (int i = line->firstWord; i < line->lastWord; i++)
         shrinkabilitySum += words->getRef(i)->shrinkability;

      if (shrinkabilitySum > 0) {
         int shrinkabilityCum = 0;
         int spaceDiffCum = 0;
         for (int i = line->firstWord; i < line->lastWord; i++) {
            Word *word = words->getRef (i);
            shrinkabilityCum += word->shrinkability;
            int spaceDiff =
               shrinkabilityCum * diff / shrinkabilitySum - spaceDiffCum;
            spaceDiffCum += spaceDiff;

            word->effSpace = word->origSpace + spaceDiff;
         }
      }
   }
}


Textblock::Line *Textblock::addLine (int firstWord, int lastWord,
                                     bool temporary)
{
   PRINTF ("[%p] ADD_LINE (%d, %d)\n", this, firstWord, lastWord);

   Word *lastWordOfLine = words->getRef(lastWord);
   // Word::totalWidth includes the hyphen (which is what we want here).
   int lineWidth = lastWordOfLine->totalWidth;
   int maxOfMinWidth, sumOfMaxWidth;
   accumulateWordExtremees (firstWord, lastWord, &maxOfMinWidth,
                            &sumOfMaxWidth);

   PRINTF ("   words[%d]->totalWidth = %d\n", lastWord,
           lastWordOfLine->totalWidth);

   lines->increase ();
   if(!temporary) {
      // If the last line was temporary, this will be temporary, too, even
      // if not requested.
      if (lines->size () == 1 || nonTemporaryLines == lines->size () -1)
         nonTemporaryLines = lines->size ();
   }

   PRINTF ("nonTemporaryLines = %d\n", nonTemporaryLines);

   int lineIndex = lines->size () - 1;
   Line *line = lines->getRef (lineIndex);

   line->firstWord = firstWord;
   line->lastWord = lastWord;
   line->boxAscent = line->contentAscent = 0;
   line->boxDescent = line->contentDescent = 0;
   line->marginDescent = 0;
   line->breakSpace = 0;
   line->leftOffset = 0;

   alignLine (line);
   for (int i = line->firstWord; i < line->lastWord; i++) {
      Word *word = words->getRef (i);
      lineWidth += (word->effSpace - word->origSpace);
   }
   

   if (lines->size () == 1) {
      line->top = 0;

      // TODO What to do with this one: lastLine->maxLineWidth = line1OffsetEff;
      line->maxLineWidth = lineWidth;
      line->maxParMin = maxOfMinWidth;
      line->parMax = line->maxParMax = sumOfMaxWidth;
   } else {
      Line *prevLine = lines->getRef (lines->size () - 2);

      line->top = prevLine->top + prevLine->boxAscent +
         prevLine->boxDescent + prevLine->breakSpace;

      line->maxLineWidth = misc::max (lineWidth, prevLine->maxLineWidth);
      line->maxParMin = misc::max (maxOfMinWidth, prevLine->maxParMin);

      Word *lastWordOfPrevLine = words->getRef (prevLine->lastWord);
      if (lastWordOfPrevLine->content.type == core::Content::BREAK)
         // This line starts a new paragraph.
         line->parMax = sumOfMaxWidth;
      else
         // This line continues the paragraph from prevLine.
         line->parMax = prevLine->parMax + sumOfMaxWidth;

      line->maxParMax = misc::max (line->parMax, prevLine->maxParMax);

   }
   
   for(int i = line->firstWord; i <= line->lastWord; i++)
      accumulateWordForLine (lineIndex, i);

   PRINTF ("   line[%d].top = %d\n", lines->size () - 1, line->top);
   PRINTF ("   line[%d].boxAscent = %d\n", lines->size () - 1, line->boxAscent);
   PRINTF ("   line[%d].boxDescent = %d\n",
           lines->size () - 1, line->boxDescent);
   PRINTF ("   line[%d].contentAscent = %d\n", lines->size () - 1,
           line->contentAscent);
   PRINTF ("   line[%d].contentDescent = %d\n",
           lines->size () - 1, line->contentDescent);

   mustQueueResize = true;

   return line;
}

void Textblock::accumulateWordExtremees (int firstWord, int lastWord,
                                         int *maxOfMinWidth, int *sumOfMaxWidth)
{
   *maxOfMinWidth = *sumOfMaxWidth = 0;

   for (int i = firstWord; i <= lastWord; i++) {
      Word *word = words->getRef (i);
      core::Extremes extremes;
      getWordExtremes (word, &extremes);

      *maxOfMinWidth = misc::min (*maxOfMinWidth, extremes.minWidth);
      *sumOfMaxWidth += (extremes.maxWidth + word->origSpace);
      // Regarding the sum: if this is the end of the paragraph, it
      // does not matter, since word->space is 0 in this case.
   }
}

/*
 * This method is called in two cases: (i) when a word is added
 * (ii) when a page has to be (partially) rewrapped. It does word wrap,
 * and adds new lines if necessary.
 */
void Textblock::wordWrap (int wordIndex, bool wrapAll)
{
   Word *word;
   //core::Extremes wordExtremes;

   if (!wrapAll)
      removeTemporaryLines ();

   initLine1Offset (wordIndex);

   word = words->getRef (wordIndex);
   word->effSpace = word->origSpace;

   accumulateWordData (wordIndex);

   bool newLine;
   do {
      bool tempNewLine = false;
      int firstIndex = lines->size() == 0 ?
         0 : lines->getRef(lines->size() - 1)->lastWord + 1;
      int searchUntil;

      if (wrapAll && wordIndex >= firstIndex && wordIndex == words->size() -1) {
         newLine = true;
         searchUntil = wordIndex;
         tempNewLine = true;
         PRINTF ("NEW LINE: last word\n");
      } else if (wordIndex >= firstIndex &&
          word->badnessAndPenalty.lineMustBeBroken ()) {
         newLine = true;
         searchUntil = wordIndex;
         PRINTF ("NEW LINE: forced break\n");
      } else if (wordIndex > firstIndex &&
                 word->badnessAndPenalty.lineTooTight () &&
                 words->getRef(wordIndex- 1)
                 ->badnessAndPenalty.lineCanBeBroken ()) {
         // TODO Comment the last condition (also below where the minimun is
         // searched for)
         newLine = true;
         searchUntil = wordIndex - 1;
         PRINTF ("NEW LINE: line too tight\n");
      } else
         newLine = false;

      if(newLine) {
         PRINTF ("   searching from %d to %d\n", firstIndex, searchUntil);
         
         accumulateWordData (wordIndex);

         int breakPos = -1;
         for (int i = firstIndex; i <= searchUntil; i++) {
            Word *w = words->getRef(i);

            if(word->content.type && core::Content::REAL_CONTENT) {
               PRINTF ("      %d (of %d): ", i, words->size ());

               switch(w->content.type) {
               case core::Content::TEXT:
                  PRINTF ("\"%s\"", w->content.text);
                  break;
               case core::Content::WIDGET:
                  PRINTF ("<widget: %p>\n", w->content.widget);
                  break;
               case core::Content::BREAK:
                  PRINTF ("<break>\n");
                  break;
               default:
                  PRINTF ("<?>\n");
                  break;                 
               }

               PRINTF (" [%d / %d + %d - %d] => ",
                       w->size.width, w->origSpace, w->stretchability,
                       w->shrinkability);
               w->badnessAndPenalty.print ();
               PRINTF ("\n");
            }
            

            // TODO: is this condition needed:
            // if(w->badnessAndPenalty.lineCanBeBroken ()) ?

            if (breakPos == -1 ||
                w->badnessAndPenalty.compareTo
                (&words->getRef(breakPos)->badnessAndPenalty) <= 0)
               // "<=" instead of "<" in the next lines tends to result in more
               // words per line -- theoretically. Practically, the case "=="
               // will never occur.
               breakPos = i;
         }

         if (wrapAll && searchUntil == words->size () - 1) {
            // Since no break and no space is added, the last word
            // will have a penalty of inf. Actually, it should be -inf,
            // since it is the last word. However, since more words may
            // follow, the penalty is not changesd, but here, the search
            // is corrected (maybe only temporary).
            Word *lastWord = words->getRef (searchUntil);
            BadnessAndPenalty correctedBap = lastWord->badnessAndPenalty;
            correctedBap.setPenaltyForceBreak ();
            if (correctedBap.compareTo
                (&words->getRef(breakPos)->badnessAndPenalty) <= 0)
               breakPos = searchUntil;
         }

         PRINTF ("   new line from %d to %d\n", firstIndex, breakPos);
         addLine (firstIndex, breakPos, tempNewLine);
         PRINTF ("   accumulating again from %d to %d\n",
                 breakPos + 1, wordIndex);

         for(int i = breakPos + 1; i <= wordIndex; i++)
            accumulateWordData (i);
      }
   } while (newLine);
}

void Textblock::accumulateWordForLine (int lineIndex, int wordIndex)
{
   Line *line = lines->getRef (lineIndex);
   Word *word = words->getRef (wordIndex);

   PRINTF ("      %d + %d / %d + %d\n", line->boxAscent, line->boxDescent,
           word->size.ascent, word->size.descent);

   line->boxAscent = misc::max (line->boxAscent, word->size.ascent);
   line->boxDescent = misc::max (line->boxDescent, word->size.descent);

   int len = word->style->font->ascent;
   if (word->style->valign == core::style::VALIGN_SUPER)
      len += len / 2;
   line->contentAscent = misc::max (line->contentAscent, len);
         
   len = word->style->font->descent;
   if (word->style->valign == core::style::VALIGN_SUB)
      len += word->style->font->ascent / 3;
   line->contentDescent = misc::max (line->contentDescent, len);

   if (word->content.type == core::Content::WIDGET) {
      int collapseMarginTop = 0;

      line->marginDescent =
         misc::max (line->marginDescent,
                    word->size.descent +
                    word->content.widget->getStyle()->margin.bottom);

      if (lines->size () == 1 &&
          word->content.widget->blockLevel () &&
          getStyle ()->borderWidth.top == 0 &&
          getStyle ()->padding.top == 0) {
         // collapse top margins of parent element and its first child
         // see: http://www.w3.org/TR/CSS21/box.html#collapsing-margins
         collapseMarginTop = getStyle ()->margin.top;
      }

      line->boxAscent =
            misc::max (line->boxAscent,
                       word->size.ascent,
                       word->size.ascent
                       + word->content.widget->getStyle()->margin.top
                       - collapseMarginTop);

      word->content.widget->parentRef = lineIndex;
   } else {
      line->marginDescent =
         misc::max (line->marginDescent, line->boxDescent);

      if (word->content.type == core::Content::BREAK)
         line->breakSpace =
            misc::max (word->content.breakSpace,
                       line->marginDescent - line->boxDescent,
                       line->breakSpace);
   }
}

void Textblock::accumulateWordData (int wordIndex)
{
   PRINTF ("[%p] ACCUMULATE_WORD_DATA: %d\n", this, wordIndex);

   Word *word = words->getRef (wordIndex);
   int availWidth = calcAvailWidth (); // todo: variable? parameter?

   if (wordIndex == 0 ||
       (lines->size () > 0 &&
        wordIndex == lines->getRef(lines->size () - 1)->lastWord + 1)) {
      // first word of the (not neccessarily yet existing) line
      word->totalWidth = word->size.width + word->hyphenWidth;
      word->totalStretchability = 0;
      word->totalShrinkability = 0;
   } else {
      Word *prevWord = words->getRef (wordIndex - 1);

      word->totalWidth = prevWord->totalWidth
         + prevWord->origSpace - prevWord->hyphenWidth
         + word->size.width + word->hyphenWidth;
      word->totalStretchability =
         prevWord->totalStretchability + prevWord->stretchability;
      word->totalShrinkability =
         prevWord->totalShrinkability + prevWord->shrinkability;
   }

   PRINTF("      line width: %d of %d\n", word->totalWidth, availWidth);
   PRINTF("      spaces: + %d - %d\n",
          word->totalStretchability, word->totalShrinkability);

   word->badnessAndPenalty.calcBadness (word->totalWidth, availWidth,
                                        word->totalStretchability,
                                        word->totalShrinkability);
}

int Textblock::calcAvailWidth ()
{
   int availWidth =
      this->availWidth - getStyle()->boxDiffWidth() - innerPadding;
   if (limitTextWidth &&
       layout->getUsesViewport () &&
       availWidth > layout->getWidthViewport () - 10)
      availWidth = layout->getWidthViewport () - 10;

   //PRINTF("[%p] CALC_AVAIL_WIDTH => %d - %d - %d = %d\n",
   //       this, this->availWidth, getStyle()->boxDiffWidth(), innerPadding,
   //       availWidth);

   return availWidth;
}

void Textblock::initLine1Offset (int wordIndex)
{
   Word *word = words->getRef (wordIndex);

   /* Test whether line1Offset can be used. */
   if (wordIndex == 0) {
      if (ignoreLine1OffsetSometimes &&
          line1Offset + word->size.width > availWidth) {
         line1OffsetEff = 0;
      } else {
         int indent = 0;

         if (word->content.type == core::Content::WIDGET &&
             word->content.widget->blockLevel() == true) {
            /* don't use text-indent when nesting blocks */
         } else {
            if (core::style::isPerLength(getStyle()->textIndent)) {
               indent = misc::roundInt(this->availWidth *
                        core::style::perLengthVal (getStyle()->textIndent));
            } else {
               indent = core::style::absLengthVal (getStyle()->textIndent);
            }
         }
         line1OffsetEff = line1Offset + indent;
      }
   }
}

/**
 * Align the line.
 *
 * \todo Use block's style instead once paragraphs become proper blocks.
 */
void Textblock::alignLine (Line *line)
{
   int availWidth = calcAvailWidth ();
   Word *firstWord = words->getRef (line->firstWord);
   Word *lastWord = words->getRef (line->lastWord);

   for (int i = line->firstWord; i < line->lastWord; i++)
      words->getRef(i)->origSpace = words->getRef(i)->effSpace;

   if (firstWord->content.type != core::Content::BREAK) {
      switch (firstWord->style->textAlign) {
      case core::style::TEXT_ALIGN_LEFT:
      case core::style::TEXT_ALIGN_STRING:   /* handled elsewhere (in the
                                              * future)? */
         line->leftOffset = 0;
         break;
      case core::style::TEXT_ALIGN_JUSTIFY:  /* see some lines above */
         line->leftOffset = 0;
         if(lastWord->content.type != core::Content::BREAK &&
            line->lastWord != words->size () - 1) {
            PRINTF ("      justifyLine => %d vs. %d\n",
                    lastWord->totalWidth, availWidth);
            justifyLine (line, availWidth - lastWord->totalWidth);
         }
         break;
      case core::style::TEXT_ALIGN_RIGHT:
         line->leftOffset = availWidth - lastWord->totalWidth;
         break;
      case core::style::TEXT_ALIGN_CENTER:
         line->leftOffset = (availWidth - lastWord->totalWidth) / 2;
         break;
      default:
         /* compiler happiness */
         line->leftOffset = 0;
      }

      /* For large lines (images etc), which do not fit into the viewport: */
      if (line->leftOffset < 0)
         line->leftOffset = 0;
   }
}

/**
 * Rewrap the page from the line from which this is necessary.
 * There are basically two times we'll want to do this:
 * either when the viewport is resized, or when the size changes on one
 * of the child widgets.
 */
void Textblock::rewrap ()
{
   PRINTF ("[%p] REWRAP: wrapRef = %d\n", this, wrapRef);

   if (wrapRef == -1)
      /* page does not have to be rewrapped */
      return;

   /* All lines up from wrapRef will be rebuild from the word list,
    * the line list up from this position is rebuild. */
   lines->setSize (wrapRef);
   nonTemporaryLines = misc::min (nonTemporaryLines, wrapRef);

   int firstWord;
   if (lines->size () > 0)
      firstWord = lines->getLastRef()->lastWord + 1;
   else
      firstWord = 0;

   for (int i = firstWord; i < words->size (); i++) {
      Word *word = words->getRef (i);
         
      if (word->content.type == core::Content::WIDGET)
         calcWidgetSize (word->content.widget, &word->size);
      
      wordWrap (i, false);
      
      if (word->content.type == core::Content::WIDGET) {
         word->content.widget->parentRef = lines->size () - 1;
      }
   }

   /* Next time, the page will not have to be rewrapped. */
   wrapRef = -1;
}

void Textblock::showMissingLines ()
{
   int firstWordToWrap = lines->size () > 0 ?
      lines->getRef(lines->size () - 1)->lastWord + 1 : 0;
   for (int i = firstWordToWrap; i < words->size (); i++)
      wordWrap (i, true);
}


void Textblock::removeTemporaryLines ()
{
   lines->setSize (nonTemporaryLines);
}

} // namespace dw