1/*
2 *******************************************************************************
3 * Copyright (C) 1998-2010, International Business Machines Corporation and    *
4 * others. All Rights Reserved.                                                *
5 *******************************************************************************
6 *
7 * Created on Dec 3, 2003
8 *
9 *******************************************************************************
10 */
11package com.ibm.icu.dev.tool.layout;
12
13
14import java.io.IOException;
15import java.io.PrintWriter;
16import java.io.Writer;
17
18import com.ibm.icu.impl.Utility;
19import com.ibm.icu.text.UTF16;
20
21public class LigatureTree
22{
23    static class Lignode
24    {
25        int target;
26        int ligature = -1;
27        Lignode[] subnodes = null;
28
29        Lignode()
30        {
31            target = -1;
32        }
33
34        Lignode(int target)
35        {
36            this.target = target;
37        }
38
39        boolean isMatch()
40        {
41            return ligature != -1;
42        }
43
44        int getLigature()
45        {
46            return ligature;
47        }
48
49        Lignode subnode(int c)
50        {
51            if (subnodes != null) {
52                int len = subnodes.length;
53
54                if (c <= subnodes[len - 1].target) {
55                    for (int i = 0; i < len; i+= 1) {
56                        int t = subnodes[i].target;
57
58                        if (t > c) {
59                            return null;
60                        }
61
62                        if (t == c) {
63                            return subnodes[i];
64                        }
65                    }
66                }
67            }
68
69            return null;
70        }
71
72        String ligatureString(int[] chars)
73        {
74            StringBuffer result = new StringBuffer();
75            int len = chars.length - 1;
76
77            for (int i = 0; i < len; i += 1) {
78                if (i > 0) {
79                    result.append(" + ");
80                }
81
82                result.append(Utility.hex(chars[i], 6));
83           }
84
85            result.append(" => " + Utility.hex(chars[len], 6));
86
87            return result.toString();
88        }
89
90        void insert(int[] chars, int index)
91        {
92            int c = chars[index];
93            int len = chars.length;
94
95            if (len == index + 1) {
96                if (ligature != -1) {
97                    System.out.println("ignoring ligature " + ligatureString(chars) +
98                                       ": already have " + Utility.hex(ligature, 6));
99                } else {
100                    ligature = c;
101                }
102
103                return;
104            }
105
106            if (subnodes == null) {
107                subnodes = new Lignode[1];
108                subnodes[0] = new Lignode(c);
109                subnodes[0].insert(chars, index + 1);
110            } else {
111                int i;
112
113                for (i = 0; i < subnodes.length; i += 1)
114                {
115                    int t = subnodes[i].target;
116
117                    if (t == c) {
118                        subnodes[i].insert(chars, index + 1);
119                        return;
120                    } else if (t > c) {
121                        break;
122                    }
123                }
124
125                Lignode[] nnodes = new Lignode[subnodes.length + 1];
126
127                if (i > 0) {
128                    System.arraycopy(subnodes, 0, nnodes, 0, i);
129                }
130
131                nnodes[i] = new Lignode(c);
132
133                if (i < subnodes.length) {
134                    System.arraycopy(subnodes, i, nnodes, i + 1, subnodes.length - i);
135                }
136
137                subnodes = nnodes;
138
139                subnodes[i].insert(chars, index + 1);
140            }
141        }
142
143        public void walk(TreeWalker walker)
144        {
145            if (target != -1) {
146                walker.down(target);
147            }
148
149            if (subnodes != null) {
150                for (int i = 0; i < subnodes.length; i += 1)
151                {
152                    subnodes[i].walk(walker);
153                }
154            }
155
156            if (ligature != -1) {
157                walker.ligature(ligature);
158            }
159
160            walker.up();
161        }
162
163        static final String ind = "                                      ";
164
165        /*
166         * Write debugging information to w, starting at the provided indentation level.
167         */
168        public void dump(Writer w, int indent)
169        {
170            String tab = ind.substring(0, Math.min(indent, ind.length()));
171
172            try {
173                w.write(tab);
174                if (target != -1) {
175                    w.write(Utility.hex(target, 6));
176                }
177
178                if (ligature != -1)
179                {
180                    w.write(" --> ");
181                    w.write(Utility.hex(ligature, 6));
182                }
183
184                w.write("\n");
185
186                if (subnodes != null) {
187                    w.write(tab);
188                    w.write("{\n");
189                    indent += 4;
190
191                    for (int i = 0; i < subnodes.length; i += 1) {
192                        subnodes[i].dump(w, indent);
193                    }
194
195                    w.write(tab);
196                    w.write("}\n");
197                }
198            } catch (IOException e) {
199                System.out.println(e);
200            }
201        }
202
203    }
204
205    private Lignode root = new Lignode();
206
207    public LigatureTree()
208    {
209        // anything?
210    }
211
212    private int[] toIntArray(String s)
213    {
214        int count = UTF16.countCodePoint(s);
215        int[] result = new int[count];
216
217        for (int i = 0; i < count; i += 1) {
218            result[i] = UTF16.charAt(s, i);
219        }
220
221        return result;
222    }
223
224    public void insert(String string)
225    {
226        root.insert(toIntArray(string), 0);
227    }
228
229    public void insert(int[] chars)
230    {
231        root.insert(chars, 0);
232    }
233
234    public void walk(TreeWalker walker)
235    {
236        root.walk(walker);
237        walker.done();
238    }
239
240    public void dump()
241    {
242        PrintWriter pw = new PrintWriter(System.out);
243
244        root.dump(pw, 0);
245        pw.flush();
246    }
247}
248