public class GRNode
extends java.lang.Object
Original documentation:
GRNode implements basic capabilities of Red-Black trees, an efficient kind of balanced binary tree. The particular algorithms used are adaptations of those in Corman, Lieserson, and Rivest's Introduction to Algorithms. This class was inspired by (and code cross-checked with) a similar class by Chuck McManis. The implementations of rebalancings during insertion and deletion are a little trickier than those versions: Most standard accounts use a special dummy `nil' node for such purposes, but that doesn't work well in a possibly concurrent environment.
GRForest is a collection of static functions that operate on GRNode Trees.
Each tree's root is stored in mmj.lang.Cnst.gRRoot(dot).
A tree contains every Notation Grammar Rule that begins with the gRRoot's Cnst. Each leaf node has a reference (pointer) to a sub-tree, and so on. This enables all Rules whose expressions begin with "(" to share a common root.
The purpose of GRForest and GRNode was to provide a searchable repository of NotationRule information, and it is used for that purpose in mmj.verify.BottomUpParser.java. However, the Bottom Up algorithm is to inefficient for Metamath's set.mm and has been "deprecated" (to put it politely), in favor of mmj.verify.EarleyParser.java.
So, GRForest and GRNode are teetering on obsolescence and could be removed from without too much trouble. The only use for them still is checking for duplicate Rule expressions, and there is obviously a cheaper way to do that than with these things...(I'm guessing that since each GrammarRule carries its own expression that the hash code for each rule could be pre-computed and even stored, if desired, and then used as the key to a HashSet. Bada bing, bada boom.)
Therefore, I am not going to document these any further.
Modifier and Type | Field and Description |
---|---|
protected boolean |
color_ |
protected Cnst |
elementCnst_ |
protected GRNode |
elementDownLevelRoot_ |
protected NotationRule |
elementNotationRule_ |
protected GRNode |
elementUpLevel_ |
protected GRNode |
left_ |
protected GRNode |
parent_ |
protected GRNode |
right_ |
Constructor and Description |
---|
GRNode(Cnst elementCnst) |
GRNode(Cnst elementCnst,
NotationRule elementNotationRule,
GRNode elementUpLevel,
GRNode elementDownLevelRoot) |
Modifier and Type | Method and Description |
---|---|
protected void |
copyContents(GRNode t) |
Cnst |
elementCnst() |
void |
elementCnst(Cnst v) |
GRNode |
elementDownLevelRoot() |
void |
elementDownLevelRoot(GRNode v) |
NotationRule |
elementNotationRule() |
void |
elementNotationRule(NotationRule v) |
GRNode |
elementUpLevel() |
void |
elementUpLevel(GRNode v) |
GRNode |
find(Cnst elementCnst) |
protected GRNode |
fixAfterInsertion(GRNode root) |
GRNode |
insertLeft(GRNode cell,
GRNode root) |
GRNode |
insertRight(GRNode cell,
GRNode root) |
boolean |
isRoot() |
GRNode |
left() |
GRNode |
leftmost() |
void |
loadRuleCollection(java.util.Collection<NotationRule> ruleCollection) |
GRNode |
parent() |
GRNode |
predecessor() |
GRNode |
right() |
GRNode |
rightmost() |
GRNode |
root() |
protected GRNode |
rotateLeft(GRNode root) |
protected GRNode |
rotateRight(GRNode root) |
int |
size() |
GRNode |
successor() |
protected Cnst elementCnst_
protected NotationRule elementNotationRule_
protected GRNode elementUpLevel_
protected GRNode elementDownLevelRoot_
protected boolean color_
protected GRNode left_
protected GRNode right_
protected GRNode parent_
public GRNode(Cnst elementCnst)
public GRNode(Cnst elementCnst, NotationRule elementNotationRule, GRNode elementUpLevel, GRNode elementDownLevelRoot)
public void loadRuleCollection(java.util.Collection<NotationRule> ruleCollection)
public final Cnst elementCnst()
public final NotationRule elementNotationRule()
public final GRNode elementUpLevel()
public final GRNode elementDownLevelRoot()
public final void elementCnst(Cnst v)
public final void elementNotationRule(NotationRule v)
public final void elementUpLevel(GRNode v)
public final void elementDownLevelRoot(GRNode v)
public final GRNode left()
public final GRNode right()
public final GRNode parent()
protected void copyContents(GRNode t)
public final GRNode leftmost()
public final GRNode rightmost()
public final GRNode root()
public final boolean isRoot()
public final GRNode successor()
public final GRNode predecessor()
public final int size()