最近在解析Android安装包内经过编译的二进制XML文件时想在内存中建立起其对应的树结构。
想了一早晨，思路如下图。
多叉树中的每个节点除了有子节点和兄弟节点以外还有一个指针指向父节点，然后根据状态转移图执行相应的代码就行。
public void main() {
XmlTagTree tree = new XmlTagTree();
while (true) {
// 获取xml标签
Tag tag = getTag();
if (tag.isStartTag()) {
tree.addNode(tag, XmlTagTree.STATE_START);
} else if (tag.isEndTag()){
tree.addNode(null, XmlTagTree.STATE_END);
}
}
}
class Tag {
private Tag parent;
private Tag child;
private Tag next;
}
class XmlTagTree {
public final static int STATE_START = 0;
public final static int STATE_END = 1;
private int mCurrentState = STATE_START;
private Tag mRoot;
private Tag mCurrent;
private XmlTreeOperate[][] mOperates;
private int mSize = 0;
public XmlTagTree() {
mOperates = new XmlTreeOperate[2][2];
mOperates[STATE_START][STATE_START] = new XmlTreeOperate() {
@Override
public void operate(Tag chunk, int state) {
if (mRoot == null) {
// 第一次操作，初始化节点
mRoot = chunk;
mCurrent = chunk;
} else {
// (START, START) -> addChild
mCurrent.child = chunk;
chunk.parent = mCurrent;
mCurrent = chunk;
++mSize;
}
}
};
mOperates[STATE_START][STATE_END] = new XmlTreeOperate() {
@Override
public void operate(Tag chunk, int state) {
// (START, END) -> none
// do not do anything
}
};
mOperates[STATE_END][STATE_START] = new XmlTreeOperate() {
@Override
public void operate(Tag chunk, int state) {
// (END, START) -> addSibling
mCurrent.next = chunk;
chunk.parent = mCurrent.parent;
mCurrent = chunk;
++mSize;
}
};
mOperates[STATE_END][STATE_END] = new XmlTreeOperate() {
@Override
public void operate(Tag chunk, int state) {
// (END, END) -> goParent
mCurrent = mCurrent.parent;
}
};
}
public void addNode(Tag chunk, int state) {
if (mRoot == null && state != STATE_START) {
throw new RuntimeException("first state in XmlTagTree must be STATE_START");
}
mOperates[mCurrentState][state].operate(chunk, state);
mCurrentState = state;
}
private interface XmlTreeOperate {
void operate(Tag chunk, int state);
}
}