How can this design be improved to deal with overlapping date ranges and resolve conflicts between date ranges?
I am working on some code that deals with date ranges. I have a price activity that has a start date and an end date to set a specific price for that range. There are several pricing operations with overlapping date ranges.
Ultimately I need the ability to query valid prices for a date range. I go over (jan1, jan31) and I return a list that says jan1 -> jan10 $ 4, jan11 -> jan19 $ 3 jan20 -> jan31 $ 4.
There are priorities between pricing. Some types of pricing have high priority, so they override other pricing actions, and for certain types of price transactions, the lowest price gains, etc.
I currently have a class that does these pricing operations and keeps the allowed price calendar. When I add new pricing types, I update the allowed calendar. As I write more tests / code, it started to get very complicated in all different cases (pricing operations overlap in different ways). I end up with a very complex code where I allow a new added price activity. See below method AddPricingActivity()
.
Can anyone think of an easier way to handle this? Could there be similar code out there somewhere?
Public class PricingActivity()
{
DateTime startDate;
DateTime endDate;
Double price;
Public bool StartsBeforeEndsAfter (PricingActivity pAct)
{
// pAct covers this pricing activity
}
Public bool StartsMiddleEndsAfter (PricingActivity pAct){
// early part of pAct Itersects with later part of this pricing activity
}
//more similar methods to cover all the combinations of intersecting
}
Public Class PricingActivityList()
{
List<PricingActivity> activities;
SortedDictionary<Date, PricingActivity> resolvedPricingCalendar;
Public void AddPricingActivity(PricingActivity pAct)
{
//update the resolvedCalendar
//go over each activity and find intersecting ones
//update the resolved calendar correctly
//depending on the type of the intersection
//this part is getting out of hand…..
}
}
source to share
Some suggestions: -
-
Abstract DateTimeRange from this. Do all the work of computing overlaps, intersections, and joins in the reusable DateTimeRange class, not here.
-
Don't try to update data structures two with inserts, updates and deletes - both the original information and the allowed calendar - instead update the original data and then recalculate the permitted information using a simple drilldown algorithm like the others. If you NEED to cache the allowed calendar between changes to the original data, do so (flush the cached copy whenever the original changes and recalculate), otherwise just recalculate them every time, because memory, not CPU, tends to be tight place these days, and optimization is something you should only do if you need to.
source to share
A simple line sweep algorithm is what you are looking for. Essentially:
- Sorting all the start and end points of your price transactions into an array of "events".
- Doing this array essentially gives you every pricing "event" as it is (the beginning or end of any pricing period).
- Scanning with this array in order, allows you to maintain a list of actions that are in effect on any particular date.
So, given any date range, you can:
- Start at the beginning of the array with an empty "current set of actions".
- Look at each element in the array; if this is the starting point, you add this activity to your current set; if it is an endpoint you are discarding that activity from the set.
- Continue sweeping until you reach the desired date range.
- When you go through your "withdrawal range", you can generate your actual price based on any actions in the set; recalculation of prices at each stage of the event.
- When you've scanned the end of your desired range, you're done.
This way you don't need to potentially maintain the n!
size of the activity intersections, and you can generate a valid one-pass price list O(n*a)
( a
) which is the average number of activities in the current set, close enough to linear if this is small / constant).
source to share
You can implement IComparable<T>
and PricingActivity
will become sortable. I think if you understood correctly you will need to sort by the start of the range and then the priority. This way, when you request your sorted list, you get the first action whose range should start and which has the highest priority. Then you simply scroll through the list until you see: the action that starts after the last selected ends, -or-, an action with a higher priority than the last selected. Once you had the entire list, you had to select the highest priority actions in every possible interval of the (sub) range.
Something like this: (not tested)
Date selectedStart = Date.MinValue;
PricingActivity selected = sortedList[0];
foreach(PricingActivity act in sortedList)
{
if (act.Start >= selected.End ||
act.Priority > selected.Priority)
{
// Store the selected activity with the applicable date range.
selectedActivities.Add(
new DateRange(selectedStart, Math.Min(selected.End, act.Start)),
selected);
// The next activity (act) would start here.
selectedStart = act.Start;
selected = act;
}
}
selectedActivities
will contain an ordered list of actions that have their applicable ranges ( DateRange
just came up by me), just as you wanted. However, you will need to add code to first jump to the first activity that is in the requested range and stop at the first activity that is outside the requested range.
source to share