Re: Did April go missing in Asia/Amman?

[Eric Brine]

Thanks! Yeah, knowing that, I can easily make my code only consider
minutes. I'll also incorporate your "rd" optimziation

On Sat, Apr 23, 2016 at 5:16 PM, Zefram  wrote:

> Eric Brine wrote:
> >Thanks. I'll study this. I didn't think dividing by 60, adding 60 and
> >subtracting 60 was safe before of leap seconds.
>
> POSIX time, what DateTime calls "epoch" time, doesn't count leap seconds.
> Each multiple of 60 corresponds to the top of a UTC minute.
>
> -zefram
>

Re: Did April go missing in Asia/Amman?

[Zefram]

Eric Brine wrote:
>Thanks. I'll study this. I didn't think dividing by 60, adding 60 and
>subtracting 60 was safe before of leap seconds.

POSIX time, what DateTime calls "epoch" time, doesn't count leap seconds.
Each multiple of 60 corresponds to the top of a UTC minute.

-zefram

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Sat, Apr 23, 2016 at 4:56 PM, Zefram  wrote:

> Eric Brine wrote:
> >The binary search found:
> ...
> >2013-11-03T03:45:00 UTC
> >2013-11-03T04:07:30 UTC
>
> You should only examine integral minutes.  Truncate to the minute
> when bisecting, before you pass your bisected time to DateTime.  Or,
> to avoid fractions entirely, extend the search radius to 2048 minutes.
> Either way, do not burden DateTime with any arithmetical job.
>
> Here's an implementation of what I mean:
>
> sub start_of_day {
> my($tgt_date_str, $zone) = @_;
> $tgt_date_str =~ /\A([0-9]{4})-([0-9]{2})-([0-9]{2})\z/ or die;
> my $tgt_date_ut = DateTime->new(year => "$1", month => "$2",
> day => "$3", time_zone => "UTC");
> my($tgt_date_epoch_min) = $tgt_date_ut->epoch / 60;
> my($tgt_date_rd) = $tgt_date_ut->utc_rd_values;
> my $left_epoch_min = $tgt_date_epoch_min - 1440;
> my $right_epoch_min = $tgt_date_epoch_min + 1440;
> while(($right_epoch_min - $left_epoch_min) > 1) {
> my $try_epoch_min = ($left_epoch_min + $right_epoch_min) >> 1;
> my $try_dt = DateTime->from_epoch(epoch => $try_epoch_min*60,
> time_zone => $zone);
> (($try_dt->local_rd_values)[0] >= $tgt_date_rd ?
> $right_epoch_min : $left_epoch_min) = $try_epoch_min;
> }
> return DateTime->from_epoch(epoch => $right_epoch_min*60);
> }
>
> Use as in:
>
> @ARGV == 2 or die;
> my($tgt_date_str, $zone_name) = @ARGV;
> my $zone = DateTime::TimeZone->new(name => $zone_name);
> print start_of_day($tgt_date_str, $zone), "Z\n";
>
> -zefram
>

Thanks. I'll study this. I didn't think dividing by 60, adding 60 and
subtracting 60 was safe before of leap seconds.

Re: Did April go missing in Asia/Amman?

[Zefram]

Eric Brine wrote:
>The binary search found:
...
>2013-11-03T03:45:00 UTC
>2013-11-03T04:07:30 UTC

You should only examine integral minutes.  Truncate to the minute
when bisecting, before you pass your bisected time to DateTime.  Or,
to avoid fractions entirely, extend the search radius to 2048 minutes.
Either way, do not burden DateTime with any arithmetical job.

Here's an implementation of what I mean:

sub start_of_day {
my($tgt_date_str, $zone) = @_;
$tgt_date_str =~ /\A([0-9]{4})-([0-9]{2})-([0-9]{2})\z/ or die;
my $tgt_date_ut = DateTime->new(year => "$1", month => "$2",
day => "$3", time_zone => "UTC");
my($tgt_date_epoch_min) = $tgt_date_ut->epoch / 60;
my($tgt_date_rd) = $tgt_date_ut->utc_rd_values;
my $left_epoch_min = $tgt_date_epoch_min - 1440;
my $right_epoch_min = $tgt_date_epoch_min + 1440;
while(($right_epoch_min - $left_epoch_min) > 1) {
my $try_epoch_min = ($left_epoch_min + $right_epoch_min) >> 1;
my $try_dt = DateTime->from_epoch(epoch => $try_epoch_min*60,
time_zone => $zone);
(($try_dt->local_rd_values)[0] >= $tgt_date_rd ?
$right_epoch_min : $left_epoch_min) = $try_epoch_min;
}
return DateTime->from_epoch(epoch => $right_epoch_min*60);
}

Use as in:

@ARGV == 2 or die;
my($tgt_date_str, $zone_name) = @ARGV;
my $zone = DateTime::TimeZone->new(name => $zone_name);
print start_of_day($tgt_date_str, $zone), "Z\n";

-zefram

Re: Did April go missing in Asia/Amman?

[Eric Brine]

Then I don't understand your algorithm. I perform a binary search on epoch
times with two UTC dt as bounds. The result is 2013-11-02T23:59:03 in the
desired time zone.


On Sat, Apr 23, 2016 at 4:08 PM, Zefram  wrote:

> Eric Brine wrote:
> >00:00:04   <--- Starting from this
>
> You shouldn't be getting such a time at any point in the algorithm I
> was proposing.
>

Then I don't understand your algorithm. I started with

min: 2013-11-02T00:00:00 UTC
max: 2013-11-04T00:00:00 UTC

The binary search found:

2013-11-03T00:00:00 UTC
2013-11-03T12:00:00 UTC
2013-11-03T06:00:00 UTC
2013-11-03T03:00:00 UTC
2013-11-03T04:30:00 UTC
2013-11-03T03:45:00 UTC
2013-11-03T04:07:30 UTC
2013-11-03T03:56:15 UTC
2013-11-03T04:01:52 UTC
2013-11-03T03:59:03 UTC
2013-11-03T04:00:27 UTC

Re: Did April go missing in Asia/Amman?

[Zefram]

Eric Brine wrote:
>00:00:04   <--- Starting from this

You shouldn't be getting such a time at any point in the algorithm I
was proposing.

-zefram

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Sat, Apr 23, 2016 at 3:52 PM, Zefram  wrote:

> Eric Brine wrote:
> >I can't figure out how to search only down to the minute without causing
> it
> >to find the wrong answer on days with two midnights.
>
> In those fairly common cases, where DST ending causes time to jump back
> from 01:00 to 00:00, you want to consistently get the earlier midnight.
> This doesn't pose any real difficulty.


Indeed, finding the minute posed no difficulty.

The problem I had:

00:00:00   <--- I wanted this
00:00:04   <--- Starting from this
00:59:59
00:00:00   <--- I was getting this.

Switching from

$dt->truncate( to => 'minute' )

to

$dt->substract( seconds => $dt->second )

solved that problem.

Re: Did April go missing in Asia/Amman?

[Zefram]

Eric Brine wrote:
>I can't figure out how to search only down to the minute without causing it
>to find the wrong answer on days with two midnights.

In those fairly common cases, where DST ending causes time to jump back
from 01:00 to 00:00, you want to consistently get the earlier midnight.
This doesn't pose any real difficulty.  Finding a UT time that corresponds
to local time 00:00 doesn't tell you that you've found the real boundary:
it only tells you that the real boundary is no later than this time.
You continue the binary search.  The criterion you use, to decide which
range endpoint to replace with the bisected timestamp, is whether the
local time to which it corresponds is greater than or equal to 00:00
on the target day.  You should end up with two consecutive UT minutes,
the earlier of which precedes the target day in zone time, and the later
of which falls on or follows the target day in zone time.

The only situation that would really screw up this search is if time
jumped back from, say, 00:30 to 23:30, making the span of a calendar date
discontinuous in zone time.  (Is this what you meant by "two midnights"?)
No zone actually does this.  While changing the effective length of a
local day is quite palatable, making a day discontinuous is too big an
inconvenience.  Note that this is inconvenient *for people in the zone*,
unlike things like there being no local 12:00, which is inconvenient
*for programmers* and happens all the time.

-zefram

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Sat, Apr 23, 2016 at 3:42 PM, Eric Brine  wrote:

> On Fri, Apr 22, 2016 at 8:04 PM, Zefram  wrote:
>
>> 18 steps
>> of binary search gets you down to the second, but actually modern zones
>> are always on integral-minute offsets, so you could look only at integral
>> minutes and take only 12 steps.  For each UT time you try, convert it
>> to zone time and see which month it ends up in.
>>
>
> I can't figure out how to search only down to the minute without causing
> it to find the wrong answer on days with two midnights.
>

Nevermind. $dt->truncate( to => 'minute') doesn't work, but $dt->subtract(
seconds => $dt->second ) does. Optimized the linked code.

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Fri, Apr 22, 2016 at 8:04 PM, Zefram  wrote:

> 18 steps
> of binary search gets you down to the second, but actually modern zones
> are always on integral-minute offsets, so you could look only at integral
> minutes and take only 12 steps.  For each UT time you try, convert it
> to zone time and see which month it ends up in.
>

I can't figure out how to search only down to the minute without causing it
to find the wrong answer on days with two midnights.

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Sat, Apr 23, 2016 at 2:58 PM, Eric Brine  wrote:

> On Sat, Apr 23, 2016 at 2:57 PM, Eric Brine  wrote:
>
>> Zephram, could you verify the updated code:
>>
>> http://stackoverflow.com/a/21000824/589924
>>
>> Assumptions:
>>
>>
>>- There is no dt to which one can add time to obtain a dt with an
>>earlier date.
>>- In no time zone does a date starts more than 48*60*60 seconds
>>before the date starts in UTC.
>>- In no time zone does a date starts more than 48*60*60 seconds after
>>the date starts in UTC.
>>
>>
>> Hold on, it's buggy.
>

Bug fixed. Couple you please check it out?

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Sat, Apr 23, 2016 at 2:57 PM, Eric Brine  wrote:

> Zephram, could you verify the updated code:
>
> http://stackoverflow.com/a/21000824/589924
>
> Assumptions:
>
>
>- There is no dt to which one can add time to obtain a dt with an
>earlier date.
>- In no time zone does a date starts more than 48*60*60 seconds before
>the date starts in UTC.
>- In no time zone does a date starts more than 48*60*60 seconds after
>the date starts in UTC.
>
>
> Hold on, it's buggy.

Re: Did April go missing in Asia/Amman?

[Eric Brine]

Zephram, could you verify the updated code:

http://stackoverflow.com/a/21000824/589924

Assumptions:


   - There is no dt to which one can add time to obtain a dt with an
   earlier date.
   - In no time zone does a date starts more than 48*60*60 seconds before
   the date starts in UTC.
   - In no time zone does a date starts more than 48*60*60 seconds after
   the date starts in UTC.

Re: Did April go missing in Asia/Amman?

[Zefram]

Bill Moseley wrote:
>The code Eric pointed me to sets the hour to 12 on a floating $dt and then
>sets the timezone.  Sounds like there's cases where that could still fail.

Right, that's broken.  That's not the algorithm I was proposing.
You should search among *UT* times, and the only kind of conversion
you need is to represent a given UT time in zone terms, which doesn't
run into this problem.  There is no need to specify a local time and
convert it to UT or otherwise process it.  Your initial search range is
centred around the UT start of the specified day, with a radius around
that centre point of 1440 minutes or so.

>This is for a form where a user can enter a start and end date (not a time)
>and expect to see all events during those days.  i.e.   From 2016-04-01 to
>2016-04-30.

To handle the inclusive upper day boundary, increment the supplied date
(calendar arithmetic only, ignore zone behaviour) to get an exclusive
upper day boundary.  Find the beginning of that day in zone time to get
an exclusive upper UT time boundary.

>The form's defaults are suppose to be the dates for the *current* start and
>end of the month *in the user's time zone*.

For this part, you just take the current UT time and represent it in
zone terms.  That tells you what month to default to.

-zefram

Re: Did April go missing in Asia/Amman?

[Bill Moseley]

On Sat, Apr 23, 2016 at 10:14 AM, Zefram  wrote:

> Bill Moseley wrote:
> >hour=> 12,  # Assume this exists
>
> This does not always exist.  Africa/Khartoum on 2000-01-15, for example.
> In fact, thanks to cases such as Pacific/Apia on 2011-12-30, not only is
> there no hour that exists on every day in every zone, there are actually
> some zone days for which no hour exists.
>

$ perl -le 'use DateTime; my $dt = DateTime->new( year => 2000, month => 1,
day => 15, hour => 12 )->set_time_zone( "Africa/Khartoum")'
Invalid local time for date in time zone: Africa/Khartoum

Fun.

The code Eric pointed me to sets the hour to 12 on a floating $dt and then
sets the timezone.  Sounds like there's cases where that could still fail.

If I cannot assume hour 12 exists (or assume anything) how can I find my
starting valid $dt in the target time zone to look back for the starting
time?




>
> >And for the end time of the month (to the second):
>
> Rather than subtract a second and use a <= comparison, it's cleaner to
> use the start time of the next month and a < comparison.
>

Yes, that makes sense.

This is for a form where a user can enter a start and end date (not a time)
and expect to see all events during those days.  i.e.   From 2016-04-01 to
2016-04-30.

The form's defaults are suppose to be the dates for the *current* start and
end of the month *in the user's time zone*.

I then need to convert those into a timestamp (including offset) that the
database can compare against.  The database's session is not in the target
timezone so I cannot simply compare the date part.



>
> >I was thinking of an implementation that assumed DST change happened at an
> >hour boundary and simply try incrementing hours until no more exceptions.
>
> That's a bad assumption.  You can assume *minute* boundaries, but
> not hours.
>
> -zefram
>

Thanks!



-- 
Bill Moseley
mose...@hank.org

Re: Did April go missing in Asia/Amman?

[Zefram]

Bill Moseley wrote:
>hour=> 12,  # Assume this exists

This does not always exist.  Africa/Khartoum on 2000-01-15, for example.
In fact, thanks to cases such as Pacific/Apia on 2011-12-30, not only is
there no hour that exists on every day in every zone, there are actually
some zone days for which no hour exists.

>And for the end time of the month (to the second):

Rather than subtract a second and use a <= comparison, it's cleaner to
use the start time of the next month and a < comparison.

>I was thinking of an implementation that assumed DST change happened at an
>hour boundary and simply try incrementing hours until no more exceptions.

That's a bad assumption.  You can assume *minute* boundaries, but
not hours.

-zefram

Re: Did April go missing in Asia/Amman?

[Eric Brine]

On Fri, Apr 22, 2016 at 8:04 PM, Zefram  wrote:

> Bill Moseley wrote:
> >In other words, I'm trying to find the start and end times for the current
> >month based on a given timezone and then use those in my database query.
>
> You can perform a binary search on UT times, looking for the boundaries
> where the month changes in zone time.  For each month boundary, start
> with a range of the UT month boundary plus and minus 24 hours.  18 steps
> of binary search gets you down to the second, but actually modern zones
> are always on integral-minute offsets, so you could look only at integral
> minutes and take only 12 steps.  For each UT time you try, convert it
> to zone time and see which month it ends up in.


The page linked below has an implementation that finds the start of the day
using the approach Zefram described. It should be trivial to change to to
find the start of the month.
http://stackoverflow.com/a/21000824/589924