1/*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5/*
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements.  See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License.  You may obtain a copy of the License at
12 *
13 *      http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21
22package com.sun.org.apache.xerces.internal.impl.xpath.regex;
23
24/**
25 */
26
27final class CaseInsensitiveMap {
28
29    private static final int CHUNK_SHIFT = 10;           /* 2^10 = 1k */
30    private static final int CHUNK_SIZE = (1<<CHUNK_SHIFT);
31    private static final int CHUNK_MASK = (CHUNK_SIZE-1);
32    private static final int INITIAL_CHUNK_COUNT = 64;   /* up to 0xFFFF */
33
34    private static int[][][] caseInsensitiveMap;
35
36    private static final int LOWER_CASE_MATCH = 1;
37    private static final int UPPER_CASE_MATCH = 2;
38
39    static {
40        buildCaseInsensitiveMap();
41    }
42
43    /**
44     *  Return a list of code point characters (not including the input value)
45     *  that can be substituted in a case insensitive match
46     */
47    static public int[] get(int codePoint) {
48        return (codePoint < 0x10000) ? getMapping(codePoint) : null;
49    }
50
51    private static int[] getMapping(int codePoint) {
52        int chunk = codePoint >>> CHUNK_SHIFT;
53        int offset = codePoint & CHUNK_MASK;
54
55        return caseInsensitiveMap[chunk][offset];
56    }
57
58    private static void buildCaseInsensitiveMap() {
59        caseInsensitiveMap = new int[INITIAL_CHUNK_COUNT][CHUNK_SIZE][];
60        int lc, uc;
61        for (int i=0; i<0x10000; i++) {
62            lc = Character.toLowerCase(i);
63            uc = Character.toUpperCase(i);
64
65            // lower/upper case value is not the same as code point
66            if (lc != uc || lc != i) {
67                int[] map = new int[2];
68                int index = 0;
69
70                if (lc != i) {
71                    map[index++] = lc;
72                    map[index++] = LOWER_CASE_MATCH;
73                    int[] lcMap = getMapping(lc);
74                    if (lcMap != null) {
75                        map = updateMap(i, map, lc, lcMap, LOWER_CASE_MATCH);
76                    }
77                }
78
79                if (uc != i) {
80                    if (index == map.length) {
81                        map = expandMap(map, 2);
82                    }
83                    map[index++] = uc;
84                    map[index++] = UPPER_CASE_MATCH;
85                    int[] ucMap = getMapping(uc);
86                    if (ucMap != null) {
87                        map = updateMap(i, map, uc, ucMap, UPPER_CASE_MATCH);
88                    }
89                }
90
91                set(i, map);
92            }
93        }
94    }
95
96    private static int[] expandMap(int[] srcMap, int expandBy) {
97        final int oldLen = srcMap.length;
98        int[] newMap = new int[oldLen + expandBy];
99
100        System.arraycopy(srcMap, 0, newMap, 0, oldLen);
101        return newMap;
102    }
103
104    private static void set(int codePoint, int[] map) {
105        int chunk = codePoint >>> CHUNK_SHIFT;
106        int offset = codePoint & CHUNK_MASK;
107
108        caseInsensitiveMap[chunk][offset] = map;
109    }
110
111    private static int[] updateMap(int codePoint, int[] codePointMap,
112            int ciCodePoint, int[] ciCodePointMap, int matchType) {
113        for (int i=0; i<ciCodePointMap.length; i+=2) {
114            int c = ciCodePointMap[i];
115            int[] cMap = getMapping(c);
116            if (cMap != null) {
117                if (contains(cMap, ciCodePoint, matchType)) {
118                    if (!contains(cMap, codePoint)) {
119                        cMap = expandAndAdd(cMap, codePoint, matchType);
120                        set(c, cMap);
121                    }
122                    if (!contains(codePointMap, c)) {
123                        codePointMap = expandAndAdd(codePointMap, c,matchType);
124                    }
125                }
126            }
127        }
128
129        if (!contains(ciCodePointMap, codePoint)) {
130            ciCodePointMap = expandAndAdd(ciCodePointMap, codePoint, matchType);
131            set(ciCodePoint, ciCodePointMap);
132        }
133
134        return codePointMap;
135    }
136
137    private static boolean contains(int[] map, int codePoint) {
138        for (int i=0; i<map.length; i += 2) {
139            if (map[i] == codePoint) {
140                return true;
141            }
142        }
143        return false;
144    }
145
146    private static boolean contains(int[] map, int codePoint, int matchType) {
147        for (int i=0; i<map.length; i += 2) {
148            if (map[i] == codePoint && map[i+1] == matchType) {
149                return true;
150            }
151        }
152        return false;
153    }
154
155    private static int[] expandAndAdd(int[] srcMap, int codePoint, int matchType) {
156        final int oldLen = srcMap.length;
157        int[] newMap = new int[oldLen + 2];
158
159        System.arraycopy(srcMap, 0, newMap, 0, oldLen);
160        newMap[oldLen] = codePoint;
161        newMap[oldLen+1] = matchType;
162        return newMap;
163    }
164}
165