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