1dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt/* 2dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * Copyright (C) 2010 The Android Open Source Project 3dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * 4dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * Licensed under the Apache License, Version 2.0 (the "License"); 5dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * you may not use this file except in compliance with the License. 6dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * You may obtain a copy of the License at 7dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * 8dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * http://www.apache.org/licenses/LICENSE-2.0 9dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * 10dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * Unless required by applicable law or agreed to in writing, software 11dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * distributed under the License is distributed on an "AS IS" BASIS, 12dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * See the License for the specific language governing permissions and 14dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * limitations under the License. 15dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt */ 16dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt 17dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Feltpackage android.text; 18dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt 19a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournaderimport android.icu.lang.UCharacter; 20a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournaderimport android.icu.lang.UCharacterDirection; 21a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournaderimport android.icu.lang.UProperty; 22a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournaderimport android.icu.text.Bidi; 23a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournaderimport android.icu.text.BidiClassifier; 24e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Feltimport android.text.Layout.Directions; 25e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 26ed09ae1fccfb1c02109a0c1428ddff52daa939d5Siyamed Sinirimport com.android.internal.annotations.VisibleForTesting; 27ed09ae1fccfb1c02109a0c1428ddff52daa939d5Siyamed Sinir 28dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt/** 29dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * Access the ICU bidi implementation. 30dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt * @hide 31dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt */ 32ed09ae1fccfb1c02109a0c1428ddff52daa939d5Siyamed Sinir@VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE) 33ed09ae1fccfb1c02109a0c1428ddff52daa939d5Siyamed Sinirpublic class AndroidBidi { 34dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt 35adcb6cac12b5af9d632a4ecbb30bdeac32e22a01Siyamed Sinir /** 36adcb6cac12b5af9d632a4ecbb30bdeac32e22a01Siyamed Sinir * Overrides ICU {@link BidiClassifier} in order to correctly handle character directions for 37adcb6cac12b5af9d632a4ecbb30bdeac32e22a01Siyamed Sinir * newest emoji that ICU is not aware of. 38adcb6cac12b5af9d632a4ecbb30bdeac32e22a01Siyamed Sinir */ 39adcb6cac12b5af9d632a4ecbb30bdeac32e22a01Siyamed Sinir public static class EmojiBidiOverride extends BidiClassifier { 40adcb6cac12b5af9d632a4ecbb30bdeac32e22a01Siyamed Sinir public EmojiBidiOverride() { 41a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader super(null /* No persisting object needed */); 42a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader } 43a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader 44a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader // Tells ICU to use the standard Unicode value. 45a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader private static final int NO_OVERRIDE = 46a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader UCharacter.getIntPropertyMaxValue(UProperty.BIDI_CLASS) + 1; 47a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader 48a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader @Override 49a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader public int classify(int c) { 50a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader if (Emoji.isNewEmoji(c)) { 51a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader // All new emoji characters in Unicode 10.0 are of the bidi class ON. 52a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader return UCharacterDirection.OTHER_NEUTRAL; 53a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader } else { 54a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader return NO_OVERRIDE; 55a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader } 56a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader } 57a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader } 58a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader 59a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader private static final EmojiBidiOverride sEmojiBidiOverride = new EmojiBidiOverride(); 60a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader 61a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader /** 62a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader * Runs the bidi algorithm on input text. 63a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader */ 64a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader public static int bidi(int dir, char[] chs, byte[] chInfo) { 65dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt if (chs == null || chInfo == null) { 66dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt throw new NullPointerException(); 67dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt } 68dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt 69a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader final int length = chs.length; 70a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader if (chInfo.length < length) { 71dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt throw new IndexOutOfBoundsException(); 72dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt } 73dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt 74a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader final byte paraLevel; 75a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader switch (dir) { 76a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader case Layout.DIR_REQUEST_LTR: paraLevel = Bidi.LTR; break; 77a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader case Layout.DIR_REQUEST_RTL: paraLevel = Bidi.RTL; break; 78a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader case Layout.DIR_REQUEST_DEFAULT_LTR: paraLevel = Bidi.LEVEL_DEFAULT_LTR; break; 79a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader case Layout.DIR_REQUEST_DEFAULT_RTL: paraLevel = Bidi.LEVEL_DEFAULT_RTL; break; 80a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader default: paraLevel = Bidi.LTR; break; 81dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt } 82a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader final Bidi icuBidi = new Bidi(length /* maxLength */, 0 /* maxRunCount */); 83a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader icuBidi.setCustomClassifier(sEmojiBidiOverride); 84a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader icuBidi.setPara(chs, paraLevel, null /* embeddingLevels */); 85a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader for (int i = 0; i < length; i++) { 86a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader chInfo[i] = icuBidi.getLevelAt(i); 87a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader } 88a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader final byte result = icuBidi.getParaLevel(); 89a15fd848cb21242fd362f3299bb819bf2a400c20Roozbeh Pournader return (result & 0x1) == 0 ? Layout.DIR_LEFT_TO_RIGHT : Layout.DIR_RIGHT_TO_LEFT; 90dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt } 91dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt 92e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt /** 93e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * Returns run direction information for a line within a paragraph. 94e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * 95e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @param dir base line direction, either Layout.DIR_LEFT_TO_RIGHT or 96e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * Layout.DIR_RIGHT_TO_LEFT 97e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @param levels levels as returned from {@link #bidi} 98e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @param lstart start of the line in the levels array 99e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @param chars the character array (used to determine whitespace) 100e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @param cstart the start of the line in the chars array 101e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @param len the length of the line 102e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt * @return the directions 103e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt */ 104e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt public static Directions directions(int dir, byte[] levels, int lstart, 105e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt char[] chars, int cstart, int len) { 10668669a42fb78682945a9974e50d18cd86fee9607Raph Levien if (len == 0) { 10768669a42fb78682945a9974e50d18cd86fee9607Raph Levien return Layout.DIRS_ALL_LEFT_TO_RIGHT; 10868669a42fb78682945a9974e50d18cd86fee9607Raph Levien } 109e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 110e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int baseLevel = dir == Layout.DIR_LEFT_TO_RIGHT ? 0 : 1; 111e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int curLevel = levels[lstart]; 112e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int minLevel = curLevel; 113e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int runCount = 1; 114e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt for (int i = lstart + 1, e = lstart + len; i < e; ++i) { 115e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int level = levels[i]; 116e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (level != curLevel) { 117e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt curLevel = level; 118e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ++runCount; 119e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 120e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 121e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 122e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // add final run for trailing counter-directional whitespace 123e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int visLen = len; 124e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if ((curLevel & 1) != (baseLevel & 1)) { 125e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // look for visible end 126e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt while (--visLen >= 0) { 127e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt char ch = chars[cstart + visLen]; 128e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 129e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (ch == '\n') { 130e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt --visLen; 131e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt break; 132e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 133e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 134e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (ch != ' ' && ch != '\t') { 135e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt break; 136e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 137e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 138e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ++visLen; 139e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (visLen != len) { 140e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ++runCount; 141e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 142e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 143e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 144e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (runCount == 1 && minLevel == baseLevel) { 145e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // we're done, only one run on this line 146e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if ((minLevel & 1) != 0) { 147e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt return Layout.DIRS_ALL_RIGHT_TO_LEFT; 148e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 149e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt return Layout.DIRS_ALL_LEFT_TO_RIGHT; 150e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 151e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 152e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int[] ld = new int[runCount * 2]; 153e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int maxLevel = minLevel; 154e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int levelBits = minLevel << Layout.RUN_LEVEL_SHIFT; 155e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt { 156e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // Start of first pair is always 0, we write 157e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // length then start at each new run, and the 158e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // last run length after we're done. 159e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int n = 1; 160e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int prev = lstart; 161e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt curLevel = minLevel; 162e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt for (int i = lstart, e = lstart + visLen; i < e; ++i) { 163e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int level = levels[i]; 164e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (level != curLevel) { 165e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt curLevel = level; 166e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (level > maxLevel) { 167e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt maxLevel = level; 168e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } else if (level < minLevel) { 169e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt minLevel = level; 170e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 171e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // XXX ignore run length limit of 2^RUN_LEVEL_SHIFT 172e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ld[n++] = (i - prev) | levelBits; 173e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ld[n++] = i - lstart; 174e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt levelBits = curLevel << Layout.RUN_LEVEL_SHIFT; 175e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt prev = i; 176e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 177e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 178e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ld[n] = (lstart + visLen - prev) | levelBits; 179e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (visLen < len) { 180e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ld[++n] = visLen; 181e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt ld[++n] = (len - visLen) | (baseLevel << Layout.RUN_LEVEL_SHIFT); 182e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 183e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 184e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt 185e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // See if we need to swap any runs. 186e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // If the min level run direction doesn't match the base 187e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // direction, we always need to swap (at this point 188e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // we have more than one run). 189e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // Otherwise, we don't need to swap the lowest level. 190e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // Since there are no logically adjacent runs at the same 191e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // level, if the max level is the same as the (new) min 192e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // level, we have a series of alternating levels that 193e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // is already in order, so there's no more to do. 194e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt // 195e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt boolean swap; 196e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if ((minLevel & 1) == baseLevel) { 197e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt minLevel += 1; 198e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt swap = maxLevel > minLevel; 199e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } else { 200e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt swap = runCount > 1; 201e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 202e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (swap) { 203e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt for (int level = maxLevel - 1; level >= minLevel; --level) { 204e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt for (int i = 0; i < ld.length; i += 2) { 205e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt if (levels[ld[i]] >= level) { 206e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int e = i + 2; 207e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt while (e < ld.length && levels[ld[e]] >= level) { 208e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt e += 2; 209e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 210e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt for (int low = i, hi = e - 2; low < hi; low += 2, hi -= 2) { 211e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt int x = ld[low]; ld[low] = ld[hi]; ld[hi] = x; 212e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt x = ld[low+1]; ld[low+1] = ld[hi+1]; ld[hi+1] = x; 213e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 214e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt i = e + 2; 215e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 216e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 217e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 218e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 219e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt return new Directions(ld); 220e8e45f2c05cb3b6d23f30c8f96d8e0b3699cea7aDoug Felt } 221dae8e94cce0881f3e10ef5e34b881f512bb52a75Doug Felt}