Suggestion for Data Structure regarding Timetabling and Time Intervals

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Suggestion for Data Structure regarding Timetabling and Time Intervals

Michael Roth
I would like to experiment with timetabling algorithms and resource
scheduling in a special use case: I have time intervals like A, B and C
and they are put sequentially on a time line.
However, between the major time intervals like A, B etc. their are
always "minor" time intervals which separates the major ones. For example:

     a, A, ab, B, bc, C, c

Upper case letters denotes "major" time intervals and lower case letters
denotes the minor intervals which always separates the major ones.

The minor time intervals only have a duration, their exact occurrence in
time doesn't matter, only the fact that they occur between the major
time intervals are important.
The major time intervals start and stop a specific time; they don't
overlap and maybe there is free time between major and/or minor time
intervals.
The minor time intervals "a" and "b" at the beginning and ending of the
complete time line I'm not interested in and can be omitted completely.


Say, to insert a time interval X after B, assuming there is enough free
time between B and C, the resulting structure is:

     a, A, ab, B, bx, X, xc, C, c

The minor time interval "bc" is discarded and two new minor time
intervals "bx" and "xc" are inserted.


I'm a little bit stuck what a good data structure would be for this
problem. Additionally I would like to use an infinite data structure,
because a priori I don't know how many time intervals have to be created
and inserted into the time line.
The time intervals are not generated in an ascending order. An algorithm
will search for possible places to insert the new created major time
intervals and creates the corresponding minor time intervals.
There is the concept of a "present time" in this process. The algorithm
can only manipulate the future. I thought to push all time intervals in
the past respective to this "present time" to a MonadWriter to get my
infinite list of time intervals. The "present time" is moved forward at
specific events.


What do you experts think about the approach with the MonadWriter? What
would be a good data structure to ensure that all major time intervals
are separated by minor time intervals?


Thank you in advance for your ideas and comments,


Michael Roth


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Suggestion for Data Structure regarding Timetabling and Time Intervals

Olaf Klinke
Dear Michael,

if you can be sure your intervals will never overlap, why not use a binary search tree, such as Data.Set from containers? You could make a data structure distinguishing major and minor intervals such as:

type Time = -- your favourite totally ordered time type
data Major = Major {
  fromTime :: Time,
  untilTime :: Time} deriving (Eq)
data Minor = Minor {
  after :: Time
  before :: Time} deriving (Eq)
type TimeInterval = Either Minor Major

instance Ord (Either Minor Major) where
   Left  a <= Left  b = before a <= after b
   Right a <= Right b = untilTime a <= fromTime b
   Left  a <= Right b = before a <= fromTime b
   Right a <= Left  b = untilTime a <= after b

If I understood your intentions correctly, inserting a minor interval between a :: Major and b :: Major where a < b would mean to insert

Minor {after = untilTime a, before = fromTime b}

It might also be handy to define a new type (isomorphic to the product (a,b))

Anno a b = Anno a b

whose Ord instance uses the Ord instance of b only, so that

Anno "Some annotation" (Major t0 t1)

is an interval bearing some annotation that can be ordered just like the Major type.

If your intervals _do_ overlap, then two intervals can be in six different configurations (instead of LT, GT and EQ), and several tree structures exist that support some operations more or less efficiently. Bioinformatics and geometry has developed good data structures and algorithms to deal with efficient overlap searches.

Olaf
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Suggestion for Data Structure regarding Timetabling and Time Intervals

Dominic Steinitz-2
In reply to this post by Michael Roth
I don’t know if this is relevant but for manipulating time intervals, I have found the intervals package very useful.

> Message: 5
> Date: Wed, 2 Nov 2016 21:26:32 +0100
> From: Olaf Klinke <[hidden email]>
> To: [hidden email]
> Cc: [hidden email]
> Subject: Re: [Haskell-cafe] Suggestion for Data Structure regarding
> Timetabling and Time Intervals
> Message-ID: <[hidden email]>
> Content-Type: text/plain; charset=us-ascii
>
> Dear Michael,
>
> if you can be sure your intervals will never overlap, why not use a binary search tree, such as Data.Set from containers? You could make a data structure distinguishing major and minor intervals such as:
>
> type Time = -- your favourite totally ordered time type
> data Major = Major {
>  fromTime :: Time,
>  untilTime :: Time} deriving (Eq)
> data Minor = Minor {
>  after :: Time
>  before :: Time} deriving (Eq)
> type TimeInterval = Either Minor Major
>
> instance Ord (Either Minor Major) where
>   Left  a <= Left  b = before a <= after b
>   Right a <= Right b = untilTime a <= fromTime b
>   Left  a <= Right b = before a <= fromTime b
>   Right a <= Left  b = untilTime a <= after b
>
> If I understood your intentions correctly, inserting a minor interval between a :: Major and b :: Major where a < b would mean to insert
>
> Minor {after = untilTime a, before = fromTime b}
>
> It might also be handy to define a new type (isomorphic to the product (a,b))
>
> Anno a b = Anno a b
>
> whose Ord instance uses the Ord instance of b only, so that
>
> Anno "Some annotation" (Major t0 t1)
>
> is an interval bearing some annotation that can be ordered just like the Major type.
>
> If your intervals _do_ overlap, then two intervals can be in six different configurations (instead of LT, GT and EQ), and several tree structures exist that support some operations more or less efficiently. Bioinformatics and geometry has developed good data structures and algorithms to deal with efficient overlap searches.
>
> Olaf
>
>

Dominic Steinitz
[hidden email]
http://idontgetoutmuch.wordpress.com

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.