On Sat, 15 Feb 2003, John Peacock wrote: > Is there any chance you would consider something other than RedBlack trees for > the individual TZ files? The reason I ask is we could choose some algorithm > that was faster for searching than RedBlack trees as long as we make some > assumptions about the data.
I have no particular leaning towards a red-black tree. It simply offered a simple API for what needed to be done. > I'm looking at my copy of "Introduction to Algorithms" for inspiration, but > nothing is actually leaping out at me. I think that an array of objects would > be suffient, as long as we could assume that > > a) the utc_start values are unique for each TZ; > b) the utc_end values are not overlapping the subsequent utc_start; > c) they are sorted. > > In this case, we could actually use a binary search on the array to locate the > appropriate utc_start/utc_end values for the period in question. This would be > faster than O(1) in practice for search. > > Or am I missing some instance where we would have to insert values into the TZ? Values _do_ get inserted, actually. Only a certain range of data is pre-generated in the DT::TZ files (time of generation + 10 years). So if a datetime object is greater than that range, we generate data as needed for the spans around the datetime. But as long as we generate only spans that are greater than the current max we should be fine. -dave /*======================= House Absolute Consulting www.houseabsolute.com =======================*/
