1 /* 2 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package java.util.stream; 26 27 import java.util.HashSet; 28 import java.util.LinkedHashSet; 29 import java.util.Objects; 30 import java.util.Set; 31 import java.util.Spliterator; 32 import java.util.concurrent.ConcurrentHashMap; 33 import java.util.concurrent.atomic.AtomicBoolean; 34 import java.util.function.IntFunction; 35 36 /** 37 * Factory methods for transforming streams into duplicate-free streams, using 38 * {@link Object#equals(Object)} to determine equality. 39 * 40 * @since 1.8 41 */ 42 final class DistinctOps { 43 DistinctOps()44 private DistinctOps() { } 45 46 /** 47 * Appends a "distinct" operation to the provided stream, and returns the 48 * new stream. 49 * 50 * @param <T> the type of both input and output elements 51 * @param upstream a reference stream with element type T 52 * @return the new stream 53 */ makeRef(AbstractPipeline<?, T, ?> upstream)54 static <T> ReferencePipeline<T, T> makeRef(AbstractPipeline<?, T, ?> upstream) { 55 return new ReferencePipeline.StatefulOp<T, T>(upstream, StreamShape.REFERENCE, 56 StreamOpFlag.IS_DISTINCT | StreamOpFlag.NOT_SIZED) { 57 58 <P_IN> Node<T> reduce(PipelineHelper<T> helper, Spliterator<P_IN> spliterator) { 59 // If the stream is SORTED then it should also be ORDERED so the following will also 60 // preserve the sort order 61 TerminalOp<T, LinkedHashSet<T>> reduceOp 62 = ReduceOps.<T, LinkedHashSet<T>>makeRef(LinkedHashSet::new, LinkedHashSet::add, 63 LinkedHashSet::addAll); 64 return Nodes.node(reduceOp.evaluateParallel(helper, spliterator)); 65 } 66 67 @Override 68 // Android-changed: Make public, to match the method it's overriding. 69 public <P_IN> Node<T> opEvaluateParallel(PipelineHelper<T> helper, 70 Spliterator<P_IN> spliterator, 71 IntFunction<T[]> generator) { 72 if (StreamOpFlag.DISTINCT.isKnown(helper.getStreamAndOpFlags())) { 73 // No-op 74 return helper.evaluate(spliterator, false, generator); 75 } 76 else if (StreamOpFlag.ORDERED.isKnown(helper.getStreamAndOpFlags())) { 77 return reduce(helper, spliterator); 78 } 79 else { 80 // Holder of null state since ConcurrentHashMap does not support null values 81 AtomicBoolean seenNull = new AtomicBoolean(false); 82 ConcurrentHashMap<T, Boolean> map = new ConcurrentHashMap<>(); 83 TerminalOp<T, Void> forEachOp = ForEachOps.makeRef(t -> { 84 if (t == null) 85 seenNull.set(true); 86 else 87 map.putIfAbsent(t, Boolean.TRUE); 88 }, false); 89 forEachOp.evaluateParallel(helper, spliterator); 90 91 // If null has been seen then copy the key set into a HashSet that supports null values 92 // and add null 93 Set<T> keys = map.keySet(); 94 if (seenNull.get()) { 95 // TODO Implement a more efficient set-union view, rather than copying 96 keys = new HashSet<>(keys); 97 keys.add(null); 98 } 99 return Nodes.node(keys); 100 } 101 } 102 103 @Override 104 // Android-changed: Make public, to match the method it's overriding. 105 public <P_IN> Spliterator<T> opEvaluateParallelLazy(PipelineHelper<T> helper, Spliterator<P_IN> spliterator) { 106 if (StreamOpFlag.DISTINCT.isKnown(helper.getStreamAndOpFlags())) { 107 // No-op 108 return helper.wrapSpliterator(spliterator); 109 } 110 else if (StreamOpFlag.ORDERED.isKnown(helper.getStreamAndOpFlags())) { 111 // Not lazy, barrier required to preserve order 112 return reduce(helper, spliterator).spliterator(); 113 } 114 else { 115 // Lazy 116 return new StreamSpliterators.DistinctSpliterator<>(helper.wrapSpliterator(spliterator)); 117 } 118 } 119 120 @Override 121 // Android-changed: Make public, to match the method it's overriding. 122 public Sink<T> opWrapSink(int flags, Sink<T> sink) { 123 Objects.requireNonNull(sink); 124 125 if (StreamOpFlag.DISTINCT.isKnown(flags)) { 126 return sink; 127 } else if (StreamOpFlag.SORTED.isKnown(flags)) { 128 return new Sink.ChainedReference<T, T>(sink) { 129 boolean seenNull; 130 T lastSeen; 131 132 @Override 133 public void begin(long size) { 134 seenNull = false; 135 lastSeen = null; 136 downstream.begin(-1); 137 } 138 139 @Override 140 public void end() { 141 seenNull = false; 142 lastSeen = null; 143 downstream.end(); 144 } 145 146 @Override 147 public void accept(T t) { 148 if (t == null) { 149 if (!seenNull) { 150 seenNull = true; 151 downstream.accept(lastSeen = null); 152 } 153 } else if (lastSeen == null || !t.equals(lastSeen)) { 154 downstream.accept(lastSeen = t); 155 } 156 } 157 }; 158 } else { 159 return new Sink.ChainedReference<T, T>(sink) { 160 Set<T> seen; 161 162 @Override 163 public void begin(long size) { 164 seen = new HashSet<>(); 165 downstream.begin(-1); 166 } 167 168 @Override 169 public void end() { 170 seen = null; 171 downstream.end(); 172 } 173 174 @Override 175 public void accept(T t) { 176 if (!seen.contains(t)) { 177 seen.add(t); 178 downstream.accept(t); 179 } 180 } 181 }; 182 } 183 } 184 }; 185 } 186 } 187