query.java

一个专门为手机写的程序

/***********************************************************************
 *
 *
 *		软件：公交路线选择软件
 *		作者：李蛟
 *		学校：浙江工业大学计本
 *		邮箱：[e-mail]
 *
 *		说明：本软件是用于查询市公交路线选择的软件。
 *			  本软件在对相应文件进行修改后可用于任何类似各个城市的公交路线等的查询。
 *			  除了用于商业需经得本人同意外，你可以学习使用甚至修改。
 *			  第一次发布，难免很多的错误和不足，欢迎有兴趣的朋友批评指正，发现问
 *			  题请与本人联系，咱们可以交流交流！
 *
 *
 ***********************************************************************/
 
 
/***********************************************************************
 *
 *此文件对路线选择的进行全权处理
 *包括读入数据（文件），生成数据结构，提供函数用于搜索
 *并有一些其他操作，保障安全
 *
 ***********************************************************************/
//package classes;
//import query.*;
//import query.StopFile;
//import query.BusFile;
//import query.GoodLine;
import java.io.*;
import javax.microedition.midlet.*;
import javax.microedition.lcdui.*;

public class Query
{
	public Query()
	{
		m_lines=new GoodLine[m_maxline];
		m_line=new GoodLine();
		for(int i=0;i<m_maxline;i++)m_lines[i]=new GoodLine();
		if(m_line==null)
		{
			System.out.println("not enough memory!");
		}
	}

	//设置或获得 路径的深度即最多可乘的车辆数
	public void setDepth(int i){if(i<=GoodLine.maxnum)m_routeDepth=i;}
	public int getDepth(){return m_routeDepth;}
	//reset all the values of the object of this class
	private void reset()
	{
		m_lineNum=0;
		m_line.reset();
		for(int i=0; i<m_lines.length; ++i)
			m_lines[i].reset();
		m_curRouteDepth=0;
	}

	//设置或获得 起始或终点 站点
	public short getEndStop(){return m_endStop;}
	public short getStartStop(){return m_startStop;}
	public void setEndStop(short pid){m_endStop=pid;}
	public void setEndStop(int pid){m_endStop=(short)pid;}
	public void setEndStop(String name)
	{
		m_endStop=(short)getStopIDFromName(name);
	}
	public void setStartStop(short pid){m_startStop=pid;}
	public void setStartStop(int pid){m_startStop=(short)pid;}
	public void setStartStop(String name)
	{
		m_startStop=(short)getStopIDFromName(name);
	//	if(m_startStop>=0) m_startStop%=m_stopNameLen;
		
	}
	public int getStopIDFromName(String name)
	{
		if(name==null || name.length()==0) return -1;
		return m_stopName.indexOf(name)/m_stopNameLen;
	}
	
	public int getBusIdFromName(String name)
	{
		if(name==null || name.length()==0) return -1;
		return m_busName.indexOf(name)/m_busNameLen;	
	}
	public int getLineNum() {return m_lineNum;}	//返回路径的数量
	public void setDepth(short depth){m_routeDepth=depth>GoodLine.maxnum?GoodLine.maxnum:depth;}
	//获得下标为i的可行路径
	public final GoodLine getGoodLine(int i){if(i<m_lineNum) return (m_lines[i]);else return null;}
	
	
	public short getStopNum(){return m_stopNum;}
	public short getBusNum(){return m_busNum;}
	//获得名称的长度
	public short getStopNameLen(){return m_stopNameLen;}
	public short getBusNameLen(){return m_busNameLen;}
	//获得第 index 个名称
	public final String getStopName(int index)
	{
		if(index<0 || index>=m_stopNum) return null;
		return m_stopName.substring(index*m_stopNameLen, (index+1)*m_stopNameLen);
	}
	public final String getBusName(int index)
	{
		if(index<0 || index>=m_busNum) return null;
		return m_busName.substring(index*m_busNameLen, (index+1)*m_busNameLen);
	}
	
	//public short getStopNameLen(){return m_stopNameLen;}
	//public short getStopNameLen(){return m_stopNameLen;}
	
	
	
	private boolean createNode()
	{
		if(!(m_busList.readFile()) || !(m_stopList.readFile()))
		{
			m_stopList.reset();
			m_busList.reset();
			return false;
		}
		return true;
	}
	
	public boolean createStopAndBus()
	{	
		if(!m_nodeCreaded)
		{
			m_nodeCreaded=true;
			return createNode();
		}
		return true;
	}
/*************************站点名的文件结构****************
 *short int busnum	//站点数量
 *short int namelen	//名字的统一长度
 *loop{
 *	short int namelen;
 *	byte name[];	//Unicode
 *}
*************************公交车名的文件结构****************
 *short int busnum	//公交车数量
 *short int namelen	//名字的统一长度
 *loop{
 *	byte name[];	//Unicode
 *}
 * *******************************************************/	
 	public boolean readName()
	{	
		if(m_stopName!=null) return true;
		try{
			//read stop's name
			DataInputStream	stopName=new DataInputStream(getClass().getResourceAsStream("stopname.db"));
			//DataInputStream	stopName=new DataInputStream(new FileInputStream("stopname.db"));
			m_stopNum=stopName.readShort();
			m_stopNameLen=stopName.readShort();
			
			char [] stopNameChars=new char[m_stopNum*m_stopNameLen];
			//stopName.read(m_stopName, 0, m_stopNum*m_stopNameLen);
			for(int i=0; i<m_stopNum*m_stopNameLen; ++i)
				stopNameChars[i]=stopName.readChar();
			m_stopName=new String(stopNameChars);
			stopNameChars=null;
			stopName.close();	
			
			//read bus's name
			DataInputStream	busName=new DataInputStream(getClass().getResourceAsStream("busname.db"));
			//DataInputStream	busName=new DataInputStream(new FileInputStream("busname.db"));
			m_busNum=busName.readShort();
			m_busNameLen=busName.readShort();
			
			char []busNameChars=new char[m_busNum*m_busNameLen];
			for(int i=0; i<m_busNum*m_busNameLen; ++i)
				busNameChars[i]=busName.readChar();
			m_busName=new String(busNameChars);
			busNameChars=null;
			busName.close();
		}catch(Exception e)
		{
			//System.out.println("读站点名和公交车名时出错!!!!!!!!!!!!!!!!!!!!!!!!!!");
			return false;	
		}
		return true;		
	}
	
	//查找可行路径
	public boolean isFinded()
	{
		if(m_startStop==-1 || m_endStop==-1 || m_startStop == m_endStop)
		{
			return false;
		}
		
		reset();
		startFind(m_startStop);
		if(m_lineNum==0) 
		{
			System.out.println("no way found!");
			return false;
		}
		else return true;
	}

//真正地开始搜索
	private	void startFind(short stop)
	{
		if(m_line.getBusNum() >= m_routeDepth) return;
		short curBus=0, curStop=0;
		
		for(int busOnStop=0; busOnStop<m_stopList.getBusNumOnStop(stop); ++busOnStop)
		{
			curBus=m_stopList.getBusIDOnStop(stop,busOnStop);
			
			if(m_line.inBuses(curBus)) continue;
			m_line.addBus(curBus);
	
			for(int stopOnBus=0; stopOnBus<m_busList.getStopNumOnBus(curBus); ++stopOnBus)
			{
				curStop=m_busList.getStopIDOnBus(curBus,stopOnBus);
				
				if(m_line.inPorts(curStop) ||curStop==m_startStop) continue;
				m_line.addPort(curStop);
				
				//too long or too length
				if(m_lineNum == m_maxline && m_routeDepth <= m_line.getBusNum())
				{
					m_line.deletePort();
					m_line.deleteBus();
					return;
				}
				//exist a goodline
				if(m_line.topPort()==m_endStop)
				{
					//add a new line is still room to store
					if(m_lineNum<m_maxline) 
					{
						m_lines[m_lineNum++].evaluate(m_line);
						if(m_curRouteDepth < m_line.getBusNum()) //刷新当前的最大深度
							m_curRouteDepth = m_line.getBusNum();
					}
					else if(m_line.getBusNum() >=m_curRouteDepth){}//满了，且不是更好的则舍弃
					else//替换掉存在的比目前路线更长的路线
					{
						int i=0,rnum=0;//找到那条差的
						for(int j=0;j<m_lineNum;j++) 
						{
							if(rnum<m_lines[j].getBusNum())
							{
								rnum=m_lines[j].getBusNum() ;
								i=j;
							}
						}
						m_lines[i].evaluate(m_line);
						m_curRouteDepth=rnum;
					}
					m_line.deletePort();
					break;
				}
				startFind(curStop);
				m_line.deletePort();
			}
			m_line.deleteBus();
		}
		return;
	}

	//搜索站点名字
	public void searchStopName(final String name, List stopName)
	{
		if(stopName==null) return;
		if(m_stopName==null) readName();
		createStopAndBus();
		//先清空
		int num=stopName.size();
		for(int i=0; i<num; ++i) stopName.delete(0);
		int hasRun=0;
		for(num=m_stopName.indexOf(name, 0) ; num>-1 && num<m_stopName.length(); hasRun++)
		{
			//System.out.println(num);
			if(num==-1)break;
			if(hasRun!=0 && num<=0) break;
			stopName.append(getStopName(num/m_stopNameLen),null);
			num=(num/m_stopNameLen)*m_stopNameLen+m_stopNameLen;
			num=m_stopName.indexOf(name, num);
		}	
	}
	
	//搜索车次名字
	public void searchBusName(final String name, List busName)
	{
		if(busName==null) return;
		if(m_busName==null) readName();
		createStopAndBus();
		//先清空
		int num=busName.size();
		for(int i=0; i<num; ++i) busName.delete(0);
		int hasRun=0;
		for(num=m_busName.indexOf(name, 0) ; num>-1 && num<m_busName.length(); hasRun++)
		{
			//System.out.println(num);
			if(num==-1)break;
			if(hasRun!=0 && num<=0) break;
			busName.append(getBusName(num/m_busNameLen),null);
			num=(num/m_busNameLen)*m_busNameLen+m_busNameLen;
			num=m_busName.indexOf(name, num);
		}	
	}
/**************ATTRIBUTE*****************/
	private	short m_startStop=-1;//起点站点的ID号
	private	short m_endStop=-1;	//终点站点的ID号

	//站点链表及路线链表
	public	StopFile m_stopList=new StopFile();
	public	BusFile m_busList=new BusFile();
	
	//名称
	private short m_stopNum=0, m_stopNameLen;
	private short m_busNum=0, m_busNameLen;
	private String m_stopName=null;
	private String m_busName=null;
	
	public	static final int m_maxline=20;
//用于存放所得到的路径
	private	GoodLine[] m_lines=null;
	private	GoodLine m_line=null;//current line for findIT()函数
	private	int m_lineNum=0;//生成路线的当前数量
	private	int m_routeDepth=2;//路径的深度
	private int m_curRouteDepth=0;//当前可行路径的最大深度
	
	private boolean m_nodeCreaded=false;//有没有生成结构
/*	public static void main(String[] args)
	{
		Query finder=new Query();
		finder.reset();
		finder.setDepth(1);
		
		finder.createStopAndBus();
///////////////		
		finder.m_stopList.m_stopNum=3;
		finder.m_stopList.m_busNumPerStop=new short[3];
		finder.m_stopList.m_busesPerStop=new short[3][];
		for(int i=0; i<3; ++i)
		{
			finder.m_stopList.m_busNumPerStop[i]=2;
			finder.m_stopList.m_busesPerStop[i]=new short[2];
		}
		finder.m_stopList.m_busesPerStop[0][0]=0;
		finder.m_stopList.m_busesPerStop[0][1]=2;
		finder.m_stopList.m_busesPerStop[1][0]=0;
		finder.m_stopList.m_busesPerStop[1][1]=1;
		finder.m_stopList.m_busesPerStop[2][0]=1;
		finder.m_stopList.m_busesPerStop[2][1]=2;
		
		
		finder.m_busList.m_busNum=3;
		finder.m_busList.m_stopNumPerBus=new short[3];
		finder.m_busList.m_stopsPerBus=new short[3][];
		for(int i=0; i<3; ++i)
		{
			finder.m_busList.m_stopNumPerBus[i]=2;
			finder.m_busList.m_stopsPerBus[i]=new short[2];
		}
		finder.m_busList.m_stopsPerBus[0][0]=0;
		finder.m_busList.m_stopsPerBus[0][1]=1;
		finder.m_busList.m_stopsPerBus[1][0]=2;
		finder.m_busList.m_stopsPerBus[1][1]=1;
		finder.m_busList.m_stopsPerBus[2][0]=0;
		finder.m_busList.m_stopsPerBus[2][1]=2;
//////////////		
		finder.setStartPort(0);
		finder.setEndPort(1);
		
		
		if(!finder.isFinded()) 
		{
			System.out.print("No way finded!");
		}
		else
		{
			System.out.print(finder.m_lineNum);
			System.out.print(" ways for you to choose!\n\n");
			for(int i=0;i<finder.getLineNum();i++)
			{
				System.out.print('[');
				System.out.print(i+1);
				System.out.print("] ");
				
				System.out.print("from port ");
				System.out.print(finder.getStartPort());
				for(int j=0;j<finder.getGoodLine(i).getBusNum() ;j++)
				{
					System.out.print(" by(");
					System.out.print(finder.getGoodLine(i).buses[j]);
					System.out.print(") to port ");
					System.out.print(finder.getGoodLine(i).stops[j]);
				}
				System.out.print("\n");
			}
			System.out.print("\n");
			System.out.flush();
		}
		return;
	}

	public void print()
	{
		System.out.print(this.m_lineNum);
		System.out.print(" ways for you to choose!\n\n");
		for(int i=0;i<this.getLineNum();i++)
		{
			System.out.print('[');
			System.out.print(i+1);
			System.out.print("] ");
			
			System.out.print("from port ");
			System.out.print(this.getStartStop());
			for(int j=0;j<this.getGoodLine(i).getBusNum() ;j++)
			{
				System.out.print(" by(");
				System.out.print(this.getGoodLine(i).buses[j]);
				System.out.print(") to port ");
				System.out.print(this.getGoodLine(i).stops[j]);
			}
			System.out.print("\n");
		}
		System.out.print("\n");
		System.out.flush();
	}*/
}