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