001: /*
002: Copyright (C) 2007 Mobixess Inc. http://www.java-objects-database.com
003:
004: This file is part of the JODB (Java Objects Database) open source project.
005:
006: JODB is free software; you can redistribute it and/or modify it under
007: the terms of version 2 of the GNU General Public License as published
008: by the Free Software Foundation.
009:
010: JODB is distributed in the hope that it will be useful, but WITHOUT ANY
011: WARRANTY; without even the implied warranty of MERCHANTABILITY or
012: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
013: for more details.
014:
015: You should have received a copy of the GNU General Public License along
016: with this program; if not, write to the Free Software Foundation, Inc.,
017: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
018: */
019: package com.mobixess.jodb.core.query;
020:
021: import java.io.IOException;
022: import java.util.Stack;
023:
024: import com.mobixess.jodb.core.query.SortDataCache.SortNodeRecord;
025:
026: public class QueryUtils {
027:
028: public static final void quickQuerySort(long[] arrayOfIds,
029: SortingDataProvider sortingDataProvider,
030: SortNodeRecord[] nodes) throws IOException {
031: int start = 0;
032: int end = -1;
033: Stack<Range> stack = new Stack<Range>();
034: int low;
035: int high;
036: Range range;
037: int pivot;
038: SortingDataContainer pivotVal;
039: long tmpVal;
040:
041: stack.push(new Range(0, arrayOfIds.length - 1));
042:
043: while (stack.size() > 0) {
044: if (start >= end) {
045: range = (Range) stack.pop();
046: start = range.start;
047: end = range.end;
048: }
049:
050: if (start < end) {
051: // select middle
052: pivot = start + (end - start) / 2;
053:
054: // select median of three
055: // if ((end - start) > 10)
056: // pivot = ((arrayOfIds[start] < arrayOfIds[pivot]) ?
057: // ((arrayOfIds[pivot] < arrayOfIds[end]) ? pivot : ((arrayOfIds[start] < arrayOfIds[end]) ? end : start)) :
058: // ((arrayOfIds[pivot] > arrayOfIds[end]) ? pivot : ((arrayOfIds[start] > arrayOfIds[end]) ? end : start)));
059:
060: pivotVal = sortingDataProvider
061: .getComparableForId(arrayOfIds[pivot]);
062: low = start;
063: high = end;
064:
065: while (low < high) {
066: while (sortingDataProvider.getComparableForId(
067: arrayOfIds[low]).compareTo(pivotVal, nodes) < 0
068: && (low <= end)) {
069: low++;
070: }
071: while (sortingDataProvider.getComparableForId(
072: arrayOfIds[high])
073: .compareTo(pivotVal, nodes) > 0
074: && (high >= start)) {
075: high--;
076: }
077:
078: if (low <= high) {
079: if (low < high) {
080: tmpVal = arrayOfIds[low];
081: arrayOfIds[low] = arrayOfIds[high];
082: arrayOfIds[high] = tmpVal;
083: }
084: low++;
085: high--;
086: }
087: }
088:
089: if ((high - start) > (end - low)) {
090: stack.push(new Range(low, end));
091: end = high;
092: } else {
093: stack.push(new Range(start, high));
094: start = low;
095: }
096: }
097: }
098: }
099:
100: /** Holds information about a quicksort partition range. */
101: private static final class Range {
102: private int start;
103: private int end;
104:
105: private Range(int start, int end) {
106: this.start = start;
107: this.end = end;
108: }
109: }
110: }
|