1 /** 2 Creates a range of values not included in the other given ranges. 3 */ 4 module ddash.algorithm.difference; 5 6 /// 7 unittest { 8 import std.algorithm: map; 9 assert([1, 2, 3].difference([1], 3).equal([2])); 10 11 import std.math: ceil; 12 assert([2.1, 2.4, 1.2, 2.9].difference!ceil([2.3, 0.1]).equal([1.2])); 13 assert([2.1, 2.4, 1.2, 2.9].difference!((a, b) => ceil(a) < ceil(b))([2.3, 3.4]).equal([1.2])); 14 15 struct A { 16 int value; 17 } 18 19 assert([A(1), A(2), A(3)].difference!((a, b) => a.value < b.value)([A(2), A(3)]).equal([A(1)])); 20 } 21 22 import ddash.common; 23 24 private template isRangeOverValidPredicate(alias pred, Range) if (from!"std.range".isInputRange!Range) { 25 import bolts.traits: isNullType, isUnaryOver, isBinaryOver; 26 import std.range: ElementType; 27 enum isRangeOverValidPredicate = isNullType!pred || isUnaryOver!(pred, ElementType!Range) || isBinaryOver!(pred, ElementType!Range); 28 } 29 30 private template isSortednessValid(R1, R2, string byMember, alias pred) { 31 import bolts.traits: isNullType; 32 import bolts.range: isSortedRange; 33 enum isSortednessValid = byMember.length == 0 && isNullType!pred && isSortedRange!R1 && isSortedRange!R2; 34 } 35 36 struct Difference(string member, alias pred, R1, R2) { 37 import bolts.range: CommonTypeOfRanges; 38 39 private R1 r1; 40 private R2 r2; 41 42 alias E = CommonTypeOfRanges!(R1, R2); 43 44 private void moveToNextElement() { 45 import bolts.traits: isBinaryOver, isNullType; 46 import bolts.range: isSortedRange; 47 import std.range: empty, front, popFront; 48 49 static if (isSortednessValid!(R1, R2, member, pred)) { 50 import bolts.range: sortingPredicate; 51 52 alias cmp = (a, b) => sortingPredicate!R1(a, b); 53 54 while (!r1.empty && !r2.empty) { 55 if (cmp(r1.front, r2.front)) { 56 break; 57 } 58 if (cmp(r2.front, r1.front)) { 59 while (!r2.empty && cmp(r2.front, r1.front)) r2.popFront; 60 continue; 61 } 62 r1.popFront; 63 } 64 } else { 65 import std.algorithm: canFind; 66 import ddash.algorithm: equalBy; 67 68 static if (isBinaryOver!(pred, E)) { 69 import ddash.functional: lt; 70 alias eq = (a, b) => equalBy!(member, lt!pred)(a, b); 71 } else { 72 alias eq = (a, b) => equalBy!(member, pred)(a, b); 73 } 74 75 while (!this.r1.empty && this.r2.canFind!eq(this.r1.front)) { 76 this.r1.popFront; 77 } 78 } 79 } 80 81 this(R1 r1, R2 r2) { 82 this.r1 = r1; 83 this.r2 = r2; 84 this.moveToNextElement; 85 } 86 87 bool empty() @property { 88 import std.range: empty; 89 return this.r1.empty; 90 } 91 auto front() @property { 92 import std.range: front; 93 return this.r1.front; 94 } 95 void popFront() { 96 import std.range: popFront; 97 this.r1.popFront; 98 this.moveToNextElement; 99 } 100 } 101 102 /** 103 Creates a range of values not included in the other given ranges. 104 105 You may pass in a unary or binary predicate. If a unary predicate is passed in, then a 106 transformation will be appled to each element before comparing. If a binary predicate is 107 passed in, it must be a comparator predicate that returns true if if a < b. 108 109 If `pred` is null or unary, and the range is sortable, a sort is applied followed by an 110 optimized linear algorithm. If the range is already sorted and `pred` is null, then the linear algorithm 111 is just used with the sorted rang's $(DDOX_NAMED_REF range.sortingpredicate, `sorting predicate`). 112 113 Params: 114 pred = unary transformation or binary comparator 115 range = the range to inspect 116 values = ranges or single values to exclude 117 118 Returns: 119 New array of filtered results. If `Rs` is empty, then `range` is returned 120 121 Since: 122 0.0.1 123 */ 124 auto difference(alias pred = null, Range, Rs...)(Range range, Rs values) if (isRangeOverValidPredicate!(pred, Range)) { 125 return differenceBase!("", pred)(range, values); 126 } 127 128 /// 129 unittest { 130 assert([1, 2, 3].difference([0, 1, 2]).equal([3])); 131 assert([1, 2, 3].difference([1, 2]).equal([3])); 132 assert([1, 2, 3].difference([1], 2).equal([3])); 133 assert([1, 2, 3].difference([1], [3]).equal([2])); 134 assert([1, 2, 3].difference(3).equal([1, 2])); 135 } 136 137 /// 138 unittest { 139 // Implicitly convertible elements ok 140 assert([1.0, 2.0].difference(2).equal([1.0])); 141 142 // Implicitly convertible ranges ok 143 assert([1.0, 2.0].difference([2]).equal([1.0])); 144 145 // Non implicily convertible elements not ok 146 static assert(!__traits(compiles, [1].difference(1.0))); 147 148 // Non implicily convertible range not ok 149 static assert(!__traits(compiles, [1].difference([1.0]))); 150 } 151 152 /// 153 unittest { 154 import std.math: ceil; 155 assert([2.1, 1.2].difference!ceil([2.3, 3.4]).equal([1.2])); 156 assert([9, 2, 3, 2, 3, 9].difference([7, 3, 1, 5]).equal([2, 2, 9, 9])); 157 } 158 159 /** 160 Same as `difference` except you can make it operatete on a publicly accessible member of ElementType!Range 161 162 Params: 163 member = which member in `ElementType!Range` to find difference over 164 pred = unary transformation or binary comparator 165 range = the range to inspect 166 values = ranges or single values to exclude 167 168 SeeAlso: 169 `difference` 170 171 Since: 172 0.0.1 173 */ 174 auto differenceBy(string member, alias pred = null, Range, Rs...)(Range range, Rs values) if (isRangeOverValidPredicate!(pred, Range)) { 175 return differenceBase!(member, pred)(range, values); 176 } 177 178 /// 179 unittest { 180 struct A { 181 int value; 182 } 183 // with normal difference 184 assert([A(1), A(2), A(3)].difference!((a, b) => a.value < b.value)([A(2), A(3)]).equal([A(1)])); 185 186 // by using the By() version 187 assert([A(1), A(2), A(3)].differenceBy!"value"([A(2), A(3)]).equal([A(1)])); 188 } 189 190 auto differenceBase(string member, alias pred, Range, Values...)(Range range, Values values) 191 if (isRangeOverValidPredicate!(pred, Range) && from!"bolts.traits".areCombinable!(Range, Values)) 192 { 193 static if (!Values.length) { 194 return range; 195 } else { 196 import std.range: ElementType; 197 import ddash.algorithm: concat; 198 import bolts.traits: isBinaryOver, isUnaryOver; 199 import std.meta: Alias; 200 201 auto combinedValues = values.concat; 202 203 alias R1 = Range; 204 alias R2 = typeof(combinedValues); 205 alias E1 = ElementType!R1; 206 alias E2 = ElementType!R2; 207 208 static assert( 209 is(E2 : E1), 210 "Cannot get difference between supplied range of element type `" 211 ~ E1.stringof ~ "` and values of common element type `" ~ E2.stringof ~ "`" 212 ); 213 214 static if (isSortednessValid!(R1, R2, member, pred)) { 215 import bolts.range: sortingPredicate; 216 alias sortPred = sortingPredicate!R1; 217 } else static if (isUnaryOver!(pred, E1)) { 218 alias sortPred = (a, b) => pred(a) < pred(b); 219 } else static if (isBinaryOver!(pred, E1, E2)) { 220 alias sortPred = pred; 221 } else { 222 alias sortPred = (a, b) => a < b; 223 } 224 225 import ddash.algorithm: maybeSortBy; 226 auto r1 = maybeSortBy!(member, sortPred)(range); 227 auto r2 = maybeSortBy!(member, sortPred)(combinedValues); 228 229 return Difference!(member, pred, typeof(r1), typeof(r2))(r1, r2); 230 } 231 } 232 233 unittest { 234 assert([1, 1, 1, 2, 2, 3].difference(2, 3).equal([1, 1, 1])); 235 assert([1, 1, 1, 2, 2, 3, 3].difference(2, 3).equal([1, 1, 1])); 236 assert([1, 1, 1, 2, 2, 3, 3].difference(3).equal([1, 1, 1, 2, 2])); 237 assert([1, 1, 1, 2, 2, 3, 3].difference(2).equal([1, 1, 1, 3, 3])); 238 assert([1, 1, 1, 2, 2, 3].difference(1, 2).equal([3])); 239 assert([1, 1, 1, 2, 2, 3, 3].difference(1, 2).equal([3, 3])); 240 assert([1, 1, 1, 2, 2, 3].difference(-1, 2).equal([1, 1, 1, 3])); 241 assert([1, 1, 1, 2, 2, 3].difference(7, 1).equal([2, 2, 3])); 242 }