diff --git a/core/java/android/text/AndroidBidi.java b/core/java/android/text/AndroidBidi.java
index e4f934e..eacd40d 100644
--- a/core/java/android/text/AndroidBidi.java
+++ b/core/java/android/text/AndroidBidi.java
@@ -16,6 +16,8 @@
 
 package android.text;
 
+import android.text.Layout.Directions;
+
 /**
  * Access the ICU bidi implementation.
  * @hide
@@ -44,5 +46,132 @@
         return result;
     }
 
+    /**
+     * Returns run direction information for a line within a paragraph.
+     *
+     * @param dir base line direction, either Layout.DIR_LEFT_TO_RIGHT or
+     *     Layout.DIR_RIGHT_TO_LEFT
+     * @param levels levels as returned from {@link #bidi}
+     * @param lstart start of the line in the levels array
+     * @param chars the character array (used to determine whitespace)
+     * @param cstart the start of the line in the chars array
+     * @param len the length of the line
+     * @return the directions
+     */
+    public static Directions directions(int dir, byte[] levels, int lstart,
+            char[] chars, int cstart, int len) {
+
+        int baseLevel = dir == Layout.DIR_LEFT_TO_RIGHT ? 0 : 1;
+        int curLevel = levels[lstart];
+        int minLevel = curLevel;
+        int runCount = 1;
+        for (int i = lstart + 1, e = lstart + len; i < e; ++i) {
+            int level = levels[i];
+            if (level != curLevel) {
+                curLevel = level;
+                ++runCount;
+            }
+        }
+
+        // add final run for trailing counter-directional whitespace
+        int visLen = len;
+        if ((curLevel & 1) != (baseLevel & 1)) {
+            // look for visible end
+            while (--visLen >= 0) {
+                char ch = chars[cstart + visLen];
+
+                if (ch == '\n') {
+                    --visLen;
+                    break;
+                }
+
+                if (ch != ' ' && ch != '\t') {
+                    break;
+                }
+            }
+            ++visLen;
+            if (visLen != len) {
+                ++runCount;
+            }
+        }
+
+        if (runCount == 1 && minLevel == baseLevel) {
+            // we're done, only one run on this line
+            if ((minLevel & 1) != 0) {
+                return Layout.DIRS_ALL_RIGHT_TO_LEFT;
+            }
+            return Layout.DIRS_ALL_LEFT_TO_RIGHT;
+        }
+
+        int[] ld = new int[runCount * 2];
+        int maxLevel = minLevel;
+        int levelBits = minLevel << Layout.RUN_LEVEL_SHIFT;
+        {
+            // Start of first pair is always 0, we write
+            // length then start at each new run, and the
+            // last run length after we're done.
+            int n = 1;
+            int prev = lstart;
+            curLevel = minLevel;
+            for (int i = lstart, e = lstart + visLen; i < e; ++i) {
+                int level = levels[i];
+                if (level != curLevel) {
+                    curLevel = level;
+                    if (level > maxLevel) {
+                        maxLevel = level;
+                    } else if (level < minLevel) {
+                        minLevel = level;
+                    }
+                    // XXX ignore run length limit of 2^RUN_LEVEL_SHIFT
+                    ld[n++] = (i - prev) | levelBits;
+                    ld[n++] = i - lstart;
+                    levelBits = curLevel << Layout.RUN_LEVEL_SHIFT;
+                    prev = i;
+                }
+            }
+            ld[n] = (lstart + visLen - prev) | levelBits;
+            if (visLen < len) {
+                ld[++n] = visLen;
+                ld[++n] = (len - visLen) | (baseLevel << Layout.RUN_LEVEL_SHIFT);
+            }
+        }
+
+        // See if we need to swap any runs.
+        // If the min level run direction doesn't match the base
+        // direction, we always need to swap (at this point
+        // we have more than one run).
+        // Otherwise, we don't need to swap the lowest level.
+        // Since there are no logically adjacent runs at the same
+        // level, if the max level is the same as the (new) min
+        // level, we have a series of alternating levels that
+        // is already in order, so there's no more to do.
+        //
+        boolean swap;
+        if ((minLevel & 1) == baseLevel) {
+            minLevel += 1;
+            swap = maxLevel > minLevel;
+        } else {
+            swap = runCount > 1;
+        }
+        if (swap) {
+            for (int level = maxLevel - 1; level >= minLevel; --level) {
+                for (int i = 0; i < ld.length; i += 2) {
+                    if (levels[ld[i]] >= level) {
+                        int e = i + 2;
+                        while (e < ld.length && levels[ld[e]] >= level) {
+                            e += 2;
+                        }
+                        for (int low = i, hi = e - 2; low < hi; low += 2, hi -= 2) {
+                            int x = ld[low]; ld[low] = ld[hi]; ld[hi] = x;
+                            x = ld[low+1]; ld[low+1] = ld[hi+1]; ld[hi+1] = x;
+                        }
+                        i = e + 2;
+                    }
+                }
+            }
+        }
+        return new Directions(ld);
+    }
+
     private native static int runBidi(int dir, char[] chs, byte[] chInfo, int n, boolean haveInfo);
 }
\ No newline at end of file
diff --git a/core/java/android/text/BoringLayout.java b/core/java/android/text/BoringLayout.java
index 944f735..9309b05 100644
--- a/core/java/android/text/BoringLayout.java
+++ b/core/java/android/text/BoringLayout.java
@@ -208,11 +208,11 @@
              * width because the width that was passed in was for the
              * full text, not the ellipsized form.
              */
-            synchronized (sTemp) {
-                mMax = (int) (FloatMath.ceil(Styled.measureText(paint, sTemp,
-                                                source, 0, source.length(),
-                                                null)));
-            }
+            TextLine line = TextLine.obtain();
+            line.set(paint, source, 0, source.length(), Layout.DIR_LEFT_TO_RIGHT,
+                    Layout.DIRS_ALL_LEFT_TO_RIGHT, false, null);
+            mMax = (int) FloatMath.ceil(line.metrics(null));
+            TextLine.recycle(line);
         }
 
         if (includepad) {
@@ -276,14 +276,13 @@
             if (fm == null) {
                 fm = new Metrics();
             }
-    
-            int wid;
 
-            synchronized (sTemp) {
-                wid = (int) (FloatMath.ceil(Styled.measureText(paint, sTemp,
-                                                text, 0, text.length(), fm)));
-            }
-            fm.width = wid;
+            TextLine line = TextLine.obtain();
+            line.set(paint, text, 0, text.length(), Layout.DIR_LEFT_TO_RIGHT,
+                    Layout.DIRS_ALL_LEFT_TO_RIGHT, false, null);
+            fm.width = (int) FloatMath.ceil(line.metrics(fm));
+            TextLine.recycle(line);
+
             return fm;
         } else {
             return null;
@@ -389,7 +388,7 @@
 
     public static class Metrics extends Paint.FontMetricsInt {
         public int width;
-        
+
         @Override public String toString() {
             return super.toString() + " width=" + width;
         }
diff --git a/core/java/android/text/Layout.java b/core/java/android/text/Layout.java
index ff1f2a60..3b8f295 100644
--- a/core/java/android/text/Layout.java
+++ b/core/java/android/text/Layout.java
@@ -19,12 +19,10 @@
 import com.android.internal.util.ArrayUtils;
 
 import android.emoji.EmojiFactory;
-import android.graphics.Bitmap;
 import android.graphics.Canvas;
 import android.graphics.Paint;
 import android.graphics.Path;
 import android.graphics.Rect;
-import android.graphics.RectF;
 import android.text.method.TextKeyListener;
 import android.text.style.AlignmentSpan;
 import android.text.style.LeadingMarginSpan;
@@ -60,9 +58,7 @@
             MIN_EMOJI = -1;
             MAX_EMOJI = -1;
         }
-    };
-
-    private RectF mEmojiRect;
+    }
 
     /**
      * Return how wide a layout must be in order to display the
@@ -91,8 +87,8 @@
                 next = end;
 
             // note, omits trailing paragraph char
-            float w = measureText(paint, workPaint,
-                                  source, i, next, null, true, null);
+            float w = measurePara(paint, workPaint,
+                                  source, i, next, true, null);
 
             if (w > need)
                 need = w;
@@ -122,6 +118,15 @@
         if (width < 0)
             throw new IllegalArgumentException("Layout: " + width + " < 0");
 
+        // Ensure paint doesn't have baselineShift set.
+        // While normally we don't modify the paint the user passed in,
+        // we were already doing this in Styled.drawUniformRun with both
+        // baselineShift and bgColor.  We probably should reevaluate bgColor.
+        if (paint != null) {
+            paint.bgColor = 0;
+            paint.baselineShift = 0;
+        }
+
         mText = text;
         mPaint = paint;
         mWorkPaint = new TextPaint();
@@ -262,6 +267,7 @@
 
         Alignment align = mAlignment;
 
+        TextLine tl = TextLine.obtain();
         // Next draw the lines, one at a time.
         // the baseline is the top of the following line minus the current
         // line's descent.
@@ -373,11 +379,11 @@
                 // XXX: assumes there's nothing additional to be done
                 c.drawText(buf, start, end, x, lbaseline, paint);
             } else {
-                drawText(c, buf, start, end, dir, directions,
-                    x, ltop, lbaseline, lbottom, paint, mWorkPaint,
-                    hasTab, spans);
+                tl.set(paint, buf, start, end, dir, directions, hasTab, spans);
+                tl.draw(c, x, ltop, lbaseline, lbottom);
             }
         }
+        TextLine.recycle(tl);
     }
 
     /**
@@ -639,7 +645,7 @@
 
     private float getHorizontal(int offset, boolean trailing, int line) {
         int start = getLineStart(line);
-        int end = getLineVisibleEnd(line);
+        int end = getLineEnd(line);
         int dir = getParagraphDirection(line);
         boolean tab = getLineContainsTab(line);
         Directions directions = getLineDirections(line);
@@ -649,17 +655,10 @@
             tabs = ((Spanned) mText).getSpans(start, end, TabStopSpan.class);
         }
 
-        float wid = measureText(mPaint, mWorkPaint, mText, start, offset, end,
-                                dir, directions, trailing, tab, tabs);
-
-        if (offset > end) {
-            if (dir == DIR_RIGHT_TO_LEFT)
-                wid -= measureText(mPaint, mWorkPaint,
-                                   mText, end, offset, null, tab, tabs);
-            else
-                wid += measureText(mPaint, mWorkPaint,
-                                   mText, end, offset, null, tab, tabs);
-        }
+        TextLine tl = TextLine.obtain();
+        tl.set(mPaint, mText, start, end, dir, directions, tab, tabs);
+        float wid = tl.measure(offset - start, trailing, null);
+        TextLine.recycle(tl);
 
         Alignment align = getParagraphAlignment(line);
         int left = getParagraphLeft(line);
@@ -761,21 +760,15 @@
 
     private float getLineMax(int line, Object[] tabs, boolean full) {
         int start = getLineStart(line);
-        int end;
+        int end = full ? getLineEnd(line) : getLineVisibleEnd(line);
+        boolean hasTabs = getLineContainsTab(line);
+        Directions directions = getLineDirections(line);
 
-        if (full) {
-            end = getLineEnd(line);
-        } else {
-            end = getLineVisibleEnd(line);
-        }
-        boolean tab = getLineContainsTab(line);
-
-        if (tabs == null && tab && mText instanceof Spanned) {
-            tabs = ((Spanned) mText).getSpans(start, end, TabStopSpan.class);
-        }
-
-        return measureText(mPaint, mWorkPaint,
-                           mText, start, end, null, tab, tabs);
+        TextLine tl = TextLine.obtain();
+        tl.set(mPaint, mText, start, end, 1, directions, hasTabs, tabs);
+        float width = tl.metrics(null);
+        TextLine.recycle(tl);
+        return width;
     }
 
     /**
@@ -975,165 +968,49 @@
         return getOffsetToLeftRightOf(offset, false);
     }
 
-    // 1) The caret marks the leading edge of a character. The character
-    // logically before it might be on a different level, and the active caret
-    // position is on the character at the lower level. If that character
-    // was the previous character, the caret is on its trailing edge.
-    // 2) Take this character/edge and move it in the indicated direction.
-    // This gives you a new character and a new edge.
-    // 3) This position is between two visually adjacent characters.  One of
-    // these might be at a lower level.  The active position is on the
-    // character at the lower level.
-    // 4) If the active position is on the trailing edge of the character,
-    // the new caret position is the following logical character, else it
-    // is the character.
     private int getOffsetToLeftRightOf(int caret, boolean toLeft) {
         int line = getLineForOffset(caret);
         int lineStart = getLineStart(line);
         int lineEnd = getLineEnd(line);
+        int lineDir = getParagraphDirection(line);
 
-        boolean paraIsRtl = getParagraphDirection(line) == -1;
-        int[] runs = getLineDirections(line).mDirections;
-
-        int runIndex, runLevel = 0, runStart = lineStart, runLimit = lineEnd, newCaret = -1;
-        boolean trailing = false;
-
-        if (caret == lineStart) {
-            runIndex = -2;
-        } else if (caret == lineEnd) {
-            runIndex = runs.length;
-        } else {
-          // First, get information about the run containing the character with
-          // the active caret.
-          for (runIndex = 0; runIndex < runs.length; runIndex += 2) {
-            runStart = lineStart + runs[runIndex];
-            if (caret >= runStart) {
-              runLimit = runStart + (runs[runIndex+1] & RUN_LENGTH_MASK);
-              if (runLimit > lineEnd) {
-                  runLimit = lineEnd;
-              }
-              if (caret < runLimit) {
-                runLevel = (runs[runIndex+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
-                if (caret == runStart) {
-                  // The caret is on a run boundary, see if we should
-                  // use the position on the trailing edge of the previous
-                  // logical character instead.
-                  int prevRunIndex, prevRunLevel, prevRunStart, prevRunLimit;
-                  int pos = caret - 1;
-                  for (prevRunIndex = 0; prevRunIndex < runs.length; prevRunIndex += 2) {
-                    prevRunStart = lineStart + runs[prevRunIndex];
-                    if (pos >= prevRunStart) {
-                      prevRunLimit = prevRunStart + (runs[prevRunIndex+1] & RUN_LENGTH_MASK);
-                      if (prevRunLimit > lineEnd) {
-                          prevRunLimit = lineEnd;
-                      }
-                      if (pos < prevRunLimit) {
-                        prevRunLevel = (runs[prevRunIndex+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
-                        if (prevRunLevel < runLevel) {
-                          // Start from logically previous character.
-                          runIndex = prevRunIndex;
-                          runLevel = prevRunLevel;
-                          runStart = prevRunStart;
-                          runLimit = prevRunLimit;
-                          trailing = true;
-                          break;
-                        }
-                      }
-                    }
-                  }
+        boolean advance = toLeft == (lineDir == DIR_RIGHT_TO_LEFT);
+        if (caret == (advance ? lineEnd : lineStart)) {
+            // walking off line, so look at the line we're headed to
+            if (caret == lineStart) {
+                if (line > 0) {
+                    --line;
+                } else {
+                    return caret; // at very start, don't move
                 }
-                break;
-              }
+            } else {
+                if (line < getLineCount() - 1) {
+                    ++line;
+                } else {
+                    return caret; // at very end, don't move
+                }
             }
-          }
 
-          // caret might be = lineEnd.  This is generally a space or paragraph
-          // separator and has an associated run, but might be the end of
-          // text, in which case it doesn't.  If that happens, we ran off the
-          // end of the run list, and runIndex == runs.length.  In this case,
-          // we are at a run boundary so we skip the below test.
-          if (runIndex != runs.length) {
-              boolean rtlRun = (runLevel & 0x1) != 0;
-              boolean advance = toLeft == rtlRun;
-              if (caret != (advance ? runLimit : runStart) || advance != trailing) {
-                  // Moving within or into the run, so we can move logically.
-                  newCaret = getOffsetBeforeAfter(caret, advance);
-                  // If the new position is internal to the run, we're at the strong
-                  // position already so we're finished.
-                  if (newCaret != (advance ? runLimit : runStart)) {
-                      return newCaret;
-                  }
-              }
-          }
+            lineStart = getLineStart(line);
+            lineEnd = getLineEnd(line);
+            int newDir = getParagraphDirection(line);
+            if (newDir != lineDir) {
+                // unusual case.  we want to walk onto the line, but it runs
+                // in a different direction than this one, so we fake movement
+                // in the opposite direction.
+                toLeft = !toLeft;
+                lineDir = newDir;
+            }
         }
 
-        // If newCaret is -1, we're starting at a run boundary and crossing
-        // into another run. Otherwise we've arrived at a run boundary, and
-        // need to figure out which character to attach to.  Note we might
-        // need to run this twice, if we cross a run boundary and end up at
-        // another run boundary.
-        while (true) {
-          boolean advance = toLeft == paraIsRtl;
-          int otherRunIndex = runIndex + (advance ? 2 : -2);
-          if (otherRunIndex >= 0 && otherRunIndex < runs.length) {
-            int otherRunStart = lineStart + runs[otherRunIndex];
-            int otherRunLimit = otherRunStart + (runs[otherRunIndex+1] & RUN_LENGTH_MASK);
-            if (otherRunLimit > lineEnd) {
-                otherRunLimit = lineEnd;
-            }
-            int otherRunLevel = runs[otherRunIndex+1] >>> RUN_LEVEL_SHIFT & RUN_LEVEL_MASK;
-            boolean otherRunIsRtl = (otherRunLevel & 1) != 0;
+        Directions directions = getLineDirections(line);
 
-            advance = toLeft == otherRunIsRtl;
-            if (newCaret == -1) {
-              newCaret = getOffsetBeforeAfter(advance ? otherRunStart : otherRunLimit, advance);
-              if (newCaret == (advance ? otherRunLimit : otherRunStart)) {
-                // Crossed and ended up at a new boundary, repeat a second and final time.
-                runIndex = otherRunIndex;
-                runLevel = otherRunLevel;
-                continue;
-              }
-              break;
-            }
-
-            // The new caret is at a boundary.
-            if (otherRunLevel < runLevel) {
-              // The strong character is in the other run.
-              newCaret = advance ? otherRunStart : otherRunLimit;
-            }
-            break;
-          }
-
-          if (newCaret == -1) {
-              // We're walking off the end of the line.  The paragraph
-              // level is always equal to or lower than any internal level, so
-              // the boundaries get the strong caret.
-              newCaret = getOffsetBeforeAfter(caret, advance);
-              break;
-          }
-          // Else we've arrived at the end of the line.  That's a strong position.
-          // We might have arrived here by crossing over a run with no internal
-          // breaks and dropping out of the above loop before advancing one final
-          // time, so reset the caret.
-          // Note, we use '<=' below to handle a situation where the only run
-          // on the line is a counter-directional run.  If we're not advancing,
-          // we can end up at the 'lineEnd' position but the caret we want is at
-          // the lineStart.
-          if (newCaret <= lineEnd) {
-              newCaret = advance ? lineEnd : lineStart;
-          }
-          break;
-        }
-
-        return newCaret;
-    }
-
-    // utility, maybe just roll into the above.
-    private int getOffsetBeforeAfter(int offset, boolean after) {
-        if (after) {
-            return TextUtils.getOffsetAfter(mText, offset);
-        }
-        return TextUtils.getOffsetBefore(mText, offset);
+        TextLine tl = TextLine.obtain();
+        // XXX: we don't care about tabs
+        tl.set(mPaint, mText, lineStart, lineEnd, lineDir, directions, false, null);
+        caret = lineStart + tl.getOffsetToLeftRightOf(caret - lineStart, toLeft);
+        tl = TextLine.recycle(tl);
+        return caret;
     }
 
     private int getOffsetAtStartOf(int offset) {
@@ -1427,373 +1304,28 @@
         return right;
     }
 
-    private void drawText(Canvas canvas,
-                                 CharSequence text, int start, int end,
-                                 int dir, Directions directions,
-                                 float x, int top, int y, int bottom,
-                                 TextPaint paint,
-                                 TextPaint workPaint,
-                                 boolean hasTabs, Object[] parspans) {
-        char[] buf;
-        if (!hasTabs) {
-            if (directions == DIRS_ALL_LEFT_TO_RIGHT) {
-                if (DEBUG) {
-                    Assert.assertTrue(DIR_LEFT_TO_RIGHT == dir);
-                }
-                Styled.drawText(canvas, text, start, end, dir, false, x, top, y, bottom, paint, workPaint, false);
-                return;
+    /* package */
+    static float measurePara(TextPaint paint, TextPaint workPaint,
+            CharSequence text, int start, int end, boolean hasTabs,
+            Object[] tabs) {
+
+        MeasuredText mt = MeasuredText.obtain();
+        TextLine tl = TextLine.obtain();
+        try {
+            mt.setPara(text, start, end, DIR_REQUEST_LTR);
+            Directions directions;
+            if (mt.mEasy){
+                directions = DIRS_ALL_LEFT_TO_RIGHT;
+            } else {
+                directions = AndroidBidi.directions(mt.mDir, mt.mLevels,
+                    0, mt.mChars, 0, mt.mLen);
             }
-            buf = null;
-        } else {
-            buf = TextUtils.obtain(end - start);
-            TextUtils.getChars(text, start, end, buf, 0);
+            tl.set(paint, text, start, end, 1, directions, hasTabs, tabs);
+            return tl.metrics(null);
+        } finally {
+            TextLine.recycle(tl);
+            MeasuredText.recycle(mt);
         }
-
-        float h = 0;
-
-        int lastRunIndex = directions.mDirections.length - 2;
-        for (int i = 0; i < directions.mDirections.length; i += 2) {
-            int here = start + directions.mDirections[i];
-            int there = here + (directions.mDirections[i+1] & RUN_LENGTH_MASK);
-            boolean runIsRtl = (directions.mDirections[i+1] & RUN_RTL_FLAG) != 0;
-
-            if (there > end)
-                there = end;
-
-            int segstart = here;
-            for (int j = hasTabs ? here : there; j <= there; j++) {
-                int pj = j - start;
-                if (j == there || buf[pj] == '\t') {
-                    h += Styled.drawText(canvas, text,
-                                         segstart, j,
-                                         dir, runIsRtl, x + h,
-                                         top, y, bottom, paint, workPaint,
-                                         i != lastRunIndex || j != end);
-
-                    if (j != there)
-                        h = dir * nextTab(text, start, end, h * dir, parspans);
-
-                    segstart = j + 1;
-                } else if (hasTabs && buf[pj] >= 0xD800 && buf[pj] <= 0xDFFF && j + 1 < there) {
-                    int emoji = Character.codePointAt(buf, pj);
-
-                    if (emoji >= MIN_EMOJI && emoji <= MAX_EMOJI) {
-                        Bitmap bm = EMOJI_FACTORY.
-                            getBitmapFromAndroidPua(emoji);
-
-                        if (bm != null) {
-                            h += Styled.drawText(canvas, text,
-                                                 segstart, j,
-                                                 dir, runIsRtl, x + h,
-                                                 top, y, bottom, paint, workPaint,
-                                                 i != lastRunIndex || j != end);
-
-                            if (mEmojiRect == null) {
-                                mEmojiRect = new RectF();
-                            }
-
-                            workPaint.set(paint);
-                            Styled.measureText(paint, workPaint, text,
-                                               j, j + 1,
-                                               null);
-
-                            float bitmapHeight = bm.getHeight();
-                            float textHeight = -workPaint.ascent();
-                            float scale = textHeight / bitmapHeight;
-                            float width = bm.getWidth() * scale;
-
-                            mEmojiRect.set(x + h, y - textHeight,
-                                           x + h + width, y);
-
-                            canvas.drawBitmap(bm, null, mEmojiRect, paint);
-                            h += width;
-
-                            j++;
-                            segstart = j + 1;
-                        }
-                    }
-                }
-            }
-        }
-
-        if (hasTabs)
-            TextUtils.recycle(buf);
-    }
-
-    /**
-     * Get the distance from the margin to the requested edge of the character
-     * at offset on the line from start to end.  Trailing indicates the edge
-     * should be the trailing edge of the character at offset-1.
-     */
-    /* package */ static float measureText(TextPaint paint,
-                                     TextPaint workPaint,
-                                     CharSequence text,
-                                     int start, int offset, int end,
-                                     int dir, Directions directions,
-                                     boolean trailing, boolean hasTabs,
-                                     Object[] tabs) {
-        char[] buf = null;
-
-        if (hasTabs) {
-            buf = TextUtils.obtain(end - start);
-            TextUtils.getChars(text, start, end, buf, 0);
-        }
-
-        float h = 0;
-
-        int target = trailing ? offset - 1 : offset;
-        if (target < start) {
-            return 0;
-        }
-
-        int[] runs = directions.mDirections;
-        for (int i = 0; i < runs.length; i += 2) {
-            int here = start + runs[i];
-            int there = here + (runs[i+1] & RUN_LENGTH_MASK);
-            if (there > end) {
-                there = end;
-            }
-            boolean runIsRtl = (runs[i+1] & RUN_RTL_FLAG) != 0;
-
-            int segstart = here;
-            for (int j = hasTabs ? here : there; j <= there; j++) {
-                int codept = 0;
-                Bitmap bm = null;
-
-                if (hasTabs && j < there) {
-                    codept = buf[j - start];
-                }
-
-                if (codept >= 0xD800 && codept <= 0xDFFF && j + 1 < there) {
-                    codept = Character.codePointAt(buf, j - start);
-
-                    if (codept >= MIN_EMOJI && codept <= MAX_EMOJI) {
-                        bm = EMOJI_FACTORY.getBitmapFromAndroidPua(codept);
-                    }
-                }
-
-                if (j == there || codept == '\t' || bm != null) {
-                    float segw;
-
-                    boolean inSegment = target >= segstart && target < j;
-
-                    if (inSegment) {
-                        if (dir == DIR_LEFT_TO_RIGHT && !runIsRtl) {
-                            h += Styled.measureText(paint, workPaint, text,
-                                                    segstart, offset,
-                                                    null);
-                            return h;
-                        }
-
-                        if (dir == DIR_RIGHT_TO_LEFT && runIsRtl) {
-                            h -= Styled.measureText(paint, workPaint, text,
-                                                    segstart, offset,
-                                                    null);
-                            return h;
-                        }
-                    }
-
-                    // XXX Style.measureText assumes LTR?
-                    segw = Styled.measureText(paint, workPaint, text,
-                                              segstart, j,
-                                              null);
-
-                    if (inSegment) {
-                        if (dir == DIR_LEFT_TO_RIGHT) {
-                            h += segw - Styled.measureText(paint, workPaint,
-                                                           text,
-                                                           segstart,
-                                                           offset, null);
-                            return h;
-                        }
-
-                        if (dir == DIR_RIGHT_TO_LEFT) {
-                            h -= segw - Styled.measureText(paint, workPaint,
-                                                           text,
-                                                           segstart,
-                                                           offset, null);
-                            return h;
-                        }
-                    }
-
-                    if (dir == DIR_RIGHT_TO_LEFT)
-                        h -= segw;
-                    else
-                        h += segw;
-
-                    if (j != there && buf[j - start] == '\t') {
-                        if (offset == j)
-                            return h;
-
-                        h = dir * nextTab(text, start, end, h * dir, tabs);
-
-                        if (target == j) {
-                            return h;
-                        }
-                    }
-
-                    if (bm != null) {
-                        workPaint.set(paint);
-                        Styled.measureText(paint, workPaint, text,
-                                           j, j + 2, null);
-
-                        float wid = bm.getWidth() *
-                                    -workPaint.ascent() / bm.getHeight();
-
-                        if (dir == DIR_RIGHT_TO_LEFT) {
-                            h -= wid;
-                        } else {
-                            h += wid;
-                        }
-
-                        j++;
-                    }
-
-                    segstart = j + 1;
-                }
-            }
-        }
-
-        if (hasTabs)
-            TextUtils.recycle(buf);
-
-        return h;
-    }
-
-    /**
-     * Measure width of a run of text on a single line that is known to all be
-     * in the same direction as the paragraph base direction. Returns the width,
-     * and the line metrics in fm if fm is not null.
-     *
-     * @param paint the paint for the text; will not be modified
-     * @param workPaint paint available for modification
-     * @param text text
-     * @param start start of the line
-     * @param end limit of the line
-     * @param fm object to return integer metrics in, can be null
-     * @param hasTabs true if it is known that the line has tabs
-     * @param tabs tab position information
-     * @return the width of the text from start to end
-     */
-    /* package */ static float measureText(TextPaint paint,
-                                           TextPaint workPaint,
-                                           CharSequence text,
-                                           int start, int end,
-                                           Paint.FontMetricsInt fm,
-                                           boolean hasTabs, Object[] tabs) {
-        char[] buf = null;
-
-        if (hasTabs) {
-            buf = TextUtils.obtain(end - start);
-            TextUtils.getChars(text, start, end, buf, 0);
-        }
-
-        int len = end - start;
-
-        int lastPos = 0;
-        float width = 0;
-        int ascent = 0, descent = 0, top = 0, bottom = 0;
-
-        if (fm != null) {
-            fm.ascent = 0;
-            fm.descent = 0;
-        }
-
-        for (int pos = hasTabs ? 0 : len; pos <= len; pos++) {
-            int codept = 0;
-            Bitmap bm = null;
-
-            if (hasTabs && pos < len) {
-                codept = buf[pos];
-            }
-
-            if (codept >= 0xD800 && codept <= 0xDFFF && pos < len) {
-                codept = Character.codePointAt(buf, pos);
-
-                if (codept >= MIN_EMOJI && codept <= MAX_EMOJI) {
-                    bm = EMOJI_FACTORY.getBitmapFromAndroidPua(codept);
-                }
-            }
-
-            if (pos == len || codept == '\t' || bm != null) {
-                workPaint.baselineShift = 0;
-
-                // XXX Styled.measureText assumes the run direction is LTR,
-                // but it might not be.  Check this.
-                width += Styled.measureText(paint, workPaint, text,
-                                        start + lastPos, start + pos,
-                                        fm);
-
-                if (fm != null) {
-                    if (workPaint.baselineShift < 0) {
-                        fm.ascent += workPaint.baselineShift;
-                        fm.top += workPaint.baselineShift;
-                    } else {
-                        fm.descent += workPaint.baselineShift;
-                        fm.bottom += workPaint.baselineShift;
-                    }
-                }
-
-                if (pos != len) {
-                    if (bm == null) {
-                        // no emoji, must have hit a tab
-                        width = nextTab(text, start, end, width, tabs);
-                    } else {
-                        // This sets up workPaint with the font on the emoji
-                        // text, so that we can extract the ascent and scale.
-
-                        // We can't use the result of the previous call to
-                        // measureText because the emoji might have its own style.
-                        // We have to initialize workPaint here because if the
-                        // text is unstyled measureText might not use workPaint
-                        // at all.
-                        workPaint.set(paint);
-                        Styled.measureText(paint, workPaint, text,
-                                           start + pos, start + pos + 1, null);
-
-                        width += bm.getWidth() *
-                                    -workPaint.ascent() / bm.getHeight();
-
-                        // Since we had an emoji, we bump past the second half
-                        // of the surrogate pair.
-                        pos++;
-                    }
-                }
-
-                if (fm != null) {
-                    if (fm.ascent < ascent) {
-                        ascent = fm.ascent;
-                    }
-                    if (fm.descent > descent) {
-                        descent = fm.descent;
-                    }
-
-                    if (fm.top < top) {
-                        top = fm.top;
-                    }
-                    if (fm.bottom > bottom) {
-                        bottom = fm.bottom;
-                    }
-
-                    // No need to take bitmap height into account here,
-                    // since it is scaled to match the text height.
-                }
-
-                lastPos = pos + 1;
-            }
-        }
-
-        if (fm != null) {
-            fm.ascent = ascent;
-            fm.descent = descent;
-            fm.top = top;
-            fm.bottom = bottom;
-        }
-
-        if (hasTabs)
-            TextUtils.recycle(buf);
-
-        return width;
     }
 
     /**
@@ -1898,6 +1430,7 @@
      * line is ellipsized, not getLineStart().)
      */
     public abstract int getEllipsisStart(int line);
+
     /**
      * Returns the number of characters to be ellipsized away, or 0 if
      * no ellipsis is to take place.
diff --git a/core/java/android/text/MeasuredText.java b/core/java/android/text/MeasuredText.java
new file mode 100644
index 0000000..e3a113d
--- /dev/null
+++ b/core/java/android/text/MeasuredText.java
@@ -0,0 +1,250 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+package android.text;
+
+import com.android.internal.util.ArrayUtils;
+
+import android.graphics.Paint;
+import android.icu.text.ArabicShaping;
+import android.text.style.MetricAffectingSpan;
+import android.text.style.ReplacementSpan;
+import android.util.Log;
+
+/**
+ * @hide
+ */
+class MeasuredText {
+    /* package */ CharSequence mText;
+    /* package */ int mTextStart;
+    /* package */ float[] mWidths;
+    /* package */ char[] mChars;
+    /* package */ byte[] mLevels;
+    /* package */ int mDir;
+    /* package */ boolean mEasy;
+    /* package */ int mLen;
+    private int mPos;
+    private float[] mWorkWidths; // temp buffer for Paint.measureText, arrgh
+    private TextPaint mWorkPaint;
+
+    private MeasuredText() {
+        mWorkPaint = new TextPaint();
+    }
+
+    private static MeasuredText[] cached = new MeasuredText[3];
+
+    /* package */
+    static MeasuredText obtain() {
+        MeasuredText mt;
+        synchronized (cached) {
+            for (int i = cached.length; --i >= 0;) {
+                if (cached[i] != null) {
+                    mt = cached[i];
+                    cached[i] = null;
+                    return mt;
+                }
+            }
+        }
+        mt = new MeasuredText();
+        Log.e("MEAS", "new: " + mt);
+        return mt;
+    }
+
+    /* package */
+    static MeasuredText recycle(MeasuredText mt) {
+        mt.mText = null;
+        if (mt.mLen < 1000) {
+            synchronized(cached) {
+                for (int i = 0; i < cached.length; ++i) {
+                    if (cached[i] == null) {
+                        cached[i] = mt;
+                        break;
+                    }
+                }
+            }
+        }
+        return null;
+    }
+
+    /**
+     * Analyzes text for
+     * bidirectional runs.  Allocates working buffers.
+     */
+    /* package */
+    void setPara(CharSequence text, int start, int end, int bidiRequest) {
+        mText = text;
+        mTextStart = start;
+
+        int len = end - start;
+        mLen = len;
+        mPos = 0;
+
+        if (mWidths == null || mWidths.length < len) {
+            mWidths = new float[ArrayUtils.idealFloatArraySize(len)];
+            mWorkWidths = new float[mWidths.length];
+        }
+        if (mChars == null || mChars.length < len) {
+            mChars = new char[ArrayUtils.idealCharArraySize(len)];
+        }
+        TextUtils.getChars(text, start, end, mChars, 0);
+
+        if (text instanceof Spanned) {
+            Spanned spanned = (Spanned) text;
+            ReplacementSpan[] spans = spanned.getSpans(start, end,
+                    ReplacementSpan.class);
+
+            for (int i = 0; i < spans.length; i++) {
+                int startInPara = spanned.getSpanStart(spans[i]) - start;
+                int endInPara = spanned.getSpanEnd(spans[i]) - start;
+                for (int j = startInPara; j < endInPara; j++) {
+                    mChars[j] = '\uFFFC';
+                }
+            }
+        }
+
+        if (TextUtils.doesNotNeedBidi(mChars, 0, len)) {
+            mDir = 1;
+            mEasy = true;
+        } else {
+            if (mLevels == null || mLevels.length < len) {
+                mLevels = new byte[ArrayUtils.idealByteArraySize(len)];
+            }
+            mDir = AndroidBidi.bidi(bidiRequest, mChars, mLevels, len, false);
+            mEasy = false;
+
+            // shape
+            if (mLen > 0) {
+                byte[] levels = mLevels;
+                char[] chars = mChars;
+                byte level = levels[0];
+                int pi = 0;
+                for (int i = 1, e = mLen;; ++i) {
+                    if (i == e || levels[i] != level) {
+                        if ((level & 0x1) != 0) {
+                            AndroidCharacter.mirror(chars, pi, i - pi);
+                            ArabicShaping.SHAPER.shape(chars, pi, i - pi);
+                        }
+                        if (i == e) {
+                            break;
+                        }
+                        pi = i;
+                        level = levels[i];
+                    }
+                }
+            }
+        }
+    }
+
+    float addStyleRun(TextPaint paint, int len, Paint.FontMetricsInt fm) {
+        int p = mPos;
+        float[] w = mWidths, ww = mWorkWidths;
+        int count = paint.getTextWidths(mChars, p, len, ww);
+        int width = 0;
+        if (count < len) {
+            // must have surrogate pairs in here, pad out the array with zero
+            // for the trailing surrogates
+            char[] chars = mChars;
+            for (int i = 0, e = mLen; i < count; ++i) {
+                width += (w[p++] = ww[i]);
+                if (p < e && chars[p] >= '\udc00' && chars[p] < '\ue000' &&
+                        chars[p-1] >= '\ud800' && chars[p-1] < '\udc00') {
+                    w[p++] = 0;
+                }
+            }
+        } else {
+            for (int i = 0; i < len; ++i) {
+                width += (w[p++] = ww[i]);
+            }
+        }
+        mPos = p;
+        if (fm != null) {
+            paint.getFontMetricsInt(fm);
+        }
+        return width;
+    }
+
+    float addStyleRun(TextPaint paint, MetricAffectingSpan[] spans, int len,
+            Paint.FontMetricsInt fm) {
+
+        TextPaint workPaint = mWorkPaint;
+        workPaint.set(paint);
+        // XXX paint should not have a baseline shift, but...
+        workPaint.baselineShift = 0;
+
+        ReplacementSpan replacement = null;
+        for (int i = 0; i < spans.length; i++) {
+            MetricAffectingSpan span = spans[i];
+            if (span instanceof ReplacementSpan) {
+                replacement = (ReplacementSpan)span;
+            } else {
+                span.updateMeasureState(workPaint);
+            }
+        }
+
+        float wid;
+        if (replacement == null) {
+            wid = addStyleRun(workPaint, len, fm);
+        } else {
+            // Use original text.  Shouldn't matter.
+            wid = replacement.getSize(workPaint, mText, mTextStart + mPos,
+                    mTextStart + mPos + len, fm);
+            float[] w = mWidths;
+            w[mPos] = wid;
+            for (int i = mPos + 1, e = mPos + len; i < e; i++)
+                w[i] = 0;
+        }
+
+        if (fm != null) {
+            if (workPaint.baselineShift < 0) {
+                fm.ascent += workPaint.baselineShift;
+                fm.top += workPaint.baselineShift;
+            } else {
+                fm.descent += workPaint.baselineShift;
+                fm.bottom += workPaint.baselineShift;
+            }
+        }
+
+        return wid;
+    }
+
+    int breakText(int start, int limit, boolean forwards, float width) {
+        float[] w = mWidths;
+        if (forwards) {
+            for (int i = start; i < limit; ++i) {
+                if ((width -= w[i]) < 0) {
+                    return i - start;
+                }
+            }
+        } else {
+            for (int i = limit; --i >= start;) {
+                if ((width -= w[i]) < 0) {
+                    return limit - i -1;
+                }
+            }
+        }
+
+        return limit - start;
+    }
+
+    float measure(int start, int limit) {
+        float width = 0;
+        float[] w = mWidths;
+        for (int i = start; i < limit; ++i) {
+            width += w[i];
+        }
+        return width;
+    }
+}
\ No newline at end of file
diff --git a/core/java/android/text/StaticLayout.java b/core/java/android/text/StaticLayout.java
index bfa0ab6..0c6c545 100644
--- a/core/java/android/text/StaticLayout.java
+++ b/core/java/android/text/StaticLayout.java
@@ -23,8 +23,6 @@
 import android.text.style.LeadingMarginSpan;
 import android.text.style.LineHeightSpan;
 import android.text.style.MetricAffectingSpan;
-import android.text.style.ReplacementSpan;
-import android.util.Log;
 
 /**
  * StaticLayout is a Layout for text that will not be edited after it
@@ -96,13 +94,13 @@
         mLineDirections = new Directions[
                              ArrayUtils.idealIntArraySize(2 * mColumns)];
 
+        mMeasured = MeasuredText.obtain();
+
         generate(source, bufstart, bufend, paint, outerwidth, align,
                  spacingmult, spacingadd, includepad, includepad,
                  ellipsize != null, ellipsizedWidth, ellipsize);
 
-        mChdirs = null;
-        mChs = null;
-        mWidths = null;
+        mMeasured = MeasuredText.recycle(mMeasured);
         mFontMetricsInt = null;
     }
 
@@ -113,6 +111,7 @@
         mLines = new int[ArrayUtils.idealIntArraySize(2 * mColumns)];
         mLineDirections = new Directions[
                              ArrayUtils.idealIntArraySize(2 * mColumns)];
+        mMeasured = MeasuredText.obtain();
     }
 
     /* package */ void generate(CharSequence source, int bufstart, int bufend,
@@ -130,38 +129,22 @@
         Paint.FontMetricsInt fm = mFontMetricsInt;
         int[] choosehtv = null;
 
-        int end = TextUtils.indexOf(source, '\n', bufstart, bufend);
-        int bufsiz = end >= 0 ? end - bufstart : bufend - bufstart;
-        boolean first = true;
+        MeasuredText measured = mMeasured;
 
-        if (mChdirs == null) {
-            mChdirs = new byte[ArrayUtils.idealByteArraySize(bufsiz + 1)];
-            mChs = new char[ArrayUtils.idealCharArraySize(bufsiz + 1)];
-            mWidths = new float[ArrayUtils.idealIntArraySize((bufsiz + 1) * 2)];
-        }
-
-        byte[] chdirs = mChdirs;
-        char[] chs = mChs;
-        float[] widths = mWidths;
-
-        AlteredCharSequence alter = null;
         Spanned spanned = null;
-
         if (source instanceof Spanned)
             spanned = (Spanned) source;
 
         int DEFAULT_DIR = DIR_LEFT_TO_RIGHT; // XXX
 
-        for (int start = bufstart; start <= bufend; start = end) {
-            if (first)
-                first = false;
+        int paraEnd;
+        for (int paraStart = bufstart; paraStart <= bufend; paraStart = paraEnd) {
+            paraEnd = TextUtils.indexOf(source, '\n', paraStart, bufend);
+            if (paraEnd < 0)
+                paraEnd = bufend;
             else
-                end = TextUtils.indexOf(source, '\n', start, bufend);
-
-            if (end < 0)
-                end = bufend;
-            else
-                end++;
+                paraEnd++;
+            int paraLen = paraEnd - paraStart;
 
             int firstWidthLineCount = 1;
             int firstwidth = outerwidth;
@@ -170,19 +153,20 @@
             LineHeightSpan[] chooseht = null;
 
             if (spanned != null) {
-                LeadingMarginSpan[] sp;
-
-                sp = spanned.getSpans(start, end, LeadingMarginSpan.class);
+                LeadingMarginSpan[] sp = spanned.getSpans(paraStart, paraEnd,
+                        LeadingMarginSpan.class);
                 for (int i = 0; i < sp.length; i++) {
                     LeadingMarginSpan lms = sp[i];
                     firstwidth -= sp[i].getLeadingMargin(true);
                     restwidth -= sp[i].getLeadingMargin(false);
                     if (lms instanceof LeadingMarginSpan.LeadingMarginSpan2) {
-                        firstWidthLineCount = ((LeadingMarginSpan.LeadingMarginSpan2)lms).getLeadingMarginLineCount();
+                        firstWidthLineCount =
+                            ((LeadingMarginSpan.LeadingMarginSpan2)lms)
+                            .getLeadingMarginLineCount();
                     }
                 }
 
-                chooseht = spanned.getSpans(start, end, LineHeightSpan.class);
+                chooseht = spanned.getSpans(paraStart, paraEnd, LineHeightSpan.class);
 
                 if (chooseht.length != 0) {
                     if (choosehtv == null ||
@@ -194,7 +178,7 @@
                     for (int i = 0; i < chooseht.length; i++) {
                         int o = spanned.getSpanStart(chooseht[i]);
 
-                        if (o < start) {
+                        if (o < paraStart) {
                             // starts in this layout, before the
                             // current paragraph
 
@@ -208,135 +192,48 @@
                 }
             }
 
-            if (end - start > chdirs.length) {
-                chdirs = new byte[ArrayUtils.idealByteArraySize(end - start)];
-                mChdirs = chdirs;
-            }
-            if (end - start > chs.length) {
-                chs = new char[ArrayUtils.idealCharArraySize(end - start)];
-                mChs = chs;
-            }
-            if ((end - start) * 2 > widths.length) {
-                widths = new float[ArrayUtils.idealIntArraySize((end - start) * 2)];
-                mWidths = widths;
-            }
+            measured.setPara(source, paraStart, paraEnd, DIR_REQUEST_DEFAULT_LTR);
+            char[] chs = measured.mChars;
+            float[] widths = measured.mWidths;
+            byte[] chdirs = measured.mLevels;
+            int dir = measured.mDir;
+            boolean easy = measured.mEasy;
 
-            TextUtils.getChars(source, start, end, chs, 0);
-            final int n = end - start;
-
-            boolean easy = true;
-            boolean altered = false;
-            int dir = DEFAULT_DIR; // XXX pass value in
-
-            for (int i = 0; i < n; i++) {
-                if (chs[i] >= FIRST_RIGHT_TO_LEFT) {
-                    easy = false;
-                    break;
-                }
-            }
-
-            // Ensure that none of the underlying characters are treated
-            // as viable breakpoints, and that the entire run gets the
-            // same bidi direction.
-
-            if (source instanceof Spanned) {
-                Spanned sp = (Spanned) source;
-                ReplacementSpan[] spans = sp.getSpans(start, end, ReplacementSpan.class);
-
-                for (int y = 0; y < spans.length; y++) {
-                    int a = sp.getSpanStart(spans[y]);
-                    int b = sp.getSpanEnd(spans[y]);
-
-                    for (int x = a; x < b; x++) {
-                        chs[x - start] = '\uFFFC';
-                    }
-                }
-            }
-
-            if (!easy) {
-                // XXX put override flags, etc. into chdirs
-                // XXX supply dir rather than force
-                dir = AndroidBidi.bidi(DIR_REQUEST_DEFAULT_LTR, chs, chdirs, n, false);
-
-                // Do mirroring for right-to-left segments
-
-                for (int i = 0; i < n; i++) {
-                    if (chdirs[i] == Character.DIRECTIONALITY_RIGHT_TO_LEFT) {
-                        int j;
-
-                        for (j = i; j < n; j++) {
-                            if (chdirs[j] !=
-                                Character.DIRECTIONALITY_RIGHT_TO_LEFT)
-                                break;
-                        }
-
-                        if (AndroidCharacter.mirror(chs, i, j - i))
-                            altered = true;
-
-                        i = j - 1;
-                    }
-                }
-            }
-
-            CharSequence sub;
-
-            if (altered) {
-                if (alter == null)
-                    alter = AlteredCharSequence.make(source, chs, start, end);
-                else
-                    alter.update(chs, start, end);
-
-                sub = alter;
-            } else {
-                sub = source;
-            }
+            CharSequence sub = source;
 
             int width = firstwidth;
 
             float w = 0;
-            int here = start;
+            int here = paraStart;
 
-            int ok = start;
+            int ok = paraStart;
             float okwidth = w;
             int okascent = 0, okdescent = 0, oktop = 0, okbottom = 0;
 
-            int fit = start;
+            int fit = paraStart;
             float fitwidth = w;
             int fitascent = 0, fitdescent = 0, fittop = 0, fitbottom = 0;
 
             boolean tab = false;
 
-            int next;
-            for (int i = start; i < end; i = next) {
+            int spanEnd;
+            for (int spanStart = paraStart; spanStart < paraEnd; spanStart = spanEnd) {
                 if (spanned == null)
-                    next = end;
+                    spanEnd = paraEnd;
                 else
-                    next = spanned.nextSpanTransition(i, end,
-                                                      MetricAffectingSpan.
-                                                      class);
+                    spanEnd = spanned.nextSpanTransition(spanStart, paraEnd,
+                            MetricAffectingSpan.class);
+
+                int spanLen = spanEnd - spanStart;
+                int startInPara = spanStart - paraStart;
+                int endInPara = spanEnd - paraStart;
 
                 if (spanned == null) {
-                    paint.getTextWidths(sub, i, next, widths);
-                    System.arraycopy(widths, 0, widths,
-                                     end - start + (i - start), next - i);
-
-                    paint.getFontMetricsInt(fm);
+                    measured.addStyleRun(paint, spanLen, fm);
                 } else {
-                    mWorkPaint.baselineShift = 0;
-
-                    Styled.getTextWidths(paint, mWorkPaint,
-                                         spanned, i, next,
-                                         widths, fm);
-                    System.arraycopy(widths, 0, widths,
-                                     end - start + (i - start), next - i);
-
-                    if (mWorkPaint.baselineShift < 0) {
-                        fm.ascent += mWorkPaint.baselineShift;
-                        fm.top += mWorkPaint.baselineShift;
-                    } else {
-                        fm.descent += mWorkPaint.baselineShift;
-                        fm.bottom += mWorkPaint.baselineShift;
-                    }
+                    MetricAffectingSpan[] spans =
+                        spanned.getSpans(spanStart, spanEnd, MetricAffectingSpan.class);
+                    measured.addStyleRun(paint, spans, spanLen, fm);
                 }
 
                 int fmtop = fm.top;
@@ -344,27 +241,17 @@
                 int fmascent = fm.ascent;
                 int fmdescent = fm.descent;
 
-                if (false) {
-                    StringBuilder sb = new StringBuilder();
-                    for (int j = i; j < next; j++) {
-                        sb.append(widths[j - start + (end - start)]);
-                        sb.append(' ');
-                    }
-
-                    Log.e("text", sb.toString());
-                }
-
-                for (int j = i; j < next; j++) {
-                    char c = chs[j - start];
+                for (int j = spanStart; j < spanEnd; j++) {
+                    char c = chs[j - paraStart];
                     float before = w;
 
                     if (c == '\n') {
                         ;
                     } else if (c == '\t') {
-                        w = Layout.nextTab(sub, start, end, w, null);
+                        w = Layout.nextTab(sub, paraStart, paraEnd, w, null);
                         tab = true;
-                    } else if (c >= 0xD800 && c <= 0xDFFF && j + 1 < next) {
-                        int emoji = Character.codePointAt(chs, j - start);
+                    } else if (c >= 0xD800 && c <= 0xDFFF && j + 1 < spanEnd) {
+                        int emoji = Character.codePointAt(chs, j - paraStart);
 
                         if (emoji >= MIN_EMOJI && emoji <= MAX_EMOJI) {
                             Bitmap bm = EMOJI_FACTORY.
@@ -387,13 +274,13 @@
                                 tab = true;
                                 j++;
                             } else {
-                                w += widths[j - start + (end - start)];
+                                w += widths[j - paraStart];
                             }
                         } else {
-                            w += widths[j - start + (end - start)];
+                            w += widths[j - paraStart];
                         }
                     } else {
-                        w += widths[j - start + (end - start)];
+                        w += widths[j - paraStart];
                     }
 
                     // Log.e("text", "was " + before + " now " + w + " after " + c + " within " + width);
@@ -429,12 +316,12 @@
 
                         if (c == ' ' || c == '\t' ||
                             ((c == '.'  || c == ',' || c == ':' || c == ';') &&
-                             (j - 1 < here || !Character.isDigit(chs[j - 1 - start])) &&
-                             (j + 1 >= next || !Character.isDigit(chs[j + 1 - start]))) ||
+                             (j - 1 < here || !Character.isDigit(chs[j - 1 - paraStart])) &&
+                             (j + 1 >= spanEnd || !Character.isDigit(chs[j + 1 - paraStart]))) ||
                             ((c == '/' || c == '-') &&
-                             (j + 1 >= next || !Character.isDigit(chs[j + 1 - start]))) ||
+                             (j + 1 >= spanEnd || !Character.isDigit(chs[j + 1 - paraStart]))) ||
                             (c >= FIRST_CJK && isIdeographic(c, true) &&
-                             j + 1 < next && isIdeographic(chs[j + 1 - start], false))) {
+                             j + 1 < spanEnd && isIdeographic(chs[j + 1 - paraStart], false))) {
                             okwidth = w;
                             ok = j + 1;
 
@@ -451,7 +338,7 @@
                         if (ok != here) {
                             // Log.e("text", "output ok " + here + " to " +ok);
 
-                            while (ok < next && chs[ok - start] == ' ') {
+                            while (ok < spanEnd && chs[ok - paraStart] == ' ') {
                                 ok++;
                             }
 
@@ -461,9 +348,9 @@
                                     v,
                                     spacingmult, spacingadd, chooseht,
                                     choosehtv, fm, tab,
-                                    needMultiply, start, chdirs, dir, easy,
+                                    needMultiply, paraStart, chdirs, dir, easy,
                                     ok == bufend, includepad, trackpad,
-                                    widths, start, end - start,
+                                    chs, widths, here - paraStart,
                                     where, ellipsizedWidth, okwidth,
                                     paint);
 
@@ -487,7 +374,7 @@
                         if (ok != here) {
                             // Log.e("text", "output ok " + here + " to " +ok);
 
-                            while (ok < next && chs[ok - start] == ' ') {
+                            while (ok < spanEnd && chs[ok - paraStart] == ' ') {
                                 ok++;
                             }
 
@@ -497,9 +384,9 @@
                                     v,
                                     spacingmult, spacingadd, chooseht,
                                     choosehtv, fm, tab,
-                                    needMultiply, start, chdirs, dir, easy,
+                                    needMultiply, paraStart, chdirs, dir, easy,
                                     ok == bufend, includepad, trackpad,
-                                    widths, start, end - start,
+                                    chs, widths, here - paraStart,
                                     where, ellipsizedWidth, okwidth,
                                     paint);
 
@@ -513,18 +400,19 @@
                                     v,
                                     spacingmult, spacingadd, chooseht,
                                     choosehtv, fm, tab,
-                                    needMultiply, start, chdirs, dir, easy,
+                                    needMultiply, paraStart, chdirs, dir, easy,
                                     fit == bufend, includepad, trackpad,
-                                    widths, start, end - start,
+                                    chs, widths, here - paraStart,
                                     where, ellipsizedWidth, fitwidth,
                                     paint);
 
                             here = fit;
                         } else {
                             // Log.e("text", "output one " + here + " to " +(here + 1));
-                            measureText(paint, mWorkPaint,
-                                        source, here, here + 1, fm, tab,
-                                        null);
+                            // XXX not sure why the existing fm wasn't ok.
+                            // measureText(paint, mWorkPaint,
+                            //             source, here, here + 1, fm, tab,
+                            //             null);
 
                             v = out(source,
                                     here, here+1,
@@ -533,18 +421,18 @@
                                     v,
                                     spacingmult, spacingadd, chooseht,
                                     choosehtv, fm, tab,
-                                    needMultiply, start, chdirs, dir, easy,
+                                    needMultiply, paraStart, chdirs, dir, easy,
                                     here + 1 == bufend, includepad,
                                     trackpad,
-                                    widths, start, end - start,
+                                    chs, widths, here - paraStart,
                                     where, ellipsizedWidth,
-                                    widths[here - start], paint);
+                                    widths[here - paraStart], paint);
 
                             here = here + 1;
                         }
 
-                        if (here < i) {
-                            j = next = here; // must remeasure
+                        if (here < spanStart) {
+                            j = spanEnd = here; // must remeasure
                         } else {
                             j = here - 1;    // continue looping
                         }
@@ -561,7 +449,7 @@
                 }
             }
 
-            if (end != here) {
+            if (paraEnd != here) {
                 if ((fittop | fitbottom | fitdescent | fitascent) == 0) {
                     paint.getFontMetricsInt(fm);
 
@@ -574,20 +462,20 @@
                 // Log.e("text", "output rest " + here + " to " + end);
 
                 v = out(source,
-                        here, end, fitascent, fitdescent,
+                        here, paraEnd, fitascent, fitdescent,
                         fittop, fitbottom,
                         v,
                         spacingmult, spacingadd, chooseht,
                         choosehtv, fm, tab,
-                        needMultiply, start, chdirs, dir, easy,
-                        end == bufend, includepad, trackpad,
-                        widths, start, end - start,
+                        needMultiply, paraStart, chdirs, dir, easy,
+                        paraEnd == bufend, includepad, trackpad,
+                        chs, widths, here - paraStart,
                         where, ellipsizedWidth, w, paint);
             }
 
-            start = end;
+            paraStart = paraEnd;
 
-            if (end == bufend)
+            if (paraEnd == bufend)
                 break;
         }
 
@@ -602,9 +490,9 @@
                     v,
                     spacingmult, spacingadd, null,
                     null, fm, false,
-                    needMultiply, bufend, chdirs, DEFAULT_DIR, true,
+                    needMultiply, bufend, null, DEFAULT_DIR, true,
                     true, includepad, trackpad,
-                    widths, bufstart, 0,
+                    null, null, bufstart,
                     where, ellipsizedWidth, 0, paint);
         }
     }
@@ -714,28 +602,6 @@
     }
 */
 
-    private static int getFit(TextPaint paint,
-                              TextPaint workPaint,
-                       CharSequence text, int start, int end,
-                       float wid) {
-        int high = end + 1, low = start - 1, guess;
-
-        while (high - low > 1) {
-            guess = (high + low) / 2;
-
-            if (measureText(paint, workPaint,
-                            text, start, guess, null, true, null) > wid)
-                high = guess;
-            else
-                low = guess;
-        }
-
-        if (low < start)
-            return start;
-        else
-            return low;
-    }
-
     private int out(CharSequence text, int start, int end,
                       int above, int below, int top, int bottom, int v,
                       float spacingmult, float spacingadd,
@@ -744,7 +610,7 @@
                       boolean needMultiply, int pstart, byte[] chdirs,
                       int dir, boolean easy, boolean last,
                       boolean includepad, boolean trackpad,
-                      float[] widths, int widstart, int widoff,
+                      char[] chs, float[] widths, int widstart,
                       TextUtils.TruncateAt ellipsize, float ellipsiswidth,
                       float textwidth, TextPaint paint) {
         int j = mLineCount;
@@ -752,8 +618,6 @@
         int want = off + mColumns + TOP;
         int[] lines = mLines;
 
-        // Log.e("text", "line " + start + " to " + end + (last ? "===" : ""));
-
         if (want >= lines.length) {
             int nlen = ArrayUtils.idealIntArraySize(want + 1);
             int[] grow = new int[nlen];
@@ -840,122 +704,12 @@
         if (easy) {
             mLineDirections[j] = linedirs;
         } else {
-            int startOff = start - pstart;
-            int baseLevel = dir == DIR_LEFT_TO_RIGHT ? 0 : 1;
-            int curLevel = chdirs[startOff];
-            int minLevel = curLevel;
-            int runCount = 1;
-            for (int i = start + 1; i < end; ++i) {
-                int level = chdirs[i - pstart];
-                if (level != curLevel) {
-                    curLevel = level;
-                    ++runCount;
-                }
-            }
-
-            // add final run for trailing counter-directional whitespace
-            int visEnd = end;
-            if ((curLevel & 1) != (baseLevel & 1)) {
-                // look for visible end
-                while (--visEnd >= start) {
-                    char ch = text.charAt(visEnd);
-
-                    if (ch == '\n') {
-                        --visEnd;
-                        break;
-                    }
-
-                    if (ch != ' ' && ch != '\t') {
-                        break;
-                    }
-                }
-                ++visEnd;
-                if (visEnd != end) {
-                    ++runCount;
-                }
-            }
-
-            if (runCount == 1 && minLevel == baseLevel) {
-                if ((minLevel & 1) != 0) {
-                    linedirs = DIRS_ALL_RIGHT_TO_LEFT;
-                }
-                // we're done, only one run on this line
-            } else {
-                int[] ld = new int[runCount * 2];
-                int maxLevel = minLevel;
-                int levelBits = minLevel << RUN_LEVEL_SHIFT;
-                {
-                    // Start of first pair is always 0, we write
-                    // length then start at each new run, and the
-                    // last run length after we're done.
-                    int n = 1;
-                    int prev = start;
-                    curLevel = minLevel;
-                    for (int i = start; i < visEnd; ++i) {
-                        int level = chdirs[i - pstart];
-                        if (level != curLevel) {
-                            curLevel = level;
-                            if (level > maxLevel) {
-                                maxLevel = level;
-                            } else if (level < minLevel) {
-                                minLevel = level;
-                            }
-                            // XXX ignore run length limit of 2^RUN_LEVEL_SHIFT
-                            ld[n++] = (i - prev) | levelBits;
-                            ld[n++] = i - start;
-                            levelBits = curLevel << RUN_LEVEL_SHIFT;
-                            prev = i;
-                        }
-                    }
-                    ld[n] = (visEnd - prev) | levelBits;
-                    if (visEnd < end) {
-                        ld[++n] = visEnd - start;
-                        ld[++n] = (end - visEnd) | (baseLevel << RUN_LEVEL_SHIFT);
-                    }
-                }
-
-                // See if we need to swap any runs.
-                // If the min level run direction doesn't match the base
-                // direction, we always need to swap (at this point
-                // we have more than one run).
-                // Otherwise, we don't need to swap the lowest level.
-                // Since there are no logically adjacent runs at the same
-                // level, if the max level is the same as the (new) min
-                // level, we have a series of alternating levels that
-                // is already in order, so there's no more to do.
-                //
-                boolean swap;
-                if ((minLevel & 1) == baseLevel) {
-                    minLevel += 1;
-                    swap = maxLevel > minLevel;
-                } else {
-                    swap = runCount > 1;
-                }
-                if (swap) {
-                    for (int level = maxLevel - 1; level >= minLevel; --level) {
-                        for (int i = 0; i < ld.length; i += 2) {
-                            if (chdirs[startOff + ld[i]] >= level) {
-                                int e = i + 2;
-                                while (e < ld.length && chdirs[startOff + ld[e]] >= level) {
-                                    e += 2;
-                                }
-                                for (int low = i, hi = e - 2; low < hi; low += 2, hi -= 2) {
-                                    int x = ld[low]; ld[low] = ld[hi]; ld[hi] = x;
-                                    x = ld[low+1]; ld[low+1] = ld[hi+1]; ld[hi+1] = x;
-                                }
-                                i = e + 2;
-                            }
-                        }
-                    }
-                }
-                linedirs = new Directions(ld);
-            }
-
-            mLineDirections[j] = linedirs;
+            mLineDirections[j] = AndroidBidi.directions(dir, chdirs, widstart, chs,
+                    widstart, end - start);
 
             // If ellipsize is in marquee mode, do not apply ellipsis on the first line
             if (ellipsize != null && (ellipsize != TextUtils.TruncateAt.MARQUEE || j != 0)) {
-                calculateEllipsis(start, end, widths, widstart, widoff,
+                calculateEllipsis(start, end, widths, widstart,
                                   ellipsiswidth, ellipsize, j,
                                   textwidth, paint);
             }
@@ -966,7 +720,7 @@
     }
 
     private void calculateEllipsis(int linestart, int lineend,
-                                   float[] widths, int widstart, int widoff,
+                                   float[] widths, int widstart,
                                    float avail, TextUtils.TruncateAt where,
                                    int line, float textwidth, TextPaint paint) {
         int len = lineend - linestart;
@@ -986,7 +740,7 @@
             int i;
 
             for (i = len; i >= 0; i--) {
-                float w = widths[i - 1 + linestart - widstart + widoff];
+                float w = widths[i - 1 + linestart - widstart];
 
                 if (w + sum + ellipsiswid > avail) {
                     break;
@@ -1002,7 +756,7 @@
             int i;
 
             for (i = 0; i < len; i++) {
-                float w = widths[i + linestart - widstart + widoff];
+                float w = widths[i + linestart - widstart];
 
                 if (w + sum + ellipsiswid > avail) {
                     break;
@@ -1019,7 +773,7 @@
 
             float ravail = (avail - ellipsiswid) / 2;
             for (right = len; right >= 0; right--) {
-                float w = widths[right - 1 + linestart - widstart + widoff];
+                float w = widths[right - 1 + linestart - widstart];
 
                 if (w + rsum > ravail) {
                     break;
@@ -1030,7 +784,7 @@
 
             float lavail = avail - ellipsiswid - rsum;
             for (left = 0; left < right; left++) {
-                float w = widths[left + linestart - widstart + widoff];
+                float w = widths[left + linestart - widstart];
 
                 if (w + lsum > lavail) {
                     break;
@@ -1047,7 +801,7 @@
         mLines[mColumns * line + ELLIPSIS_COUNT] = ellipsisCount;
     }
 
-    // Override the baseclass so we can directly access our members,
+    // Override the base class so we can directly access our members,
     // rather than relying on member functions.
     // The logic mirrors that of Layout.getLineForVertical
     // FIXME: It may be faster to do a linear search for layouts without many lines.
@@ -1156,10 +910,8 @@
     private static final char FIRST_RIGHT_TO_LEFT = '\u0590';
 
     /*
-     * These are reused across calls to generate()
+     * This is reused across calls to generate()
      */
-    private byte[] mChdirs;
-    private char[] mChs;
-    private float[] mWidths;
+    private MeasuredText mMeasured;
     private Paint.FontMetricsInt mFontMetricsInt = new Paint.FontMetricsInt();
 }
diff --git a/core/java/android/text/Styled.java b/core/java/android/text/Styled.java
deleted file mode 100644
index 513b2cd..0000000
--- a/core/java/android/text/Styled.java
+++ /dev/null
@@ -1,434 +0,0 @@
-/*
- * Copyright (C) 2006 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.
- */
-package android.text;
-
-import android.graphics.Canvas;
-import android.graphics.Paint;
-import android.text.style.CharacterStyle;
-import android.text.style.MetricAffectingSpan;
-import android.text.style.ReplacementSpan;
-
-/**
- * This class provides static methods for drawing and measuring styled text,
- * like {@link android.text.Spanned} object with
- * {@link android.text.style.ReplacementSpan}.
- *
- * @hide
- */
-public class Styled
-{
-    /**
-     * Draws and/or measures a uniform run of text on a single line. No span of
-     * interest should start or end in the middle of this run (if not
-     * drawing, character spans that don't affect metrics can be ignored).
-     * Neither should the run direction change in the middle of the run.
-     *
-     * <p>The x position is the leading edge of the text. In a right-to-left
-     * paragraph, this will be to the right of the text to be drawn. Paint
-     * should not have an Align value other than LEFT or positioning will get
-     * confused.
-     *
-     * <p>On return, workPaint will reflect the original paint plus any
-     * modifications made by character styles on the run.
-     *
-     * <p>The returned width is signed and will be < 0 if the paragraph
-     * direction is right-to-left.
-     */
-    private static float drawUniformRun(Canvas canvas,
-                              Spanned text, int start, int end,
-                              int dir, boolean runIsRtl,
-                              float x, int top, int y, int bottom,
-                              Paint.FontMetricsInt fmi,
-                              TextPaint paint,
-                              TextPaint workPaint,
-                              boolean needWidth) {
-
-        boolean haveWidth = false;
-        float ret = 0;
-        CharacterStyle[] spans = text.getSpans(start, end, CharacterStyle.class);
-
-        ReplacementSpan replacement = null;
-
-        // XXX: This shouldn't be modifying paint, only workPaint.
-        // However, the members belonging to TextPaint should have default
-        // values anyway.  Better to ensure this in the Layout constructor.
-        paint.bgColor = 0;
-        paint.baselineShift = 0;
-        workPaint.set(paint);
-
-		if (spans.length > 0) {
-			for (int i = 0; i < spans.length; i++) {
-				CharacterStyle span = spans[i];
-
-				if (span instanceof ReplacementSpan) {
-					replacement = (ReplacementSpan)span;
-				}
-				else {
-					span.updateDrawState(workPaint);
-				}
-			}
-		}
-
-        if (replacement == null) {
-            CharSequence tmp;
-            int tmpstart, tmpend;
-
-            if (runIsRtl) {
-                tmp = TextUtils.getReverse(text, start, end);
-                tmpstart = 0;
-                // XXX: assumes getReverse doesn't change the length of the text
-                tmpend = end - start;
-            } else {
-                tmp = text;
-                tmpstart = start;
-                tmpend = end;
-            }
-
-            if (fmi != null) {
-                workPaint.getFontMetricsInt(fmi);
-            }
-
-            if (canvas != null) {
-                if (workPaint.bgColor != 0) {
-                    int c = workPaint.getColor();
-                    Paint.Style s = workPaint.getStyle();
-                    workPaint.setColor(workPaint.bgColor);
-                    workPaint.setStyle(Paint.Style.FILL);
-
-                    if (!haveWidth) {
-                        ret = workPaint.measureText(tmp, tmpstart, tmpend);
-                        haveWidth = true;
-                    }
-
-                    if (dir == Layout.DIR_RIGHT_TO_LEFT)
-                        canvas.drawRect(x - ret, top, x, bottom, workPaint);
-                    else
-                        canvas.drawRect(x, top, x + ret, bottom, workPaint);
-
-                    workPaint.setStyle(s);
-                    workPaint.setColor(c);
-                }
-
-                if (dir == Layout.DIR_RIGHT_TO_LEFT) {
-                    if (!haveWidth) {
-                        ret = workPaint.measureText(tmp, tmpstart, tmpend);
-                        haveWidth = true;
-                    }
-
-                    canvas.drawText(tmp, tmpstart, tmpend,
-                                    x - ret, y + workPaint.baselineShift, workPaint);
-                } else {
-                    if (needWidth) {
-                        if (!haveWidth) {
-                            ret = workPaint.measureText(tmp, tmpstart, tmpend);
-                            haveWidth = true;
-                        }
-                    }
-
-                    canvas.drawText(tmp, tmpstart, tmpend,
-                                    x, y + workPaint.baselineShift, workPaint);
-                }
-            } else {
-                if (needWidth && !haveWidth) {
-                    ret = workPaint.measureText(tmp, tmpstart, tmpend);
-                    haveWidth = true;
-                }
-            }
-        } else {
-            ret = replacement.getSize(workPaint, text, start, end, fmi);
-
-            if (canvas != null) {
-                if (dir == Layout.DIR_RIGHT_TO_LEFT)
-                    replacement.draw(canvas, text, start, end,
-                                     x - ret, top, y, bottom, workPaint);
-                else
-                    replacement.draw(canvas, text, start, end,
-                                     x, top, y, bottom, workPaint);
-            }
-        }
-
-        if (dir == Layout.DIR_RIGHT_TO_LEFT)
-            return -ret;
-        else
-            return ret;
-    }
-
-    /**
-     * Returns the advance widths for a uniform left-to-right run of text with
-     * no style changes in the middle of the run. If any style is replacement
-     * text, the first character will get the width of the replacement and the
-     * remaining characters will get a width of 0.
-     * 
-     * @param paint the paint, will not be modified
-     * @param workPaint a paint to modify; on return will reflect the original
-     *        paint plus the effect of all spans on the run
-     * @param text the text
-     * @param start the start of the run
-     * @param end the limit of the run
-     * @param widths array to receive the advance widths of the characters. Must
-     *        be at least a large as (end - start).
-     * @param fmi FontMetrics information; can be null
-     * @return the actual number of widths returned
-     */
-    public static int getTextWidths(TextPaint paint,
-                                    TextPaint workPaint,
-                                    Spanned text, int start, int end,
-                                    float[] widths, Paint.FontMetricsInt fmi) {
-        MetricAffectingSpan[] spans =
-            text.getSpans(start, end, MetricAffectingSpan.class);
-
-		ReplacementSpan replacement = null;
-        workPaint.set(paint);
-		
-		for (int i = 0; i < spans.length; i++) {
-			MetricAffectingSpan span = spans[i];
-			if (span instanceof ReplacementSpan) {
-				replacement = (ReplacementSpan)span;
-			}
-			else {
-				span.updateMeasureState(workPaint);
-			}
-		}
-	
-        if (replacement == null) {
-            workPaint.getFontMetricsInt(fmi);
-            workPaint.getTextWidths(text, start, end, widths);
-        } else {
-            int wid = replacement.getSize(workPaint, text, start, end, fmi);
-
-            if (end > start) {
-                widths[0] = wid;
-                for (int i = start + 1; i < end; i++)
-                    widths[i - start] = 0;
-            }
-        }
-        return end - start;
-    }
-
-    /**
-     * Renders and/or measures a directional run of text on a single line.
-     * Unlike {@link #drawUniformRun}, this can render runs that cross style
-     * boundaries.  Returns the signed advance width, if requested.
-     *
-     * <p>The x position is the leading edge of the text. In a right-to-left
-     * paragraph, this will be to the right of the text to be drawn. Paint
-     * should not have an Align value other than LEFT or positioning will get
-     * confused.
-     *
-     * <p>This optimizes for unstyled text and so workPaint might not be
-     * modified by this call.
-     *
-     * <p>The returned advance width will be < 0 if the paragraph
-     * direction is right-to-left.
-     */
-    private static float drawDirectionalRun(Canvas canvas,
-                                 CharSequence text, int start, int end,
-                                 int dir, boolean runIsRtl,
-                                 float x, int top, int y, int bottom,
-                                 Paint.FontMetricsInt fmi,
-                                 TextPaint paint,
-                                 TextPaint workPaint,
-                                 boolean needWidth) {
-
-        // XXX: It looks like all calls to this API match dir and runIsRtl, so
-        // having both parameters is redundant and confusing.
-
-        // fast path for unstyled text
-        if (!(text instanceof Spanned)) {
-            float ret = 0;
-
-            if (runIsRtl) {
-                CharSequence tmp = TextUtils.getReverse(text, start, end);
-                // XXX: this assumes getReverse doesn't tweak the length of
-                // the text
-                int tmpend = end - start;
-
-                if (canvas != null || needWidth)
-                    ret = paint.measureText(tmp, 0, tmpend);
-
-                if (canvas != null)
-                    canvas.drawText(tmp, 0, tmpend,
-                                    x - ret, y, paint);
-            } else {
-                if (needWidth)
-                    ret = paint.measureText(text, start, end);
-
-                if (canvas != null)
-                    canvas.drawText(text, start, end, x, y, paint);
-            }
-
-            if (fmi != null) {
-                paint.getFontMetricsInt(fmi);
-            }
-
-            return ret * dir;   // Layout.DIR_RIGHT_TO_LEFT == -1
-        }
-        
-        float ox = x;
-        int minAscent = 0, maxDescent = 0, minTop = 0, maxBottom = 0;
-
-        Spanned sp = (Spanned) text;
-        Class<?> division;
-
-        if (canvas == null)
-            division = MetricAffectingSpan.class;
-        else
-            division = CharacterStyle.class;
-
-        int next;
-        for (int i = start; i < end; i = next) {
-            next = sp.nextSpanTransition(i, end, division);
-
-            // XXX: if dir and runIsRtl were not the same, this would draw
-            // spans in the wrong order, but no one appears to call it this
-            // way.
-            x += drawUniformRun(canvas, sp, i, next, dir, runIsRtl,
-                  x, top, y, bottom, fmi, paint, workPaint,
-                  needWidth || next != end);
-
-            if (fmi != null) {
-                if (fmi.ascent < minAscent)
-                    minAscent = fmi.ascent;
-                if (fmi.descent > maxDescent)
-                    maxDescent = fmi.descent;
-
-                if (fmi.top < minTop)
-                    minTop = fmi.top;
-                if (fmi.bottom > maxBottom)
-                    maxBottom = fmi.bottom;
-            }
-        }
-
-        if (fmi != null) {
-            if (start == end) {
-                paint.getFontMetricsInt(fmi);
-            } else {
-                fmi.ascent = minAscent;
-                fmi.descent = maxDescent;
-                fmi.top = minTop;
-                fmi.bottom = maxBottom;
-            }
-        }
-
-        return x - ox;
-    }
-
-    /**
-     * Draws a unidirectional run of text on a single line, and optionally
-     * returns the signed advance.  Unlike drawDirectionalRun, the paragraph
-     * direction and run direction can be different.
-     */
-    /* package */ static float drawText(Canvas canvas,
-                                       CharSequence text, int start, int end,
-                                       int dir, boolean runIsRtl,
-                                       float x, int top, int y, int bottom,
-                                       TextPaint paint,
-                                       TextPaint workPaint,
-                                       boolean needWidth) {
-        // XXX this logic is (dir == DIR_LEFT_TO_RIGHT) == runIsRtl
-        if ((dir == Layout.DIR_RIGHT_TO_LEFT && !runIsRtl) ||
-            (runIsRtl && dir == Layout.DIR_LEFT_TO_RIGHT)) {
-            // TODO: this needs the real direction
-            float ch = drawDirectionalRun(null, text, start, end,
-                    Layout.DIR_LEFT_TO_RIGHT, false, 0, 0, 0, 0, null, paint,
-                    workPaint, true);
-
-            ch *= dir;  // DIR_RIGHT_TO_LEFT == -1
-            drawDirectionalRun(canvas, text, start, end, -dir,
-                    runIsRtl, x + ch, top, y, bottom, null, paint,
-                    workPaint, true);
-
-            return ch;
-        }
-
-        return drawDirectionalRun(canvas, text, start, end, dir, runIsRtl,
-                       x, top, y, bottom, null, paint, workPaint,
-                       needWidth);
-    }
-    
-    /**
-     * Draws a run of text on a single line, with its
-     * origin at (x,y), in the specified Paint. The origin is interpreted based
-     * on the Align setting in the Paint.
-     *
-     * This method considers style information in the text (e.g. even when text
-     * is an instance of {@link android.text.Spanned}, this method correctly
-     * draws the text). See also
-     * {@link android.graphics.Canvas#drawText(CharSequence, int, int, float,
-     * float, Paint)} and
-     * {@link android.graphics.Canvas#drawRect(float, float, float, float,
-     * Paint)}.
-     * 
-     * @param canvas The target canvas
-     * @param text The text to be drawn
-     * @param start The index of the first character in text to draw
-     * @param end (end - 1) is the index of the last character in text to draw
-     * @param direction The direction of the text. This must be
-     *        {@link android.text.Layout#DIR_LEFT_TO_RIGHT} or
-     *        {@link android.text.Layout#DIR_RIGHT_TO_LEFT}.
-     * @param x The x-coordinate of origin for where to draw the text
-     * @param top The top side of the rectangle to be drawn
-     * @param y The y-coordinate of origin for where to draw the text
-     * @param bottom The bottom side of the rectangle to be drawn
-     * @param paint The main {@link TextPaint} object.
-     * @param workPaint The {@link TextPaint} object used for temporal
-     *        workspace.
-     * @param needWidth If true, this method returns the width of drawn text
-     * @return Width of the drawn text if needWidth is true
-     */
-    public static float drawText(Canvas canvas,
-                                 CharSequence text, int start, int end,
-                                 int direction,
-                                 float x, int top, int y, int bottom,
-                                 TextPaint paint,
-                                 TextPaint workPaint,
-                                 boolean needWidth) {
-        // For safety.
-        direction = direction >= 0 ? Layout.DIR_LEFT_TO_RIGHT
-                : Layout.DIR_RIGHT_TO_LEFT;
-
-        // Hide runIsRtl parameter since it is meaningless for external
-        // developers.
-        // XXX: the runIsRtl probably ought to be the same as direction, then
-        // this could draw rtl text.
-        return drawText(canvas, text, start, end, direction, false,
-                        x, top, y, bottom, paint, workPaint, needWidth);
-    }
-    
-    /**
-     * Returns the width of a run of left-to-right text on a single line,
-     * considering style information in the text (e.g. even when text is an
-     * instance of {@link android.text.Spanned}, this method correctly measures
-     * the width of the text).
-     * 
-     * @param paint the main {@link TextPaint} object; will not be modified
-     * @param workPaint the {@link TextPaint} object available for modification;
-     *        will not necessarily be used
-     * @param text the text to measure
-     * @param start the index of the first character to start measuring
-     * @param end 1 beyond the index of the last character to measure
-     * @param fmi FontMetrics information; can be null
-     * @return The width of the text
-     */
-    public static float measureText(TextPaint paint,
-                                    TextPaint workPaint,
-                                    CharSequence text, int start, int end,
-                                    Paint.FontMetricsInt fmi) {
-        return drawDirectionalRun(null, text, start, end,
-                       Layout.DIR_LEFT_TO_RIGHT, false,
-                       0, 0, 0, 0, fmi, paint, workPaint, true);
-    }
-}
diff --git a/core/java/android/text/TextLine.java b/core/java/android/text/TextLine.java
new file mode 100644
index 0000000..8ab481b
--- /dev/null
+++ b/core/java/android/text/TextLine.java
@@ -0,0 +1,1053 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+package android.text;
+
+import com.android.internal.util.ArrayUtils;
+
+import android.graphics.Bitmap;
+import android.graphics.Canvas;
+import android.graphics.Paint;
+import android.graphics.RectF;
+import android.graphics.Paint.FontMetricsInt;
+import android.icu.text.ArabicShaping;
+import android.text.Layout.Directions;
+import android.text.style.CharacterStyle;
+import android.text.style.MetricAffectingSpan;
+import android.text.style.ReplacementSpan;
+import android.text.style.TabStopSpan;
+import android.util.Log;
+
+/**
+ * Represents a line of styled text, for measuring in visual order and
+ * for rendering.
+ *
+ * <p>Get a new instance using obtain(), and when finished with it, return it
+ * to the pool using recycle().
+ *
+ * <p>Call set to prepare the instance for use, then either draw, measure,
+ * metrics, or caretToLeftRightOf.
+ *
+ * @hide
+ */
+class TextLine {
+    private TextPaint mPaint;
+    private CharSequence mText;
+    private int mStart;
+    private int mLen;
+    private int mDir;
+    private Directions mDirections;
+    private boolean mHasTabs;
+    private TabStopSpan[] mTabs;
+
+    private char[] mChars;
+    private boolean mCharsValid;
+    private Spanned mSpanned;
+    private TextPaint mWorkPaint = new TextPaint();
+    private int mPreppedIndex;
+    private int mPreppedLimit;
+
+    private static TextLine[] cached = new TextLine[3];
+
+    /**
+     * Returns a new TextLine from the shared pool.
+     *
+     * @return an uninitialized TextLine
+     */
+    static TextLine obtain() {
+        TextLine tl;
+        synchronized (cached) {
+            for (int i = cached.length; --i >= 0;) {
+                if (cached[i] != null) {
+                    tl = cached[i];
+                    cached[i] = null;
+                    return tl;
+                }
+            }
+        }
+        tl = new TextLine();
+        Log.e("TLINE", "new: " + tl);
+        return tl;
+    }
+
+    /**
+     * Puts a TextLine back into the shared pool. Do not use this TextLine once
+     * it has been returned.
+     * @param tl the textLine
+     * @return null, as a convenience from clearing references to the provided
+     * TextLine
+     */
+    static TextLine recycle(TextLine tl) {
+        tl.mText = null;
+        tl.mPaint = null;
+        tl.mDirections = null;
+        if (tl.mLen < 250) {
+            synchronized(cached) {
+                for (int i = 0; i < cached.length; ++i) {
+                    if (cached[i] == null) {
+                        cached[i] = tl;
+                        break;
+                    }
+                }
+            }
+        }
+        return null;
+    }
+
+    /**
+     * Initializes a TextLine and prepares it for use.
+     *
+     * @param paint the base paint for the line
+     * @param text the text, can be Styled
+     * @param start the start of the line relative to the text
+     * @param limit the limit of the line relative to the text
+     * @param dir the paragraph direction of this line
+     * @param directions the directions information of this line
+     * @param hasTabs true if the line might contain tabs or emoji
+     * @param spans array of paragraph-level spans, of which only TabStopSpans
+     * are used.  Can be null.
+     */
+    void set(TextPaint paint, CharSequence text, int start, int limit, int dir,
+            Directions directions, boolean hasTabs, Object[] spans) {
+        mPaint = paint;
+        mText = text;
+        mStart = start;
+        mLen = limit - start;
+        mDir = dir;
+        mDirections = directions;
+        mHasTabs = hasTabs;
+        mSpanned = null;
+        mPreppedIndex = 0;
+        mPreppedLimit = 0;
+
+        boolean hasReplacement = false;
+        if (text instanceof Spanned) {
+            mSpanned = (Spanned) text;
+            hasReplacement = mSpanned.getSpans(start, limit,
+                    ReplacementSpan.class).length > 0;
+        }
+
+        mCharsValid = hasReplacement || hasTabs ||
+            directions != Layout.DIRS_ALL_LEFT_TO_RIGHT;
+
+        if (mCharsValid) {
+            if (mChars == null || mChars.length < mLen) {
+                mChars = new char[ArrayUtils.idealCharArraySize(mLen)];
+            }
+            TextUtils.getChars(text, start, limit, mChars, 0);
+
+            if (hasTabs) {
+                TabStopSpan[] tabs = mTabs;
+                int tabLen = 0;
+                if (mSpanned != null && spans == null) {
+                    TabStopSpan[] newTabs = mSpanned.getSpans(start, limit,
+                            TabStopSpan.class);
+                    if (tabs == null || tabs.length < newTabs.length) {
+                        tabs = newTabs;
+                    } else {
+                        for (int i = 0; i < newTabs.length; ++i) {
+                            tabs[i] = newTabs[i];
+                        }
+                    }
+                    tabLen = newTabs.length;
+                } else if (spans != null) {
+                    if (tabs == null || tabs.length < spans.length) {
+                        tabs = new TabStopSpan[spans.length];
+                    }
+                    for (int i = 0; i < spans.length; ++i) {
+                        if (spans[i] instanceof TabStopSpan) {
+                            tabs[tabLen++] = (TabStopSpan) spans[i];
+                        }
+                    }
+                }
+
+                if (tabs != null && tabLen < tabs.length){
+                    tabs[tabLen] = null;
+                }
+                mTabs = tabs;
+            }
+        }
+    }
+
+    /**
+     * Renders the TextLine.
+     *
+     * @param c the canvas to render on
+     * @param x the leading margin position
+     * @param top the top of the line
+     * @param y the baseline
+     * @param bottom the bottom of the line
+     */
+    void draw(Canvas c, float x, int top, int y, int bottom) {
+        if (!mHasTabs) {
+            if (mDirections == Layout.DIRS_ALL_LEFT_TO_RIGHT) {
+                drawRun(c, 0, 0, mLen, false, x, top, y, bottom, false);
+                return;
+            }
+            if (mDirections == Layout.DIRS_ALL_RIGHT_TO_LEFT) {
+                drawRun(c, 0, 0, mLen, true, x, top, y, bottom, false);
+                return;
+            }
+        }
+
+        float h = 0;
+        int[] runs = mDirections.mDirections;
+        RectF emojiRect = null;
+
+        int lastRunIndex = runs.length - 2;
+        for (int i = 0; i < runs.length; i += 2) {
+            int runStart = runs[i];
+            int runLimit = runStart + (runs[i+1] & Layout.RUN_LENGTH_MASK);
+            if (runLimit > mLen) {
+                runLimit = mLen;
+            }
+            boolean runIsRtl = (runs[i+1] & Layout.RUN_RTL_FLAG) != 0;
+
+            int segstart = runStart;
+            char[] chars = mChars;
+            for (int j = mHasTabs ? runStart : runLimit; j <= runLimit; j++) {
+                int codept = 0;
+                Bitmap bm = null;
+
+                if (mHasTabs && j < runLimit) {
+                    codept = mChars[j];
+                    if (codept >= 0xd800 && codept < 0xdc00 && j + 1 < runLimit) {
+                        codept = Character.codePointAt(mChars, j);
+                        if (codept >= Layout.MIN_EMOJI && codept <= Layout.MAX_EMOJI) {
+                            bm = Layout.EMOJI_FACTORY.getBitmapFromAndroidPua(codept);
+                        } else if (codept > 0xffff) {
+                            ++j;
+                            continue;
+                        }
+                    }
+                }
+
+                if (j == runLimit || codept == '\t' || bm != null) {
+                    h += drawRun(c, i, segstart, j, runIsRtl, x+h, top, y, bottom,
+                            i != lastRunIndex || j != mLen);
+
+                    if (codept == '\t') {
+                        h = mDir * nextTab(h * mDir);
+                    } else if (bm != null) {
+                        float bmAscent = ascent(j);
+                        float bitmapHeight = bm.getHeight();
+                        float scale = -bmAscent / bitmapHeight;
+                        float width = bm.getWidth() * scale;
+
+                        if (emojiRect == null) {
+                            emojiRect = new RectF();
+                        }
+                        emojiRect.set(x + h, y + bmAscent,
+                                x + h + width, y);
+                        c.drawBitmap(bm, null, emojiRect, mPaint);
+                        h += width;
+                        j++;
+                    }
+                    segstart = j + 1;
+                }
+            }
+        }
+    }
+
+    /**
+     * Returns metrics information for the entire line.
+     *
+     * @param fmi receives font metrics information, can be null
+     * @return the signed width of the line
+     */
+    float metrics(FontMetricsInt fmi) {
+        return measure(mLen, false, fmi);
+    }
+
+    /**
+     * Returns information about a position on the line.
+     *
+     * @param offset the line-relative character offset, between 0 and the
+     * line length, inclusive
+     * @param trailing true to measure the trailing edge of the character
+     * before offset, false to measure the leading edge of the character
+     * at offset.
+     * @param fmi receives metrics information about the requested
+     * character, can be null.
+     * @return the signed offset from the leading margin to the requested
+     * character edge.
+     */
+    float measure(int offset, boolean trailing, FontMetricsInt fmi) {
+        int target = trailing ? offset - 1 : offset;
+        if (target < 0) {
+            return 0;
+        }
+
+        float h = 0;
+
+        if (!mHasTabs) {
+            if (mDirections == Layout.DIRS_ALL_LEFT_TO_RIGHT) {
+                return measureRun( 0, 0, target, mLen, false, fmi);
+            }
+            if (mDirections == Layout.DIRS_ALL_RIGHT_TO_LEFT) {
+                return measureRun(0, 0, target, mLen, true, fmi);
+            }
+        }
+
+        char[] chars = mChars;
+        int[] runs = mDirections.mDirections;
+        for (int i = 0; i < runs.length; i += 2) {
+            int runStart = runs[i];
+            int runLimit = runStart + (runs[i+1] & Layout.RUN_LENGTH_MASK);
+            if (runLimit > mLen) {
+                runLimit = mLen;
+            }
+            boolean runIsRtl = (runs[i+1] & Layout.RUN_RTL_FLAG) != 0;
+
+            int segstart = runStart;
+            for (int j = mHasTabs ? runStart : runLimit; j <= runLimit; j++) {
+                int codept = 0;
+                Bitmap bm = null;
+
+                if (mHasTabs && j < runLimit) {
+                    codept = chars[j];
+                    if (codept >= 0xd800 && codept < 0xdc00 && j + 1 < runLimit) {
+                        codept = Character.codePointAt(chars, j);
+                        if (codept >= Layout.MIN_EMOJI && codept <= Layout.MAX_EMOJI) {
+                            bm = Layout.EMOJI_FACTORY.getBitmapFromAndroidPua(codept);
+                        } else if (codept > 0xffff) {
+                            ++j;
+                            continue;
+                        }
+                    }
+                }
+
+                if (j == runLimit || codept == '\t' || bm != null) {
+                    boolean inSegment = target >= segstart && target < j;
+
+                    boolean advance = (mDir == Layout.DIR_RIGHT_TO_LEFT) == runIsRtl;
+                    if (inSegment && advance) {
+                        return h += measureRun(i, segstart, offset, j, runIsRtl, fmi);
+                    }
+
+                    float w = measureRun(i, segstart, j, j, runIsRtl, fmi);
+                    h += advance ? w : -w;
+
+                    if (inSegment) {
+                        return h += measureRun(i, segstart, offset, j, runIsRtl, null);
+                    }
+
+                    if (codept == '\t') {
+                        if (offset == j) {
+                            return h;
+                        }
+                        h = mDir * nextTab(h * mDir);
+                        if (target == j) {
+                            return h;
+                        }
+                    }
+
+                    if (bm != null) {
+                        float bmAscent = ascent(j);
+                        float wid = bm.getWidth() * -bmAscent / bm.getHeight();
+                        h += mDir * wid;
+                        j++;
+                    }
+
+                    segstart = j + 1;
+                }
+            }
+        }
+
+        return h;
+    }
+
+    /**
+     * Draws a unidirectional (but possibly multi-styled) run of text.
+     *
+     * @param c the canvas to draw on
+     * @param runIndex the index of this directional run
+     * @param start the line-relative start
+     * @param limit the line-relative limit
+     * @param runIsRtl true if the run is right-to-left
+     * @param x the position of the run that is closest to the leading margin
+     * @param top the top of the line
+     * @param y the baseline
+     * @param bottom the bottom of the line
+     * @param needWidth true if the width value is required.
+     * @return the signed width of the run, based on the paragraph direction.
+     * Only valid if needWidth is true.
+     */
+    private float drawRun(Canvas c, int runIndex, int start,
+            int limit, boolean runIsRtl, float x, int top, int y, int bottom,
+            boolean needWidth) {
+
+        if ((mDir == Layout.DIR_LEFT_TO_RIGHT) == runIsRtl) {
+            float w = -measureRun(runIndex, start, limit, limit, runIsRtl, null);
+            handleRun(runIndex, start, limit, limit, runIsRtl, c, x + w, top,
+                    y, bottom, null, false, PREP_NONE);
+            return w;
+        }
+
+        return handleRun(runIndex, start, limit, limit, runIsRtl, c, x, top,
+                y, bottom, null, needWidth, PREP_NEEDED);
+    }
+
+    /**
+     * Measures a unidirectional (but possibly multi-styled) run of text.
+     *
+     * @param runIndex the run index
+     * @param start the line-relative start of the run
+     * @param offset the offset to measure to, between start and limit inclusive
+     * @param limit the line-relative limit of the run
+     * @param runIsRtl true if the run is right-to-left
+     * @param fmi receives metrics information about the requested
+     * run, can be null.
+     * @return the signed width from the start of the run to the leading edge
+     * of the character at offset, based on the run (not paragraph) direction
+     */
+    private float measureRun(int runIndex, int start,
+            int offset, int limit, boolean runIsRtl, FontMetricsInt fmi) {
+        return handleRun(runIndex, start, offset, limit, runIsRtl, null,
+                0, 0, 0, 0, fmi, true, PREP_NEEDED);
+    }
+
+    /**
+     * Prepares a run for measurement or rendering.  This ensures that any
+     * required shaping of the text in the run has been performed so that
+     * measurements reflect the shaped text.
+     *
+     * @param runIndex the run index
+     * @param start the line-relative start of the run
+     * @param limit the line-relative limit of the run
+     * @param runIsRtl true if the run is right-to-left
+     */
+    private void prepRun(int runIndex, int start, int limit,
+            boolean runIsRtl) {
+        handleRun(runIndex, start, limit, limit, runIsRtl, null, 0, 0, 0,
+                0, null, false, PREP_ONLY);
+    }
+
+    /**
+     * Walk the cursor through this line, skipping conjuncts and
+     * zero-width characters.
+     *
+     * <p>This function cannot properly walk the cursor off the ends of the line
+     * since it does not know about any shaping on the previous/following line
+     * that might affect the cursor position. Callers must either avoid these
+     * situations or handle the result specially.
+     *
+     * <p>The paint is required because the region around the cursor might not
+     * have been formatted yet, and the valid positions can depend on the glyphs
+     * used to render the text, which in turn depends on the paint.
+     *
+     * @param paint the base paint of the line
+     * @param cursor the starting position of the cursor, between 0 and the
+     * length of the line, inclusive
+     * @param toLeft true if the caret is moving to the left.
+     * @return the new offset.  If it is less than 0 or greater than the length
+     * of the line, the previous/following line should be examined to get the
+     * actual offset.
+     */
+    int getOffsetToLeftRightOf(int cursor, boolean toLeft) {
+        // 1) The caret marks the leading edge of a character. The character
+        // logically before it might be on a different level, and the active caret
+        // position is on the character at the lower level. If that character
+        // was the previous character, the caret is on its trailing edge.
+        // 2) Take this character/edge and move it in the indicated direction.
+        // This gives you a new character and a new edge.
+        // 3) This position is between two visually adjacent characters.  One of
+        // these might be at a lower level.  The active position is on the
+        // character at the lower level.
+        // 4) If the active position is on the trailing edge of the character,
+        // the new caret position is the following logical character, else it
+        // is the character.
+
+        int lineStart = 0;
+        int lineEnd = mLen;
+        boolean paraIsRtl = mDir == -1;
+        int[] runs = mDirections.mDirections;
+
+        int runIndex, runLevel = 0, runStart = lineStart, runLimit = lineEnd, newCaret = -1;
+        boolean trailing = false;
+
+        if (cursor == lineStart) {
+            runIndex = -2;
+        } else if (cursor == lineEnd) {
+            runIndex = runs.length;
+        } else {
+          // First, get information about the run containing the character with
+          // the active caret.
+          for (runIndex = 0; runIndex < runs.length; runIndex += 2) {
+            runStart = lineStart + runs[runIndex];
+            if (cursor >= runStart) {
+              runLimit = runStart + (runs[runIndex+1] & Layout.RUN_LENGTH_MASK);
+              if (runLimit > lineEnd) {
+                  runLimit = lineEnd;
+              }
+              if (cursor < runLimit) {
+                runLevel = (runs[runIndex+1] >>> Layout.RUN_LEVEL_SHIFT) &
+                    Layout.RUN_LEVEL_MASK;
+                if (cursor == runStart) {
+                  // The caret is on a run boundary, see if we should
+                  // use the position on the trailing edge of the previous
+                  // logical character instead.
+                  int prevRunIndex, prevRunLevel, prevRunStart, prevRunLimit;
+                  int pos = cursor - 1;
+                  for (prevRunIndex = 0; prevRunIndex < runs.length; prevRunIndex += 2) {
+                    prevRunStart = lineStart + runs[prevRunIndex];
+                    if (pos >= prevRunStart) {
+                      prevRunLimit = prevRunStart +
+                          (runs[prevRunIndex+1] & Layout.RUN_LENGTH_MASK);
+                      if (prevRunLimit > lineEnd) {
+                          prevRunLimit = lineEnd;
+                      }
+                      if (pos < prevRunLimit) {
+                        prevRunLevel = (runs[prevRunIndex+1] >>> Layout.RUN_LEVEL_SHIFT)
+                            & Layout.RUN_LEVEL_MASK;
+                        if (prevRunLevel < runLevel) {
+                          // Start from logically previous character.
+                          runIndex = prevRunIndex;
+                          runLevel = prevRunLevel;
+                          runStart = prevRunStart;
+                          runLimit = prevRunLimit;
+                          trailing = true;
+                          break;
+                        }
+                      }
+                    }
+                  }
+                }
+                break;
+              }
+            }
+          }
+
+          // caret might be == lineEnd.  This is generally a space or paragraph
+          // separator and has an associated run, but might be the end of
+          // text, in which case it doesn't.  If that happens, we ran off the
+          // end of the run list, and runIndex == runs.length.  In this case,
+          // we are at a run boundary so we skip the below test.
+          if (runIndex != runs.length) {
+              boolean runIsRtl = (runLevel & 0x1) != 0;
+              boolean advance = toLeft == runIsRtl;
+              if (cursor != (advance ? runLimit : runStart) || advance != trailing) {
+                  // Moving within or into the run, so we can move logically.
+                  prepRun(runIndex, runStart, runLimit, runIsRtl);
+                  newCaret = getOffsetBeforeAfter(runIndex, cursor, advance);
+                  // If the new position is internal to the run, we're at the strong
+                  // position already so we're finished.
+                  if (newCaret != (advance ? runLimit : runStart)) {
+                      return newCaret;
+                  }
+              }
+          }
+        }
+
+        // If newCaret is -1, we're starting at a run boundary and crossing
+        // into another run. Otherwise we've arrived at a run boundary, and
+        // need to figure out which character to attach to.  Note we might
+        // need to run this twice, if we cross a run boundary and end up at
+        // another run boundary.
+        while (true) {
+          boolean advance = toLeft == paraIsRtl;
+          int otherRunIndex = runIndex + (advance ? 2 : -2);
+          if (otherRunIndex >= 0 && otherRunIndex < runs.length) {
+            int otherRunStart = lineStart + runs[otherRunIndex];
+            int otherRunLimit = otherRunStart +
+            (runs[otherRunIndex+1] & Layout.RUN_LENGTH_MASK);
+            if (otherRunLimit > lineEnd) {
+                otherRunLimit = lineEnd;
+            }
+            int otherRunLevel = (runs[otherRunIndex+1] >>> Layout.RUN_LEVEL_SHIFT) &
+                Layout.RUN_LEVEL_MASK;
+            boolean otherRunIsRtl = (otherRunLevel & 1) != 0;
+
+            advance = toLeft == otherRunIsRtl;
+            if (newCaret == -1) {
+                prepRun(otherRunIndex, otherRunStart, otherRunLimit,
+                        otherRunIsRtl);
+                newCaret = getOffsetBeforeAfter(otherRunIndex,
+                        advance ? otherRunStart : otherRunLimit, advance);
+                if (newCaret == (advance ? otherRunLimit : otherRunStart)) {
+                    // Crossed and ended up at a new boundary,
+                    // repeat a second and final time.
+                    runIndex = otherRunIndex;
+                    runLevel = otherRunLevel;
+                    continue;
+                }
+                break;
+            }
+
+            // The new caret is at a boundary.
+            if (otherRunLevel < runLevel) {
+              // The strong character is in the other run.
+              newCaret = advance ? otherRunStart : otherRunLimit;
+            }
+            break;
+          }
+
+          if (newCaret == -1) {
+              // We're walking off the end of the line.  The paragraph
+              // level is always equal to or lower than any internal level, so
+              // the boundaries get the strong caret.
+              newCaret = getOffsetBeforeAfter(-1, cursor, advance);
+              break;
+          }
+
+          // Else we've arrived at the end of the line.  That's a strong position.
+          // We might have arrived here by crossing over a run with no internal
+          // breaks and dropping out of the above loop before advancing one final
+          // time, so reset the caret.
+          // Note, we use '<=' below to handle a situation where the only run
+          // on the line is a counter-directional run.  If we're not advancing,
+          // we can end up at the 'lineEnd' position but the caret we want is at
+          // the lineStart.
+          if (newCaret <= lineEnd) {
+              newCaret = advance ? lineEnd : lineStart;
+          }
+          break;
+        }
+
+        return newCaret;
+    }
+
+    /**
+     * Returns the next valid offset within this directional run, skipping
+     * conjuncts and zero-width characters.  This should not be called to walk
+     * off the end of the run.
+     *
+     * @param runIndex the run index
+     * @param offset the offset
+     * @param after true if the new offset should logically follow the provided
+     * offset
+     * @return the new offset
+     */
+    private int getOffsetBeforeAfter(int runIndex, int offset, boolean after) {
+        // XXX note currently there is no special handling of zero-width
+        // combining marks, since the only analysis involves mock shaping.
+
+        boolean offEnd = offset == (after ? mLen : 0);
+        if (runIndex >= 0 && !offEnd && mCharsValid) {
+            char[] chars = mChars;
+            if (after) {
+                int cp = Character.codePointAt(chars, offset, mLen);
+                if (cp >= 0x10000) {
+                    ++offset;
+                }
+                while (++offset < mLen && chars[offset] == '\ufeff'){}
+            } else {
+                while (--offset >= 0 && chars[offset] == '\ufeff'){}
+                int cp = Character.codePointBefore(chars, offset + 1);
+                if (cp >= 0x10000) {
+                    --offset;
+                }
+            }
+            return offset;
+        }
+
+        if (after) {
+            return TextUtils.getOffsetAfter(mText, offset + mStart) - mStart;
+        }
+        return TextUtils.getOffsetBefore(mText, offset + mStart) - mStart;
+    }
+
+    /**
+     * Utility function for measuring and rendering text.  The text must
+     * not include a tab or emoji.
+     *
+     * @param wp the working paint
+     * @param start the start of the text
+     * @param limit the limit of the text
+     * @param runIsRtl true if the run is right-to-left
+     * @param c the canvas, can be null if rendering is not needed
+     * @param x the edge of the run closest to the leading margin
+     * @param top the top of the line
+     * @param y the baseline
+     * @param bottom the bottom of the line
+     * @param fmi receives metrics information, can be null
+     * @param needWidth true if the width of the run is needed
+     * @return the signed width of the run based on the run direction; only
+     * valid if needWidth is true
+     */
+    private float handleText(TextPaint wp, int start, int limit,
+            boolean runIsRtl, Canvas c, float x, int top, int y, int bottom,
+            FontMetricsInt fmi, boolean needWidth) {
+
+        float ret = 0;
+
+        int runLen = limit - start;
+        if (needWidth || (c != null && (wp.bgColor != 0 || runIsRtl))) {
+            if (mCharsValid) {
+                ret = wp.measureText(mChars, start, runLen);
+            } else {
+                ret = wp.measureText(mText, mStart + start,
+                        mStart + start + runLen);
+            }
+        }
+
+        if (fmi != null) {
+            wp.getFontMetricsInt(fmi);
+        }
+
+        if (c != null) {
+            if (runIsRtl) {
+                x -= ret;
+            }
+
+            if (wp.bgColor != 0) {
+                int color = wp.getColor();
+                Paint.Style s = wp.getStyle();
+                wp.setColor(wp.bgColor);
+                wp.setStyle(Paint.Style.FILL);
+
+                c.drawRect(x, top, x + ret, bottom, wp);
+
+                wp.setStyle(s);
+                wp.setColor(color);
+            }
+
+            drawTextRun(c, wp, start, limit, runIsRtl, x, y + wp.baselineShift);
+        }
+
+        return runIsRtl ? -ret : ret;
+    }
+
+    /**
+     * Utility function for measuring and rendering a replacement.
+     *
+     * @param replacement the replacement
+     * @param wp the work paint
+     * @param runIndex the run index
+     * @param start the start of the run
+     * @param limit the limit of the run
+     * @param runIsRtl true if the run is right-to-left
+     * @param c the canvas, can be null if not rendering
+     * @param x the edge of the replacement closest to the leading margin
+     * @param top the top of the line
+     * @param y the baseline
+     * @param bottom the bottom of the line
+     * @param fmi receives metrics information, can be null
+     * @param needWidth true if the width of the replacement is needed
+     * @param prepFlags one of PREP_NONE, PREP_REQUIRED, or PREP_ONLY
+     * @return the signed width of the run based on the run direction; only
+     * valid if needWidth is true
+     */
+    private float handleReplacement(ReplacementSpan replacement, TextPaint wp,
+            int runIndex, int start, int limit, boolean runIsRtl, Canvas c,
+            float x, int top, int y, int bottom, FontMetricsInt fmi,
+            boolean needWidth, int prepFlags) {
+
+        float ret = 0;
+
+        // Preparation replaces the first character of the series with the
+        // object-replacement character and the remainder with zero width
+        // non-break space aka BOM.  Cursor movement code skips over the BOMs
+        // so that the replacement character is the only character 'seen'.
+        if (prepFlags != PREP_NONE && limit > start &&
+                (runIndex > mPreppedIndex ||
+                        (runIndex == mPreppedIndex && start >= mPreppedLimit))) {
+            char[] chars = mChars;
+            chars[start] = '\ufffc';
+            for (int i = start + 1; i < limit; ++i) {
+                chars[i] = '\ufeff'; // used as ZWNBS, marks positions to skip
+            }
+            mPreppedIndex = runIndex;
+            mPreppedLimit = limit;
+        }
+
+        if (prepFlags != PREP_ONLY) {
+            int textStart = mStart + start;
+            int textLimit = mStart + limit;
+
+            if (needWidth || (c != null && runIsRtl)) {
+                ret = replacement.getSize(wp, mText, textStart, textLimit, fmi);
+            }
+
+            if (c != null) {
+                if (runIsRtl) {
+                    x -= ret;
+                }
+                replacement.draw(c, mText, textStart, textLimit,
+                        x, top, y, bottom, wp);
+            }
+        }
+
+        return runIsRtl ? -ret : ret;
+    }
+
+    /**
+     * Utility function for handling a unidirectional run.  The run must not
+     * contain tabs or emoji but can contain styles.
+     *
+     * @param p the base paint
+     * @param runIndex the run index
+     * @param start the line-relative start of the run
+     * @param offset the offset to measure to, between start and limit inclusive
+     * @param limit the limit of the run
+     * @param runIsRtl true if the run is right-to-left
+     * @param c the canvas, can be null
+     * @param x the end of the run closest to the leading margin
+     * @param top the top of the line
+     * @param y the baseline
+     * @param bottom the bottom of the line
+     * @param fmi receives metrics information, can be null
+     * @param needWidth true if the width is required
+     * @param prepFlags one of PREP_NONE, PREP_REQUIRED, or PREP_ONLY
+     * @return the signed width of the run based on the run direction; only
+     * valid if needWidth is true
+     */
+    private float handleRun(int runIndex, int start, int offset,
+            int limit, boolean runIsRtl, Canvas c, float x, int top, int y,
+            int bottom, FontMetricsInt fmi, boolean needWidth, int prepFlags) {
+
+        // Shaping needs to take into account context up to metric boundaries,
+        // but rendering needs to take into account character style boundaries.
+        // So we iterate through metric runs, shape using the initial
+        // paint (the same typeface is used up to the next metric boundary),
+        // then within each metric run iterate through character style runs.
+        float ox = x;
+        for (int i = start, inext; i < offset; i = inext) {
+            TextPaint wp = mWorkPaint;
+            wp.set(mPaint);
+
+            int mnext;
+            if (mSpanned == null) {
+                inext = limit;
+                mnext = offset;
+            } else {
+                inext = mSpanned.nextSpanTransition(mStart + i, mStart + limit,
+                        MetricAffectingSpan.class) - mStart;
+
+                mnext = inext < offset ? inext : offset;
+                MetricAffectingSpan[] spans = mSpanned.getSpans(mStart + i,
+                        mStart + mnext, MetricAffectingSpan.class);
+
+                if (spans.length > 0) {
+                    ReplacementSpan replacement = null;
+                    for (int j = 0; j < spans.length; j++) {
+                        MetricAffectingSpan span = spans[j];
+                        if (span instanceof ReplacementSpan) {
+                            replacement = (ReplacementSpan)span;
+                        } else {
+                            span.updateDrawState(wp); // XXX or measureState?
+                        }
+                    }
+
+                    if (replacement != null) {
+                        x += handleReplacement(replacement, wp, runIndex, i,
+                                mnext, runIsRtl, c, x, top, y, bottom, fmi,
+                                needWidth || mnext < offset, prepFlags);
+                        continue;
+                    }
+                }
+            }
+
+            if (prepFlags != PREP_NONE) {
+                handlePrep(wp, runIndex, i, inext, runIsRtl);
+            }
+
+            if (prepFlags != PREP_ONLY) {
+                if (mSpanned == null || c == null) {
+                    x += handleText(wp, i, mnext, runIsRtl, c, x, top,
+                            y, bottom, fmi, needWidth || mnext < offset);
+                } else {
+                    for (int j = i, jnext; j < mnext; j = jnext) {
+                        jnext = mSpanned.nextSpanTransition(mStart + j,
+                                mStart + mnext, CharacterStyle.class) - mStart;
+
+                        CharacterStyle[] spans = mSpanned.getSpans(mStart + j,
+                                mStart + jnext, CharacterStyle.class);
+
+                        wp.set(mPaint);
+                        for (int k = 0; k < spans.length; k++) {
+                            CharacterStyle span = spans[k];
+                            span.updateDrawState(wp);
+                        }
+
+                        x += handleText(wp, j, jnext, runIsRtl, c, x,
+                                top, y, bottom, fmi, needWidth || jnext < offset);
+                    }
+                }
+            }
+        }
+
+        return x - ox;
+    }
+
+    private static final int PREP_NONE = 0;
+    private static final int PREP_NEEDED = 1;
+    private static final int PREP_ONLY = 2;
+
+    /**
+     * Prepares text for measuring or rendering.
+     *
+     * @param paint the paint used to shape the text
+     * @param runIndex the run index
+     * @param start the start of the text to prepare
+     * @param limit the limit of the text to prepare
+     * @param runIsRtl true if the run is right-to-left
+     */
+    private void handlePrep(TextPaint paint, int runIndex, int start, int limit,
+            boolean runIsRtl) {
+
+        // The current implementation 'prepares' text by manipulating the
+        // character array.  In order to keep track of what ranges have
+        // already been prepared, it uses the runIndex and the limit of
+        // the prepared text within that run.  This index is required
+        // since operations that prepare the text always proceed in visual
+        // order and the limit itself does not let us know which runs have
+        // been processed and which have not.
+        //
+        // This bookkeeping is an attempt to let us process a line partially,
+        // for example, by only shaping up to the cursor position.  This may
+        // not make sense if we can reuse the line, say by caching repeated
+        // accesses to the same line for both measuring and drawing, since in
+        // those cases we'd always prepare the entire line.  At the
+        // opposite extreme, we might shape and then immediately discard only
+        // the run of text we're working with at the moment, instead of retaining
+        // the results of shaping (as the chars array is).  In this case as well
+        // we would not need to do the index/limit bookkeeping.
+        //
+        // Technically, the only reason for bookkeeping is so that we don't
+        // re-mirror already-mirrored glyphs, since the shaping and object
+        // replacement operations will not change already-processed text.
+
+        if (runIndex > mPreppedIndex ||
+                (runIndex == mPreppedIndex && start >= mPreppedLimit)) {
+            if (runIsRtl) {
+                int runLen = limit - start;
+                AndroidCharacter.mirror(mChars, start, runLen);
+                ArabicShaping.SHAPER.shape(mChars, start, runLen);
+
+                // Note: tweaked MockShaper to put '\ufeff' in place of
+                // alef when it forms lam-alef ligatures, so no extra
+                // processing is necessary here.
+            }
+            mPreppedIndex = runIndex;
+            mPreppedLimit = limit;
+        }
+    }
+
+    /**
+     * Render a text run with the set-up paint.
+     *
+     * @param c the canvas
+     * @param wp the paint used to render the text
+     * @param start the run start
+     * @param limit the run limit
+     * @param runIsRtl true if the run is right-to-left
+     * @param x the x position of the left edge of the run
+     * @param y the baseline of the run
+     */
+    private void drawTextRun(Canvas c, TextPaint wp, int start, int limit,
+            boolean runIsRtl, float x, int y) {
+
+        // Since currently skia only renders text left-to-right, we need to
+        // put the shaped characters into visual order before rendering.
+        // Since we might want to re-render the line again, we swap them
+        // back when we're done.  If we left them swapped, measurement
+        // would be broken since it expects the characters in logical order.
+        if (runIsRtl) {
+            swapRun(start, limit);
+        }
+        if (mCharsValid) {
+            c.drawText(mChars, start, limit - start, x, y, wp);
+        } else {
+            c.drawText(mText, mStart + start, mStart + limit, x, y, wp);
+        }
+        if (runIsRtl) {
+            swapRun(start, limit);
+        }
+    }
+
+    /**
+     * Reverses the order of characters in the chars array between start and
+     * limit, used by drawTextRun.
+     * @param start the start of the run to reverse
+     * @param limit the limit of the run to reverse
+     */
+    private void swapRun(int start, int limit) {
+        // First we swap all the characters one for one, then we
+        // do another pass looking for surrogate pairs and swapping them
+        // back into their logical order.
+        char[] chars = mChars;
+        for (int s = start, e = limit - 1; s < e; ++s, --e) {
+            char ch = chars[s]; chars[s] = chars[e]; chars[e] = ch;
+        }
+
+        for (int s = start, e = limit - 1; s < e; ++s) {
+            char c1 = chars[s];
+            if (c1 >= 0xdc00 && c1 < 0xe000) {
+                char c2 = chars[s+1];
+                if (c2 >= 0xd800 && c2 < 0xdc00) {
+                    chars[s++] = c2;
+                    chars[s] = c1;
+                }
+            }
+        }
+    }
+
+    /**
+     * Returns the ascent of the text at start.  This is used for scaling
+     * emoji.
+     *
+     * @param pos the line-relative position
+     * @return the ascent of the text at start
+     */
+    float ascent(int pos) {
+        if (mSpanned == null) {
+            return mPaint.ascent();
+        }
+
+        pos += mStart;
+        MetricAffectingSpan[] spans = mSpanned.getSpans(pos, pos + 1,
+                MetricAffectingSpan.class);
+        if (spans.length == 0) {
+            return mPaint.ascent();
+        }
+
+        TextPaint wp = mWorkPaint;
+        wp.set(mPaint);
+        for (MetricAffectingSpan span : spans) {
+            span.updateMeasureState(wp);
+        }
+        return wp.ascent();
+    }
+
+    /**
+     * Returns the next tab position.
+     *
+     * @param h the (unsigned) offset from the leading margin
+     * @return the (unsigned) tab position after this offset
+     */
+    float nextTab(float h) {
+        float nh = Float.MAX_VALUE;
+        boolean alltabs = false;
+
+        if (mHasTabs && mTabs != null) {
+            TabStopSpan[] tabs = mTabs;
+            for (int i = 0; i < tabs.length && tabs[i] != null; ++i) {
+                int where = tabs[i].getTabStop();
+                if (where < nh && where > h) {
+                    nh = where;
+                }
+            }
+            if (nh != Float.MAX_VALUE) {
+                return nh;
+            }
+        }
+
+        return ((int) ((h + TAB_INCREMENT) / TAB_INCREMENT)) * TAB_INCREMENT;
+    }
+
+    private static final int TAB_INCREMENT = 20;
+}
diff --git a/core/java/android/text/TextUtils.java b/core/java/android/text/TextUtils.java
index 9589bf3..2d6c7b6 100644
--- a/core/java/android/text/TextUtils.java
+++ b/core/java/android/text/TextUtils.java
@@ -17,12 +17,11 @@
 package android.text;
 
 import com.android.internal.R;
+import com.android.internal.util.ArrayUtils;
 
-import android.content.res.ColorStateList;
 import android.content.res.Resources;
 import android.os.Parcel;
 import android.os.Parcelable;
-import android.text.method.TextKeyListener.Capitalize;
 import android.text.style.AbsoluteSizeSpan;
 import android.text.style.AlignmentSpan;
 import android.text.style.BackgroundColorSpan;
@@ -45,10 +44,8 @@
 import android.text.style.UnderlineSpan;
 import android.util.Printer;
 
-import com.android.internal.util.ArrayUtils;
-
-import java.util.regex.Pattern;
 import java.util.Iterator;
+import java.util.regex.Pattern;
 
 public class TextUtils {
     private TextUtils() { /* cannot be instantiated */ }
@@ -983,7 +980,7 @@
     /**
      * Returns the original text if it fits in the specified width
      * given the properties of the specified Paint,
-     * or, if it does not fit, a copy with ellipsis character added 
+     * or, if it does not fit, a copy with ellipsis character added
      * at the specified edge or center.
      * If <code>preserveLength</code> is specified, the returned copy
      * will be padded with zero-width spaces to preserve the original
@@ -992,7 +989,7 @@
      * report the start and end of the ellipsized range.
      */
     public static CharSequence ellipsize(CharSequence text,
-                                         TextPaint p,
+                                         TextPaint paint,
                                          float avail, TruncateAt where,
                                          boolean preserveLength,
                                          EllipsizeCallback callback) {
@@ -1003,13 +1000,12 @@
 
         int len = text.length();
 
-        // Use Paint.breakText() for the non-Spanned case to avoid having
-        // to allocate memory and accumulate the character widths ourselves.
+        MeasuredText mt = MeasuredText.obtain();
+        try {
+            float width = setPara(mt, paint, text, 0, text.length(),
+                    Layout.DIR_REQUEST_DEFAULT_LTR);
 
-        if (!(text instanceof Spanned)) {
-            float wid = p.measureText(text, 0, len);
-
-            if (wid <= avail) {
+            if (width <= avail) {
                 if (callback != null) {
                     callback.ellipsized(0, 0);
                 }
@@ -1017,250 +1013,69 @@
                 return text;
             }
 
-            float ellipsiswid = p.measureText(sEllipsis);
+            // XXX assumes ellipsis string does not require shaping and
+            // is unaffected by style
+            float ellipsiswid = paint.measureText(sEllipsis);
+            avail -= ellipsiswid;
 
-            if (ellipsiswid > avail) {
-                if (callback != null) {
-                    callback.ellipsized(0, len);
-                }
-
-                if (preserveLength) {
-                    char[] buf = obtain(len);
-                    for (int i = 0; i < len; i++) {
-                        buf[i] = '\uFEFF';
-                    }
-                    String ret = new String(buf, 0, len);
-                    recycle(buf);
-                    return ret;
-                } else {
-                    return "";
-                }
-            }
-
-            if (where == TruncateAt.START) {
-                int fit = p.breakText(text, 0, len, false,
-                                      avail - ellipsiswid, null);
-
-                if (callback != null) {
-                    callback.ellipsized(0, len - fit);
-                }
-
-                if (preserveLength) {
-                    return blank(text, 0, len - fit);
-                } else {
-                    return sEllipsis + text.toString().substring(len - fit, len);
-                }
+            int left = 0;
+            int right = len;
+            if (avail < 0) {
+                // it all goes
+            } else if (where == TruncateAt.START) {
+                right = len - mt.breakText(0, len, false, avail);
             } else if (where == TruncateAt.END) {
-                int fit = p.breakText(text, 0, len, true,
-                                      avail - ellipsiswid, null);
-
-                if (callback != null) {
-                    callback.ellipsized(fit, len);
-                }
-
-                if (preserveLength) {
-                    return blank(text, fit, len);
-                } else {
-                    return text.toString().substring(0, fit) + sEllipsis;
-                } 
-            } else /* where == TruncateAt.MIDDLE */ {
-                int right = p.breakText(text, 0, len, false,
-                                        (avail - ellipsiswid) / 2, null);
-                float used = p.measureText(text, len - right, len);
-                int left = p.breakText(text, 0, len - right, true,
-                                       avail - ellipsiswid - used, null);
-
-                if (callback != null) {
-                    callback.ellipsized(left, len - right);
-                }
-
-                if (preserveLength) {
-                    return blank(text, left, len - right);
-                } else {
-                    String s = text.toString();
-                    return s.substring(0, left) + sEllipsis +
-                           s.substring(len - right, len);
-                }
-            }
-        }
-
-        // But do the Spanned cases by hand, because it's such a pain
-        // to iterate the span transitions backwards and getTextWidths()
-        // will give us the information we need.
-
-        // getTextWidths() always writes into the start of the array,
-        // so measure each span into the first half and then copy the
-        // results into the second half to use later.
-
-        float[] wid = new float[len * 2];
-        TextPaint temppaint = new TextPaint();
-        Spanned sp = (Spanned) text;
-
-        int next;
-        for (int i = 0; i < len; i = next) {
-            next = sp.nextSpanTransition(i, len, MetricAffectingSpan.class);
-
-            Styled.getTextWidths(p, temppaint, sp, i, next, wid, null);
-            System.arraycopy(wid, 0, wid, len + i, next - i);
-        }
-
-        float sum = 0;
-        for (int i = 0; i < len; i++) {
-            sum += wid[len + i];
-        }
-
-        if (sum <= avail) {
-            if (callback != null) {
-                callback.ellipsized(0, 0);
-            }
-
-            return text;
-        }
-
-        float ellipsiswid = p.measureText(sEllipsis);
-
-        if (ellipsiswid > avail) {
-            if (callback != null) {
-                callback.ellipsized(0, len);
-            }
-
-            if (preserveLength) {
-                char[] buf = obtain(len);
-                for (int i = 0; i < len; i++) {
-                    buf[i] = '\uFEFF';
-                }
-                SpannableString ss = new SpannableString(new String(buf, 0, len));
-                recycle(buf);
-                copySpansFrom(sp, 0, len, Object.class, ss, 0);
-                return ss;
+                left = mt.breakText(0, len, true, avail);
             } else {
-                return "";
-            }
-        }
-
-        if (where == TruncateAt.START) {
-            sum = 0;
-            int i;
-
-            for (i = len; i >= 0; i--) {
-                float w = wid[len + i - 1];
-
-                if (w + sum + ellipsiswid > avail) {
-                    break;
-                }
-
-                sum += w;
-            }
-
-            if (callback != null) {
-                callback.ellipsized(0, i);
-            }
-
-            if (preserveLength) {
-                SpannableString ss = new SpannableString(blank(text, 0, i));
-                copySpansFrom(sp, 0, len, Object.class, ss, 0);
-                return ss;
-            } else {
-                SpannableStringBuilder out = new SpannableStringBuilder(sEllipsis);
-                out.insert(1, text, i, len);
-
-                return out;
-            }
-        } else if (where == TruncateAt.END) {
-            sum = 0;
-            int i;
-
-            for (i = 0; i < len; i++) {
-                float w = wid[len + i];
-
-                if (w + sum + ellipsiswid > avail) {
-                    break;
-                }
-
-                sum += w;
-            }
-
-            if (callback != null) {
-                callback.ellipsized(i, len);
-            }
-
-            if (preserveLength) {
-                SpannableString ss = new SpannableString(blank(text, i, len));
-                copySpansFrom(sp, 0, len, Object.class, ss, 0);
-                return ss;
-            } else {
-                SpannableStringBuilder out = new SpannableStringBuilder(sEllipsis);
-                out.insert(0, text, 0, i);
-
-                return out;
-            }
-        } else /* where = TruncateAt.MIDDLE */ {
-            float lsum = 0, rsum = 0;
-            int left = 0, right = len;
-
-            float ravail = (avail - ellipsiswid) / 2;
-            for (right = len; right >= 0; right--) {
-                float w = wid[len + right - 1];
-
-                if (w + rsum > ravail) {
-                    break;
-                }
-
-                rsum += w;
-            }
-
-            float lavail = avail - ellipsiswid - rsum;
-            for (left = 0; left < right; left++) {
-                float w = wid[len + left];
-
-                if (w + lsum > lavail) {
-                    break;
-                }
-
-                lsum += w;
+                right = len - mt.breakText(0, len, false, avail / 2);
+                avail -= mt.measure(right, len);
+                left = mt.breakText(0, right, true, avail);
             }
 
             if (callback != null) {
                 callback.ellipsized(left, right);
             }
 
+            char[] buf = mt.mChars;
+            Spanned sp = text instanceof Spanned ? (Spanned) text : null;
+
+            int remaining = len - (right - left);
             if (preserveLength) {
-                SpannableString ss = new SpannableString(blank(text, left, right));
+                if (remaining > 0) { // else eliminate the ellipsis too
+                    buf[left++] = '\u2026';
+                }
+                for (int i = left; i < right; i++) {
+                    buf[i] = '\uFEFF';
+                }
+                String s = new String(buf, 0, len);
+                if (sp == null) {
+                    return s;
+                }
+                SpannableString ss = new SpannableString(s);
                 copySpansFrom(sp, 0, len, Object.class, ss, 0);
                 return ss;
-            } else {
-                SpannableStringBuilder out = new SpannableStringBuilder(sEllipsis);
-                out.insert(0, text, 0, left);
-                out.insert(out.length(), text, right, len);
-
-                return out;
             }
-        }
-    }
 
-    private static String blank(CharSequence source, int start, int end) {
-        int len = source.length();
-        char[] buf = obtain(len);
-
-        if (start != 0) {
-            getChars(source, 0, start, buf, 0);
-        }
-        if (end != len) {
-            getChars(source, end, len, buf, end);
-        }
-
-        if (start != end) {
-            buf[start] = '\u2026';
-
-            for (int i = start + 1; i < end; i++) {
-                buf[i] = '\uFEFF';
+            if (remaining == 0) {
+                return "";
             }
-        }
-    
-        String ret = new String(buf, 0, len);
-        recycle(buf);
 
-        return ret;
+            if (sp == null) {
+                StringBuilder sb = new StringBuilder(remaining + sEllipsis.length());
+                sb.append(buf, 0, left);
+                sb.append(sEllipsis);
+                sb.append(buf, right, len - right);
+                return sb.toString();
+            }
+
+            SpannableStringBuilder ssb = new SpannableStringBuilder();
+            ssb.append(text, 0, left);
+            ssb.append(sEllipsis);
+            ssb.append(text, right, len);
+            return ssb;
+        } finally {
+            MeasuredText.recycle(mt);
+        }
     }
 
     /**
@@ -1278,80 +1093,121 @@
                                               TextPaint p, float avail,
                                               String oneMore,
                                               String more) {
-        int len = text.length();
-        char[] buf = new char[len];
-        TextUtils.getChars(text, 0, len, buf, 0);
 
-        int commaCount = 0;
-        for (int i = 0; i < len; i++) {
-            if (buf[i] == ',') {
-                commaCount++;
-            }
-        }
-
-        float[] wid;
-
-        if (text instanceof Spanned) {
-            Spanned sp = (Spanned) text;
-            TextPaint temppaint = new TextPaint();
-            wid = new float[len * 2];
-
-            int next;
-            for (int i = 0; i < len; i = next) {
-                next = sp.nextSpanTransition(i, len, MetricAffectingSpan.class);
-
-                Styled.getTextWidths(p, temppaint, sp, i, next, wid, null);
-                System.arraycopy(wid, 0, wid, len + i, next - i);
+        MeasuredText mt = MeasuredText.obtain();
+        try {
+            int len = text.length();
+            float width = setPara(mt, p, text, 0, len, Layout.DIR_REQUEST_DEFAULT_LTR);
+            if (width <= avail) {
+                return text;
             }
 
-            System.arraycopy(wid, len, wid, 0, len);
-        } else {
-            wid = new float[len];
-            p.getTextWidths(text, 0, len, wid);
-        }
+            char[] buf = mt.mChars;
 
-        int ok = 0;
-        int okRemaining = commaCount + 1;
-        String okFormat = "";
-
-        int w = 0;
-        int count = 0;
-
-        for (int i = 0; i < len; i++) {
-            w += wid[i];
-
-            if (buf[i] == ',') {
-                count++;
-
-                int remaining = commaCount - count + 1;
-                float moreWid;
-                String format;
-
-                if (remaining == 1) {
-                    format = " " + oneMore;
-                } else {
-                    format = " " + String.format(more, remaining);
-                }
-
-                moreWid = p.measureText(format);
-
-                if (w + moreWid <= avail) {
-                    ok = i + 1;
-                    okRemaining = remaining;
-                    okFormat = format;
+            int commaCount = 0;
+            for (int i = 0; i < len; i++) {
+                if (buf[i] == ',') {
+                    commaCount++;
                 }
             }
-        }
 
-        if (w <= avail) {
-            return text;
-        } else {
+            int remaining = commaCount + 1;
+
+            int ok = 0;
+            int okRemaining = remaining;
+            String okFormat = "";
+
+            int w = 0;
+            int count = 0;
+            float[] widths = mt.mWidths;
+
+            int request = mt.mDir == 1 ? Layout.DIR_REQUEST_LTR :
+                Layout.DIR_REQUEST_RTL;
+
+            MeasuredText tempMt = MeasuredText.obtain();
+            for (int i = 0; i < len; i++) {
+                w += widths[i];
+
+                if (buf[i] == ',') {
+                    count++;
+
+                    String format;
+                    // XXX should not insert spaces, should be part of string
+                    // XXX should use plural rules and not assume English plurals
+                    if (--remaining == 1) {
+                        format = " " + oneMore;
+                    } else {
+                        format = " " + String.format(more, remaining);
+                    }
+
+                    // XXX this is probably ok, but need to look at it more
+                    tempMt.setPara(format, 0, format.length(), request);
+                    float moreWid = mt.addStyleRun(p, mt.mLen, null);
+
+                    if (w + moreWid <= avail) {
+                        ok = i + 1;
+                        okRemaining = remaining;
+                        okFormat = format;
+                    }
+                }
+            }
+            MeasuredText.recycle(tempMt);
+
             SpannableStringBuilder out = new SpannableStringBuilder(okFormat);
             out.insert(0, text, 0, ok);
             return out;
+        } finally {
+            MeasuredText.recycle(mt);
         }
     }
 
+    private static float setPara(MeasuredText mt, TextPaint paint,
+            CharSequence text, int start, int end, int bidiRequest) {
+
+        mt.setPara(text, start, end, bidiRequest);
+
+        float width;
+        Spanned sp = text instanceof Spanned ? (Spanned) text : null;
+        int len = end - start;
+        if (sp == null) {
+            width = mt.addStyleRun(paint, len, null);
+        } else {
+            width = 0;
+            int spanEnd;
+            for (int spanStart = 0; spanStart < len; spanStart = spanEnd) {
+                spanEnd = sp.nextSpanTransition(spanStart, len,
+                        MetricAffectingSpan.class);
+                MetricAffectingSpan[] spans = sp.getSpans(
+                        spanStart, spanEnd, MetricAffectingSpan.class);
+                width += mt.addStyleRun(paint, spans, spanEnd - spanStart, null);
+            }
+        }
+
+        return width;
+    }
+
+    private static final char FIRST_RIGHT_TO_LEFT = '\u0590';
+
+    /* package */
+    static boolean doesNotNeedBidi(CharSequence s, int start, int end) {
+        for (int i = start; i < end; i++) {
+            if (s.charAt(i) >= FIRST_RIGHT_TO_LEFT) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /* package */
+    static boolean doesNotNeedBidi(char[] text, int start, int len) {
+        for (int i = start, e = i + len; i < e; i++) {
+            if (text[i] >= FIRST_RIGHT_TO_LEFT) {
+                return false;
+            }
+        }
+        return true;
+    }
+
     /* package */ static char[] obtain(int len) {
         char[] buf;
 
@@ -1529,7 +1385,7 @@
      */
     public static final int CAP_MODE_CHARACTERS
             = InputType.TYPE_TEXT_FLAG_CAP_CHARACTERS;
-    
+
     /**
      * Capitalization mode for {@link #getCapsMode}: capitalize the first
      * character of all words.  This value is explicitly defined to be the same as
@@ -1537,7 +1393,7 @@
      */
     public static final int CAP_MODE_WORDS
             = InputType.TYPE_TEXT_FLAG_CAP_WORDS;
-    
+
     /**
      * Capitalization mode for {@link #getCapsMode}: capitalize the first
      * character of each sentence.  This value is explicitly defined to be the same as
@@ -1545,13 +1401,13 @@
      */
     public static final int CAP_MODE_SENTENCES
             = InputType.TYPE_TEXT_FLAG_CAP_SENTENCES;
-    
+
     /**
      * Determine what caps mode should be in effect at the current offset in
      * the text.  Only the mode bits set in <var>reqModes</var> will be
      * checked.  Note that the caps mode flags here are explicitly defined
      * to match those in {@link InputType}.
-     * 
+     *
      * @param cs The text that should be checked for caps modes.
      * @param off Location in the text at which to check.
      * @param reqModes The modes to be checked: may be any combination of
@@ -1651,7 +1507,7 @@
 
         return mode;
     }
-    
+
     private static Object sLock = new Object();
     private static char[] sTemp = null;
 }
diff --git a/icu4j/java/android/icu/text/ArabicShaping.java b/icu4j/java/android/icu/text/ArabicShaping.java
new file mode 100644
index 0000000..13e2175
--- /dev/null
+++ b/icu4j/java/android/icu/text/ArabicShaping.java
@@ -0,0 +1,1947 @@
+/*
+*******************************************************************************
+*   Copyright (C) 2001-2009, International Business Machines
+*   Corporation and others.  All Rights Reserved.
+*******************************************************************************
+*/
+
+/*
+ * Ported with minor modifications from ICU4J 4.2's
+ * com.ibm.icu.text.ArabicShaping class.
+ */
+
+package android.icu.text;
+
+
+/**
+ * Shape Arabic text on a character basis.
+ *
+ * <p>ArabicShaping performs basic operations for "shaping" Arabic text. It is most
+ * useful for use with legacy data formats and legacy display technology
+ * (simple terminals). All operations are performed on Unicode characters.</p>
+ *
+ * <p>Text-based shaping means that some character code points in the text are
+ * replaced by others depending on the context. It transforms one kind of text
+ * into another. In comparison, modern displays for Arabic text select
+ * appropriate, context-dependent font glyphs for each text element, which means
+ * that they transform text into a glyph vector.</p>
+ *
+ * <p>Text transformations are necessary when modern display technology is not
+ * available or when text needs to be transformed to or from legacy formats that
+ * use "shaped" characters. Since the Arabic script is cursive, connecting
+ * adjacent letters to each other, computers select images for each letter based
+ * on the surrounding letters. This usually results in four images per Arabic
+ * letter: initial, middle, final, and isolated forms. In Unicode, on the other
+ * hand, letters are normally stored abstract, and a display system is expected
+ * to select the necessary glyphs. (This makes searching and other text
+ * processing easier because the same letter has only one code.) It is possible
+ * to mimic this with text transformations because there are characters in
+ * Unicode that are rendered as letters with a specific shape
+ * (or cursive connectivity). They were included for interoperability with
+ * legacy systems and codepages, and for unsophisticated display systems.</p>
+ *
+ * <p>A second kind of text transformations is supported for Arabic digits:
+ * For compatibility with legacy codepages that only include European digits,
+ * it is possible to replace one set of digits by another, changing the
+ * character code points. These operations can be performed for either
+ * Arabic-Indic Digits (U+0660...U+0669) or Eastern (Extended) Arabic-Indic
+ * digits (U+06f0...U+06f9).</p>
+ *
+ * <p>Some replacements may result in more or fewer characters (code points).
+ * By default, this means that the destination buffer may receive text with a
+ * length different from the source length. Some legacy systems rely on the
+ * length of the text to be constant. They expect extra spaces to be added
+ * or consumed either next to the affected character or at the end of the
+ * text.</p>
+ * @stable ICU 2.0
+ *
+ * @hide
+ */
+public class ArabicShaping {
+    private final int options;
+    private boolean isLogical; // convenience
+    private boolean spacesRelativeToTextBeginEnd;
+    private char tailChar;
+
+    public static final ArabicShaping SHAPER = new ArabicShaping(
+            ArabicShaping.TEXT_DIRECTION_LOGICAL |
+            ArabicShaping.LENGTH_FIXED_SPACES_NEAR |
+            ArabicShaping.LETTERS_SHAPE |
+            ArabicShaping.DIGITS_NOOP);
+
+    /**
+     * Convert a range of text in the source array, putting the result
+     * into a range of text in the destination array, and return the number
+     * of characters written.
+     *
+     * @param source An array containing the input text
+     * @param sourceStart The start of the range of text to convert
+     * @param sourceLength The length of the range of text to convert
+     * @param dest The destination array that will receive the result.
+     *   It may be <code>NULL</code> only if  <code>destSize</code> is 0.
+     * @param destStart The start of the range of the destination buffer to use.
+     * @param destSize The size (capacity) of the destination buffer.
+     *   If <code>destSize</code> is 0, then no output is produced,
+     *   but the necessary buffer size is returned ("preflighting").  This
+     *   does not validate the text against the options, for example,
+     *   if letters are being unshaped, and spaces are being consumed
+     *   following lamalef, this will not detect a lamalef without a
+     *   corresponding space.  An error will be thrown when the actual
+     *   conversion is attempted.
+     * @return The number of chars written to the destination buffer.
+     *   If an error occurs, then no output was written, or it may be
+     *   incomplete.
+     * @throws ArabicShapingException if the text cannot be converted according to the options.
+     * @stable ICU 2.0
+     */
+    public int shape(char[] source, int sourceStart, int sourceLength,
+                     char[] dest, int destStart, int destSize) throws ArabicShapingException {
+        if (source == null) {
+            throw new IllegalArgumentException("source can not be null");
+        }
+        if (sourceStart < 0 || sourceLength < 0 || sourceStart + sourceLength > source.length) {
+            throw new IllegalArgumentException("bad source start (" + sourceStart +
+                                               ") or length (" + sourceLength +
+                                               ") for buffer of length " + source.length);
+        }
+        if (dest == null && destSize != 0) {
+            throw new IllegalArgumentException("null dest requires destSize == 0");
+        }
+        if ((destSize != 0) &&
+            (destStart < 0 || destSize < 0 || destStart + destSize > dest.length)) {
+            throw new IllegalArgumentException("bad dest start (" + destStart +
+                                               ") or size (" + destSize +
+                                               ") for buffer of length " + dest.length);
+        }
+        /* Validate input options */
+        if ( ((options&TASHKEEL_MASK) > 0) &&
+             !(((options & TASHKEEL_MASK)==TASHKEEL_BEGIN)  ||
+               ((options & TASHKEEL_MASK)==TASHKEEL_END )   ||
+               ((options & TASHKEEL_MASK)==TASHKEEL_RESIZE )||
+               ((options & TASHKEEL_MASK)==TASHKEEL_REPLACE_BY_TATWEEL)) ){
+            throw new IllegalArgumentException("Wrong Tashkeel argument");
+        }
+
+       ///CLOVER:OFF
+       //According to Steven Loomis, the code is unreachable when you OR all the constants within the if statements
+       if(((options&LAMALEF_MASK) > 0)&&
+              !(((options & LAMALEF_MASK)==LAMALEF_BEGIN)  ||
+                ((options & LAMALEF_MASK)==LAMALEF_END )   ||
+                ((options & LAMALEF_MASK)==LAMALEF_RESIZE )||
+                 ((options & LAMALEF_MASK)==LAMALEF_AUTO)  ||
+                 ((options & LAMALEF_MASK)==LAMALEF_NEAR))){
+           throw new IllegalArgumentException("Wrong Lam Alef argument");
+       }
+       ///CLOVER:ON
+
+       /* Validate Tashkeel (Tashkeel replacement options should be enabled in shaping mode only)*/
+       if(((options&TASHKEEL_MASK) > 0) && (options&LETTERS_MASK) == LETTERS_UNSHAPE) {
+            throw new IllegalArgumentException("Tashkeel replacement should not be enabled in deshaping mode ");
+       }
+       return internalShape(source, sourceStart, sourceLength, dest, destStart, destSize);
+    }
+
+    /**
+     * Convert a range of text in place.  This may only be used if the Length option
+     * does not grow or shrink the text.
+     *
+     * @param source An array containing the input text
+     * @param start The start of the range of text to convert
+     * @param length The length of the range of text to convert
+     * @throws ArabicShapingException if the text cannot be converted according to the options.
+     * @stable ICU 2.0
+     */
+    public void shape(char[] source, int start, int length) throws ArabicShapingException {
+        if ((options & LAMALEF_MASK) == LAMALEF_RESIZE) {
+            throw new ArabicShapingException("Cannot shape in place with length option resize.");
+        }
+        shape(source, start, length, source, start, length);
+    }
+
+    /**
+     * Convert a string, returning the new string.
+     *
+     * @param text the string to convert
+     * @return the converted string
+     * @throws ArabicShapingException if the string cannot be converted according to the options.
+     * @stable ICU 2.0
+     */
+    public String shape(String text) throws ArabicShapingException {
+        char[] src = text.toCharArray();
+        char[] dest = src;
+        if (((options & LAMALEF_MASK) == LAMALEF_RESIZE) &&
+            ((options & LETTERS_MASK) == LETTERS_UNSHAPE)) {
+
+            dest = new char[src.length * 2]; // max
+        }
+        int len = shape(src, 0, src.length, dest, 0, dest.length);
+
+        return new String(dest, 0, len);
+    }
+
+    /**
+     * Construct ArabicShaping using the options flags.
+     * The flags are as follows:<br>
+     * 'LENGTH' flags control whether the text can change size, and if not,
+     * how to maintain the size of the text when LamAlef ligatures are
+     * formed or broken.<br>
+     * 'TEXT_DIRECTION' flags control whether the text is read and written
+     * in visual order or in logical order.<br>
+     * 'LETTERS_SHAPE' flags control whether conversion is to or from
+     * presentation forms.<br>
+     * 'DIGITS' flags control whether digits are shaped, and whether from
+     * European to Arabic-Indic or vice-versa.<br>
+     * 'DIGIT_TYPE' flags control whether standard or extended Arabic-Indic
+     * digits are used when performing digit conversion.
+     * @stable ICU 2.0
+     */
+    public ArabicShaping(int options) {
+        this.options = options;
+        if ((options & DIGITS_MASK) > 0x80) {
+            throw new IllegalArgumentException("bad DIGITS options");
+        }
+
+        isLogical = ( (options & TEXT_DIRECTION_MASK) == TEXT_DIRECTION_LOGICAL );
+        /* Validate options */
+        spacesRelativeToTextBeginEnd = ( (options & SPACES_RELATIVE_TO_TEXT_MASK) == SPACES_RELATIVE_TO_TEXT_BEGIN_END );
+        if ( (options&SHAPE_TAIL_TYPE_MASK) == SHAPE_TAIL_NEW_UNICODE){
+            tailChar = NEW_TAIL_CHAR;
+        } else {
+            tailChar = OLD_TAIL_CHAR;
+        }
+    }
+
+    /* Seen Tail options */
+    /**
+     * Memory option: the result must have the same length as the source.
+     * Shaping mode: The SEEN family character will expand into two characters using space near
+     *               the SEEN family character(i.e. the space after the character).
+     *               if there are no spaces found, ArabicShapingException will be thrown
+     *
+     * De-shaping mode: Any Seen character followed by Tail character will be
+     *                  replaced by one cell Seen and a space will replace the Tail.
+     * Affects: Seen options
+     */
+    public static final int SEEN_TWOCELL_NEAR = 0x200000;
+
+    /** Bit mask for Seen memory options. */
+    public static final int SEEN_MASK = 0x700000;
+
+    /* YehHamza options */
+    /**
+     * Memory option: the result must have the same length as the source.
+     * Shaping mode: The YEHHAMZA character will expand into two characters using space near it
+     *              (i.e. the space after the character)
+     *               if there are no spaces found, ArabicShapingException will be thrown
+     *
+     * De-shaping mode: Any Yeh (final or isolated) character followed by Hamza character will be
+     *                  replaced by one cell YehHamza and space will replace the Hamza.
+     * Affects: YehHamza options
+     */
+    public static final int YEHHAMZA_TWOCELL_NEAR  = 0x1000000;
+
+
+    /** Bit mask for YehHamza memory options. */
+    public static final int YEHHAMZA_MASK = 0x3800000;
+
+    /* New Tashkeel options */
+    /**
+     * Memory option: the result must have the same length as the source.
+     * Shaping mode: Tashkeel characters will be replaced by spaces.
+     *               Spaces will be placed at beginning of the buffer
+     *
+     * De-shaping mode: N/A
+     * Affects: Tashkeel options
+     */
+    public static final int TASHKEEL_BEGIN = 0x40000;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * Shaping mode: Tashkeel characters will be replaced by spaces.
+     *               Spaces will be placed at end of the buffer
+     *
+     * De-shaping mode: N/A
+     * Affects: Tashkeel options
+     */
+    public static final int TASHKEEL_END = 0x60000;
+
+    /**
+     * Memory option: allow the result to have a different length than the source.
+     * Shaping mode: Tashkeel characters will be removed, buffer length will shrink.
+     * De-shaping mode: N/A
+     *
+     * Affects: Tashkeel options
+     */
+    public static final int TASHKEEL_RESIZE = 0x80000;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * Shaping mode: Tashkeel characters will be replaced by Tatweel if it is connected to adjacent
+     *               characters (i.e. shaped on Tatweel) or replaced by space if it is not connected.
+     *
+     * De-shaping mode: N/A
+     * Affects: YehHamza options
+     */
+    public static final int TASHKEEL_REPLACE_BY_TATWEEL = 0xC0000;
+
+    /** Bit mask for Tashkeel replacement with Space or Tatweel memory options. */
+    public static final int TASHKEEL_MASK  = 0xE0000;
+
+    /* Space location Control options */
+    /**
+     * This option effects the meaning of BEGIN and END options. if this option is not used the default
+     * for BEGIN and END will be as following:
+     * The Default (for both Visual LTR, Visual RTL and Logical Text)
+     *           1. BEGIN always refers to the start address of physical memory.
+     *           2. END always refers to the end address of physical memory.
+     *
+     * If this option is used it will swap the meaning of BEGIN and END only for Visual LTR text.
+     *
+     * The affect on BEGIN and END Memory Options will be as following:
+     *    A. BEGIN For Visual LTR text: This will be the beginning (right side) of the visual text
+     *       (corresponding to the physical memory address end, same as END in default behavior)
+     *    B. BEGIN For Logical text: Same as BEGIN in default behavior.
+     *    C. END For Visual LTR text: This will be the end (left side) of the visual text. (corresponding to
+     *      the physical memory address beginning, same as BEGIN in default behavior)
+     *    D. END For Logical text: Same as END in default behavior.
+     * Affects: All LamAlef BEGIN, END and AUTO options.
+     */
+    public static final int SPACES_RELATIVE_TO_TEXT_BEGIN_END = 0x4000000;
+
+    /** Bit mask for swapping BEGIN and END for Visual LTR text */
+    public static final int SPACES_RELATIVE_TO_TEXT_MASK = 0x4000000;
+
+    /**
+     * If this option is used, shaping will use the new Unicode code point for TAIL (i.e. 0xFE73).
+     * If this option is not specified (Default), old unofficial Unicode TAIL code point is used (i.e. 0x200B)
+     * De-shaping will not use this option as it will always search for both the new Unicode code point for the
+     * TAIL (i.e. 0xFE73) or the old unofficial Unicode TAIL code point (i.e. 0x200B) and de-shape the
+     * Seen-Family letter accordingly.
+     *
+     * Shaping Mode: Only shaping.
+     * De-shaping Mode: N/A.
+     * Affects: All Seen options
+     */
+    public static final int SHAPE_TAIL_NEW_UNICODE = 0x8000000;
+
+    /** Bit mask for new Unicode Tail option */
+    public static final int SHAPE_TAIL_TYPE_MASK = 0x8000000;
+
+    /**
+     * Memory option: allow the result to have a different length than the source.
+     * @stable ICU 2.0
+     */
+    public static final int LENGTH_GROW_SHRINK = 0;
+
+    /**
+     * Memory option: allow the result to have a different length than the source.
+     * Affects: LamAlef options
+     * This option is an alias to LENGTH_GROW_SHRINK
+     */
+    public static final int LAMALEF_RESIZE   = 0;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * If more room is necessary, then try to consume spaces next to modified characters.
+     * @stable ICU 2.0
+     */
+    public static final int LENGTH_FIXED_SPACES_NEAR = 1;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * If more room is necessary, then try to consume spaces next to modified characters.
+     * Affects: LamAlef options
+     * This option is an alias to LENGTH_FIXED_SPACES_NEAR
+     */
+    public static final int LAMALEF_NEAR = 1 ;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * If more room is necessary, then try to consume spaces at the end of the text.
+     * @stable ICU 2.0
+     */
+    public static final int LENGTH_FIXED_SPACES_AT_END = 2;
+
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * If more room is necessary, then try to consume spaces at the end of the text.
+     * Affects: LamAlef options
+     * This option is an alias to LENGTH_FIXED_SPACES_AT_END
+     */
+    public static final int LAMALEF_END = 2;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * If more room is necessary, then try to consume spaces at the beginning of the text.
+     * @stable ICU 2.0
+     */
+    public static final int LENGTH_FIXED_SPACES_AT_BEGINNING = 3;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * If more room is necessary, then try to consume spaces at the beginning of the text.
+     * Affects: LamAlef options
+     * This option is an alias to LENGTH_FIXED_SPACES_AT_BEGINNING
+     */
+    public static final int LAMALEF_BEGIN = 3;
+
+    /**
+     * Memory option: the result must have the same length as the source.
+     * Shaping Mode: For each LAMALEF character found, expand LAMALEF using space at end.
+     *               If there is no space at end, use spaces at beginning of the buffer. If there
+     *               is no space at beginning of the buffer, use spaces at the near (i.e. the space
+     *               after the LAMALEF character).
+     *
+     * Deshaping Mode: Perform the same function as the flag equals LAMALEF_END.
+     * Affects: LamAlef options
+     */
+    public static final int LAMALEF_AUTO  = 0x10000;
+
+    /**
+     * Bit mask for memory options.
+     * @stable ICU 2.0
+     */
+    public static final int LENGTH_MASK = 0x10003;
+
+    /** Bit mask for LamAlef memory options. */
+
+    public static final int LAMALEF_MASK  = 0x10003;
+
+    /**
+     * Direction indicator: the source is in logical (keyboard) order.
+     * @stable ICU 2.0
+     */
+    public static final int TEXT_DIRECTION_LOGICAL = 0;
+
+    /**
+     * Direction indicator:the source is in visual RTL order,
+     * the rightmost displayed character stored first.
+     * This option is an alias to U_SHAPE_TEXT_DIRECTION_LOGICAL
+     */
+    public static final int TEXT_DIRECTION_VISUAL_RTL = 0;
+
+    /**
+     * Direction indicator: the source is in visual (display) order, that is,
+     * the leftmost displayed character is stored first.
+     * @stable ICU 2.0
+     */
+    public static final int TEXT_DIRECTION_VISUAL_LTR = 4;
+
+    /**
+     * Bit mask for direction indicators.
+     * @stable ICU 2.0
+     */
+    public static final int TEXT_DIRECTION_MASK = 4;
+
+
+    /**
+     * Letter shaping option: do not perform letter shaping.
+     * @stable ICU 2.0
+     */
+    public static final int LETTERS_NOOP = 0;
+
+    /**
+     * Letter shaping option: replace normative letter characters in the U+0600 (Arabic) block,
+     * by shaped ones in the U+FE70 (Presentation Forms B) block. Performs Lam-Alef ligature
+     * substitution.
+     * @stable ICU 2.0
+     */
+    public static final int LETTERS_SHAPE = 8;
+
+    /**
+     * Letter shaping option: replace shaped letter characters in the U+FE70 (Presentation Forms B) block
+     * by normative ones in the U+0600 (Arabic) block.  Converts Lam-Alef ligatures to pairs of Lam and
+     * Alef characters, consuming spaces if required.
+     * @stable ICU 2.0
+     */
+    public static final int LETTERS_UNSHAPE = 0x10;
+
+    /**
+     * Letter shaping option: replace normative letter characters in the U+0600 (Arabic) block,
+     * except for the TASHKEEL characters at U+064B...U+0652, by shaped ones in the U+Fe70
+     * (Presentation Forms B) block.  The TASHKEEL characters will always be converted to
+     * the isolated forms rather than to their correct shape.
+     * @stable ICU 2.0
+     */
+    public static final int LETTERS_SHAPE_TASHKEEL_ISOLATED = 0x18;
+
+    /**
+     * Bit mask for letter shaping options.
+     * @stable ICU 2.0
+     */
+    public static final int LETTERS_MASK = 0x18;
+
+
+    /**
+     * Digit shaping option: do not perform digit shaping.
+     * @stable ICU 2.0
+     */
+    public static final int DIGITS_NOOP = 0;
+
+    /**
+     * Digit shaping option: Replace European digits (U+0030...U+0039) by Arabic-Indic digits.
+     * @stable ICU 2.0
+     */
+    public static final int DIGITS_EN2AN = 0x20;
+
+    /**
+     * Digit shaping option: Replace Arabic-Indic digits by European digits (U+0030...U+0039).
+     * @stable ICU 2.0
+     */
+    public static final int DIGITS_AN2EN = 0x40;
+
+    /**
+     * Digit shaping option:
+     * Replace European digits (U+0030...U+0039) by Arabic-Indic digits
+     * if the most recent strongly directional character
+     * is an Arabic letter (its Bidi direction value is RIGHT_TO_LEFT_ARABIC).
+     * The initial state at the start of the text is assumed to be not an Arabic,
+     * letter, so European digits at the start of the text will not change.
+     * Compare to DIGITS_ALEN2AN_INIT_AL.
+     * @stable ICU 2.0
+     */
+    public static final int DIGITS_EN2AN_INIT_LR = 0x60;
+
+    /**
+     * Digit shaping option:
+     * Replace European digits (U+0030...U+0039) by Arabic-Indic digits
+     * if the most recent strongly directional character
+     * is an Arabic letter (its Bidi direction value is RIGHT_TO_LEFT_ARABIC).
+     * The initial state at the start of the text is assumed to be an Arabic,
+     * letter, so European digits at the start of the text will change.
+     * Compare to DIGITS_ALEN2AN_INT_LR.
+     * @stable ICU 2.0
+     */
+    public static final int DIGITS_EN2AN_INIT_AL = 0x80;
+
+    /** Not a valid option value. */
+    //private static final int DIGITS_RESERVED = 0xa0;
+
+    /**
+     * Bit mask for digit shaping options.
+     * @stable ICU 2.0
+     */
+    public static final int DIGITS_MASK = 0xe0;
+
+    /**
+     * Digit type option: Use Arabic-Indic digits (U+0660...U+0669).
+     * @stable ICU 2.0
+     */
+    public static final int DIGIT_TYPE_AN = 0;
+
+    /**
+     * Digit type option: Use Eastern (Extended) Arabic-Indic digits (U+06f0...U+06f9).
+     * @stable ICU 2.0
+     */
+    public static final int DIGIT_TYPE_AN_EXTENDED = 0x100;
+
+    /**
+     * Bit mask for digit type options.
+     * @stable ICU 2.0
+     */
+    public static final int DIGIT_TYPE_MASK = 0x0100; // 0x3f00?
+
+    /**
+     * some constants
+     */
+    private static final char HAMZAFE_CHAR       = '\ufe80';
+    private static final char HAMZA06_CHAR       = '\u0621';
+    private static final char YEH_HAMZA_CHAR     = '\u0626';
+    private static final char YEH_HAMZAFE_CHAR   = '\uFE89';
+    private static final char LAMALEF_SPACE_SUB  = '\uffff';
+    private static final char TASHKEEL_SPACE_SUB = '\ufffe';
+    private static final char LAM_CHAR      = '\u0644';
+    private static final char SPACE_CHAR    = '\u0020';
+    private static final char SPACE_CHAR_FOR_LAMALEF = '\ufeff'; // XXX: tweak for TextLine use
+    private static final char SHADDA_CHAR   = '\uFE7C';
+    private static final char TATWEEL_CHAR  = '\u0640';
+    private static final char SHADDA_TATWEEL_CHAR = '\uFE7D';
+    private static final char NEW_TAIL_CHAR = '\uFE73';
+    private static final char OLD_TAIL_CHAR = '\u200B';
+    private static final int SHAPE_MODE      = 0;
+    private static final int DESHAPE_MODE    = 1;
+
+    /**
+     * @stable ICU 2.0
+     */
+    public boolean equals(Object rhs) {
+        return rhs != null &&
+            rhs.getClass() == ArabicShaping.class &&
+            options == ((ArabicShaping)rhs).options;
+    }
+
+    /**
+     * @stable ICU 2.0
+     */
+     ///CLOVER:OFF
+    public int hashCode() {
+        return options;
+    }
+
+    /**
+     * @stable ICU 2.0
+     */
+    public String toString() {
+        StringBuffer buf = new StringBuffer(super.toString());
+        buf.append('[');
+
+        switch (options & LAMALEF_MASK) {
+        case LAMALEF_RESIZE: buf.append("LamAlef resize"); break;
+        case LAMALEF_NEAR: buf.append("LamAlef spaces at near"); break;
+        case LAMALEF_BEGIN: buf.append("LamAlef spaces at begin"); break;
+        case LAMALEF_END: buf.append("LamAlef spaces at end"); break;
+        case LAMALEF_AUTO: buf.append("lamAlef auto"); break;
+        }
+        switch (options & TEXT_DIRECTION_MASK) {
+        case TEXT_DIRECTION_LOGICAL: buf.append(", logical"); break;
+        case TEXT_DIRECTION_VISUAL_LTR: buf.append(", visual"); break;
+        }
+        switch (options & LETTERS_MASK) {
+        case LETTERS_NOOP: buf.append(", no letter shaping"); break;
+        case LETTERS_SHAPE: buf.append(", shape letters"); break;
+        case LETTERS_SHAPE_TASHKEEL_ISOLATED: buf.append(", shape letters tashkeel isolated"); break;
+        case LETTERS_UNSHAPE: buf.append(", unshape letters"); break;
+        }
+        switch (options & SEEN_MASK) {
+        case SEEN_TWOCELL_NEAR: buf.append(", Seen at near"); break;
+        }
+        switch (options & YEHHAMZA_MASK) {
+        case YEHHAMZA_TWOCELL_NEAR: buf.append(", Yeh Hamza at near"); break;
+        }
+        switch (options & TASHKEEL_MASK) {
+        case TASHKEEL_BEGIN: buf.append(", Tashkeel at begin"); break;
+        case TASHKEEL_END: buf.append(", Tashkeel at end"); break;
+        case TASHKEEL_REPLACE_BY_TATWEEL: buf.append(", Tashkeel replace with tatweel"); break;
+        case TASHKEEL_RESIZE: buf.append(", Tashkeel resize"); break;
+        }
+
+        switch (options & DIGITS_MASK) {
+        case DIGITS_NOOP: buf.append(", no digit shaping"); break;
+        case DIGITS_EN2AN: buf.append(", shape digits to AN"); break;
+        case DIGITS_AN2EN: buf.append(", shape digits to EN"); break;
+        case DIGITS_EN2AN_INIT_LR: buf.append(", shape digits to AN contextually: default EN"); break;
+        case DIGITS_EN2AN_INIT_AL: buf.append(", shape digits to AN contextually: default AL"); break;
+        }
+        switch (options & DIGIT_TYPE_MASK) {
+        case DIGIT_TYPE_AN: buf.append(", standard Arabic-Indic digits"); break;
+        case DIGIT_TYPE_AN_EXTENDED: buf.append(", extended Arabic-Indic digits"); break;
+        }
+        buf.append("]");
+
+        return buf.toString();
+    }
+    ///CLOVER:ON
+
+    //
+    // ported api
+    //
+
+    private static final int IRRELEVANT = 4;
+    private static final int LAMTYPE = 16;
+    private static final int ALEFTYPE = 32;
+
+    private static final int LINKR = 1;
+    private static final int LINKL = 2;
+    private static final int LINK_MASK = 3;
+
+    private static final int irrelevantPos[] = {
+        0x0, 0x2, 0x4, 0x6, 0x8, 0xA, 0xC, 0xE
+    };
+
+/*
+    private static final char convertLamAlef[] =  {
+        '\u0622', // FEF5
+        '\u0622', // FEF6
+        '\u0623', // FEF7
+        '\u0623', // FEF8
+        '\u0625', // FEF9
+        '\u0625', // FEFA
+        '\u0627', // FEFB
+        '\u0627'  // FEFC
+    };
+*/
+
+    private static final int tailFamilyIsolatedFinal[] = {
+        /* FEB1 */ 1,
+        /* FEB2 */ 1,
+        /* FEB3 */ 0,
+        /* FEB4 */ 0,
+        /* FEB5 */ 1,
+        /* FEB6 */ 1,
+        /* FEB7 */ 0,
+        /* FEB8 */ 0,
+        /* FEB9 */ 1,
+        /* FEBA */ 1,
+        /* FEBB */ 0,
+        /* FEBC */ 0,
+        /* FEBD */ 1,
+        /* FEBE */ 1
+    };
+
+    private static final int tashkeelMedial[] = {
+        /* FE70 */ 0,
+        /* FE71 */ 1,
+        /* FE72 */ 0,
+        /* FE73 */ 0,
+        /* FE74 */ 0,
+        /* FE75 */ 0,
+        /* FE76 */ 0,
+        /* FE77 */ 1,
+        /* FE78 */ 0,
+        /* FE79 */ 1,
+        /* FE7A */ 0,
+        /* FE7B */ 1,
+        /* FE7C */ 0,
+        /* FE7D */ 1,
+        /* FE7E */ 0,
+        /* FE7F */ 1
+    };
+
+    private static final char yehHamzaToYeh[] =
+    {
+    /* isolated*/ 0xFEEF,
+    /* final   */ 0xFEF0
+    };
+
+    private static final char convertNormalizedLamAlef[] = {
+        '\u0622', // 065C
+        '\u0623', // 065D
+        '\u0625', // 065E
+        '\u0627', // 065F
+    };
+
+    private static final int[] araLink = {
+        1           + 32 + 256 * 0x11,  /*0x0622*/
+        1           + 32 + 256 * 0x13,  /*0x0623*/
+        1                + 256 * 0x15,  /*0x0624*/
+        1           + 32 + 256 * 0x17,  /*0x0625*/
+        1 + 2            + 256 * 0x19,  /*0x0626*/
+        1           + 32 + 256 * 0x1D,  /*0x0627*/
+        1 + 2            + 256 * 0x1F,  /*0x0628*/
+        1                + 256 * 0x23,  /*0x0629*/
+        1 + 2            + 256 * 0x25,  /*0x062A*/
+        1 + 2            + 256 * 0x29,  /*0x062B*/
+        1 + 2            + 256 * 0x2D,  /*0x062C*/
+        1 + 2            + 256 * 0x31,  /*0x062D*/
+        1 + 2            + 256 * 0x35,  /*0x062E*/
+        1                + 256 * 0x39,  /*0x062F*/
+        1                + 256 * 0x3B,  /*0x0630*/
+        1                + 256 * 0x3D,  /*0x0631*/
+        1                + 256 * 0x3F,  /*0x0632*/
+        1 + 2            + 256 * 0x41,  /*0x0633*/
+        1 + 2            + 256 * 0x45,  /*0x0634*/
+        1 + 2            + 256 * 0x49,  /*0x0635*/
+        1 + 2            + 256 * 0x4D,  /*0x0636*/
+        1 + 2            + 256 * 0x51,  /*0x0637*/
+        1 + 2            + 256 * 0x55,  /*0x0638*/
+        1 + 2            + 256 * 0x59,  /*0x0639*/
+        1 + 2            + 256 * 0x5D,  /*0x063A*/
+        0, 0, 0, 0, 0,                  /*0x063B-0x063F*/
+        1 + 2,                          /*0x0640*/
+        1 + 2            + 256 * 0x61,  /*0x0641*/
+        1 + 2            + 256 * 0x65,  /*0x0642*/
+        1 + 2            + 256 * 0x69,  /*0x0643*/
+        1 + 2       + 16 + 256 * 0x6D,  /*0x0644*/
+        1 + 2            + 256 * 0x71,  /*0x0645*/
+        1 + 2            + 256 * 0x75,  /*0x0646*/
+        1 + 2            + 256 * 0x79,  /*0x0647*/
+        1                + 256 * 0x7D,  /*0x0648*/
+        1                + 256 * 0x7F,  /*0x0649*/
+        1 + 2            + 256 * 0x81,  /*0x064A*/
+        4, 4, 4, 4,                     /*0x064B-0x064E*/
+        4, 4, 4, 4,                     /*0x064F-0x0652*/
+        4, 4, 4, 0, 0,                  /*0x0653-0x0657*/
+        0, 0, 0, 0,                     /*0x0658-0x065B*/
+        1                + 256 * 0x85,  /*0x065C*/
+        1                + 256 * 0x87,  /*0x065D*/
+        1                + 256 * 0x89,  /*0x065E*/
+        1                + 256 * 0x8B,  /*0x065F*/
+        0, 0, 0, 0, 0,                  /*0x0660-0x0664*/
+        0, 0, 0, 0, 0,                  /*0x0665-0x0669*/
+        0, 0, 0, 0, 0, 0,               /*0x066A-0x066F*/
+        4,                              /*0x0670*/
+        0,                              /*0x0671*/
+        1           + 32,               /*0x0672*/
+        1           + 32,               /*0x0673*/
+        0,                              /*0x0674*/
+        1           + 32,               /*0x0675*/
+        1, 1,                           /*0x0676-0x0677*/
+        1+2, 1+2, 1+2, 1+2, 1+2, 1+2,   /*0x0678-0x067D*/
+        1+2, 1+2, 1+2, 1+2, 1+2, 1+2,   /*0x067E-0x0683*/
+        1+2, 1+2, 1+2, 1+2,             /*0x0684-0x0687*/
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1,   /*0x0688-0x0691*/
+        1, 1, 1, 1, 1, 1, 1, 1,         /*0x0692-0x0699*/
+        1+2, 1+2, 1+2, 1+2, 1+2, 1+2,   /*0x069A-0x06A3*/
+        1+2, 1+2, 1+2, 1+2,             /*0x069A-0x06A3*/
+        1+2, 1+2, 1+2, 1+2, 1+2, 1+2,   /*0x06A4-0x06AD*/
+        1+2, 1+2, 1+2, 1+2,             /*0x06A4-0x06AD*/
+        1+2, 1+2, 1+2, 1+2, 1+2, 1+2,   /*0x06AE-0x06B7*/
+        1+2, 1+2, 1+2, 1+2,             /*0x06AE-0x06B7*/
+        1+2, 1+2, 1+2, 1+2, 1+2, 1+2,   /*0x06B8-0x06BF*/
+        1+2, 1+2,                       /*0x06B8-0x06BF*/
+        1,                              /*0x06C0*/
+        1+2,                            /*0x06C1*/
+        1, 1, 1, 1, 1, 1, 1, 1, 1, 1,   /*0x06C2-0x06CB*/
+        1+2,                            /*0x06CC*/
+        1,                              /*0x06CD*/
+        1+2, 1+2, 1+2, 1+2,             /*0x06CE-0x06D1*/
+        1, 1                            /*0x06D2-0x06D3*/
+    };
+
+    private static final int[] presLink = {
+        1 + 2,                        /*0xFE70*/
+        1 + 2,                        /*0xFE71*/
+        1 + 2, 0, 1+ 2, 0, 1+ 2,      /*0xFE72-0xFE76*/
+        1 + 2,                        /*0xFE77*/
+        1+ 2, 1 + 2, 1+2, 1 + 2,      /*0xFE78-0xFE81*/
+        1+ 2, 1 + 2, 1+2, 1 + 2,      /*0xFE82-0xFE85*/
+        0, 0 + 32, 1 + 32, 0 + 32,    /*0xFE86-0xFE89*/
+        1 + 32, 0, 1,  0 + 32,        /*0xFE8A-0xFE8D*/
+        1 + 32, 0, 2,  1 + 2,         /*0xFE8E-0xFE91*/
+        1, 0 + 32, 1 + 32, 0,         /*0xFE92-0xFE95*/
+        2, 1 + 2, 1, 0,               /*0xFE96-0xFE99*/
+        1, 0, 2, 1 + 2,               /*0xFE9A-0xFE9D*/
+        1, 0, 2, 1 + 2,               /*0xFE9E-0xFEA1*/
+        1, 0, 2, 1 + 2,               /*0xFEA2-0xFEA5*/
+        1, 0, 2, 1 + 2,               /*0xFEA6-0xFEA9*/
+        1, 0, 2, 1 + 2,               /*0xFEAA-0xFEAD*/
+        1, 0, 1, 0,                   /*0xFEAE-0xFEB1*/
+        1, 0, 1, 0,                   /*0xFEB2-0xFEB5*/
+        1, 0, 2, 1+2,                 /*0xFEB6-0xFEB9*/
+        1, 0, 2, 1+2,                 /*0xFEBA-0xFEBD*/
+        1, 0, 2, 1+2,                 /*0xFEBE-0xFEC1*/
+        1, 0, 2, 1+2,                 /*0xFEC2-0xFEC5*/
+        1, 0, 2, 1+2,                 /*0xFEC6-0xFEC9*/
+        1, 0, 2, 1+2,                 /*0xFECA-0xFECD*/
+        1, 0, 2, 1+2,                 /*0xFECE-0xFED1*/
+        1, 0, 2, 1+2,                 /*0xFED2-0xFED5*/
+        1, 0, 2, 1+2,                 /*0xFED6-0xFED9*/
+        1, 0, 2, 1+2,                 /*0xFEDA-0xFEDD*/
+        1, 0, 2, 1+2,                 /*0xFEDE-0xFEE1*/
+        1, 0 + 16, 2 + 16, 1 + 2 +16, /*0xFEE2-0xFEE5*/
+        1 + 16, 0, 2, 1+2,            /*0xFEE6-0xFEE9*/
+        1, 0, 2, 1+2,                 /*0xFEEA-0xFEED*/
+        1, 0, 2, 1+2,                 /*0xFEEE-0xFEF1*/
+        1, 0, 1, 0,                   /*0xFEF2-0xFEF5*/
+        1, 0, 2, 1+2,                 /*0xFEF6-0xFEF9*/
+        1, 0, 1, 0,                   /*0xFEFA-0xFEFD*/
+        1, 0, 1, 0,
+        1
+    };
+
+    private static int[] convertFEto06 = {
+        /***********0******1******2******3******4******5******6******7******8******9******A******B******C******D******E******F***/
+        /*FE7*/   0x64B, 0x64B, 0x64C, 0x64C, 0x64D, 0x64D, 0x64E, 0x64E, 0x64F, 0x64F, 0x650, 0x650, 0x651, 0x651, 0x652, 0x652,
+        /*FE8*/   0x621, 0x622, 0x622, 0x623, 0x623, 0x624, 0x624, 0x625, 0x625, 0x626, 0x626, 0x626, 0x626, 0x627, 0x627, 0x628,
+        /*FE9*/   0x628, 0x628, 0x628, 0x629, 0x629, 0x62A, 0x62A, 0x62A, 0x62A, 0x62B, 0x62B, 0x62B, 0x62B, 0x62C, 0x62C, 0x62C,
+        /*FEA*/   0x62C, 0x62D, 0x62D, 0x62D, 0x62D, 0x62E, 0x62E, 0x62E, 0x62E, 0x62F, 0x62F, 0x630, 0x630, 0x631, 0x631, 0x632,
+        /*FEB*/   0x632, 0x633, 0x633, 0x633, 0x633, 0x634, 0x634, 0x634, 0x634, 0x635, 0x635, 0x635, 0x635, 0x636, 0x636, 0x636,
+        /*FEC*/   0x636, 0x637, 0x637, 0x637, 0x637, 0x638, 0x638, 0x638, 0x638, 0x639, 0x639, 0x639, 0x639, 0x63A, 0x63A, 0x63A,
+        /*FED*/   0x63A, 0x641, 0x641, 0x641, 0x641, 0x642, 0x642, 0x642, 0x642, 0x643, 0x643, 0x643, 0x643, 0x644, 0x644, 0x644,
+        /*FEE*/   0x644, 0x645, 0x645, 0x645, 0x645, 0x646, 0x646, 0x646, 0x646, 0x647, 0x647, 0x647, 0x647, 0x648, 0x648, 0x649,
+        /*FEF*/   0x649, 0x64A, 0x64A, 0x64A, 0x64A, 0x65C, 0x65C, 0x65D, 0x65D, 0x65E, 0x65E, 0x65F, 0x65F
+    };
+
+    private static final int shapeTable[][][] = {
+        { {0,0,0,0}, {0,0,0,0}, {0,1,0,3}, {0,1,0,1} },
+        { {0,0,2,2}, {0,0,1,2}, {0,1,1,2}, {0,1,1,3} },
+        { {0,0,0,0}, {0,0,0,0}, {0,1,0,3}, {0,1,0,3} },
+        { {0,0,1,2}, {0,0,1,2}, {0,1,1,2}, {0,1,1,3} }
+    };
+
+    /*
+     * This function shapes European digits to Arabic-Indic digits
+     * in-place, writing over the input characters.  Data is in visual
+     * order.
+     */
+    private void shapeToArabicDigitsWithContext(char[] dest,
+                                                int start,
+                                                int length,
+                                                char digitBase,
+                                                boolean lastStrongWasAL) {
+        digitBase -= '0'; // move common adjustment out of loop
+
+        for(int i = start + length; --i >= start;) {
+            char ch = dest[i];
+            switch (Character.getDirectionality(ch)) {
+            case Character.DIRECTIONALITY_LEFT_TO_RIGHT:
+            case Character.DIRECTIONALITY_RIGHT_TO_LEFT:
+                lastStrongWasAL = false;
+                break;
+            case Character.DIRECTIONALITY_RIGHT_TO_LEFT_ARABIC:
+                lastStrongWasAL = true;
+                break;
+            case Character.DIRECTIONALITY_EUROPEAN_NUMBER:
+                if (lastStrongWasAL && ch <= '\u0039') {
+                    dest[i] = (char)(ch + digitBase);
+                }
+                break;
+            default:
+                break;
+            }
+        }
+    }
+
+    /*
+     * Name    : invertBuffer
+     * Function: This function inverts the buffer, it's used
+     *           in case the user specifies the buffer to be
+     *           TEXT_DIRECTION_LOGICAL
+     */
+    private static void invertBuffer(char[] buffer,
+                                     int start,
+                                     int length) {
+
+        for(int i = start, j = start + length - 1; i < j; i++, --j) {
+            char temp = buffer[i];
+            buffer[i] = buffer[j];
+            buffer[j] = temp;
+        }
+    }
+
+    /*
+     * Name    : changeLamAlef
+     * Function: Converts the Alef characters into an equivalent
+     *           LamAlef location in the 0x06xx Range, this is an
+     *           intermediate stage in the operation of the program
+     *           later it'll be converted into the 0xFExx LamAlefs
+     *           in the shaping function.
+     */
+    private static char changeLamAlef(char ch) {
+        switch(ch) {
+        case '\u0622': return '\u065C';
+        case '\u0623': return '\u065D';
+        case '\u0625': return '\u065E';
+        case '\u0627': return '\u065F';
+        default:  return '\u0000'; // not a lamalef
+        }
+    }
+
+    /*
+     * Name    : specialChar
+     * Function: Special Arabic characters need special handling in the shapeUnicode
+     *           function, this function returns 1 or 2 for these special characters
+     */
+    private static int specialChar(char ch) {
+        if ((ch > '\u0621' && ch < '\u0626') ||
+            (ch == '\u0627') ||
+            (ch > '\u062E' && ch < '\u0633') ||
+            (ch > '\u0647' && ch < '\u064A') ||
+            (ch == '\u0629')) {
+            return 1;
+        } else if (ch >= '\u064B' && ch<= '\u0652') {
+            return 2;
+        } else if (ch >= 0x0653 && ch <= 0x0655 ||
+                   ch == 0x0670 ||
+                   ch >= 0xFE70 && ch <= 0xFE7F) {
+            return 3;
+        } else {
+            return 0;
+        }
+    }
+
+    /*
+     * Name    : getLink
+     * Function: Resolves the link between the characters as
+     *           Arabic characters have four forms :
+     *           Isolated, Initial, Middle and Final Form
+     */
+    private static int getLink(char ch) {
+        if (ch >= '\u0622' && ch <= '\u06D3') {
+            return araLink[ch - '\u0622'];
+        } else if (ch == '\u200D') {
+            return 3;
+        } else if (ch >= '\u206D' && ch <= '\u206F') {
+            return 4;
+        } else if (ch >= '\uFE70' && ch <= '\uFEFC') {
+            return presLink[ch - '\uFE70'];
+        } else {
+            return 0;
+        }
+    }
+
+    /*
+     * Name    : countSpaces
+     * Function: Counts the number of spaces
+     *           at each end of the logical buffer
+     */
+    private static int countSpacesLeft(char[] dest,
+                                       int start,
+                                       int count) {
+        for (int i = start, e = start + count; i < e; ++i) {
+            if (dest[i] != SPACE_CHAR) {
+                return i - start;
+            }
+        }
+        return count;
+    }
+
+    private static int countSpacesRight(char[] dest,
+                                        int start,
+                                        int count) {
+
+        for (int i = start + count; --i >= start;) {
+            if (dest[i] != SPACE_CHAR) {
+                return start + count - 1 - i;
+            }
+        }
+        return count;
+    }
+
+    /*
+     * Name    : isTashkeelChar
+     * Function: Returns true for Tashkeel characters else return false
+     */
+    private static boolean isTashkeelChar(char ch) {
+        return ( ch >='\u064B' && ch <= '\u0652' );
+    }
+
+    /*
+     *Name     : isSeenTailFamilyChar
+     *Function : returns 1 if the character is a seen family isolated character
+     *           in the FE range otherwise returns 0
+     */
+
+    private static int isSeenTailFamilyChar(char ch) {
+        if (ch >= 0xfeb1 && ch < 0xfebf){
+             return tailFamilyIsolatedFinal [ch - 0xFEB1];
+        } else {
+             return 0;
+        }
+    }
+
+     /* Name     : isSeenFamilyChar
+      * Function : returns 1 if the character is a seen family character in the Unicode
+      *            06 range otherwise returns 0
+     */
+
+    private static int isSeenFamilyChar(char  ch){
+        if (ch >= 0x633 && ch <= 0x636){
+            return 1;
+        }else {
+            return 0;
+        }
+    }
+
+    /*
+     *Name     : isTailChar
+     *Function : returns true if the character matches one of the tail characters
+     *           (0xfe73 or 0x200b) otherwise returns false
+     */
+
+    private static boolean isTailChar(char ch) {
+        if(ch == OLD_TAIL_CHAR || ch == NEW_TAIL_CHAR){
+                return true;
+        }else{
+                return false;
+        }
+    }
+
+    /*
+     *Name     : isAlefMaksouraChar
+     *Function : returns true if the character is a Alef Maksoura Final or isolated
+     *           otherwise returns false
+     */
+    private static boolean isAlefMaksouraChar(char ch) {
+        return ( (ch == 0xFEEF) || ( ch == 0xFEF0) || (ch == 0x0649));
+    }
+
+    /*
+     * Name     : isYehHamzaChar
+     * Function : returns true if the character is a yehHamza isolated or yehhamza
+     *            final is found otherwise returns false
+     */
+    private static boolean isYehHamzaChar(char ch) {
+        if((ch==0xFE89)||(ch==0xFE8A)){
+            return true;
+        }else{
+            return false;
+        }
+    }
+
+    /*
+     *Name     : isTashkeelCharFE
+     *Function : Returns true for Tashkeel characters in FE range else return false
+     */
+
+    private static boolean isTashkeelCharFE(char ch) {
+        return ( ch!=0xFE75 &&(ch>=0xFE70 && ch<= 0xFE7F) );
+    }
+
+    /*
+     * Name: isTashkeelOnTatweelChar
+     * Function: Checks if the Tashkeel Character is on Tatweel or not,if the
+     *           Tashkeel on tatweel (FE range), it returns 1 else if the
+     *           Tashkeel with shadda on tatweel (FC range)return 2 otherwise
+     *           returns 0
+     */
+    private static int isTashkeelOnTatweelChar(char ch){
+        if (ch >= 0xfe70 && ch <= 0xfe7f && ch != NEW_TAIL_CHAR && ch != 0xFE75 && ch != SHADDA_TATWEEL_CHAR)
+        {
+            return tashkeelMedial [ch - 0xFE70];
+        } else if( (ch >= 0xfcf2 && ch <= 0xfcf4) || (ch == SHADDA_TATWEEL_CHAR)) {
+            return 2;
+        } else {
+            return 0;
+        }
+    }
+
+    /*
+     * Name: isIsolatedTashkeelChar
+     * Function: Checks if the Tashkeel Character is in the isolated form
+     *           (i.e. Unicode FE range) returns 1 else if the Tashkeel
+     *           with shadda is in the isolated form (i.e. Unicode FC range)
+     *           returns 1 otherwise returns 0
+     */
+    private static int isIsolatedTashkeelChar(char ch){
+        if (ch >= 0xfe70 && ch <= 0xfe7f && ch != NEW_TAIL_CHAR && ch != 0xFE75){
+            return (1 - tashkeelMedial [ch - 0xFE70]);
+        } else if(ch >= 0xfc5e && ch <= 0xfc63){
+            return 1;
+        } else{
+            return 0;
+        }
+    }
+
+    /*
+     * Name    : isAlefChar
+     * Function: Returns 1 for Alef characters else return 0
+     */
+    private static boolean isAlefChar(char ch) {
+        return ch == '\u0622' || ch == '\u0623' || ch == '\u0625' || ch == '\u0627';
+    }
+
+    /*
+     * Name    : isLamAlefChar
+     * Function: Returns true for LamAlef characters else return false
+     */
+    private static boolean isLamAlefChar(char ch) {
+        return ch >= '\uFEF5' && ch <= '\uFEFC';
+    }
+
+    private static boolean isNormalizedLamAlefChar(char ch) {
+        return ch >= '\u065C' && ch <= '\u065F';
+    }
+
+    /*
+     * Name    : calculateSize
+     * Function: This function calculates the destSize to be used in preflighting
+     *           when the destSize is equal to 0
+     */
+    private int calculateSize(char[] source,
+                              int sourceStart,
+                              int sourceLength) {
+
+        int destSize = sourceLength;
+
+        switch (options & LETTERS_MASK) {
+        case LETTERS_SHAPE:
+        case LETTERS_SHAPE_TASHKEEL_ISOLATED:
+            if (isLogical) {
+                for (int i = sourceStart, e = sourceStart + sourceLength - 1; i < e; ++i) {
+                    if ((source[i] == LAM_CHAR && isAlefChar(source[i+1])) || isTashkeelCharFE(source[i])){
+                        --destSize;
+                    }
+                }
+            } else { // visual
+                for(int i = sourceStart + 1, e = sourceStart + sourceLength; i < e; ++i) {
+                    if ((source[i] == LAM_CHAR && isAlefChar(source[i-1])) || isTashkeelCharFE(source[i])) {
+                        --destSize;
+                    }
+                }
+            }
+            break;
+
+        case LETTERS_UNSHAPE:
+            for(int i = sourceStart, e = sourceStart + sourceLength; i < e; ++i) {
+                if (isLamAlefChar(source[i])) {
+                    destSize++;
+                }
+            }
+            break;
+
+        default:
+            break;
+        }
+
+        return destSize;
+    }
+
+
+    /*
+     * Name    : countSpaceSub
+     * Function: Counts number of times the subChar appears in the array
+     */
+    public static int countSpaceSub(char [] dest,int length, char subChar){
+        int i = 0;
+        int count = 0;
+        while (i < length) {
+          if (dest[i] == subChar) {
+              count++;
+              }
+          i++;
+        }
+        return count;
+    }
+
+    /*
+     * Name    : shiftArray
+     * Function: Shifts characters to replace space sub characters
+     */
+    public static void shiftArray(char [] dest,int start, int e, char subChar){
+        int w = e;
+        int r = e;
+        while (--r >= start) {
+          char ch = dest[r];
+          if (ch != subChar) {
+            --w;
+            if (w != r) {
+              dest[w] = ch;
+            }
+          }
+        }
+   }
+
+    /*
+     * Name    : flipArray
+     * Function: inverts array, so that start becomes end and vice versa
+     */
+      public static int flipArray(char [] dest, int start, int e, int w){
+        int r;
+        if (w > start) {
+        // shift, assume small buffer size so don't use arraycopy
+          r = w;
+          w = start;
+          while (r < e) {
+            dest[w++] = dest[r++];
+           }
+         } else {
+             w = e;
+         }
+        return w;
+      }
+
+    /*
+     * Name     : handleTashkeelWithTatweel
+     * Function : Replaces Tashkeel as following:
+     *            Case 1 :if the Tashkeel on tatweel, replace it with Tatweel.
+     *            Case 2 :if the Tashkeel aggregated with Shadda on Tatweel, replace
+     *                   it with Shadda on Tatweel.
+     *            Case 3: if the Tashkeel is isolated replace it with Space.
+     *
+     */
+    private static int handleTashkeelWithTatweel(char[] dest, int sourceLength) {
+                     int i;
+                     for(i = 0; i < sourceLength; i++){
+                         if((isTashkeelOnTatweelChar(dest[i]) == 1)){
+                             dest[i] = TATWEEL_CHAR;
+                        }else if((isTashkeelOnTatweelChar(dest[i]) == 2)){
+                             dest[i] = SHADDA_TATWEEL_CHAR;
+                        }else if((isIsolatedTashkeelChar(dest[i])==1) && dest[i] != SHADDA_CHAR){
+                             dest[i] = SPACE_CHAR;
+                        }
+                     }
+                     return sourceLength;
+    }
+
+    /*
+     *Name     : handleGeneratedSpaces
+     *Function : The shapeUnicode function converts Lam + Alef into LamAlef + space,
+     *           and Tashkeel to space.
+     *           handleGeneratedSpaces function puts these generated spaces
+     *           according to the options the user specifies. LamAlef and Tashkeel
+     *           spaces can be replaced at begin, at end, at near or decrease the
+     *           buffer size.
+     *
+     *           There is also Auto option for LamAlef and tashkeel, which will put
+     *           the spaces at end of the buffer (or end of text if the user used
+     *           the option SPACES_RELATIVE_TO_TEXT_BEGIN_END).
+     *
+     *           If the text type was visual_LTR and the option
+     *           SPACES_RELATIVE_TO_TEXT_BEGIN_END was selected the END
+     *           option will place the space at the beginning of the buffer and
+     *           BEGIN will place the space at the end of the buffer.
+     */
+  private int handleGeneratedSpaces(char[] dest,
+            int start,
+            int length) {
+
+      int lenOptionsLamAlef = options & LAMALEF_MASK;
+      int lenOptionsTashkeel = options & TASHKEEL_MASK;
+      boolean lamAlefOn = false;
+      boolean tashkeelOn = false;
+
+      if (!isLogical & !spacesRelativeToTextBeginEnd) {
+          switch (lenOptionsLamAlef) {
+          case LAMALEF_BEGIN: lenOptionsLamAlef = LAMALEF_END; break;
+          case LAMALEF_END: lenOptionsLamAlef = LAMALEF_BEGIN; break;
+          default: break;
+         }
+          switch (lenOptionsTashkeel){
+          case TASHKEEL_BEGIN: lenOptionsTashkeel = TASHKEEL_END; break;
+          case TASHKEEL_END: lenOptionsTashkeel = TASHKEEL_BEGIN; break;
+          default: break;
+          }
+        }
+
+
+      if (lenOptionsLamAlef == LAMALEF_NEAR) {
+          for (int i = start, e = i + length; i < e; ++i) {
+              if (dest[i] == LAMALEF_SPACE_SUB) {
+                  dest[i] = SPACE_CHAR_FOR_LAMALEF;
+              }
+          }
+
+      } else {
+
+          final int e = start + length;
+          int wL = countSpaceSub(dest, length, LAMALEF_SPACE_SUB);
+          int wT = countSpaceSub(dest, length, TASHKEEL_SPACE_SUB);
+
+          if (lenOptionsLamAlef == LAMALEF_END){
+            lamAlefOn = true;
+          }
+          if (lenOptionsTashkeel == TASHKEEL_END){
+            tashkeelOn = true;
+          }
+
+
+          if (lamAlefOn && (lenOptionsLamAlef == LAMALEF_END)) {
+            shiftArray(dest, start, e, LAMALEF_SPACE_SUB);
+            while (wL > start) {
+                dest[--wL] = SPACE_CHAR;
+            }
+          }
+
+          if (tashkeelOn && (lenOptionsTashkeel == TASHKEEL_END)){
+            shiftArray(dest, start, e, TASHKEEL_SPACE_SUB);
+            while (wT > start) {
+                 dest[--wT] = SPACE_CHAR;
+            }
+          }
+
+          lamAlefOn = false;
+          tashkeelOn = false;
+
+          if (lenOptionsLamAlef == LAMALEF_RESIZE){
+            lamAlefOn = true;
+          }
+          if (lenOptionsTashkeel == TASHKEEL_RESIZE){
+            tashkeelOn = true;
+          }
+
+          if (lamAlefOn && (lenOptionsLamAlef == LAMALEF_RESIZE)){
+              shiftArray(dest, start, e, LAMALEF_SPACE_SUB);
+              wL = flipArray(dest,start,e, wL);
+              length = wL - start;
+          }
+          if (tashkeelOn && (lenOptionsTashkeel == TASHKEEL_RESIZE)) {
+              shiftArray(dest, start, e, TASHKEEL_SPACE_SUB);
+              wT = flipArray(dest,start,e, wT);
+              length = wT - start;
+          }
+
+          lamAlefOn = false;
+          tashkeelOn = false;
+
+          if ((lenOptionsLamAlef == LAMALEF_BEGIN) ||
+              (lenOptionsLamAlef == LAMALEF_AUTO)){
+                lamAlefOn = true;
+          }
+          if (lenOptionsTashkeel == TASHKEEL_BEGIN){
+                tashkeelOn = true;
+          }
+
+          if (lamAlefOn && ((lenOptionsLamAlef == LAMALEF_BEGIN)||
+                            (lenOptionsLamAlef == LAMALEF_AUTO))) { // spaces at beginning
+              shiftArray(dest, start, e, LAMALEF_SPACE_SUB);
+               wL = flipArray(dest,start,e, wL);
+                  while (wL < e) {
+                      dest[wL++] = SPACE_CHAR;
+                  }
+              }
+              if(tashkeelOn && (lenOptionsTashkeel == TASHKEEL_BEGIN)){
+               shiftArray(dest, start, e, TASHKEEL_SPACE_SUB);
+               wT = flipArray(dest,start,e, wT);
+                  while (wT < e) {
+                      dest[wT++] = SPACE_CHAR;
+                  }
+              }
+           }
+
+      return length;
+  }
+
+
+  /*
+   *Name     :expandCompositCharAtBegin
+   *Function :Expands the LamAlef character to Lam and Alef consuming the required
+   *         space from beginning of the buffer. If the text type was visual_LTR
+   *         and the option SPACES_RELATIVE_TO_TEXT_BEGIN_END was selected
+   *         the spaces will be located at end of buffer.
+   *         If there are no spaces to expand the LamAlef, an exception is thrown.
+*/
+ private boolean expandCompositCharAtBegin(char[] dest,int start, int length,
+                            int lacount) {
+     boolean spaceNotFound = false;
+
+     if (lacount > countSpacesRight(dest, start, length)) {
+         spaceNotFound = true;
+         return spaceNotFound;
+     }
+     for (int r = start + length - lacount, w = start + length; --r >= start;) {
+         char ch = dest[r];
+         if (isNormalizedLamAlefChar(ch)) {
+             dest[--w] = LAM_CHAR;
+             dest[--w] = convertNormalizedLamAlef[ch - '\u065C'];
+         } else {
+             dest[--w] = ch;
+         }
+     }
+     return spaceNotFound;
+
+  }
+
+  /*
+   *Name     : expandCompositCharAtEnd
+   *Function : Expands the LamAlef character to Lam and Alef consuming the
+   *           required space from end of the buffer. If the text type was
+   *           Visual LTR and the option SPACES_RELATIVE_TO_TEXT_BEGIN_END
+   *           was used, the spaces will be consumed from begin of buffer. If
+   *           there are no spaces to expand the LamAlef, an exception is thrown.
+   */
+
+  private boolean  expandCompositCharAtEnd(char[] dest,int start, int length,
+                          int lacount){
+      boolean spaceNotFound = false;
+
+      if (lacount > countSpacesLeft(dest, start, length)) {
+          spaceNotFound = true;
+          return spaceNotFound;
+      }
+      for (int r = start + lacount, w = start, e = start + length; r < e; ++r) {
+          char ch = dest[r];
+          if (isNormalizedLamAlefChar(ch)) {
+              dest[w++] = convertNormalizedLamAlef[ch - '\u065C'];
+              dest[w++] = LAM_CHAR;
+          } else {
+              dest[w++] = ch;
+          }
+      }
+      return spaceNotFound;
+  }
+
+  /*
+   *Name     : expandCompositCharAtNear
+   *Function : Expands the LamAlef character into Lam + Alef, YehHamza character
+   *           into Yeh + Hamza, SeenFamily character into SeenFamily character
+   *           + Tail, while consuming the space next to the character.
+   */
+
+  private boolean expandCompositCharAtNear(char[] dest,int start, int length,
+                                       int yehHamzaOption, int seenTailOption, int lamAlefOption){
+
+      boolean spaceNotFound = false;
+
+
+
+      if (isNormalizedLamAlefChar(dest[start])) {
+          spaceNotFound = true;
+          return spaceNotFound;
+      }
+      for (int i = start + length; --i >=start;) {
+          char ch = dest[i];
+          if (lamAlefOption == 1 && isNormalizedLamAlefChar(ch)) {
+              if (i>start &&dest[i-1] == SPACE_CHAR) {
+                  dest[i] = LAM_CHAR;
+                  dest[--i] = convertNormalizedLamAlef[ch - '\u065C'];
+              } else {
+                  spaceNotFound = true;
+                  return spaceNotFound;
+              }
+          }else if(seenTailOption == 1 && isSeenTailFamilyChar(ch) == 1){
+              if(i>start &&dest[i-1] == SPACE_CHAR){
+                  dest[i-1] = tailChar;
+              } else{
+                  spaceNotFound = true;
+                  return spaceNotFound;
+              }
+          }else if(yehHamzaOption == 1 && isYehHamzaChar(ch)){
+
+               if(i>start &&dest[i-1] == SPACE_CHAR){
+                  dest[i] = yehHamzaToYeh[ch - YEH_HAMZAFE_CHAR];
+                  dest[i-1] = HAMZAFE_CHAR;
+              }else{
+                  spaceNotFound = true;
+                  return spaceNotFound;
+                }
+
+
+          }
+      }
+      return false;
+
+  }
+
+    /*
+     * Name    : expandCompositChar
+     * Function: LamAlef needs special handling as the LamAlef is
+     *           one character while expanding it will give two
+     *           characters Lam + Alef, so we need to expand the LamAlef
+     *           in near or far spaces according to the options the user
+     *           specifies or increase the buffer size.
+     *           Dest has enough room for the expansion if we are growing.
+     *           lamalef are normalized to the 'special characters'
+     */
+    private int expandCompositChar(char[] dest,
+                              int start,
+                              int length,
+                              int lacount,
+                              int shapingMode) throws ArabicShapingException {
+
+        int lenOptionsLamAlef = options & LAMALEF_MASK;
+        int lenOptionsSeen = options & SEEN_MASK;
+        int lenOptionsYehHamza = options & YEHHAMZA_MASK;
+        boolean spaceNotFound = false;
+
+        if (!isLogical && !spacesRelativeToTextBeginEnd) {
+            switch (lenOptionsLamAlef) {
+            case LAMALEF_BEGIN: lenOptionsLamAlef = LAMALEF_END; break;
+            case LAMALEF_END: lenOptionsLamAlef = LAMALEF_BEGIN; break;
+            default: break;
+            }
+        }
+
+        if(shapingMode == 1){
+            if(lenOptionsLamAlef == LAMALEF_AUTO){
+                if(isLogical){
+                    spaceNotFound = expandCompositCharAtEnd(dest, start, length, lacount);
+                    if(spaceNotFound){
+                        spaceNotFound = expandCompositCharAtBegin(dest, start, length, lacount);
+                    }
+                    if(spaceNotFound){
+                        spaceNotFound = expandCompositCharAtNear(dest, start, length,0,0,1);
+                    }
+                    if(spaceNotFound){
+                        throw new ArabicShapingException("No spacefor lamalef");
+                    }
+                }else{
+                    spaceNotFound = expandCompositCharAtBegin(dest, start, length, lacount);
+                    if(spaceNotFound){
+                        spaceNotFound = expandCompositCharAtEnd(dest, start, length, lacount);
+                    }
+                    if(spaceNotFound){
+                        spaceNotFound = expandCompositCharAtNear(dest, start, length,0,0,1);
+                    }
+                    if(spaceNotFound){
+                        throw new ArabicShapingException("No spacefor lamalef");
+                    }
+                }
+            }else if(lenOptionsLamAlef == LAMALEF_END){
+                spaceNotFound = expandCompositCharAtEnd(dest, start, length, lacount);
+                if(spaceNotFound){
+                    throw new ArabicShapingException("No spacefor lamalef");
+                }
+            }else if(lenOptionsLamAlef == LAMALEF_BEGIN){
+                spaceNotFound = expandCompositCharAtBegin(dest, start, length, lacount);
+                if(spaceNotFound){
+                    throw new ArabicShapingException("No spacefor lamalef");
+                }
+            }else if(lenOptionsLamAlef == LAMALEF_NEAR){
+                spaceNotFound = expandCompositCharAtNear(dest, start, length,0,0,1);
+                if(spaceNotFound){
+                    throw new ArabicShapingException("No spacefor lamalef");
+            }
+            }else if(lenOptionsLamAlef == LAMALEF_RESIZE){
+                for (int r = start + length, w = r + lacount; --r >= start;) {
+                    char ch = dest[r];
+                    if (isNormalizedLamAlefChar(ch)) {
+                        dest[--w] = '\u0644';
+                        dest[--w] = convertNormalizedLamAlef[ch - '\u065C'];
+                    } else {
+                        dest[--w] = ch;
+                    }
+                }
+                length += lacount;
+            }
+            }else{
+                if(lenOptionsSeen == SEEN_TWOCELL_NEAR){
+                spaceNotFound = expandCompositCharAtNear(dest, start, length,0,1,0);
+                if(spaceNotFound){
+                    throw new ArabicShapingException("No space for Seen tail expansion");
+                }
+            }
+            if(lenOptionsYehHamza == YEHHAMZA_TWOCELL_NEAR){
+                spaceNotFound = expandCompositCharAtNear(dest, start, length,1,0,0);
+                if(spaceNotFound){
+                    throw new ArabicShapingException("No space for YehHamza expansion");
+                }
+            }
+            }
+        return length;
+    }
+
+
+    /* Convert the input buffer from FExx Range into 06xx Range
+     * to put all characters into the 06xx range
+     * even the lamalef is converted to the special region in
+     * the 06xx range.  Return the number of lamalef chars found.
+     */
+    private int normalize(char[] dest, int start, int length) {
+        int lacount = 0;
+        for (int i = start, e = i + length; i < e; ++i) {
+            char ch = dest[i];
+            if (ch >= '\uFE70' && ch <= '\uFEFC') {
+                if (isLamAlefChar(ch)) {
+                    ++lacount;
+                }
+                dest[i] = (char)convertFEto06[ch - '\uFE70'];
+            }
+        }
+        return lacount;
+    }
+
+    /*
+     * Name    : deshapeNormalize
+     * Function: Convert the input buffer from FExx Range into 06xx Range
+     *           even the lamalef is converted to the special region in the 06xx range.
+     *           According to the options the user enters, all seen family characters
+     *           followed by a tail character are merged to seen tail family character and
+     *           any yeh followed by a hamza character are merged to yehhamza character.
+     *           Method returns the number of lamalef chars found.
+     */
+    private int deshapeNormalize(char[] dest, int start, int length) {
+        int lacount = 0;
+        int yehHamzaComposeEnabled = 0;
+        int seenComposeEnabled = 0;
+
+        yehHamzaComposeEnabled = ((options&YEHHAMZA_MASK) == YEHHAMZA_TWOCELL_NEAR) ? 1 : 0;
+        seenComposeEnabled = ((options&SEEN_MASK) == SEEN_TWOCELL_NEAR)? 1 : 0;
+
+        for (int i = start, e = i + length; i < e; ++i) {
+            char ch = dest[i];
+
+        if( (yehHamzaComposeEnabled == 1) && ((ch == HAMZA06_CHAR) || (ch == HAMZAFE_CHAR))
+               && (i < (length - 1)) && isAlefMaksouraChar(dest[i+1] )) {
+                dest[i] = SPACE_CHAR;
+                dest[i+1] = YEH_HAMZA_CHAR;
+       } else if ( (seenComposeEnabled == 1) && (isTailChar(ch)) && (i< (length - 1))
+                       && (isSeenTailFamilyChar(dest[i+1])==1) ) {
+               dest[i] = SPACE_CHAR;
+       }
+       else if (ch >= '\uFE70' && ch <= '\uFEFC') {
+                if (isLamAlefChar(ch)) {
+                    ++lacount;
+                }
+                dest[i] = (char)convertFEto06[ch - '\uFE70'];
+            }
+        }
+        return lacount;
+    }
+
+    /*
+     * Name    : shapeUnicode
+     * Function: Converts an Arabic Unicode buffer in 06xx Range into a shaped
+     *           arabic Unicode buffer in FExx Range
+     */
+    private int shapeUnicode(char[] dest,
+                             int start,
+                             int length,
+                             int destSize,
+                             int tashkeelFlag)throws ArabicShapingException {
+
+        int lamalef_count = normalize(dest, start, length);
+
+        // resolve the link between the characters.
+        // Arabic characters have four forms: Isolated, Initial, Medial and Final.
+        // Tashkeel characters have two, isolated or medial, and sometimes only isolated.
+        // tashkeelFlag == 0: shape normally, 1: shape isolated, 2: don't shape
+
+        boolean lamalef_found = false, seenfam_found = false;
+        boolean yehhamza_found = false, tashkeel_found = false;
+        int i = start + length - 1;
+        int currLink = getLink(dest[i]);
+        int nextLink = 0;
+        int prevLink = 0;
+        int lastLink = 0;
+        //int prevPos = i;
+        int lastPos = i;
+        int nx = -2;
+        int nw = 0;
+
+        while (i >= 0) {
+            // If high byte of currLink > 0 then there might be more than one shape
+            if ((currLink & '\uFF00') > 0 || isTashkeelChar(dest[i])) {
+                nw = i - 1;
+                nx = -2;
+                while (nx < 0) { // we need to know about next char
+                    if (nw == -1) {
+                        nextLink = 0;
+                        nx = Integer.MAX_VALUE;
+                    } else {
+                        nextLink = getLink(dest[nw]);
+                        if ((nextLink & IRRELEVANT) == 0) {
+                            nx = nw;
+                        } else {
+                            --nw;
+                        }
+                    }
+                }
+
+                if (((currLink & ALEFTYPE) > 0) && ((lastLink & LAMTYPE) > 0)) {
+                    lamalef_found = true;
+                    char wLamalef = changeLamAlef(dest[i]); // get from 0x065C-0x065f
+                    if (wLamalef != '\u0000') {
+                        // replace alef by marker, it will be removed later
+                        dest[i] = '\uffff';
+                        dest[lastPos] = wLamalef;
+                        i = lastPos;
+                    }
+
+                    lastLink = prevLink;
+                    currLink = getLink(wLamalef); // requires '\u0000', unfortunately
+                }
+                if ((i > 0) && (dest[i-1] == SPACE_CHAR))
+                {
+                    if ( isSeenFamilyChar(dest[i]) == 1){
+                        seenfam_found = true;
+                    } else if (dest[i] == YEH_HAMZA_CHAR) {
+                        yehhamza_found = true;
+                    }
+                }
+                else if(i==0){
+                    if ( isSeenFamilyChar(dest[i]) == 1){
+                        seenfam_found = true;
+                    } else if (dest[i] == YEH_HAMZA_CHAR) {
+                        yehhamza_found = true;
+                    }
+                }
+
+
+                // get the proper shape according to link ability of neighbors
+                // and of character; depends on the order of the shapes
+                // (isolated, initial, middle, final) in the compatibility area
+
+                int flag = specialChar(dest[i]);
+
+                int shape = shapeTable[nextLink & LINK_MASK]
+                    [lastLink & LINK_MASK]
+                    [currLink & LINK_MASK];
+
+                if (flag == 1) {
+                    shape &= 0x1;
+                } else if (flag == 2) {
+                    if (tashkeelFlag == 0 &&
+                        ((lastLink & LINKL) != 0) &&
+                        ((nextLink & LINKR) != 0) &&
+                        dest[i] != '\u064C' &&
+                        dest[i] != '\u064D' &&
+                        !((nextLink & ALEFTYPE) == ALEFTYPE &&
+                          (lastLink & LAMTYPE) == LAMTYPE)) {
+
+                        shape = 1;
+                    } else {
+                        shape = 0;
+                    }
+                }
+                if (flag == 2) {
+                    if (tashkeelFlag == 2) {
+                        dest[i] = TASHKEEL_SPACE_SUB;
+                        tashkeel_found = true;
+                    }
+                    else{
+                        dest[i] = (char)('\uFE70' + irrelevantPos[dest[i] - '\u064B'] + shape);
+                    }
+                    // else leave tashkeel alone
+                } else {
+                    dest[i] = (char)('\uFE70' + (currLink >> 8) + shape);
+                }
+            }
+
+            // move one notch forward
+            if ((currLink & IRRELEVANT) == 0) {
+                prevLink = lastLink;
+                lastLink = currLink;
+                //prevPos = lastPos;
+                lastPos = i;
+            }
+
+            --i;
+            if (i == nx) {
+                currLink = nextLink;
+                nx = -2;
+            } else if (i != -1) {
+                currLink = getLink(dest[i]);
+            }
+        }
+
+        // If we found a lam/alef pair in the buffer
+        // call handleGeneratedSpaces to remove the spaces that were added
+
+        destSize = length;
+        if (lamalef_found || tashkeel_found) {
+            destSize = handleGeneratedSpaces(dest, start, length);
+        }
+        if (seenfam_found || yehhamza_found){
+            destSize = expandCompositChar(dest, start, destSize, lamalef_count, SHAPE_MODE);
+        }
+        return destSize;
+    }
+
+    /*
+     * Name    : deShapeUnicode
+     * Function: Converts an Arabic Unicode buffer in FExx Range into unshaped
+     *           arabic Unicode buffer in 06xx Range
+     */
+    private int deShapeUnicode(char[] dest,
+                               int start,
+                               int length,
+                               int destSize) throws ArabicShapingException {
+
+        int lamalef_count = deshapeNormalize(dest, start, length);
+
+        // If there was a lamalef in the buffer call expandLamAlef
+        if (lamalef_count != 0) {
+            // need to adjust dest to fit expanded buffer... !!!
+            destSize = expandCompositChar(dest, start, length, lamalef_count,DESHAPE_MODE);
+        } else {
+            destSize = length;
+        }
+
+        return destSize;
+    }
+
+    private int internalShape(char[] source,
+                              int sourceStart,
+                              int sourceLength,
+                              char[] dest,
+                              int destStart,
+                              int destSize) throws ArabicShapingException {
+
+        if (sourceLength == 0) {
+            return 0;
+        }
+
+        if (destSize == 0) {
+            if (((options & LETTERS_MASK) != LETTERS_NOOP) &&
+                ((options & LAMALEF_MASK) == LAMALEF_RESIZE)) {
+
+                return calculateSize(source, sourceStart, sourceLength);
+            } else {
+                return sourceLength; // by definition
+            }
+        }
+
+        // always use temp buffer
+        char[] temp = new char[sourceLength * 2]; // all lamalefs requiring expansion
+        System.arraycopy(source, sourceStart, temp, 0, sourceLength);
+
+        if (isLogical) {
+            invertBuffer(temp, 0, sourceLength);
+        }
+
+        int outputSize = sourceLength;
+
+        switch (options & LETTERS_MASK) {
+        case LETTERS_SHAPE_TASHKEEL_ISOLATED:
+            outputSize = shapeUnicode(temp, 0, sourceLength, destSize, 1);
+            break;
+
+        case LETTERS_SHAPE:
+            if( ((options&TASHKEEL_MASK)> 0) &&
+                ((options&TASHKEEL_MASK) !=TASHKEEL_REPLACE_BY_TATWEEL)) {
+                   /* Call the shaping function with tashkeel flag == 2 for removal of tashkeel */
+                outputSize = shapeUnicode(temp, 0, sourceLength, destSize, 2);
+                }else {
+                   //default Call the shaping function with tashkeel flag == 1 */
+                    outputSize = shapeUnicode(temp, 0, sourceLength, destSize, 0);
+
+                   /*After shaping text check if user wants to remove tashkeel and replace it with tatweel*/
+                   if( (options&TASHKEEL_MASK) == TASHKEEL_REPLACE_BY_TATWEEL){
+                       outputSize = handleTashkeelWithTatweel(temp,sourceLength);
+                   }
+               }
+            break;
+
+        case LETTERS_UNSHAPE:
+            outputSize = deShapeUnicode(temp, 0, sourceLength, destSize);
+            break;
+
+        default:
+            break;
+        }
+
+        if (outputSize > destSize) {
+            throw new ArabicShapingException("not enough room for result data");
+        }
+
+        if ((options & DIGITS_MASK) != DIGITS_NOOP) {
+            char digitBase = '\u0030'; // European digits
+            switch (options & DIGIT_TYPE_MASK) {
+            case DIGIT_TYPE_AN:
+                digitBase = '\u0660';  // Arabic-Indic digits
+                break;
+
+            case DIGIT_TYPE_AN_EXTENDED:
+                digitBase = '\u06f0';  // Eastern Arabic-Indic digits (Persian and Urdu)
+                break;
+
+            default:
+                break;
+            }
+
+            switch (options & DIGITS_MASK) {
+            case DIGITS_EN2AN:
+                {
+                    int digitDelta = digitBase - '\u0030';
+                    for (int i = 0; i < outputSize; ++i) {
+                        char ch = temp[i];
+                        if (ch <= '\u0039' && ch >= '\u0030') {
+                            temp[i] += digitDelta;
+                        }
+                    }
+                }
+                break;
+
+            case DIGITS_AN2EN:
+                {
+                    char digitTop = (char)(digitBase + 9);
+                    int digitDelta = '\u0030' - digitBase;
+                    for (int i = 0; i < outputSize; ++i) {
+                        char ch = temp[i];
+                        if (ch <= digitTop && ch >= digitBase) {
+                            temp[i] += digitDelta;
+                        }
+                    }
+                }
+                break;
+
+            case DIGITS_EN2AN_INIT_LR:
+                shapeToArabicDigitsWithContext(temp, 0, outputSize, digitBase, false);
+                break;
+
+            case DIGITS_EN2AN_INIT_AL:
+                shapeToArabicDigitsWithContext(temp, 0, outputSize, digitBase, true);
+                break;
+
+            default:
+                break;
+            }
+        }
+
+        if (isLogical) {
+            invertBuffer(temp, 0, outputSize);
+        }
+
+        System.arraycopy(temp, 0, dest, destStart, outputSize);
+
+        return outputSize;
+    }
+
+    private static class ArabicShapingException extends RuntimeException {
+        ArabicShapingException(String msg) {
+            super(msg);
+        }
+    }
+}
diff --git a/icu4j/license.html b/icu4j/license.html
new file mode 100644
index 0000000..b905ddf
--- /dev/null
+++ b/icu4j/license.html
@@ -0,0 +1,51 @@
+<html>
+
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></meta>
+<title>ICU License - ICU 1.8.1 and later</title>
+</head>
+
+<body BGCOLOR="#ffffff">
+<h2>ICU License - ICU 1.8.1 and later</h2>
+
+<p>COPYRIGHT AND PERMISSION NOTICE</p>
+
+<p>
+Copyright (c) 1995-2006 International Business Machines Corporation and others
+</p>
+<p>
+All rights reserved.
+</p>
+<p>
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"),
+to deal in the Software without restriction, including without limitation
+the rights to use, copy, modify, merge, publish, distribute, and/or sell
+copies of the Software, and to permit persons
+to whom the Software is furnished to do so, provided that the above
+copyright notice(s) and this permission notice appear in all copies
+of the Software and that both the above copyright notice(s) and this
+permission notice appear in supporting documentation.
+</p>
+<p>
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
+INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. IN NO EVENT SHALL
+THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM,
+OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER
+RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE
+USE OR PERFORMANCE OF THIS SOFTWARE.
+</p>
+<p>
+Except as contained in this notice, the name of a copyright holder shall not be
+used in advertising or otherwise to promote the sale, use or other dealings in
+this Software without prior written authorization of the copyright holder.
+</p>
+
+<hr>
+<p><small>
+All trademarks and registered trademarks mentioned herein are the property of their respective owners.
+</small></p>
+</body>
+</html>