private int getScriptIndex(int script) {
    if(script < 0) {
        return 0;
    } else if(script < numScripts) {
        return scriptsIndex[script];
    } else if(script < Collator.ReorderCodes.FIRST) {
        return 0;
    } else {
        script -= Collator.ReorderCodes.FIRST;
        if(script < MAX_NUM_SPECIAL_REORDER_CODES) {
            return scriptsIndex[numScripts + script];
        } else {
            return 0;
        }
    }
}
 

/**
 * Gets a script or reorder code from its string representation.
 * @return the script/reorder code, or
 * -1 if not recognized
 */
public static int getReorderCode(String word) {
    for(int i = 0; i < gSpecialReorderCodes.length; ++i) {
        if(word.equalsIgnoreCase(gSpecialReorderCodes[i])) {
            return Collator.ReorderCodes.FIRST + i;
        }
    }
    try {
        int script = UCharacter.getPropertyValueEnum(UProperty.SCRIPT, word);
        if(script >= 0) {
            return script;
        }
    } catch (IllegalIcuArgumentException e) {
        // fall through
    }
    if(word.equalsIgnoreCase("others")) {
        return Collator.ReorderCodes.OTHERS;  // same as Zzzz = USCRIPT_UNKNOWN 
    }
    return -1;
}
 

private int findOrInsertNodeForRootCE(long ce, int strength) {
    assert((int)(ce >>> 56) != Collation.UNASSIGNED_IMPLICIT_BYTE);

    // Find or insert the node for each of the root CE's weights,
    // down to the requested level/strength.
    // Root CEs must have common=zero quaternary weights (for which we never insert any nodes).
    assert((ce & 0xc0) == 0);
    int index = findOrInsertNodeForPrimary(ce >>> 32);
    if(strength >= Collator.SECONDARY) {
        int lower32 = (int)ce;
        index = findOrInsertWeakNode(index, lower32 >>> 16, Collator.SECONDARY);
        if(strength >= Collator.TERTIARY) {
            index = findOrInsertWeakNode(index, lower32 & Collation.ONLY_TERTIARY_MASK,
                                        Collator.TERTIARY);
        }
    }
    return index;
}
 

/**
 * Makes and inserts a new tailored node into the list, after the one at index.
 * Skips over nodes of weaker strength to maintain collation order
 * ("postpone insertion").
 * @return the new node's index
 */
private int insertTailoredNodeAfter(int index, int strength) {
    assert(0 <= index && index < nodes.size());
    if(strength >= Collator.SECONDARY) {
        index = findCommonNode(index, Collator.SECONDARY);
        if(strength >= Collator.TERTIARY) {
            index = findCommonNode(index, Collator.TERTIARY);
        }
    }
    // Postpone insertion:
    // Insert the new node before the next one with a strength at least as strong.
    long node = nodes.elementAti(index);
    int nextIndex;
    while((nextIndex = nextIndexFromNode(node)) != 0) {
        node = nodes.elementAti(nextIndex);
        if(strengthFromNode(node) <= strength) { break; }
        // Skip the next node which has a weaker (larger) strength than the new one.
        index = nextIndex;
    }
    node = IS_TAILORED | nodeFromStrength(strength);
    return insertNodeBetween(index, nextIndex, node);
}
 

private boolean loadGroups(CollationData data) {
    headerLength = 1 + NUM_SPECIAL_GROUPS;
    int r0 = (CollationFastLatin.VERSION << 8) | headerLength;
    result.append((char)r0);
    // The first few reordering groups should be special groups
    // (space, punct, ..., digit) followed by Latn, then Grek and other scripts.
    for(int i = 0; i < NUM_SPECIAL_GROUPS; ++i) {
        lastSpecialPrimaries[i] = data.getLastPrimaryForGroup(Collator.ReorderCodes.FIRST + i);
        if(lastSpecialPrimaries[i] == 0) {
            // missing data
            return false;
        }
        result.append(0);  // reserve a slot for this group
    }

    firstDigitPrimary = data.getFirstPrimaryForGroup(Collator.ReorderCodes.DIGIT);
    firstLatinPrimary = data.getFirstPrimaryForGroup(UScript.LATIN);
    lastLatinPrimary = data.getLastPrimaryForGroup(UScript.LATIN);
    if(firstDigitPrimary == 0 || firstLatinPrimary == 0) {
        // missing data
        return false;
    }
    return true;
}
 

private static void setCollatorStrength(RuleBasedCollator collator, CollationSpecifier specifier) {
    if (specifier.caseSensitive() && specifier.accentSensitive()) {
        collator.setStrength(Collator.TERTIARY);
        collator.setCaseLevel(false);
    }
    else if (specifier.caseSensitive() && !specifier.accentSensitive()) {
        collator.setCaseLevel(true);
        collator.setStrength(Collator.PRIMARY);
    }
    else if (!specifier.caseSensitive() && specifier.accentSensitive()) {
        collator.setStrength(Collator.SECONDARY);
        collator.setCaseLevel(false);
    }
    else {
        collator.setStrength(Collator.PRIMARY);
        collator.setCaseLevel(false);
    }
}
 

private String createStaticFields() {
	HashSet<String> added= new HashSet<String>();
	List<NLSSubstitution> subs= new ArrayList<NLSSubstitution>();
	for (int i= 0; i < fNLSSubstitutions.length; i++) {
		NLSSubstitution substitution= fNLSSubstitutions[i];
		int newState= substitution.getState();
		if ((substitution.hasStateChanged() || substitution.isAccessorRename())&& newState == NLSSubstitution.EXTERNALIZED) {
			if (added.add(substitution.getKey()))
				subs.add(substitution);
		}
	}
	Collections.sort(subs, new Comparator<NLSSubstitution>() {
		private Collator fCollator= Collator.getInstance();
		public int compare(NLSSubstitution s0, NLSSubstitution s1) {
			return fCollator.compare(s0.getKey(), s1.getKey());
		}
	});
	StringBuffer buf= new StringBuffer();
	for (Iterator<NLSSubstitution> iter= subs.iterator(); iter.hasNext();) {
		NLSSubstitution element= iter.next();
		appendStaticField(buf, element);
	}
	return buf.toString();
}
 

private synchronized void ensurePagesRegistered() {
	if (fPageDescriptors != null)
		return;
	
	ArrayList<CleanUpTabPageDescriptor> result= new ArrayList<CleanUpTabPageDescriptor>();

	IExtensionPoint point= Platform.getExtensionRegistry().getExtensionPoint(JavaPlugin.getPluginId(), EXTENSION_POINT_NAME);
	IConfigurationElement[] elements= point.getConfigurationElements();
	for (int i= 0; i < elements.length; i++) {
		IConfigurationElement element= elements[i];

		if (TABPAGE_CONFIGURATION_ELEMENT_NAME.equals(element.getName())) {
			result.add(new CleanUpTabPageDescriptor(element));
		}
	}

	fPageDescriptors= result.toArray(new CleanUpTabPageDescriptor[result.size()]);
	Arrays.sort(fPageDescriptors, new Comparator<CleanUpTabPageDescriptor>() {
		public int compare(CleanUpTabPageDescriptor o1, CleanUpTabPageDescriptor o2) {
			String name1= o1.getName();
			String name2= o2.getName();
			return Collator.getInstance().compare(name1.replaceAll("&", ""), name2.replaceAll("&", "")); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
		}
	});
}
 

public int compare(String o1, String o2) {
	if (o1.equals(o2))
		return 0;

	History history= QualifiedTypeNameHistory.getDefault();

	int pos1= history.getPosition(o1);
	int pos2= history.getPosition(o2);

	if (pos1 == pos2)
		return Collator.getInstance().compare(o1, o2);

	if (pos1 > pos2) {
		return -1;
	} else {
		return 1;
	}
}
 

private void initializeCollator( ) throws DataException
{
	if ( session != null )
	{
		IBaseDataSetDesign design = ( (DataEngineImpl) this.session.getEngine( ) ).getDataSetDesign( getDataSetName( ) );
		if ( design != null )
		{
			String nullOrdering = design.getNullsOrdering( );
			Collator collator = design.getCompareLocale( ) == null ? null
					: Collator.getInstance( design.getCompareLocale( ) );

			dataSet.setCompareLocale( collator );
			dataSet.setNullest( nullOrdering );

			dataSet.getScriptScope( ).put( "compare_locale",
					dataSet.getScriptScope( ),
					collator );
		}
	}
}
 

public Object execute( Object[] args, IScriptFunctionContext context ) throws BirtException
{
	Collator collator = (Collator) context.findProperty( "compare_locale" );
	if ( args == null || args.length != 3 )
		throw new IllegalArgumentException( MessageFormat.format( WRONG_ARGUMENT,
				new Object[]{
					BETWEEN
				} ) );
	
	try
	{
		return this.mode
				? Boolean.valueOf( compare( args[0], args[1],collator ) >= 0
						&& compare( args[0], args[2],collator ) <= 0 )
				: Boolean.valueOf( !( compare( args[0], args[1],collator ) >= 0 && compare( args[0],
						args[2],collator ) <= 0 ) );
	}
	catch ( BirtException e )
	{
		throw new IllegalArgumentException( e.getLocalizedMessage( ) );
	}
}
 

private List<String> getCollationInfo() {
    // FIXME: spec issue? Search collators cannot specify any other collation type through a Unicode extension
    // value. Does this apply to all Collator implementations or just when implemented with ICU? If the former,
    // does it make sense to change the spec to make it more clear that %Collator%.[[SearchLocaleData]] always
    // returns a list containing only `null` for the "co" extension key?
    if (usage == CollatorUsage.Search) {
        return Collections.singletonList((String) null);
    }
    String[] values = Collator.getKeywordValuesForLocale("collation", locale, false);
    ArrayList<String> result = new ArrayList<>(values.length);
    result.add(null); // null must be first value, cf. 10.2.3
    for (int i = 0; i < values.length; ++i) {
        CollationType type = CollationType.forName(values[i]);
        if (type == CollationType.standard || type == CollationType.search) {
            // 'standard' and 'search' must not be elements of 'co' array, cf. 10.2.3
            continue;
        }
        result.add(type.getName());
    }
    return result;
}
 

@Override
@Nonnull
public TextCollator getTextCollator(@Nonnull String locale, int strength) {
    return MapUtils.computeIfAbsent(collators, Pair.of(locale, strength), key -> {
        final Collator collator = DEFAULT_LOCALE.equals(locale) ?
                                  Collator.getInstance() :
                                  Collator.getInstance(new ULocale(locale));
        collator.setStrength(strength);
        return new TextCollatorICU(collator);
    });
}
 

/**
 * Explicitly set the collator for this object.
 * @param collator The collator object to be passed.
 * @return this, for chaining
 * @draft ICU 3.6
 * @provisional This API might change or be removed in a future release.
 */
public GlobalizationPreferences setCollator(Collator collator) {
    if (isFrozen()) {
        throw new UnsupportedOperationException("Attempt to modify immutable object");
    }
    try {
        this.collator = (Collator) collator.clone(); // clone for safety
    } catch (CloneNotSupportedException e) {
            throw new ICUCloneNotSupportedException("Error in cloning collator", e);
    }
    return this;
}
 

/**
 * Set the sort conditions
 * 
 * @param sortKeys
 * @param sortOrderings
 */
void setSortCondition( Object[] sortKeys, boolean[] sortOrderings, int[] sortStrength, ULocale[] sortLocale )
{
	this.sortKeys = sortKeys;
	this.sortDirections = sortOrderings;
	this.comparator = new Collator[this.sortKeys.length];
	this.compareHints = new CompareHints[this.sortKeys.length];
	for( int i = 0; i < this.comparator.length; i++ )
	{
		this.comparator[i] = sortStrength[i] == ISortDefinition.ASCII_SORT_STRENGTH
				? null : Collator.getInstance( sortLocale[i]);
		this.compareHints[i] = new CompareHints( this.comparator[i], null );
	}
}
 

public int[] getEquivalentScripts(int script) {
    int index = getScriptIndex(script);
    if(index == 0) { return EMPTY_INT_ARRAY; }
    if(script >= Collator.ReorderCodes.FIRST) {
        // Special groups have no aliases.
        return new int[] { script };
    }

    int length = 0;
    for(int i = 0; i < numScripts; ++i) {
        if(scriptsIndex[i] == index) {
            ++length;
        }
    }
    int[] dest = new int[length];
    if(length == 1) {
        dest[0] = script;
        return dest;
    }
    length = 0;
    for(int i = 0; i < numScripts; ++i) {
        if(scriptsIndex[i] == index) {
            dest[length++] = i;
        }
    }
    return dest;
}
 

private void parseRuleChain() throws ParseException {
    int resetStrength = parseResetAndPosition();
    boolean isFirstRelation = true;
    for(;;) {
        int result = parseRelationOperator();
        if(result < 0) {
            if(ruleIndex < rules.length() && rules.charAt(ruleIndex) == 0x23) {
                // '#' starts a comment, until the end of the line
                ruleIndex = skipComment(ruleIndex + 1);
                continue;
            }
            if(isFirstRelation) {
                setParseError("reset not followed by a relation");
            }
            return;
        }
        int strength = result & STRENGTH_MASK;
        if(resetStrength < Collator.IDENTICAL) {
            // reset-before rule chain
            if(isFirstRelation) {
                if(strength != resetStrength) {
                    setParseError("reset-before strength differs from its first relation");
                    return;
                }
            } else {
                if(strength < resetStrength) {
                    setParseError("reset-before strength followed by a stronger relation");
                    return;
                }
            }
        }
        int i = ruleIndex + (result >> OFFSET_SHIFT);  // skip over the relation operator
        if((result & STARRED_FLAG) == 0) {
            parseRelationStrings(strength, i);
        } else {
            parseStarredCharacters(strength, i);
        }
        isFirstRelation = false;
    }
}
 

private int parseResetAndPosition() throws ParseException {
    int i = skipWhiteSpace(ruleIndex + 1);
    int j;
    char c;
    int resetStrength;
    if(rules.regionMatches(i, BEFORE, 0, BEFORE.length()) &&
            (j = i + BEFORE.length()) < rules.length() &&
            PatternProps.isWhiteSpace(rules.charAt(j)) &&
            ((j = skipWhiteSpace(j + 1)) + 1) < rules.length() &&
            0x31 <= (c = rules.charAt(j)) && c <= 0x33 &&
            rules.charAt(j + 1) == 0x5d) {
        // &[before n] with n=1 or 2 or 3
        resetStrength = Collator.PRIMARY + (c - 0x31);
        i = skipWhiteSpace(j + 2);
    } else {
        resetStrength = Collator.IDENTICAL;
    }
    if(i >= rules.length()) {
        setParseError("reset without position");
        return UCOL_DEFAULT;
    }
    if(rules.charAt(i) == 0x5b) {  // '['
        i = parseSpecialPosition(i, rawBuilder);
    } else {
        i = parseTailoringString(i, rawBuilder);
    }
    try {
        sink.addReset(resetStrength, rawBuilder);
    } catch(Exception e) {
        setParseError("adding reset failed", e);
        return UCOL_DEFAULT;
    }
    ruleIndex = i;
    return resetStrength;
}
 

private static int compareAsString( Object obj1, Object obj2, Collator comp )
		throws BirtException
{
	return comp == null ? DataTypeUtil.toString( obj1 )
			.compareTo( DataTypeUtil.toString( obj2 ) )
			: comp.compare( DataTypeUtil.toString( obj1 ),
					DataTypeUtil.toString( obj2 ) );
}
 

void sort( List aggregateData, SortOption so, Collator collator )
{
	if ( so == null )
	{
		return;
	}

	this.ascending = so == SortOption.ASCENDING_LITERAL;
	this.collator = collator;

	Collections.sort( aggregateData, this );
}
 

/**
 * Picks one of the current CEs and finds or inserts a node in the graph
 * for the CE + strength.
 */
private int findOrInsertNodeForCEs(int strength) {
    assert(Collator.PRIMARY <= strength && strength <= Collator.QUATERNARY);

    // Find the last CE that is at least as "strong" as the requested difference.
    // Note: Stronger is smaller (Collator.PRIMARY=0).
    long ce;
    for(;; --cesLength) {
        if(cesLength == 0) {
            ce = ces[0] = 0;
            cesLength = 1;
            break;
        } else {
            ce = ces[cesLength - 1];
        }
        if(ceStrength(ce) <= strength) { break; }
    }

    if(isTempCE(ce)) {
        // No need to findCommonNode() here for lower levels
        // because insertTailoredNodeAfter() will do that anyway.
        return indexFromTempCE(ce);
    }

    // root CE
    if((int)(ce >>> 56) == Collation.UNASSIGNED_IMPLICIT_BYTE) {
        throw new UnsupportedOperationException(
                "tailoring relative to an unassigned code point not supported");
    }
    return findOrInsertNodeForRootCE(ce, strength);
}
 

private static int ceStrength(long ce) {
    return
        isTempCE(ce) ? strengthFromTempCE(ce) :
        (ce & 0xff00000000000000L) != 0 ? Collator.PRIMARY :
        ((int)ce & 0xff000000) != 0 ? Collator.SECONDARY :
        ce != 0 ? Collator.TERTIARY :
        Collator.IDENTICAL;
}
 

/**
 * Create a new ICUCollatedTermAttributeImpl
 * @param collator Collation key generator
 */
public ICUCollatedTermAttributeImpl(Collator collator) {
  // clone the collator: see http://userguide.icu-project.org/collation/architecture
  try {
    this.collator = (Collator) collator.clone();
  } catch (CloneNotSupportedException e) {
    throw new RuntimeException(e);
  }
}
 

/**
 * Create a new ICUCollationDocValuesField.
 * <p>
 * NOTE: you should not create a new one for each document, instead
 * just make one and reuse it during your indexing process, setting
 * the value via {@link #setStringValue(String)}.
 * @param name field name
 * @param collator Collator for generating collation keys.
 */
// TODO: can we make this trap-free? maybe just synchronize on the collator
// instead? 
public ICUCollationDocValuesField(String name, Collator collator) {
  super(name, SortedDocValuesField.TYPE);
  this.name = name;
  try {
    this.collator = (Collator) collator.clone();
  } catch (CloneNotSupportedException e) {
    throw new RuntimeException(e);
  }
  fieldsData = bytes; // so wrong setters cannot be called
}
 

public void testThreadSafe() throws Exception {
  int iters = 20 * RANDOM_MULTIPLIER;
  for (int i = 0; i < iters; i++) {
    Locale locale = Locale.GERMAN;
    Collator collator = Collator.getInstance(locale);
    collator.setStrength(Collator.IDENTICAL);
    Analyzer a = new ICUCollationKeyAnalyzer(collator);
    assertThreadSafe(a);
    a.close();
  }
}
 

public void testBasic() throws Exception {
  Directory dir = newDirectory();
  RandomIndexWriter iw = new RandomIndexWriter(random(), dir);
  Document doc = new Document();
  Field field = newField("field", "", StringField.TYPE_STORED);
  ICUCollationDocValuesField collationField = new ICUCollationDocValuesField("collated", Collator.getInstance(ULocale.ENGLISH));
  doc.add(field);
  doc.add(collationField);

  field.setStringValue("ABC");
  collationField.setStringValue("ABC");
  iw.addDocument(doc);
  
  field.setStringValue("abc");
  collationField.setStringValue("abc");
  iw.addDocument(doc);
  
  IndexReader ir = iw.getReader();
  iw.close();
  
  IndexSearcher is = newSearcher(ir);
  
  SortField sortField = new SortField("collated", SortField.Type.STRING);
  
  TopDocs td = is.search(new MatchAllDocsQuery(), 5, new Sort(sortField));
  assertEquals("abc", ir.document(td.scoreDocs[0].doc).get("field"));
  assertEquals("ABC", ir.document(td.scoreDocs[1].doc).get("field"));
  ir.close();
  dir.close();
}
 

public void testRanges() throws Exception {
  Directory dir = newDirectory();
  RandomIndexWriter iw = new RandomIndexWriter(random(), dir);
  Document doc = new Document();
  Field field = newField("field", "", StringField.TYPE_STORED);
  Collator collator = Collator.getInstance(); // uses -Dtests.locale
  if (random().nextBoolean()) {
    collator.setStrength(Collator.PRIMARY);
  }
  ICUCollationDocValuesField collationField = new ICUCollationDocValuesField("collated", collator);
  doc.add(field);
  doc.add(collationField);
  
  int numDocs = atLeast(500);
  for (int i = 0; i < numDocs; i++) {
    String value = TestUtil.randomSimpleString(random());
    field.setStringValue(value);
    collationField.setStringValue(value);
    iw.addDocument(doc);
  }
  
  IndexReader ir = iw.getReader();
  iw.close();
  IndexSearcher is = newSearcher(ir);
  
  int numChecks = atLeast(100);
  for (int i = 0; i < numChecks; i++) {
    String start = TestUtil.randomSimpleString(random());
    String end = TestUtil.randomSimpleString(random());
    BytesRef lowerVal = new BytesRef(collator.getCollationKey(start).toByteArray());
    BytesRef upperVal = new BytesRef(collator.getCollationKey(end).toByteArray());
    doTestRanges(is, start, end, lowerVal, upperVal, collator);
  }
  
  ir.close();
  dir.close();
}
 

private void doTestRanges(IndexSearcher is, String startPoint, String endPoint, BytesRef startBR, BytesRef endBR, Collator collator) throws Exception { 
  SortedDocValues dvs = MultiDocValues.getSortedValues(is.getIndexReader(), "collated");
  for(int docID=0;docID<is.getIndexReader().maxDoc();docID++) {
    Document doc = is.doc(docID);
    String s = doc.getField("field").stringValue();
    boolean collatorAccepts = collator.compare(s, startPoint) >= 0 && collator.compare(s, endPoint) <= 0;
    assertEquals(docID, dvs.nextDoc());
    BytesRef br = dvs.binaryValue();
    boolean luceneAccepts = br.compareTo(startBR) >= 0 && br.compareTo(endBR) <= 0;
    assertEquals(collatorAccepts, luceneAccepts);
  }
}
 

/**
 * Compare the two objects
 * @param o1 object1
 * @param 02 object2
 * @return the compare result
 */
public int compare( Object o1, Object o2 )
{
	String name1 = null;
	String name2 = null;

	if ( o1 instanceof DesignElementHandle
			&& o2 instanceof DesignElementHandle )
	{
		name1 = ( (DesignElementHandle) o1 ).getDefn( ).getName( );
		name2 = ( (DesignElementHandle) o2 ).getDefn( ).getName( );

		if ( ascending )
		{
			ret = Collator.getInstance( ).compare( name1, name2 );
		}
		else
		{
			ret = Collator.getInstance( ).compare( name2, name1 );
		}
		if ( ret != 0 )
		{
			return ret;
		}

		// if ret == 0
		AlphabeticallyComparator comparator = new AlphabeticallyComparator( );
		return comparator.compare( o1, o2 );

	}

	return 0;
}
 

/**
 * Read custom rules from a file, and create a RuleBasedCollator
 * The file cannot support comments, as # might be in the rules!
 */
static Collator createFromRules(String fileName, ResourceLoader loader) {
  InputStream input = null;
  try {
   input = loader.openResource(fileName);
   String rules = IOUtils.toString(input, "UTF-8");
   return new RuleBasedCollator(rules);
  } catch (Exception e) {
    // io error or invalid rules
    throw new RuntimeException(e);
  } finally {
    IOUtils.closeQuietly(input);
  }
}