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