root / trunk / libraries / libGDBMS / src / main / java / com / hardcode / gdbms / engine / data / indexes / QuickSort.java @ 10627
History | View | Annotate | Download (3.55 KB)
| 1 |
package com.hardcode.gdbms.engine.data.indexes; |
|---|---|
| 2 |
|
| 3 |
import com.hardcode.gdbms.driver.exceptions.ReadDriverException; |
| 4 |
import com.hardcode.gdbms.engine.data.DataSource; |
| 5 |
import com.hardcode.gdbms.engine.instruction.IncompatibleTypesException; |
| 6 |
import com.hardcode.gdbms.engine.values.BooleanValue; |
| 7 |
import com.hardcode.gdbms.engine.values.Value; |
| 8 |
|
| 9 |
import java.io.IOException; |
| 10 |
|
| 11 |
import java.util.Stack; |
| 12 |
|
| 13 |
|
| 14 |
/**
|
| 15 |
* DOCUMENT ME!
|
| 16 |
*
|
| 17 |
* @author Fernando Gonz?lez Cort?s
|
| 18 |
*/
|
| 19 |
public class QuickSort { |
| 20 |
private FixedIndexSet ret;
|
| 21 |
private int fieldId; |
| 22 |
private DataSource dataSource; |
| 23 |
|
| 24 |
/**
|
| 25 |
* DOCUMENT ME!
|
| 26 |
*
|
| 27 |
* @param ini DOCUMENT ME!
|
| 28 |
* @param fin DOCUMENT ME!
|
| 29 |
*
|
| 30 |
* @return DOCUMENT ME!
|
| 31 |
* @throws ReadDriverException TODO
|
| 32 |
* @throws IOException
|
| 33 |
*/
|
| 34 |
private long partition(long ini, long fin) |
| 35 |
throws ReadDriverException, IOException { |
| 36 |
long first = ini;
|
| 37 |
long last = fin;
|
| 38 |
|
| 39 |
long pivotIndex = first;
|
| 40 |
Object pivot = dataSource.getFieldValue(ret.getIndex(pivotIndex),
|
| 41 |
fieldId); |
| 42 |
|
| 43 |
long up = first;
|
| 44 |
long down = last;
|
| 45 |
|
| 46 |
while (up < down) {
|
| 47 |
//Encuentra el primer valor > que el pivote
|
| 48 |
while (compare(pivot,
|
| 49 |
dataSource.getFieldValue(ret.getIndex(up), fieldId)) <= 0) {
|
| 50 |
up++; |
| 51 |
|
| 52 |
if (up > fin) {
|
| 53 |
break;
|
| 54 |
} |
| 55 |
} |
| 56 |
|
| 57 |
//Encuentra el primer valor <= que el pivote
|
| 58 |
while (compare(pivot,
|
| 59 |
dataSource.getFieldValue(ret.getIndex(down), fieldId)) > 0) {
|
| 60 |
down--; |
| 61 |
|
| 62 |
if (down < ini) {
|
| 63 |
break;
|
| 64 |
} |
| 65 |
} |
| 66 |
|
| 67 |
if (up < down) {
|
| 68 |
long aux = ret.getIndex(up);
|
| 69 |
ret.setIndex(up, ret.getIndex(down)); |
| 70 |
ret.setIndex(down, aux); |
| 71 |
} |
| 72 |
} |
| 73 |
|
| 74 |
long aux = ret.getIndex(pivotIndex);
|
| 75 |
ret.setIndex(pivotIndex, ret.getIndex(down)); |
| 76 |
ret.setIndex(down, aux); |
| 77 |
|
| 78 |
return up;
|
| 79 |
} |
| 80 |
|
| 81 |
/**
|
| 82 |
* DOCUMENT ME!
|
| 83 |
*
|
| 84 |
* @param o1 DOCUMENT ME!
|
| 85 |
* @param o2 DOCUMENT ME!
|
| 86 |
*
|
| 87 |
* @return DOCUMENT ME!
|
| 88 |
*
|
| 89 |
* @throws RuntimeException DOCUMENT ME!
|
| 90 |
*/
|
| 91 |
private int compare(Object o1, Object o2) { |
| 92 |
Value v1 = (Value) o1; |
| 93 |
Value v2 = (Value) o2; |
| 94 |
|
| 95 |
try {
|
| 96 |
if (((BooleanValue) v1.less(v2)).getValue()) {
|
| 97 |
return -1; |
| 98 |
} else if (((BooleanValue) v2.less(v1)).getValue()) { |
| 99 |
return 1; |
| 100 |
} else {
|
| 101 |
return 0; |
| 102 |
} |
| 103 |
} catch (IncompatibleTypesException e) {
|
| 104 |
throw new RuntimeException( |
| 105 |
"Como incompatibles si se indexa sobre la misma columna?");
|
| 106 |
} |
| 107 |
} |
| 108 |
|
| 109 |
/**
|
| 110 |
* DOCUMENT ME!
|
| 111 |
*
|
| 112 |
* @param v DOCUMENT ME!
|
| 113 |
* @param fieldId DOCUMENT ME!
|
| 114 |
* @param low DOCUMENT ME!
|
| 115 |
* @param high DOCUMENT ME!
|
| 116 |
* @throws IOException
|
| 117 |
* @throws ReadDriverException TODO
|
| 118 |
*/
|
| 119 |
public void quickSort(DataSource v, int fieldId, long low, long high) |
| 120 |
throws IOException, ReadDriverException { |
| 121 |
dataSource = v; |
| 122 |
this.fieldId = fieldId;
|
| 123 |
|
| 124 |
ret = IndexFactory.createFixedIndex(high - low + 1);
|
| 125 |
|
| 126 |
for (int i = 0; i < ret.getIndexCount(); i++) { |
| 127 |
ret.setIndex(i, i); |
| 128 |
} |
| 129 |
|
| 130 |
Stack intervalos = new Stack(); |
| 131 |
Intervalo inicial = new Intervalo(low, high);
|
| 132 |
intervalos.push(inicial); |
| 133 |
|
| 134 |
while (!intervalos.empty()) {
|
| 135 |
Intervalo i = (Intervalo) intervalos.pop(); |
| 136 |
|
| 137 |
long pivote = partition(i.ini, i.fin);
|
| 138 |
|
| 139 |
if (i.ini < (pivote - 1)) { |
| 140 |
intervalos.push(new Intervalo(i.ini, pivote - 2)); |
| 141 |
} |
| 142 |
|
| 143 |
if ((pivote + 1) < i.fin) { |
| 144 |
intervalos.push(new Intervalo(pivote, i.fin));
|
| 145 |
} |
| 146 |
} |
| 147 |
} |
| 148 |
|
| 149 |
/**
|
| 150 |
* DOCUMENT ME!
|
| 151 |
*
|
| 152 |
* @return Returns the indexes.
|
| 153 |
*/
|
| 154 |
public FixedIndexSet getIndexes() {
|
| 155 |
return ret;
|
| 156 |
} |
| 157 |
|
| 158 |
/**
|
| 159 |
* DOCUMENT ME!
|
| 160 |
*
|
| 161 |
* @author Fernando Gonz?lez Cort?s
|
| 162 |
*/
|
| 163 |
public class Intervalo { |
| 164 |
long ini;
|
| 165 |
long fin;
|
| 166 |
|
| 167 |
/**
|
| 168 |
* Crea un nuevo Intervalo.
|
| 169 |
*
|
| 170 |
* @param ini DOCUMENT ME!
|
| 171 |
* @param fin DOCUMENT ME!
|
| 172 |
*/
|
| 173 |
public Intervalo(long ini, long fin) { |
| 174 |
this.ini = ini;
|
| 175 |
this.fin = fin;
|
| 176 |
} |
| 177 |
} |
| 178 |
} |