hierarchypropertyparser.java

wekaUT是 university texas austin 开发的基于weka的半指导学习(semi supervised learning)的分类器

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program 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 for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    HierarchyPropertyParser.java
 *    Copyright (C) 2001 Xin Xu
 *
 */

package weka.gui;

import java.util.*;
import java.lang.*;
import java.io.*;


/**
 * This class implements a parser to read properties that have
 * a hierarchy(i.e. tree) structure.  Conceptually it's similar to 
 * the XML DOM/SAX parser but of course is much simpler and 
 * uses dot as the seperator of levels instead of back-slash.<br>
 * It provides interfaces to both build a parser tree and traverse
 * the tree. <br>
 * Note that this implementation does not lock the tree when different
 * threads are traversing it simultaneously, i.e. it's NOT synchronized
 * and multi-thread safe.  It is recommended that later implementation
 * extending this class provide a locking scheme and override the 
 * functions with the "synchronized" modifier (most of them are 
 * goToXXX() and information accessing functions).<p>
 *
 * @author Xin Xu ([e-mail])
 * @version $Revision: 1.1.1.1 $
 */
public class HierarchyPropertyParser implements Serializable{

    /** Keep track of the root of the tree */
    private TreeNode m_Root;
    
    /** Keep track of the current node when traversing the tree */
    private TreeNode m_Current;

    /** The level separate in the path */
    private String m_Seperator = ".";
    
    /** The depth of the tree */
    private int m_Depth = 0;
	
    /** 
     * The inner class implementing a single tree node.
     * All fields are made public simply for convenient access,
     * Although a severe violation of OO Design principle.
     */
    private class TreeNode{
	/** The parent of this node */
	public TreeNode parent = null;
	
	/** The value of this node.  Always String  */
	public String value = null;

	/** The children of this node */
	public Vector children = null;	

	/** The level of this node */
	public int level = 0;

	/** The context of this node */
	public String context = null;
    }
    
    /** Default constructor */
    public HierarchyPropertyParser(){
	m_Root = new TreeNode();
	m_Root.parent = null;
	m_Root.children = new Vector();
	goToRoot();
    }
    
    /**
     * Constructor that builds a tree from the given property with
     * the given delimitor
     *
     * @param p the given property string
     * @param delim the given dilimitor
     */
    public HierarchyPropertyParser(String p, String delim) throws Exception {
	this();		
	build(p, delim);
    }
    
    /**
     * Set the seperator between levels.  Default is dot.
     *
     * @param s the seperator symbol
     */
    public void setSeperator(String s){
	m_Seperator = s;
    }

    /**
     * Get the seperator between levels.  Default is dot.
     *
     * @return the seperator symbol
     */
    public String getSeperator(){ return m_Seperator; }
   
    /** 
     * Build a tree from the given property with the given delimitor
     *
     * @param p the given property
     * @param delim the given delimitor
     */
    public void build(String p, String delim) throws Exception {
	StringTokenizer st = new StringTokenizer(p, delim);
	//System.err.println("delim: "+delim);
	while(st.hasMoreTokens()){
	    String property = st.nextToken().trim();
	    if(!isHierachic(property))
		throw new Exception("The given property is not in"+
				    "hierachy structure with seperators!");
	    add(property);	   
	}
	goToRoot();
    }

    /**
     * Add the given item of property to the tree
     *
     * @param property the given item
     */ 
    public synchronized void add(String property){
	String[] values = tokenize(property);
	if(m_Root.value == null)
	    m_Root.value = values[0];
	
	buildBranch(m_Root, values, 1);
    }
    
    /** 
     * Private function to build one branch of the tree
     * based on one property 
     * 
     * @param parent the parent of the node to be built
     * @param values the value of one property
     * @param lvl the level of the node to be built in the tree
     */
    private void buildBranch(TreeNode parent, String[] values, int lvl){
	// Precondition: children is not null
	
	if(lvl == values.length){  // Parent is leaf
	    parent.children = null;
	    return;
	}
	
	if(lvl > (m_Depth-1))
	    m_Depth = lvl+1;  // Depth starts from 1
	
	Vector kids = parent.children;
	int index = search(kids, values[lvl]);
	if(index != -1){
	    TreeNode newParent = (TreeNode)kids.elementAt(index);
	    if(newParent.children == null)
		newParent.children = new Vector();
	    buildBranch(newParent, values, lvl+1);
	}
	else{
	    TreeNode added = new TreeNode();
	    added.parent = parent;
	    added.value = values[lvl];
	    added.children = new Vector();
	    added.level = lvl;
	    if(parent != m_Root)
		added.context = parent.context + m_Seperator + parent.value;
	    else
		added.context = parent.value;
	    
	    kids.addElement(added);
	    buildBranch(added, values, lvl+1);
	}
    }
    
    /**
     * Tokenize the given string based on the seperator and
     * put the tokens into an array of strings
     *
     * @param rawString the given string
     * @return an array of strings
     */
    public String[] tokenize(String rawString){
	Vector result = new Vector();
	StringTokenizer tk = new StringTokenizer(rawString, m_Seperator);
	while(tk.hasMoreTokens())
	    result.addElement(tk.nextToken());
	
	String[] newStrings = new String[result.size()];
	for(int i=0; i < result.size(); i++)
	    newStrings[i] = (String)result.elementAt(i);
	
	return newStrings;
    }
    
    /**
     * Whether the HierarchyPropertyParser contains the given
     * string
     *
     * @param string the given string
     * @return whether contains
     */
    public boolean contains(String string){
	String[] item = tokenize(string);
	if(!item[0].equals(m_Root.value))
	    return false;
	
	return isContained(m_Root, item, 1);
    }
    
    /** 
     * Private function to decide whether one level of one branch 
     * contains the relevant values
     * 
     * @param parent the parent of the node to be searched
     * @param values the value of one property
     * @param lvl the level of the node in question
     * @return whether this branch contains the corresponding values
     */
    private boolean isContained(TreeNode parent, String[] values, int lvl){
	if(lvl == values.length)  // Parent is leaf
	    return true;
	else if(lvl > values.length)
	    return false;
	else{
	    Vector kids = parent.children;
	    int index = search(kids, values[lvl]);
	    if(index != -1){
		TreeNode newParent = (TreeNode)kids.elementAt(index);
		return isContained(newParent, values, lvl+1);
	    }
	    else
		return false;
	}
    }
    
    /** 
     * Whether the given string has a hierachy structure with
     * the seperators
     *
     * @param string the given string
     */
    public boolean isHierachic(String string){
	int index = string.indexOf(m_Seperator); 
	// Seperator not occur or first occurance at the end
	if((index == (string.length()-1)) || (index == -1))
	    return false;
	
	return true;
    }

    /**
     * Helper function to search for the given target string in a 
     * given vector in which the elements' value may hopefully is equal
     * to the target.  If such elements are found the first index
     * is returned, otherwise -1
     *
     * @param vct the given vector
     * @param target the given target string
     * @return the index of the found element, -1 if not found
     */
    public int search(Vector vct, String target){
	if(vct == null)
	    return -1;
	
	for(int i=0; i < vct.size(); i++)
	    if(target.equals(((TreeNode)vct.elementAt(i)).value))
		return i;
	
	return -1;
    }

    /**
     * Go to a certain node of the tree according to the specified path
     * Note that the path must be absolute path from the root.  <br>
     * For relative path, see goDown(String path).
     *
     * @param path the given absolute path
     * @return whether the path exists, if false the current position does
     * not move
     */
    public synchronized boolean goTo(String path){
	if(!isHierachic(path)){
	    if(m_Root.value.equals(path)){
		goToRoot();
		return true;
	    }
	    else
		return false;
	}
	
	TreeNode old = m_Current;
	m_Current = new TreeNode(); 
	goToRoot();
	String[] nodes = tokenize(path);
	if(!m_Current.value.equals(nodes[0]))
	    return false;

	for(int i=1; i < nodes.length; i++){
	    int pos = search(m_Current.children, nodes[i]);
	    if(pos == -1){
		m_Current = old;
		return false;