001: /*
002: *
003: *
004: * Portions Copyright 2000-2007 Sun Microsystems, Inc. All Rights
005: * Reserved. Use is subject to license terms.
006: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
007: *
008: * This program is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU General Public License version
010: * 2 only, as published by the Free Software Foundation.
011: *
012: * This program is distributed in the hope that it will be useful, but
013: * WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * General Public License version 2 for more details (a copy is
016: * included at /legal/license.txt).
017: *
018: * You should have received a copy of the GNU General Public License
019: * version 2 along with this work; if not, write to the Free Software
020: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
021: * 02110-1301 USA
022: *
023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
024: * Clara, CA 95054 or visit www.sun.com if you need additional
025: * information or have any questions.
026: *
027: * Copyright 2000 Motorola, Inc. All Rights Reserved.
028: * This notice does not imply publication.
029: */
030:
031: package javax.microedition.rms;
032:
033: import com.sun.midp.log.Logging;
034: import com.sun.midp.log.LogChannels;
035:
036: /**
037: * This class implements the RecordEnumeration interface.
038: */
039: class RecordEnumerationImpl implements RecordEnumeration,
040: RecordListener {
041:
042: /** The associated record store for this enumeration */
043: private RecordStore recordStore;
044:
045: /** The record filter this enumeration should use, or null if none */
046: private RecordFilter filter;
047:
048: /** The record comparator this enumeration should use, or null if none */
049: private RecordComparator comparator;
050:
051: /** True if this should listen to <code>recordStore</code> for changes */
052: private boolean keepEnumUpdated; // false by default
053:
054: /** Current pos within the enumeration */
055: private int index; // NO_SUCH_RECORD by default
056:
057: /** Array of recordId's of records included in the enumeration */
058: private int[] records;
059:
060: /**
061: * A constant recordId indicating the splice point between the
062: * last and first records in the enumeration. Returned by
063: * <code>nextElement()</code> and <code>prevElement()</code>
064: * when the next or prev element does not exist.
065: */
066: private static final int NO_SUCH_RECORD = -1;
067:
068: /**
069: * Builds an enumeration to traverse a set of records in the
070: * given record store in an optionally specified order.<p>
071: *
072: * The filter, if non-null, will be used to determine what
073: * subset of the record store records will be used.<p>
074: *
075: * The comparator, if non-null, will be used to determine the
076: * order in which the records are returned.<p>
077: *
078: * If both the filter and comparator are null, the enumeration
079: * will traverse all records in the record store in an undefined
080: * order. This is the most efficient way to traverse all of the
081: * records in a record store.
082: *
083: * @param inp_recordStore the RecordStore to enumerate.
084: * @param inp_filter if non-null, will be used to determine what
085: * subset of the record store records will be used.
086: * @param inp_comparator if non-null, will be used to determine the
087: * order in which the records are returned.
088: * @param keepUpdated if true, the enumerator will keep its enumeration
089: * current with any changes in the records of the record store.
090: * Use with caution as there are performance consequences.
091: *
092: * @see #rebuild
093: */
094: RecordEnumerationImpl(RecordStore inp_recordStore,
095: RecordFilter inp_filter, RecordComparator inp_comparator,
096: boolean keepUpdated) {
097: recordStore = inp_recordStore;
098: filter = inp_filter;
099: comparator = inp_comparator;
100: keepEnumUpdated = keepUpdated;
101:
102: if (keepUpdated) {
103: inp_recordStore.addRecordListener(this );
104: }
105:
106: rebuild();
107: }
108:
109: /**
110: * Returns the number of records available in this enumeration's
111: * set. That is, the number of records that have matched the
112: * filter criterion. Note that this forces the RecordEnumeration
113: * to fully build the enumeration by applying the filter to all
114: * records, which may take a non-trivial amount
115: * of time if there are a lot of records in the record store.
116: *
117: * @return the number of records available in this enumeration's
118: * set. That is, the number of records that have matched
119: * the filter criterion.
120: */
121: public synchronized int numRecords() {
122: checkDestroyed();
123:
124: return records.length;
125: }
126:
127: /**
128: * Returns a copy of the <i>next</i> record in this enumeration,
129: * where <i>next</i> is defined by the comparator and/or filter
130: * supplied in the constructor of this enumerator. The byte array
131: * returned is a copy of the record. Any changes made to this array
132: * will NOT be reflected in the record store. After calling
133: * this method, the enumeration is advanced to the next available
134: * record.
135: *
136: * @exception InvalidRecordIDException no more records are available
137: *
138: * @return the next record in this enumeration.
139: */
140: public synchronized byte[] nextRecord()
141: throws InvalidRecordIDException,
142: RecordStoreNotOpenException, RecordStoreException {
143: checkDestroyed();
144: return recordStore.getRecord(nextRecordId());
145: }
146:
147: /**
148: * Returns the recordId of the <i>next</i> record in this enumeration,
149: * where <i>next</i> is defined by the comparator and/or filter
150: * supplied in the constructor of this enumerator. After calling
151: * this method, the enumeration is advanced to the next available
152: * record.
153: *
154: * @exception InvalidRecordIDException no more records are available.
155: *
156: * @return the recordId of the next record in this enumeration.
157: */
158: public synchronized int nextRecordId()
159: throws InvalidRecordIDException {
160: checkDestroyed();
161: if (index == records.length - 1) {
162: throw new InvalidRecordIDException();
163: }
164: if (index == NO_SUCH_RECORD) {
165: index = 0;
166: } else {
167: index++;
168: }
169: return records[index];
170: }
171:
172: /**
173: * Returns a copy of the <i>previous</i> record in this enumeration,
174: * where <i>previous</i> is defined by the comparator and/or filter
175: * supplied in the constructor of this enumerator. The byte array
176: * returned is a copy of the record. Any changes made to this array
177: * will NOT be reflected in the record store. After calling
178: * this method, the enumeration is advanced to the next (previous)
179: * available record.
180: *
181: * @exception InvalidRecordIDException no more records are available.
182: *
183: * @return the previous record in this enumeration.
184: */
185: public synchronized byte[] previousRecord()
186: throws InvalidRecordIDException,
187: RecordStoreNotOpenException, RecordStoreException {
188:
189: checkDestroyed();
190: return recordStore.getRecord(previousRecordId());
191: }
192:
193: /**
194: * Returns the recordId of the <i>previous</i> record in this enumeration,
195: * where <i>previous</i> is defined by the comparator and/or filter
196: * supplied in the constructor of this enumerator. After this method
197: * is called, the enumeration is advanced to the next (previous)
198: * available record.
199: *
200: * @exception InvalidRecordIDException when no more records are available.
201: *
202: * @return the recordId of the previous record in this enumeration.
203: */
204: public synchronized int previousRecordId()
205: throws InvalidRecordIDException {
206: checkDestroyed();
207: if (index == 0 || records.length == 0) {
208: throw new InvalidRecordIDException();
209: }
210: if (index == NO_SUCH_RECORD) {
211: index = records.length - 1;
212: } else {
213: index--;
214: }
215: return records[index];
216: }
217:
218: /**
219: * Returns true if more elements exist in the <i>next</i> direction.
220: *
221: * @return true if more elements exist in the <i>next</i> direction.
222: */
223: public boolean hasNextElement() {
224: checkDestroyed();
225: if (records.length == 0 || !recordStore.isOpen()) {
226: return false;
227: }
228: return (index != records.length - 1);
229: }
230:
231: /**
232: * Returns true if more elements exist in the <i>previous</i> direction.
233: *
234: * @return true if more elements exist in the <i>previous</i> direction.
235: */
236: public boolean hasPreviousElement() {
237: checkDestroyed();
238: if (records.length == 0 || !recordStore.isOpen()) {
239: return false; // no records in the enumeration
240: }
241: return (index != 0);
242: }
243:
244: /**
245: * Returns the index point of the enumeration to the beginning.
246: */
247: public void reset() {
248: checkDestroyed();
249: index = NO_SUCH_RECORD;
250: }
251:
252: /**
253: * Request that the enumeration be updated to reflect the current
254: * record set. Useful for when an application makes a number of
255: * changes to the record store, and then wants an existing
256: * RecordEnumeration to enumerate the new changes.
257: *
258: * @see #keepUpdated
259: */
260: public void rebuild() {
261: checkDestroyed();
262:
263: int[] tmp = recordStore.getRecordIDs();
264: reFilterSort(tmp);
265: }
266:
267: /**
268: * Used to set whether the enumeration should be registered
269: * as a listener of the record store, and rebuild its internal
270: * index with every record addition/deletion in the record store.
271: * Note that this should be used carefully due to the potential
272: * performance cost associated with maintaining the
273: * enumeration with every change.
274: *
275: * @param keepUpdated if true, the enumerator will keep its enumeration
276: * current with any changes in the records of the record store.
277: * Use with caution as there are possible performance consequences.
278: * If false, the enumeration will not be kept current and may
279: * return recordIds for records that have been deleted or miss
280: * records that are added later. It may also return records out
281: * of order that have been modified after the enumeration was
282: * built.
283: *
284: * @see #rebuild
285: */
286: public void keepUpdated(boolean keepUpdated) {
287: checkDestroyed();
288: if (keepUpdated != keepEnumUpdated) {
289: keepEnumUpdated = keepUpdated;
290: if (keepUpdated) {
291: recordStore.addRecordListener(this );
292: rebuild();
293: } else {
294: recordStore.removeRecordListener(this );
295: }
296: }
297: }
298:
299: /**
300: * Returns true if the enumeration keeps its enumeration
301: * current with any changes in the records.
302: *
303: * @return true if the enumeration keeps its enumeration
304: * current with any changes in the records
305: */
306: public boolean isKeptUpdated() {
307: checkDestroyed();
308: return keepEnumUpdated;
309: }
310:
311: /**
312: * From the RecordListener interface. This method is called if
313: * a record is added to <code>recordStore</code>.
314: *
315: * @param inp_recordStore the record store to which a record was added
316: * @param recordId the record ID of the new record
317: */
318: public synchronized void recordAdded(RecordStore inp_recordStore,
319: int recordId) {
320: checkDestroyed();
321: filterAdd(recordId);
322: }
323:
324: /**
325: * From the RecordListener interface. This method is called if
326: * a record in <code>recordStore</code> is modified.
327: *
328: * @param inp_recordStore the record store in which a record was modified
329: * @param recordId the record ID of the modified record.
330: */
331: public synchronized void recordChanged(RecordStore inp_recordStore,
332: int recordId) {
333: checkDestroyed();
334:
335: int recIndex = findIndexOfRecord(recordId);
336: if (recIndex >= 0) {
337: removeRecordAtIndex(recIndex);
338: } // else record not previously in the enumeration
339:
340: filterAdd(recordId);
341: }
342:
343: /**
344: * From the RecordListener interface. This method is called when a
345: * record in <code>recordStore</code> is deleted.
346: *
347: * @param inp_recordStore the record store from which a record was deleted
348: * @param recordId the record id of the deleted record
349: */
350: public synchronized void recordDeleted(RecordStore inp_recordStore,
351: int recordId) {
352: checkDestroyed();
353:
354: /*
355: * Remove the deleted element from the records array.
356: * No resorting is required.
357: */
358:
359: int recIndex = findIndexOfRecord(recordId);
360:
361: if (recIndex < 0) {
362: return; // not in the enumeration
363: }
364:
365: // remove this record from the enumeration
366: removeRecordAtIndex(recIndex);
367: }
368:
369: /**
370: * Implements RecordEnumeration.destroy() interface. Called
371: * to signal that this enumeration will no longer be used, and that
372: * its resources may be collected.
373: */
374: public synchronized void destroy() {
375: checkDestroyed();
376: if (keepEnumUpdated) {
377: recordStore.removeRecordListener(this );
378: }
379:
380: filter = null;
381: comparator = null;
382: records = null;
383: recordStore = null; // a signal that this is destroyed!
384: }
385:
386: /**
387: * Helper method that checks if this enumeration can be used.
388: * If this enumeration has been destroyed, an exception is thrown.
389: *
390: * @exception IllegalStateException if RecordEnumeration has been
391: * destroyed.
392: */
393: private void checkDestroyed() {
394: if (recordStore == null) {
395: throw new IllegalStateException();
396: }
397: }
398:
399: /**
400: * Used to add a record to an already filtered and sorted
401: * <code>records</code> array. More efficient than
402: * <code>reFilterSort</code> because it relies on
403: * <code>records</code> being in sorted order.
404: *
405: * First ensures that record <code>recordId</code>
406: * meets this enumeration's filter criteria.
407: * If it does it is added to records as array element
408: * 0. If a comparator is defined for this enumeration,
409: * the helper method <code>sortAdd</code> is called to
410: * properly position <code>recordId</code> within the ordered
411: * <code>records</code> array.
412: *
413: * Should be called from within a
414: * synchronized (recordStore.rsLock) block.
415: *
416: * @param recordId the record to add to this enumeration
417: */
418: private void filterAdd(int recordId) {
419: int insertPoint = -1;
420: if (filter != null) {
421: try {
422: if (!filter.matches(recordStore.getRecord(recordId))) {
423: if (Logging.REPORT_LEVEL <= Logging.WARNING) {
424: Logging.report(Logging.WARNING,
425: LogChannels.LC_RMS,
426: "Unexpected case in filterAdd: "
427: + "recordId filtered out");
428: }
429: return; // recordId filtered out
430: }
431: } catch (RecordStoreException rse) {
432: return; // recordId does not exist
433: }
434: }
435:
436: // the new record has been accepted by the filter
437: int[] newrecs = new int[records.length + 1];
438: newrecs[0] = recordId; // insert new record at front of list
439: System.arraycopy(records, 0, newrecs, 1, records.length);
440: records = newrecs;
441: if (comparator != null) { // move the new record into place
442: try {
443: insertPoint = sortInsert();
444: } catch (RecordStoreException rse) {
445: // NOTE: - should never be here
446: // throw a RSE? destroy record enumeration?
447: if (Logging.TRACE_ENABLED) {
448: Logging.trace(rse, "Unexpected case in filterAdd: "
449: + "caught RSE");
450: }
451: }
452: }
453: // keep index up to date as well
454: if (index != NO_SUCH_RECORD && insertPoint <= index) {
455: index++;
456: }
457: }
458:
459: /**
460: * Helper method called by <code>filterAdd</code>.
461: * Moves the possibly unsorted element zero in the
462: * <code>records</code> array to its sorted position
463: * within the array.
464: *
465: * @return index of inserted element.
466: * @exception RecordStoreException if an error occurs
467: * in the comparator function.
468: */
469: private int sortInsert() throws RecordStoreException {
470: // bubble sort the first record in records into place
471: int tmp;
472: int i;
473: int j;
474: for (i = 0, j = 1; i < records.length - 1; i++, j++) {
475: if (comparator.compare(recordStore.getRecord(records[i]),
476: recordStore.getRecord(records[j])) == RecordComparator.FOLLOWS) {
477: // if i follows j swap them in records
478: tmp = records[i];
479: records[i] = records[j];
480: records[j] = tmp;
481: } else {
482: break; // done sorting if compare returns EQUALS or PRECEDES
483: }
484: }
485: return i; // final index of new record in records
486: }
487:
488: /**
489: * Find the index in records of record <code>recordId</code>
490: * and return it.
491: *
492: * @param recordId the record index to find
493: * @return the index of the record, or -1.
494: */
495: private int findIndexOfRecord(int recordId) {
496: int idx;
497: int recIndex = -1;
498: for (idx = records.length - 1; idx >= 0; idx--) {
499: if (records[idx] == recordId) {
500: recIndex = idx;
501: break;
502: }
503: }
504: return recIndex;
505: }
506:
507: /**
508: * Internal helper method which
509: * removes the array element at index <code>recIndex</code>
510: * from the internal <code>records</code> array.
511: *
512: * <code>recIndex</code> should be non negative.
513: *
514: * @param recIndex the array element to remove.
515: */
516: private void removeRecordAtIndex(int recIndex) {
517: int[] tmp = new int[records.length - 1];
518: System.arraycopy(records, 0, tmp, 0, recIndex);
519: System.arraycopy(records, recIndex + 1, tmp, recIndex,
520: (records.length - recIndex) - 1);
521: records = tmp;
522:
523: /*
524: * If a record prior to current index was deleted
525: * update index so nothing is skipped
526: */
527: if (index != NO_SUCH_RECORD && recIndex <= index) {
528: index--;
529: } else if (index == records.length) {
530: // last element in records removed
531: index--;
532: }
533: }
534:
535: /**
536: * Internal helper method for filtering and sorting records if
537: * necessary. Called from rebuild().
538: *
539: * Should be called from within a synchronized(recordStore.rsLock) block
540: *
541: * @param filtered array of record stores to filter and sort.
542: */
543: private void reFilterSort(int[] filtered) {
544: int filteredIndex = 0;
545: if (filter == null) {
546: /*
547: * If this enumeration doesn't have any filters, the
548: * recordId's returned by getRecordIDs should be
549: * used as they are.
550: */
551: records = filtered;
552: } else {
553: /*
554: * If a filter has been specified, filter the recordStore
555: * records to determine the subset to be used for this
556: * enumeration.
557: */
558: for (int i = 0; i < filtered.length; i++) {
559: // if this record matches the filter keep it
560: try {
561: if (filter.matches(recordStore
562: .getRecord(filtered[i]))) {
563: // need revisit : if element overlap is allowed
564: if (filteredIndex != i) {
565: filtered[filteredIndex++] = filtered[i];
566: } else {
567: filteredIndex++;
568: }
569: }
570: } catch (RecordStoreException rse) {
571: // if a record can't be found it doesn't match
572: }
573: }
574:
575: records = new int[filteredIndex];
576: System.arraycopy(filtered, 0, records, 0, filteredIndex);
577: }
578: /*
579: * If a comparator has been specified, sort the remaining
580: * records by comparing records against each other using
581: * the comparator the application provides.
582: */
583: if (comparator != null) {
584: try {
585: QuickSort(records, 0, records.length - 1, comparator);
586: } catch (RecordStoreException rse) {
587: // NOTE: - should never be here
588: // throw a RSE? destroy record enumeration?
589:
590: if (Logging.TRACE_ENABLED) {
591: Logging.trace(rse,
592: "Unexpected case in reFilterSort:"
593: + " caught RSE");
594: }
595: }
596: }
597: reset(); // reset the current index of this enumeration
598: }
599:
600: /**
601: * Quicksort helper function for sorting the records.
602: *
603: * @param a the array of recordId's to sort using comparator.
604: * @param lowIndex the low bound of the range to sort.
605: * @param highIndex the hight bound of the range to sort.
606: * @param inp_comparator the RecordComparator to use to compare records.
607: */
608: private void QuickSort(int a[], int lowIndex, int highIndex,
609: RecordComparator inp_comparator)
610: throws RecordStoreException {
611:
612: /*
613: * A different sorting algorithm may be preferred, because a
614: * large recursive quicksort can consume lots of
615: * stack. Quicksort is very fast for most random sequences
616: * however...
617: */
618: int left = lowIndex; // the "left" index
619: int right = highIndex; // the "right" index
620:
621: /*
622: * First partition the data into two regions, where every
623: * element on the left side of the partition is less than
624: * every element on the right side of the element.
625: */
626: if (highIndex > lowIndex) {
627: /*
628: * Arbitrarily choose the initial pivot point to be the
629: * middle of the array.
630: */
631: int ind = (lowIndex + highIndex) / 2;
632: int pivotIndex = a[ind];
633: byte[] pivotData = recordStore.getRecord(pivotIndex);
634:
635: // loop through the array until the indices cross
636: while (left <= right) {
637: /*
638: * Starting on the left, scan right until the
639: * first element greater than or equal to the
640: * pivot element is found.
641: */
642: while ((left < highIndex)
643: && (inp_comparator.compare(recordStore
644: .getRecord(a[left]), pivotData) == RecordComparator.PRECEDES)) {
645: left++;
646: }
647: /*
648: * Starting on the right, scan left until the
649: * first element that is less than or equal to the
650: * pivot element is found.
651: */
652: while ((right > lowIndex)
653: && (inp_comparator.compare(recordStore
654: .getRecord(a[right]), pivotData) == RecordComparator.FOLLOWS)) {
655: right--;
656: }
657:
658: // if the indexes haven't crossed, swap the elements
659: if (left <= right) {
660: int tmp = a[left];
661: a[left] = a[right];
662: a[right] = tmp;
663: left++;
664: right--;
665: }
666: }
667:
668: // Sort the left side of the partition
669: if (lowIndex < right) {
670: QuickSort(a, lowIndex, right, inp_comparator);
671: }
672: // Sort the right side of the partition
673: if (left < highIndex) {
674: QuickSort(a, left, highIndex, inp_comparator);
675: }
676: }
677: }
678: }
|