Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

ubidiln.c

00001 /*  
00002 *******************************************************************************
00003 *
00004 *   Copyright (C) 1999-2000, International Business Machines
00005 *   Corporation and others.  All Rights Reserved.
00006 *
00007 *******************************************************************************
00008 *   file name:  ubidiln.c
00009 *   encoding:   US-ASCII
00010 *   tab size:   8 (not used)
00011 *   indentation:4
00012 *
00013 *   created on: 1999aug06
00014 *   created by: Markus W. Scherer
00015 */
00016 
00017 /* set import/export definitions */
00018 #ifndef U_COMMON_IMPLEMENTATION
00019 #   define U_COMMON_IMPLEMENTATION
00020 #endif
00021 
00022 #include "cmemory.h"
00023 #include "unicode/utypes.h"
00024 #include "unicode/ustring.h"
00025 #include "unicode/uchar.h"
00026 #include "unicode/ubidi.h"
00027 #include "ubidiimp.h"
00028 
00029 /*
00030  * General remarks about the functions in this file:
00031  *
00032  * These functions deal with the aspects of potentially mixed-directional
00033  * text in a single paragraph or in a line of a single paragraph
00034  * which has already been processed according to
00035  * the Unicode 3.0 BiDi algorithm as defined in
00036  * http://www.unicode.org/unicode/reports/tr9/ , version 5,
00037  * also described in The Unicode Standard, Version 3.0 .
00038  *
00039  * This means that there is a UBiDi object with a levels
00040  * and a dirProps array.
00041  * paraLevel and direction are also set.
00042  * Only if the length of the text is zero, then levels==dirProps==NULL.
00043  *
00044  * The overall directionality of the paragraph
00045  * or line is used to bypass the reordering steps if possible.
00046  * Even purely RTL text does not need reordering there because
00047  * the ubidi_getLogical/VisualIndex() functions can compute the
00048  * index on the fly in such a case.
00049  *
00050  * The implementation of the access to same-level-runs and of the reordering
00051  * do attempt to provide better performance and less memory usage compared to
00052  * a direct implementation of especially rule (L2) with an array of
00053  * one (32-bit) integer per text character.
00054  *
00055  * Here, the levels array is scanned as soon as necessary, and a vector of
00056  * same-level-runs is created. Reordering then is done on this vector.
00057  * For each run of text positions that were resolved to the same level,
00058  * only 8 bytes are stored: the first text position of the run and the visual
00059  * position behind the run after reordering.
00060  * One sign bit is used to hold the directionality of the run.
00061  * This is inefficient if there are many very short runs. If the average run
00062  * length is <2, then this uses more memory.
00063  *
00064  * In a further attempt to save memory, the levels array is never changed
00065  * after all the resolution rules (Xn, Wn, Nn, In).
00066  * Many functions have to consider the field trailingWSStart:
00067  * if it is less than length, then there is an implicit trailing run
00068  * at the paraLevel,
00069  * which is not reflected in the levels array.
00070  * This allows a line UBiDi object to use the same levels array as
00071  * its paragraph parent object.
00072  *
00073  * When a UBiDi object is created for a line of a paragraph, then the
00074  * paragraph's levels and dirProps arrays are reused by way of setting
00075  * a pointer into them, not by copying. This again saves memory and forbids to
00076  * change the now shared levels for (L1).
00077  */
00078 
00079 /* prototypes --------------------------------------------------------------- */
00080 
00081 static void
00082 setTrailingWSStart(UBiDi *pBiDi);
00083 
00084 static void
00085 getSingleRun(UBiDi *pBiDi, UBiDiLevel level);
00086 
00087 static void
00088 reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel);
00089 
00090 static UBool
00091 prepareReorder(const UBiDiLevel *levels, UTextOffset length,
00092                UTextOffset *indexMap,
00093                UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel);
00094 
00095 /* ubidi_setLine ------------------------------------------------------------ */
00096 
00097 U_CAPI void U_EXPORT2
00098 ubidi_setLine(const UBiDi *pParaBiDi,
00099               UTextOffset start, UTextOffset limit,
00100               UBiDi *pLineBiDi,
00101               UErrorCode *pErrorCode) {
00102     UTextOffset length;
00103 
00104     /* check the argument values */
00105     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
00106         return;
00107     } else if(pParaBiDi==NULL || pLineBiDi==NULL) {
00108         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
00109         return;
00110     } else if(start<0 || start>limit || limit>pParaBiDi->length) {
00111         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
00112         return;
00113     }
00114 
00115     /* set the values in pLineBiDi from its pParaBiDi parent */
00116     pLineBiDi->text=pParaBiDi->text+start;
00117     length=pLineBiDi->length=limit-start;
00118     pLineBiDi->paraLevel=pParaBiDi->paraLevel;
00119 
00120     pLineBiDi->runs=NULL;
00121     pLineBiDi->flags=0;
00122 
00123     if(length>0) {
00124         pLineBiDi->dirProps=pParaBiDi->dirProps+start;
00125         pLineBiDi->levels=pParaBiDi->levels+start;
00126         pLineBiDi->runCount=-1;
00127 
00128         if(pParaBiDi->direction!=UBIDI_MIXED) {
00129             /* the parent is already trivial */
00130             pLineBiDi->direction=pParaBiDi->direction;
00131 
00132             /*
00133              * The parent's levels are all either
00134              * implicitly or explicitly ==paraLevel;
00135              * do the same here.
00136              */
00137             if(pParaBiDi->trailingWSStart<=start) {
00138                 pLineBiDi->trailingWSStart=0;
00139             } else if(pParaBiDi->trailingWSStart<limit) {
00140                 pLineBiDi->trailingWSStart=pParaBiDi->trailingWSStart-start;
00141             } else {
00142                 pLineBiDi->trailingWSStart=length;
00143             }
00144         } else {
00145             const UBiDiLevel *levels=pLineBiDi->levels;
00146             UTextOffset i, trailingWSStart;
00147             UBiDiLevel level;
00148 
00149             setTrailingWSStart(pLineBiDi);
00150             trailingWSStart=pLineBiDi->trailingWSStart;
00151 
00152             /* recalculate pLineBiDi->direction */
00153             if(trailingWSStart==0) {
00154                 /* all levels are at paraLevel */
00155                 pLineBiDi->direction=(UBiDiDirection)(pLineBiDi->paraLevel&1);
00156             } else {
00157                 /* get the level of the first character */
00158                 level=(UBiDiLevel)(levels[0]&1);
00159 
00160                 /* if there is anything of a different level, then the line is mixed */
00161                 if(trailingWSStart<length && (pLineBiDi->paraLevel&1)!=level) {
00162                     /* the trailing WS is at paraLevel, which differs from levels[0] */
00163                     pLineBiDi->direction=UBIDI_MIXED;
00164                 } else {
00165                     /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
00166                     i=1;
00167                     for(;;) {
00168                         if(i==trailingWSStart) {
00169                             /* the direction values match those in level */
00170                             pLineBiDi->direction=(UBiDiDirection)level;
00171                             break;
00172                         } else if((levels[i]&1)!=level) {
00173                             pLineBiDi->direction=UBIDI_MIXED;
00174                             break;
00175                         }
00176                         ++i;
00177                     }
00178                 }
00179             }
00180 
00181             switch(pLineBiDi->direction) {
00182             case UBIDI_LTR:
00183                 /* make sure paraLevel is even */
00184                 pLineBiDi->paraLevel=(UBiDiLevel)((pLineBiDi->paraLevel+1)&~1);
00185 
00186                 /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
00187                 pLineBiDi->trailingWSStart=0;
00188                 break;
00189             case UBIDI_RTL:
00190                 /* make sure paraLevel is odd */
00191                 pLineBiDi->paraLevel|=1;
00192 
00193                 /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
00194                 pLineBiDi->trailingWSStart=0;
00195                 break;
00196             default:
00197                 break;
00198             }
00199         }
00200     } else {
00201         /* create an object for a zero-length line */
00202         pLineBiDi->direction=pLineBiDi->paraLevel&1 ? UBIDI_RTL : UBIDI_LTR;
00203         pLineBiDi->trailingWSStart=pLineBiDi->runCount=0;
00204 
00205         pLineBiDi->dirProps=NULL;
00206         pLineBiDi->levels=NULL;
00207     }
00208     return;
00209 }
00210 
00211 U_CAPI UBiDiLevel U_EXPORT2
00212 ubidi_getLevelAt(const UBiDi *pBiDi, UTextOffset charIndex) {
00213     /* return paraLevel if in the trailing WS run, otherwise the real level */
00214     if(pBiDi==NULL || charIndex<0 || pBiDi->length<=charIndex) {
00215         return 0;
00216     } else if(pBiDi->direction!=UBIDI_MIXED || charIndex>=pBiDi->trailingWSStart) {
00217         return pBiDi->paraLevel;
00218     } else {
00219         return pBiDi->levels[charIndex];
00220     }
00221 }
00222 
00223 U_CAPI const UBiDiLevel * U_EXPORT2
00224 ubidi_getLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
00225     UTextOffset start, length;
00226 
00227     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
00228         return NULL;
00229     } else if(pBiDi==NULL || (length=pBiDi->length)<=0) {
00230         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
00231         return NULL;
00232     }
00233 
00234     if((start=pBiDi->trailingWSStart)==length) {
00235         /* the current levels array reflects the WS run */
00236         return pBiDi->levels;
00237     }
00238 
00239     /*
00240      * After the previous if(), we know that the levels array
00241      * has an implicit trailing WS run and therefore does not fully
00242      * reflect itself all the levels.
00243      * This must be a UBiDi object for a line, and
00244      * we need to create a new levels array.
00245      */
00246 
00247     if(getLevelsMemory(pBiDi, length)) {
00248         UBiDiLevel *levels=pBiDi->levelsMemory;
00249 
00250         if(start>0 && levels!=pBiDi->levels) {
00251             uprv_memcpy(levels, pBiDi->levels, start);
00252         }
00253         uprv_memset(levels+start, pBiDi->paraLevel, length-start);
00254 
00255         /* this new levels array is set for the line and reflects the WS run */
00256         pBiDi->trailingWSStart=length;
00257         return pBiDi->levels=levels;
00258     } else {
00259         /* out of memory */
00260         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
00261         return NULL;
00262     }
00263 }
00264 
00265 U_CAPI void U_EXPORT2
00266 ubidi_getLogicalRun(const UBiDi *pBiDi, UTextOffset logicalStart,
00267                     UTextOffset *pLogicalLimit, UBiDiLevel *pLevel) {
00268     UTextOffset length;
00269 
00270     if(pBiDi==NULL || logicalStart<0 || (length=pBiDi->length)<=logicalStart) {
00271         return;
00272     }
00273 
00274     if(pBiDi->direction!=UBIDI_MIXED || logicalStart>=pBiDi->trailingWSStart) {
00275         if(pLogicalLimit!=NULL) {
00276             *pLogicalLimit=length;
00277         }
00278         if(pLevel!=NULL) {
00279             *pLevel=pBiDi->paraLevel;
00280         }
00281     } else {
00282         UBiDiLevel *levels=pBiDi->levels;
00283         UBiDiLevel level=levels[logicalStart];
00284 
00285         /* search for the end of the run */
00286         length=pBiDi->trailingWSStart;
00287         while(++logicalStart<length && level==levels[logicalStart]) {}
00288 
00289         if(pLogicalLimit!=NULL) {
00290             *pLogicalLimit=logicalStart;
00291         }
00292         if(pLevel!=NULL) {
00293             *pLevel=level;
00294         }
00295     }
00296 }
00297 
00298 /* handle trailing WS (L1) -------------------------------------------------- */
00299 
00300 /*
00301  * setTrailingWSStart() sets the start index for a trailing
00302  * run of WS in the line. This is necessary because we do not modify
00303  * the paragraph's levels array that we just point into.
00304  * Using trailingWSStart is another form of performing (L1).
00305  *
00306  * To make subsequent operations easier, we also include the run
00307  * before the WS if it is at the paraLevel - we merge the two here.
00308  */
00309 static void
00310 setTrailingWSStart(UBiDi *pBiDi) {
00311     /* pBiDi->direction!=UBIDI_MIXED */
00312 
00313     const DirProp *dirProps=pBiDi->dirProps;
00314     UBiDiLevel *levels=pBiDi->levels;
00315     UTextOffset start=pBiDi->length;
00316     UBiDiLevel paraLevel=pBiDi->paraLevel;
00317 
00318     /* go backwards across all WS, BN, explicit codes */
00319     while(start>0 && DIRPROP_FLAG(dirProps[start-1])&MASK_WS) {
00320         --start;
00321     }
00322 
00323     /* if the WS run can be merged with the previous run then do so here */
00324     while(start>0 && levels[start-1]==paraLevel) {
00325         --start;
00326     }
00327 
00328     pBiDi->trailingWSStart=start;
00329 }
00330 
00331 /* runs API functions ------------------------------------------------------- */
00332 
00333 U_CAPI UTextOffset U_EXPORT2
00334 ubidi_countRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
00335     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
00336         return -1;
00337     } else if(pBiDi==NULL || (pBiDi->runCount<0 && !ubidi_getRuns(pBiDi))) {
00338         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
00339         return -1;
00340     } else {
00341         return pBiDi->runCount;
00342     }
00343 }
00344 
00345 U_CAPI UBiDiDirection U_EXPORT2
00346 ubidi_getVisualRun(UBiDi *pBiDi, UTextOffset runIndex,
00347                    UTextOffset *pLogicalStart, UTextOffset *pLength) {
00348     if( pBiDi==NULL || runIndex<0 ||
00349         (pBiDi->runCount==-1 && !ubidi_getRuns(pBiDi)) ||
00350         runIndex>=pBiDi->runCount
00351     ) {
00352         return UBIDI_LTR;
00353     } else {
00354         UTextOffset start=pBiDi->runs[runIndex].logicalStart;
00355         if(pLogicalStart!=NULL) {
00356             *pLogicalStart=GET_INDEX(start);
00357         }
00358         if(pLength!=NULL) {
00359             if(runIndex>0) {
00360                 *pLength=pBiDi->runs[runIndex].visualLimit-
00361                          pBiDi->runs[runIndex-1].visualLimit;
00362             } else {
00363                 *pLength=pBiDi->runs[0].visualLimit;
00364             }
00365         }
00366         return (UBiDiDirection)GET_ODD_BIT(start);
00367     }
00368 }
00369 
00370 /* compute the runs array --------------------------------------------------- */
00371 
00372 /*
00373  * Compute the runs array from the levels array.
00374  * After ubidi_getRuns() returns TRUE, runCount is guaranteed to be >0
00375  * and the runs are reordered.
00376  * Odd-level runs have visualStart on their visual right edge and
00377  * they progress visually to the left.
00378  */
00379 U_CFUNC UBool
00380 ubidi_getRuns(UBiDi *pBiDi) {
00381     if(pBiDi->direction!=UBIDI_MIXED) {
00382         /* simple, single-run case - this covers length==0 */
00383         getSingleRun(pBiDi, pBiDi->paraLevel);
00384     } else /* UBIDI_MIXED, length>0 */ {
00385         /* mixed directionality */
00386         UTextOffset length=pBiDi->length, limit;
00387 
00388         /*
00389          * If there are WS characters at the end of the line
00390          * and the run preceding them has a level different from
00391          * paraLevel, then they will form their own run at paraLevel (L1).
00392          * Count them separately.
00393          * We need some special treatment for this in order to not
00394          * modify the levels array which a line UBiDi object shares
00395          * with its paragraph parent and its other line siblings.
00396          * In other words, for the trailing WS, it may be
00397          * levels[]!=paraLevel but we have to treat it like it were so.
00398          */
00399         limit=pBiDi->trailingWSStart;
00400         if(limit==0) {
00401             /* there is only WS on this line */
00402             getSingleRun(pBiDi, pBiDi->paraLevel);
00403         } else {
00404             UBiDiLevel *levels=pBiDi->levels;
00405             UTextOffset i, runCount;
00406             UBiDiLevel level=UBIDI_DEFAULT_LTR;   /* initialize with no valid level */
00407 
00408             /* count the runs, there is at least one non-WS run, and limit>0 */
00409             runCount=0;
00410             for(i=0; i<limit; ++i) {
00411                 /* increment runCount at the start of each run */
00412                 if(levels[i]!=level) {
00413                     ++runCount;
00414                     level=levels[i];
00415                 }
00416             }
00417 
00418             /*
00419              * We don't need to see if the last run can be merged with a trailing
00420              * WS run because setTrailingWSStart() would have done that.
00421              */
00422             if(runCount==1 && limit==length) {
00423                 /* There is only one non-WS run and no trailing WS-run. */
00424                 getSingleRun(pBiDi, levels[0]);
00425             } else /* runCount>1 || limit<length */ {
00426                 /* allocate and set the runs */
00427                 Run *runs;
00428                 UTextOffset runIndex, start;
00429                 UBiDiLevel minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
00430 
00431                 /* now, count a (non-mergable) WS run */
00432                 if(limit<length) {
00433                     ++runCount;
00434                 }
00435 
00436                 /* runCount>1 */
00437                 if(getRunsMemory(pBiDi, runCount)) {
00438                     runs=pBiDi->runsMemory;
00439                 } else {
00440                     return FALSE;
00441                 }
00442 
00443                 /* set the runs */
00444                 /* this could be optimized, e.g.: 464->444, 484->444, 575->555, 595->555 */
00445                 /* however, that would take longer and make other functions more complicated */
00446                 runIndex=0;
00447 
00448                 /* search for the run limits and initialize visualLimit values with the run lengths */
00449                 i=0;
00450                 do {
00451                     /* prepare this run */
00452                     start=i;
00453                     level=levels[i];
00454                     if(level<minLevel) {
00455                         minLevel=level;
00456                     }
00457                     if(level>maxLevel) {
00458                         maxLevel=level;
00459                     }
00460 
00461                     /* look for the run limit */
00462                     while(++i<limit && levels[i]==level) {}
00463 
00464                     /* i is another run limit */
00465                     runs[runIndex].logicalStart=start;
00466                     runs[runIndex].visualLimit=i-start;
00467                     ++runIndex;
00468                 } while(i<limit);
00469 
00470                 if(limit<length) {
00471                     /* there is a separate WS run */
00472                     runs[runIndex].logicalStart=limit;
00473                     runs[runIndex].visualLimit=length-limit;
00474                     if(pBiDi->paraLevel<minLevel) {
00475                         minLevel=pBiDi->paraLevel;
00476                     }
00477                 }
00478 
00479                 /* set the object fields */
00480                 pBiDi->runs=runs;
00481                 pBiDi->runCount=runCount;
00482 
00483                 reorderLine(pBiDi, minLevel, maxLevel);
00484 
00485                 /* now add the direction flags and adjust the visualLimit's to be just that */
00486                 ADD_ODD_BIT_FROM_LEVEL(runs[0].logicalStart, levels[runs[0].logicalStart]);
00487                 limit=runs[0].visualLimit;
00488                 for(i=1; i<runIndex; ++i) {
00489                     ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
00490                     limit=runs[i].visualLimit+=limit;
00491                 }
00492 
00493                 /* same for the trailing WS run */
00494                 if(runIndex<runCount) {
00495                     ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, pBiDi->paraLevel);
00496                     runs[runIndex].visualLimit+=limit;
00497                 }
00498             }
00499         }
00500     }
00501     return TRUE;
00502 }
00503 
00504 /* in trivial cases there is only one trivial run; called by ubidi_getRuns() */
00505 static void
00506 getSingleRun(UBiDi *pBiDi, UBiDiLevel level) {
00507     /* simple, single-run case */
00508     pBiDi->runs=pBiDi->simpleRuns;
00509     pBiDi->runCount=1;
00510 
00511     /* fill and reorder the single run */
00512     pBiDi->runs[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, level);
00513     pBiDi->runs[0].visualLimit=pBiDi->length;
00514 }
00515 
00516 /* reorder the runs array (L2) ---------------------------------------------- */
00517 
00518 /*
00519  * Reorder the same-level runs in the runs array.
00520  * Here, runCount>1 and maxLevel>=minLevel>=paraLevel.
00521  * All the visualStart fields=logical start before reordering.
00522  * The "odd" bits are not set yet.
00523  *
00524  * Reordering with this data structure lends itself to some handy shortcuts:
00525  *
00526  * Since each run is moved but not modified, and since at the initial maxLevel
00527  * each sequence of same-level runs consists of only one run each, we
00528  * don't need to do anything there and can predecrement maxLevel.
00529  * In many simple cases, the reordering is thus done entirely in the
00530  * index mapping.
00531  * Also, reordering occurs only down to the lowest odd level that occurs,
00532  * which is minLevel|1. However, if the lowest level itself is odd, then
00533  * in the last reordering the sequence of the runs at this level or higher
00534  * will be all runs, and we don't need the elaborate loop to search for them.
00535  * This is covered by ++minLevel instead of minLevel|=1 followed
00536  * by an extra reorder-all after the reorder-some loop.
00537  * About a trailing WS run:
00538  * Such a run would need special treatment because its level is not
00539  * reflected in levels[] if this is not a paragraph object.
00540  * Instead, all characters from trailingWSStart on are implicitly at
00541  * paraLevel.
00542  * However, for all maxLevel>paraLevel, this run will never be reordered
00543  * and does not need to be taken into account. maxLevel==paraLevel is only reordered
00544  * if minLevel==paraLevel is odd, which is done in the extra segment.
00545  * This means that for the main reordering loop we don't need to consider
00546  * this run and can --runCount. If it is later part of the all-runs
00547  * reordering, then runCount is adjusted accordingly.
00548  */
00549 static void
00550 reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel) {
00551     Run *runs;
00552     UBiDiLevel *levels;
00553     UTextOffset firstRun, endRun, limitRun, runCount,
00554         temp;
00555 
00556     /* nothing to do? */
00557     if(maxLevel<=(minLevel|1)) {
00558         return;
00559     }
00560 
00561     /*
00562      * Reorder only down to the lowest odd level
00563      * and reorder at an odd minLevel in a separate, simpler loop.
00564      * See comments above for why minLevel is always incremented.
00565      */
00566     ++minLevel;
00567 
00568     runs=pBiDi->runs;
00569     levels=pBiDi->levels;
00570     runCount=pBiDi->runCount;
00571 
00572     /* do not include the WS run at paraLevel<=old minLevel except in the simple loop */
00573     if(pBiDi->trailingWSStart<pBiDi->length) {
00574         --runCount;
00575     }
00576 
00577     while(--maxLevel>=minLevel) {
00578         firstRun=0;
00579 
00580         /* loop for all sequences of runs */
00581         for(;;) {
00582             /* look for a sequence of runs that are all at >=maxLevel */
00583             /* look for the first run of such a sequence */
00584             while(firstRun<runCount && levels[runs[firstRun].logicalStart]<maxLevel) {
00585                 ++firstRun;
00586             }
00587             if(firstRun>=runCount) {
00588                 break;  /* no more such runs */
00589             }
00590 
00591             /* look for the limit run of such a sequence (the run behind it) */
00592             for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=maxLevel;) {}
00593 
00594             /* Swap the entire sequence of runs from firstRun to limitRun-1. */
00595             endRun=limitRun-1;
00596             while(firstRun<endRun) {
00597                 temp=runs[firstRun].logicalStart;
00598                 runs[firstRun].logicalStart=runs[endRun].logicalStart;
00599                 runs[endRun].logicalStart=temp;
00600 
00601                 temp=runs[firstRun].visualLimit;
00602                 runs[firstRun].visualLimit=runs[endRun].visualLimit;
00603                 runs[endRun].visualLimit=temp;
00604 
00605                 ++firstRun;
00606                 --endRun;
00607             }
00608 
00609             if(limitRun==runCount) {
00610                 break;  /* no more such runs */
00611             } else {
00612                 firstRun=limitRun+1;
00613             }
00614         }
00615     }
00616 
00617     /* now do maxLevel==old minLevel (==odd!), see above */
00618     if(!(minLevel&1)) {
00619         firstRun=0;
00620 
00621         /* include the trailing WS run in this complete reordering */
00622         if(pBiDi->trailingWSStart==pBiDi->length) {
00623             --runCount;
00624         }
00625 
00626         /* Swap the entire sequence of all runs. (endRun==runCount) */
00627         while(firstRun<runCount) {
00628             temp=runs[firstRun].logicalStart;
00629             runs[firstRun].logicalStart=runs[runCount].logicalStart;
00630             runs[runCount].logicalStart=temp;
00631 
00632             temp=runs[firstRun].visualLimit;
00633             runs[firstRun].visualLimit=runs[runCount].visualLimit;
00634             runs[runCount].visualLimit=temp;
00635 
00636             ++firstRun;
00637             --runCount;
00638         }
00639     }
00640 }
00641 
00642 /* reorder a line based on a levels array (L2) ------------------------------ */
00643 
00644 U_CAPI void U_EXPORT2
00645 ubidi_reorderLogical(const UBiDiLevel *levels, UTextOffset length, UTextOffset *indexMap) {
00646     UTextOffset start, limit, sumOfSosEos;
00647     UBiDiLevel minLevel, maxLevel;
00648 
00649     if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
00650         return;
00651     }
00652 
00653     /* nothing to do? */
00654     if(minLevel==maxLevel && (minLevel&1)==0) {
00655         return;
00656     }
00657 
00658     /* reorder only down to the lowest odd level */
00659     minLevel|=1;
00660 
00661     /* loop maxLevel..minLevel */
00662     do {
00663         start=0;
00664 
00665         /* loop for all sequences of levels to reorder at the current maxLevel */
00666         for(;;) {
00667             /* look for a sequence of levels that are all at >=maxLevel */
00668             /* look for the first index of such a sequence */
00669             while(start<length && levels[start]<maxLevel) {
00670                 ++start;
00671             }
00672             if(start>=length) {
00673                 break;  /* no more such sequences */
00674             }
00675 
00676             /* look for the limit of such a sequence (the index behind it) */
00677             for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
00678 
00679             /*
00680              * sos=start of sequence, eos=end of sequence
00681              *
00682              * The closed (inclusive) interval from sos to eos includes all the logical
00683              * and visual indexes within this sequence. They are logically and
00684              * visually contiguous and in the same range.
00685              *
00686              * For each run, the new visual index=sos+eos-old visual index;
00687              * we pre-add sos+eos into sumOfSosEos ->
00688              * new visual index=sumOfSosEos-old visual index;
00689              */
00690             sumOfSosEos=start+limit-1;
00691 
00692             /* reorder each index in the sequence */
00693             do {
00694                 indexMap[start]=sumOfSosEos-indexMap[start];
00695             } while(++start<limit);
00696 
00697             /* start==limit */
00698             if(limit==length) {
00699                 break;  /* no more such sequences */
00700             } else {
00701                 start=limit+1;
00702             }
00703         }
00704     } while(--maxLevel>=minLevel);
00705 }
00706 
00707 U_CAPI void U_EXPORT2
00708 ubidi_reorderVisual(const UBiDiLevel *levels, UTextOffset length, UTextOffset *indexMap) {
00709     UTextOffset start, end, limit, temp;
00710     UBiDiLevel minLevel, maxLevel;
00711 
00712     if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
00713         return;
00714     }
00715 
00716     /* nothing to do? */
00717     if(minLevel==maxLevel && (minLevel&1)==0) {
00718         return;
00719     }
00720 
00721     /* reorder only down to the lowest odd level */
00722     minLevel|=1;
00723 
00724     /* loop maxLevel..minLevel */
00725     do {
00726         start=0;
00727 
00728         /* loop for all sequences of levels to reorder at the current maxLevel */
00729         for(;;) {
00730             /* look for a sequence of levels that are all at >=maxLevel */
00731             /* look for the first index of such a sequence */
00732             while(start<length && levels[start]<maxLevel) {
00733                 ++start;
00734             }
00735             if(start>=length) {
00736                 break;  /* no more such runs */
00737             }
00738 
00739             /* look for the limit of such a sequence (the index behind it) */
00740             for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
00741 
00742             /*
00743              * Swap the entire interval of indexes from start to limit-1.
00744              * We don't need to swap the levels for the purpose of this
00745              * algorithm: the sequence of levels that we look at does not
00746              * move anyway.
00747              */
00748             end=limit-1;
00749             while(start<end) {
00750                 temp=indexMap[start];
00751                 indexMap[start]=indexMap[end];
00752                 indexMap[end]=temp;
00753 
00754                 ++start;
00755                 --end;
00756             }
00757 
00758             if(limit==length) {
00759                 break;  /* no more such sequences */
00760             } else {
00761                 start=limit+1;
00762             }
00763         }
00764     } while(--maxLevel>=minLevel);
00765 }
00766 
00767 static UBool
00768 prepareReorder(const UBiDiLevel *levels, UTextOffset length,
00769                UTextOffset *indexMap,
00770                UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel) {
00771     UTextOffset start;
00772     UBiDiLevel level, minLevel, maxLevel;
00773 
00774     if(levels==NULL || length<=0) {
00775         return FALSE;
00776     }
00777 
00778     /* determine minLevel and maxLevel */
00779     minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1;
00780     maxLevel=0;
00781     for(start=length; start>0;) {
00782         level=levels[--start];
00783         if(level>UBIDI_MAX_EXPLICIT_LEVEL+1) {
00784             return FALSE;
00785         }
00786         if(level<minLevel) {
00787             minLevel=level;
00788         }
00789         if(level>maxLevel) {
00790             maxLevel=level;
00791         }
00792     }
00793     *pMinLevel=minLevel;
00794     *pMaxLevel=maxLevel;
00795 
00796     /* initialize the index map */
00797     for(start=length; start>0;) {
00798         --start;
00799         indexMap[start]=start;
00800     }
00801 
00802     return TRUE;
00803 }
00804 
00805 /* API functions for logical<->visual mapping ------------------------------- */
00806 
00807 U_CAPI UTextOffset U_EXPORT2
00808 ubidi_getVisualIndex(UBiDi *pBiDi, UTextOffset logicalIndex, UErrorCode *pErrorCode) {
00809     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
00810         return 0;
00811     } else if(pBiDi==NULL) {
00812         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
00813         return 0;
00814     } else if(logicalIndex<0 || pBiDi->length<=logicalIndex) {
00815         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
00816         return 0;
00817     } else {
00818         /* we can do the trivial cases without the runs array */
00819         switch(pBiDi->direction) {
00820         case UBIDI_LTR:
00821             return logicalIndex;
00822         case UBIDI_RTL:
00823             return pBiDi->length-logicalIndex-1;
00824         default:
00825             if(pBiDi->runCount<0 && !ubidi_getRuns(pBiDi)) {
00826                 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
00827                 return 0;
00828             } else {
00829                 Run *runs=pBiDi->runs;
00830                 UTextOffset i, visualStart=0, offset, length;
00831 
00832                 /* linear search for the run, search on the visual runs */
00833                 for(i=0;; ++i) {
00834                     length=runs[i].visualLimit-visualStart;
00835                     offset=logicalIndex-GET_INDEX(runs[i].logicalStart);
00836                     if(offset>=0 && offset<length) {
00837                         if(IS_EVEN_RUN(runs[i].logicalStart)) {
00838                             /* LTR */
00839                             return visualStart+offset;
00840                         } else {
00841                             /* RTL */
00842                             return visualStart+length-offset-1;
00843                         }
00844                     }
00845                     visualStart+=length;
00846                 }
00847             }
00848         }
00849     }
00850 }
00851 
00852 U_CAPI UTextOffset U_EXPORT2
00853 ubidi_getLogicalIndex(UBiDi *pBiDi, UTextOffset visualIndex, UErrorCode *pErrorCode) {
00854     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
00855         return 0;
00856     } else if(pBiDi==NULL) {
00857         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
00858         return 0;
00859     } else if(visualIndex<0 || pBiDi->length<=visualIndex) {
00860         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
00861         return 0;
00862     } else {
00863         /* we can do the trivial cases without the runs array */
00864         switch(pBiDi->direction) {
00865         case UBIDI_LTR:
00866             return visualIndex;
00867         case UBIDI_RTL:
00868             return pBiDi->length-visualIndex-1;
00869         default:
00870             if(pBiDi->runCount<0 && !ubidi_getRuns(pBiDi)) {
00871                 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
00872                 return 0;
00873             } else {
00874                 Run *runs=pBiDi->runs;
00875                 UTextOffset i, runCount=pBiDi->runCount, start;
00876 
00877                 if(runCount<=10) {
00878                     /* linear search for the run */
00879                     for(i=0; visualIndex>=runs[i].visualLimit; ++i) {}
00880                 } else {
00881                     /* binary search for the run */
00882                     UTextOffset begin=0, limit=runCount;
00883 
00884                     /* the middle if() will guaranteed find the run, we don't need a loop limit */
00885                     for(;;) {
00886                         i=(begin+limit)/2;
00887                         if(visualIndex>=runs[i].visualLimit) {
00888                             begin=i+1;
00889                         } else if(i==0 || visualIndex>=runs[i-1].visualLimit) {
00890                             break;
00891                         } else {
00892                             limit=i;
00893                         }
00894                     }
00895                 }
00896 
00897                 start=runs[i].logicalStart;
00898                 if(IS_EVEN_RUN(start)) {
00899                     /* LTR */
00900                     /* the offset in runs[i] is visualIndex-runs[i-1].visualLimit */
00901                     if(i>0) {
00902                         visualIndex-=runs[i-1].visualLimit;
00903                     }
00904                     return GET_INDEX(start)+visualIndex;
00905                 } else {
00906                     /* RTL */
00907                     return GET_INDEX(start)+runs[i].visualLimit-visualIndex-1;
00908                 }
00909             }
00910         }
00911     }
00912 }
00913 
00914 U_CAPI void U_EXPORT2
00915 ubidi_getLogicalMap(UBiDi *pBiDi, UTextOffset *indexMap, UErrorCode *pErrorCode) {
00916     UBiDiLevel *levels;
00917 
00918     /* ubidi_getLevels() checks all of its and our arguments */
00919     if((levels=(UBiDiLevel *)ubidi_getLevels(pBiDi, pErrorCode))==NULL) {
00920         /* no op */
00921     } else if(indexMap==NULL) {
00922         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
00923     } else {
00924         ubidi_reorderLogical(levels, pBiDi->length, indexMap);
00925     }
00926 }
00927 
00928 U_CAPI void U_EXPORT2
00929 ubidi_getVisualMap(UBiDi *pBiDi, UTextOffset *indexMap, UErrorCode *pErrorCode) {
00930     /* ubidi_countRuns() checks all of its and our arguments */
00931     if(ubidi_countRuns(pBiDi, pErrorCode)<=0) {
00932         /* no op */
00933     } else if(indexMap==NULL) {
00934         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
00935     } else {
00936         /* fill a visual-to-logical index map using the runs[] */
00937         Run *runs=pBiDi->runs, *runsLimit=runs+pBiDi->runCount;
00938         UTextOffset logicalStart, visualStart, visualLimit;
00939 
00940         visualStart=0;
00941         for(; runs<runsLimit; ++runs) {
00942             logicalStart=runs->logicalStart;
00943             visualLimit=runs->visualLimit;
00944             if(IS_EVEN_RUN(logicalStart)) {
00945                 do { /* LTR */
00946                     *indexMap++ = logicalStart++;
00947                 } while(++visualStart<visualLimit);
00948             } else {
00949                 REMOVE_ODD_BIT(logicalStart);
00950                 logicalStart+=visualLimit-visualStart;  /* logicalLimit */
00951                 do { /* RTL */
00952                     *indexMap++ = --logicalStart;
00953                 } while(++visualStart<visualLimit);
00954             }
00955             /* visualStart==visualLimit; */
00956         }
00957     }
00958 }
00959 
00960 U_CAPI void U_EXPORT2
00961 ubidi_invertMap(const UTextOffset *srcMap, UTextOffset *destMap, UTextOffset length) {
00962     if(srcMap!=NULL && destMap!=NULL) {
00963         srcMap+=length;
00964         while(length>0) {
00965             destMap[*--srcMap]=--length;
00966         }
00967     }
00968 }

Generated at Tue Dec 5 10:47:55 2000 for ICU by doxygen1.2.3 written by Dimitri van Heesch, © 1997-2000