# scalendar: Haskell Library to deal with resource availability in a Calendar.
[](https://travis-ci.org/stackbuilders/scalendar)
This is a library for handling calendars and resource availability based on the
`top-nodes algorithm` and set operations. That's why it is called `scalendar`: Calendars
which which keep track of the availability of a set of resources.
Since the bare `top-nodes algorithm` is not enough to IDENTIFY which are the
specific resources which are available in a given period of time - for example,
the id of the rooms which can still be reserved in a given `(checkIn-checkOut)`
interval - it was necessary to generalize that algorithm to work on sets of
strings which identify the available resources in a period. That generalization
was pretty smooth since addition in numbers was replaced by set Union and substraction
in numbers was replaced by set Difference. Another important fact about sets is that
they do not allow duplicates, so every identifier is guaranteed to be unique.
# Introduction
# Data Types
`scalendar` is a library based on binary trees, where a Calendar is defined as follows:
```
data Calendar =
Unit TimePeriod (Set Text) (Set Text)
| Node TimePeriod (Set Text) (Set Text) Calendar Calendar
data TimePeriod =
TimeInterval UTCTime UTCTime
| TimeUnit UTCTime
```
The idea is that each node in the calendar will store a TimePeriod which is a data type which stores
a time-interval with an`start-date` and an `end-date`.
The purpose is that terminal nodes (leaves) will represent a unit of time, `TimeUnit`, which in this case
is a nominal day or 86400 seconds. Thus non-terminal nodes are intended to store a `TimeInterval` and
leaves are intended to store `TimeUnits`. Both leaves and nodes store `Q` and `QN` sets, which are the
data structures which allow the Calendar to keep track of the availability of a set of resources.
For more information about the time representation according to the `top-nodes`
algorithm check [this](https://en.wikipedia.org/wiki/Top-nodes_algorithm)
Knowing what the `Q` and `QN` sets mean is not quite important to use this library but
roughly:
- `QN(Node)` represents reserved elements for all reservations having this node as `top-node`
- `Q(Node) = U(Q(LeftChild), Q(RightChild)) U QN(Node)`
In order to use this library, it only suffices to know the meaning of the following
data type:
```
data SCalendar = SCalendar
{ calUnits :: Set Text
, calendar :: Calendar
} deriving (Eq, Show)
```
An `SCalendar` is only a product type of a set of identifiers and a group of available resources - for
example, the numbers which are used to identify rooms in a hotel `{"101", "102", ...}` - and a `Calendar`,
which is the tree that keeps track of the availability of that set of resources.
Other important data types are:
- ```
data Reservation = Reservation
{ reservUnits :: Set Text
, reservPeriod :: TimePeriod
}
```
which represents a set of resources we want to reserve over a `TimePeriod` in a `SCalendar`.
- ```
data Cancellation = Cancellation
{ cancUnits :: Set Text
, cancPeriod :: TimePeriod
}
```
which represents a set of resources we want to cancel over a `TimePeriod` in a `SCalendar`
- ```
data Report = Report
{ reportPeriod :: TimePeriod
, totalUnits :: Set Text
, reservedUnits :: Set Text
, remainingUnits :: Set Text
}
```
which represents a `Report` for a given `TimePeriod` where a `Report` has the following
information:
- `totalUnits`: The set of total identifiers for resources which can be reserved in a
`SCalendar`.
- `reservedUnits`: The set of identifiers for resources which have been reserved for a `TimePeriod`.
- `remainingUnits`: The set of remaining identifiers for resources which can still be
reserved without creating conflicts in a `TimePeriod`.
# Creating a Calendar
Functions to create Calendars are located in `Time.SCalendar.Types`
To create a bare `Calendar` which is not associated to any set of identifiers we can use
```
createCalendar :: Integer -- Year.
-> Int -- Month.
-> Int -- Day.
-> Int -- NumDays.
-> Maybe Calendar
```
where
- `Year`: It is an `Integer` representing the starting year of the `Calendar`. For example
`2017`.
- `Month`: It is an `Int` representing the starting month of the `Calendar`. For
example, `2` is equivalent to February.
- `Day`: It is an `Int` representing the starting day of the `Calendar`. It can be
any number representing one of the days of `Month`.
- `NumDays`: It is the number of Days we want our `Calendar` to cover. The days covered
by it will always be a power of `2`. Thus if you input `30`, `createCalendar` will
find the first power of `2` which is greater or equal to `32`, in this case `2^5 = 32`.
So if everything is ok, this function `Just` returns a new `Calendar` which is suitable for
the given `NumDays`. A new `Calendar` is one which has neither reservations nor cancellations.
`createSCalendar` is almost like `createCalendar` but instead of returning a bare `Calendar`,
it returns an `SCalendar` which is a `Calendar` together with a set of identifiers (of type `Text`)
which uniquely identify a group of available resources. The following example create an `SCalendar`
of `2 ^ 8 = 512 days` starting from `2016-February-2` with a set of identifiers `{ a, b, c, d }`
```
createSCalendar :: Integer -- Year.
-> Int -- Month.
-> Int -- Day.
-> Int -- NumDays.
-> Set Text -- Set of Identifiers
-> Maybe SCalendar
createSCalendar 2017 2 1 365 (Set.fromList ["a", "b", "c", "d"])
```
# Checking Availability
There are two functions to check availability for a reservation. The first one is
```
isQuantityAvailable :: Int -> TimePeriod -> SCalendar -> Bool
```
where `Int` is an amount of resource we want to reserve, `TimePeriod` is the period of
time we want to reserve for that amount of resource, and `SCalendar` is the calendar
where we want to check availability. Naturally, this function returns a `Bool` if the
amount of resources is available.
Note that here we are just concerned with the amount of resources and whether there is
some set of identifiers whose size is greater of equal to that amount. If we need
to check if a particular set of identifiers is available for reservation, we can
use the following function:
```
isReservAvailable :: Reservation -> SCalendar -> Bool
```
which is almost like the first function, but here we are taking into account the set
of strings which identifies the resources we want to reserve since we are providing
a `Reservation` as input.
# Adding reservations to a Calendar
There are two pairs of functions to add reservations to a calendar:
```
reservPeriod' :: Reservation -> Calendar -> Maybe Calendar
```
which inserts reservations into a calendar without any constraint. That's it, this
function does not apply any availability check before making the `Reservation`. That's
why this function does not need a `SCalendar`, because it does not need to take
into account the set of total available resources.
The safe version is `reservPeriod` (without the quote) which enforces the
`isReservAvailable` check over that reservation before adding it. Its type is
```
reservePeriod :: Reservation -> SCalendar -> Maybe SCalendar
```
where an `SCalendar` is needed because we are taking into account the set of total
available resources to make the validation.
The other pair of functions are quite similar but are handy for adding a list of
reservations at once:
```
reserveManyPeriods' :: [Reservation] -> Calendar -> Maybe Calendar
```
which adds several reservations at once in a Calendar without any availability check.
```
reserveManyPeriods :: [Reservation] -> SCalendar -> Maybe SCalendar
```
which will return a `SCalendar` only with the reservations that pass the
`isReservAvailable` test. Here we must take into consideration that reservations will be
inserted in the same order they come in the input list. So, if a reservation conflicts
with the ones that have been already inserted, it will not be included in the `SCalendar`.
# Removing Reservation: Cancellations
There are two operations which allow us to remove reserved resources from a period of
time:
```
cancelPeriod :: Cancellation -> Calendar -> Maybe Calendar
```
This operation takes a `Cancellation` and returns a `Calendar` with that `Cancellation`'s
set of resource identifiers subtracted from that `Calendar` in that `Cancellation`'s
period of time.
Be careful with this operation because there is no restriction over the period you are
deleting. You may be deleting from several reservations, from periods of time which are
meaningless - which have already elapsed-, and so on. However, all this library is
intended to be used together with some persistent storage system which will allow you
to keep record of the exact dates and resources which are reserved or cancelled.
The other operation is
```
cancelManyPeriods :: [Cancellation] -> Calendar -> Maybe Calendar
```
which is handy for cancelling a list of periods at once.
Note that for cancellations we do not need a `SCalendar` because we don't need to make
any availability check.
# One important thing to note
Since this calendar implementation uses `Sets` and `Set` operations, you don't have to worry
about things like updating the total number of resource identifiers for your `SCalendar`.
You can freely remove or add identifiers to your `SCalendar` and there will be no
conflicts while making availability checks, reservations, cancellations, and so on.
# Reports
It is very useful to have an operation which can summarize some information about the
state of the calendar in a given period of time. That's why this library has
```
periodReport :: TimePeriod -> SCalendar -> Maybe Report
```
where `TimePeriod` is the interval of time you would like the `Report` to summarize and
`SCalendar` is the calendar we are working on. This function returns a `Report` over that
period of time with the following information:
- `totalUnits`: The set of total identifiers for resources in the `SCalendar`,
in other words, the set part of `(SCalendar set calendar)`.
- `reservedUnits`: The set of resources which have been reserved for that period of time.
- `remainingUnits`: The set of remaining resources which can still be reserved without
creating conflicts in a `TimePeriod`.
Note that `totalUnits`, `reservedUnits`, `remainingUnits` are all of type `Set`, and that the type
of `Report` is :
```
data Report = Report
{ reportPeriod :: TimePeriod
, totalUnits :: Set Text
, reservedUnits :: Set Text
, remainingUnits :: Set Text
}
```
# Have Fun!
So if you find this library useful, have fun with it in applications which need some
sort of calendar and resource availability management!!
# Acknowledgements
The base code for this library was written by [Sebastián Pulido Gómez](https://github.com/sebashack) and
was sponsored by [Stack Builders](https://www.stackbuilders.com/)
Thanks to [Mark Karpov](https://www.stackbuilders.com/) and [Javier Casas](https://github.com/javcasas) for
their code reviews and suggestions.
# Top-Nodes Algorithm Patent information
The ideas used to implement this library come from an invention by [Martin Rayrole](https://worldwide.espacenet.com/publicationDetails/biblio?locale=en_EP&II=8&FT=D&CC=US&DB=EPODOC&NR=2004204978A1&date=20041014&ND=3&KC=A1&adjacent=true#).
This version of the algorithm invented by Martin Rayrole now does not have any patent protection. You can verify that by clicking on the `Abandonment` section of this [web-page](https://register.epo.org/ipfwretrieve?lng=en&apn=US.76452604.A). Thus this now belongs to the public domain!