001/*
002 * Copyright 2013 Alex Kasko (alexkasko.com)
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.alexkasko.unsafe.offheapstruct;
018
019import com.alexkasko.unsafe.offheap.OffHeapDisposableIterable;
020import com.alexkasko.unsafe.offheap.OffHeapDisposableIterator;
021import com.alexkasko.unsafe.offheaplong.OffHeapLongArray;
022import com.alexkasko.unsafe.offheaplong.OffHeapLongComparator;
023import com.alexkasko.unsafe.offheaplong.OffHeapLongSorter;
024
025import java.util.Comparator;
026
027import static com.alexkasko.unsafe.offheap.OffHeapUtils.freeAll;
028
029/**
030 * <p>alexkasko: borrowed from {@code https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java}
031 * and adapted to {@link com.alexkasko.unsafe.offheapstruct.OffHeapStructCollection} to sort it by reference.
032 * without changing element positions in array itself.
033 *
034 * <p>Temporary {@link com.alexkasko.unsafe.offheaplong.OffHeapLongArray} with the same size
035 * as collection itself will be used to hold references.
036 *
037 * <p>This class implements the Dual-Pivot Quicksort algorithm by
038 * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
039 * offers O(n log(n)) performance on many data sets that cause other
040 * quicksorts to degrade to quadratic performance, and is typically
041 * faster than traditional (one-pivot) Quicksort implementations.
042 *
043 * @author Vladimir Yaroslavskiy
044 * @author Jon Bentley
045 * @author Josh Bloch
046 *
047 * @version 2009.11.29 m765.827.12i
048 */
049public class OffHeapStructSorterByReference {
050
051    /**
052     * Sorts collection using additional {@link com.alexkasko.unsafe.offheaplong.OffHeapLongArray} with the same size
053     * as collection itself as an array of references (indices) of the collection
054     *
055     * @param a the off-heap struct collection to be sorted
056     * @param comparator structs comparator
057     * @return sorted iterable over the collection
058     * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())}
059     */
060    static OffHeapDisposableIterable<byte[]> sortedIterable(OffHeapStructCollection a, Comparator<OffHeapStructAccessor> comparator) {
061        return sortedIterable(a, 0, a.size(), comparator);
062    }
063
064    /**
065     * Sorts collection using additional {@link com.alexkasko.unsafe.offheaplong.OffHeapLongArray} with the same size
066     * as collection itself as an array of references (indices) of the collection
067     *
068     * @param a the off-heap struct collection to be sorted
069     * @param fromIndex the index of the first element, inclusive, to be sorted
070     * @param toIndex the index of the last element, exclusive, to be sorted
071     * @param comparator structs comparator
072     * @return sorted iterable over the collection
073     * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())}
074     */
075    static OffHeapDisposableIterable<byte[]> sortedIterable(OffHeapStructCollection a, long fromIndex,
076                                           long toIndex, Comparator<OffHeapStructAccessor> comparator) {
077        if(null == comparator) throw new IllegalArgumentException("Provided comparator is null");
078        if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size()) {
079            throw new IllegalArgumentException("Illegal input, collection size: [" + a.size() + "], " +
080                    "fromIndex: [" + fromIndex + "], toIndex: [" + toIndex + "]");
081        }
082        OffHeapLongArray indices = new OffHeapLongArray(toIndex - fromIndex);
083        for (long i = fromIndex; i < toIndex; i++) {
084            indices.set(i, i);
085        }
086        OffHeapLongComparator indexComp = new OffHeapReferenceComparator(a, comparator);
087        OffHeapLongSorter.sort(indices, indexComp);
088        return new ReferenceIterable(a, indices);
089    }
090
091    /**
092     * Comparator wrapper to use with references, not thread-safe
093     */
094    private static class OffHeapReferenceComparator implements OffHeapLongComparator {
095        private final Comparator<OffHeapStructAccessor> comp;
096        private final OffHeapStructIndexAccessor ac1;
097        private final OffHeapStructIndexAccessor ac2;
098
099        /**
100         * Constructor
101         *
102         * @param data data in sorting
103         * @param comp user provided comparator
104         */
105        private OffHeapReferenceComparator(OffHeapStructCollection data, Comparator<OffHeapStructAccessor> comp) {
106            this.comp = comp;
107            this.ac1 = new OffHeapStructIndexAccessor(data);
108            this.ac2 = new OffHeapStructIndexAccessor(data);
109        }
110
111        /**
112         * {@inheritDoc}
113         */
114        @Override
115        public int compare(long l1, long l2) {
116            ac1.setIndex(l1);
117            ac2.setIndex(l2);
118            return comp.compare(ac1, ac2);
119        }
120    }
121
122    /**
123     * Struct's accessor implementation for off-heap stored structs
124     *
125     * @author alexkasko
126     *         Date: 9/13/13
127     */
128    private static class OffHeapStructIndexAccessor implements OffHeapStructAccessor {
129        private final OffHeapStructCollection col;
130        private long index = -1;
131
132        /**
133         * Constructor
134         *
135         * @param col collection to access structs from
136         */
137        private OffHeapStructIndexAccessor(OffHeapStructCollection col) {
138            this.col = col;
139        }
140
141        /**
142         * {@inheritDoc}
143         */
144        @Override
145        public int structLength() {
146            return col.structLength();
147        }
148
149        /**
150         * {@inheritDoc}
151         */
152        @Override
153        public void get(byte[] buffer) {
154            col.get(index, buffer);
155        }
156
157        /**
158         * {@inheritDoc}
159         */
160        @Override
161        public void get(int srcPos, byte[] dest, int destPos, int length) {
162            col.get(index, srcPos, dest, destPos, length);
163        }
164
165        /**
166         * {@inheritDoc}
167         */
168        @Override
169        public byte getByte(int offset) {
170            return col.getByte(index, offset);
171        }
172
173        /**
174         * {@inheritDoc}
175         */
176        @Override
177        public short getUnsignedByte(int offset) {
178            return col.getUnsignedByte(index, offset);
179        }
180
181        /**
182         * {@inheritDoc}
183         */
184        @Override
185        public short getShort(int offset) {
186            return col.getShort(index, offset);
187        }
188
189        /**
190         * {@inheritDoc}
191         */
192        @Override
193        public int getUnsignedShort(int offset) {
194            return col.getUnsignedShort(index, offset);
195        }
196
197        /**
198         * {@inheritDoc}
199         */
200        @Override
201        public int getInt(int offset) {
202            return col.getInt(index, offset);
203        }
204
205        /**
206         * {@inheritDoc}
207         */
208        @Override
209        public long getUnsignedInt(int offset) {
210            return col.getUnsignedInt(index, offset);
211        }
212
213        /**
214         * {@inheritDoc}
215         */
216        @Override
217        public long getLong(int offset) {
218            return col.getLong(index, offset);
219        }
220
221        /**
222         * Sets index value
223         *
224         * @param index index value
225         */
226        private void setIndex(long index) {
227            this.index = index;
228        }
229
230        /**
231         * {@inheritDoc}
232         */
233        @Override
234        public String toString() {
235            final StringBuilder sb = new StringBuilder();
236            sb.append("OffHeapStructIndexAccessor");
237            sb.append("{col=").append(col);
238            sb.append(", index=").append(index);
239            sb.append('}');
240            return sb.toString();
241        }
242    }
243
244    /**
245     * Iterable over the data collection using indices from specified array
246     */
247    private static class ReferenceIterable implements OffHeapDisposableIterable<byte[]> {
248        private final OffHeapStructCollection data;
249        private final OffHeapLongArray index;
250
251        /**
252         * Constructor
253         *
254         * @param data data to iterate over
255         * @param index sorted index
256         */
257        private ReferenceIterable(OffHeapStructCollection data, OffHeapLongArray index) {
258            this.data = data;
259            this.index = index;
260        }
261
262        /**
263         * {@inheritDoc}
264         */
265        @Override
266        public OffHeapDisposableIterator<byte[]> iterator() {
267            return new ReferenceIterator(data, index);
268        }
269
270        /**
271         * {@inheritDoc}
272         */
273        @Override
274        public void free() {
275            freeAll(data, index);
276        }
277    }
278
279    /**
280     * Iterator returning data elements in the order specified by indices array
281     */
282    private static class ReferenceIterator implements OffHeapDisposableIterator<byte[]> {
283        private final OffHeapStructCollection data;
284        private final OffHeapLongArray index;
285        private final byte[] buf;
286        private final long size;
287        private long ii = 0;
288
289        /**
290         * Constructor
291         *
292         * @param data data to iterate over
293         * @param index sorted index
294         */
295        private ReferenceIterator(OffHeapStructCollection data, OffHeapLongArray index) {
296            this.data = data;
297            this.index = index;
298            this.buf = new byte[data.structLength()];
299            this.size = index.size();
300        }
301
302        /**
303         * {@inheritDoc}
304         */
305        @Override
306        public long size() {
307            return index.size();
308        }
309
310        /**
311         * {@inheritDoc}
312         */
313        @Override
314        public boolean hasNext() {
315            return ii < size;
316        }
317
318        /**
319         * {@inheritDoc}
320         */
321        @Override
322        public byte[] next() {
323            long ind = index.get(ii);
324            ii += 1;
325            data.get(ind, buf);
326            return buf;
327        }
328
329        /**
330         * {@inheritDoc}
331         */
332        @Override
333        public void remove() {
334            throw new UnsupportedOperationException("remove");
335        }
336
337        /**
338         * {@inheritDoc}
339         */
340        @Override
341        public void free() {
342            freeAll(data, index);
343        }
344
345        /**
346         * {@inheritDoc}
347         */
348        @Override
349        public String toString() {
350            final StringBuilder sb = new StringBuilder();
351            sb.append("ReferenceIterator");
352            sb.append("{data=").append(data);
353            sb.append(", index=").append(index);
354            sb.append(", ii=").append(ii);
355            sb.append('}');
356            return sb.toString();
357        }
358    }
359}