12ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller/* GENERATED SOURCE. DO NOT MODIFY. */ 2f86f25d102340da66b9c7cb6b2d5ecdc0de43ecfFredrik Roubert// © 2016 and later: Unicode, Inc. and others. 3f86f25d102340da66b9c7cb6b2d5ecdc0de43ecfFredrik Roubert// License & terms of use: http://www.unicode.org/copyright.html#License 42ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller/******************************************************************** 52ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * COPYRIGHT: 61c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert * Copyright (c) 2001-2016, International Business Machines Corporation and 72ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * others. All Rights Reserved. 82ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ********************************************************************/ 92ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerpackage android.icu.text; 112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerimport java.util.HashSet; 132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerimport java.util.List; 142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerimport java.util.Set; 152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerimport android.icu.impl.Assert; 172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller/** 192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller * This class represents a node in the parse tree created by the RBBI Rule compiler. 202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller */ 212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fullerclass RBBINode { 222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 231c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // enum NodeType { 252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int setRef = 0; 262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int uset = 1; 272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int varRef = 2; 282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int leafChar = 3; 292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int lookAhead = 4; 302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int tag = 5; 312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int endMark = 6; 322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opStart = 7; 332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opCat = 8; 342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opOr = 9; 352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opStar = 10; 362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opPlus = 11; 372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opQuestion = 12; 382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opBreak = 13; 392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opReverse = 14; 402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int opLParen = 15; 412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int nodeTypeLimit = 16; // For Assertion checking only. 421c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final String [] nodeTypeNames = { 442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "setRef", 452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "uset", 462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "varRef", 472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "leafChar", 482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "lookAhead", 492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "tag", 502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "endMark", 512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opStart", 522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opCat", 532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opOr", 542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opStar", 552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opPlus", 562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opQuestion", 572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opBreak", 582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opReverse", 592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller "opLParen" 602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller }; 612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 621c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert// enum OpPrecedence { 632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int precZero = 0; 642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int precStart = 1; 652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int precLParen = 2; 662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int precOpOr = 3; 672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static final int precOpCat = 4; 681c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int fType; // enum NodeType 702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode fParent; 712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode fLeftChild; 722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode fRightChild; 732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller UnicodeSet fInputSet; // For uset nodes only. 742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int fPrecedence = precZero; // enum OpPrecedence, For binary ops only. 751c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller String fText; // Text corresponding to this node. 772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // May be lazily evaluated when (if) needed 782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // for some node types. 792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int fFirstPos; // Position in the rule source string of the 802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // first text associated with the node. 812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // If there's a left child, this will be the same 822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // as that child's left pos. 832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int fLastPos; // Last position in the rule source string 842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // of any text associated with this node. 852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // If there's a right child, this will be the same 862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // as that child's last postion. 872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller boolean fNullable; // See Aho DFA table generation algorithm 892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int fVal; // For leafChar nodes, the value. 902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Values are the character category, 912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // corresponds to columns in the final 922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // state transition table. 932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller boolean fLookAheadEnd; // For endMark nodes, set TRUE if 951c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert // marking the end of a look-ahead rule. 961c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 971c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert boolean fRuleRoot; // True if this node is the root of a rule. 981c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert boolean fChainIn; // True if chaining into this rule is allowed 991c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert // (no '^' present). 1001c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 1012ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller Set<RBBINode> fFirstPosSet; // See Aho DFA table generation algorithm 1031c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert Set<RBBINode> fLastPosSet; // See Aho. 1042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller Set<RBBINode> fFollowPos; // See Aho. 1051c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 1062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller int fSerialNum; // Debugging aids. Each node gets a unique serial number. 1072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static int gLastSerial; 1082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode(int t) { 1102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller Assert.assrt(t < nodeTypeLimit); 1112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fSerialNum = ++gLastSerial; 1122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fType = t; 1132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fFirstPosSet = new HashSet<RBBINode>(); 1152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLastPosSet = new HashSet<RBBINode>(); 1162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fFollowPos = new HashSet<RBBINode>(); 1172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (t == opCat) { 1182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fPrecedence = precOpCat; 1192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if (t == opOr) { 1202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fPrecedence = precOpOr; 1212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if (t == opStart) { 1222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fPrecedence = precStart; 1232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if (t == opLParen) { 1242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fPrecedence = precLParen; 1252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 1262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fPrecedence = precZero; 1272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode(RBBINode other) { 1312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fSerialNum = ++gLastSerial; 1322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fType = other.fType; 1332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fInputSet = other.fInputSet; 1342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fPrecedence = other.fPrecedence; 1352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fText = other.fText; 1362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fFirstPos = other.fFirstPos; 1372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLastPos = other.fLastPos; 1382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fNullable = other.fNullable; 1392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fVal = other.fVal; 1401c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert fRuleRoot = false; 1411c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert fChainIn = other.fChainIn; 1422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fFirstPosSet = new HashSet<RBBINode>(other.fFirstPosSet); 1432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLastPosSet = new HashSet<RBBINode>(other.fLastPosSet); 1442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fFollowPos = new HashSet<RBBINode>(other.fFollowPos); 1452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 1482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 1492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // cloneTree Make a copy of the subtree rooted at this node. 1502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Discard any variable references encountered along the way, 1512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // and replace with copies of the variable's definitions. 1522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Used to replicate the expression underneath variable 1532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // references in preparation for generating the DFA tables. 1542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 1552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 1562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode cloneTree() { 1572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode n; 1582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fType == RBBINode.varRef) { 1602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // If the current node is a variable reference, skip over it 1612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // and clone the definition of the variable instead. 1622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n = fLeftChild.cloneTree(); 1632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else if (fType == RBBINode.uset) { 1642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n = this; 1652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 1662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n = new RBBINode(this); 1672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fLeftChild != null) { 1682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n.fLeftChild = fLeftChild.cloneTree(); 1692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n.fLeftChild.fParent = n; 1702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fRightChild != null) { 1722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n.fRightChild = fRightChild.cloneTree(); 1732ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller n.fRightChild.fParent = n; 1742ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return n; 1772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 1782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 1812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 1822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 1832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // flattenVariables Walk a parse tree, replacing any variable 1842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // references with a copy of the variable's definition. 1852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Aside from variables, the tree is not changed. 1862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 1872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Return the root of the tree. If the root was not a variable 1882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // reference, it remains unchanged - the root we started with 1892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // is the root we return. If, however, the root was a variable 1902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // reference, the root of the newly cloned replacement tree will 1912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // be returned, and the original tree deleted. 1922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 1932ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // This function works by recursively walking the tree 1942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // without doing anything until a variable reference is 1952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // found, then calling cloneTree() at that point. Any 1962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // nested references are handled by cloneTree(), not here. 1972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 1982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 1992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode flattenVariables() { 2002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fType == varRef) { 201f86f25d102340da66b9c7cb6b2d5ecdc0de43ecfFredrik Roubert RBBINode retNode = fLeftChild.cloneTree(); 202f86f25d102340da66b9c7cb6b2d5ecdc0de43ecfFredrik Roubert retNode.fRuleRoot = this.fRuleRoot; 203f86f25d102340da66b9c7cb6b2d5ecdc0de43ecfFredrik Roubert retNode.fChainIn = this.fChainIn; 2042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return retNode; 2052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fLeftChild != null) { 2082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild = fLeftChild.flattenVariables(); 2092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild.fParent = this; 2102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fRightChild != null) { 2122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild = fRightChild.flattenVariables(); 2132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild.fParent = this; 2142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller return this; 2162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 2192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // flattenSets Walk the parse tree, replacing any nodes of type setRef 2212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // with a copy of the expression tree for the set. A set's 2222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // equivalent expression tree is precomputed and saved as 2232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // the left child of the uset node. 2242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 2262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller void flattenSets() { 2272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller Assert.assrt(fType != setRef); 2282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fLeftChild != null) { 2302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fLeftChild.fType == setRef) { 2312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode setRefNode = fLeftChild; 2322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode usetNode = setRefNode.fLeftChild; 2332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode replTree = usetNode.fLeftChild; 2342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild = replTree.cloneTree(); 2352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild.fParent = this; 2362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 2372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild.flattenSets(); 2382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fRightChild != null) { 2422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fRightChild.fType == setRef) { 2432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode setRefNode = fRightChild; 2442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode usetNode = setRefNode.fLeftChild; 2452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode replTree = usetNode.fLeftChild; 2462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild = replTree.cloneTree(); 2472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild.fParent = this; 2482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // delete setRefNode; 2492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 2502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild.flattenSets(); 2512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 2562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // findNodes() Locate all the nodes of the specified type, starting 2582ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // at the specified root. 2592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 2612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller void findNodes(List<RBBINode> dest, int kind) { 2622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fType == kind) { 2632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller dest.add(this); 2642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fLeftChild != null) { 2662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild.findNodes(dest, kind); 2672ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2682ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fRightChild != null) { 2692ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild.findNodes(dest, kind); 2702ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2712ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2722ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2731c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 2741c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 2752ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 2762ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2772ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // print. Print out a single node, for debugging. 2782ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 2792ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller //------------------------------------------------------------------------- 2802ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:OFF 2812ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static void printNode(RBBINode n) { 2822ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 2832ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (n==null) { 2842ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.print (" -- null --\n"); 2852ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } else { 2862ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printInt( n.fSerialNum, 10); 2872ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printString(nodeTypeNames[n.fType], 11); 2882ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printInt(n.fParent==null? 0 : n.fParent.fSerialNum, 11); 2892ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printInt(n.fLeftChild==null? 0 : n.fLeftChild.fSerialNum, 11); 2902ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printInt(n.fRightChild==null? 0 : n.fRightChild.fSerialNum, 12); 2912ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printInt(n.fFirstPos, 12); 2922ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller RBBINode.printInt(n.fVal, 7); 2931c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 2942ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (n.fType == varRef) { 2952ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.print(" " + n.fText); 2962ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2972ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 2982ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.println(""); 2992ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3002ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:ON 3011c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 3022ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3032ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Print a String in a fixed field size. 3042ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Debugging function. 3052ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:OFF 3062ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static void printString(String s, int minWidth) { 3072ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for (int i = minWidth; i < 0; i++) { 3082ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // negative width means pad leading spaces, not fixed width. 3092ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.print(' '); 3102ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3112ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller for (int i = s.length(); i < minWidth; i++) { 3122ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.print(' '); 3132ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3142ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.print(s); 3152ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3162ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:ON 3172ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3182ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 3192ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Print an int in a fixed size field. 3202ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Debugging function. 3212ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 3222ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:OFF 3232ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static void printInt(int i, int minWidth) { 3242ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller String s = Integer.toString(i); 3252ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printString(s, Math.max(minWidth, s.length() + 1)); 3262ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3272ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:ON 3282ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3292ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:OFF 3302ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller static void printHex(int i, int minWidth) { 3312ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller String s = Integer.toString(i, 16); 3322ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller String leadingZeroes = "00000" 3332ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller .substring(0, Math.max(0, 5 - s.length())); 3342ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller s = leadingZeroes + s; 3352ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printString(s, minWidth); 3362ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3372ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:ON 3382ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3392ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3402ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // ------------------------------------------------------------------------- 3412ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 3422ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // print. Print out the tree of nodes rooted at "this" 3432ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // 3442ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // ------------------------------------------------------------------------- 3452ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:OFF 3462ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller void printTree(boolean printHeading) { 3472ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (printHeading) { 3482ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.println( "-------------------------------------------------------------------"); 3492ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller System.out.println(" Serial type Parent LeftChild RightChild position value"); 3502ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3512ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller printNode(this); 3522ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Only dump the definition under a variable reference if asked to. 3532ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller // Unconditinally dump children of all other node types. 3542ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fType != varRef) { 3552ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fLeftChild != null) { 3562ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fLeftChild.printTree(false); 3572ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3581c8a530973739aafa823d758240d2cd5dad96fe3Fredrik Roubert 3592ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller if (fRightChild != null) { 3602ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller fRightChild.printTree(false); 3612ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3622ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3632ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller } 3642ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller ///CLOVER:ON 3652ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller 3662ae130017183d2f66d55bf0ca51f8da3294644fdNeil Fuller} 367