@Test public void sortTest() throws IOException { DiskBackedList2<TestValue> dbl = new DiskBackedList2<>(codec); try { Random random = new Random(1984); int numEntries = 20000; int[] vals = new int[numEntries]; for (int i = 0; i < numEntries; i++) { vals[i] = random.nextInt(3 * numEntries); } int[] sortedVals = vals.clone(); Arrays.sort(sortedVals); for (int val : vals) { dbl.add(new TestValue(val)); } Comparator<TestValue> comp = new Comparator<TestValue>() { @Override public int compare(TestValue o1, TestValue o2) { return (int) (o1.value - o2.value); } }; dbl.sort(comp); int i = 0; for (TestValue tv : dbl) { Assert.assertEquals(sortedVals[i++], tv.value); } dbl.clear(); } finally { if (dbl != null) { LessFiles.deleteDir(dbl.getDirectory()); } } }
public void sort(final Comparator<? super K> comp) { try { sortEachChunk(comp); if (chunks.size() <= 1) { return; } Comparator<Pair<K, Integer>> pairComp = new Comparator<Pair<K, Integer>>() { @Override public int compare(Pair<K, Integer> e1, Pair<K, Integer> e2) { return comp.compare(e1.getLeft(), e2.getLeft()); } }; PriorityQueue<Pair<K, Integer>> heap = new PriorityQueue<>(chunks.size(), pairComp); ArrayList<Iterator> iterators = new ArrayList<>(chunks.size()); close(); for (int i = 0; i < chunks.size(); i++) { Iterator<K> it = chunks.get(i).getChunkIterator(); iterators.add(i, it); if (it.hasNext()) { K elt = it.next(); if (elt != null) { heap.add(Pair.of(elt, i)); } } } long storageMaxChunkSize = maxChunkSizeBytes / (1 + chunks.size() / 20); DiskBackedList2<K> storage = new DiskBackedList2<>(codec, storageMaxChunkSize, directory); while (!heap.isEmpty()) { Pair<K, Integer> leastElt = heap.poll(); storage.add(leastElt.getLeft()); @SuppressWarnings({"unchecked"}) Iterator<K> polledIterator = iterators.get(leastElt.getRight()); if (polledIterator.hasNext()) { heap.add(Pair.of(polledIterator.next(), leastElt.getRight())); } } storage.close(); chunks = storage.getChunks(); currentChunk = null; } catch (IOException io) { throw Throwables.propagate(io); } }
DiskBackedList2 implements List<K> { public void sort(final Comparator<? super K> comp) { try { sortEachChunk(comp); if (chunks.size() <= 1) { return; } Comparator<Pair<K, Integer>> pairComp = new Comparator<Pair<K, Integer>>() { @Override public int compare(Pair<K, Integer> e1, Pair<K, Integer> e2) { return comp.compare(e1.getLeft(), e2.getLeft()); } }; PriorityQueue<Pair<K, Integer>> heap = new PriorityQueue<>(chunks.size(), pairComp); ArrayList<Iterator> iterators = new ArrayList<>(chunks.size()); close(); for (int i = 0; i < chunks.size(); i++) { Iterator<K> it = chunks.get(i).getChunkIterator(); iterators.add(i, it); if (it.hasNext()) { K elt = it.next(); if (elt != null) { heap.add(Pair.of(elt, i)); } } } long storageMaxChunkSize = maxChunkSizeBytes / (1 + chunks.size() / 20); DiskBackedList2<K> storage = new DiskBackedList2<>(codec, storageMaxChunkSize, directory); while (!heap.isEmpty()) { Pair<K, Integer> leastElt = heap.poll(); storage.add(leastElt.getLeft()); @SuppressWarnings({"unchecked"}) Iterator<K> polledIterator = iterators.get(leastElt.getRight()); if (polledIterator.hasNext()) { heap.add(Pair.of(polledIterator.next(), leastElt.getRight())); } } storage.close(); chunks = storage.getChunks(); currentChunk = null; } catch (IOException io) { throw Throwables.propagate(io); } } }
DiskBackedList2 implements List<K> { public void sort(final Comparator<? super K> comp) { try { sortEachChunk(comp); if (chunks.size() <= 1) { return; } Comparator<Pair<K, Integer>> pairComp = new Comparator<Pair<K, Integer>>() { @Override public int compare(Pair<K, Integer> e1, Pair<K, Integer> e2) { return comp.compare(e1.getLeft(), e2.getLeft()); } }; PriorityQueue<Pair<K, Integer>> heap = new PriorityQueue<>(chunks.size(), pairComp); ArrayList<Iterator> iterators = new ArrayList<>(chunks.size()); close(); for (int i = 0; i < chunks.size(); i++) { Iterator<K> it = chunks.get(i).getChunkIterator(); iterators.add(i, it); if (it.hasNext()) { K elt = it.next(); if (elt != null) { heap.add(Pair.of(elt, i)); } } } long storageMaxChunkSize = maxChunkSizeBytes / (1 + chunks.size() / 20); DiskBackedList2<K> storage = new DiskBackedList2<>(codec, storageMaxChunkSize, directory); while (!heap.isEmpty()) { Pair<K, Integer> leastElt = heap.poll(); storage.add(leastElt.getLeft()); @SuppressWarnings({"unchecked"}) Iterator<K> polledIterator = iterators.get(leastElt.getRight()); if (polledIterator.hasNext()) { heap.add(Pair.of(polledIterator.next(), leastElt.getRight())); } } storage.close(); chunks = storage.getChunks(); currentChunk = null; } catch (IOException io) { throw Throwables.propagate(io); } } DiskBackedList2(ItemCodec<K> codec);  DiskBackedList2(ItemCodec<K> codec, long maxChunkSizeBytes, File directory); }
DiskBackedList2 implements List<K> { public void sort(final Comparator<? super K> comp) { try { sortEachChunk(comp); if (chunks.size() <= 1) { return; } Comparator<Pair<K, Integer>> pairComp = new Comparator<Pair<K, Integer>>() { @Override public int compare(Pair<K, Integer> e1, Pair<K, Integer> e2) { return comp.compare(e1.getLeft(), e2.getLeft()); } }; PriorityQueue<Pair<K, Integer>> heap = new PriorityQueue<>(chunks.size(), pairComp); ArrayList<Iterator> iterators = new ArrayList<>(chunks.size()); close(); for (int i = 0; i < chunks.size(); i++) { Iterator<K> it = chunks.get(i).getChunkIterator(); iterators.add(i, it); if (it.hasNext()) { K elt = it.next(); if (elt != null) { heap.add(Pair.of(elt, i)); } } } long storageMaxChunkSize = maxChunkSizeBytes / (1 + chunks.size() / 20); DiskBackedList2<K> storage = new DiskBackedList2<>(codec, storageMaxChunkSize, directory); while (!heap.isEmpty()) { Pair<K, Integer> leastElt = heap.poll(); storage.add(leastElt.getLeft()); @SuppressWarnings({"unchecked"}) Iterator<K> polledIterator = iterators.get(leastElt.getRight()); if (polledIterator.hasNext()) { heap.add(Pair.of(polledIterator.next(), leastElt.getRight())); } } storage.close(); chunks = storage.getChunks(); currentChunk = null; } catch (IOException io) { throw Throwables.propagate(io); } } DiskBackedList2(ItemCodec<K> codec);  DiskBackedList2(ItemCodec<K> codec, long maxChunkSizeBytes, File directory); void setCodec(ItemCodec<K> codec); String toString(); @Override boolean add(K element); @Override /** * This function adds an element to a particular location. * TODO does not presently respect maxChunkSize */ void add(int elementIndex, K element); @Override boolean addAll(Collection<? extends K> c); @Override boolean addAll(int index, Collection<? extends K> c); @Override void clear(); @Override boolean contains(Object o); @Override boolean containsAll(Collection<?> c); @Override K get(int elementIndex); @Override int indexOf(Object o); @Override boolean isEmpty(); @Override Iterator<K> iterator(); @Override int lastIndexOf(Object o); @Override ListIterator<K> listIterator(); @Override ListIterator<K> listIterator(final int ind); @Override boolean remove(Object o); @Override K remove(int elementIndex); @Override boolean removeAll(Collection<?> c); @Override boolean retainAll(Collection<?> c); @Override K set(int elementIndex, K element); @Override int size(); @Override List<K> subList(int fromIndex, int toIndex); @Override Object[] toArray(); @Override T[] toArray(T[] a); void close(); void sort(final Comparator<? super K> comp); void addEncodedData(Iterator<byte[]> stream); Iterator<byte[]> getEncodedData(); void loadAllChunksFromDirectory(); void saveAllChunksToDirectory(); File getDirectory(); }
DiskBackedList2 implements List<K> { public void sort(final Comparator<? super K> comp) { try { sortEachChunk(comp); if (chunks.size() <= 1) { return; } Comparator<Pair<K, Integer>> pairComp = new Comparator<Pair<K, Integer>>() { @Override public int compare(Pair<K, Integer> e1, Pair<K, Integer> e2) { return comp.compare(e1.getLeft(), e2.getLeft()); } }; PriorityQueue<Pair<K, Integer>> heap = new PriorityQueue<>(chunks.size(), pairComp); ArrayList<Iterator> iterators = new ArrayList<>(chunks.size()); close(); for (int i = 0; i < chunks.size(); i++) { Iterator<K> it = chunks.get(i).getChunkIterator(); iterators.add(i, it); if (it.hasNext()) { K elt = it.next(); if (elt != null) { heap.add(Pair.of(elt, i)); } } } long storageMaxChunkSize = maxChunkSizeBytes / (1 + chunks.size() / 20); DiskBackedList2<K> storage = new DiskBackedList2<>(codec, storageMaxChunkSize, directory); while (!heap.isEmpty()) { Pair<K, Integer> leastElt = heap.poll(); storage.add(leastElt.getLeft()); @SuppressWarnings({"unchecked"}) Iterator<K> polledIterator = iterators.get(leastElt.getRight()); if (polledIterator.hasNext()) { heap.add(Pair.of(polledIterator.next(), leastElt.getRight())); } } storage.close(); chunks = storage.getChunks(); currentChunk = null; } catch (IOException io) { throw Throwables.propagate(io); } } DiskBackedList2(ItemCodec<K> codec);  DiskBackedList2(ItemCodec<K> codec, long maxChunkSizeBytes, File directory); void setCodec(ItemCodec<K> codec); String toString(); @Override boolean add(K element); @Override /** * This function adds an element to a particular location. * TODO does not presently respect maxChunkSize */ void add(int elementIndex, K element); @Override boolean addAll(Collection<? extends K> c); @Override boolean addAll(int index, Collection<? extends K> c); @Override void clear(); @Override boolean contains(Object o); @Override boolean containsAll(Collection<?> c); @Override K get(int elementIndex); @Override int indexOf(Object o); @Override boolean isEmpty(); @Override Iterator<K> iterator(); @Override int lastIndexOf(Object o); @Override ListIterator<K> listIterator(); @Override ListIterator<K> listIterator(final int ind); @Override boolean remove(Object o); @Override K remove(int elementIndex); @Override boolean removeAll(Collection<?> c); @Override boolean retainAll(Collection<?> c); @Override K set(int elementIndex, K element); @Override int size(); @Override List<K> subList(int fromIndex, int toIndex); @Override Object[] toArray(); @Override T[] toArray(T[] a); void close(); void sort(final Comparator<? super K> comp); void addEncodedData(Iterator<byte[]> stream); Iterator<byte[]> getEncodedData(); void loadAllChunksFromDirectory(); void saveAllChunksToDirectory(); File getDirectory();  }