cpath.cs

地理信息 地理信息 地理信息 地理信息

using System;
using System.Collections; 

namespace MainSystem
{
	struct Routine			//一条公交线路
	{
		public short		nFlag;			//0:双向;1:上行;2:下行
		public short		nStationNumber;
		public string		szRoutineName;
		public string[]		szStaionName;
	};

	struct Node
	{
		public short nNodeNumber;
		public short[] nRoutineOrder;
		public short[] nStationOrder;
	};

	struct Station
	{
		public string szStationName;
		public short nRoutineNumber;
		public short[] pnRoutineID;
		public short[] pnOrder;
	};

	struct PathNode				
	{
		public short		nSegNumber;
		public string[]	szRoutineName;
		public string[]	szFromStationName;
		public string[]	szToStationName;
	};

	/// <summary>
	/// Summary description for CPath.
	/// </summary>
	public class CPath
	{
		private int TIMELIMIT = 3;
		private Routine[] _pRoutine;
		private Station[] _pStations;
		private short _nRCount;
		private short _nSCount;

		public CPath()
		{
			_pRoutine = new Routine[1000];
			_pStations = new Station[5000];
		}

		public void Build(CEnvironment env)
		{
			_nRCount = BuildRoutine(_pRoutine,env);
			_nSCount = BuildStationIndex(_pRoutine,_nRCount,_pStations);
		}

		short BuildRoutine(Routine[] pRoutine, CEnvironment env)
		{
			System.Data.DataTable typeTbl = env.m_dataSet.Tables["公交车站路线"];

			System.Data.DataRow[] rowstypes;
			if (env.m_szBusFilter != "")
				rowstypes = typeTbl.Select(env.m_szBusFilter);
			else
				rowstypes = typeTbl.Select();
			
			short nCount = 0;
			short nSCount = 0;

			string rName;
			string sName;
			string sTemp1;
			string sTemp2;
			string[] sNames = new string[350];
			foreach (System.Data.DataRow myRow in rowstypes)
			{
				rName = myRow[0].ToString();
				sTemp1 = myRow[1].ToString();
				sName = myRow[2].ToString();
				sTemp2 = myRow[0].ToString();

				if(nCount ==0)
				{
					pRoutine[nCount] = new Routine();
 
					pRoutine[nCount].szRoutineName=string.Copy (rName);
					if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("上行"))
						pRoutine[nCount].nFlag = 1;
					else if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("下行"))
						pRoutine[nCount].nFlag = 2;
					else 
						pRoutine[nCount].nFlag = 0;
					nCount++;
					nSCount = 0;
					sNames[nSCount] = string.Copy(sName);
					nSCount = 1;
				}
				else
				{
					if(pRoutine[nCount-1].szRoutineName.Equals( rName))
					{
						sNames[nSCount]=string.Copy( sName);
						nSCount++;
					}
					else
					{
						//结束上一站
						pRoutine[nCount-1].nStationNumber = nSCount;
						pRoutine[nCount-1].szStaionName = new string [nSCount];
						for(short i=0;i<nSCount;i++)
							pRoutine[nCount-1].szStaionName[i] = string.Copy (sNames[i]);
			
						pRoutine[nCount] = new Routine();
						if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("上行"))
							pRoutine[nCount].nFlag = 1;
						else if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("下行"))
							pRoutine[nCount].nFlag = 2;
						else 			
							pRoutine[nCount].nFlag = 0;
						pRoutine[nCount].szRoutineName=string.Copy( rName);
						nCount++;
						nSCount = 0;
						sNames[nSCount]=string.Copy (sName);
						nSCount = 1;
					}
				}
			}
			pRoutine[nCount-1].nStationNumber = nSCount;
			pRoutine[nCount-1].szStaionName = new string [nSCount];
			for(short i=0;i<nSCount;i++)
				pRoutine[nCount-1].szStaionName[i]= string.Copy( sNames[i]);
			
			return nCount;
		}

		short BuildStationIndex(Routine[] pAllRoutines,short nSize,Station[] pStations)
		{
			short nCount = 0;
			for(short i=0;i<nSize;i++)
			{
				for(short j=0;j<pAllRoutines[i].nStationNumber;j++)
				{
					short k;

					for( k=0;k<nCount;k++)
					{
						if(pStations[k].szStationName.Equals(pAllRoutines[i].szStaionName[j]))
							break;
					}
					if(k==nCount)
					{
						//添加一个新站
						pStations[k] = new Station();
 
						pStations[k].szStationName=string.Copy(pAllRoutines[i].szStaionName[j]);
						pStations[k].nRoutineNumber=1;
						nCount++;
					}
					else
						pStations[k].nRoutineNumber++;
				}
			}
			//为各个站的信息分配内存
			for(int i=0;i<nCount;i++)
			{
				pStations[i].pnRoutineID = new short[pStations[i].nRoutineNumber];
				pStations[i].pnOrder = new short[pStations[i].nRoutineNumber];
				pStations[i].nRoutineNumber = 0;		//下面重新数
			}

			//重新设置信息
			for(int i=0;i<nSize;i++)
			{
				for(short j=0;j<pAllRoutines[i].nStationNumber;j++)
				{
					short k;

					for(k=0;k<nCount;k++)
					{
						if(pStations[k].szStationName.Equals(pAllRoutines[i].szStaionName[j]))
							break;
					}
					pStations[k].pnRoutineID[pStations[k].nRoutineNumber] = (short)i;
					pStations[k].pnOrder[pStations[k].nRoutineNumber] = j;
					pStations[k].nRoutineNumber++;
				}
			}
			return nCount;
		}

		public ArrayList Search(string sz1, string sz2,ArrayList array)
		{
			Search(_pRoutine,_nRCount,_pStations,_nSCount,sz1,sz2,array);			
			return array;
		}

		short Search(Routine[] pAllRoutines,short nSize,Station[] pStations,short nSCount,string szFrom,string szTo,ArrayList pResPath)
		{
			short nCount = 0;

			short nStationOrder;
			Node nodeCurrent  ;
			Queue queueNodes = new Queue();	//存储需要访问的节点
			short nRoutineCurrent;
			short nStationCurrent;
			short i;
			short nMinChangeTimes=1000;		//第一次找到的换乘次数

			//先得到起点站的线路
			for(i=0;i<nSize;i++)
			{
				nStationOrder = HasStation( pAllRoutines[i],szFrom,0,0);
				if(nStationOrder >= 0)
				{	
					nodeCurrent = new Node();
					nodeCurrent.nNodeNumber = 1;
					nodeCurrent.nRoutineOrder = new short [10];
					nodeCurrent.nStationOrder = new short [10];

					nodeCurrent.nRoutineOrder[0] = i;
					nodeCurrent.nStationOrder[0] = nStationOrder;
					//入队列操作
					queueNodes.Enqueue(nodeCurrent);
				}
			}

			while( !(0 == queueNodes.Count) )
			{
				nodeCurrent = (Node)queueNodes.Dequeue();//.GetFront();

				if((nodeCurrent.nNodeNumber>=TIMELIMIT+1) || (nodeCurrent.nNodeNumber>nMinChangeTimes-1) || (queueNodes.Count >1500000))		//换乘次数限制
					break;
				//得到队列头
				//从队头站点序列的最后一个站开始检索是否能够找到到站
				nRoutineCurrent = nodeCurrent.nRoutineOrder[nodeCurrent.nNodeNumber-1];
				nStationCurrent = nodeCurrent.nStationOrder[nodeCurrent.nNodeNumber-1];
				
				nStationOrder = HasStation( pAllRoutines[nRoutineCurrent], szTo, nStationCurrent, pAllRoutines[nRoutineCurrent].nFlag);
				if(nStationOrder>=0)  //表示找到
				{
					nodeCurrent.nRoutineOrder[nodeCurrent.nNodeNumber] = nRoutineCurrent;
					nodeCurrent.nStationOrder[nodeCurrent.nNodeNumber] = nStationOrder;
					nodeCurrent.nNodeNumber++;

					if(nodeCurrent.nNodeNumber>nMinChangeTimes)
						break;

					PathNode pPathTempNode = new PathNode();
					pPathTempNode.nSegNumber = (short)(nodeCurrent.nNodeNumber-1);
					pPathTempNode.szRoutineName = new string[pPathTempNode.nSegNumber];
					pPathTempNode.szFromStationName = new string[pPathTempNode.nSegNumber];
					pPathTempNode.szToStationName = new string[pPathTempNode.nSegNumber];
					for(i=0;i<pPathTempNode.nSegNumber;i++)
					{
						pPathTempNode.szRoutineName[i] =string.Copy(pAllRoutines[nodeCurrent.nRoutineOrder[i]].szRoutineName);
						pPathTempNode.szFromStationName[i] = string.Copy(pAllRoutines[nodeCurrent.nRoutineOrder[i]].szStaionName[nodeCurrent.nStationOrder[i]]);
						pPathTempNode.szToStationName[i] = string.Copy(pAllRoutines[nodeCurrent.nRoutineOrder[i+1]].szStaionName[nodeCurrent.nStationOrder[i+1]]);
					}
					pResPath.Add(pPathTempNode);

					if(nCount == 0)
						nMinChangeTimes = nodeCurrent.nNodeNumber;
					nCount++;
					if(nCount >20)
						break;
				}
				else  //要将所有可能的路径加入队列
				{
					for(i=(short)(nStationCurrent+1);i<pAllRoutines[nRoutineCurrent].nStationNumber;i++)
					{
						string szTheStation;
						szTheStation= string.Copy(pAllRoutines[nRoutineCurrent].szStaionName[i]);
						
						short j = SearchStation(pStations,nSCount,szTheStation);						
						for(short k=0;k<pStations[j].nRoutineNumber;k++)
						{
							short l;
							for(l=0;l<nodeCurrent.nNodeNumber;l++)
								if(pStations[j].pnRoutineID[k]==nodeCurrent.nRoutineOrder[l])
									break;
							if(l<nodeCurrent.nNodeNumber)		//说明已经处理过该线路
								continue;

							Node nodeTemp = new Node();
							nodeTemp.nNodeNumber = (short)(nodeCurrent.nNodeNumber+1);
							nodeTemp.nRoutineOrder = new short [10];
							nodeTemp.nStationOrder = new short [10];
							for(l=0;l<nodeCurrent.nNodeNumber;l++)
							{
								nodeTemp.nRoutineOrder[l] = nodeCurrent.nRoutineOrder[l];
								nodeTemp.nStationOrder[l] = nodeCurrent.nStationOrder[l];
							}
							nodeTemp.nRoutineOrder[nodeCurrent.nNodeNumber]=pStations[j].pnRoutineID[k];
							nodeTemp.nStationOrder[nodeCurrent.nNodeNumber]=pStations[j].pnOrder[k];
							queueNodes.Enqueue(nodeTemp);
						}
					}
					if( pAllRoutines[nRoutineCurrent].nFlag==0 )		//双向线路，需要两个方向查询
					{
						for(i=(short)(nStationCurrent-1);i>=0;i--)
						{
							string szTheStation;
							szTheStation=string.Copy(pAllRoutines[nRoutineCurrent].szStaionName[i]);

							short j = SearchStation(pStations,nSCount,szTheStation);
							for(short k=0;k<pStations[j].nRoutineNumber;k++)
							{
								short l;
								for(l=0;l<nodeCurrent.nNodeNumber;l++)
									if(pStations[j].pnRoutineID[k]==nodeCurrent.nRoutineOrder[l])
										break;
								if(l<nodeCurrent.nNodeNumber)		//说明已经处理过该线路
									continue;
								Node nodeTemp = new Node();
								nodeTemp.nNodeNumber = (short)(nodeCurrent.nNodeNumber+1);
								nodeTemp.nRoutineOrder = new short [10];
								nodeTemp.nStationOrder = new short [10];
								for(l=0;l<nodeCurrent.nNodeNumber;l++)
								{
									nodeTemp.nRoutineOrder[l] = nodeCurrent.nRoutineOrder[l];
									nodeTemp.nStationOrder[l] = nodeCurrent.nStationOrder[l];
								}
								nodeTemp.nRoutineOrder[nodeCurrent.nNodeNumber]=pStations[j].pnRoutineID[k];
								nodeTemp.nStationOrder[nodeCurrent.nNodeNumber]=pStations[j].pnOrder[k];
								queueNodes.Enqueue(nodeTemp);
							}
						}
					}
				}
			}
			return nCount;
		}

		//根据站名得到它是一条公交线路上第几站,基0,-1表示没有
		//nSearchFrom为开始搜寻的站序号
		//nFlag标记向那个方向搜索,0表示双方向,1表示单向
		short HasStation(Routine theRoutine,string szStation,short nSearchFrom,short nFlag)
		{
			if( nFlag!=0 )
			{
				for(short i=nSearchFrom;i<theRoutine.nStationNumber;i++)
					if(theRoutine.szStaionName[i].Equals(szStation))
						return i;
			}
			else if( nFlag==0 )
			{
				for(short i=nSearchFrom;i<theRoutine.nStationNumber;i++)		//正向搜索
					if(theRoutine.szStaionName[i].Equals(szStation))
						return i;
				for(short i=nSearchFrom;i>=0;i--)								//反向搜索
					if(theRoutine.szStaionName[i].Equals(szStation))
						return i;
			}
			return -1;
		}

		short SearchStation(Station[] pStations,short nSCount,string theName)
		{
			short j;
			//用于统计时间
			for(j=0;j<nSCount;j++)
			{
				if(pStations[j].szStationName.Equals(theName))
				{
					return j;
				}
			}	
			return j;
		}

		void FreeStationIndex(Station[] pStations,short nSize)
		{
			for(short i=0;i<nSize;i++)
			{
				pStations[i].pnRoutineID = null;
				pStations[i].pnOrder = null;
			}
		}

		void FreeRoutineInfo(Routine[] pAllRoutines,short nSize)
		{
			for(short i=0;i<nSize;i++)
			{
				pAllRoutines[i].szStaionName = null;
			}
		}



	}
}