ICU-6740 The previous svn copy operation used a wrong revision.  I was supposed to use trunk@25425, but I actually specified @25423.  So, picking up the changes up to r25426.

X-SVN-Rev: 25428
diff --git a/src/com/ibm/icu/dev/test/serializable/ExceptionTests.java b/src/com/ibm/icu/dev/test/serializable/ExceptionTests.java
index 662c841..5b60ad0 100644
--- a/src/com/ibm/icu/dev/test/serializable/ExceptionTests.java
+++ b/src/com/ibm/icu/dev/test/serializable/ExceptionTests.java
@@ -1,6 +1,6 @@
 /*
  *******************************************************************************
- * Copyright (C) 1996-2006, International Business Machines Corporation and    *
+ * Copyright (C) 1996-2009, International Business Machines Corporation and    *
  * others. All Rights Reserved.                                                *
  *******************************************************************************
  *
@@ -13,6 +13,7 @@
 import com.ibm.icu.impl.InvalidFormatException;
 import com.ibm.icu.text.ArabicShapingException;
 import com.ibm.icu.text.StringPrepParseException;
+import com.ibm.icu.util.InvalidLocaleException;
 import com.ibm.icu.util.UResourceTypeMismatchException;
 
 /**
@@ -97,6 +98,21 @@
         }
     }
 
+    static class InvalidLocaleExceptionHandler extends ExceptionHandler
+    {
+        public Object[] getTestObjects()
+        {
+            Locale locales[] = SerializableTest.getLocales();
+            InvalidLocaleException exceptions[] = new InvalidLocaleException[locales.length];
+            
+            for (int i = 0; i < locales.length; i += 1) {
+                exceptions[i] = new InvalidLocaleException(locales[i].toString());
+            }
+            
+            return exceptions;
+        }
+    }
+
     public static void main(String[] args)
     {
     }
diff --git a/src/com/ibm/icu/dev/test/serializable/SerializableTest.java b/src/com/ibm/icu/dev/test/serializable/SerializableTest.java
index 1fd2b32..7fd636e 100644
--- a/src/com/ibm/icu/dev/test/serializable/SerializableTest.java
+++ b/src/com/ibm/icu/dev/test/serializable/SerializableTest.java
@@ -17,6 +17,7 @@
 import com.ibm.icu.impl.JavaTimeZone;
 import com.ibm.icu.impl.OlsonTimeZone;
 import com.ibm.icu.impl.TimeZoneAdapter;
+import com.ibm.icu.impl.locale.BaseLocale;
 import com.ibm.icu.math.BigDecimal;
 import com.ibm.icu.math.MathContext;
 import com.ibm.icu.util.AnnualTimeZoneRule;
@@ -634,6 +635,19 @@
         }
     }
 
+    private static class BaseLocaleHandler implements Handler {
+        public Object[] getTestObjects() {
+            BaseLocale baseLoc = BaseLocale.get("en", "Latn", "US", "");
+            return new Object[] {baseLoc};
+        }
+
+        public boolean hasSameBehavior(Object a, Object b) {
+            BaseLocale baseLoc1 = (BaseLocale)a;
+            BaseLocale baseLoc2 = (BaseLocale)b;
+            return (baseLoc1.equals(baseLoc2));
+        }
+    }
+
     private static HashMap map = new HashMap();
     
     static {
@@ -699,6 +713,8 @@
 //#endif
         map.put("com.ibm.icu.impl.duration.BasicDurationFormat", new FormatTests.BasicDurationFormatHandler());
         map.put("com.ibm.icu.impl.RelativeDateFormat", new FormatTests.RelativeDateFormatHandler());
+        map.put("com.ibm.icu.impl.locale.BaseLocale", new BaseLocaleHandler());
+        map.put("com.ibm.icu.util.InvalidLocaleException", new ExceptionTests.InvalidLocaleExceptionHandler());
     }
     
     public SerializableTest()
diff --git a/src/com/ibm/icu/dev/test/util/LocaleBuilderTest.java b/src/com/ibm/icu/dev/test/util/LocaleBuilderTest.java
new file mode 100644
index 0000000..25f0850
--- /dev/null
+++ b/src/com/ibm/icu/dev/test/util/LocaleBuilderTest.java
@@ -0,0 +1,129 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.dev.test.util;
+
+import com.ibm.icu.dev.test.TestFmwk;
+import com.ibm.icu.impl.Utility;
+import com.ibm.icu.util.InvalidLocaleException;
+import com.ibm.icu.util.ULocale;
+import com.ibm.icu.util.ULocale.LocaleBuilder;
+
+/**
+ * Test cases for ULocale.LocaleBuilder
+ */
+public class LocaleBuilderTest extends TestFmwk {
+
+    public static void main(String[] args) throws Exception {
+        new LocaleBuilderTest().run(args);
+    }
+
+    public void TestLocaleBuilder() {
+        // "L": +1 = language
+        // "S": +1 = script
+        // "R": +1 = region
+        // "V": +1 = variant
+        // "K": +1 = locale key / +2 = locale type
+        // "E": +1 = extension letter / +2 = extension value
+        // "P": +1 = private use
+        // "X": indicates an exception must be thrown
+        // "T": +1 = expected language tag
+        String[][] TESTCASE = {
+            {"L", "en", "R", "us", "T", "en-US"},
+            {"L", "en", "R", "FR", "L", "fr", "T", "fr-FR"},
+            {"L", "123", "X"},
+            {"R", "us", "T", "und-US"},
+            {"R", "usa", "X"},
+            {"R", "123", "L", "en", "T", "en-123"},
+            {"S", "LATN", "L", "DE", "T", "de-Latn"},
+            {"S", "latin", "X"},
+//            {"E", "z", "ExtZ", "L", "en", "T", "en-z-extz"},
+            {"E", "z", "ExtZ", "L", "en", "T", "en"},
+//            {"L", "fr", "R", "FR", "P", "Yoshito-ICU", "T", "fr-FR-x-yoshito-icu"},
+            {"L", "fr", "R", "FR", "P", "Yoshito-ICU", "T", "fr-FR"},
+//            {"L", "ja", "R", "jp", "K", "ca", "japanese", "T", "ja-JP-u-ca-japanese"},
+            {"L", "ja", "R", "jp", "K", "ca", "japanese", "T", "ja-JP-x-ldml-k-ca-japanese"},
+//            {"K", "co", "PHONEBK", "K", "ca", "greg", "L", "De", "T", "de-u-ca-greg-co-phonebk"},
+            {"K", "co", "PHONEBK", "K", "ca", "greg", "L", "De", "T", "de-x-ldml-k-ca-greg-k-co-phonebk"},
+        };
+
+        for (int tidx = 0; tidx < TESTCASE.length; tidx++) {
+            LocaleBuilder bld = new LocaleBuilder();
+            int i = 0;
+            String expected = null;
+            while (true) {
+                String method = TESTCASE[tidx][i++];
+                try {
+                    if (method.equals("L")) {
+                        bld.setLanguage(TESTCASE[tidx][i++]);
+                    } else if (method.equals("S")) {
+                        bld.setScript(TESTCASE[tidx][i++]);
+                    } else if (method.equals("R")) {
+                        bld.setRegion(TESTCASE[tidx][i++]);
+                    } else if (method.equals("V")) {
+                        bld.setVariant(TESTCASE[tidx][i++]);
+                    } else if (method.equals("K")) {
+                        String key = TESTCASE[tidx][i++];
+                        String type = TESTCASE[tidx][i++];
+                        bld.setLocaleKeyword(key, type);
+                    } else if (method.equals("E")) {
+                        String key = TESTCASE[tidx][i++];
+                        String value = TESTCASE[tidx][i++];
+                        bld.setExtension(key.charAt(0), value);
+                    } else if (method.equals("P")) {
+                        bld.setPrivateUse(TESTCASE[tidx][i++]);
+                    } else if (method.equals("X")) {
+                        errln("FAIL: No excetion was thrown - test csae: "
+                                + Utility.arrayToString(TESTCASE[tidx]));
+                    } else if (method.equals("T")) {
+                        expected = TESTCASE[tidx][i];
+                        break;
+                    }
+                } catch (InvalidLocaleException e) {
+                    if (TESTCASE[tidx][i].equals("X")) {
+                        // This exception is expected
+                        break;
+                    } else {
+                        errln("FAIL: InvalidLocaleException at offset " + i
+                                + " in test case: " + Utility.arrayToString(TESTCASE[tidx]));
+                    }
+                }
+            }
+            if (expected != null) {
+                ULocale loc = bld.get();
+                String langtag = loc.toLanguageTag();
+                if (!expected.equals(langtag)) {
+                    errln("FAIL: Wrong language tag - " + langtag + 
+                            " for test case: " + Utility.arrayToString(TESTCASE[tidx]));
+                }
+                ULocale loc1 = ULocale.forLanguageTag(langtag);
+                if (!loc.equals(loc1)) {
+                    errln("FAIL: Language tag round trip failed for " + loc);
+                }
+            }
+        }
+    }
+
+    public void TestSetLocale() {
+        ULocale loc = new ULocale("th_TH@calendar=greg");
+        LocaleBuilder bld = new LocaleBuilder();
+        try {
+            bld.setLocale(loc);
+            ULocale loc1 = bld.get();
+            if (!loc.equals(loc1)) {
+                errln("FAIL: Locale loc1 " + loc1 + " was returned by the builder.  Expected " + loc);
+            }
+            bld.setLanguage("").setLocaleKeyword("calendar", "buddhist")
+                .setLanguage("TH").setLocaleKeyword("calendar", "greg");
+            ULocale loc2 = bld.get();
+            if (!loc.equals(loc2)) {
+                errln("FAIL: Locale loc2 " + loc2 + " was returned by the builder.  Expected " + loc);
+            }            
+        } catch (InvalidLocaleException e) {
+            errln("FAIL: InvalidLocaleException: " + e.getMessage());
+        }
+    }
+}
diff --git a/src/com/ibm/icu/dev/test/util/TestAll.java b/src/com/ibm/icu/dev/test/util/TestAll.java
index 122de7e..1b0df4e 100644
--- a/src/com/ibm/icu/dev/test/util/TestAll.java
+++ b/src/com/ibm/icu/dev/test/util/TestAll.java
@@ -1,6 +1,6 @@
 /*
  *******************************************************************************
- * Copyright (C) 1996-2008, International Business Machines Corporation and    *
+ * Copyright (C) 1996-2009, International Business Machines Corporation and    *
  * others. All Rights Reserved.                                                *
  *******************************************************************************
  */
@@ -29,7 +29,8 @@
             "LocaleDataTest",
             "ULocaleTest",
             "LocaleAliasTest",
-            "DebugUtilitiesTest"
+            "DebugUtilitiesTest",
+            "LocaleBuilderTest",
         },
               "Test miscellaneous public utilities");
     }
diff --git a/src/com/ibm/icu/impl/locale/AsciiUtil.java b/src/com/ibm/icu/impl/locale/AsciiUtil.java
new file mode 100644
index 0000000..c97bca9
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/AsciiUtil.java
@@ -0,0 +1,132 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.impl.locale;
+
+public final class AsciiUtil {
+    public static boolean caseIgnoreMatch(String s1, String s2) {
+        if (s1 == s2) {
+            return true;
+        }
+        int len = s1.length();
+        if (len != s2.length()) {
+            return false;
+        }
+        int i = 0;
+        while (i < len) {
+            char c1 = s1.charAt(i);
+            char c2 = s2.charAt(i);
+            if (c1 != c2 && toLower(c1) != toLower(c2)) {
+                break;
+            }
+            i++;
+        }
+        return (i == len);
+    }
+
+    public static int caseIgnoreCompare(String s1, String s2) {
+        if (s1 == s2) {
+            return 0;
+        }
+        return AsciiUtil.toLowerString(s1).compareTo(AsciiUtil.toLowerString(s2));
+    }
+
+
+    public static char toUpper(char c) {
+        if (c >= 'a' && c <= 'z') {
+            c -= 0x20;
+        }
+        return c;
+    }
+
+    public static char toLower(char c) {
+        if (c >= 'A' && c <= 'Z') {
+            c += 0x20;
+        }
+        return c;
+    }
+
+    public static String toLowerString(String s) {
+        int idx = 0;
+        for (; idx < s.length(); idx++) {
+            char c = s.charAt(idx);
+            if (c >= 'A' && c <= 'Z') {
+                break;
+            }
+        }
+        if (idx == s.length()) {
+            return s;
+        }
+        StringBuffer buf = new StringBuffer(s.substring(0, idx));
+        for (; idx < s.length(); idx++) {
+            buf.append(toLower(s.charAt(idx)));
+        }
+        return buf.toString();
+    }
+
+    public static String toUpperString(String s) {
+        int idx = 0;
+        for (; idx < s.length(); idx++) {
+            char c = s.charAt(idx);
+            if (c >= 'a' && c <= 'z') {
+                break;
+            }
+        }
+        if (idx == s.length()) {
+            return s;
+        }
+        StringBuffer buf = new StringBuffer(s.substring(0, idx));
+        for (; idx < s.length(); idx++) {
+            buf.append(toUpper(s.charAt(idx)));
+        }
+        return buf.toString();
+    }
+
+    public static boolean isAlpha(char c) {
+        return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
+    }
+
+    public static boolean isAlphaString(String s) {
+        boolean b = true;
+        for (int i = 0; i < s.length(); i++) {
+            if (!isAlpha(s.charAt(i))) {
+                b = false;
+                break;
+            }
+        }
+        return b;
+    }
+
+    public static boolean isNumeric(char c) {
+        return (c >= '0' && c <= '9');
+    }
+
+    public static boolean isNumericString(String s) {
+        boolean b = true;
+        for (int i = 0; i < s.length(); i++) {
+            if (!isNumeric(s.charAt(i))) {
+                b = false;
+                break;
+            }
+        }
+        return b;
+    }
+
+    public static boolean isAlphaNumeric(char c) {
+        return isAlpha(c) || isNumeric(c);
+    }
+
+    public static boolean isAlphaNumericString(String s) {
+        boolean b = true;
+        for (int i = 0; i < s.length(); i++) {
+            if (!isAlphaNumeric(s.charAt(i))) {
+                b = false;
+                break;
+            }
+        }
+        return b;
+    }
+}
diff --git a/src/com/ibm/icu/impl/locale/BaseLocale.java b/src/com/ibm/icu/impl/locale/BaseLocale.java
new file mode 100644
index 0000000..c794bfa
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/BaseLocale.java
@@ -0,0 +1,287 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+
+package com.ibm.icu.impl.locale;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.Serializable;
+
+
+public final class BaseLocale implements Serializable {
+
+    private static final long serialVersionUID = 1L;
+
+    private String _language = "";
+    private String _script = "";
+    private String _region = "";
+    private String _variant = "";
+
+    private transient String _id = "";
+    private transient String _java6id = "";
+    private transient BaseLocale _parent;
+
+    private static final char SEPCHAR = '_';
+
+    private static LocaleObjectPool/*<BaseLocaleKey,BaseLocale>*/ BASELOCALEPOOL
+        = new LocaleObjectPool/*<BaseLocaleKey,BaseLocale>*/();
+
+    private static final BaseLocale ROOT;
+
+    static {
+        ROOT = new BaseLocale("", "", "", "");
+        BASELOCALEPOOL.registerPermanent(ROOT.createKey(), ROOT);
+    }
+
+    private BaseLocale(String language, String script, String region, String variant) {
+        if (language != null) {
+            _language = language;
+        }
+        if (script != null) {
+            _script = script;
+        }
+        if (region != null) {
+            _region = region;
+        }
+        if (variant != null) {
+            _variant = variant;
+        }
+    }
+
+    public static BaseLocale get(String language, String script, String region, String variant) {
+        BaseLocaleKey key = new BaseLocaleKey(language, script, region, variant);
+        BaseLocale singleton = (BaseLocale)BASELOCALEPOOL.get(key);
+        if (singleton == null) {
+            // Create a canonical BaseLocale instance
+            singleton = new BaseLocale(language, script, region, variant).canonicalize();
+            singleton = (BaseLocale)BASELOCALEPOOL.register(singleton.createKey(), singleton);
+        }
+        return singleton;
+    }
+
+    /*
+     * getPermanent get a singleton instance from BaseLocale pool.  If an instance is not found
+     * in the pool, create a new canonical BaseLocale and put it in the pool.  If an instance
+     * is found and it is not marked as permanent (i.e. such instances could be GCed), the
+     * instance is promoted to the permanent status (therefore, it resides in the pool forever).
+     */
+    public static BaseLocale getPermanent(String language, String script, String region, String variant) {
+        BaseLocaleKey key = new BaseLocaleKey(language, script, region, variant);
+        BaseLocale singleton = (BaseLocale)BASELOCALEPOOL.getPermanent(key);
+        if (singleton == null) {
+            singleton = (BaseLocale)BASELOCALEPOOL.get(key);
+            if (singleton == null) {
+                // Create a canonical BaseLocale instance
+                singleton = new BaseLocale(language, script, region, variant).canonicalize();
+            }
+            singleton = (BaseLocale)BASELOCALEPOOL.registerPermanent(singleton.createKey(), singleton);
+        }
+        return singleton;
+    }
+
+    public boolean equals(Object obj) {
+        return (this == obj) ||
+                ((obj instanceof BaseLocale)
+                        && _id == ((BaseLocale)obj)._id);
+    }
+
+    public int hashCode() {
+        return _id.hashCode();
+    }
+
+    public String getJava6String() {
+        return _java6id;
+    }
+
+    public String getLanguage() {
+        return _language;
+    }
+
+    public String getScript() {
+        return _script;
+    }
+
+    public String getRegion() {
+        return _region;
+    }
+
+    public String getVariant() {
+        return _variant;
+    }
+
+    public BaseLocale getParent() {
+        return _parent;
+    }
+
+    public String toString() {
+        return _id;
+    }
+
+    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
+        stream.defaultReadObject();
+        canonicalize();
+    }
+
+    private BaseLocale canonicalize() {
+
+        StringBuffer id = new StringBuffer();
+
+        int languageLen = _language.length();
+        int scriptLen = _script.length();
+        int regionLen = _region.length();
+        int variantLen = _variant.length();
+
+        if (languageLen > 0) {
+            // language to lower case
+            _language = AsciiUtil.toLowerString(_language).intern();
+
+            id.append(_language);
+        }
+
+        if (scriptLen > 0) {
+            // script - the first letter to upper case, the rest to lower case
+            StringBuffer buf = new StringBuffer();
+            buf.append(AsciiUtil.toUpper(_script.charAt(0)));
+            for (int i = 1; i < _script.length(); i++) {
+                buf.append(AsciiUtil.toLower(_script.charAt(i)));
+            }
+            _script = buf.toString().intern();
+
+            if (languageLen > 0) {
+                id.append(SEPCHAR);
+            }
+            id.append(_script);
+        }
+
+        if (regionLen > 0) {
+            // region to upper case
+            _region = AsciiUtil.toUpperString(_region).intern();
+
+            id.append(SEPCHAR);
+            id.append(_region);
+        }
+
+        if (variantLen > 0) {
+            // variant is case sensitive in JDK
+            _variant = _variant.intern();
+
+            if (regionLen == 0) {
+                id.append(SEPCHAR);
+            }
+            id.append(SEPCHAR);
+            id.append(_variant);
+        }
+
+        _id = id.toString().intern();
+
+        // Compose legacy JDK ID string if required
+        if (scriptLen > 0) {
+            StringBuffer buf = new StringBuffer(_language);
+            if (regionLen > 0) {
+                buf.append(SEPCHAR);
+                buf.append(_region);
+            }
+            if (variantLen > 0) {
+                buf.append(SEPCHAR);
+                buf.append(_variant);
+            }
+            _java6id = buf.toString().intern();
+        } else if (languageLen == 0 && regionLen == 0 && variantLen > 0) {
+            _java6id = "";
+        } else {
+            _java6id = _id;
+        }
+
+        // Resolve parent
+        if (variantLen > 0) {
+            // variant field in Java Locale may contain multiple
+            // subtags
+            int lastSep = _variant.lastIndexOf(SEPCHAR);
+            if (lastSep == -1) {
+                _parent = get(_language, _script, _region, "");
+            } else {
+                _parent = get(_language, _script, _region, _variant.substring(0, lastSep));
+            }
+        } else if (regionLen > 0) {
+            _parent = get(_language, _script, "", "");
+        } else if (scriptLen > 0) {
+            _parent = get(_language, "", "", "");
+        } else if (languageLen > 0) {
+            _parent = ROOT;
+        } else {
+            // This is the root
+            // We should never get here, because ROOT is pre-populated.
+            _parent = null;
+        }
+        return this;
+    }
+
+    private BaseLocaleKey createKey() {
+        return new BaseLocaleKey(_language, _script, _region, _variant);
+    }
+
+    private static class BaseLocaleKey implements Comparable/*<BaseLocaleKey>*/ {
+        private String _lang;
+        private String _scrt;
+        private String _regn;
+        private String _vart;
+        private int _hash; // Default to 0
+
+        public BaseLocaleKey(String language, String script, String region, String variant) {
+            _lang = language;
+            _scrt = script;
+            _regn = region;
+            _vart = variant;
+        }
+
+        public boolean equals(Object obj) {
+            return (this == obj) ||
+                    (obj instanceof BaseLocaleKey)
+                    && AsciiUtil.caseIgnoreMatch(((BaseLocaleKey)obj)._lang, this._lang)
+                    && AsciiUtil.caseIgnoreMatch(((BaseLocaleKey)obj)._scrt, this._scrt)
+                    && AsciiUtil.caseIgnoreMatch(((BaseLocaleKey)obj)._regn, this._regn)
+                    && ((BaseLocaleKey)obj)._vart.equals(_vart); // variant is case sensitive in JDK!
+        }
+
+        //public int compareTo(BaseLocaleKey other) {
+        public int compareTo(Object obj) {
+            BaseLocaleKey other = (BaseLocaleKey)obj;
+            int res = AsciiUtil.caseIgnoreCompare(this._lang, other._lang);
+            if (res == 0) {
+                res = AsciiUtil.caseIgnoreCompare(this._scrt, other._scrt);
+                if (res == 0) {
+                    res = AsciiUtil.caseIgnoreCompare(this._regn, other._regn);
+                    if (res == 0) {
+                        res = AsciiUtil.caseIgnoreCompare(this._vart, other._vart);
+                    }
+                }
+            }
+            return res;
+        }
+
+        public int hashCode() {
+            int h = _hash;
+            if (h == 0) {
+                // Generating a hash value from language, script, region and variant
+                for (int i = 0; i < _lang.length(); i++) {
+                    h = 31*h + AsciiUtil.toLower(_lang.charAt(i));
+                }
+                for (int i = 0; i < _scrt.length(); i++) {
+                    h = 31*h + AsciiUtil.toLower(_scrt.charAt(i));
+                }
+                for (int i = 0; i < _regn.length(); i++) {
+                    h = 31*h + AsciiUtil.toLower(_regn.charAt(i));
+                }
+                for (int i = 0; i < _vart.length(); i++) {
+                    h = 31*h + AsciiUtil.toLower(_vart.charAt(i));
+                }
+                _hash = h;
+            }
+            return h;
+        }
+    }
+}
diff --git a/src/com/ibm/icu/impl/locale/InternalLocaleBuilder.java b/src/com/ibm/icu/impl/locale/InternalLocaleBuilder.java
new file mode 100644
index 0000000..aa39c3f
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/InternalLocaleBuilder.java
@@ -0,0 +1,343 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.impl.locale;
+
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+
+import com.ibm.icu.impl.Utility;
+
+public final class InternalLocaleBuilder {
+
+    private String _language = "";
+    private String _script = "";
+    private String _region = "";
+    private String _variant = "";
+
+    private FieldHandler _handler = FieldHandler.DEFAULT;
+
+    private TreeMap/*<String,String>*/ _extensions;
+    private TreeMap/*<String,String>*/ _keywords;
+    private String _privateuse = "";
+
+    private static final char PRIVUSE = 'x';
+    private static final char LOCALESINGLETON = 'u';
+
+    private static final String LANGTAGSEP = "-";
+    private static final String LOCALESEP = "_";
+
+    public InternalLocaleBuilder() {
+    }
+
+    public InternalLocaleBuilder(FieldHandler handler) {
+        _handler = handler;
+    }
+
+    public String setLanguage(String language) {
+        if (language == null || language.length() == 0) {
+            _language = "";
+        } else {
+            String newval = _handler.process(FieldType.LANGUAGE, language);
+            if (newval == null) {
+                return null;
+            }
+            _language = newval;
+        }
+        return _language;
+    }
+
+    public String setScript(String script) {
+        if (script == null || script.length() == 0) {
+            _script = "";
+        } else {
+            String newval = _handler.process(FieldType.SCRIPT, script);
+            if (newval == null) {
+                return null;
+            }
+            _script = newval;
+        }
+        return _script;
+    }
+
+    public String setRegion(String region) {
+        if (region == null || region.length() == 0) {
+            _region = "";
+        } else {
+            String newval = _handler.process(FieldType.REGION, region);
+            if (newval == null) {
+                return null;
+            }
+            _region = newval;
+        }
+        return _region;
+    }
+
+    public String setVariant(String variant) {
+        if (variant == null || variant.length() == 0) {
+            _variant = "";
+        } else {
+            String newval = _handler.process(FieldType.VARIANT, variant);
+            if (newval == null) {
+                return null;
+            }
+            _variant = newval;
+        }
+        return _variant;
+    }
+
+    public boolean setLocaleKeyword(String key, String type) {
+        if (key == null || key.length() == 0) {
+            throw new IllegalArgumentException("The specified key is null or empty");
+        }
+        if (type == null || type.length() == 0) {
+            if (_keywords != null) {
+                _keywords.remove(key);
+            }
+            return true;
+        }
+
+        key = _handler.process(FieldType.LOCALEKEY, key);
+        type = _handler.process(FieldType.LOCALETYPE, type);
+        if (key == null || type == null) {
+            return false;
+        }
+        if (_keywords == null) {
+            _keywords = new TreeMap/*<String,String>*/();
+        }
+        _keywords.put(key, type);
+
+        return true;
+    }
+
+    public boolean setExtension(char singleton, String value) {
+        if (!AsciiUtil.isAlphaNumeric(singleton)) {
+            throw new IllegalArgumentException("Letter '" + singleton
+                    + "' cannot be used for the singleton extensions.");
+        }
+
+        // singleton char to lower case
+        singleton = AsciiUtil.toLower(singleton);
+
+        if (singleton == PRIVUSE) {
+            throw new IllegalArgumentException("Letter '" + singleton
+                    + "' is reserved for the private use.");
+        }
+
+        //value = value.replaceAll(LANGTAGSEP, LOCALESEP);
+        value = Utility.replaceAll(value, LANGTAGSEP, LOCALESEP);
+
+        if (singleton == LOCALESINGLETON) {
+            // keep locale keywords maintained in _keywords
+            Map/*<String,String>*/ kwds = LocaleExtension.parseKeywordSubtags(value, LOCALESEP);
+            Set/*<Map.Entry<String,String>>*/ entries = kwds.entrySet();
+
+            // check if all key/type pairs are valid, so we can put the set of key/type
+            // pairs atomically.
+            Map/*<String,String>*/ validkwds = new HashMap/*<String,String>*/(kwds.size());
+            Iterator itr = entries.iterator();
+            //for (Map.Entry<String,String> entry : entries) {
+            while (itr.hasNext()) {
+                Map.Entry entry = (Map.Entry)itr.next();
+                String kwkey = _handler.process(FieldType.LOCALEKEY, (String)entry.getKey());
+                String kwtype = _handler.process(FieldType.LOCALETYPE, (String)entry.getValue());
+                if (kwkey == null || kwtype == null) {
+                    return false;
+                }
+                validkwds.put(kwkey, kwtype);
+            }
+            // put the validated key/type pairs in _keywords
+            Set/*<Map.Entry<String,String>>*/ newentries = validkwds.entrySet();
+            Iterator itrn = newentries.iterator();
+            //for (Map.Entry<String,String> newentry : newentries) {
+            while (itrn.hasNext()) {
+                Map.Entry newentry = (Map.Entry)itrn.next();
+                _keywords.put(newentry.getKey(), newentry.getValue());
+            }
+        } else {
+            if (value == null || value.length() == 0) {
+                if (_extensions != null) {
+                    _extensions.remove(String.valueOf(singleton));
+                }
+            } else {
+                value = _handler.process(FieldType.EXTENSION, value);
+                if (value == null) {
+                    return false;
+                }
+                if (_extensions == null) {
+                    _extensions = new TreeMap/*<String,String>*/();
+                }
+                _extensions.put(String.valueOf(singleton).intern(), value);
+            }
+        }
+        return true;
+    }
+
+    public String setPrivateUse(String privuse) {
+        if (privuse == null || privuse.length() == 0) {
+            _privateuse = "";
+        } else {
+            //String newval = _handler.process(FieldType.PRIVATEUSE, privuse.replaceAll(LANGTAGSEP, LOCALESEP));
+            String newval = _handler.process(FieldType.PRIVATEUSE, Utility.replaceAll(privuse, LANGTAGSEP, LOCALESEP));
+            if (newval == null) {
+                return null;
+            }
+            _privateuse = newval;
+        }
+        return _privateuse;
+    }
+
+    public InternalLocaleBuilder removeLocaleExtension() {
+        _keywords = null;
+        _extensions = null;
+        _privateuse = "";
+        return this;
+    }
+
+    public BaseLocale getBaseLocale() {
+        return BaseLocale.get(_language, _script, _region, _variant);
+    }
+
+    public LocaleExtension getLocaleExtension() {
+        TreeMap/*<String,String>*/ map = null;
+        if (_extensions != null || _keywords != null) {
+            // Create a new map
+            map = new TreeMap/*<String,String>*/();
+            if (_extensions != null) {
+                map.putAll(_extensions);
+            }
+            if (_keywords != null) {
+                // Add keywords as an extension
+                StringBuffer buf = new StringBuffer();
+                String lockwd = LocaleExtension.mapToLocaleExtensionString(_keywords, buf);
+                map.put(String.valueOf(LOCALESINGLETON), lockwd);
+            }
+        }
+        return LocaleExtension.get(map, _privateuse);
+    }
+
+//    protected enum FieldType {
+//        LANGUAGE,
+//        SCRIPT,
+//        REGION,
+//        VARIANT,
+//        LOCALEKEY,
+//        LOCALETYPE,
+//        EXTENSION,
+//        PRIVATEUSE
+//    }
+
+    protected static interface FieldType {
+        public static final int LANGUAGE = 0;
+        public static final int SCRIPT = 1;
+        public static final int REGION = 2;
+        public static final int VARIANT = 3;
+        public static final int LOCALEKEY = 4;
+        public static final int LOCALETYPE = 5;
+        public static final int EXTENSION = 6;
+        public static final int PRIVATEUSE = 7;
+    }
+
+    public static class FieldHandler {
+
+        public static final int LANGUAGE = FieldType.LANGUAGE;
+        public static final int SCRIPT = FieldType.SCRIPT;
+        public static final int REGION = FieldType.REGION;
+        public static final int VARIANT = FieldType.VARIANT;
+        public static final int LOCALEKEY = FieldType.LOCALEKEY;
+        public static final int LOCALETYPE = FieldType.LOCALETYPE;
+        public static final int EXTENSION = FieldType.EXTENSION;
+        public static final int PRIVATEUSE = FieldType.PRIVATEUSE;
+
+        public static FieldHandler DEFAULT = new FieldHandler();
+
+        protected FieldHandler() {
+        }
+
+        //public String process(FieldType type, String value) {
+        public String process(int type, String value) {
+            value = map(type, value);
+            if (!validate(type, value)) {
+                return null;
+            }
+            return value.intern();
+        }
+
+        //protected String map(FieldType type, String value) {
+        protected String map(int type, String value) {
+            switch (type) {
+            case LANGUAGE:
+                value = LanguageCode.getShortest(AsciiUtil.toLowerString(value));
+                break;
+            case SCRIPT:
+                //TODO
+                break;
+            case REGION:
+                value = AsciiUtil.toLowerString(value);
+                break;
+            case VARIANT:
+                // Java variant is case sensitive
+                break;
+            case LOCALEKEY:
+            case LOCALETYPE:
+            case EXTENSION:
+            case PRIVATEUSE:
+                value = AsciiUtil.toLowerString(value);
+                break;
+            }
+            return value;
+        }
+
+        //protected boolean validate(FieldType type, String value) {
+        protected boolean validate(int type, String value) {
+            boolean isValid = false;
+            String[] subtags;
+
+            switch (type) {
+            case LANGUAGE:
+                isValid = LanguageTag.isLanguageSubtag(value);
+                break;
+            case SCRIPT:
+                isValid = LanguageTag.isScriptSubtag(value);
+                break;
+            case REGION:
+                isValid = LanguageTag.isRegionSubtag(value);
+                break;
+            case VARIANT:
+                isValid = LanguageTag.isVariantSubtag(value);
+                break;
+            case LOCALEKEY:
+                isValid = LanguageTag.isExtensionSubtag(value);
+                break;
+            case LOCALETYPE:
+                isValid = LanguageTag.isExtensionSubtag(value);
+                break;
+            case EXTENSION:
+                //subtags = value.split(LOCALESEP);
+                subtags = Utility.split(value, LOCALESEP.charAt(0));
+                //for (String subtag : subtags) {
+                for (int i = 0; i < subtags.length; i++) {
+                    String subtag = subtags[i];
+                    isValid = LanguageTag.isExtensionSubtag(subtag);
+                }
+                break;
+            case PRIVATEUSE:
+                //subtags = value.split(LOCALESEP);
+                subtags = Utility.split(value, LOCALESEP.charAt(0));
+                //for (String subtag : subtags) {
+                for (int i = 0; i < subtags.length; i++) {
+                    String subtag = subtags[i];
+                    isValid = LanguageTag.isPrivateuseValueSubtag(subtag);
+                }
+                break;
+            }
+            return isValid;
+        }
+    }
+}
diff --git a/src/com/ibm/icu/impl/locale/LanguageCode.java b/src/com/ibm/icu/impl/locale/LanguageCode.java
new file mode 100644
index 0000000..2fca91b
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/LanguageCode.java
@@ -0,0 +1,221 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.impl.locale;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class LanguageCode {
+
+    private static final Map/*<String,String>*/ THREE_TO_TWO;
+
+    static {
+        THREE_TO_TWO = new HashMap/*<String,String>*/();
+
+        String[] alpha3to2 = {
+            "aar", "aa",    // Afar
+            "abk", "ab",    // Abkhazian
+            "afr", "af",    // Afrikaans
+            "aka", "ak",    // Akan
+            "amh", "am",    // Amharic
+            "ara", "ar",    // Arabic
+            "arg", "an",    // Aragonese
+            "asm", "as",    // Assamese
+            "ava", "av",    // Avaric
+            "ave", "ae",    // Avestan
+            "aym", "ay",    // Aymara
+            "aze", "az",    // Azerbaijani
+            "bak", "ba",    // Bashkir
+            "bam", "bm",    // Bambara
+            "bel", "be",    // Belarusian
+            "ben", "bn",    // Bengali
+            "bih", "bh",    // Bihari
+            "bis", "bi",    // Bislama
+            "bod", "bo",    // Tibetan
+            "bos", "bs",    // Bosnian
+            "bre", "br",    // Breton
+            "bul", "bg",    // Bulgarian
+            "cat", "ca",    // Catalan; Valencian
+            "ces", "cs",    // Czech
+            "cha", "ch",    // Chamorro
+            "che", "ce",    // Chechen
+            "chu", "cu",    // Church Slavic; Old Slavonic; Church Slavonic; Old Bulgarian; Old Church Slavonic
+            "chv", "cv",    // Chuvash
+            "cor", "kw",    // Cornish
+            "cos", "co",    // Corsican
+            "cre", "cr",    // Cree
+            "cym", "cy",    // Welsh
+            "dan", "da",    // Danish
+            "deu", "de",    // German
+            "div", "dv",    // Divehi; Dhivehi; Maldivian
+            "dzo", "dz",    // Dzongkha
+            "ell", "el",    // Greek, Modern (1453-)
+            "eng", "en",    // English
+            "epo", "eo",    // Esperanto
+            "est", "et",    // Estonian
+            "eus", "eu",    // Basque
+            "ewe", "ee",    // Ewe
+            "fao", "fo",    // Faroese
+            "fas", "fa",    // Persian
+            "fij", "fj",    // Fijian
+            "fin", "fi",    // Finnish
+            "fra", "fr",    // French
+            "fry", "fy",    // Western Frisian
+            "ful", "ff",    // Fulah
+            "gla", "gd",    // Gaelic; Scottish Gaelic
+            "gle", "ga",    // Irish
+            "glg", "gl",    // Galician
+            "glv", "gv",    // Manx
+            "grn", "gn",    // Guarani
+            "guj", "gu",    // Gujarati
+            "hat", "ht",    // Haitian; Haitian Creole
+            "hau", "ha",    // Hausa
+            "heb", "he",    // Hebrew
+            "her", "hz",    // Herero
+            "hin", "hi",    // Hindi
+            "hmo", "ho",    // Hiri Motu
+            "hrv", "hr",    // Croatian
+            "hun", "hu",    // Hungarian
+            "hye", "hy",    // Armenian
+            "ibo", "ig",    // Igbo
+            "ido", "io",    // Ido
+            "iii", "ii",    // Sichuan Yi; Nuosu
+            "iku", "iu",    // Inuktitut
+            "ile", "ie",    // Interlingue; Occidental
+            "ina", "ia",    // Interlingua (International Auxiliary Language Association)
+            "ind", "id",    // Indonesian
+            "ipk", "ik",    // Inupiaq
+            "isl", "is",    // Icelandic
+            "ita", "it",    // Italian
+            "jav", "jv",    // Javanese
+            "jpn", "ja",    // Japanese
+            "kal", "kl",    // Kalaallisut; Greenlandic
+            "kan", "kn",    // Kannada
+            "kas", "ks",    // Kashmiri
+            "kat", "ka",    // Georgian
+            "kau", "kr",    // Kanuri
+            "kaz", "kk",    // Kazakh
+            "khm", "km",    // Central Khmer
+            "kik", "ki",    // Kikuyu; Gikuyu
+            "kin", "rw",    // Kinyarwanda
+            "kir", "ky",    // Kirghiz; Kyrgyz
+            "kom", "kv",    // Komi
+            "kon", "kg",    // Kongo
+            "kor", "ko",    // Korean
+            "kua", "kj",    // Kuanyama; Kwanyama
+            "kur", "ku",    // Kurdish
+            "lao", "lo",    // Lao
+            "lat", "la",    // Latin
+            "lav", "lv",    // Latvian
+            "lim", "li",    // Limburgan; Limburger; Limburgish
+            "lin", "ln",    // Lingala
+            "lit", "lt",    // Lithuanian
+            "ltz", "lb",    // Luxembourgish; Letzeburgesch
+            "lub", "lu",    // Luba-Katanga
+            "lug", "lg",    // Ganda
+            "mah", "mh",    // Marshallese
+            "mal", "ml",    // Malayalam
+            "mar", "mr",    // Marathi
+            "mkd", "mk",    // Macedonian
+            "mlg", "mg",    // Malagasy
+            "mlt", "mt",    // Maltese
+            "mon", "mn",    // Mongolian
+            "mri", "mi",    // Maori
+            "msa", "ms",    // Malay
+            "mya", "my",    // Burmese
+            "nau", "na",    // Nauru
+            "nav", "nv",    // Navajo; Navaho
+            "nbl", "nr",    // Ndebele, South; South Ndebele
+            "nde", "nd",    // Ndebele, North; North Ndebele
+            "ndo", "ng",    // Ndonga
+            "nep", "ne",    // Nepali
+            "nld", "nl",    // Dutch; Flemish
+            "nno", "nn",    // Norwegian Nynorsk; Nynorsk, Norwegian
+            "nob", "nb",    // Bokmal, Norwegian; Norwegian Bokmal
+            "nor", "no",    // Norwegian
+            "nya", "ny",    // Chichewa; Chewa; Nyanja
+            "oci", "oc",    // Occitan (post 1500); Provencal
+            "oji", "oj",    // Ojibwa
+            "ori", "or",    // Oriya
+            "orm", "om",    // Oromo
+            "oss", "os",    // Ossetian; Ossetic
+            "pan", "pa",    // Panjabi; Punjabi
+            "pli", "pi",    // Pali
+            "pol", "pl",    // Polish
+            "por", "pt",    // Portuguese
+            "pus", "ps",    // Pushto; Pashto
+            "que", "qu",    // Quechua
+            "roh", "rm",    // Romansh
+            "ron", "ro",    // Romanian; Moldavian; Moldovan
+            "run", "rn",    // Rundi
+            "rus", "ru",    // Russian
+            "sag", "sg",    // Sango
+            "san", "sa",    // Sanskrit
+            "sin", "si",    // Sinhala; Sinhalese
+            "slk", "sk",    // Slovak
+            "slv", "sl",    // Slovenian
+            "sme", "se",    // Northern Sami
+            "smo", "sm",    // Samoan
+            "sna", "sn",    // Shona
+            "snd", "sd",    // Sindhi
+            "som", "so",    // Somali
+            "sot", "st",    // Sotho, Southern
+            "spa", "es",    // Spanish; Castilian
+            "sqi", "sq",    // Albanian
+            "srd", "sc",    // Sardinian
+            "srp", "sr",    // Serbian
+            "ssw", "ss",    // Swati
+            "sun", "su",    // Sundanese
+            "swa", "sw",    // Swahili
+            "swe", "sv",    // Swedish
+            "tah", "ty",    // Tahitian
+            "tam", "ta",    // Tamil
+            "tat", "tt",    // Tatar
+            "tel", "te",    // Telugu
+            "tgk", "tg",    // Tajik
+            "tgl", "tl",    // Tagalog
+            "tha", "th",    // Thai
+            "tir", "ti",    // Tigrinya
+            "ton", "to",    // Tonga (Tonga Islands)
+            "tsn", "tn",    // Tswana
+            "tso", "ts",    // Tsonga
+            "tuk", "tk",    // Turkmen
+            "tur", "tr",    // Turkish
+            "twi", "tw",    // Twi
+            "uig", "ug",    // Uighur; Uyghur
+            "ukr", "uk",    // Ukrainian
+            "urd", "ur",    // Urdu
+            "uzb", "uz",    // Uzbek
+            "ven", "ve",    // Venda
+            "vie", "vi",    // Vietnamese
+            "vol", "vo",    // Volapuk
+            "wln", "wa",    // Walloon
+            "wol", "wo",    // Wolof
+            "xho", "xh",    // Xhosa
+            "yid", "yi",    // Yiddish
+            "yor", "yo",    // Yoruba
+            "zha", "za",    // Zhuang; Chuang
+            "zho", "zh",    // Chinese
+            "zul", "zu",    // Zulu
+        };
+        int i = 0;
+        while (i < alpha3to2.length) {
+            THREE_TO_TWO.put(alpha3to2[i], alpha3to2[i+1]);
+            i += 2;
+        }
+    }
+
+    public static String getShortest(String code) {
+        if (code.length() == 3) {
+            String code3 = AsciiUtil.toLowerString(code);
+            String code2 = (String)THREE_TO_TWO.get(code3);
+            if (code2 != null)
+                return code2;
+        }
+        return code;
+    }
+}
diff --git a/src/com/ibm/icu/impl/locale/LanguageTag.java b/src/com/ibm/icu/impl/locale/LanguageTag.java
new file mode 100644
index 0000000..30e3308
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/LanguageTag.java
@@ -0,0 +1,395 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.impl.locale;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+
+import com.ibm.icu.impl.Utility;
+import com.ibm.icu.util.InvalidLocaleException;
+
+public final class LanguageTag {
+
+    private String _languageTag;        // entire language tag
+    private String _grandfathered;      // grandfathered tag
+    private String _privateuse;         // privateuse, not including leading "x-"
+    private String _language;           // language subtag
+    private String[] _extlang;          // array of extlang subtags
+    private String _script;             // script subtag
+    private String _region;             // region subtag
+    private String _variant;            // variant subtags in a single string
+    private List/*<Extension>*/ _extension; // extension key/value pairs
+
+    private static final int MINLEN = 2; // minimum length of a valid language tag
+
+    private static final String SEP = "-";
+    private static final String PRIVATEUSE = "x";
+
+    // Map contains grandfathered tags and its preferred mappings from
+    // http://www.ietf.org/internet-drafts/draft-ietf-ltru-4645bis-09.txt
+//    private static final ConcurrentHashMap<String,String> GRANDFATHERED = 
+//        new ConcurrentHashMap<String,String>();
+
+    private static final Map GRANDFATHERED = new HashMap();
+
+    static {
+        final String[][] entries = {
+          //{"tag",         "preferred"},
+            {"art-lojban",  "jbo"},
+            {"cel-gaulish", ""},
+            {"en-GB-oed",   ""},
+            {"i-ami",       "ami"},
+            {"i-bnn",       "bnn"},
+            {"i-default",   ""},
+            {"i-enochian",  ""},
+            {"i-hak",       "hak"},
+            {"i-klingon",   "tlh"},
+            {"i-lux",       "lb"},
+            {"i-mingo",     ""},
+            {"i-navajo",    "nv"},
+            {"i-pwn",       "pwn"},
+            {"i-tao",       "tao"},
+            {"i-tay",       "tay"},
+            {"i-tsu",       "tsu"},
+            {"no-bok",      "nb"},
+            {"no-nyn",      "nn"},
+            {"sgn-BE-FR",   "sfb"},
+            {"sgn-BE-NL",   "vgt"},
+            {"sgn-CH-DE",   "sgg"},
+            {"zh-guoyu",    "cmn"},
+            {"zh-hakka",    "hak"},
+            {"zh-min",      ""},
+            {"zh-min-nan",  "nan"},
+            {"zh-xiang",    "hsn"},
+        };
+        //for (String[] e : entries) {
+        for (int i = 0; i < entries.length; i++) {
+            String[] e = entries[i];
+            GRANDFATHERED.put(e[0], e[1]);
+        }
+    }
+
+    private LanguageTag(String tag) {
+        _languageTag = tag;
+    }
+
+    // Bit flags used by the language tag parser
+    private static final int LANG = 0x0001;
+    private static final int EXTL = 0x0002;
+    private static final int SCRT = 0x0004;
+    private static final int REGN = 0x0008;
+    private static final int VART = 0x0010;
+    private static final int EXTS = 0x0020;
+    private static final int EXTV = 0x0040;
+    private static final int PRIV = 0x0080;
+
+    public static LanguageTag parse(String tag) throws InvalidLocaleException {
+        if (tag.length() < MINLEN) {
+            throw new InvalidLocaleException("The specified tag '"
+                    + tag + "' is too short");
+        }
+
+        if (tag.endsWith(SEP)) {
+            // This code utilizes Stirng#split, which drops off the last empty segment.
+            // We need to check if the tag ends with '-' here.
+            throw new InvalidLocaleException("The specified tag '"
+                    + tag + "' ends with " + SEP);
+        }
+
+        LanguageTag t = new LanguageTag(tag);
+
+        // Check if the tag is grandfathered
+        if (GRANDFATHERED.containsKey(tag)) {
+            t._grandfathered = tag;
+            // Preferred mapping
+            String preferred = (String)GRANDFATHERED.get(tag);
+            if (preferred.length() > 0) {
+                t._language = preferred;
+            }
+            return t;
+        }
+
+        // langtag       = language
+        //                 ["-" script]
+        //                 ["-" region]
+        //                 *("-" variant)
+        //                 *("-" extension)
+        //                 ["-" privateuse]
+
+        //String[] subtags = tag.split(SEP);
+        String[] subtags = Utility.split(tag, SEP.charAt(0));
+        int idx = 0;
+        int extlangIdx = 0;
+        StringBuffer varBuf = null;
+        String extSingleton = null;
+        StringBuffer extBuf = null;
+        int next = LANG | PRIV;
+        while (true) {
+            if (idx >= subtags.length) {
+                break;
+            }
+            if ((next & LANG) != 0) {
+                if (isLanguageSubtag(subtags[idx])) {
+                    t._language = subtags[idx++];
+                    next = EXTL | SCRT | REGN | VART | EXTS | PRIV;
+                    continue;
+                }
+            }
+            if ((next & EXTL) != 0) {
+                if (isExtlangSubtag(subtags[idx])) {
+                    if (extlangIdx == 0) {
+                        t._extlang = new String[3];
+                    }
+                    t._extlang[extlangIdx++] = subtags[idx++];
+                    if (extlangIdx < 3) {
+                        next = EXTL | SCRT | REGN | VART | EXTS | PRIV;
+                    } else {
+                        next = SCRT | REGN | VART | EXTS | PRIV;
+                    }
+                    continue;
+                }
+            }
+            if ((next & SCRT) != 0) {
+                if (isScriptSubtag(subtags[idx])) {
+                    t._script = subtags[idx++];
+                    next = REGN | VART | EXTS | PRIV;
+                    continue;
+                }
+            }
+            if ((next & REGN) != 0) {
+                if (isRegionSubtag(subtags[idx])) {
+                    t._region = subtags[idx++];
+                    next = VART | EXTS | PRIV;
+                    continue;
+                }
+            }
+            if ((next & VART) != 0) {
+                if (isVariantSubtag(subtags[idx])) {
+                    if (varBuf == null) {
+                        varBuf = new StringBuffer(subtags[idx++]);
+                    } else {
+                        varBuf.append(SEP);
+                        varBuf.append(subtags[idx++]);
+                    }
+                    next = VART | EXTS | PRIV;
+                    continue;
+                }
+            }
+            if ((next & EXTS) != 0) {
+                if (isExtensionSingleton(subtags[idx])) {
+                    if (extSingleton != null) {
+                        if (extBuf == null) {
+                            throw new InvalidLocaleException("The specified tag '"
+                                    + tag + "' contains an incomplete extension: "
+                                    + extSingleton);
+                        }
+                        // Emit the previous extension key/value pair
+                        if (t._extension == null) {
+                            t._extension = new LinkedList/*<Extension>*/();
+                        }
+                        Extension e = new Extension(extSingleton, extBuf.toString());
+                        t._extension.add(e);
+                    }
+                    extSingleton = subtags[idx++];
+                    extBuf = null; // Clear the extension value buffer
+                    next = EXTV;
+                    continue;
+                }
+            }
+            if ((next & EXTV) != 0) {
+                if (isExtensionSubtag(subtags[idx])) {
+                    if (extBuf == null) {
+                        extBuf = new StringBuffer(subtags[idx++]);
+                    } else {
+                        extBuf.append(SEP);
+                        extBuf.append(subtags[idx++]);
+                    }
+                    next = EXTS | EXTV | PRIV;
+                    continue;
+                }
+            }
+            if ((next & PRIV) != 0) {
+                if (AsciiUtil.caseIgnoreMatch(PRIVATEUSE, subtags[idx])) {
+                    // The rest of part will be private use value subtags
+                    StringBuffer puBuf = new StringBuffer();
+                    idx++;
+                    for (boolean bFirst = true ; idx < subtags.length; idx++) {
+                        if (!isPrivateuseValueSubtag(subtags[idx])) {
+                            throw new InvalidLocaleException("The specified tag '"
+                                    + tag + "' contains an illegal private use subtag: "
+                                    + (subtags[idx].length() == 0 ? "<empty>" : subtags[idx]));
+                        }
+                        if (bFirst) {
+                            bFirst = false;
+                        } else {
+                            puBuf.append(SEP);
+                        }
+                        puBuf.append(subtags[idx]);
+                    }
+                    t._privateuse = puBuf.toString();
+                    if (t._privateuse.length() == 0) {
+                        // Empty privateuse value
+                        throw new InvalidLocaleException("The specified tag '"
+                                + tag + "' contains an empty private use subtag");
+                    }
+                    break;
+                }
+            }
+            // If we fell through here, it means this subtag is illegal
+            throw new InvalidLocaleException("The specified tag '" + tag
+                    + "' contains an illegal subtag: "
+                    + (subtags[idx].length() == 0 ? "<empty>" : subtags[idx]));
+        }
+
+        if (varBuf != null) {
+            t._variant = varBuf.toString();
+        }
+
+        if (extSingleton != null) {
+            if (extBuf == null) {
+                // extension singleton without following extension value
+                throw new InvalidLocaleException("The specified tag '"
+                        + tag + "' contains an incomplete extension: "
+                        + extSingleton);
+            }
+            // Emit the last extension key/value pair
+            if (t._extension == null) {
+                t._extension = new LinkedList/*<Extension>*/();
+            }
+            Extension e = new Extension(extSingleton, extBuf.toString());
+            t._extension.add(e);
+        }
+
+        return t;
+    }
+
+    public String getTag() {
+        return _languageTag;
+    }
+
+    public String getLanguage() {
+        return _language;
+    }
+
+    public String getExtlang(int idx) {
+        if (_extlang != null && idx < _extlang.length) {
+            return _extlang[idx];
+        }
+        return null;
+    }
+
+    public String getScript() {
+        return _script;
+    }
+
+    public String getRegion() {
+        return _region;
+    }
+
+    public String getVariant() {
+        return _variant;
+    }
+
+    public List/*<Extension>*/ getExtensions() {
+        if (_extension != null) {
+            return Collections.unmodifiableList(_extension);
+        }
+        return null;
+    }
+
+    public String getPrivateUse() {
+        return _privateuse;
+    }
+
+    public String getGrandfathered() {
+        return _grandfathered;
+    }
+
+    public static boolean isLanguageSubtag(String s) {
+        // language      = 2*3ALPHA            ; shortest ISO 639 code
+        //                 ["-" extlang]       ; sometimes followed by
+        //                                     ;   extended language subtags
+        //               / 4ALPHA              ; or reserved for future use
+        //               / 5*8ALPHA            ; or registered language subtag
+        return (s.length() >= 2) && (s.length() <= 8) && AsciiUtil.isAlphaString(s);
+    }
+
+    public static boolean isExtlangSubtag(String s) {
+        // extlang       = 3ALPHA              ; selected ISO 639 codes
+        //                 *2("-" 3ALPHA)      ; permanently reserved
+        return (s.length() == 3) && AsciiUtil.isAlphaString(s);
+    }
+
+    public static boolean isScriptSubtag(String s) {
+        // script        = 4ALPHA              ; ISO 15924 code
+        return (s.length() == 4) && AsciiUtil.isAlphaString(s);
+    }
+
+    public static boolean isRegionSubtag(String s) {
+        // region        = 2ALPHA              ; ISO 3166-1 code
+        //               / 3DIGIT              ; UN M.49 code
+        return ((s.length() == 2) && AsciiUtil.isAlphaString(s))
+                || ((s.length() == 3) && AsciiUtil.isNumericString(s));
+    }
+
+    public static boolean isVariantSubtag(String s) {
+        // variant       = 5*8alphanum         ; registered variants
+        //               / (DIGIT 3alphanum)
+        int len = s.length();
+        if (len >= 5 && len <= 8) {
+            return AsciiUtil.isAlphaNumericString(s);
+        }
+        if (len == 4) {
+            return AsciiUtil.isNumeric(s.charAt(0))
+                    && AsciiUtil.isAlpha(s.charAt(1))
+                    && AsciiUtil.isAlpha(s.charAt(2))
+                    && AsciiUtil.isAlpha(s.charAt(3));
+        }
+        return false;
+    }
+
+    public static boolean isExtensionSingleton(String s) {
+        // extension     = singleton 1*("-" (2*8alphanum))
+        return (s.length() == 1)
+                && AsciiUtil.isAlphaString(s)
+                && !AsciiUtil.caseIgnoreMatch(PRIVATEUSE, s);
+    }
+
+    public static boolean isExtensionSubtag(String s) {
+        // extension     = singleton 1*("-" (2*8alphanum))
+        return (s.length() >= 2) && (s.length() <= 8) && AsciiUtil.isAlphaNumericString(s);
+    }
+
+    public static boolean isPrivateuseValueSubtag(String s) {
+        // privateuse    = "x" 1*("-" (1*8alphanum))
+        return (s.length() >= 1) && (s.length() <= 8) && AsciiUtil.isAlphaNumericString(s);
+    }
+
+    /*
+     * Language tag extension key/value container
+     */
+    public static class Extension {
+        private String _singleton;
+        private String _value;
+
+        public Extension(String singleton, String value) {
+            _singleton = singleton;
+            _value = value;
+        }
+
+        public String getSingleton() {
+            return _singleton;
+        }
+
+        public String getValue() {
+            return _value;
+        }
+    }
+}
diff --git a/src/com/ibm/icu/impl/locale/LocaleExtension.java b/src/com/ibm/icu/impl/locale/LocaleExtension.java
new file mode 100644
index 0000000..7b232fd
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/LocaleExtension.java
@@ -0,0 +1,348 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.impl.locale;
+
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+
+import com.ibm.icu.impl.Utility;
+import com.ibm.icu.util.InvalidLocaleException;
+
+public final class LocaleExtension {
+
+    private String _canonical;
+
+    private transient TreeMap/*<String,String>*/ _extensions;
+    private transient String _privuse;
+    private transient TreeMap/*<String,String>*/ _keywords;
+
+    private static final LocaleObjectPool/*<String,LocaleExtension>*/ EXTENSIONPOOL =
+        new LocaleObjectPool/*<String,LocaleExtension>*/();
+
+    public static final LocaleExtension EMPTY_EXTENSION = new LocaleExtension("");
+
+    private static final String LOCALESEP = "_";
+    private static final String LOCALESINGLETON = "u";
+    private static final String PRIVUSE = "x";
+
+    private static final int MINLEN = 3; // minium length of string representation "x_?"
+
+    private LocaleExtension(String canonical) {
+        _canonical = canonical;
+    }
+
+    public static LocaleExtension get(String extstr) throws InvalidLocaleException {
+        if (extstr == null || extstr.length() == 0) {
+            return EMPTY_EXTENSION;
+        }
+        // Convert to lower case
+        extstr = AsciiUtil.toLowerString(extstr);
+        LocaleExtension singleton = (LocaleExtension)EXTENSIONPOOL.get(extstr);
+        if (singleton == null) {
+            LocaleExtension locext = getCanonical(extstr);
+            // Try to get from the pool with the canonicalized string
+            singleton = (LocaleExtension)EXTENSIONPOOL.get(locext.toString());
+            if (singleton == null) {
+                singleton = (LocaleExtension)EXTENSIONPOOL.register(locext.toString(), locext);
+            }
+        }
+        return singleton;
+    }
+
+    /*
+     * This method is package local and used by LocaleBuilder.
+     * LocaleBuilder stores singleton extensions including locale
+     * keywords in a Map structure, so we do not need to parse plain
+     * extension string again.
+     */
+    static LocaleExtension get(TreeMap/*<String,String>*/ extensions, String privuse) {
+        boolean hasExtensions = (extensions != null && extensions.size() > 0);
+        boolean hasPrivuse = (privuse != null && privuse.length() > 0);
+
+        if (!hasExtensions && !hasPrivuse) {
+            return EMPTY_EXTENSION;
+        }
+
+        StringBuffer buf = new StringBuffer();
+        if (hasExtensions) {
+            mapToLocaleExtensionString(extensions, buf);
+        }
+        if (hasPrivuse) {
+            // prepend x_
+            privuse = PRIVUSE + LOCALESEP + privuse;
+            if (buf.length() > 0) {
+                buf.append(LOCALESEP);
+            }
+            buf.append(privuse);
+        }
+        String extstr = buf.toString();
+
+        // Check if the same LocaleExtension is available in the pool
+        LocaleExtension singleton = (LocaleExtension)EXTENSIONPOOL.get(extstr);
+        if (singleton == null) {
+            // create a new one
+            singleton = new LocaleExtension(extstr.intern());
+            singleton._extensions = extensions;
+            singleton._privuse = privuse;
+            if (singleton._extensions != null) {
+                String kwdstr = (String)singleton._extensions.get(LOCALESINGLETON);
+                if (kwdstr != null) {
+                    singleton._keywords = parseKeywordSubtags(kwdstr, LOCALESEP);
+                }
+            }
+            singleton = (LocaleExtension)EXTENSIONPOOL.register(singleton._canonical, singleton);
+        }
+
+        return singleton;
+    }
+
+    private static LocaleExtension getCanonical(String extstr) throws InvalidLocaleException {
+        if (extstr == null || extstr.length() == 0) {
+            return EMPTY_EXTENSION;
+        }
+        if (extstr.length() < MINLEN) {
+            throw new InvalidLocaleException("Locale extension string '" + extstr + "' is too short.");
+        }
+        extstr = AsciiUtil.toLowerString(extstr);
+
+        TreeMap/*<String,String>*/ extensions = null;
+        TreeMap/*<String,String>*/ keywords = null;
+        String ext = null;  // extensions part
+        String prv = null;  // private use part
+
+        if (extstr.charAt(0) == PRIVUSE.charAt(0)) {
+            if (extstr.charAt(1) == LOCALESEP.charAt(0)) {
+                prv = extstr.substring(2).intern();
+            } else {
+                throw new InvalidLocaleException("Locale extension string '" + extstr
+                        + "' must start with a singleton segment.");
+            }
+        } else {
+            int idx = extstr.indexOf(LOCALESEP + PRIVUSE + LOCALESEP);
+            if (idx == -1) {
+                ext = extstr;
+            } else {
+                ext = extstr.substring(0, idx);
+                prv = extstr.substring(idx + 3).intern();
+            }
+        }
+
+        if (ext != null) {
+            //String[] subtags = ext.split(LOCALESEP);
+            String[] subtags = Utility.split(ext, LOCALESEP.charAt(0));
+
+            String letter = subtags[0];
+            if (letter.length() != 1) {
+                throw new InvalidLocaleException("Locale extension string '" + extstr
+                        + "' must start with a singleton segment.");
+            }
+
+            extensions = new TreeMap/*<String,String>*/();
+            StringBuffer buf = new StringBuffer();
+            boolean inLocaleKeywords = false;
+            String kwkey = null;
+
+            for (int i = 1; i < subtags.length; i++) {
+                if (subtags[i].length() == 0) {
+                    throw new InvalidLocaleException("Locale extension string '" + extstr
+                            + "' contains an empty segment.");
+                }
+                if (subtags[i].length() == 1) {
+                    // next extension singleton
+                    if (extensions.containsKey(subtags[i])) {
+                        throw new InvalidLocaleException("Locale extension string '" + extstr
+                                + "' contains multiple extensions: " + subtags[i]);
+                    }
+
+                    // write out the previous extension
+                    if (inLocaleKeywords) {
+                        if (kwkey != null) {
+                            throw new InvalidLocaleException("Locale extension string '" + extstr
+                                    + "' contains a malformed locale keywords: " + kwkey);
+                        }
+                        // creating a single string including locale keyword key/type pairs
+                        mapToLocaleExtensionString(keywords, buf);
+                        inLocaleKeywords = false;
+                    }
+                    if (buf.length() == 0) {
+                        throw new InvalidLocaleException("Locale extension string '" + extstr
+                                + "' contains an empty extension value.");
+                    }
+                    extensions.put(letter.intern(), buf.toString().intern());
+
+                    // preparation for next extension
+                    if (subtags[i].equals(LOCALESINGLETON)) {
+                        keywords = new TreeMap/*<String,String>*/();
+                        inLocaleKeywords = true;
+                    }
+                    letter = subtags[i];
+                    buf.setLength(0);
+                    continue;
+                }
+
+                if (inLocaleKeywords) {
+                    if (kwkey == null) {
+                        kwkey = subtags[i];
+                    } else {
+                        keywords.put(kwkey.intern(), subtags[i].intern());
+                        kwkey = null;
+                    }
+                } else {
+                    // append an extension subtag
+                    if (buf.length() > 0) {
+                        buf.append(LOCALESEP);
+                    }
+                    buf.append(subtags[i]);
+                }
+            }
+
+            // process the last extension
+            if (inLocaleKeywords) {
+                if (kwkey != null) {
+                    throw new InvalidLocaleException("Locale extension string '" + extstr
+                            + "' contains a malformed locale keywords: " + kwkey);
+                }
+                // creating a single string including locale keyword key/type pairs
+                mapToLocaleExtensionString(keywords, buf);
+            }
+            if (buf.length() == 0) {
+                throw new InvalidLocaleException("Locale extension string '" + extstr
+                        + "' contains an empty extension value.");
+            }
+            extensions.put(letter.intern(), buf.toString().intern());
+        }
+
+        // Reconstruct a locale extension string
+        StringBuffer canonicalbuf = new StringBuffer();
+        if (extensions != null) {
+            Set/*<Map.Entry<String,String>>*/ entries = extensions.entrySet();
+            //for (Map.Entry<String,String> entry : entries) {
+            Iterator itr = entries.iterator();
+            while (itr.hasNext()) {
+                Map.Entry entry = (Map.Entry)itr.next();
+                if (canonicalbuf.length() > 0) {
+                    canonicalbuf.append(LOCALESEP);
+                }
+                canonicalbuf.append(entry.getKey());
+                canonicalbuf.append(LOCALESEP);
+                canonicalbuf.append(entry.getValue());
+            }
+        }
+        if (prv != null) {
+            if (canonicalbuf.length() > 0) {
+                canonicalbuf.append(LOCALESEP);
+            }
+            canonicalbuf.append(PRIVUSE);
+            canonicalbuf.append(LOCALESEP);
+            canonicalbuf.append(prv);
+        }
+
+        // Finally, create an instance of LocaleExtension
+        LocaleExtension le = new LocaleExtension(canonicalbuf.toString().intern());
+        le._extensions = extensions;
+        le._keywords = keywords;
+        le._privuse = prv;
+
+        return le;
+    }
+
+    public String toString() {
+        return _canonical;
+    }
+
+    public int hashCode() {
+        return _canonical.hashCode();
+    }
+
+    public String getPrivateUse() {
+        return _privuse;
+    }
+
+    public Set/*<String>*/ getLocaleKeywordKeys() {
+        if (_keywords != null) {
+            return _keywords.keySet();
+        }
+        return null;
+    }
+
+    public boolean containsLocaleKeywordKey(String key) {
+        if (_keywords != null) {
+            return _keywords.containsKey(key);
+        }
+        return false;
+    }
+
+    public String getLocaleKeywordType(String key) {
+        if (_keywords != null) {
+            return (String)_keywords.get(key);
+        }
+        return null;
+    }
+
+    public Set/*<String>*/ getExtensionKeys() {
+        if (_extensions != null) {
+            return _extensions.keySet();
+        }
+        return null;
+    }
+
+    public boolean containsExtensionKey(String key) {
+        if (_extensions != null) {
+            return _extensions.containsKey(key);
+        }
+        return false;
+    }
+
+    public String getExtensionValue(String key) {
+        if (_extensions != null) {
+            return (String)_extensions.get(key);
+        }
+        return null;
+    }
+
+    static String mapToLocaleExtensionString(Map/*<String,String>*/ map, StringBuffer buf) {
+      Set/*<Map.Entry<String,String>>*/ entries = map.entrySet();
+      Iterator itr = entries.iterator();
+      //for (Map.Entry<String,String> entry : entries) {
+      while (itr.hasNext()) {
+          Map.Entry entry = (Map.Entry)itr.next();
+          if (buf.length() > 0) {
+              buf.append(LOCALESEP);
+          }
+          buf.append(entry.getKey());
+          buf.append(LOCALESEP);
+          buf.append(entry.getValue());
+      }
+      return buf.toString();
+    }
+
+    static TreeMap/*<String,String>*/ parseKeywordSubtags(String text, String delim) {
+        if (text == null || text.length() == 0) {
+            return null;
+        }
+        //String[] subtags = AsciiUtil.toLowerString(text).split(delim);
+        String[] subtags = Utility.split(AsciiUtil.toLowerString(text), delim.charAt(0));
+        if ((subtags.length % 2) != 0) {
+            // number of keyword subtags must be even
+            return null;
+        }
+
+        TreeMap/*<String,String>*/ keywords = new TreeMap/*<String,String>*/();
+        int idx = 0;
+        while (idx < subtags.length) {
+            String key = subtags[idx++];
+            String type = subtags[idx++];
+
+            if ((keywords.put(key.intern(), type.intern())) != null) {
+                return null;
+            }
+        }
+        return keywords;
+    }
+}
diff --git a/src/com/ibm/icu/impl/locale/LocaleObjectPool.java b/src/com/ibm/icu/impl/locale/LocaleObjectPool.java
new file mode 100644
index 0000000..977bcbb
--- /dev/null
+++ b/src/com/ibm/icu/impl/locale/LocaleObjectPool.java
@@ -0,0 +1,150 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.impl.locale;
+
+import java.lang.ref.Reference;
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.WeakReference;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+//import java.util.concurrent.ConcurrentHashMap;
+
+public class LocaleObjectPool/*<K,V>*/ {
+
+    //private ConcurrentHashMap<K,ValueRef<V>> _map = new ConcurrentHashMap<K,ValueRef<V>>();
+    private Map _map = Collections.synchronizedMap(new HashMap());
+    private ReferenceQueue/*<V>*/ _rq = new ReferenceQueue/*<V>*/();
+
+    public LocaleObjectPool() {
+    }
+
+    //public V get(Object key) {
+    public Object get(Object key) {
+        expungeStaleEntries();
+        //ValueRef<V> ref = _map.get(key);
+        ValueRef ref = (ValueRef)_map.get(key);
+        if (ref != null) {
+            return ref.get();
+        }
+        return null;
+    }
+
+    //public V getPermanent(Object key) {
+    public Object getPermanent(Object key) {
+        expungeStaleEntries();
+        //ValueRef<V> ref = _map.get(key);
+        ValueRef ref = (ValueRef)_map.get(key);
+        if (ref != null && ref instanceof StrongValueRef) {
+            return ref.get();
+        }
+        return null;
+    }
+
+    /*
+     * Unlike Map#put, this method returns non-null value actually
+     * in the pool, even no values for the key was not available
+     * before.
+     */
+    //public V register(K key, V value) {
+    public Object register(Object key, Object value) {
+        expungeStaleEntries();
+        //V valInPool = value;
+        Object valInPool = value;
+        synchronized(_map) {
+            //ValueRef<V> ref = _map.get(key);
+            ValueRef ref = (ValueRef)_map.get(key);
+            //V tmpVal = (ref == null) ? null : ref.get();
+            Object tmpVal = (ref == null) ? null : ref.get();
+            if (tmpVal == null) {
+                _map.put(key, new WeakValueRef/*<V>*/(key, value, _rq));
+            } else {
+                valInPool = tmpVal;
+            }
+        }
+        return valInPool;
+    }
+
+    /*
+     * Unlike Map#put, this method returns non-null value actually
+     * in the pool, even no values for the key was not available
+     * before.  When the value for the key was available and the value
+     * was weakly referenced, this method will replace the reference
+     * type to strong, but actual value object won't be changed.
+     */
+    //synchronized public V registerPermanent(K key, V value) {
+    synchronized public Object registerPermanent(Object key, Object value) {
+        expungeStaleEntries();
+        //V valInPool = value;
+        Object valInPool = value;
+        synchronized(_map) {
+            //ValueRef<V> ref = _map.get(key);
+            ValueRef ref = (ValueRef)_map.get(key);
+            boolean isStrongRef = false;
+            //V tmpVal = null;
+            Object tmpVal = null;
+            if (ref != null) {
+                tmpVal = ref.get();
+                isStrongRef = (ref instanceof StrongValueRef);
+            }
+            if (tmpVal == null) {
+                _map.put(key, new StrongValueRef/*<V>*/(value));
+            } else if (!isStrongRef) {
+                // If the key already exist and its value is currently
+                // weakly referenced, we use the value with a strong reference.
+                _map.put(key, new StrongValueRef/*<V>*/(tmpVal));
+                valInPool = tmpVal;
+            }
+        }
+        return valInPool;
+    }
+
+    private void expungeStaleEntries() {
+        Reference/*<? extends V>*/ val;
+        while ((val = _rq.poll()) != null) {
+            Object key = ((WeakValueRef/*<?>*/)val).getKey();
+            _map.remove(key);
+        }
+    }
+
+    private static interface ValueRef/*<V>*/ {
+        //V get();
+        Object get();
+    }
+
+    private static class StrongValueRef/*<V>*/ implements ValueRef/*<V>*/ {
+        //private V _value;
+        private Object _value;
+        //public StrongValueRef(V value) {
+        public StrongValueRef(Object value) {
+            _value = value;
+        }
+        //public V get() {
+        public Object get() {
+            return _value;
+        }
+    }
+
+    private static class WeakValueRef/*<V>*/ extends WeakReference/*<V>*/ implements ValueRef/*<V>*/{
+        private Object _key;
+
+        //public WeakValueRef(Object key, V value, ReferenceQueue<V> rq) {
+        public WeakValueRef(Object key, Object value, ReferenceQueue rq) {
+            super(value, rq);
+            _key = key;
+        }
+
+        //public V get() {
+        public Object get() {
+            return super.get();
+        }
+
+        public Object getKey() {
+            return _key;
+        }
+    }
+}
diff --git a/src/com/ibm/icu/util/InvalidLocaleException.java b/src/com/ibm/icu/util/InvalidLocaleException.java
new file mode 100644
index 0000000..905001a
--- /dev/null
+++ b/src/com/ibm/icu/util/InvalidLocaleException.java
@@ -0,0 +1,29 @@
+/*
+ *******************************************************************************
+ * Copyright (C) 2009, International Business Machines Corporation and         *
+ * others. All Rights Reserved.                                                *
+ *******************************************************************************
+ */
+package com.ibm.icu.util;
+
+/**
+ * This exception is used to indicate that a locale field has an
+ * invalid syntax.
+ * 
+ * @draft ICU 4.2
+ * @provisional This API might change or be removed in a future release.
+ */
+public class InvalidLocaleException extends Exception {
+
+    private static final long serialVersionUID = 4129352440101206300L;
+
+    /**
+     * Constructs the exception with the given message.
+     * @param msg the error message for the exception.
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */
+    public InvalidLocaleException(String msg) {
+        super(msg);
+    }
+}
diff --git a/src/com/ibm/icu/util/ULocale.java b/src/com/ibm/icu/util/ULocale.java
index 972c1d5..9ecdda6 100644
--- a/src/com/ibm/icu/util/ULocale.java
+++ b/src/com/ibm/icu/util/ULocale.java
@@ -15,12 +15,19 @@
 import java.util.Locale;
 import java.util.Map;
 import java.util.MissingResourceException;
+import java.util.Set;
 import java.util.TreeMap;
 
 import com.ibm.icu.impl.ICUCache;
 import com.ibm.icu.impl.ICUResourceBundle;
 import com.ibm.icu.impl.LocaleUtility;
 import com.ibm.icu.impl.SimpleCache;
+import com.ibm.icu.impl.Utility;
+import com.ibm.icu.impl.locale.AsciiUtil;
+import com.ibm.icu.impl.locale.BaseLocale;
+import com.ibm.icu.impl.locale.InternalLocaleBuilder;
+import com.ibm.icu.impl.locale.LanguageTag;
+import com.ibm.icu.impl.locale.LocaleExtension;
 
 /**
  * A class analogous to {@link java.util.Locale} that provides additional
@@ -3756,4 +3763,444 @@
     
         return null;
     }
+
+    /** 
+     * Returns an instance of ULocale for the BCP47 language tag.
+     * When the given language tag does not satisfy the locale syntax
+     * requirement, this method stop parsing at the problematic subtag and
+     * create a locale instance with the valid substring.
+     * 
+     * @param languageTag BCP47 language tag 
+     * @return A locale for the given language tag.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */ 
+    public static ULocale forLanguageTag(String languageTag) {
+        //TODO temporary implementation
+        ULocale loc;
+        while (true) {
+            try {
+                loc = forLanguageTagStrict(languageTag);
+                break;
+            } catch (InvalidLocaleException e) {
+                // remove the last subtag and try it again
+                int idx = languageTag.lastIndexOf('-');
+                if (idx == -1) {
+                    // no more subtags
+                    loc = ULocale.ROOT;
+                    break;
+                }
+                languageTag = languageTag.substring(0, idx);
+            }
+        }
+        return loc;
+    }
+
+    /**
+     * Returns an instance of ULocale for the BCP47 language tag.
+     * When the given language tag does not satisfy the locale syntax
+     * requirement, this method throws InvalidLocaleException.
+     * 
+     * @param languageTag BCP47 language tag 
+     * @return A locale for the given language tag.
+     * @throws InvalidLocaleException if the language tag contains invalid subtags.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */
+    public static ULocale forLanguageTagStrict(String languageTag) throws InvalidLocaleException {
+        //TODO temporary implementation
+        LanguageTag tag = LanguageTag.parse(languageTag);
+        String language = tag.getLanguage();
+        String script = tag.getScript();
+        String region = tag.getRegion();
+        String variant = tag.getVariant();
+        String privuse = tag.getPrivateUse();
+
+        boolean hasRegion = false;
+        StringBuffer buf = new StringBuffer();
+        if (language != null && language.length() > 0) {
+            if (!language.equals("und")) {
+                buf.append(language);
+            }
+        }
+        if (script != null && script.length() > 0) {
+            buf.append("_");
+            buf.append(script);
+        }
+        if (region != null && region.length() > 0) {
+            buf.append("_");
+            buf.append(region);
+            hasRegion = true;
+        }
+        if (variant != null && variant.length() > 0) {
+            if (hasRegion) {
+                buf.append("_");
+            }
+            buf.append("_");
+            buf.append(region);
+        }
+
+        if (privuse != null && privuse.length() > 0) {
+            privuse = AsciiUtil.toLowerString(privuse);
+            if (privuse.startsWith("ldml-")) {
+                String[] subtags = Utility.split(privuse, '-');
+                if ((subtags.length - 1)%3 != 0) {
+                    throw new InvalidLocaleException("Invalid ldml keyword sequence: " + privuse);
+                }
+                boolean insertSep = false;
+                buf.append("@");
+                int idx = 1;
+                while (idx < subtags.length) {
+                    String k = subtags[idx++];
+                    if (!k.equals("k")) {
+                        throw new InvalidLocaleException("Invalid ldml keyword sequence: " + privuse);
+                    }
+                    String key = subtags[idx++];
+                    String type = subtags[idx++];
+                    if (insertSep) {
+                        buf.append(";");
+                    } else {
+                        insertSep = true;
+                    }
+                    buf.append(key);
+                    buf.append("=");
+                    buf.append(type);
+                }
+            }
+        }
+        String locID = buf.toString();
+        return new ULocale(locID);
+    }
+
+    /** 
+     * Returns the BCP47 language tag string for this locale. 
+     * 
+     * @return BCP47 language tag string for the locale.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */ 
+    public String toLanguageTag() {
+        //TODO temporary implementation
+        String language = getLanguage();
+        String script = getScript();
+        String region = getCountry();
+        String variant = getVariant();
+
+        StringBuffer buf = new StringBuffer();
+        if (language.length() == 0) {
+            buf.append("und");
+        } else {
+            buf.append(language);
+        }
+        if (script.length() > 0) {
+            buf.append("-");
+            buf.append(script);
+        }
+        if (region.length() > 0) {
+            buf.append("-");
+            buf.append(region);
+        }
+        if (variant.length() > 0) {
+            buf.append("-");
+            buf.append(variant);
+        }
+
+        Iterator itr = getKeywords();
+        if (itr != null) {
+            boolean first = true;
+            while (itr.hasNext()) {
+                String key = (String)itr.next();
+                String type = getKeywordValue(key);
+                if (first) {
+                    buf.append("-x-ldml-k-");
+                    first = false;
+                } else {
+                    buf.append("-k-");
+                }
+                buf.append(key);
+                buf.append("-");
+                buf.append(type);
+            }
+        }
+
+        return buf.toString();
+    }
+
+    /**
+     * Returns an extension value for the specified extension key in this
+     * locale instance.
+     * 
+     * @param key
+     * @return The extension value for the specified extension key, or null
+     * if the extension is not available.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */
+    public String getExtensionValue(String key) {
+        //TODO not implemented
+        return null;
+    }
+
+    /**
+     * Returns an iterator over extension singleton letters.
+     * 
+     * @return An iterator over extension singleton letters, or null ff no
+     * extensions are set in this locale instance.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */
+    public Iterator getExtensionKeys() {
+        //TODO not implemented
+        return null;
+    }
+
+    /**
+     * Returns a private use string.
+     * 
+     * @return A private use string, or null if no private use value is available.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */
+    public String getPrivateUse() {
+        //TODO not implemented
+        return null;
+    }
+
+    /**
+     * This class provides APIs to build an instance of ULocale.
+     * 
+     * @draft ICU 4.2
+     * @provisional This API might change or be removed in a future release.
+     */
+    public static class LocaleBuilder {
+
+        private InternalLocaleBuilder _locbld = new InternalLocaleBuilder();
+
+        /**
+         * Constructs an empty LocaleBuilder.
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder() {
+        }
+
+        /**
+         * Sets the locale to this builder.
+         * 
+         * @param loc the locale
+         * @return this builder
+         * @throws InvalidLocaleException
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setLocale(ULocale loc) throws InvalidLocaleException {
+            setLanguage(loc.getLanguage()).setScript(loc.getScript())
+                .setRegion(loc.getCountry()).setVariant(loc.getVariant());
+
+            Iterator itr = loc.getKeywords();
+            if (itr != null) {
+                while (itr.hasNext()) {
+                    String key = (String)itr.next();
+                    setLocaleKeyword(key, loc.getKeywordValue(key));
+                }
+            }
+            return this;
+        }
+
+        /**
+         * Sets the language to this builder.  If the specified language is empty or null,
+         * this method clears the language value previously set.
+         * 
+         * @param language the language
+         * @return this builder
+         * 
+         * @throws InvalidLocaleException
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setLanguage(String language) throws InvalidLocaleException {
+            String newval = _locbld.setLanguage(language);
+            if (newval == null) {
+                throw new InvalidLocaleException("Invalid language: " + language);
+            }
+            return this;
+        }
+
+        /**
+         * Sets the language to this builder.  If the specified script is empty or null,
+         * this method clears the script value previously set.
+         * 
+         * @param script the script
+         * @return this builder
+         * 
+         * @throws InvalidLocaleException
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setScript(String script) throws InvalidLocaleException {
+            String newval = _locbld.setScript(script);
+            if (newval == null) {
+                throw new InvalidLocaleException("Invalid script: " + script);
+            }
+            return this;
+        }
+
+        /**
+         * Sets the region to this builder.  If the specified region is empty or null,
+         * this method clears the region value previously set.
+         * 
+         * @param region the region
+         * @return this builder
+         * @throws InvalidLocaleException
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setRegion(String region) throws InvalidLocaleException {
+            String newval = _locbld.setRegion(region);
+            if (newval == null) {
+                throw new InvalidLocaleException("Invalid region: " + region);
+            }
+            return this;
+        }
+
+        /**
+         * Sets the variant to this builder.  If the specified variant is empty or null,
+         * this method clears the variant value previously set.
+         * 
+         * @param variant the variant
+         * @return this builder
+         * @throws InvalidLocaleException
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setVariant(String variant) throws InvalidLocaleException {
+            String newval = _locbld.setVariant(variant);
+            if (newval == null) {
+                throw new InvalidLocaleException("Invalid variant: " + variant);
+            }
+            return this;
+        }
+
+        /**
+         * Sets the locale keyword to this builder.  If the specified type is empty or null,
+         * this method clears the type previously set for the key.
+         * 
+         * @param key the locale keyword key
+         * @param type the locake keyword type
+         * @return this builder
+         * @throws InvalidLocaleException
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setLocaleKeyword(String key, String type) throws InvalidLocaleException {
+            boolean set = _locbld.setLocaleKeyword(key, type);
+            if (!set) {
+                throw new InvalidLocaleException("Invalid locale keyword key/type pairs: key=" + key + "/type=" + type);
+            }
+            return this;
+        }
+
+        /**
+         * Sets the locale extension to this builder.  If the specified value is empty or null,
+         * this method clears the value previously set for the key.
+         * 
+         * @param key the extension character key
+         * @param value the extension value
+         * @return this builder
+         * @throws InvalidLocaleException
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setExtension(char key, String value) throws InvalidLocaleException {
+            boolean set = _locbld.setExtension(key, value);
+            if (!set) {
+                throw new InvalidLocaleException("Invalid extension key/value pairs: key=" + key + "/value=" + value);
+            }
+            return this;
+        }
+
+        /**
+         * Sets the private use value to this builder.  If the specified private use value
+         * is empty or null, this method clears the private use value previously set.
+         * 
+         * @param privuse the private use value
+         * @return this builder
+         * @throws InvalidLocaleException
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public LocaleBuilder setPrivateUse(String privuse) throws InvalidLocaleException {
+            String newval = _locbld.setPrivateUse(privuse);
+            if (newval == null) {
+                throw new InvalidLocaleException("Invalid private use value: " + privuse);
+            }
+            return this;
+        }
+
+        /**
+         * Returns an instance of locale created from locale fields configured by
+         * the setters in this locale builder instance.
+         * 
+         * @return a locale
+         * 
+         * @draft ICU 4.2
+         * @provisional This API might change or be removed in a future release.
+         */
+        public ULocale get() {
+            //TODO Make ULocale to store locale identifier in BaseLocale and LocaleExtension
+            //Tentative implementation below -
+            BaseLocale base = _locbld.getBaseLocale();
+            LocaleExtension extension = _locbld.getLocaleExtension();
+
+            StringBuffer buf = new StringBuffer(base.getLanguage());
+            if (base.getScript().length() > 0) {
+                buf.append("_");
+                buf.append(base.getScript());
+            }
+            if (base.getRegion().length() > 0) {
+                buf.append("_");
+                buf.append(base.getRegion());
+            }
+            if (base.getVariant().length() > 0) {
+                if (base.getRegion().length() == 0) {
+                    buf.append("_");
+                }
+                buf.append("_");
+                buf.append(base.getVariant());
+            }
+
+            Set keys = extension.getLocaleKeywordKeys();
+            if (keys != null && keys.size() > 0) {
+                buf.append("@");
+                boolean insertSep = false;
+                Iterator itr = keys.iterator();
+                while (itr.hasNext()) {
+                    String key = (String)itr.next();
+                    String type = extension.getLocaleKeywordType(key);
+                    if (insertSep) {
+                        buf.append(";");
+                    } else {
+                        insertSep = true;
+                    }
+                    buf.append(key);
+                    buf.append("=");
+                    buf.append(type);
+                }
+            }
+            String locID = buf.toString();
+            return new ULocale(locID);
+        }
+    }
 }