xyobjarray.java

Last week I posted an article on a simple C++ template class, XYDataArray, I used in my system devel

import java.util.*;

public class XYObjArray
{
	int m_nSize;
	int m_nGrowBy;
	int m_nSort;
	Object[] m_pObj;
	public static int nSearchThreshold = 8;
	public static int nSortThreshold = 8;

	static Random randomGen = new Random(new Date().getTime());
	static public final int GetRandomInt(int nMax)
	{
		synchronized(randomGen)
		{
			return randomGen.nextInt(nMax);
		}
	}

	public XYObjArray()
	{
		m_nSize = 0;
		m_nGrowBy = 64;
		m_nSort = 0;
		m_pObj = null;
	}
	public XYObjArray(Object[] pObj, int nGrowBy)
	{
		m_nSize = 0;
		m_nGrowBy = 64;
		m_nSort = 0;
		m_pObj = null;
		SetSize(pObj.length,nGrowBy);
		for(int i=0;i<m_nSize;i++) m_pObj[i] = pObj[i];
	}
	public final synchronized void SetSort(int nSort)
	{
		if(nSort!=m_nSort) Sort(nSort);
	}
	public final synchronized int GetSize()
	{
		return m_nSize;
	}
	public final synchronized void SetSize(int nSize, int nGrowBy)
	{
		if(nSize<0||nGrowBy<=0)
		{
			return;
		}
		if(nSize>m_nSize) m_nSort = 0;
		m_nGrowBy = nGrowBy;
		int nStoreSize = m_pObj==null?0:m_pObj.length;
		if(nSize>=(nStoreSize-m_nGrowBy)&&nSize<=nStoreSize)
		{
			m_nSize = nSize;
			return;
		}
		int nMin = nSize>m_nSize?m_nSize:nSize;
		m_nSize = nSize;	
		Object[] pObj = new Object[(m_nSize/m_nGrowBy+1)*m_nGrowBy];
		if(nMin>0)
		{
			System.arraycopy(m_pObj,0,pObj,0,nMin);
		}
		m_pObj = pObj;
	}
	public final synchronized Object[] GetDataPtr()
	{
		return m_pObj;
	}
	public final synchronized int Add(Object obj)
	{
		int nSort = m_nSort;
		int nIndex = Locate(obj);
		Insert(nIndex, obj);
		m_nSort = nSort;
		return nIndex;
	}
	public final synchronized int Locate(Object obj)
	{
		int nIndex = -1;
		if(m_nSort==0||m_nSize==0) nIndex = m_nSize;
		else
		{
			Comparable ref = (Comparable)obj;
			int nMin, nMax, nMid;
			nMin = 0;
			nMax = m_nSize-1;
			while(nMax-nMin>1)
			{
				nMid = (nMax+nMin)/2;
				if(m_nSort>0)
				{
					if(ref.compareTo(m_pObj[nMid])<0) nMax = nMid;
					else nMin = nMid;
				}
				else
				{
					if(ref.compareTo(m_pObj[nMid])>0) nMax = nMid;
					else nMin = nMid;
				}
			}
			if(m_nSort>0)
			{
				if(ref.compareTo(m_pObj[nMin])<0) nIndex = nMin;
				else if(ref.compareTo(m_pObj[nMax])<0) nIndex = nMax;
				else nIndex = nMax+1;
			}
			else
			{
				if(ref.compareTo(m_pObj[nMin])>0) nIndex = nMin;
				else if(ref.compareTo(m_pObj[nMax])>0) nIndex = nMax;
				else nIndex = nMax+1;
			}
		}
		return nIndex;
	}
	public final synchronized int Find(Object obj)
	{
		if(m_pObj==null) return -1;
		Comparable ref = (Comparable)obj;
		if(m_nSort==0||m_nSize<nSearchThreshold)
		{
			for(int i=0;i<m_nSize;i++)
			{
				if(ref.compareTo(m_pObj[i])==0) return i;
			}
			return -1;
		}
		if(ref.compareTo(m_pObj[0])==0) return 0;
		else if(ref.compareTo(m_pObj[m_nSize-1])==0) return m_nSize-1;
		int nMid, nMin = 0, nMax = m_nSize-1;
		while(nMax-nMin>1)
		{
			nMid = (nMax+nMin)/2;
			if(ref.compareTo(m_pObj[nMid])==0) return nMid;
			if(m_nSort>0)
			{
				if(ref.compareTo(m_pObj[nMid])>0) nMin = nMid;
				else nMax = nMid;
			}
			else
			{
				if(ref.compareTo(m_pObj[nMid])<0) nMin = nMid;
				else nMax = nMid;
			}
		}
		return -1;
	}
	public final synchronized int Insert(int nIndex, Object obj)
	{
		if(nIndex<0||nIndex>m_nSize) 
		{
			return -1;
		}
		m_nSort = 0;
		if(nIndex==m_nSize&&m_pObj!=null&&nIndex<m_pObj.length)
		{
			m_pObj[nIndex] = obj;
		}
		else
		{
			int nStoreSize = m_pObj==null?m_nGrowBy:(m_nSize<m_pObj.length?m_pObj.length:(m_nGrowBy+m_pObj.length));
			Object[] pObj = new Object[nStoreSize];
			pObj[nIndex] = obj;
			if(m_pObj!=null)
			{
				if(nIndex>0) System.arraycopy(m_pObj,0,pObj,0,nIndex);
				if(nIndex<m_nSize) System.arraycopy(m_pObj,nIndex,pObj,nIndex+1,m_nSize-nIndex);
			}
			m_pObj = pObj;
		}
		m_nSize++;
		return nIndex;
	}
	public final synchronized int Remove(int nIndex)
	{
		if(nIndex<0||nIndex>=m_nSize)
		{
			return -1;
		}
		int nSegmentSize = m_nSize-nIndex-1;
		if(nSegmentSize>0)
		{
			Object[] pObj = new Object[nSegmentSize];
			System.arraycopy(m_pObj,nIndex+1,pObj,0,nSegmentSize);
			System.arraycopy(pObj,0,m_pObj,nIndex,nSegmentSize);
		}
		m_nSize--;
		return m_nSize;
	}
	public final synchronized Object GetAt(int nIndex)
	{
		if(nIndex<0||nIndex>=m_nSize)
		{
			return null;
		}
		return m_pObj[nIndex];
	}
	public final synchronized int SetAt(int nIndex, Object obj)
	{
		if(nIndex<0||nIndex>=m_nSize)
		{
			return -1;
		}
		m_nSort = 0;
		m_pObj[nIndex] = obj;
		return nIndex;
	}
	public final synchronized void Push(Object obj)
	{
		Insert(m_nSize,obj);
	}
	public final synchronized Object Pop()
	{
		if(m_nSize==0) return null;
		m_nSize--;
		return m_pObj[m_nSize];
	}
	public final synchronized void Sort(int nSort)
	{
		if(m_nSize==0)
		{
			m_nSort = nSort;
			return;
		}
		else if(nSort>0&&m_nSort>0||nSort<0&&m_nSort<0||nSort==0)
		{
			return;
		}
		Object[] pObj = new Object[m_pObj.length];
		int[] pIndex = new int[m_nSize];
		for(int i=0;i<m_nSize;i++) pIndex[i] = i;	
		SortIndex(pIndex, nSort);
		for(int j=0;j<m_nSize;j++) pObj[j] = m_pObj[pIndex[j]];
		m_pObj = pObj;
		m_nSort = nSort;
	}
	public final synchronized void SortIndex(int[] pIndex, int nSort)
	{
		if(m_nSize==0||nSort==0) 
		{
			return;
		}
		
		int i,j,k;
		int nMin, nMax;
		int nTemp1, nTemp2, nSwap;
		XYObjArray theStack = new XYObjArray();	
		int[] pRefIndex = new int[m_nSize];
		for(i=0;i<m_nSize;i++) pRefIndex[i] = i;
		
		theStack.Push(new Integer(0));
		theStack.Push(new Integer(m_nSize-1));

		while(theStack.GetSize()>0)
		{
			nMax = ((Integer)theStack.Pop()).intValue();
			nMin = ((Integer)theStack.Pop()).intValue();
			if(nMax-nMin<nSortThreshold)
			{
				for(i=nMin+1;i<=nMax;i++)
				{
					nTemp1 = pIndex[i];
					nTemp2 = pRefIndex[i];	
					j = i-1;
					Comparable ref = (Comparable)m_pObj[nTemp1];
					if(nSort>0)
					{
						while(j>=nMin&&(ref.compareTo(m_pObj[pIndex[j]])<0||pRefIndex[j]>nTemp2&&ref.compareTo(m_pObj[pIndex[j]])==0)) j--;
					}
					else
					{
						while(j>=nMin&&(ref.compareTo(m_pObj[pIndex[j]])>0||pRefIndex[j]>nTemp2&&ref.compareTo(m_pObj[pIndex[j]])==0)) j--;
					}
					if(j+1<i)
					{
						for(k=i;k>j+1;k--)
						{
							pIndex[k] = pIndex[k-1];
							pRefIndex[k] = pRefIndex[k-1];
						}
						pIndex[j+1] = nTemp1;
						pRefIndex[j+1] = nTemp2;
					}
				}
			}
			else
			{
				i = nMin+(GetRandomInt(0x7FFFFFFF)%(nMax-nMin))+1; 
				nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[i]; pIndex[i] = nSwap;
				nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[i]; pRefIndex[i] = nSwap;
				Comparable ref = (Comparable)m_pObj[pIndex[nMin]];
				if(nSort>0)
				{
					if(ref.compareTo(m_pObj[pIndex[nMin+1]])<0||pRefIndex[nMin+1]>pRefIndex[nMin]&&ref.compareTo(m_pObj[pIndex[nMin+1]])==0) 
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[nMin+1]; pIndex[nMin+1] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[nMin+1]; pRefIndex[nMin+1] = nSwap;
						ref = (Comparable)m_pObj[pIndex[nMin]];
					}
					if(ref.compareTo(m_pObj[pIndex[nMax]])>0||pRefIndex[nMin]>pRefIndex[nMax]&&ref.compareTo(m_pObj[pIndex[nMax]])==0) 
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[nMax]; pIndex[nMax] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[nMax]; pRefIndex[nMax] = nSwap;
						ref = (Comparable)m_pObj[pIndex[nMin]];
					}
					if(ref.compareTo(m_pObj[pIndex[nMin+1]])<0||pRefIndex[nMin+1]>pRefIndex[nMin]&&ref.compareTo(m_pObj[pIndex[nMin+1]])==0) 
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[nMin+1]; pIndex[nMin+1] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[nMin+1]; pRefIndex[nMin+1] = nSwap;
						ref = (Comparable)m_pObj[pIndex[nMin]];
					}
				}
				else
				{
					if(ref.compareTo(m_pObj[pIndex[nMin+1]])>0||pRefIndex[nMin+1]>pRefIndex[nMin]&&ref.compareTo(m_pObj[pIndex[nMin+1]])==0) 
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[nMin+1]; pIndex[nMin+1] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[nMin+1]; pRefIndex[nMin+1] = nSwap;
						ref = (Comparable)m_pObj[pIndex[nMin]];
					}
					if(ref.compareTo(m_pObj[pIndex[nMax]])<0||pRefIndex[nMin]>pRefIndex[nMax]&&ref.compareTo(m_pObj[pIndex[nMax]])==0) 
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[nMax]; pIndex[nMax] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[nMax]; pRefIndex[nMax] = nSwap;
						ref = (Comparable)m_pObj[pIndex[nMin]];
					}
					if(ref.compareTo(m_pObj[pIndex[nMin+1]])>0||pRefIndex[nMin+1]>pRefIndex[nMin]&&ref.compareTo(m_pObj[pIndex[nMin+1]])==0) 
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[nMin+1]; pIndex[nMin+1] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[nMin+1]; pRefIndex[nMin+1] = nSwap;
						ref = (Comparable)m_pObj[pIndex[nMin]];
					}
				}
				i = nMin+1;
				j = nMax;	
				while(true)
				{
					if(nSort>0)
					{
						while
						(
							ref.compareTo(m_pObj[pIndex[i]])>0||
							pRefIndex[i]<pRefIndex[nMin]&&ref.compareTo(m_pObj[pIndex[i]])==0
						) i++;
						while
						(
							ref.compareTo(m_pObj[pIndex[j]])<0||
							pRefIndex[nMin]<pRefIndex[j]&&ref.compareTo(m_pObj[pIndex[j]])==0
						) j--;
					}
					else
					{
						while
						(
							ref.compareTo(m_pObj[pIndex[i]])<0||
							pRefIndex[i]<pRefIndex[nMin]&&ref.compareTo(m_pObj[pIndex[i]])==0
						) i++;
						while
						(
							ref.compareTo(m_pObj[pIndex[j]])>0||
							pRefIndex[nMin]<pRefIndex[j]&&ref.compareTo(m_pObj[pIndex[j]])==0
						) j--;
					}
					if(i>j)
					{
						nSwap = pIndex[nMin]; pIndex[nMin] = pIndex[j]; pIndex[j] = nSwap;
						nSwap = pRefIndex[nMin]; pRefIndex[nMin] = pRefIndex[j]; pRefIndex[j] = nSwap;
						break;
					}
					nSwap = pIndex[i]; pIndex[i] = pIndex[j]; pIndex[j] = nSwap;
					nSwap = pRefIndex[i]; pRefIndex[i] = pRefIndex[j]; pRefIndex[j] = nSwap;
				}
				if(nMin<j-1)
				{
					theStack.Add(new Integer(nMin));
					theStack.Add(new Integer(j-1));
				}
				if(j+1<nMax)
				{
					theStack.Add(new Integer(j+1));
					theStack.Add(new Integer(nMax));
				}
			}
		}
	}
}