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