/*
   Copyright (c) 2008 Health Market Science, Inc.
   
   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 com.healthmarketscience.jackcess.impl;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Map;
  import java.util.Set;
  
  import static com.healthmarketscience.jackcess.impl.ByteUtil.ByteStream;
  
  /**
   * The "general legacy" (access 2000-2007) weight table, and the encoder which
   * turns a text value into an index entry.  Every other collation extends this
   * one: a family replaces the weight table, and a tailoring moves a few
   * characters against the table of its family.
   *
   * @author James Ahlborn
   */
  public class GeneralLegacyIndexCodes {
  
    static final int MAX_TEXT_INDEX_CHAR_LENGTH =
      (JetFormat.TEXT_FIELD_MAX_LENGTH / JetFormat.TEXT_FIELD_UNIT_SIZE);
  
    static final byte END_TEXT = (byte)0x01;
    static final byte END_EXTRA_TEXT = (byte)0x00;
  
    // unprintable char is removed from normal text.
    // pattern for unprintable chars in the extra bytes:
    // 01 01 01 <pos> 06  <code> )
    // <pos> = 7 + (4 * char_pos) | 0x8000 (as short)
    // <code> = char code
    // in ms access, char_pos counts the two byte primary units written so far,
    // a position in the primary output rather than a count of extra codes
    // bytes.  the 06 is the type byte of the char's weight table entry and
    // <code> is that entry's low byte
    static final int UNPRINTABLE_COUNT_START = 7;
    static final int UNPRINTABLE_COUNT_MULTIPLIER = 4;
    static final int UNPRINTABLE_OFFSET_FLAGS = 0x8000;
    static final byte UNPRINTABLE_MIDFIX = (byte)0x06;
    /** a weight table whose entries are not all the same number of bytes wide,
        which the general legacy table is: its latin codes take one byte and its
        arabic codes two */
    static final int VARIABLE_UNIT_WIDTH = 0;
    /** what stands in for a character whose weight is shorter than a whole
        entry of its table, where every other character takes
        INTERNATIONAL_EXTRA_PLACEHOLDER */
    static final byte SHORT_WEIGHT_EXTRA_PLACEHOLDER = (byte)0x00;
  
    /** what a repeat mark writes when no weight has been written before it */
    private static final byte[] NO_REPEATED_WEIGHT = {(byte)0xFF, (byte)0xFF};
  
    // international char is replaced with ascii char.
    // pattern for international chars in the extra bytes:
    // [ 02 (for each normal char) ] [ <symbol_code> (for each inat char) ]
    static final byte INTERNATIONAL_EXTRA_PLACEHOLDER = (byte)0x02;
  
    // see writeCrazyCodes
    static final byte CRAZY_CODE_START = (byte)0x80;
    static final byte CRAZY_CODE_1 = (byte)0x02;
    static final byte CRAZY_CODE_2 = (byte)0x03;
    // the suffix which follows the crazy codes is
    // ff 02 [80 x numRepeats] ff [80 x numRepeats], where numRepeats grows with
    // the number of chars on the crazy path, one repeat per (partial) group of
    // CRAZY_CODES_PER_SUFFIX_REPEAT chars
    static final byte CRAZY_CODES_SUFFIX_START = (byte)0xFF;
    static final byte CRAZY_CODES_SUFFIX_MIDFIX = (byte)0x02;
    static final byte CRAZY_CODES_SUFFIX_SEPARATOR = (byte)0xFF;
    static final byte CRAZY_CODES_SUFFIX_REPEAT = (byte)0x80;
    static final int CRAZY_CODES_PER_SUFFIX_REPEAT = 7;
    /** what a repeat mark writes before the weight it copies, where that weight
        is more than one entry */
    static final byte LONG_REPEATED_WEIGHT_PREFIX = (byte)0x05;
    /** the entry which leads the weight of a cjk ideograph, where the entry
        after it is the ideograph's own.  Such a weight is two entries and stands
        for one character, which every other weight of two entries does not */
    static final byte[] CJK_WEIGHT_LEAD = {(byte)0xFD, (byte)0xFF};
    /** how many weight entries ms access keeps room for in each character of a
        value, which a character of four entries writes past */
    static final int WEIGHT_ENTRIES_PER_CHAR = 3;
    /** how many tertiary weights ms access keeps room for in each character of
       a value, which a value of more character units writes past */
   static final int TERTIARY_WEIGHTS_PER_CHAR = 3;
   /** the tertiary weight of every character the tertiary weights file does
       not name */
   static final byte DEFAULT_TERTIARY_WEIGHT = (byte)0x01;
   /** a second run of crazy codes says, for each character which took a crazy
       code, whether it is a character of its own, a repeat mark standing for
       the one before it, or the prolonged sound mark */
   static final byte CRAZY_COPY_CODE_CHAR = (byte)0x01;
   static final byte CRAZY_COPY_CODE_REPEAT = (byte)0x02;
   static final byte CRAZY_COPY_CODE_PROLONGED = (byte)0x03;
   static final byte CRAZY_CODES_UNPRINT_SUFFIX = (byte)0xFF;
 
   /** the name this family carries in the name of a codes file */
   static final String GEN_LEG_FAMILY = "genleg";
 
   // the weight table, one handler per code point
   private static final String CODES_FILE =
     DatabaseImpl.RESOURCE_PATH + "index_codes_" + GEN_LEG_FAMILY + ".txt";
   private static final String EXT_CODES_FILE =
     DatabaseImpl.RESOURCE_PATH + "index_codes_ext_" + GEN_LEG_FAMILY + ".txt";
 
   /**
    * Enum which classifies the types of char encoding strategies used when
    * creating text index entries.
    */
   enum Type {
     SIMPLE("S") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseSimpleCodes(codeStrings);
       }
     },
     INTERNATIONAL("I") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseInternationalCodes(codeStrings);
       }
     },
     UNPRINTABLE("U") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseUnprintableCodes(codeStrings);
       }
     },
     UNPRINTABLE_EXT("P") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseUnprintableExtCodes(codeStrings);
       }
     },
     INTERNATIONAL_EXT("Z") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseInternationalExtCodes(codeStrings);
       }
     },
     SIGNIFICANT("G") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseSignificantCodes(codeStrings);
       }
     },
     SURROGATE("Q") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         // these are not parsed from the codes files
         throw new UnsupportedOperationException();
       }
     },
     IGNORED("X") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return IGNORED_CHAR_HANDLER;
       }
     },
     REPEAT("R") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         return parseRepeatCodes(codeStrings);
       }
     },
     // this type only reads the prefix of the prolonged sound mark.  its handler
     // reports Type.REPEAT, so the writer handles it as a repeat mark, and
     // getType never returns this type
     PROLONGED("V") {
       @Override public CharHandler parseCodes(String[] codeStrings) {
         // the mark has no codes of its own, so a line which gives it any
         // fails the load
         if((codeStrings.length != 1) || !codeStrings[0].isEmpty()) {
           throw new IllegalStateException("Unexpected code strings " +
                                           Arrays.asList(codeStrings));
         }
         return PROLONGED_SOUND_CHAR_HANDLER;
       }
     };
 
     private final String _prefixCode;
 
     private Type(String prefixCode) {
       _prefixCode = prefixCode;
     }
 
     public String getPrefixCode() {
       return _prefixCode;
     }
 
     public abstract CharHandler parseCodes(String[] codeStrings);
   }
 
   /** the Types by the prefix code which names each one in a codes file */
   private static final Map<String,Type> PREFIX_MAP = createPrefixMap();
 
   private static Map<String,Type> createPrefixMap() {
     Map<String,Type> prefixMap = new HashMap<>();
     for(Type type : Type.values()) {
       prefixMap.put(type.getPrefixCode(), type);
     }
     return prefixMap;
   }
 
   /** the first byte of the two byte inline code of a kana */
   private static final byte KANA_CODE_PREFIX = (byte)0x7F;
   /** the inline code of the vowel a kana ends on, keyed by the second byte of
       the kana's own inline code, with 0 where the mark copies instead.  the
       vowel cannot be read off the character: the rows of the syllabary are
       not contiguous, and a voiced kana, a small kana, a circled kana and a
       halfwidth kana all carry the code of the plain kana they sort as.  the
       vowel follows that code, so a character the two families weigh
       differently takes a different vowel in each */
   private static final byte[] KANA_VOWEL_CODES = {
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x03,
     0x04, 0x05, 0x06, 0x00, 0x00, 0x00, 0x02, 0x03, 0x04, 0x05, 0x06, 0x00,
     0x00, 0x00, 0x02, 0x03, 0x04, 0x05, 0x06, 0x00, 0x00, 0x00, 0x02, 0x03,
     0x04, 0x05, 0x06, 0x00, 0x00, 0x00, 0x02, 0x03, 0x04, 0x05, 0x06, 0x00,
     0x00, 0x00, 0x02, 0x03, 0x04, 0x05, 0x06, 0x00, 0x00, 0x00, 0x02, 0x00,
     0x04, 0x00, 0x06, 0x00, 0x00, 0x00, 0x02, 0x03, 0x04, 0x05, 0x06, 0x00,
     0x00, 0x00, 0x02, 0x03, 0x00, 0x05, 0x06,
   };
   /** the weight a prolonged sound mark writes for each vowel, indexed by the
       vowel's code.  the writer only reads a weight, so one array for each
       vowel serves every mark */
   private static final byte[][] KANA_VOWEL_WEIGHTS = createKanaVowelWeights();
 
   /**
    * Base class for the handlers which hold the text index character encoding
    * information.
    */
   abstract static class CharHandler {
     /** set once the whole table is read, see countCharUnits */
     private int _numCharUnits = 1;
     /** set once the whole table is read, see countCharUnits */
     private int _numPrimaryUnits = 1;
     /** set once the whole table is read, see countCharUnits */
     private byte _extraPlaceholder = INTERNATIONAL_EXTRA_PLACEHOLDER;
 
     public abstract Type getType();
     /**
      * @return whether this is the prolonged sound mark, which takes the place
      *         of the kana before it like a repeat mark but writes the code of
      *         that kana's vowel rather than a copy of the whole kana
      */
     public boolean isProlongedSound() {
       return false;
     }
     public byte[] getInlineBytes(char c) {
       return null;
     }
     /**
      * @return how many characters this one counts as in the offsets which the
      *         extra, unprintable and crazy codes carry.  A character weighed
      *         as two, such as the sharp s of "ss", counts as two
      */
     public int getNumCharUnits() {
       return _numCharUnits;
     }
     /**
      * @return how many places this character takes in the offset which an
      *         unprintable weight carries, which counts the weight entries
      *         written rather than the characters they stand for.  The general
      *         table writes every entry in two bytes, so a four byte weight is
      *         two entries there although it carries one diacritic weight
      */
     public int getNumPrimaryUnits() {
       return _numPrimaryUnits;
     }
     /**
      * @return the byte which stands in for this character in the diacritic
      *         weights where it has none of its own.  A character whose weight
      *         is shorter than a whole entry of its table takes {@code 00}
      *         rather than the usual placeholder
      */
     public byte getExtraPlaceholder() {
       return _extraPlaceholder;
     }
     public byte[] getExtraBytes() {
       return null;
     }
     public byte[] getUnprintableBytes() {
       return null;
     }
     public byte getExtraByteModifier() {
       return 0;
     }
     public byte getCrazyFlag() {
       return 0;
     }
     public boolean isSignificantChar() {
       return false;
     }
   }
 
   /**
    * CharHandler for Type.SIMPLE
    */
   private static final class SimpleCharHandler extends CharHandler {
     private final byte[] _bytes;
     private SimpleCharHandler(byte[] bytes) {
       _bytes = bytes;
     }
     @Override public Type getType() {
       return Type.SIMPLE;
     }
     @Override public byte[] getInlineBytes(char c) {
       return _bytes;
     }
   }
 
   /**
    * CharHandler for Type.INTERNATIONAL
    */
   private static final class InternationalCharHandler extends CharHandler {
     private final byte[] _bytes;
     private final byte[] _extraBytes;
     private InternationalCharHandler(byte[] bytes, byte[] extraBytes) {
       _bytes = bytes;
       _extraBytes = extraBytes;
     }
     @Override public Type getType() {
       return Type.INTERNATIONAL;
     }
     @Override public byte[] getInlineBytes(char c) {
       return _bytes;
     }
     @Override public byte[] getExtraBytes() {
       return _extraBytes;
     }
   }
 
   /**
    * CharHandler for Type.UNPRINTABLE
    */
   private static final class UnprintableCharHandler extends CharHandler {
     private final byte[] _unprintBytes;
     private UnprintableCharHandler(byte[] unprintBytes) {
       _unprintBytes = unprintBytes;
     }
     @Override public Type getType() {
       return Type.UNPRINTABLE;
     }
     @Override public byte[] getUnprintableBytes() {
       return _unprintBytes;
     }
   }
 
   /**
    * CharHandler for Type.UNPRINTABLE_EXT
    */
   private static final class UnprintableExtCharHandler extends CharHandler {
     private final byte _extraByteMod;
     private UnprintableExtCharHandler(Byte extraByteMod) {
       _extraByteMod = extraByteMod;
     }
     @Override public Type getType() {
       return Type.UNPRINTABLE_EXT;
     }
     @Override public byte getExtraByteModifier() {
       return _extraByteMod;
     }
   }
 
   /**
    * CharHandler for Type.INTERNATIONAL_EXT
    */
   private static final class InternationalExtCharHandler extends CharHandler {
     private final byte[] _bytes;
     private final byte[] _extraBytes;
     private final byte _crazyFlag;
     private InternationalExtCharHandler(byte[] bytes, byte[] extraBytes,
                                         byte crazyFlag) {
       _bytes = bytes;
       _extraBytes = extraBytes;
       _crazyFlag = crazyFlag;
     }
     @Override public Type getType() {
       return Type.INTERNATIONAL_EXT;
     }
     @Override public byte[] getInlineBytes(char c) {
       return _bytes;
     }
     @Override public byte[] getExtraBytes() {
       return _extraBytes;
     }
     @Override public byte getCrazyFlag() {
       return _crazyFlag;
     }
   }
 
   /**
    * CharHandler for Type.SIGNIFICANT
    */
   private static final class SignificantCharHandler extends CharHandler {
     private final byte[] _bytes;
     private SignificantCharHandler(byte[] bytes) {
       _bytes = bytes;
     }
     @Override public Type getType() {
       return Type.SIGNIFICANT;
     }
     @Override public byte[] getInlineBytes(char c) {
       return _bytes;
     }
     @Override public boolean isSignificantChar() {
       return true;
     }
   }
 
   /**
    * A sequence of characters which a collation weighs as a unit, such as
    * {@code ch} in czech, which is one weight of its own between h and i.  It
    * writes what a character writes, so it holds CharHandlers, and hungarian
    * needs more than one of them: it writes a doubled digraph such as
    * {@code ccs} as the weight of {@code cs} twice.
    */
   static final class Contraction
   {
     private final String _seq;
     private final CharHandler[] _handlers;
     /** where the case rule starts, which is 1 for a doubled digraph and 0
         for every other sequence */
     private final int _caseStart;
 
     Contraction(String seq, CharHandler[] handlers, int caseStart) {
       _seq = seq;
       _handlers = handlers;
       _caseStart = caseStart;
     }
 
     public int getLength() {
       return _seq.length();
     }
 
     public int getNumUnits() {
       return _handlers.length;
     }
 
     public CharHandler getHandler(int idx) {
       return _handlers[idx];
     }
 
     /**
      * Whether this sequence is the one at the given position of the value.
      * Ms access weighs a sequence as a unit only when it is written all in
      * lower case, all in upper case, or in title case, so {@code cha}
      * contracts and {@code cHa} is a {@code c} and an {@code h}.  A doubled
      * digraph such as the hungarian {@code ccs} is the leading letter and
      * then the digraph, and the rule holds for the digraph alone, so
      * {@code cCSa} contracts.
      */
     public boolean matches(String str, int idx) {
       return (str.regionMatches(true, idx, _seq, 0, _seq.length()) &&
               casesMatch(str, idx + _caseStart, idx + _seq.length()));
     }
 
     private static boolean casesMatch(String str, int start, int end) {
       boolean sawUpper = false;
       boolean sawLower = false;
       for(int i = start; i < end; ++i) {
         char c = str.charAt(i);
         if(Character.isUpperCase(c)) {
           sawUpper = true;
         } else if(Character.isLowerCase(c)) {
           sawLower = true;
         }
       }
       if(!sawUpper || !sawLower) {
         // all of one case, a character with no case counting as either
         return true;
       }
       // mixed, so only title case is left: the first character upper and no
       // other one upper
       if(!Character.isUpperCase(str.charAt(start))) {
         return false;
       }
       for(int i = start + 1; i < end; ++i) {
         if(Character.isUpperCase(str.charAt(i))) {
           return false;
         }
       }
       return true;
     }
 
     @Override
     public String toString() {
       return _seq;
     }
   }
 
   /**
    * CharHandler for Type.REPEAT, a mark which stands for the character before
    * it, such as the arabic shadda or a japanese iteration mark.  It writes a
    * copy of the weight written before it, which the handler cannot know, so
    * writeNonNullIndexTextValue supplies the bytes.
    */
   private static final CharHandler REPEAT_CHAR_HANDLER = new CharHandler() {
     @Override public Type getType() {
       return Type.REPEAT;
     }
   };
 
   /**
    * CharHandler for the prolonged sound mark, which lengthens the kana before
    * it.  The mark writes the code of the vowel that kana ends on rather than a
    * copy of the whole kana, and after anything which is not a kana it copies.
    * Its type is Type.REPEAT, because it takes the place of the character
    * before it the same way a repeat mark does.
    */
   static final CharHandler PROLONGED_SOUND_CHAR_HANDLER = new CharHandler() {
     @Override public Type getType() {
       return Type.REPEAT;
     }
     @Override public boolean isProlongedSound() {
       return true;
     }
   };
 
   /**
    * CharHandler for a Type.REPEAT mark which has a secondary weight of its
    * own, such as the voiced japanese iteration marks.  It copies the weight
    * before it like any other repeat mark and adds its own weight to the extra
    * codes.
    */
   private static final class RepeatExtraCharHandler extends CharHandler {
     private final byte[] _extraBytes;
     private RepeatExtraCharHandler(byte[] extraBytes) {
       _extraBytes = extraBytes;
     }
     @Override public Type getType() {
       return Type.REPEAT;
     }
     @Override public byte[] getExtraBytes() {
       return _extraBytes;
     }
   }
 
   /** shared CharHandler instance for Type.IGNORED */
   static final CharHandler IGNORED_CHAR_HANDLER = new CharHandler() {
     @Override public Type getType() {
       return Type.IGNORED;
     }
   };
 
   /** the surrogate char bufs are computed on the fly.  re-use a buffer for
       those */
   private static final ThreadLocal<byte[]> SURROGATE_CHAR_BUF =
     ThreadLocal.withInitial(() -> new byte[2]);
 
   /**
    * Supplies the handler for a surrogate char.  The surrogates are not in the
    * codes files, and which handler a char takes depends on where it falls in
    * the weight table, so the collations differ here.
    */
   interface SurrogateCharHandlers {
     CharHandler get(char c);
   }
 
   /** the general legacy collation gives a surrogate no weight at all, so both
       halves of a pair are ignored */
   static final SurrogateCharHandlers IGNORED_SURROGATES =
     c -> IGNORED_CHAR_HANDLER;
 
   /**
    * Base for the handlers of the surrogate chars, which are computed rather
    * than read from the codes files.  Only the general collation weights them,
    * so the general legacy collation has no subclass of this.
    */
   static abstract class SurrogateCharHandler extends CharHandler {
     private final byte[] _extraBytes;
 
     protected SurrogateCharHandler(byte extraByte) {
       _extraBytes = new byte[]{extraByte};
     }
     @Override public Type getType() {
       return Type.SURROGATE;
     }
     @Override public byte[] getExtraBytes() {
       return _extraBytes;
     }
     protected static byte[] toInlineBytes(int idxC) {
       byte[] bytes = SURROGATE_CHAR_BUF.get();
       bytes[0] = (byte)((idxC >>> 8) & 0xFF);
       bytes[1] = (byte)(idxC & 0xFF);
       return bytes;
     }
   }
 
   static final char FIRST_CHAR = (char)0x0000;
   static final char LAST_CHAR = (char)0x00FF;
   static final char FIRST_EXT_CHAR = LAST_CHAR + 1;
   static final char LAST_EXT_CHAR = (char)0xFFFF;
 
   private static final class Codes
   {
     /** handlers for the first 256 chars.  use nested class to lazy load the
         handlers */
     private static final CharHandler[] _values = loadCodes(
         CODES_FILE, FIRST_CHAR, LAST_CHAR);
   }
 
   private static final class ExtCodes
   {
     /** handlers for the rest of the chars in BMP 0.  use nested class to
         lazy load the handlers */
     private static final CharHandler[] _values = loadCodes(
         EXT_CODES_FILE, FIRST_EXT_CHAR, LAST_EXT_CHAR, IGNORED_SURROGATES,
         Codes._values);
   }
 
   static final GeneralLegacyIndexCodes GEN_LEG_INSTANCE =
     new GeneralLegacyIndexCodes();
 
   GeneralLegacyIndexCodes() {
   }
 
   /**
    * @return how many bytes a weight entry of this table takes, or
    *         {@link #VARIABLE_UNIT_WIDTH} where the widths are mixed
    */
   int getPrimaryUnitWidth() {
     return VARIABLE_UNIT_WIDTH;
   }
 
   /**
    * @return the tertiary weight of each unit of the given character, or
    *         {@code null} where every one of them is
    *         {@link #DEFAULT_TERTIARY_WEIGHT}.  The general legacy table gives
    *         no character more than three units, so a value can never write
    *         past the room the tertiary weights have and nothing here is ever
    *         read
    */
   byte[] getTertiaryWeights(char c) {
     return null;
   }
 
   /**
    * Returns the CharHandler for the given character.
    */
   CharHandler getCharHandler(char c)
   {
     if(c <= LAST_CHAR) {
       return Codes._values[c];
     }
 
     int extOffset = asUnsignedChar(c) - asUnsignedChar(FIRST_EXT_CHAR);
     return ExtCodes._values[extOffset];
   }
 
   /**
    * Returns the sequence of characters which this collation weighs as a unit
    * at the given position of the value, or {@code null} where it weighs none.
    * Most collations have no such sequence anywhere.
    */
   Contraction getContraction(String str, int idx)
   {
     return null;
   }
 
   /**
    * Loads the CharHandlers for the given range of characters from the
    * resource file with the given name.
    */
   static CharHandler[] loadCodes(String codesFilePath,
                                  char firstChar, char lastChar)
   {
     return loadCodes(codesFilePath, firstChar, lastChar, IGNORED_SURROGATES,
                      null);
   }
 
   /**
    * Loads the CharHandlers for the given range of characters from the
    * resource file with the given name, taking the handlers for the surrogate
    * chars from the given source.  The handlers of the rest of the weight
    * table, where the file holds only a part of it, make up the rest of the
    * codes which the character units are counted against.
    */
   static CharHandler[] loadCodes(String codesFilePath,
                                  char firstChar, char lastChar,
                                  SurrogateCharHandlers surrogates,
                                  CharHandler[] rest)
   {
     return loadCodes(codesFilePath, firstChar, lastChar, surrogates, rest,
                      VARIABLE_UNIT_WIDTH);
   }
 
   /**
    * Loads the CharHandlers as above, for a weight table whose entries are all
    * the given number of bytes wide.  A width of {@link #VARIABLE_UNIT_WIDTH}
    * means the table mixes widths, and then an entry is read against the one
    * byte codes the table holds.
    */
   static CharHandler[] loadCodes(String codesFilePath,
                                  char firstChar, char lastChar,
                                  SurrogateCharHandlers surrogates,
                                  CharHandler[] rest, int primaryWidth)
   {
     int numCodes = (asUnsignedChar(lastChar) - asUnsignedChar(firstChar)) + 1;
     CharHandler[] values = new CharHandler[numCodes];
 
     BufferedReader reader = null;
     try {
 
       reader = new BufferedReader(
           new InputStreamReader(
               DatabaseImpl.getResourceAsStream(codesFilePath), "US-ASCII"));
 
       int start = asUnsignedChar(firstChar);
       int end = asUnsignedChar(lastChar);
       for(int i = start; i <= end; ++i) {
         char c = (char)i;
         CharHandler ch = null;
         if(Character.isHighSurrogate(c) || Character.isLowSurrogate(c)) {
           // surrogate chars are not included in the codes files
           ch = surrogates.get(c);
         } else {
           ch = parseCodes(reader.readLine());
         }
         values[(i - start)] = ch;
       }
 
     } catch(IOException e) {
       throw new RuntimeException("failed loading index codes file " +
                                  codesFilePath, e);
     } finally {
       ByteUtil.closeQuietly(reader);
     }
 
     countCharUnits(values, rest, primaryWidth);
 
     return values;
   }
 
   /**
    * Works out which characters of a codes table are weighed as more than one
    * character, and tells each one, so the offsets which the extra and
    * unprintable codes carry come out where ms access puts them.
    *
    * A few characters stand for two, such as the sharp s for "ss" and the ash
    * for "ae", and hold the whole code of each character they stand for.  A
    * character which simply has a long code, such as "^" or "1/4", starts with
    * a prefix byte which is never a code on its own, so splitting its code into
    * equal parts never gives parts which are all codes.  That difference is the
    * test, and it needs no list of its own.
    *
    * The code width is not fixed.  The latin characters of the general legacy
    * table take one byte and the same table gives the arabic letters two, so a
    * code of mixed widths is read entry by entry against the bytes which are a
    * whole code on their own.
    */
   private static void countCharUnits(CharHandler[] values,
                                      CharHandler[] rest, int primaryWidth) {
     Set<Integer> leadBytes = null;
     if(primaryWidth == VARIABLE_UNIT_WIDTH) {
       leadBytes = new HashSet<Integer>();
       addOneByteCodes(leadBytes, values);
       if(rest != null) {
         // the parts of a code which stands for more than one character are
         // codes of the whole weight table, which a file holding only a part
         // of it does not have on its own
         addOneByteCodes(leadBytes, rest);
       }
     }
 
     for(CharHandler ch : values) {
       countCharUnits(ch, leadBytes, primaryWidth);
     }
   }
 
   /**
    * Adds the codes of the given handlers which are one byte wide.  A byte
    * which is not one of these starts a code two bytes wide, which is how a
    * code of mixed widths is read.
    */
   private static void addOneByteCodes(Set<Integer> leadBytes,
                                       CharHandler[] handlers) {
     for(CharHandler ch : handlers) {
       addOneByteCode(leadBytes, ch);
     }
   }
 
   /**
    * Works out the character units of the handlers which a tailored collation
    * moves, against the codes of the weight table it tailors, since the parts
    * of a code which stands for two characters are codes of that table.  The
    * german phone book collation, for one, moves the a, o and u umlauts to the
    * codes of "ae", "oe" and "ue".  See
    * {@link #countCharUnits(CharHandler[],CharHandler[],int)}.
    */
   static void countCharUnits(GeneralLegacyIndexCodes base,
                              CharHandler[] handlers) {
     // a code which stands for two characters is made of the codes of two
     // letters, and a letter is either in the first 256 characters or is one
     // the collation moves itself.  the croatian d and z-caron is the one
     // which needs both: the collation moves the digraph to the codes of the
     // two letters and moves the z-caron as well.  so the rest of the weight
     // table is never read, which keeps it unloaded for a database which holds
     // no character out of the first 256
     int primaryWidth = base.getPrimaryUnitWidth();
     Set<Integer> leadBytes = null;
     if(primaryWidth == VARIABLE_UNIT_WIDTH) {
       leadBytes = new HashSet<Integer>();
       for(int i = asUnsignedChar(FIRST_CHAR); i <= asUnsignedChar(LAST_CHAR);
           ++i) {
         addOneByteCode(leadBytes, base.getCharHandler((char)i));
       }
       addOneByteCodes(leadBytes, handlers);
     }
 
     for(CharHandler ch : handlers) {
       countCharUnits(ch, leadBytes, primaryWidth);
     }
   }
 
   /** adds the code of the given handler, where it is one byte wide */
   private static void addOneByteCode(Set<Integer> leadBytes, CharHandler ch) {
     byte[] bytes = inlineBytes(ch);
     if((bytes != null) && (bytes.length == 1)) {
       leadBytes.add(bytes[0] & 0xFF);
     }
   }
 
   /**
    * Tells the given handler how many characters it is weighed as, which is
    * how many weight entries its code holds.
    */
   private static void countCharUnits(CharHandler ch, Set<Integer> leadBytes,
                                      int primaryWidth) {
     byte[] bytes = inlineBytes(ch);
     if(bytes == null) {
       return;
     }
 
     int numEntries = countEntries(bytes, leadBytes, primaryWidth);
     // a weight entry is one character, in both tables.  the st ligature needs
     // the entry by entry read: its weight is a two byte entry and then a one
     // byte one, so it splits into no equal parts although it stands for two
     // characters
     int numUnits = numEntries;
     if(hasCjkLead(bytes)) {
       // a cjk ideograph is the lead entry and then its own, two entries which
       // stand for one character
       numUnits = 1;
     }
 
     byte[] extraBytes = ch.getExtraBytes();
     if(extraBytes != null) {
       // a character carries at most one diacritic weight for each character
       // it stands for, so two of them mean it stands for at least two.  the
       // greek dialytika tonos needs this, because its code does not split
       // while it carries the weights of the diaeresis and the tonos
       numUnits = Math.max(numUnits, extraBytes.length);
     }
 
     ch._numCharUnits = numUnits;
     ch._numPrimaryUnits = numEntries;
     if((primaryWidth != VARIABLE_UNIT_WIDTH) &&
        (bytes.length < primaryWidth)) {
       // the 23 lao vowels and tone marks from U+0EB0 to U+0ECB are the only
       // characters whose weight is shorter than an entry of their table, and
       // ms access gives them 00 where every other character takes the
       // placeholder
       ch._extraPlaceholder = SHORT_WEIGHT_EXTRA_PLACEHOLDER;
     }
   }
 
   /**
    * @return how many weight entries the given code holds.  Where the table
    *         writes every entry in the same number of bytes the count follows
    *         from the length, and a code one byte short of a whole entry still
    *         fills one.  Where the widths are mixed, a byte which is a whole
    *         code on its own is one entry and any other byte starts an entry of
    *         two
    */
   private static int countEntries(byte[] bytes, Set<Integer> leadBytes,
                                   int primaryWidth) {
     if(primaryWidth != VARIABLE_UNIT_WIDTH) {
       return ((bytes.length + (primaryWidth - 1)) / primaryWidth);
     }
     int numEntries = 0;
     for(int i = 0; i < bytes.length; ++numEntries) {
       i += (leadBytes.contains(bytes[i] & 0xFF) ? 1 : 2);
     }
     return numEntries;
   }
 
   /**
    * @return whether the given code is a cjk ideograph's, which is the lead
    *         entry and then the ideograph's own
    */
   private static boolean hasCjkLead(byte[] bytes) {
     return ((bytes.length == (CJK_WEIGHT_LEAD.length * 2)) &&
             (bytes[0] == CJK_WEIGHT_LEAD[0]) &&
             (bytes[1] == CJK_WEIGHT_LEAD[1]));
   }
 
   /**
    * @return the inline codes of a handler which has them, else {@code null}.
    *         a surrogate handler makes its codes out of the character it is
    *         given rather than holding them, so it carries no code of its own
    */
   private static byte[] inlineBytes(CharHandler ch) {
     if((ch == null) || (ch.getType() == Type.SURROGATE)) {
       return null;
     }
     return ch.getInlineBytes('\0');
   }
 
   /**
    * Returns a CharHandler parsed from the given line from an index codes
    * file.
    */
   static CharHandler parseCodes(String codeLine)
   {
     if(codeLine == null) {
       throw new IllegalStateException("Invalid codes file");
     }
     String prefix = codeLine.substring(0, 1);
     String suffix = ((codeLine.length() > 1) ? codeLine.substring(1) : "");
     return PREFIX_MAP.get(prefix).parseCodes(suffix.split(",", -1));
   }
 
   /**
    * Returns the handler for a repeat mark, which carries a secondary weight
    * only when the codes file gives it one.
    */
   private static CharHandler parseRepeatCodes(String[] codeStrings)
   {
     if(codeStrings.length != 1) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     if(codeStrings[0].isEmpty()) {
       return REPEAT_CHAR_HANDLER;
     }
     return new RepeatExtraCharHandler(codesToBytes(codeStrings[0], true));
   }
 
   /**
    * Returns the weight a prolonged sound mark writes after the given weight:
    * the weight of the vowel where the given weight is a kana's, and the given
    * weight itself where it is not a kana or the kana's vowel is its own code.
    */
   private static byte[] prolongedSoundBytes(byte[] lastWeight)
   {
     if((lastWeight.length != 2) || (lastWeight[0] != KANA_CODE_PREFIX)) {
       return lastWeight;
     }
     int code = lastWeight[1] & 0xFF;
     byte vowel = ((code < KANA_VOWEL_CODES.length) ?
                   KANA_VOWEL_CODES[code] : 0);
     return ((vowel == 0) ? lastWeight : KANA_VOWEL_WEIGHTS[vowel & 0xFF]);
   }
 
   private static byte[][] createKanaVowelWeights()
   {
     byte[][] weights = new byte[256][];
     for(byte vowel : KANA_VOWEL_CODES) {
       if((vowel != 0) && (weights[vowel & 0xFF] == null)) {
         weights[vowel & 0xFF] = new byte[]{KANA_CODE_PREFIX, vowel};
       }
     }
     return weights;
   }
 
   /**
    * Returns a SimpleCharHandler parsed from the given index code strings.
    */
   private static CharHandler parseSimpleCodes(String[] codeStrings)
   {
     if(codeStrings.length != 1) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     return new SimpleCharHandler(codesToBytes(codeStrings[0], true));
   }
 
   /**
    * Returns an InternationalCharHandler parsed from the given index code
    * strings.
    */
   private static CharHandler parseInternationalCodes(String[] codeStrings)
   {
     if(codeStrings.length != 2) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     return new InternationalCharHandler(codesToBytes(codeStrings[0], true),
                                         codesToBytes(codeStrings[1], true));
   }
 
   /**
    * Returns a UnprintableCharHandler parsed from the given index code
    * strings.
    */
   private static CharHandler parseUnprintableCodes(String[] codeStrings)
   {
     if(codeStrings.length != 1) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     return new UnprintableCharHandler(codesToBytes(codeStrings[0], true));
   }
 
   /**
    * Returns a UnprintableExtCharHandler parsed from the given index code
    * strings.
    */
   private static CharHandler parseUnprintableExtCodes(String[] codeStrings)
   {
     if(codeStrings.length != 1) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     byte[] bytes = codesToBytes(codeStrings[0], true);
     if(bytes.length != 1) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     return new UnprintableExtCharHandler(bytes[0]);
   }
 
   /**
    * Returns a InternationalExtCharHandler parsed from the given index code
    * strings.
    */
   private static CharHandler parseInternationalExtCodes(String[] codeStrings)
   {
     if(codeStrings.length != 3) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
 
     byte crazyFlag = ("1".equals(codeStrings[2]) ?
                       CRAZY_CODE_1 : CRAZY_CODE_2);
     return new InternationalExtCharHandler(codesToBytes(codeStrings[0], true),
                                            codesToBytes(codeStrings[1], false),
                                            crazyFlag);
   }
 
   /**
    * Returns a SignificantCharHandler parsed from the given index code strings.
    */
   private static CharHandler parseSignificantCodes(String[] codeStrings)
   {
     if(codeStrings.length != 1) {
       throw new IllegalStateException("Unexpected code strings " +
                                       Arrays.asList(codeStrings));
     }
     return new SignificantCharHandler(codesToBytes(codeStrings[0], true));
   }
 
   /**
    * Converts a string of hex encoded bytes to a byte[], optionally throwing
    * an exception if no codes are given.
    */
   private static byte[] codesToBytes(String codes, boolean required)
   {
     if(codes.length() == 0) {
       if(required) {
         throw new IllegalStateException("empty code bytes");
       }
       return null;
     }
     if((codes.length() % 2) != 0) {
       // stripped a leading 0
       codes = "0" + codes;
     }
     byte[] bytes = new byte[codes.length() / 2];
     for(int i = 0; i < bytes.length; ++i) {
       int charIdx = i*2;
       bytes[i] = (byte)(Integer.parseInt(codes.substring(charIdx, charIdx + 2),
                                          16));
     }
     return bytes;
   }
 
   /**
    * Returns the char as an unsigned int, so that it can be compared and
    * offset without the sign of a widened char getting in the way.
    */
   static int asUnsignedChar(char c)
   {
     return c & 0xFFFF;
   }
 
   /**
    * Writes the index entry of a text value: the inline weights of its
    * characters, then the extra codes, the unprintable codes and the crazy
    * flags which the characters put in the tail.
    */
   void writeNonNullIndexTextValue(
       Object value, ByteStream bout, boolean isAscending)
     throws IOException
   {
     // convert to string
     String str = toIndexCharSequence(value);
 
     // record previous entry length so we can do any post-processing
     // necessary for this entry (handling descending)
     int prevLength = bout.getLength();
 
     // now, convert each character to a "code" of one or more bytes
     ExtraCodesStream extraCodes = null;
     ByteStream unprintableCodes = null;
     ByteStream crazyCodes = null;
     ByteStream crazyCopyCodes = null;
     // the first character unit of each character which wrote a crazy code,
     // which says whether that code was written before or after the tertiary
     // weight which lands on top of it
     int[] crazyUnits = null;
     int tertiaryRoom = (TERTIARY_WEIGHTS_PER_CHAR * str.length());
     // the tertiary weight of every unit from tertiaryRoom on, which are the
     // weights written past the room they have.  only a value long enough to
     // write one needs it, so it stays null until one turns up
     ByteStream overrunWeights = null;
     int charOffset = 0;
     // the offset an unprintable weight carries counts the weight entries
     // written rather than the characters they stand for, which is a count of
     // its own: a repeat mark which stands for no character still writes an
     // entry, and the general table writes a four byte weight as two entries
     // although it carries one diacritic weight
     int unprintOffset = 0;
     // what a repeat mark copies: the last weight written, whether it went
     // inline or into the unprintable codes.  A diacritic weight does not
     // count, so "a" with an acute and then a repeat mark copies the "a", and
     // nor does the weight of a character weighed as more than one, which a
     // mark cannot stand for, or the vowel a prolonged sound mark writes
     byte[] lastWeight = null;
     // a repeat mark stands for the character before it in every part of the
     // entry, so it copies that character's crazy flag along with its weight
     byte lastCrazyFlag = 0;
     // and that character's tertiary weight, which is held as the character
     // rather than the weight because only a value which writes past the room
     // the tertiary weights have reads it, and looking it up here would do so
     // for every character of every value
     char lastTertiaryChar = 0;
     boolean hasLastTertiaryChar = false;
     // the weights as ms access holds them, where a weight shorter than a whole
     // entry is padded out with zeroes.  only a value which holds such a weight
     // needs it, so it stays null until one turns up
     ByteStream paddedWeights = null;
     int primaryWidth = getPrimaryUnitWidth();
     for(int i = 0; i < str.length(); ++i) {
 
       char c = str.charAt(i);
 
       // a collation can weigh a sequence of characters as a unit, and such a
       // sequence writes what one or more characters write
       Contraction contraction = getContraction(str, i);
       int numUnits = 1;
       if(contraction != null) {
         numUnits = contraction.getNumUnits();
         i += (contraction.getLength() - 1);
       }
 
       for(int u = 0; u < numUnits; ++u) {
 
         CharHandler ch = ((contraction != null) ? contraction.getHandler(u) :
                           getCharHandler(c));
 
         int curCharOffset = charOffset;
         int curUnprintOffset = unprintOffset;
         // a unit of a sequence stands for no one character, and the handlers
         // a sequence holds read their bytes from the weight table rather than
         // from the char they are given
         byte[] bytes = ch.getInlineBytes((contraction != null) ? 0 : c);
         int numCharUnits = ch.getNumCharUnits();
         int numPrimaryUnits = ch.getNumPrimaryUnits();
         boolean repeatedNothing = false;
         if(ch.getType() == Type.REPEAT) {
           // a repeat mark stands for the character before it, so it writes
           // that character's weight again, and a prolonged sound mark writes
           // the weight of the vowel instead.  with nothing to copy either one
           // writes NO_REPEATED_WEIGHT, which stands for no character: it takes
           // no place in the offsets the diacritic weights carry, it gives no
           // diacritic weight of its own, and a mark after it has nothing to
           // copy either
           repeatedNothing = (lastWeight == null);
           bytes = (repeatedNothing ? NO_REPEATED_WEIGHT :
                    (ch.isProlongedSound() ? prolongedSoundBytes(lastWeight) :
                     lastWeight));
           numCharUnits = (repeatedNothing ? 0 : 1);
           // a mark writes one weight entry either way, so an unprintable
           // weight after it carries one more place even where the mark stands
           // for no character
           numPrimaryUnits = 1;
         }
         if(bytes != null) {
           // write the "inline" codes immediately
           bout.write(bytes);
 
           // only increment the charOffset for chars with inline codes, by
           // the number of characters this one is weighed as.  ms access
           // counts a char weighed as two, such as the sharp s of "ss", twice
           // here, so a later diacritic lands one place on
           charOffset += numCharUnits;
           unprintOffset += numPrimaryUnits;
 
           if(charOffset > tertiaryRoom) {
             if(overrunWeights == null) {
               overrunWeights = new ByteStream();
             }
             // a repeat mark takes the weight of the character it stands
             // for.  a contraction weighs a sequence of characters together
             // and no one character of it carries the weight, so a sequence
             // takes the default
             byte[] tertiary = null;
             if(ch.getType() == Type.REPEAT) {
               tertiary = (hasLastTertiaryChar ?
                           getTertiaryWeights(lastTertiaryChar) : null);
             } else if(contraction == null) {
               tertiary = getTertiaryWeights(c);
             }
             for(int t = Math.max(0, (tertiaryRoom - curCharOffset));
                 t < numCharUnits; ++t) {
               overrunWeights.write(tertiaryWeight(tertiary, t));
             }
           }
 
           int paddedLen = (numPrimaryUnits * primaryWidth);
           if(paddedWeights == null) {
             if(paddedLen > bytes.length) {
               // the first weight which does not fill its entries.  everything
               // before it needed no padding, so bout holds it as ms access
               // does.  it starts at prevLength, since an index on more than
               // one column has the columns before this one in bout as well
               paddedWeights = new ByteStream(bout.getLength() + paddedLen);
               paddedWeights.write(
                   bout.getBytes(), prevLength,
                   (bout.getLength() - prevLength - bytes.length));
             }
           }
           if(paddedWeights != null) {
             paddedWeights.write(bytes);
             paddedWeights.writeFill(
                 Math.max(0, (paddedLen - bytes.length)), (byte)0);
           }
 
           // only a character weighed as one leaves a weight a repeat mark can
           // copy, which also leaves nothing after NO_REPEATED_WEIGHT.  a
           // prolonged sound mark leaves the weight of the kana it lengthens
           // and not the vowel it wrote, so a repeat mark after it copies the
           // kana
           if(!ch.isProlongedSound()) {
             lastWeight = ((numCharUnits == 1) ?
                           repeatableWeight(bytes, numPrimaryUnits) : null);
           }
           if(ch.getType() != Type.REPEAT) {
             // a mark leaves these alone, so a mark after it takes the flag
             // and the tertiary weight of the character it stands for
             lastCrazyFlag = ((numCharUnits == 1) ? ch.getCrazyFlag() : 0);
             lastTertiaryChar = c;
             hasLastTertiaryChar = (contraction == null);
           }
         }
 
         if((ch.getType() == Type.SIMPLE) &&
            (ch.getExtraPlaceholder() == INTERNATIONAL_EXTRA_PLACEHOLDER)) {
           // common case, skip further code handling.  a character which does
           // not take the usual placeholder still has to write its own
           continue;
         }
 
         if(repeatedNothing) {
           // a mark with no weight to repeat gives no secondary weight either
           continue;
         }
 
         bytes = ch.getExtraBytes();
         byte extraCodeModifier = ch.getExtraByteModifier();
         if((bytes == null) && (extraCodeModifier == 0) &&
            (ch.getExtraPlaceholder() != INTERNATIONAL_EXTRA_PLACEHOLDER)) {
           // the placeholder of this character is not the one the gaps are
           // filled with, so it is written where it stands
           bytes = new byte[numCharUnits];
           Arrays.fill(bytes, ch.getExtraPlaceholder());
         }
         if((bytes != null) || (extraCodeModifier != 0)) {
           if(extraCodes == null) {
             extraCodes = new ExtraCodesStream(str.length());
           }
 
           // keep track of the extra codes for later
           writeExtraCodes(curCharOffset, bytes, extraCodeModifier, extraCodes);
         }
 
         bytes = ch.getUnprintableBytes();
         if(bytes != null) {
           if(unprintableCodes == null) {
             unprintableCodes = new ByteStream();
           }
 
           // keep track of the unprintable codes for later
           writeUnprintableCodes(curUnprintOffset, bytes, unprintableCodes);
 
           // a repeat mark after one of these copies it in the shape it takes
           // in the unprintable codes, the midfix and then the code.  an
           // unprintable character takes no crazy code, so a mark standing for
           // one takes none either
           lastWeight = ByteUtil.concat(new byte[]{UNPRINTABLE_MIDFIX}, bytes);
           lastCrazyFlag = 0;
           // an unprintable character writes no tertiary weight of its own,
           // so a mark standing for one has none to copy and takes the
           // default
           hasLastTertiaryChar = false;
         }
 
         // a repeat mark takes the flag of the character it stands for, which
         // the inline block leaves alone and the unprintable one clears, since
         // an unprintable character takes no flag
         byte crazyFlag = ((ch.getType() == Type.REPEAT) ? lastCrazyFlag :
                           ch.getCrazyFlag());
         if(crazyFlag != 0) {
           if(crazyCodes == null) {
             crazyCodes = new ByteStream();
             crazyCopyCodes = new ByteStream();
             crazyUnits = new int[str.length()];
           }
 
           // keep track of the crazy flags for later.  a contraction can write
           // more units than it has characters, so there can be more codes than
           // the value has characters
           int numCrazyCodes = crazyCodes.getLength();
           if(numCrazyCodes == crazyUnits.length) {
             crazyUnits = Arrays.copyOf(crazyUnits, (numCrazyCodes * 2));
           }
           crazyUnits[numCrazyCodes] = curCharOffset;
           crazyCodes.write(crazyFlag);
           byte copyCode = CRAZY_COPY_CODE_CHAR;
           if(ch.isProlongedSound()) {
             // the mark carries its own code even where the vowel it writes is
             // the whole of the kana before it, as it is after the moraic nasal
             copyCode = CRAZY_COPY_CODE_PROLONGED;
           } else if(ch.getType() == Type.REPEAT) {
             copyCode = CRAZY_COPY_CODE_REPEAT;
           }
           crazyCopyCodes.write(copyCode);
         }
       }
     }
 
     // a crazy code which the tertiary overrun wrote is a weight rather than a
     // flag, and ms access trims only a trailing flag, so these codes stay
     // however they come out
     int numOverrunCodes = 0;
     if(overrunWeights != null) {
       numOverrunCodes = writeTertiaryOverrun(crazyCodes, crazyUnits,
                                              overrunWeights, tertiaryRoom);
     }
 
     // write end text flag
     bout.write(END_TEXT);
 
     extraCodes = writeWeightOverrun(bout, paddedWeights, extraCodes,
                                     charOffset, unprintOffset, str.length());
 
     if(isDiacriticsReversed() && (extraCodes != null)) {
       reverseExtraCodes(extraCodes, charOffset);
     }
 
     boolean hasExtraCodes = trimExtraCodes(
         extraCodes, (byte)0, INTERNATIONAL_EXTRA_PLACEHOLDER);
     boolean hasUnprintableCodes = (unprintableCodes != null);
     boolean hasCrazyCodes = (crazyCodes != null);
     if(hasExtraCodes || hasUnprintableCodes || hasCrazyCodes) {
 
       // we write all the international extra bytes first
       if(hasExtraCodes) {
         extraCodes.writeTo(bout);
       }
 
       if(hasCrazyCodes || hasUnprintableCodes) {
 
         // write 2 more end flags
         bout.write(END_TEXT);
         bout.write(END_TEXT);
 
         // next come the crazy flags
         if(hasCrazyCodes) {
 
           writeCrazyCodes(crazyCodes, crazyCopyCodes, numOverrunCodes,
                           bout);
 
           // if we are writing unprintable codes after this, tack on another
           // code
           if(hasUnprintableCodes) {
             bout.write(CRAZY_CODES_UNPRINT_SUFFIX);
           }
         }
 
         // then we write all the unprintable extra bytes
         if(hasUnprintableCodes) {
 
           // write another end flag
           bout.write(END_TEXT);
 
           unprintableCodes.writeTo(bout);
         }
       }
     }
 
     // handle descending order by inverting the bytes
     if(!isAscending) {
 
       // we actually write the end byte before flipping the bytes, and write
       // another one after flipping
       bout.write(END_EXTRA_TEXT);
 
       // flip the bytes that we have written thus far for this text value
       IndexData.flipBytes(bout.getBytes(), prevLength,
                           (bout.getLength() - prevLength));
     }
 
     // write end extra text
     bout.write(END_EXTRA_TEXT);
   }
 
   protected static String toIndexCharSequence(Object value)
       throws IOException {
 
     // first, convert to string
     String str = ColumnImpl.toCharSequence(value).toString();
 
     // all text columns (including memos) are only indexed up to the max
     // number of chars in a VARCHAR column
     int len = str.length();
     if(len > MAX_TEXT_INDEX_CHAR_LENGTH) {
       str = str.substring(0, MAX_TEXT_INDEX_CHAR_LENGTH);
       len = MAX_TEXT_INDEX_CHAR_LENGTH;
     }
 
     // trailing spaces are ignored for text index entries
     if((len > 0) && (str.charAt(len - 1) == ' ')) {
       do {
         --len;
       } while((len > 0) && (str.charAt(len - 1) == ' '));
 
       str = str.substring(0, len);
     }
 
     return str;
   }
 
   /**
    * @return the form a repeat mark writes to stand for a character whose
    *         weight is the given bytes.  A weight of one entry is copied as it
    *         is, and one of more entries is written short, as
    *         LONG_REPEATED_WEIGHT_PREFIX and the first byte of the last entry.
    *         Measured over fourteen cjk ideographs, whose weights are all the
    *         lead entry {@code fdff} and then one which differs
    */
   private static byte[] repeatableWeight(byte[] bytes, int numPrimaryUnits) {
     if(numPrimaryUnits <= 1) {
       return bytes;
     }
     return new byte[]{LONG_REPEATED_WEIGHT_PREFIX, bytes[bytes.length - 2]};
   }
 
   /**
    * Encodes the given extra code info in the given stream.
    */
   private static void writeExtraCodes(
       int charOffset, byte[] bytes, byte extraCodeModifier,
       ExtraCodesStream extraCodes)
   {
     // we fill in a placeholder value for any chars w/out extra codes
     int numChars = extraCodes.getNumChars();
     if(numChars < charOffset) {
       int fillChars = charOffset - numChars;
       extraCodes.writeFill(fillChars, INTERNATIONAL_EXTRA_PLACEHOLDER);
       extraCodes.incrementNumChars(fillChars);
     }
 
     if(bytes != null) {
 
       // write the actual extra codes and move the count on by what was
       // written, since the count is the place the stream has reached rather
       // than a tally of characters.  a character weighed as four which writes
       // one weight leaves the other three places to be filled later, and one
       // weighed as two which writes a weight for each of them fills both
       // itself.  the lone modifier below is the one write which takes a byte
       // without moving the count
       extraCodes.write(bytes);
       extraCodes.incrementNumChars(bytes.length);
 
     } else {
 
       // extra code modifiers modify the existing extra code bytes and do not
       // count as additional extra code chars
       int lastIdx = extraCodes.getLength() - 1;
       if(lastIdx >= 0) {
 
         // the extra code modifier is added to the last extra code written
         byte lastByte = extraCodes.get(lastIdx);
         lastByte += extraCodeModifier;
         extraCodes.set(lastIdx, lastByte);
 
       } else {
 
         // there is no previous extra code, so the modifier is the code.  it
         // takes a byte of the stream without taking a character place, so from
         // here on the stream is one byte longer than the count.  measured: a
         // modifier, a "k" and an a-umlaut give 01 ff 02 13, where the umlaut's
         // weight sits after the modifier and the placeholder for the "k"
         extraCodes.write(extraCodeModifier);
       }
     }
   }
 
   /**
    * Writes the end of the weights over the start of the diacritic weights,
    * which ms access does where the weights run long.
    * <p>
    * Ms access keeps room for three weight entries for each character of the
    * value, so a character of four entries writes two bytes more than its
    * share, and they land on the diacritic weights which follow.  Only U+06D6,
    * U+06D7, U+FD24 and U+FD6F have four entries, and three of them in a row is
    * the shortest value which runs past the room.  What lands in the diacritic
    * weights is the weight of whichever character ends the value, so this is ms
    * access reading past the end of its own weights rather than a rule about
    * those marks, but the entries ms access writes are what jackcess has to
    * match.
    *
    * @return the diacritic weights, which this makes where the value had none
    */
   private static ExtraCodesStream writeWeightOverrun(
       ByteStream bout, ByteStream paddedWeights, ExtraCodesStream extraCodes,
       int charOffset, int numEntries, int numChars)
   {
     // the room is counted over the characters of the value as it is given,
     // which is why a character writing no weight at all still takes its share
     int overrunLen = (2 * (numEntries - (WEIGHT_ENTRIES_PER_CHAR * numChars)));
     if(overrunLen <= 0) {
       return extraCodes;
     }
 
     ExtraCodesStream codes =
       ((extraCodes != null) ? extraCodes : new ExtraCodesStream(numChars));
     // the weights land on places which may carry no diacritic weight yet, so
     // the placeholders they stand on have to be written first
     int fillChars = charOffset - codes.getNumChars();
     if(fillChars > 0) {
       codes.writeFill(fillChars, INTERNATIONAL_EXTRA_PLACEHOLDER);
       codes.incrementNumChars(fillChars);
     }
 
     overrunLen = Math.min(overrunLen, codes.getLength());
     if(overrunLen <= 0) {
       return extraCodes;
     }
 
     // the END_TEXT byte is written by now, and the weights are what comes
     // before it
     byte[] weights = ((paddedWeights != null) ? paddedWeights.getBytes() :
                       bout.getBytes());
     int weightsLen = ((paddedWeights != null) ? paddedWeights.getLength() :
                       (bout.getLength() - 1));
     overrunLen = Math.min(overrunLen, weightsLen);
     int from = (weightsLen - overrunLen);
     for(int i = 0; i < overrunLen; ++i) {
       codes.set(i, weights[from + i]);
     }
     return codes;
   }
 
   /**
    * Whether the extra codes are written from the end of a value rather than
    * the start, which only the french collation does.
    */
   boolean isDiacriticsReversed() {
     return false;
   }
 
   /**
    * Reverses the extra codes, which orders the diacritics of a value from its
    * end.
    * <p>
    * The reversal is over the bytes rather than over per character groups, even
    * though a character can occupy more than one place in the list.  U+01C6
    * writes the two inline weights of d and z and two extra codes with them,
    * and ms access writes {@code 01 14 00} for it in french against
    * {@code 01 02 14 00} in general legacy, which splits the pair.
    */
   private static void reverseExtraCodes(ExtraCodesStream extraCodes,
                                         int numChars)
   {
     // the codes stop at the last char which had one, so the chars after it
     // need their placeholders before there is a list to reverse
     int fillChars = numChars - extraCodes.getNumChars();
     if(fillChars > 0) {
       extraCodes.writeFill(fillChars, INTERNATIONAL_EXTRA_PLACEHOLDER);
       extraCodes.incrementNumChars(fillChars);
     }
 
     byte[] bytes = extraCodes.getBytes();
     for(int i = 0, j = extraCodes.getLength() - 1; i < j; ++i, --j) {
       byte b = bytes[i];
       bytes[i] = bytes[j];
       bytes[j] = b;
     }
   }
 
   /**
    * Trims any bytes in the given range off of the end of the given stream,
    * returning whether or not there are any bytes left in the given stream
    * after trimming.
    */
   private static boolean trimExtraCodes(ByteStream extraCodes,
                                         byte minTrimCode, byte maxTrimCode)
   {
     return trimExtraCodes(extraCodes, minTrimCode, maxTrimCode, 0);
   }
 
   /**
    * Trims as the three argument form does, but never below the given length.
    */
   private static boolean trimExtraCodes(ByteStream extraCodes,
                                         byte minTrimCode, byte maxTrimCode,
                                         int minLength)
   {
     if(extraCodes == null) {
       return false;
     }
 
     extraCodes.trimTrailing(minTrimCode, maxTrimCode, minLength);
 
     // anything left?
     return (extraCodes.getLength() > 0);
   }
 
   /**
    * Encodes the given unprintable char codes in the given stream.
    */
   private static void writeUnprintableCodes(
       int unprintOffset, byte[] bytes, ByteStream unprintableCodes)
   {
     // the offset counts the weight entries written before this character.
     // measured with the hyphen after characters weighed as one, two, three
     // and four: the sharp s, which writes two entries, moves the hyphen from
     // place 2 to place 3
     int offset =
       (UNPRINTABLE_COUNT_START +
        (UNPRINTABLE_COUNT_MULTIPLIER * unprintOffset))
       | UNPRINTABLE_OFFSET_FLAGS;
 
     // write offset as big-endian short
     unprintableCodes.write((offset >> 8) & 0xFF);
     unprintableCodes.write(offset & 0xFF);
 
     unprintableCodes.write(UNPRINTABLE_MIDFIX);
     unprintableCodes.write(bytes);
   }
 
   /**
    * Reads a tertiary weights file, which names only the characters whose
    * weights are not all {@link #DEFAULT_TERTIARY_WEIGHT}.  A line is a code
    * point in hex, a comma, and one digit for each unit of that character:
    *
    * <pre>   00AA,3
    *   0385,10</pre>
    */
   static Map<Character,byte[]> loadTertiaryWeights(String weightsFilePath)
   {
     Map<Character,byte[]> weights = new HashMap<Character,byte[]>();
 
     BufferedReader reader = null;
     try {
 
       reader = new BufferedReader(
           new InputStreamReader(
               DatabaseImpl.getResourceAsStream(weightsFilePath), "US-ASCII"));
 
       String line = null;
       while((line = reader.readLine()) != null) {
         int sep = line.indexOf(',');
         char c = (char)Integer.parseInt(line.substring(0, sep), 16);
         String digits = line.substring(sep + 1);
         byte[] units = new byte[digits.length()];
         for(int i = 0; i < units.length; ++i) {
           units[i] = (byte)(digits.charAt(i) - '0');
         }
         weights.put(c, units);
       }
 
     } catch(IOException e) {
       throw new RuntimeException("failed loading tertiary weights file " +
                                  weightsFilePath, e);
     } finally {
       ByteUtil.closeQuietly(reader);
     }
 
     return weights;
   }
 
   /**
    * @return the tertiary weight of the given unit of a character, where
    *         {@code null} stands for a character every one of whose units
    *         takes the default
    */
   private static byte tertiaryWeight(byte[] weights, int unit) {
     return (((weights != null) && (unit < weights.length)) ? weights[unit] :
             DEFAULT_TERTIARY_WEIGHT);
   }
 
   /**
    * Writes the tertiary weights which went past their room over the crazy
    * codes, as ms access does.
    *
    * Ms access holds the tertiary weights in a run of
    * {@link #TERTIARY_WEIGHTS_PER_CHAR} for each character of the value and
    * the crazy codes in the memory straight after it, so the weight of unit
    * {@code (TERTIARY_WEIGHTS_PER_CHAR * length) + j} lands on the crazy code
    * of the jth character which took one.  Whichever of the two is written
    * last is the one which stays, and a character writes its crazy code before
    * its own tertiary weight, so one which lands on its own code loses it.
    *
    * Only a character of four units can take a value past the room, and only
    * the general table has one.
    */
   private static int writeTertiaryOverrun(ByteStream crazyCodes,
                                           int[] crazyUnits,
                                           ByteStream overrunWeights,
                                           int tertiaryRoom)
   {
     if(crazyCodes == null) {
       return 0;
     }
     int numCodes = Math.min(overrunWeights.getLength(),
                             crazyCodes.getLength());
     int numWritten = 0;
     for(int j = 0; j < numCodes; ++j) {
       if((tertiaryRoom + j) >= crazyUnits[j]) {
         crazyCodes.set(j, overrunWeights.get(j));
         numWritten = (j + 1);
       }
     }
     return numWritten;
   }
 
   /**
    * Encode the given crazy code bytes into the given byte stream.
    */
   private static void writeCrazyCodes(ByteStream crazyCodes,
                                       ByteStream crazyCopyCodes,
                                       int numOverrunCodes,
                                       ByteStream bout)
   {
     // the suffix length depends on how many chars took the crazy path, which
     // is the code count before any trimming
     int numCrazyChars = crazyCodes.getLength();
 
     // CRAZY_CODE_2 flags at the end are ignored, so ditch them
     trimExtraCodes(crazyCodes, CRAZY_CODE_2, CRAZY_CODE_2, numOverrunCodes);
     packCrazyCodes(crazyCodes, bout);
 
     // write crazy code suffix (note, we write this even if all the codes are
     // trimmed)
     writeCrazyCodesSuffix(numCrazyChars, crazyCopyCodes, bout);
   }
 
   /**
    * Packs the given crazy codes into the stream, 2 bits for each code and 3
    * codes to a byte under a common prefix.
    */
   private static void packCrazyCodes(ByteStream crazyCodes, ByteStream bout)
   {
     if(crazyCodes.getLength() == 0) {
       return;
     }
 
     byte curByte = CRAZY_CODE_START;
     int idx = 0;
     for(int i = 0; i < crazyCodes.getLength(); ++i) {
       byte nextByte = crazyCodes.get(i);
       nextByte <<= ((2 - idx) * 2);
       curByte |= nextByte;
 
       ++idx;
       if(idx == 3) {
         // write current byte and reset
         bout.write(curByte);
         curByte = CRAZY_CODE_START;
         idx = 0;
       }
     }
 
     // write last byte
     if(idx > 0) {
       bout.write(curByte);
     }
   }
 
   /**
    * Encode the suffix which follows the crazy codes into the given byte
    * stream.
    */
   private static void writeCrazyCodesSuffix(int numCrazyChars,
                                             ByteStream crazyCopyCodes,
                                             ByteStream bout)
   {
     int numRepeats =
       ((numCrazyChars + (CRAZY_CODES_PER_SUFFIX_REPEAT - 1)) /
        CRAZY_CODES_PER_SUFFIX_REPEAT);
 
     bout.write(CRAZY_CODES_SUFFIX_START);
     // the second run says which of the crazy codes a repeat mark wrote.  a
     // run which names no mark is left out, the same way the flags drop their
     // trailing CRAZY_CODE_2
     trimExtraCodes(crazyCopyCodes, CRAZY_COPY_CODE_CHAR, CRAZY_COPY_CODE_CHAR);
     packCrazyCodes(crazyCopyCodes, bout);
     bout.write(CRAZY_CODES_SUFFIX_MIDFIX);
     writeCrazyCodesSuffixRepeats(numRepeats, bout);
     bout.write(CRAZY_CODES_SUFFIX_SEPARATOR);
     writeCrazyCodesSuffixRepeats(numRepeats, bout);
   }
 
   private static void writeCrazyCodesSuffixRepeats(int numRepeats,
                                                    ByteStream bout)
   {
     for(int i = 0; i < numRepeats; ++i) {
       bout.write(CRAZY_CODES_SUFFIX_REPEAT);
     }
   }
 
   /**
    * Extension of ByteStream which keeps track of how far along the characters
    * of the value the stream has reached.
    */
   private static final class ExtraCodesStream extends ByteStream
   {
     private int _numChars;
 
     private ExtraCodesStream(int length) {
       super(length);
     }
 
     public int getNumChars() {
       return _numChars;
     }
 
     public void incrementNumChars(int inc) {
       _numChars += inc;
     }
   }
 
 }