001: package com.quadcap.sql.lock;
002:
003: /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.util.Comparator;
042:
043: import com.quadcap.util.Debug;
044:
045: /**
046: *
047: *
048: * @author Stan Bailes
049: */
050: public class SortedArray {
051: Comparator compare;
052: int size;
053: Object[] array = new Object[32];
054:
055: public SortedArray(Comparator compare) {
056: this .compare = compare;
057: }
058:
059: public final int find(Object obj) {
060: int lo = 0;
061: int hi = size - 1;
062:
063: while (lo <= hi) {
064: int mid = (lo + hi) / 2;
065: Object m = array[mid];
066: int cmp = compare.compare(m, obj);
067: if (cmp < 0) {
068: lo = mid + 1;
069: } else if (cmp > 0) {
070: hi = mid - 1;
071: } else {
072: return mid;
073: }
074: }
075: return 0 - (lo + 1);
076: }
077:
078: //#ifdef PARANOID
079: //- final void check() {
080: //- for (int i = 0; i < size; i++) {
081: //- //Debug.println(" check " + i + ": " + array[i]);
082: //- if (i < size - 1) {
083: //- int cmp = compare.compare(array[i], array[i+1]);
084: //- if (cmp != -1) {
085: //- Debug.println("CHECK ERROR: " + i + ": " + array[i] + " vs " +
086: //- array[i+1] + " = " + cmp);
087: //- Debug.println("Array = " + this);
088: //- throw new RuntimeException("CHECK Failed");
089: //- }
090: //- }
091: //- }
092: //- }
093: //#endif
094:
095: public void add(Object obj) {
096: //#ifdef PARANOID
097: //- if (obj instanceof HeldLock) {
098: //- HeldLock lock = (HeldLock)obj;
099: //- 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
115: .arraycopy(array, pos, array, pos + 1, size
116: - pos);
117: }
118: array[pos] = obj;
119: size++;
120: }
121: }
122:
123: public void remove(Object obj) {
124: removeAt(find(obj));
125: }
126:
127: public void removeAt(int pos) {
128: if (pos >= 0) {
129: int next = pos + 1;
130: if (next < size) {
131: System.arraycopy(array, next, array, pos, size - next);
132: }
133: size--;
134: }
135: }
136:
137: public int size() {
138: return size;
139: }
140:
141: public final Object get(int i) {
142: return array[i];
143: }
144:
145: final void checkSizeForAdd() {
146: if (size >= array.length) {
147: Object[] old = array;
148: array = new Object[old.length + (old.length >> 2)];
149: System.arraycopy(old, 0, array, 0, old.length);
150: }
151: }
152:
153: public String toString() {
154: StringBuffer sb = new StringBuffer("");
155: for (int i = 0; i < size; i++) {
156: sb.append("\n");
157: sb.append(String.valueOf(i));
158: sb.append(": ");
159: sb.append(array[i]);
160: }
161: sb.append("\n");
162: return sb.toString();
163: }
164:
165: }
|