jars/icu4j-4_2_1-src/src/com/ibm/richtext/styledtext/RunArray.java

   1 /*\r
   2  * (C) Copyright IBM Corp. 1998-2004.  All Rights Reserved.\r
   3  *\r
   4  * The program is provided "as is" without any warranty express or\r
   5  * implied, including the warranty of non-infringement and the implied\r
   6  * warranties of merchantibility and fitness for a particular purpose.\r
   7  * IBM will not be liable for any damages suffered by you as a result\r
   8  * of using the Program. In no event will IBM be liable for any\r
   9  * special, indirect or consequential damages or lost profits even if\r
  10  * IBM has been advised of the possibility of their occurrence. IBM\r
  11  * will not be liable for any third party claims against you.\r
  12  */\r
  13 /**\r
  14 * This class maintains intervals within a piece of text.  Interval boundaries\r
  15 * are stored in the fRunStart array.  Interval boundaries may have a\r
  16 * positive or negative representation.  A positive boundary is given as an offset\r
  17 * from 0.  A negative boundary is given as a negative offset from the ned of the text.\r
  18 * The RunArray stores positive boundaries in the entries [0, fPosEnd], and negative\r
  19 * boundaries in the entries [fNegStart, fLength).  New boundaries may be inserted into\r
  20 * the undefined middle of the RunArray.  If fPosEnd < 0, there are no positive entries.\r
  21 * If fNegStart >= fRunArray.length, there are no negative netries.  It's possible to have\r
  22 * a runarray with neither positive or negative entries.\r
  23 *\r
  24 * As an example of how the RunArray works, consider a piece of text with 5 intervals,\r
  25 * where each interval is 3 characters in length.  The RunArray for this text could\r
  26 * look like:\r
  27 *    fCurTextLength = 15, fPosEnd = 5, fNegStart = 10,\r
  28 *    fRunStart = { 0, 3, 6, 9, 12, U, U, U, U, U };\r
  29 * where U is an undefined array element.\r
  30 \r
  31 * An equivalent representation would be:\r
  32 *    fCurTextLength = 15, fPosEnd = 3, fNegStart = 8,\r
  33 *    fRunStart = { 0, 3, 6, U, U, U, U, U, -6, -3 };\r
  34 *\r
  35 * The RunArray class is used in the StyleBuffer and the ParagraphBuffer.  In the StyleBuffer,\r
  36 * the entries in fRunStart give the offsets where style runs begin.  In the\r
  37 * ParagraphBuffer, the fRunStart entries store offsets of paragraph breaks.\r
  38 *\r
  39 * This class provides methods for shifting the run table to a particular position, expanding the\r
  40 * run table, and returning the index of the run containing a particular offset in the text.  All\r
  41 * other functionality is implemented in the RunArray clients.\r
  42 *\r
  43 * RunArray uses FastIntBinarySearch for searches.  The searches are constructed on demand in\r
  44 * the findRunContaining method.  The searches are invalidated when the run array is shifted;\r
  45 * however, the RunArray can be modified by other classes.  Thus, if another class modifies\r
  46 * the entries in fRunArray, or modifies fPosEnd or fNegStart, it is responsible for\r
  47 * calling runStartsChanged.\r
  48 */\r
  49 \r
  50 package com.ibm.richtext.styledtext;\r
  51 \r
  52 import java.io.Externalizable;\r
  53 import java.io.ObjectInput;\r
  54 import java.io.ObjectOutput;\r
  55 import java.io.IOException;\r
  56 \r
  57 final class RunArray implements Externalizable {\r
  58 \r
  59     static final String COPYRIGHT =\r
  60                 "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved";\r
  61     private static final long serialVersionUID = 22356934;\r
  62 \r
  63     int[] fRunStart;\r
  64     private int fCurTextLength;\r
  65     int fPosEnd, fNegStart;\r
  66     \r
  67     transient private FastIntBinarySearch fPosSearch;\r
  68     transient private boolean fPosSearchValid;\r
  69     transient private FastIntBinarySearch fNegSearch;\r
  70     transient private boolean fNegSearchValid;\r
  71 \r
  72     private static final int CURRENT_VERSION = 1;\r
  73 \r
  74     RunArray(int initialSize, int curTextLength) {\r
  75 \r
  76         fRunStart = new int[initialSize];\r
  77         fCurTextLength = curTextLength;\r
  78         fPosEnd = -1;\r
  79         fNegStart = initialSize;\r
  80         \r
  81         fPosSearch = new FastIntBinarySearch(fRunStart, 0, 1);\r
  82         fNegSearch = new FastIntBinarySearch(fRunStart, 0, 1);\r
  83         fPosSearchValid = fNegSearchValid = false;\r
  84     }\r
  85 \r
  86     /**\r
  87      * Note: this constructor is ONLY for use by the Serialization\r
  88      * mechanism.  It does not leave this object in a valid state!\r
  89      */\r
  90     public RunArray() {\r
  91     }\r
  92 \r
  93     public void writeExternal(ObjectOutput out) throws IOException {\r
  94 \r
  95         out.writeInt(CURRENT_VERSION);\r
  96         out.writeObject(fRunStart);\r
  97         out.writeInt(fCurTextLength);\r
  98         out.writeInt(fPosEnd);\r
  99         out.writeInt(fNegStart);\r
 100     }\r
 101 \r
 102     public void readExternal(ObjectInput in) throws IOException,\r
 103                                             ClassNotFoundException {\r
 104 \r
 105         if (in.readInt() != CURRENT_VERSION) {\r
 106             throw new IOException("Invalid version of RunArray");\r
 107         }\r
 108         fRunStart = (int[]) in.readObject();\r
 109         fCurTextLength = in.readInt();\r
 110         fPosEnd = in.readInt();\r
 111         fNegStart = in.readInt();\r
 112         \r
 113         fPosSearch = new FastIntBinarySearch(fRunStart, 0, 1);\r
 114         fNegSearch = new FastIntBinarySearch(fRunStart, 0, 1);\r
 115         fPosSearchValid = fNegSearchValid = false;\r
 116     }\r
 117 \r
 118     public int getCurTextLength() {\r
 119 \r
 120         return fCurTextLength;\r
 121     }\r
 122 \r
 123     public void setCurTextLength(int curTextLength) {\r
 124 \r
 125         fCurTextLength = curTextLength;\r
 126     }\r
 127 \r
 128     public void addToCurTextLength(int delta) {\r
 129 \r
 130         fCurTextLength += delta;\r
 131     }\r
 132 \r
 133     public void runStartsChanged() {\r
 134 \r
 135         fPosSearchValid = fNegSearchValid = false;\r
 136     }\r
 137 \r
 138 /**\r
 139 * Returns the index of the last valid run.\r
 140 */\r
 141     int lastRun() {\r
 142 \r
 143         return (fNegStart == fRunStart.length)? fPosEnd : fRunStart.length-1;\r
 144     }\r
 145 \r
 146 /**\r
 147 * Returns the length of the run array.  Replaces old fLength member.\r
 148 */\r
 149     int getArrayLength() {\r
 150 \r
 151         return fRunStart.length;\r
 152     }\r
 153 \r
 154 /**\r
 155 * Shifts style table such that the last positive run\r
 156 * starts before pos.\r
 157 */\r
 158     void shiftTableTo(int pos) {\r
 159 \r
 160         int oldPosEnd = fPosEnd;\r
 161 \r
 162         while (fPosEnd >= 0 && fRunStart[fPosEnd] >= pos) {\r
 163 \r
 164             fNegStart--;\r
 165             fRunStart[fNegStart] = fRunStart[fPosEnd] - fCurTextLength;\r
 166             fPosEnd--;\r
 167 \r
 168         }\r
 169 \r
 170         pos -= fCurTextLength;\r
 171 \r
 172         while (fNegStart<fRunStart.length && fRunStart[fNegStart] < pos) {\r
 173 \r
 174             fPosEnd++;\r
 175             fRunStart[fPosEnd] = fRunStart[fNegStart] + fCurTextLength;\r
 176             fNegStart++;\r
 177         }\r
 178 \r
 179         if (oldPosEnd != fPosEnd) {\r
 180             fPosSearchValid = fNegSearchValid = false;\r
 181         }\r
 182     }\r
 183 \r
 184 /**\r
 185 * Returns index of style run containing pos.  If first style run starts before\r
 186 * pos, -1 is returned.  If pos is greater than text length, lastrun is returned.\r
 187 */\r
 188     int findRunContaining(int pos) {\r
 189 \r
 190         FastIntBinarySearch search;\r
 191         final int length = fRunStart.length;\r
 192 \r
 193         if (fNegStart < length && (pos-fCurTextLength >= fRunStart[fNegStart])) {\r
 194 \r
 195             pos -= fCurTextLength;\r
 196 \r
 197             if (!fNegSearchValid) {\r
 198                 fNegSearch.setData(fRunStart, fNegStart, length-fNegStart);\r
 199             }\r
 200             search = fNegSearch;\r
 201         }\r
 202         else if (fPosEnd >= 0) {\r
 203 \r
 204             if (!fPosSearchValid) {\r
 205                 fPosSearch.setData(fRunStart, 0, fPosEnd+1);\r
 206             }\r
 207             search = fPosSearch;\r
 208         }\r
 209         else\r
 210             return -1;\r
 211 \r
 212         int run = search.findIndex(pos);\r
 213 \r
 214         return run;\r
 215     }\r
 216 \r
 217     int getLogicalRunStart(int run) {\r
 218 \r
 219         if (run == -1) {\r
 220             return 0;\r
 221         }\r
 222         else if (run == fRunStart.length) {\r
 223             return fCurTextLength;\r
 224         }\r
 225         else {\r
 226             if (run <= fPosEnd) {\r
 227                 return fRunStart[run];\r
 228             }\r
 229             else if (run >= fNegStart) {\r
 230                 return fRunStart[run] + fCurTextLength;\r
 231             }\r
 232             else {\r
 233                 throw new IllegalArgumentException("Illegal run");\r
 234             }\r
 235         }\r
 236     }\r
 237 \r
 238 /**\r
 239 * Increases size of run table.  Current implementation doubles the run table's size.\r
 240 */\r
 241     void expandRunTable() {\r
 242 \r
 243         resizeRunTable(fRunStart.length * 2);\r
 244     }\r
 245 \r
 246 /**\r
 247 * Return the minimum number of elements possible in fRunStart.\r
 248 */\r
 249     private int getMinSize() {\r
 250 \r
 251         return Math.max(fPosEnd + (fRunStart.length-fNegStart) + 1, 1);\r
 252     }\r
 253 \r
 254     void compress() {\r
 255 \r
 256         int minSize = getMinSize();\r
 257         if (fRunStart.length > minSize) {\r
 258             resizeRunTable(minSize);\r
 259         }\r
 260     }\r
 261 \r
 262     private void resizeRunTable(int newSize) {\r
 263 \r
 264         if (newSize < getMinSize()) {\r
 265             throw new IllegalArgumentException("Attempt to make RunArray too small.");\r
 266         }\r
 267 \r
 268         final int oldLength = fRunStart.length;\r
 269 \r
 270         int newRunStart[] = new int[newSize];\r
 271         System.arraycopy(fRunStart, 0, newRunStart, 0, fPosEnd+1);\r
 272         int newNegStart = newRunStart.length - (oldLength-fNegStart);\r
 273         System.arraycopy(fRunStart, fNegStart, newRunStart, newNegStart, (oldLength-fNegStart));\r
 274 \r
 275         fNegStart = newNegStart;\r
 276         fRunStart = newRunStart;\r
 277 \r
 278         fPosSearchValid = fNegSearchValid = false;\r
 279     }\r
 280 }\r