18 #include "QuickIndex.h"
21 #define __QI_INVALID 0
23 #define __QI_INTARRAY 2
24 #define __QI_STRINGARRAY 3
26 QuickIndex::QuickIndex()
29 datatype = __QI_INVALID;
32 void QuickIndex::Index(
const IntArray & source_data)
34 source = (
const void *) &source_data;
35 datatype = __QI_INTARRAY;
37 Dimension(source_data.Length());
42 void QuickIndex::Index(
const Vector & source_data)
44 source = (
const void *) &source_data;
45 datatype = __QI_VECTOR;
47 Dimension(source_data.Length());
52 void QuickIndex::Index(
const StringArray & source_data)
54 source = (
const void *) &source_data;
55 datatype = __QI_STRINGARRAY;
57 Dimension(source_data.Length());
62 void QuickIndex::IndexCounts(
const StringIntMap & source_data)
64 IntArray counts(source_data.Length());
66 for (
int i = 0; i < source_data.Length(); i++)
67 counts[i] = source_data.GetCount(i);
72 void QuickIndex::IndexCounts(
const StringIntHash & source_data)
74 IntArray counts(source_data.Capacity());
76 for (
int i = 0; i < source_data.Capacity(); i++)
77 if (source_data.SlotInUse(i))
78 counts[i] = source_data.Integer(i);
85 Dimension(source_data.Entries());
89 bool QuickIndex::IsBefore(
int i,
int j)
99 return data[i] < data[j];
104 return data[i] < data[j];
106 case __QI_STRINGARRAY :
109 return data[i].SlowCompare(data[j]) < 0;
115 void QuickIndex::Sort()
117 struct __QuickIndexStack
126 __QuickIndexStack stack[32];
131 const int Threshold = 7;
136 int scanl, scanr, pivot;
145 if (r - l > Threshold)
151 if (IsBefore(mid, l))
157 if (IsBefore(r, mid))
179 while ((scanl < r) && IsBefore(scanl, pivot))
182 while ((scanr > l) && IsBefore(pivot, scanr))
210 stack[stackIdx].left = l;
211 stack[stackIdx].right = scanl - 1;
223 stack[stackIdx].left = scanl + 1;
224 stack[stackIdx].right = r;
236 l = stack[stackIdx].left;
237 r = stack[stackIdx].right;