Revert "Fix build: Revert "Add hyphenation to line breaking""

This reverts commit 0b25d5ac85533f64764a0d53d5e5d33b46b715fa.

2 files changed, 94 insertions, 13 deletions

diff --git a/include/minikin/Hyphenator.h b/include/minikin/Hyphenator.h
new file mode 100644
index 0000000..581c657
--- /dev/null
+++ b/include/minikin/Hyphenator.h
@@ -0,0 +1,62 @@
+/*
+ * 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 29afba0..92e72e2 100644
--- a/include/minikin/LineBreaker.h
+++ b/include/minikin/LineBreaker.h
@@ -26,6 +26,7 @@
 #include "unicode/locid.h"
 #include <cmath>
 #include <vector>
+#include "minikin/Hyphenator.h"
 
 namespace android {
 
@@ -43,6 +44,10 @@ 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;
         }
@@ -77,6 +82,8 @@ 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;
@@ -88,13 +95,8 @@ 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.
-        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
-        }
+        // Note: caller is responsible for managing lifetime of hyphenator
+        void setLocale(const icu::Locale& locale, Hyphenator* hyphenator);
 
         void resize(size_t size) {
             mTextBuf.resize(size);
@@ -130,8 +132,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(const MinikinPaint* paint, const FontCollection* typeface,
-                FontStyle style, size_t start, size_t end, bool isRtl);
+        float addStyleRun(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);
 
@@ -145,7 +147,7 @@ class LineBreaker {
             return mWidths.data();
         }
 
-        const uint8_t* getFlags() const {
+        const int* getFlags() const {
             return mFlags.data();
         }
 
@@ -166,23 +168,40 @@ 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;
 
-        void addWordBreak(size_t offset, ParaWidth preBreak, ParaWidth postBreak, float penalty);
+        // 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 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 computeBreaksOpt();
+        void computeBreaksOptimal();
+
+        // special case when LineWidth is constant (layout is rectangle)
+        void computeBreaksOptimalRect();
+
+        void finishBreaksOptimal();
 
         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;
@@ -191,7 +210,7 @@ class LineBreaker {
         // result of line breaking
         std::vector<int> mBreaks;
         std::vector<float> mWidths;
-        std::vector<uint8_t> mFlags;
+        std::vector<int> mFlags;
 
         ParaWidth mWidth = 0;
         std::vector<Candidate> mCandidates;