1/*
2*******************************************************************************
3* Copyright (C) 2007-2013, International Business Machines Corporation and
4* others. All Rights Reserved.
5*******************************************************************************
6*/
7
8#include "utypeinfo.h"  // for 'typeid' to work
9
10#include "unicode/utypes.h"
11
12#if !UCONFIG_NO_FORMATTING
13
14#include "unicode/rbtz.h"
15#include "unicode/gregocal.h"
16#include "uvector.h"
17#include "gregoimp.h"
18#include "cmemory.h"
19#include "umutex.h"
20
21U_NAMESPACE_BEGIN
22
23/**
24 * A struct representing a time zone transition
25 */
26struct Transition {
27    UDate time;
28    TimeZoneRule* from;
29    TimeZoneRule* to;
30};
31
32static UBool compareRules(UVector* rules1, UVector* rules2) {
33    if (rules1 == NULL && rules2 == NULL) {
34        return TRUE;
35    } else if (rules1 == NULL || rules2 == NULL) {
36        return FALSE;
37    }
38    int32_t size = rules1->size();
39    if (size != rules2->size()) {
40        return FALSE;
41    }
42    for (int32_t i = 0; i < size; i++) {
43        TimeZoneRule *r1 = (TimeZoneRule*)rules1->elementAt(i);
44        TimeZoneRule *r2 = (TimeZoneRule*)rules2->elementAt(i);
45        if (*r1 != *r2) {
46            return FALSE;
47        }
48    }
49    return TRUE;
50}
51
52UOBJECT_DEFINE_RTTI_IMPLEMENTATION(RuleBasedTimeZone)
53
54RuleBasedTimeZone::RuleBasedTimeZone(const UnicodeString& id, InitialTimeZoneRule* initialRule)
55: BasicTimeZone(id), fInitialRule(initialRule), fHistoricRules(NULL), fFinalRules(NULL),
56  fHistoricTransitions(NULL), fUpToDate(FALSE) {
57}
58
59RuleBasedTimeZone::RuleBasedTimeZone(const RuleBasedTimeZone& source)
60: BasicTimeZone(source), fInitialRule(source.fInitialRule->clone()),
61  fHistoricTransitions(NULL), fUpToDate(FALSE) {
62    fHistoricRules = copyRules(source.fHistoricRules);
63    fFinalRules = copyRules(source.fFinalRules);
64    if (source.fUpToDate) {
65        UErrorCode status = U_ZERO_ERROR;
66        complete(status);
67    }
68}
69
70RuleBasedTimeZone::~RuleBasedTimeZone() {
71    deleteTransitions();
72    deleteRules();
73}
74
75RuleBasedTimeZone&
76RuleBasedTimeZone::operator=(const RuleBasedTimeZone& right) {
77    if (*this != right) {
78        BasicTimeZone::operator=(right);
79        deleteRules();
80        fInitialRule = right.fInitialRule->clone();
81        fHistoricRules = copyRules(right.fHistoricRules);
82        fFinalRules = copyRules(right.fFinalRules);
83        deleteTransitions();
84        fUpToDate = FALSE;
85    }
86    return *this;
87}
88
89UBool
90RuleBasedTimeZone::operator==(const TimeZone& that) const {
91    if (this == &that) {
92        return TRUE;
93    }
94    if (typeid(*this) != typeid(that)
95        || BasicTimeZone::operator==(that) == FALSE) {
96        return FALSE;
97    }
98    RuleBasedTimeZone *rbtz = (RuleBasedTimeZone*)&that;
99    if (*fInitialRule != *(rbtz->fInitialRule)) {
100        return FALSE;
101    }
102    if (compareRules(fHistoricRules, rbtz->fHistoricRules)
103        && compareRules(fFinalRules, rbtz->fFinalRules)) {
104        return TRUE;
105    }
106    return FALSE;
107}
108
109UBool
110RuleBasedTimeZone::operator!=(const TimeZone& that) const {
111    return !operator==(that);
112}
113
114void
115RuleBasedTimeZone::addTransitionRule(TimeZoneRule* rule, UErrorCode& status) {
116    if (U_FAILURE(status)) {
117        return;
118    }
119    AnnualTimeZoneRule* atzrule = dynamic_cast<AnnualTimeZoneRule*>(rule);
120    if (atzrule != NULL && atzrule->getEndYear() == AnnualTimeZoneRule::MAX_YEAR) {
121        // A final rule
122        if (fFinalRules == NULL) {
123            fFinalRules = new UVector(status);
124            if (U_FAILURE(status)) {
125                return;
126            }
127        } else if (fFinalRules->size() >= 2) {
128            // Cannot handle more than two final rules
129            status = U_INVALID_STATE_ERROR;
130            return;
131        }
132        fFinalRules->addElement((void*)rule, status);
133    } else {
134        // Non-final rule
135        if (fHistoricRules == NULL) {
136            fHistoricRules = new UVector(status);
137            if (U_FAILURE(status)) {
138                return;
139            }
140        }
141        fHistoricRules->addElement((void*)rule, status);
142    }
143    // Mark dirty, so transitions are recalculated at next complete() call
144    fUpToDate = FALSE;
145}
146
147static UMutex gLock = U_MUTEX_INITIALIZER;
148
149void
150RuleBasedTimeZone::completeConst(UErrorCode& status) const {
151    if (U_FAILURE(status)) {
152        return;
153    }
154    UBool updated;
155    UMTX_CHECK(&gLock, fUpToDate, updated);
156    if (!updated) {
157        umtx_lock(&gLock);
158        if (!fUpToDate) {
159            RuleBasedTimeZone *ncThis = const_cast<RuleBasedTimeZone*>(this);
160            ncThis->complete(status);
161        }
162        umtx_unlock(&gLock);
163    }
164}
165
166void
167RuleBasedTimeZone::complete(UErrorCode& status) {
168    if (U_FAILURE(status)) {
169        return;
170    }
171    if (fUpToDate) {
172        return;
173    }
174    // Make sure either no final rules or a pair of AnnualTimeZoneRules
175    // are available.
176    if (fFinalRules != NULL && fFinalRules->size() != 2) {
177        status = U_INVALID_STATE_ERROR;
178        return;
179    }
180
181    UBool *done = NULL;
182    // Create a TimezoneTransition and add to the list
183    if (fHistoricRules != NULL || fFinalRules != NULL) {
184        TimeZoneRule *curRule = fInitialRule;
185        UDate lastTransitionTime = MIN_MILLIS;
186
187        // Build the transition array which represents historical time zone
188        // transitions.
189        if (fHistoricRules != NULL && fHistoricRules->size() > 0) {
190            int32_t i;
191            int32_t historicCount = fHistoricRules->size();
192            done = (UBool*)uprv_malloc(sizeof(UBool) * historicCount);
193            if (done == NULL) {
194                status = U_MEMORY_ALLOCATION_ERROR;
195                goto cleanup;
196            }
197            for (i = 0; i < historicCount; i++) {
198                done[i] = FALSE;
199            }
200            while (TRUE) {
201                int32_t curStdOffset = curRule->getRawOffset();
202                int32_t curDstSavings = curRule->getDSTSavings();
203                UDate nextTransitionTime = MAX_MILLIS;
204                TimeZoneRule *nextRule = NULL;
205                TimeZoneRule *r = NULL;
206                UBool avail;
207                UDate tt;
208                UnicodeString curName, name;
209                curRule->getName(curName);
210
211                for (i = 0; i < historicCount; i++) {
212                    if (done[i]) {
213                        continue;
214                    }
215                    r = (TimeZoneRule*)fHistoricRules->elementAt(i);
216                    avail = r->getNextStart(lastTransitionTime, curStdOffset, curDstSavings, false, tt);
217                    if (!avail) {
218                        // No more transitions from this rule - skip this rule next time
219                        done[i] = TRUE;
220                    } else {
221                        r->getName(name);
222                        if (*r == *curRule ||
223                            (name == curName && r->getRawOffset() == curRule->getRawOffset()
224                            && r->getDSTSavings() == curRule->getDSTSavings())) {
225                            continue;
226                        }
227                        if (tt < nextTransitionTime) {
228                            nextTransitionTime = tt;
229                            nextRule = r;
230                        }
231                    }
232                }
233
234                if (nextRule ==  NULL) {
235                    // Check if all historic rules are done
236                    UBool bDoneAll = TRUE;
237                    for (int32_t j = 0; j < historicCount; j++) {
238                        if (!done[j]) {
239                            bDoneAll = FALSE;
240                            break;
241                        }
242                    }
243                    if (bDoneAll) {
244                        break;
245                    }
246                }
247
248                if (fFinalRules != NULL) {
249                    // Check if one of final rules has earlier transition date
250                    for (i = 0; i < 2 /* fFinalRules->size() */; i++) {
251                        TimeZoneRule *fr = (TimeZoneRule*)fFinalRules->elementAt(i);
252                        if (*fr == *curRule) {
253                            continue;
254                        }
255                        r = (TimeZoneRule*)fFinalRules->elementAt(i);
256                        avail = r->getNextStart(lastTransitionTime, curStdOffset, curDstSavings, false, tt);
257                        if (avail) {
258                            if (tt < nextTransitionTime) {
259                                nextTransitionTime = tt;
260                                nextRule = r;
261                            }
262                        }
263                    }
264                }
265
266                if (nextRule == NULL) {
267                    // Nothing more
268                    break;
269                }
270
271                if (fHistoricTransitions == NULL) {
272                    fHistoricTransitions = new UVector(status);
273                    if (U_FAILURE(status)) {
274                        goto cleanup;
275                    }
276                }
277                Transition *trst = (Transition*)uprv_malloc(sizeof(Transition));
278                if (trst == NULL) {
279                    status = U_MEMORY_ALLOCATION_ERROR;
280                    goto cleanup;
281                }
282                trst->time = nextTransitionTime;
283                trst->from = curRule;
284                trst->to = nextRule;
285                fHistoricTransitions->addElement(trst, status);
286                if (U_FAILURE(status)) {
287                    goto cleanup;
288                }
289                lastTransitionTime = nextTransitionTime;
290                curRule = nextRule;
291            }
292        }
293        if (fFinalRules != NULL) {
294            if (fHistoricTransitions == NULL) {
295                fHistoricTransitions = new UVector(status);
296                if (U_FAILURE(status)) {
297                    goto cleanup;
298                }
299            }
300            // Append the first transition for each
301            TimeZoneRule *rule0 = (TimeZoneRule*)fFinalRules->elementAt(0);
302            TimeZoneRule *rule1 = (TimeZoneRule*)fFinalRules->elementAt(1);
303            UDate tt0, tt1;
304            UBool avail0 = rule0->getNextStart(lastTransitionTime, curRule->getRawOffset(), curRule->getDSTSavings(), false, tt0);
305            UBool avail1 = rule1->getNextStart(lastTransitionTime, curRule->getRawOffset(), curRule->getDSTSavings(), false, tt1);
306            if (!avail0 || !avail1) {
307                // Should not happen, because both rules are permanent
308                status = U_INVALID_STATE_ERROR;
309                goto cleanup;
310            }
311            Transition *final0 = (Transition*)uprv_malloc(sizeof(Transition));
312            if (final0 == NULL) {
313                status = U_MEMORY_ALLOCATION_ERROR;
314                goto cleanup;
315            }
316            Transition *final1 = (Transition*)uprv_malloc(sizeof(Transition));
317            if (final1 == NULL) {
318                uprv_free(final0);
319                status = U_MEMORY_ALLOCATION_ERROR;
320                goto cleanup;
321            }
322            if (tt0 < tt1) {
323                final0->time = tt0;
324                final0->from = curRule;
325                final0->to = rule0;
326                rule1->getNextStart(tt0, rule0->getRawOffset(), rule0->getDSTSavings(), false, final1->time);
327                final1->from = rule0;
328                final1->to = rule1;
329            } else {
330                final0->time = tt1;
331                final0->from = curRule;
332                final0->to = rule1;
333                rule0->getNextStart(tt1, rule1->getRawOffset(), rule1->getDSTSavings(), false, final1->time);
334                final1->from = rule1;
335                final1->to = rule0;
336            }
337            fHistoricTransitions->addElement(final0, status);
338            if (U_FAILURE(status)) {
339                goto cleanup;
340            }
341            fHistoricTransitions->addElement(final1, status);
342            if (U_FAILURE(status)) {
343                goto cleanup;
344            }
345        }
346    }
347    fUpToDate = TRUE;
348    if (done != NULL) {
349        uprv_free(done);
350    }
351    return;
352
353cleanup:
354    deleteTransitions();
355    if (done != NULL) {
356        uprv_free(done);
357    }
358    fUpToDate = FALSE;
359}
360
361TimeZone*
362RuleBasedTimeZone::clone(void) const {
363    return new RuleBasedTimeZone(*this);
364}
365
366int32_t
367RuleBasedTimeZone::getOffset(uint8_t era, int32_t year, int32_t month, int32_t day,
368                             uint8_t dayOfWeek, int32_t millis, UErrorCode& status) const {
369    if (U_FAILURE(status)) {
370        return 0;
371    }
372    if (month < UCAL_JANUARY || month > UCAL_DECEMBER) {
373        status = U_ILLEGAL_ARGUMENT_ERROR;
374        return 0;
375    } else {
376        return getOffset(era, year, month, day, dayOfWeek, millis,
377                         Grego::monthLength(year, month), status);
378    }
379}
380
381int32_t
382RuleBasedTimeZone::getOffset(uint8_t era, int32_t year, int32_t month, int32_t day,
383                             uint8_t /*dayOfWeek*/, int32_t millis,
384                             int32_t /*monthLength*/, UErrorCode& status) const {
385    // dayOfWeek and monthLength are unused
386    if (U_FAILURE(status)) {
387        return 0;
388    }
389    if (era == GregorianCalendar::BC) {
390        // Convert to extended year
391        year = 1 - year;
392    }
393    int32_t rawOffset, dstOffset;
394    UDate time = (UDate)Grego::fieldsToDay(year, month, day) * U_MILLIS_PER_DAY + millis;
395    getOffsetInternal(time, TRUE, kDaylight, kStandard, rawOffset, dstOffset, status);
396    if (U_FAILURE(status)) {
397        return 0;
398    }
399    return (rawOffset + dstOffset);
400}
401
402void
403RuleBasedTimeZone::getOffset(UDate date, UBool local, int32_t& rawOffset,
404                             int32_t& dstOffset, UErrorCode& status) const {
405    getOffsetInternal(date, local, kFormer, kLatter, rawOffset, dstOffset, status);
406}
407
408void
409RuleBasedTimeZone::getOffsetFromLocal(UDate date, int32_t nonExistingTimeOpt, int32_t duplicatedTimeOpt,
410                                      int32_t& rawOffset, int32_t& dstOffset, UErrorCode& status) const {
411    getOffsetInternal(date, TRUE, nonExistingTimeOpt, duplicatedTimeOpt, rawOffset, dstOffset, status);
412}
413
414
415/*
416 * The internal getOffset implementation
417 */
418void
419RuleBasedTimeZone::getOffsetInternal(UDate date, UBool local,
420                                     int32_t NonExistingTimeOpt, int32_t DuplicatedTimeOpt,
421                                     int32_t& rawOffset, int32_t& dstOffset,
422                                     UErrorCode& status) const {
423    rawOffset = 0;
424    dstOffset = 0;
425
426    if (U_FAILURE(status)) {
427        return;
428    }
429    if (!fUpToDate) {
430        // Transitions are not yet resolved.  We cannot do it here
431        // because this method is const.  Thus, do nothing and return
432        // error status.
433        status = U_INVALID_STATE_ERROR;
434        return;
435    }
436    const TimeZoneRule *rule = NULL;
437    if (fHistoricTransitions == NULL) {
438        rule = fInitialRule;
439    } else {
440        UDate tstart = getTransitionTime((Transition*)fHistoricTransitions->elementAt(0),
441            local, NonExistingTimeOpt, DuplicatedTimeOpt);
442        if (date < tstart) {
443            rule = fInitialRule;
444        } else {
445            int32_t idx = fHistoricTransitions->size() - 1;
446            UDate tend = getTransitionTime((Transition*)fHistoricTransitions->elementAt(idx),
447                local, NonExistingTimeOpt, DuplicatedTimeOpt);
448            if (date > tend) {
449                if (fFinalRules != NULL) {
450                    rule = findRuleInFinal(date, local, NonExistingTimeOpt, DuplicatedTimeOpt);
451                }
452                if (rule == NULL) {
453                    // no final rules or the given time is before the first transition
454                    // specified by the final rules -> use the last rule
455                    rule = ((Transition*)fHistoricTransitions->elementAt(idx))->to;
456                }
457            } else {
458                // Find a historical transition
459                while (idx >= 0) {
460                    if (date >= getTransitionTime((Transition*)fHistoricTransitions->elementAt(idx),
461                        local, NonExistingTimeOpt, DuplicatedTimeOpt)) {
462                        break;
463                    }
464                    idx--;
465                }
466                rule = ((Transition*)fHistoricTransitions->elementAt(idx))->to;
467            }
468        }
469    }
470    if (rule != NULL) {
471        rawOffset = rule->getRawOffset();
472        dstOffset = rule->getDSTSavings();
473    }
474}
475
476void
477RuleBasedTimeZone::setRawOffset(int32_t /*offsetMillis*/) {
478    // We don't support this operation at this moment.
479    // Nothing to do!
480}
481
482int32_t
483RuleBasedTimeZone::getRawOffset(void) const {
484    // Note: This implementation returns standard GMT offset
485    // as of current time.
486    UErrorCode status = U_ZERO_ERROR;
487    int32_t raw, dst;
488    getOffset(uprv_getUTCtime() * U_MILLIS_PER_SECOND,
489        FALSE, raw, dst, status);
490    return raw;
491}
492
493UBool
494RuleBasedTimeZone::useDaylightTime(void) const {
495    // Note: This implementation returns true when
496    // daylight saving time is used as of now or
497    // after the next transition.
498    UErrorCode status = U_ZERO_ERROR;
499    UDate now = uprv_getUTCtime() * U_MILLIS_PER_SECOND;
500    int32_t raw, dst;
501    getOffset(now, FALSE, raw, dst, status);
502    if (dst != 0) {
503        return TRUE;
504    }
505    // If DST is not used now, check if DST is used after the next transition
506    UDate time;
507    TimeZoneRule *from, *to;
508    UBool avail = findNext(now, FALSE, time, from, to);
509    if (avail && to->getDSTSavings() != 0) {
510        return TRUE;
511    }
512    return FALSE;
513}
514
515UBool
516RuleBasedTimeZone::inDaylightTime(UDate date, UErrorCode& status) const {
517    if (U_FAILURE(status)) {
518        return FALSE;
519    }
520    int32_t raw, dst;
521    getOffset(date, FALSE, raw, dst, status);
522    if (dst != 0) {
523        return TRUE;
524    }
525    return FALSE;
526}
527
528UBool
529RuleBasedTimeZone::hasSameRules(const TimeZone& other) const {
530    if (this == &other) {
531        return TRUE;
532    }
533    if (typeid(*this) != typeid(other)) {
534        return FALSE;
535    }
536    const RuleBasedTimeZone& that = (const RuleBasedTimeZone&)other;
537    if (*fInitialRule != *(that.fInitialRule)) {
538        return FALSE;
539    }
540    if (compareRules(fHistoricRules, that.fHistoricRules)
541        && compareRules(fFinalRules, that.fFinalRules)) {
542        return TRUE;
543    }
544    return FALSE;
545}
546
547UBool
548RuleBasedTimeZone::getNextTransition(UDate base, UBool inclusive, TimeZoneTransition& result) const {
549    UErrorCode status = U_ZERO_ERROR;
550    completeConst(status);
551    if (U_FAILURE(status)) {
552        return FALSE;
553    }
554    UDate transitionTime;
555    TimeZoneRule *fromRule, *toRule;
556    UBool found = findNext(base, inclusive, transitionTime, fromRule, toRule);
557    if (found) {
558        result.setTime(transitionTime);
559        result.setFrom((const TimeZoneRule&)*fromRule);
560        result.setTo((const TimeZoneRule&)*toRule);
561        return TRUE;
562    }
563    return FALSE;
564}
565
566UBool
567RuleBasedTimeZone::getPreviousTransition(UDate base, UBool inclusive, TimeZoneTransition& result) const {
568    UErrorCode status = U_ZERO_ERROR;
569    completeConst(status);
570    if (U_FAILURE(status)) {
571        return FALSE;
572    }
573    UDate transitionTime;
574    TimeZoneRule *fromRule, *toRule;
575    UBool found = findPrev(base, inclusive, transitionTime, fromRule, toRule);
576    if (found) {
577        result.setTime(transitionTime);
578        result.setFrom((const TimeZoneRule&)*fromRule);
579        result.setTo((const TimeZoneRule&)*toRule);
580        return TRUE;
581    }
582    return FALSE;
583}
584
585int32_t
586RuleBasedTimeZone::countTransitionRules(UErrorCode& /*status*/) const {
587    int32_t count = 0;
588    if (fHistoricRules != NULL) {
589        count += fHistoricRules->size();
590    }
591    if (fFinalRules != NULL) {
592        count += fFinalRules->size();
593    }
594    return count;
595}
596
597void
598RuleBasedTimeZone::getTimeZoneRules(const InitialTimeZoneRule*& initial,
599                                    const TimeZoneRule* trsrules[],
600                                    int32_t& trscount,
601                                    UErrorCode& status) const {
602    if (U_FAILURE(status)) {
603        return;
604    }
605    // Initial rule
606    initial = fInitialRule;
607
608    // Transition rules
609    int32_t cnt = 0;
610    int32_t idx;
611    if (fHistoricRules != NULL && cnt < trscount) {
612        int32_t historicCount = fHistoricRules->size();
613        idx = 0;
614        while (cnt < trscount && idx < historicCount) {
615            trsrules[cnt++] = (const TimeZoneRule*)fHistoricRules->elementAt(idx++);
616        }
617    }
618    if (fFinalRules != NULL && cnt < trscount) {
619        int32_t finalCount = fFinalRules->size();
620        idx = 0;
621        while (cnt < trscount && idx < finalCount) {
622            trsrules[cnt++] = (const TimeZoneRule*)fFinalRules->elementAt(idx++);
623        }
624    }
625    // Set the result length
626    trscount = cnt;
627}
628
629void
630RuleBasedTimeZone::deleteRules(void) {
631    delete fInitialRule;
632    fInitialRule = NULL;
633    if (fHistoricRules != NULL) {
634        while (!fHistoricRules->isEmpty()) {
635            delete (TimeZoneRule*)(fHistoricRules->orphanElementAt(0));
636        }
637        delete fHistoricRules;
638        fHistoricRules = NULL;
639    }
640    if (fFinalRules != NULL) {
641        while (!fFinalRules->isEmpty()) {
642            delete (AnnualTimeZoneRule*)(fFinalRules->orphanElementAt(0));
643        }
644        delete fFinalRules;
645        fFinalRules = NULL;
646    }
647}
648
649void
650RuleBasedTimeZone::deleteTransitions(void) {
651    if (fHistoricTransitions != NULL) {
652        while (!fHistoricTransitions->isEmpty()) {
653            Transition *trs = (Transition*)fHistoricTransitions->orphanElementAt(0);
654            uprv_free(trs);
655        }
656        delete fHistoricTransitions;
657    }
658    fHistoricTransitions = NULL;
659}
660
661UVector*
662RuleBasedTimeZone::copyRules(UVector* source) {
663    if (source == NULL) {
664        return NULL;
665    }
666    UErrorCode ec = U_ZERO_ERROR;
667    int32_t size = source->size();
668    UVector *rules = new UVector(size, ec);
669    if (U_FAILURE(ec)) {
670        return NULL;
671    }
672    int32_t i;
673    for (i = 0; i < size; i++) {
674        rules->addElement(((TimeZoneRule*)source->elementAt(i))->clone(), ec);
675        if (U_FAILURE(ec)) {
676            break;
677        }
678    }
679    if (U_FAILURE(ec)) {
680        // In case of error, clean up
681        for (i = 0; i < rules->size(); i++) {
682            TimeZoneRule *rule = (TimeZoneRule*)rules->orphanElementAt(i);
683            delete rule;
684        }
685        delete rules;
686        return NULL;
687    }
688    return rules;
689}
690
691TimeZoneRule*
692RuleBasedTimeZone::findRuleInFinal(UDate date, UBool local,
693                                   int32_t NonExistingTimeOpt, int32_t DuplicatedTimeOpt) const {
694    if (fFinalRules == NULL) {
695        return NULL;
696    }
697
698    AnnualTimeZoneRule* fr0 = (AnnualTimeZoneRule*)fFinalRules->elementAt(0);
699    AnnualTimeZoneRule* fr1 = (AnnualTimeZoneRule*)fFinalRules->elementAt(1);
700    if (fr0 == NULL || fr1 == NULL) {
701        return NULL;
702    }
703
704    UDate start0, start1;
705    UDate base;
706    int32_t localDelta;
707
708    base = date;
709    if (local) {
710        localDelta = getLocalDelta(fr1->getRawOffset(), fr1->getDSTSavings(),
711                                   fr0->getRawOffset(), fr0->getDSTSavings(),
712                                   NonExistingTimeOpt, DuplicatedTimeOpt);
713        base -= localDelta;
714    }
715    UBool avail0 = fr0->getPreviousStart(base, fr1->getRawOffset(), fr1->getDSTSavings(), TRUE, start0);
716
717    base = date;
718    if (local) {
719        localDelta = getLocalDelta(fr0->getRawOffset(), fr0->getDSTSavings(),
720                                   fr1->getRawOffset(), fr1->getDSTSavings(),
721                                   NonExistingTimeOpt, DuplicatedTimeOpt);
722        base -= localDelta;
723    }
724    UBool avail1 = fr1->getPreviousStart(base, fr0->getRawOffset(), fr0->getDSTSavings(), TRUE, start1);
725
726    if (!avail0 || !avail1) {
727        if (avail0) {
728            return fr0;
729        } else if (avail1) {
730            return fr1;
731        }
732        // Both rules take effect after the given time
733        return NULL;
734    }
735
736    return (start0 > start1) ? fr0 : fr1;
737}
738
739UBool
740RuleBasedTimeZone::findNext(UDate base, UBool inclusive, UDate& transitionTime,
741                            TimeZoneRule*& fromRule, TimeZoneRule*& toRule) const {
742    if (fHistoricTransitions == NULL) {
743        return FALSE;
744    }
745    UBool isFinal = FALSE;
746    UBool found = FALSE;
747    Transition result;
748    Transition *tzt = (Transition*)fHistoricTransitions->elementAt(0);
749    UDate tt = tzt->time;
750    if (tt > base || (inclusive && tt == base)) {
751        result = *tzt;
752        found = TRUE;
753    } else {
754        int32_t idx = fHistoricTransitions->size() - 1;
755        tzt = (Transition*)fHistoricTransitions->elementAt(idx);
756        tt = tzt->time;
757        if (inclusive && tt == base) {
758            result = *tzt;
759            found = TRUE;
760        } else if (tt <= base) {
761            if (fFinalRules != NULL) {
762                // Find a transion time with finalRules
763                TimeZoneRule *r0 = (TimeZoneRule*)fFinalRules->elementAt(0);
764                TimeZoneRule *r1 = (TimeZoneRule*)fFinalRules->elementAt(1);
765                UDate start0, start1;
766                UBool avail0 = r0->getNextStart(base, r1->getRawOffset(), r1->getDSTSavings(), inclusive, start0);
767                UBool avail1 = r1->getNextStart(base, r0->getRawOffset(), r0->getDSTSavings(), inclusive, start1);
768                //  avail0/avail1 should be always TRUE
769                if (!avail0 && !avail1) {
770                    return FALSE;
771                }
772                if (!avail1 || start0 < start1) {
773                    result.time = start0;
774                    result.from = r1;
775                    result.to = r0;
776                } else {
777                    result.time = start1;
778                    result.from = r0;
779                    result.to = r1;
780                }
781                isFinal = TRUE;
782                found = TRUE;
783            }
784        } else {
785            // Find a transition within the historic transitions
786            idx--;
787            Transition *prev = tzt;
788            while (idx > 0) {
789                tzt = (Transition*)fHistoricTransitions->elementAt(idx);
790                tt = tzt->time;
791                if (tt < base || (!inclusive && tt == base)) {
792                    break;
793                }
794                idx--;
795                prev = tzt;
796            }
797            result.time = prev->time;
798            result.from = prev->from;
799            result.to = prev->to;
800            found = TRUE;
801        }
802    }
803    if (found) {
804        // For now, this implementation ignore transitions with only zone name changes.
805        if (result.from->getRawOffset() == result.to->getRawOffset()
806            && result.from->getDSTSavings() == result.to->getDSTSavings()) {
807            if (isFinal) {
808                return FALSE;
809            } else {
810                // No offset changes.  Try next one if not final
811                return findNext(result.time, FALSE /* always exclusive */,
812                    transitionTime, fromRule, toRule);
813            }
814        }
815        transitionTime = result.time;
816        fromRule = result.from;
817        toRule = result.to;
818        return TRUE;
819    }
820    return FALSE;
821}
822
823UBool
824RuleBasedTimeZone::findPrev(UDate base, UBool inclusive, UDate& transitionTime,
825                            TimeZoneRule*& fromRule, TimeZoneRule*& toRule) const {
826    if (fHistoricTransitions == NULL) {
827        return FALSE;
828    }
829    UBool found = FALSE;
830    Transition result;
831    Transition *tzt = (Transition*)fHistoricTransitions->elementAt(0);
832    UDate tt = tzt->time;
833    if (inclusive && tt == base) {
834        result = *tzt;
835        found = TRUE;
836    } else if (tt < base) {
837        int32_t idx = fHistoricTransitions->size() - 1;
838        tzt = (Transition*)fHistoricTransitions->elementAt(idx);
839        tt = tzt->time;
840        if (inclusive && tt == base) {
841            result = *tzt;
842            found = TRUE;
843        } else if (tt < base) {
844            if (fFinalRules != NULL) {
845                // Find a transion time with finalRules
846                TimeZoneRule *r0 = (TimeZoneRule*)fFinalRules->elementAt(0);
847                TimeZoneRule *r1 = (TimeZoneRule*)fFinalRules->elementAt(1);
848                UDate start0, start1;
849                UBool avail0 = r0->getPreviousStart(base, r1->getRawOffset(), r1->getDSTSavings(), inclusive, start0);
850                UBool avail1 = r1->getPreviousStart(base, r0->getRawOffset(), r0->getDSTSavings(), inclusive, start1);
851                //  avail0/avail1 should be always TRUE
852                if (!avail0 && !avail1) {
853                    return FALSE;
854                }
855                if (!avail1 || start0 > start1) {
856                    result.time = start0;
857                    result.from = r1;
858                    result.to = r0;
859                } else {
860                    result.time = start1;
861                    result.from = r0;
862                    result.to = r1;
863                }
864            } else {
865                result = *tzt;
866            }
867            found = TRUE;
868        } else {
869            // Find a transition within the historic transitions
870            idx--;
871            while (idx >= 0) {
872                tzt = (Transition*)fHistoricTransitions->elementAt(idx);
873                tt = tzt->time;
874                if (tt < base || (inclusive && tt == base)) {
875                    break;
876                }
877                idx--;
878            }
879            result = *tzt;
880            found = TRUE;
881        }
882    }
883    if (found) {
884        // For now, this implementation ignore transitions with only zone name changes.
885        if (result.from->getRawOffset() == result.to->getRawOffset()
886            && result.from->getDSTSavings() == result.to->getDSTSavings()) {
887            // No offset changes.  Try next one if not final
888            return findPrev(result.time, FALSE /* always exclusive */,
889                transitionTime, fromRule, toRule);
890        }
891        transitionTime = result.time;
892        fromRule = result.from;
893        toRule = result.to;
894        return TRUE;
895    }
896    return FALSE;
897}
898
899UDate
900RuleBasedTimeZone::getTransitionTime(Transition* transition, UBool local,
901                                     int32_t NonExistingTimeOpt, int32_t DuplicatedTimeOpt) const {
902    UDate time = transition->time;
903    if (local) {
904        time += getLocalDelta(transition->from->getRawOffset(), transition->from->getDSTSavings(),
905                              transition->to->getRawOffset(), transition->to->getDSTSavings(),
906                              NonExistingTimeOpt, DuplicatedTimeOpt);
907    }
908    return time;
909}
910
911int32_t
912RuleBasedTimeZone::getLocalDelta(int32_t rawBefore, int32_t dstBefore, int32_t rawAfter, int32_t dstAfter,
913                             int32_t NonExistingTimeOpt, int32_t DuplicatedTimeOpt) const {
914    int32_t delta = 0;
915
916    int32_t offsetBefore = rawBefore + dstBefore;
917    int32_t offsetAfter = rawAfter + dstAfter;
918
919    UBool dstToStd = (dstBefore != 0) && (dstAfter == 0);
920    UBool stdToDst = (dstBefore == 0) && (dstAfter != 0);
921
922    if (offsetAfter - offsetBefore >= 0) {
923        // Positive transition, which makes a non-existing local time range
924        if (((NonExistingTimeOpt & kStdDstMask) == kStandard && dstToStd)
925                || ((NonExistingTimeOpt & kStdDstMask) == kDaylight && stdToDst)) {
926            delta = offsetBefore;
927        } else if (((NonExistingTimeOpt & kStdDstMask) == kStandard && stdToDst)
928                || ((NonExistingTimeOpt & kStdDstMask) == kDaylight && dstToStd)) {
929            delta = offsetAfter;
930        } else if ((NonExistingTimeOpt & kFormerLatterMask) == kLatter) {
931            delta = offsetBefore;
932        } else {
933            // Interprets the time with rule before the transition,
934            // default for non-existing time range
935            delta = offsetAfter;
936        }
937    } else {
938        // Negative transition, which makes a duplicated local time range
939        if (((DuplicatedTimeOpt & kStdDstMask) == kStandard && dstToStd)
940                || ((DuplicatedTimeOpt & kStdDstMask) == kDaylight && stdToDst)) {
941            delta = offsetAfter;
942        } else if (((DuplicatedTimeOpt & kStdDstMask) == kStandard && stdToDst)
943                || ((DuplicatedTimeOpt & kStdDstMask) == kDaylight && dstToStd)) {
944            delta = offsetBefore;
945        } else if ((DuplicatedTimeOpt & kFormerLatterMask) == kFormer) {
946            delta = offsetBefore;
947        } else {
948            // Interprets the time with rule after the transition,
949            // default for duplicated local time range
950            delta = offsetAfter;
951        }
952    }
953    return delta;
954}
955
956U_NAMESPACE_END
957
958#endif /* #if !UCONFIG_NO_FORMATTING */
959
960//eof
961
962