KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > quadcap > sql > lock > SortedArray


1 package com.quadcap.sql.lock;
2
3 /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
4  *
5  * This software is distributed under the Quadcap Free Software License.
6  * This software may be used or modified for any purpose, personal or
7  * commercial. Open Source redistributions are permitted. Commercial
8  * redistribution of larger works derived from, or works which bundle
9  * this software requires a "Commercial Redistribution License"; see
10  * http://www.quadcap.com/purchase.
11  *
12  * Redistributions qualify as "Open Source" under one of the following terms:
13  *
14  * Redistributions are made at no charge beyond the reasonable cost of
15  * materials and delivery.
16  *
17  * Redistributions are accompanied by a copy of the Source Code or by an
18  * irrevocable offer to provide a copy of the Source Code for up to three
19  * years at the cost of materials and delivery. Such redistributions
20  * must allow further use, modification, and redistribution of the Source
21  * Code under substantially the same terms as this license.
22  *
23  * Redistributions of source code must retain the copyright notices as they
24  * appear in each source code file, these license terms, and the
25  * disclaimer/limitation of liability set forth as paragraph 6 below.
26  *
27  * Redistributions in binary form must reproduce this Copyright Notice,
28  * these license terms, and the disclaimer/limitation of liability set
29  * forth as paragraph 6 below, in the documentation and/or other materials
30  * provided with the distribution.
31  *
32  * The Software is provided on an "AS IS" basis. No warranty is
33  * provided that the Software is free of defects, or fit for a
34  * particular purpose.
35  *
36  * Limitation of Liability. Quadcap Software shall not be liable
37  * for any damages suffered by the Licensee or any third party resulting
38  * from use of the Software.
39  */
40
41 import java.util.Comparator JavaDoc;
42
43 import com.quadcap.util.Debug;
44
45 /**
46  *
47  *
48  * @author Stan Bailes
49  */
50 public class SortedArray {
51     Comparator JavaDoc compare;
52     int size;
53     Object JavaDoc[] array = new Object JavaDoc[32];
54     
55     public SortedArray(Comparator JavaDoc compare) {
56         this.compare = compare;
57     }
58
59     public final int find(Object JavaDoc obj) {
60     int lo = 0;
61     int hi = size - 1;
62
63     while (lo <= hi) {
64         int mid = (lo + hi) / 2;
65         Object JavaDoc m = array[mid];
66         int cmp = compare.compare(m, obj);
67         if (cmp < 0) {
68         lo = mid + 1;
69             } else if (cmp > 0) {
70         hi = mid - 1;
71             } else {
72                 return mid;
73             }
74     }
75         return 0 - (lo + 1);
76     }
77
78     //#ifdef PARANOID
79 //- final void check() {
80 //- for (int i = 0; i < size; i++) {
81 //- //Debug.println(" check " + i + ": " + array[i]);
82 //- if (i < size - 1) {
83 //- int cmp = compare.compare(array[i], array[i+1]);
84 //- if (cmp != -1) {
85 //- Debug.println("CHECK ERROR: " + i + ": " + array[i] + " vs " +
86 //- array[i+1] + " = " + cmp);
87 //- Debug.println("Array = " + this);
88 //- throw new RuntimeException("CHECK Failed");
89 //- }
90 //- }
91 //- }
92 //- }
93 //#endif
94
95     public void add(Object JavaDoc obj) {
96         //#ifdef PARANOID
97 //- if (obj instanceof HeldLock) {
98 //- HeldLock lock = (HeldLock)obj;
99 //- if (lock.trans == null) {
100 //- try {
101 //- throw new RuntimeException("lock.trans null: " + lock);
102 //- } catch (Throwable t) {
103 //- Debug.print(t);
104 //- }
105 //- }
106 //- }
107 //#endif
108 int pos = find(obj);
109         if (pos < 0) {
110             pos = 0 - (pos + 1);
111             checkSizeForAdd();
112
113             if (pos < size) {
114                 System.arraycopy(array, pos, array, pos+1, size - pos);
115             }
116             array[pos] = obj;
117             size++;
118         }
119     }
120
121     public void remove(Object JavaDoc obj) {
122         removeAt(find(obj));
123     }
124
125     public void removeAt(int pos) {
126         if (pos >= 0) {
127             int next = pos + 1;
128             if (next < size) {
129                 System.arraycopy(array, next, array, pos, size - next);
130             }
131             size--;
132         }
133     }
134
135     public int size() {
136         return size;
137     }
138
139     public final Object JavaDoc get(int i) {
140         return array[i];
141     }
142
143     final void checkSizeForAdd() {
144         if (size >= array.length) {
145             Object JavaDoc[] old = array;
146             array = new Object JavaDoc[old.length + (old.length >> 2)];
147             System.arraycopy(old, 0, array, 0, old.length);
148         }
149     }
150
151     public String JavaDoc toString() {
152         StringBuffer JavaDoc sb = new StringBuffer JavaDoc("");
153         for (int i = 0; i < size; i++) {
154             sb.append("\n");
155             sb.append(String.valueOf(i));
156             sb.append(": ");
157             sb.append(array[i]);
158         }
159         sb.append("\n");
160         return sb.toString();
161     }
162         
163 }
164
Popular Tags