📄 xyobjarray.htm
字号:
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Author" content="Xiangyang Liu">
<meta name="GENERATOR" content="Mozilla/4.75 [en] (WinNT; U) [Netscape]">
<title>XYDataArray: A Template For General Data Arrays</title>
</head>
<body>
<br>Last week I posted an article on a simple <b><font color="#660000">C++</font></b>
template class <a href="http://www.codeproject.com/useritems/dataarray.asp">XYDataArray</a>
I used in <a href="http://hometown.aol.com/xiangyangl/">my system development
tool</a>. The main purpose of this template class is to store and
sort general data types. I need to implement the same thing in <b><font color="#660000">java</font></b>,
since the tool I developed has a compatible <b><font color="#660000">java</font></b>
version. I checked the <b><font color="#660000">Java SDK</font></b>
documentation before writing my own code, and found that almost everything
I need is already there, like the <b><font color="#660000">C++</font></b>
case.
<p>For example, the <b><font color="#660000">java.util.Vector</font></b>
class is the kind of array I want, it can dynamically change its size.
There is also various implementations of <b><font color="#006600">stable
sort algorithms</font></b> in the <b><font color="#660000">java.util.Arrays</font></b>
class. For example, the following line of code will sort a <b><font color="#660000">java</font></b>
<i><font color="#660000">Object</font></i> array in ascending order.
<p><i><font color="#006600"> Arrays.sort(myArray);</font></i>
<p>And the sort is guaranteed to be <b><font color="#006600">stable</font></b>
(equal elements will not be reordered). The objects in <i><font color="#006600">myArray</font></i>
has to be mutually comparable, of course (implementing the <b><font color="#660000">Comparable</font></b>
interface). There are other forms of the <b><font color="#660000">Arrays.sort</font></b>
method that can be used to sort primitive data types (int, double, etc.)
and even subarrays. What about sorting in descending order (note
that sorting in ascending order and then reversing the orders of all elements
makes it <b><font color="#006600">unstable</font></b>)? In that case,
you have to implement a <b><font color="#660000">Comparator</font></b>
class and pass an object of this class along with the data array into another
<b><font color="#660000">Arrays.sort</font></b> method. This is like
passing a function pointer to a generic sort function in <b><font color="#660000">C++</font></b>.
It is not exactly what I want. For example, I don't want to implement
a different <b><font color="#660000">Comparator</font></b> class for each
different way I want to sort my data. What I really need is sorting
the indices instead of the data array itself. For example, I want
to get the index of the <i><font color="#006600">10th</font></i> largest
element or the index of the <i><font color="#006600">6th</font></i> smallest
element in my array. The <b><font color="#006600">SortIndex</font></b>
method in my <b><font color="#660000">C++</font></b> code will give me
exactly what I need. The best part about the <b><font color="#006600">SortIndex</font></b>
method is, I can use it repeatedly to do multi-column sorting on tabulated
data (each column is in a separate array) without rearranging the data
elements! So I converted my <b><font color="#660000">C++</font></b>
template class <a href="http://www.codeproject.com/useritems/dataarray.asp">XYDataArray</a>
into a <b><font color="#660000">java</font></b> class <b><font color="#006600">XYObjArray</font></b>.
<p>The <b><font color="#006600">XYObjArray</font></b> class is almost identical
to its <b><font color="#660000">C++</font></b> counterpart except that
there is no template or operator overloading in <b><font color="#660000">java</font></b>.
In order to use the sort feature, objects in this class has to be mutually
comparable (implementing the <b><font color="#660000">Comparable</font></b>
interface). I have included source code and a simple test program.
There is no restriction on using the source code. The test program
creates an array with randomly generated data and then sorts the array
(and also verifies that the sort is done correctly). Here is the
command line that runs the test program, assuming you already compiled
the code and set the correct <b><font color="#660000">ClassPath.</font></b>
<p> <i><font color="#006600">java ArrayTest</font></i>
<p>Here are the descriptions of the methods in <b><font color="#006600">XYObjArray</font></b>.
<p><b><i><font color="#FF0000">public XYObjArray( );</font></i></b>
<br>This method constructs an empty array.
<p><b><i><font color="#FF0000">public XYObjArray(Object[ ] pObj, int nGrowBy);</font></i></b>
<br>This method constructs an array with given <i><font color="#660000">Object</font></i>
array <i><font color="#006600">pObj</font></i>. The <i><font color="#006600">nGrowBy</font></i>
parameter specifies how the array's internal buffer grows or shrinks.
The<i><font color="#006600"> nGrowBy </font></i>= <i><font color="#006600">64</font></i>
means that the internal buffer will grow in multiples of <i><font color="#006600">64</font></i>
elements.<b><i><font color="#FF0000"></font></i></b>
<p><b><i><font color="#FF0000">public final synchronized int Find(Object
obj);</font></i></b>
<br>This method returns the index of <i><font color="#006600">obj</font></i>
within the array. The return value is <i><font color="#006600">-1</font></i>
if <i><font color="#006600">obj</font></i> is not found. If the array
is already sorted, this method will use binary search instead of linear
search.
<p><b><i><font color="#FF0000">public final synchronized int Locate(Object
obj);</font></i></b>
<br>This method returns the position at which to insert a new element <i><font color="#006600">obj</font></i>.
If the array is already sorted, inserting at the returned position will
keep the array sorted.
<p><b><i><font color="#FF0000">public final synchronized void SetSize(int
nSize, int nGrowBy);</font></i></b>
<br>This method changes the size of the array. If the new size is
bigger than the original size, the array will be chopped. Otherwise,
<b><i><font color="#006600">null</font></i></b> elements will be added
if necessary. In any case, the original elements, except the ones
being chopped off, will be preserved.
<p><b><i><font color="#FF0000">public final synchronized int GetSize( );</font></i></b>
<br>This method returns the current size of the array.
<p><b><i><font color="#FF0000">public final synchronized Object[ ] GetDataPtr(
);</font></i></b>
<br>This method returns the internal data buffer.
<p><b><i><font color="#FF0000">public final synchronized Object GetAt(int
nIndex);</font></i></b>
<br>This method returns the element at the position
<i><font color="#006600">nIndex</font></i>.<b><i><font color="#FF0000"></font></i></b>
<p><b><i><font color="#FF0000">public final synchronized int Add(Object
obj);</font></i></b>
<br>This method adds a new element <i><font color="#006600">obj</font></i>
to the array. If the array is already sorted, adding the new element
will keep the array sorted. Otherwise, the new element will be appended
to the end of the array. The return value is the position of the
newly added element.
<p><b><i><font color="#FF0000">public final synchronized int Insert(int
nIndex, Object obj);</font></i></b>
<br>This method inserts a new element<font color="#006600"> <i>obj</i></font>
to the array at position <i><font color="#006600">nIndex</font></i>. The
return value is <i><font color="#006600">-1</font></i> if <i><font color="#006600">nIndex</font></i>
is invalid (out of the range between <i><font color="#006600">0</font></i>
and the size of the array). Otherwise, it returns <i><font color="#006600">nIndex</font></i>.
<p><b><i><font color="#FF0000">public final synchronized int Remove(int
nIndex);</font></i></b>
<br>This method removes the element<font color="#006600"> </font>at position
<i><font color="#006600">nIndex</font></i> from the array. The return
value is <i><font color="#006600">-1</font></i> if <i><font color="#006600">nIndex</font></i>
is out of range. Otherwise, it returns the size of the new array.
<p><b><i><font color="#FF0000">public final synchronized int SetAt(int
nIndex, Object obj);</font></i></b>
<br>This method assigns the element<font color="#006600"> <i>obj</i></font>
to position <i><font color="#006600">nIndex</font></i> in the array.
The return value is <i><font color="#006600">-1</font></i> if <i><font color="#006600">nIndex</font></i>
is out of range. Otherwise, it returns <i><font color="#006600">nIndex</font></i>.
<p><b><i><font color="#FF0000">public final synchronized void Push(Object
obj);</font></i></b>
<br>This method add a new element <i><font color="#006600">obj</font></i>
to the end of the array.
<p><b><i><font color="#FF0000">public final synchronized Object Pop( );</font></i></b>
<br>This method removes an element from the end of the array, the return
value is the element being removed.
<p><b><i><font color="#FF0000">public final synchronized int GetSort( );</font></i></b>
<br>This method returns <i><font color="#006600">1</font></i> if the array
is sorted in ascending order, it returns <i><font color="#006600">-1</font></i>
if sorted in descending order. Otherwise, it returns <i><font color="#006600">0</font></i>.
<p><b><i><font color="#FF0000">public final synchronized void SetSort(int
nSort);</font></i></b>
<br>If <i><font color="#006600">nSort </font></i>is <i><font color="#006600">1</font></i>,
it will sort the array in ascending order if not already sorted.
If <i><font color="#006600">nSort </font></i>is <i><font color="#006600">-1</font></i>,
it will sort the array in descending order if not already sorted.
<p><b><i><font color="#FF0000">public final synchronized virtual void Sort(int
nSort);</font></i></b>
<br>This method sorts the array. <i><font color="#006600">nSort </font></i>specifies
what order to sort, <i><font color="#006600">1</font></i> for ascending,
<i><font color="#006600">-1</font></i>
for descending.
<p><b><i><font color="#FF0000">public final synchronized virtual void SortIndex(int[
] arrayIndex, int nSort);</font></i></b>
<br>This method does not sort the array itself, instead, it sorts an index
array according to the specified order. <i><font color="#006600">arrayIndex</font></i>
must be an integer array containing integers <i><font color="#006600">0,
1, 2, ..., nSize-1</font></i>, where <i><font color="#006600">nSize</font></i>
is the size of the current array. The
<b><i><font color="#FF0000">Sort</font></i></b>
method is implemented using this method. The algorithm is a combination
of <b><font color="#006600">insertion sort</font></b> and "<font color="#FF0000">randomized</font>"
<b><font color="#006600">quick sort</font></b>. The performance is
as good as the <b><font color="#660000">Arrays.sort</font></b> method in
<b><font color="#660000">Java JDK</font></b> for randomly generated data,
according to my tests. The <b><font color="#660000">Arrays.sort</font></b>
method performs better when the input data is nearly sorted.
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -