Fix build: Revert "Add hyphenation to line breaking"

This reverts commit daf6a6bdbf2ff1f66496d6200cb253e2f50759d5.

Change-Id: I3fed65046274d3aeb748f0730585ab89927f5741

5 files changed, 49 insertions, 407 deletions

diff --git a/include/minikin/Hyphenator.h b/include/minikin/Hyphenator.h
deleted file mode 100644
index 581c657..0000000
--- a/include/minikin/Hyphenator.h
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * Copyright (C) 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-/**
- * An implementation of Liang's hyphenation algorithm.
- */
-
-#include <memory>
-#include <unordered_map>
-
-#ifndef MINIKIN_HYPHENATOR_H
-#define MINIKIN_HYPHENATOR_H
-
-namespace android {
-
-class Trie {
-public:
-    std::vector<uint8_t> result;
-    std::unordered_map<uint16_t, Trie> succ;
-};
-
-class Hyphenator {
-public:
-    // Note: this will also require a locale, for proper case folding behavior
-    static Hyphenator* load(const uint16_t* patternData, size_t size);
-
-    // Compute the hyphenation of a word, storing the hyphenation in result vector. Each
-    // entry in the vector is a "hyphen edit" to be applied at the corresponding code unit
-    // offset in the word. Currently 0 means no hyphen and 1 means insert hyphen and break,
-    // but this will be expanded to other edits for nonstandard hyphenation.
-    // Example: word is "hyphen", result is [0 0 1 0 0 0], corresponding to "hy-phen".
-    void hyphenate(std::vector<uint8_t>* result, const uint16_t* word, size_t len);
-
-private:
-    void addPattern(const uint16_t* pattern, size_t size);
-
-    void hyphenateSoft(std::vector<uint8_t>* result, const uint16_t* word, size_t len);
-
-    // TODO: these should become parameters, as they might vary by locale, screen size, and
-    // possibly explicit user control.
-    static const int MIN_PREFIX = 2;
-    static const int MIN_SUFFIX = 3;
-
-    Trie root;
-};
-
-}  // namespace android
-
-#endif   // MINIKIN_HYPHENATOR_H
\ No newline at end of file
diff --git a/include/minikin/LineBreaker.h b/include/minikin/LineBreaker.h
index 92e72e2..29afba0 100644
--- a/include/minikin/LineBreaker.h
+++ b/include/minikin/LineBreaker.h
@@ -26,7 +26,6 @@
 #include "unicode/locid.h"
 #include <cmath>
 #include <vector>
-#include "minikin/Hyphenator.h"
 
 namespace android {
 
@@ -44,10 +43,6 @@ class LineWidths {
             mFirstWidthLineCount = firstWidthLineCount;
             mRestWidth = restWidth;
         }
-        bool isConstant() const {
-            // technically mFirstWidthLineCount == 0 would count too, but doesn't actually happen
-            return mRestWidth == mFirstWidth;
-        }
         float getLineWidth(int line) const {
             return (line < mFirstWidthLineCount) ? mFirstWidth : mRestWidth;
         }
@@ -82,8 +77,6 @@ class TabStops {
 
 class LineBreaker {
     public:
-        const static int kTab_Shift = 29;  // keep synchronized with TAB_MASK in StaticLayout.java
-
         ~LineBreaker() {
             utext_close(&mUText);
             delete mBreakIterator;
@@ -95,8 +88,13 @@ class LineBreaker {
         // locale has actually changed.
         // That logic could be here but it's better for performance that it's upstream because of
         // the cost of constructing and comparing the ICU Locale object.
-        // Note: caller is responsible for managing lifetime of hyphenator
-        void setLocale(const icu::Locale& locale, Hyphenator* hyphenator);
+        void setLocale(const icu::Locale& locale) {
+            delete mBreakIterator;
+            UErrorCode status = U_ZERO_ERROR;
+            mBreakIterator = icu::BreakIterator::createLineInstance(locale, status);
+            // TODO: check status
+            // TODO: load hyphenator from locale
+        }
 
         void resize(size_t size) {
             mTextBuf.resize(size);
@@ -132,8 +130,8 @@ class LineBreaker {
         // Minikin to do the shaping of the strings. The main thing that would need to be changed
         // is having some kind of callback (or virtual class, or maybe even template), which could
         // easily be instantiated with Minikin's Layout. Future work for when needed.
-        float addStyleRun(MinikinPaint* paint, const FontCollection* typeface, FontStyle style,
-                size_t start, size_t end, bool isRtl);
+        float addStyleRun(const MinikinPaint* paint, const FontCollection* typeface,
+                FontStyle style, size_t start, size_t end, bool isRtl);
 
         void addReplacement(size_t start, size_t end, float width);
 
@@ -147,7 +145,7 @@ class LineBreaker {
             return mWidths.data();
         }
 
-        const int* getFlags() const {
+        const uint8_t* getFlags() const {
             return mFlags.data();
         }
 
@@ -168,40 +166,23 @@ class LineBreaker {
             ParaWidth postBreak;
             float penalty;  // penalty of this break (for example, hyphen penalty)
             float score;  // best score found for this break
-            size_t lineNumber;  // only updated for non-constant line widths
-            uint8_t hyphenEdit;
         };
 
         float currentLineWidth() const;
 
-        // compute shrink/stretch penalty for line
-        float computeScore(float delta, bool atEnd);
-
-        void addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak, float penalty,
-                uint8_t hyph);
+        void addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak, float penalty);
 
         void addCandidate(Candidate cand);
 
-        // push an actual break to the output. Takes care of setting flags for tab
-        void pushBreak(int offset, float width, uint8_t hyph);
-
         void computeBreaksGreedy();
 
-        void computeBreaksOptimal();
-
-        // special case when LineWidth is constant (layout is rectangle)
-        void computeBreaksOptimalRect();
-
-        void finishBreaksOptimal();
+        void computeBreaksOpt();
 
         icu::BreakIterator* mBreakIterator = nullptr;
         UText mUText = UTEXT_INITIALIZER;
         std::vector<uint16_t>mTextBuf;
         std::vector<float>mCharWidths;
 
-        Hyphenator* mHyphenator;
-        std::vector<uint8_t> mHyphBuf;
-
         // layout parameters
         BreakStrategy mStrategy = kBreakStrategy_Greedy;
         LineWidths mLineWidths;
@@ -210,7 +191,7 @@ class LineBreaker {
         // result of line breaking
         std::vector<int> mBreaks;
         std::vector<float> mWidths;
-        std::vector<int> mFlags;
+        std::vector<uint8_t> mFlags;
 
         ParaWidth mWidth = 0;
         std::vector<Candidate> mCandidates;
diff --git a/libs/minikin/Android.mk b/libs/minikin/Android.mk
index 34b535c..5406824 100644
--- a/libs/minikin/Android.mk
+++ b/libs/minikin/Android.mk
@@ -22,7 +22,6 @@ LOCAL_SRC_FILES := \
     FontCollection.cpp \
     FontFamily.cpp \
     GraphemeBreak.cpp \
-    Hyphenator.cpp \
     Layout.cpp \
     LineBreaker.cpp \
     MinikinInternal.cpp \
diff --git a/libs/minikin/Hyphenator.cpp b/libs/minikin/Hyphenator.cpp
deleted file mode 100644
index c50b386..0000000
--- a/libs/minikin/Hyphenator.cpp
+++ /dev/null
@@ -1,152 +0,0 @@
-/*
- * Copyright (C) 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <vector>
-#include <memory>
-#include <cctype>
-#include <algorithm>
-#include <string>
-
-// HACK: for reading pattern file
-#include <fcntl.h>
-
-#define LOG_TAG "Minikin"
-#include "utils/Log.h"
-
-#include "minikin/Hyphenator.h"
-
-using std::vector;
-
-namespace android {
-
-static const uint16_t CHAR_SOFT_HYPHEN = 0x00AD;
-
-void Hyphenator::addPattern(const uint16_t* pattern, size_t size) {
-    vector<uint16_t> word;
-    vector<uint8_t> result;
-
-    // start by parsing the Liang-format pattern into a word and a result vector, the
-    // vector right-aligned but without leading zeros. Examples:
-    // a1bc2d -> abcd [1, 0, 2, 0]
-    // abc1 -> abc [1]
-    // 1a2b3c4d5 -> abcd [1, 2, 3, 4, 5]
-    bool lastWasLetter = false;
-    bool haveSeenNumber = false;
-    for (size_t i = 0; i < size; i++) {
-        uint16_t c = pattern[i];
-        if (isdigit(c)) {
-            result.push_back(c - '0');
-            lastWasLetter = false;
-            haveSeenNumber = true;
-        } else {
-            word.push_back(c);
-            if (lastWasLetter && haveSeenNumber) {
-                result.push_back(0);
-            }
-            lastWasLetter = true;
-        }
-    }
-    if (lastWasLetter) {
-        result.push_back(0);
-    }
-    Trie* t = &root;
-    for (size_t i = 0; i < word.size(); i++) {
-        t = &t->succ[word[i]];
-    }
-    t->result = result;
-}
-
-// If any soft hyphen is present in the word, use soft hyphens to decide hyphenation,
-// as recommended in UAX #14 (Use of Soft Hyphen)
-void Hyphenator::hyphenateSoft(vector<uint8_t>* result, const uint16_t* word, size_t len) {
-    (*result)[0] = 0;
-    for (size_t i = 1; i < len; i++) {
-        (*result)[i] = word[i - 1] == CHAR_SOFT_HYPHEN;
-    }
-}
-
-void Hyphenator::hyphenate(vector<uint8_t>* result, const uint16_t* word, size_t len) {
-    result->clear();
-    result->resize(len);
-    if (len < MIN_PREFIX + MIN_SUFFIX) return;
-    size_t maxOffset = len - MIN_SUFFIX + 1;
-    for (size_t i = 0; i < len + 1; i++) {
-        const Trie* node = &root;
-        for (size_t j = i; j < len + 2; j++) {
-            uint16_t c;
-            if (j == 0 || j == len + 1) {
-                c = '.';  // word boundary character in pattern data files
-            } else {
-                c = word[j - 1];
-                if (c == CHAR_SOFT_HYPHEN) {
-                    hyphenateSoft(result, word, len);
-                    return;
-                }
-                // TODO: use locale-sensitive case folding from ICU.
-                c = tolower(c);
-            }
-            auto search = node->succ.find(c);
-            if (search != node->succ.end()) {
-                node = &search->second;
-            } else {
-                break;
-            }
-            if (!node->result.empty()) {
-                int resultLen = node->result.size();
-                int offset = j + 1 - resultLen;
-                int start = std::max(MIN_PREFIX - offset, 0);
-                int end = std::min(resultLen, (int)maxOffset - offset);
-                // TODO performance: this inner loop can profitably be optimized
-                for (int k = start; k < end; k++) {
-                    (*result)[offset + k] = std::max((*result)[offset + k], node->result[k]);
-                }
-#if 0
-                // debug printing of matched patterns
-                std::string dbg;
-                for (size_t k = i; k <= j + 1; k++) {
-                    int off = k - j - 2 + resultLen;
-                    if (off >= 0 && node->result[off] != 0) {
-                        dbg.push_back((char)('0' + node->result[off]));
-                    }
-                    if (k < j + 1) {
-                        uint16_t c = (k == 0 || k == len + 1) ? '.' : word[k - 1];
-                        dbg.push_back((char)c);
-                    }
-                }
-                ALOGD("%d:%d %s", i, j, dbg.c_str());
-#endif
-            }
-        }
-    }
-    // Since the above calculation does not modify values outside
-    // [MIN_PREFIX, len - MIN_SUFFIX], they are left as 0.
-    for (size_t i = MIN_PREFIX; i < maxOffset; i++) {
-        (*result)[i] &= 1;
-    }
-}
-
-Hyphenator* Hyphenator::load(const uint16_t *patternData, size_t size) {
-    Hyphenator* result = new Hyphenator;
-    for (size_t i = 0; i < size; i++) {
-        size_t end = i;
-        while (patternData[end] != '\n') end++;
-        result->addPattern(patternData + i, end - i);
-        i = end;
-    }
-    return result;
-}
-
-}  // namespace android
diff --git a/libs/minikin/LineBreaker.cpp b/libs/minikin/LineBreaker.cpp
index f7f3fb3..99d7f69 100644
--- a/libs/minikin/LineBreaker.cpp
+++ b/libs/minikin/LineBreaker.cpp
@@ -29,7 +29,6 @@ using std::vector;
 namespace android {
 
 const int CHAR_TAB = 0x0009;
-const uint16_t CHAR_SOFT_HYPHEN = 0x00AD;
 
 // Large scores in a hierarchy; we prefer desperate breaks to an overfull line. All these
 // constants are larger than any reasonable actual width score.
@@ -41,16 +40,6 @@ const float SCORE_DESPERATE = 1e10f;
 // to avoid allocation.
 const size_t MAX_TEXT_BUF_RETAIN = 32678;
 
-void LineBreaker::setLocale(const icu::Locale& locale, Hyphenator* hyphenator) {
-    delete mBreakIterator;
-    UErrorCode status = U_ZERO_ERROR;
-    mBreakIterator = icu::BreakIterator::createLineInstance(locale, status);
-    // TODO: check status
-
-    // TODO: load actual resource dependent on locale; letting Minikin do it is a hack
-    mHyphenator = hyphenator;
-}
-
 void LineBreaker::setText() {
     UErrorCode status = U_ZERO_ERROR;
     utext_openUChars(&mUText, mTextBuf.data(), mTextBuf.size(), &status);
@@ -60,7 +49,7 @@ void LineBreaker::setText() {
     // handle initial break here because addStyleRun may never be called
     mBreakIterator->next();
     mCandidates.clear();
-    Candidate cand = {0, 0, 0.0, 0.0, 0.0, 0.0, 0, 0};
+    Candidate cand = {0, 0, 0.0, 0.0, 0.0, 0.0};
     mCandidates.push_back(cand);
 
     // reset greedy breaker state
@@ -75,6 +64,7 @@ void LineBreaker::setText() {
 }
 
 void LineBreaker::setLineWidths(float firstWidth, int firstWidthLineCount, float restWidth) {
+    ALOGD("width %f", firstWidth);
     mLineWidths.setWidths(firstWidth, firstWidthLineCount, restWidth);
 }
 
@@ -91,29 +81,22 @@ static bool isLineEndSpace(uint16_t c) {
 // width buffer.
 // This method finds the candidate word breaks (using the ICU break iterator) and sends them
 // to addCandidate.
-float LineBreaker::addStyleRun(MinikinPaint* paint, const FontCollection* typeface,
+float LineBreaker::addStyleRun(const MinikinPaint* paint, const FontCollection* typeface,
         FontStyle style, size_t start, size_t end, bool isRtl) {
     Layout layout;  // performance TODO: move layout to self object to reduce allocation cost?
     float width = 0.0f;
     int bidiFlags = isRtl ? kBidi_Force_RTL : kBidi_Force_LTR;
 
-    float hyphenPenalty = 0.0;
     if (paint != nullptr) {
         layout.setFontCollection(typeface);
         layout.doLayout(mTextBuf.data(), start, end - start, mTextBuf.size(), bidiFlags, style,
                 *paint);
         layout.getAdvances(mCharWidths.data() + start);
         width = layout.getAdvance();
-
-        // a heuristic that seems to perform well
-        hyphenPenalty = 0.5 * paint->size * paint->scaleX * mLineWidths.getLineWidth(0);
     }
 
-    size_t current = (size_t)mBreakIterator->current();
-    size_t wordEnd = start;
-    size_t lastBreak = start;
-    ParaWidth lastBreakWidth = mWidth;
     ParaWidth postBreak = mWidth;
+    size_t current = (size_t)mBreakIterator->current();
     for (size_t i = start; i < end; i++) {
         uint16_t c = mTextBuf[i];
         if (c == CHAR_TAB) {
@@ -127,48 +110,14 @@ float LineBreaker::addStyleRun(MinikinPaint* paint, const FontCollection* typefa
             mWidth += mCharWidths[i];
             if (!isLineEndSpace(c)) {
                 postBreak = mWidth;
-                wordEnd = i + 1;
             }
         }
         if (i + 1 == current) {
-            // Override ICU's treatment of soft hyphen as a break opportunity, because we want it
-            // to be a hyphen break, with penalty and drawing behavior.
-            if (c != CHAR_SOFT_HYPHEN) {
-                if (paint != nullptr && mHyphenator != nullptr && wordEnd > lastBreak) {
-                    mHyphenator->hyphenate(&mHyphBuf, &mTextBuf[lastBreak], wordEnd - lastBreak);
-    #if VERBOSE_DEBUG
-                    std::string hyphenatedString;
-                    for (size_t j = lastBreak; j < wordEnd; j++) {
-                        if (mHyphBuf[j - lastBreak]) hyphenatedString.push_back('-');
-                        // Note: only works with ASCII, should do UTF-8 conversion here
-                        hyphenatedString.push_back(buffer()[j]);
-                    }
-                    ALOGD("hyphenated string: %s", hyphenatedString.c_str());
-    #endif
-
-                    // measure hyphenated substrings
-                    for (size_t j = lastBreak; j < wordEnd; j++) {
-                        uint8_t hyph = mHyphBuf[j - lastBreak];
-                        if (hyph) {
-                            paint->hyphenEdit = hyph;
-                            layout.doLayout(mTextBuf.data(), lastBreak, j - lastBreak,
-                                    mTextBuf.size(), bidiFlags, style, *paint);
-                            ParaWidth hyphPostBreak = lastBreakWidth + layout.getAdvance();
-                            paint->hyphenEdit = 0;
-                            layout.doLayout(mTextBuf.data(), j, wordEnd - j,
-                                    mTextBuf.size(), bidiFlags, style, *paint);
-                            ParaWidth hyphPreBreak = postBreak - layout.getAdvance();
-                            addWordBreak(j, hyphPreBreak, hyphPostBreak, hyphenPenalty, hyph);
-                        }
-                    }
-                }
-
-                // Skip break for zero-width characters.
-                if (current == mTextBuf.size() || mCharWidths[current] > 0) {
-                    addWordBreak(current, mWidth, postBreak, 0.0, 0);
-                }
-                lastBreak = current;
-                lastBreakWidth = mWidth;
+            // TODO: hyphenation goes here
+
+            // Skip break for zero-width characters.
+            if (current == mTextBuf.size() || mCharWidths[current] > 0) {
+                addWordBreak(current, mWidth, postBreak, 0);
             }
             current = (size_t)mBreakIterator->next();
         }
@@ -180,7 +129,7 @@ float LineBreaker::addStyleRun(MinikinPaint* paint, const FontCollection* typefa
 // add a word break (possibly for a hyphenated fragment), and add desperate breaks if
 // needed (ie when word exceeds current line width)
 void LineBreaker::addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak,
-        float penalty, uint8_t hyph) {
+        float penalty) {
     Candidate cand;
     ParaWidth width = mCandidates.back().preBreak;
     if (postBreak - width > currentLineWidth()) {
@@ -196,7 +145,6 @@ void LineBreaker::addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth post
                 cand.preBreak = width;
                 cand.postBreak = width;
                 cand.penalty = SCORE_DESPERATE;
-                cand.hyphenEdit = 0;
 #if VERBOSE_DEBUG
                 ALOGD("desperate cand: %d %g:%g",
                         mCandidates.size(), cand.postBreak, cand.preBreak);
@@ -211,24 +159,12 @@ void LineBreaker::addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth post
     cand.preBreak = preBreak;
     cand.postBreak = postBreak;
     cand.penalty = penalty;
-    cand.hyphenEdit = hyph;
 #if VERBOSE_DEBUG
     ALOGD("cand: %d %g:%g", mCandidates.size(), cand.postBreak, cand.preBreak);
 #endif
     addCandidate(cand);
 }
 
-// TODO: for justified text, refine with shrink/stretch
-float LineBreaker::computeScore(float delta, bool atEnd) {
-    if (delta < 0) {
-        return SCORE_OVERFULL;
-    } else if (atEnd && mStrategy != kBreakStrategy_Balanced) {
-        return 0.0;
-    } else {
-        return delta * delta;
-    }
-}
-
 // TODO performance: could avoid populating mCandidates if greedy only
 void LineBreaker::addCandidate(Candidate cand) {
     size_t candIndex = mCandidates.size();
@@ -238,8 +174,10 @@ void LineBreaker::addCandidate(Candidate cand) {
         if (mBestBreak == mLastBreak) {
             mBestBreak = candIndex;
         }
-        pushBreak(mCandidates[mBestBreak].offset, mCandidates[mBestBreak].postBreak - mPreBreak,
-                mCandidates[mBestBreak].hyphenEdit);
+        mBreaks.push_back(mCandidates[mBestBreak].offset);
+        mWidths.push_back(mCandidates[mBestBreak].postBreak - mPreBreak);
+        mFlags.push_back(mFirstTabIndex < mBreaks.back());
+        mFirstTabIndex = INT_MAX;
         mBestScore = SCORE_INFTY;
 #if VERBOSE_DEBUG
         ALOGD("break: %d %g", mBreaks.back(), mWidths.back());
@@ -253,15 +191,6 @@ void LineBreaker::addCandidate(Candidate cand) {
     }
 }
 
-void LineBreaker::pushBreak(int offset, float width, uint8_t hyph) {
-    mBreaks.push_back(offset);
-    mWidths.push_back(width);
-    int flags = (mFirstTabIndex < mBreaks.back()) << kTab_Shift;
-    flags |= hyph;
-    mFlags.push_back(flags);
-    mFirstTabIndex = INT_MAX;
-}
-
 void LineBreaker::addReplacement(size_t start, size_t end, float width) {
     mCharWidths[start] = width;
     std::fill(&mCharWidths[start + 1], &mCharWidths[end], 0.0f);
@@ -276,87 +205,27 @@ void LineBreaker::computeBreaksGreedy() {
     // All breaks but the last have been added in addCandidate already.
     size_t nCand = mCandidates.size();
     if (nCand == 1 || mLastBreak != nCand - 1) {
-        pushBreak(mCandidates[nCand - 1].offset, mCandidates[nCand - 1].postBreak - mPreBreak, 0);
-        // don't need to update mBestScore, because we're done
+        mBreaks.push_back(mCandidates[nCand - 1].offset);
+        mWidths.push_back(mCandidates[nCand - 1].postBreak - mPreBreak);
+        mFlags.push_back(mFirstTabIndex < mBreaks.back());
+        // don't need to update mFirstTabIndex or mBestScore, because we're done
 #if VERBOSE_DEBUG
         ALOGD("final break: %d %g", mBreaks.back(), mWidths.back());
 #endif
     }
 }
 
-// Follow "prev" links in mCandidates array, and copy to result arrays.
-void LineBreaker::finishBreaksOptimal() {
+void LineBreaker::computeBreaksOpt() {
     // clear existing greedy break result
     mBreaks.clear();
     mWidths.clear();
     mFlags.clear();
-    size_t nCand = mCandidates.size();
-    size_t prev;
-    for (size_t i = nCand - 1; i > 0; i = prev) {
-        prev = mCandidates[i].prev;
-        mBreaks.push_back(mCandidates[i].offset);
-        mWidths.push_back(mCandidates[i].postBreak - mCandidates[prev].preBreak);
-        mFlags.push_back(mCandidates[i].hyphenEdit);
-    }
-    std::reverse(mBreaks.begin(), mBreaks.end());
-    std::reverse(mWidths.begin(), mWidths.end());
-    std::reverse(mFlags.begin(), mFlags.end());
-}
-
-void LineBreaker::computeBreaksOptimal() {
-    size_t active = 0;
-    size_t nCand = mCandidates.size();
-    for (size_t i = 1; i < nCand; i++) {
-        bool atEnd = i == nCand - 1;
-        float best = SCORE_INFTY;
-        size_t bestPrev = 0;
-
-        size_t lineNumberLast = mCandidates[active].lineNumber;
-        float width = mLineWidths.getLineWidth(lineNumberLast);
-        ParaWidth leftEdge = mCandidates[i].postBreak - width;
-        float bestHope = 0;
-
-        for (size_t j = active; j < i; j++) {
-            size_t lineNumber = mCandidates[j].lineNumber;
-            if (lineNumber != lineNumberLast) {
-                float widthNew = mLineWidths.getLineWidth(lineNumber);
-                if (widthNew != width) {
-                    leftEdge = mCandidates[i].postBreak - width;
-                    bestHope = 0;
-                    width = widthNew;
-                }
-                lineNumberLast = lineNumber;
-            }
-            float jScore = mCandidates[j].score;
-            if (jScore + bestHope >= best) continue;
-            float delta = mCandidates[j].preBreak - leftEdge;
-
-            float widthScore = computeScore(delta, atEnd);
-            if (delta < 0) {
-                active = j + 1;
-            } else {
-                bestHope = widthScore;
-            }
-
-            float score = jScore + widthScore;
-            if (score <= best) {
-                best = score;
-                bestPrev = j;
-            }
-        }
-        mCandidates[i].score = best + mCandidates[i].penalty;
-        mCandidates[i].prev = bestPrev;
-        mCandidates[i].lineNumber = mCandidates[bestPrev].lineNumber + 1;
-    }
-    finishBreaksOptimal();
-}
-
-void LineBreaker::computeBreaksOptimalRect() {
     size_t active = 0;
     size_t nCand = mCandidates.size();
     float width = mLineWidths.getLineWidth(0);
+    // TODO: actually support non-constant width
     for (size_t i = 1; i < nCand; i++) {
-        bool atEnd = i == nCand - 1;
+        bool stretchIsFree = mStrategy != kBreakStrategy_Balanced && i == nCand - 1;
         float best = SCORE_INFTY;
         size_t bestPrev = 0;
 
@@ -366,15 +235,17 @@ void LineBreaker::computeBreaksOptimalRect() {
 
         ParaWidth leftEdge = mCandidates[i].postBreak - width;
         for (size_t j = active; j < i; j++) {
-            // TODO performance: can break if bestHope >= best; worth it?
             float jScore = mCandidates[j].score;
             if (jScore + bestHope >= best) continue;
             float delta = mCandidates[j].preBreak - leftEdge;
 
-            float widthScore = computeScore(delta, atEnd);
+            // TODO: for justified text, refine with shrink/stretch
+            float widthScore;
             if (delta < 0) {
+                widthScore = SCORE_OVERFULL;
                 active = j + 1;
             } else {
+                widthScore = stretchIsFree ? 0 : delta * delta;
                 bestHope = widthScore;
             }
 
@@ -387,16 +258,23 @@ void LineBreaker::computeBreaksOptimalRect() {
         mCandidates[i].score = best + mCandidates[i].penalty;
         mCandidates[i].prev = bestPrev;
     }
-    finishBreaksOptimal();
+    size_t prev;
+    for (size_t i = nCand - 1; i > 0; i = prev) {
+        prev = mCandidates[i].prev;
+        mBreaks.push_back(mCandidates[i].offset);
+        mWidths.push_back(mCandidates[i].postBreak - mCandidates[prev].preBreak);
+        mFlags.push_back(0);
+    }
+    std::reverse(mBreaks.begin(), mBreaks.end());
+    std::reverse(mWidths.begin(), mWidths.end());
+    std::reverse(mFlags.begin(), mFlags.end());
 }
 
 size_t LineBreaker::computeBreaks() {
     if (mStrategy == kBreakStrategy_Greedy) {
         computeBreaksGreedy();
-    } else if (mLineWidths.isConstant()) {
-        computeBreaksOptimalRect();
     } else {
-        computeBreaksOptimal();
+        computeBreaksOpt();
     }
     return mBreaks.size();
 }
@@ -412,8 +290,6 @@ void LineBreaker::finish() {
         mTextBuf.shrink_to_fit();
         mCharWidths.clear();
         mCharWidths.shrink_to_fit();
-        mHyphBuf.clear();
-        mHyphBuf.shrink_to_fit();
         mCandidates.shrink_to_fit();
         mBreaks.shrink_to_fit();
         mWidths.shrink_to_fit();