Created
May 18, 2021 19:26
-
-
Save safareli/4bbb90dc66bd824962909a4487389474 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import * as fc from "fast-check"; | |
import { pipe } from "fp-ts/lib/function"; | |
import { | |
fromArray, | |
groupSort, | |
map, | |
NonEmptyArray, | |
} from "fp-ts/lib/NonEmptyArray"; | |
import { Ord, ordDate, ordNumber } from "fp-ts/lib/Ord"; | |
import { | |
chunksOf, | |
comprehension, | |
dropLeft, | |
head, | |
last, | |
snoc, | |
sort, | |
} from "fp-ts/lib/Array"; | |
import { Interval, mergeIntervals } from "../../src/lib/interval"; | |
import { typeIs } from "../../src/lib/ts-utils"; | |
import { isNone, isSome } from "fp-ts/lib/Option"; | |
import { assert, notNull } from "../../src/lib/assert"; | |
type TestCase<T> = { | |
input: NonEmptyArray<Interval<T>>; | |
output: NonEmptyArray<Interval<T>>; | |
}; | |
// Generate test case with many subsequent intervals | |
// | |
// Example input and output | |
// xs: [1,2,3,4] | |
// input: [[1,2], [2,3], [3,4]] | |
// output: [[1,4]] | |
const mkArbitrarySubsequentIntervals = <T>( | |
genMin: fc.Arbitrary<T>, | |
genMiddle: fc.Arbitrary<T>, | |
genMax: fc.Arbitrary<T>, | |
ord: Ord<T> | |
): fc.Arbitrary<TestCase<T>> => { | |
return fc.tuple(genMin, fc.array(genMiddle), genMax).map( | |
([a, xs, b]): TestCase<T> => { | |
const { start, intervals } = sort(ord)(xs).reduce( | |
(acc, x) => ({ | |
start: x, | |
intervals: [...acc.intervals, { start: acc.start, end: x }], | |
}), | |
{ start: a, intervals: typeIs<Interval<T>[]>([]) } | |
); | |
const input = snoc(intervals, { start, end: b }); | |
const output: NonEmptyArray<Interval<T>> = [{ start: a, end: b }]; | |
return { | |
input, | |
output, | |
}; | |
} | |
); | |
}; | |
// Generate test case where there are no overlaps | |
// | |
// Example input and output | |
// xs: [1,2,3,4,5] | |
// input: [[1,2], [3,4]] | |
// output: [[1,2], [3,4]] | |
const mkArbitraryNonOverlappingIntervals = <T>( | |
genVal: fc.Arbitrary<T>, | |
ord: Ord<T> | |
): fc.Arbitrary<TestCase<T>> => { | |
return fc | |
.array(genVal) | |
.map((xs): null | TestCase<T> => { | |
const sortedUniqueValues = groupSort(ord)(xs).map((_) => _[0]); | |
const intervals = chunksOf(2)(sortedUniqueValues) | |
.map((chunk) => | |
chunk[0] != null && chunk[1] != null | |
? { start: chunk[0], end: chunk[1] } | |
: null | |
) | |
.filter(notNull); | |
const intervalsNEA = fromArray(intervals); | |
if (isNone(intervalsNEA)) { | |
return null; | |
} | |
return { | |
input: intervalsNEA.value, | |
output: intervalsNEA.value, | |
}; | |
}) | |
.filter(notNull); | |
}; | |
// Generate test case where there are overlaps | |
// | |
// Example input and output | |
// xs: [3, 4, 2, 1] | |
// input: [[1,3], [2,4]] | |
// output: [1,4] | |
const mkArbitraryOverlappingIntervals = <T>( | |
genVal: fc.Arbitrary<T>, | |
ord: Ord<T> | |
): fc.Arbitrary<TestCase<T>> => { | |
return fc | |
.array(genVal, { minLength: 4 }) | |
.map((xs): null | TestCase<T> => { | |
const sortedValues = sort(ord)(xs); | |
const intervals = comprehension( | |
[sortedValues, dropLeft(2)(sortedValues)], | |
(n, nPlus2) => ({ | |
start: n, | |
end: nPlus2, | |
}) | |
); | |
const headElem = head(sortedValues); | |
const lastElem = last(sortedValues); | |
const intervalsNEA = fromArray(intervals); | |
assert( | |
isSome(headElem) && isSome(lastElem) && isSome(intervalsNEA), | |
"isSome(headElem) && isSome(lastElem) && isSome(intervalsNEA)" | |
); | |
const output: NonEmptyArray<Interval<T>> = [ | |
{ start: headElem.value, end: lastElem.value }, | |
]; | |
return { | |
input: intervalsNEA.value, | |
output, | |
}; | |
}) | |
.filter(notNull); | |
}; | |
const minNum = 0; | |
const maxNum = 100; | |
const genNum = fc.integer({ min: minNum, max: maxNum }); | |
const minDate = new Date(1995, 11, 17, 3, 24, 0); | |
const maxDate = new Date(2030, 11, 17, 3, 24, 0); | |
const genDate = fc.date({ min: minDate, max: maxDate }); | |
const test = <T>(name: string, gen: fc.Arbitrary<TestCase<T>>, ord: Ord<T>) => { | |
it(name, () => { | |
fc.assert( | |
fc.property(gen, (_) => { | |
expect(mergeIntervals(ord, _.output)).toEqual(_.output); | |
}) | |
); | |
}); | |
}; | |
describe("Interval", () => { | |
describe("mergeIntervals", () => { | |
it("example 1", () => { | |
expect( | |
mergeIntervals(ordNumber, [ | |
{ start: 1, end: 3 }, | |
{ start: 2, end: 6 }, | |
{ start: 8, end: 10 }, | |
{ start: 15, end: 18 }, | |
]) | |
).toEqual([ | |
{ start: 1, end: 6 }, | |
{ start: 8, end: 10 }, | |
{ start: 15, end: 18 }, | |
]); | |
// Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. | |
}); | |
it("example 2", () => { | |
expect( | |
mergeIntervals(ordNumber, [ | |
{ start: 1, end: 4 }, | |
{ start: 4, end: 5 }, | |
]) | |
).toEqual([{ start: 1, end: 5 }]); | |
// Explanation: Intervals [1,4] and [4,5] are considered overlapping. | |
}); | |
test( | |
"Subsequent Intervals: Num", | |
mkArbitrarySubsequentIntervals( | |
fc.constant(minNum), | |
genNum, | |
fc.constant(maxNum), | |
ordNumber | |
), | |
ordNumber | |
); | |
test( | |
"Subsequent Intervals: Date", | |
mkArbitrarySubsequentIntervals( | |
fc.constant(minDate), | |
genDate, | |
fc.constant(maxDate), | |
ordDate | |
), | |
ordDate | |
); | |
test( | |
"Non Overlapping Intervals: Num", | |
mkArbitraryNonOverlappingIntervals(genNum, ordNumber), | |
ordNumber | |
); | |
test( | |
"Non Overlapping Intervals: Date", | |
mkArbitraryNonOverlappingIntervals(genDate, ordDate), | |
ordDate | |
); | |
test( | |
"Overlapping Intervals: Num", | |
mkArbitraryOverlappingIntervals(genNum, ordNumber), | |
ordNumber | |
); | |
test( | |
"Overlapping Intervals: Date", | |
mkArbitraryOverlappingIntervals(genDate, ordDate), | |
ordDate | |
); | |
}); | |
}); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import { snoc } from "fp-ts/lib/Array"; | |
import { NonEmptyArray, sort, uncons } from "fp-ts/lib/NonEmptyArray"; | |
import * as Ord from "fp-ts/lib/Ord"; | |
import { reduceNEA } from "./non-empty-array"; | |
/** | |
* Interval is generic representation of anything that has start and end | |
* It could be date/time/datetime interval or it could be range between numbers etc. | |
*/ | |
export type Interval<T> = { | |
start: T; | |
end: T; | |
}; | |
/** | |
* Merge intervals of any type `T` together. | |
* If the Interval overlap then combine them into a single `Interval` | |
* otherwise add them separately to the returned array | |
*/ | |
export const mergeIntervals = <T>( | |
ord: Ord.Ord<T>, | |
intervals: NonEmptyArray<Interval<T>> | |
): NonEmptyArray<Interval<T>> => { | |
const lessThenOrEqual = Ord.leq(ord); | |
const maximum = Ord.max(ord); | |
const equals = ord.equals; | |
const ordByStart = Ord.contramap((a: Interval<T>) => a.start)(ord); | |
const sortedByStart = sort(ordByStart)(intervals); | |
const x = reduceNEA( | |
sortedByStart, | |
(val) => { | |
// NOTE: Linked List could be used here to make this super efficient | |
const init: Interval<T>[] = []; | |
return { | |
current: val, | |
init, | |
}; | |
}, | |
(acc, val) => { | |
if ( | |
equals(acc.current.start, val.start) || | |
lessThenOrEqual(val.start, acc.current.end) | |
) { | |
const current: Interval<T> = { | |
start: acc.current.start, | |
end: maximum(acc.current.end, val.end), | |
}; | |
return { | |
current, | |
init: acc.init, | |
}; | |
} | |
const last: Interval<T> = { | |
start: acc.current.start, | |
end: acc.current.end, | |
}; | |
return { | |
current: val, | |
init: [...acc.init, last], | |
}; | |
} | |
); | |
return snoc(x.init, x.current); | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment