Sign in to follow this  
Telastyn

Functional Programming - generating lists based on values

Recommended Posts

This isn't homework, but [b]is [/b]for learning so I'm looking for help more than a [i]solution[/i].

The problem is I have a timeframe (start/duration) and a list of timefames that represent 'taken' times for something like a schedule/calendar. I'm looking to convert those into a list of 'open' timeframes, and am kinda stuck about how to do that in a nice functional way.

Working in F# if it matters.

Share this post


Link to post
Share on other sites
I'd say this problem is slightly trickier than it looks at first.

An elegant way to do this is to define a closed algebra on intervals with the operations union, complement and intersection: you can formulate your problem as intersection(big_timeframe, complement(union(taken_timeframes))).

This can be done in an optimal way in a functional language using scanline-type algorithms on lists, or slightly less optimally and more clearly using the scanline idea and an intermediate datastructure that partitions the intervals into disjoint subintervals pointing to their containing parent intervals. I'd opt for the latter.

You can build these operations easily using the following method:

Notation: {A, B} is a tuple representing an interval, A <= B. {} means tuple, [] means list.

1) Decompose intervals into [{Endpoint, Parent_interval}, ...]. Eg. the interval {A, B} is decomposed into the list [{A, {A, B}}, {B, {A, B}}].

2) Sort this based on Endpoint.

3) Use these endpoints to build disjoint subintervals which know their containing parent intervals, your datastructure is [{Subinterval, Parent_intervals_set}, ...]. 2) and 3) is basically a 1-d scanline algorithm.

4) Find the subintervals that satisfy your predicate (union, intersection, complement). For example, union simply means find subintervals whose Parent_interval_set is nonempty. The filter hof is useful for expressing these.

5) Merge contiguous subintervals.

6) ???

7) Profit.


This can be optimized by writing union, intersection and complement directly without going through
the subintervals indirection, but that's wordier and trickier.

Share this post


Link to post
Share on other sites
I must say, that wasn't very clear, and while I think I completely missed what you were trying to say (and suspect that simple set operations won't work on continuous timeframes without re-implementing essentially this code) it did kind of nudge me towards breaking the timeframe into progressively smaller ones rather than filling a collection of results.

Anyways, this slapdash newb F# appears to do what I was looking for. Critiques and criticisms are certainly welcome.
[code]
type event = {
start:int
duration:int
}
with override this.ToString() = System.String.Format("start: {0}, duration: {1}",this.start,this.duration)



let endOf a =
a.start + a.duration

let containedIn a b =
if b.start <= a.start && endOf b >= endOf a then true else false

let collidesWith a b =
if (a.start >= b.start && a.start < endOf B) then true
elif (endOf a > b.start && endOf a < endOf B) then true
else false

let nextOpenTime timeframe events =
List.min ((endOf timeframe) :: (List.filter (fun x -> List.forall (fun y -> not (collidesWith {start=x;duration=0} y)) events) (List.filter (fun i -> i >= timeframe.start) [timeframe.start..endOf timeframe])))

let rec openSlots timeframe events =
let result = {start = timeframe.start; duration =
match List.minBy (fun i -> i.start) (List.filter (fun i -> i.start >= timeframe.start) events @ [{start = endOf timeframe; duration = (endOf timeframe - timeframe.start)}]) with
| y when y.start = endOf timeframe -> timeframe.duration
| x -> x.start-timeframe.start
}

if endOf result = endOf timeframe
then if result.duration = 0 then [] else [result]
else
let x = nextOpenTime {start = endOf result; duration = endOf timeframe - endOf result} events
if x = endOf timeframe
then if result.duration = 0 then [] else [result]
else if result.duration = 0 then openSlots {start = x; duration = endOf timeframe - x} events
else result :: openSlots {start = x; duration = endOf timeframe - x} events

[/code]

Share this post


Link to post
Share on other sites
You don't have to use an if to return true or false from a boolean espression. You can directly use the boolean expression (negating it in case of need). So

[code]let containedIn a b = if b.start <= a.start && endOf b >= endOf a then true else false[/code]

can be simply written as

[code]let containedIn a b = b.start <= a.start && endOf b >= endOf a[/code]

and so on. This is valid in every language, not just F# (which I actually don't know very well). More trickier is the collidesWith function which may become

[code]let collidesWith a b = (a.start >= b.start && a.start < endOf B) || (endOf a > b.start && endOf a < endOf B)[/code]

Share this post


Link to post
Share on other sites
You're right, I was less than clear. The nudge I expected to give was to look at sweepline algorithms but I wrote scanline instead. Sorry.

I don't know F#, but that algorithm looks quadratic (it seems you're applying min operations to the list for every interval).

Here's another stab at an explanation with accompanying Haskell code.

Suppose you have a list of intervals that contains the occupied intervals AND the interval representing the timeframe.

You can partition the initial, overlapping, set of intervals into a set of disjoint intervals. If these disjoint intervals keep track of how many parent intervals overlap them, you can easily discard those with a > 1 overlap; the remaining intervals are free. This generalises to other interesting interval operations if you keep track of more than number of overlapping parents: this is where I was coming from.

You can accomplish this in O(nlogn) time or O(n) time if you get to use a non-comparison sort like radix sort. HOW you accomplish this is by first decomposing intervals into their endpoints, sorting them, and sweeping over these to generate subintervals and overlap counts.

Once you've done this, all that remains is to filter out those intervals with intersection counts > 1. The same approach works for many other interval-related problems.

[code]
import Data.List

data Interval a = In a a Int deriving ( Show )
data Point a = Pt a Int deriving ( Show )

decompose = concat . map (\(In a b _) -> [Pt a 1, Pt b (-1)])

disjoint [] = []
disjoint (Pt a e:xs) = disjoint_h e a xs

disjoint_h _ _ [] = []
disjoint_h accum a (Pt b e:rest) = In a b accum: disjoint_h (accum + e) b rest

cmp (Pt a _) (Pt b _) = compare a b
prune_empty_intervals = filter (\(In a b _) -> a /= B)

build_disjoint :: [Interval Int] -> [Interval Int]
build_disjoint = prune_empty_intervals . disjoint . (sortBy cmp) . decompose

to_internal = map (\(a, B) -> In a b 1)
from_internal = map (\(In a b accum) -> (a, B))

find_free = from_internal . find_free_h . to_internal
find_free_h intervals = filter (\(In _ _ accum) -> accum == 1) (build_disjoint intervals)
[/code]

So, let's say we have a timeframe of 1 to 10 and a few occupied intervals:

[code]
*Main> find_free [(1, 10), (1,2), (3, 6), (7, 9)]
[(2,3),(6,7),(9,10)]
*Main>
[/code]

edit: removed comments, highlighting makes the code with them harder to read

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this