| /* |
| * Copyright (c) 2002, 2018, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package nsk.share; |
| |
| import java.util.*; |
| |
| /** |
| * This denotation provides naming and indexing for nodes |
| * of a binary, or ternary, or <tt>n</tt>-ary tree. |
| * |
| * <p>Here, <tt>n</tt> would be the length of a symbols |
| * string used as an alphabeth for nodes naming. For a |
| * binary tree, <tt>n=2</tt>, and an aplhabeth could be |
| * the <tt>"LR"</tt> string. This implies the following |
| * naming for tree nodes: |
| * <pre> |
| * (empty) |
| * / \ |
| * L R |
| * / \ / \ |
| * LL LR RL RR |
| * / \ / \ / \ / \ |
| * </pre> |
| * |
| * <p>Anyway, the tree root node is named with the empty |
| * string <tt>""</tt> and is indexed with 2-zeroes array |
| * <tt>{0,0}</tt>. |
| * |
| * <p>Index for a tree node is 2-elements <tt>int[]</tt> |
| * array. The 1st element is the node's level in a tree. |
| * The 2nd element is the item's number among all nodes of |
| * that level; provided that node items are enumerated from |
| * <tt>0</tt> to <tt>n</tt><sup>level</sup><tt>-1</tt>. |
| * Given a level, lexicographic order is assumed for the |
| * nodes of the same level. |
| * |
| * <p>For example: given the above sample tree, the node |
| * <tt>"L"</tt> has the index <tt>{1,0}</tt>, while the |
| * node <tt>"RL"</tt> has the index <tt>{2,2}</tt>. |
| * |
| * <p>In general case, ordering of characters used for nodes |
| * naming is implied by the given alphabeth. This may differ |
| * from the ``natural'' ordering. For example, if alphabeth |
| * is <tt>"ZYX...CBA"</tt>, then ordering for nodes would be |
| * opposite to ``natural''. |
| */ |
| public class TreeNodesDenotation extends Denotation { |
| /** |
| * Symbols to denote tree nodes. |
| * |
| * @see #TreeNodeDenotation(String) |
| */ |
| private String alphabeth; |
| |
| /** |
| * Standard denotation for a binary tree; alphabeth |
| * is <tt>"LR"</tt>. |
| * |
| * @see #TreeNodesDenotation(String) |
| */ |
| public TreeNodesDenotation() { |
| this("LR"); |
| } |
| |
| /** |
| * Denotation for nodes of a tree. |
| * |
| * <p>Each tree node is marked with a string of symbols |
| * from the given <tt>alphabeth</tt>. A string length |
| * equals to the node's level. The root node is always |
| * denoted with the empty string. |
| * |
| * <p>For example, an <tt>alphabeth</tt> for a binary |
| * tree could be <tt>"LR"</tt>, or <tt>"01"</tt>, or |
| * any 2-symbols string. However, <tt>"lL"</tt> or |
| * <tt>"rR"</tt> would be illegal because of collision |
| * between upper- and lower- case letters. |
| * |
| * <p>In general case, it is illegal for <tt>alphabeth</tt> |
| * to contain two or several copies of the same symbol. |
| * This constructor deems lower- and upper-case variants |
| * of the same letter are the same symbol. |
| * |
| * @throws IllegalArgumentException If the <tt>alphabeth</tt> |
| * looks illegal. |
| */ |
| public TreeNodesDenotation(String alphabeth) { |
| if (alphabeth.length() == 0) |
| throw new IllegalArgumentException("empty alphabeth"); |
| // Check for lower- to upper- case collision: |
| this.alphabeth = alphabeth.toUpperCase(); |
| int length = this.alphabeth.length(); |
| Set<Character> pool = new HashSet<Character>(); // still empty |
| for (int i=0; i<length; i++) |
| pool.add(new Character(this.alphabeth.charAt(i))); |
| if (pool.size() != length) |
| throw new IllegalArgumentException("collision: " + alphabeth); |
| } |
| |
| /** |
| * Check if the <tt>name</tt> is legal, and return the |
| * numeric index for the tree node denoted by the given |
| * <tt>name</tt>. |
| * |
| * @throws IllegalArgumentException If the <tt>name</tt> |
| * is illegal. |
| */ |
| public int[] indexFor(String name) { |
| int level = name.length(); |
| int factor = alphabeth.length(); |
| long item = 0; |
| for (int i=0; i<level; i++) { |
| char symbol = Character.toUpperCase(name.charAt(i)); |
| int position = alphabeth.indexOf(symbol); |
| if (position < 0) |
| throw new IllegalArgumentException("unknown symbol: " + name); |
| item = item*factor + position; |
| if (item < 0 || item > Integer.MAX_VALUE) |
| throw new IllegalArgumentException("too long name: " + name); |
| }; |
| int[] index = new int [] { level, (int)item }; |
| return index; |
| } |
| |
| /** |
| * Check if the <tt>index[]</tt> is legal, and return |
| * a symbolic name for the tree node denoted by the |
| * given <tt>index[]</tt>. |
| * |
| * @throws IllegalArgumentException If the <tt>index[]</tt> |
| * is illegal. |
| */ |
| public String nameFor(int[] index) { |
| if (index.length != 2) |
| throw new IllegalArgumentException( |
| "index dimention: " + index.length); |
| StringBuffer name = new StringBuffer(); // still empty |
| int level = index[0]; |
| int item = index[1]; |
| if (level < 0 || item < 0) |
| throw new IllegalArgumentException( |
| "negative index: " + level + ", " + item); |
| int factor = alphabeth.length(); |
| for (int i=0; i<level; i++) { |
| int k = item % factor; |
| name.append(alphabeth.charAt(k)); |
| item = item / factor; |
| }; |
| if (item != 0) |
| throw new IllegalArgumentException( |
| "out of range: {"+ index[0] + "," + index[1] + "}"); |
| return new String(name.reverse()); |
| } |
| } |
