I don't think this is too tough. What am I missing?
using System;
using System.Collections.Generic;
public class ScheduledPerson {
public string Name {get; set;}
public Dictionary<string, Object> Fields {
get { return _fields; }
set { _fields = value; }
}
private Dictionary<string, Object> _fields = new Dictionary<string, Object>();
public List<Tuple<DateTime, DateTime>> Events {
get { return _events; }
set { _events = value; }
}
private List<Tuple<DateTime, DateTime>> _events = new List<Tuple<DateTime, DateTime>>();
public ScheduledPerson(string name){
Name = name;
}
}
I don't see a good way to make our ScheduledPerson classes generic, as it seems the fields can be anything. I'm storing the field values as Objects, as I see nothing that requires them to be dynamics. Just make sure all field value types have a sensible ToString() implementation.
If you want Events to be a List of DateRange or of your own Event class instead of Tuple, feel free.
It then remains for you to write a separate class to render each ScheduledPerson in a table, along with figuring out all the headers from all ScheduledPerson records. It you are dealing with ten thousand people, you'll want a better solution that has all the headers stored, but for most applications, it won't be too bad to enumerate all the Fields on all the ScheduledPersons to figure out the headers.
If you look at your code for swapping you:
// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.
But, ~50% of the time that string you just swapped needs to be moved back, which is why faster merge sorts work from both ends at the same time.
Next if you check to see if the first and last elements are the same before doing each of the recursive call you avoid wasting time calling a function only to quickly exit it. This happens 10000000 in your final test which does add noticeable amounts of time.
Use,
if (pivot_index -1 > start)
quick_sort(lines, start, pivot_index - 1);
if (pivot_index + 1 < end)
quick_sort(lines, pivot_index + 1, end);
You still want an outer function to do an initial if (start < end) but that only needs to happen once so that function can just call an unsafe version of your code without that outer comparison.
Also, picking a random pivot tends to avoid N^2 worst case results, but it's probably not a big deal with your random data set.
Finally, the hidden problem is QuickSort is comparing strings in ever smaller buckets that are ever closer together,
(Edit: So, AAAAA, AAAAB, AAAAC, AAAAD then AAAAA, AAAAB. So, strcmp needs to step though a lot of A's before looking the useful parts of the strings.)
but with Merge sort you look at the smallest buckets first while they are vary random. Mergsorts final passes do compare a lot of strings close to each other, but it's less of an issue then. One way to make Quick sorts faster for strings is to compare the first digits of the outer strings and if there the same ignore them when doing the inner comparisons, but you have to be careful that all strings have enough digits that your not skipping past the null terminator.
Best Answer
The typical way to store geographic data is with a spatial data structure such as an R-tree (or some variant, such as R+tree, R*tree, etc.) This is how geographic data types are normally implemented in GIS-capable RDBMS. (I know both Microsoft's SQL Server 2008 and PostGIS use R-trees for the geographic types.) They meet all of the basic requirements you've described, and trivially support intersection, location, distance, and other query types.
Depending on the type of data, you may also find such things as kD-trees, quad-trees, octrees, bounding volume hierarchies (including axis-aligned bounding box trees), etc. in common use. This is actually much more commonplace in 3D games, since the size and shape of an object is more relevant to intersection queries. They're less often used for GIS than R-trees.