Transition.h

/*
 * MIT License
 * Copyright (c) 2019 Brian T. Park
 */
 
#ifndef ACE_TIME_EXTENDED_TRANSITION_H
#define ACE_TIME_EXTENDED_TRANSITION_H
 
#include <stdint.h> // uint8_t
#include "common/logging.h"
#include "local_date_mutation.h"
#include "DateTuple.h"
 
class TransitionStorageTest_getFreeAgent;
class TransitionStorageTest_getFreeAgent2;
class TransitionStorageTest_addFreeAgentToActivePool;
class TransitionStorageTest_reservePrior;
class TransitionStorageTest_addPriorToCandidatePool;
class TransitionStorageTest_addFreeAgentToCandidatePool;
class TransitionStorageTest_setFreeAgentAsPriorIfValid;
class TransitionStorageTest_addActiveCandidatesToActivePool;
class TransitionStorageTest_findTransitionForDateTime;
class TransitionStorageTest_resetCandidatePool;
 
class Print;
 
#ifndef ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
#define ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG 0
#endif
 
namespace ace_time {
namespace extended {
 
inline bool isCompareStatusActive(CompareStatus status) {
  return status == CompareStatus::kExactMatch
      || status == CompareStatus::kWithinMatch
      || status == CompareStatus::kPrior;
}
 
template<typename D>
struct MatchingEraTemplate {
  DateTuple startDateTime;
 
  DateTuple untilDateTime;
 
  typename D::ZoneEraBroker era;
 
  MatchingEraTemplate* prevMatch;
 
  int32_t lastOffsetSeconds;
 
  int32_t lastDeltaSeconds;
 
  void log() const {
    logging::printf("MatchingEra(");
    logging::printf("start="); startDateTime.log();
    logging::printf("; until="); untilDateTime.log();
    logging::printf("; era=%c", (era.isNull()) ? '-' : '*');
    logging::printf("; prevMatch=%c", (prevMatch) ? '*' : '-');
    logging::printf(")");
  }
};
 
//---------------------------------------------------------------------------
 
template <typename D>
struct TransitionTemplate {
 
  const MatchingEraTemplate<D>* match;
 
#if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
  typename D::ZoneRuleBroker rule;
#endif
 
  DateTuple transitionTime;
 
  union {
    DateTuple transitionTimeS;
 
    DateTuple startDateTime;
  };
 
  union {
    DateTuple transitionTimeU;
 
    DateTuple untilDateTime;
  };
 
#if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
  DateTuple originalTransitionTime;
#endif
 
  acetime_t startEpochSeconds;
 
  int32_t offsetSeconds;
 
  int32_t deltaSeconds;
 
  char abbrev[kAbbrevSize];
 
  union {
    bool isValidPrior;
 
    CompareStatus compareStatus;
  };
 
  const char* format() const {
    return match->era.format();
  }
 
  void log() const {
    logging::printf("Transition(");
    if (sizeof(acetime_t) <= sizeof(int)) {
      logging::printf("start=%d", startEpochSeconds);
    } else {
      logging::printf("start=%ld", startEpochSeconds);
    }
    logging::printf("; status=%d", compareStatus);
    logging::printf("; UTC");
    logHourMinuteSecond(offsetSeconds);
    logHourMinuteSecond(deltaSeconds);
    logging::printf("; tt="); transitionTime.log();
    logging::printf("; tts="); transitionTimeS.log();
    logging::printf("; ttu="); transitionTimeU.log();
  #if ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
    if (rule.isNull()) {
      logging::printf("; rule=-");
    } else {
      logging::printf("; rule=");
      logging::printf("[%d,%d]", rule.fromYear(), rule.toYear());
    }
  #endif
  }
 
  static void logHourMinuteSecond(int32_t seconds) {
    char sign;
    if (seconds < 0) {
      sign = '-';
      seconds = -seconds;
    } else {
      sign = '+';
    }
    uint16_t minutes = seconds / 60;
    uint8_t second = seconds - minutes * int32_t(60);
    uint8_t hour = minutes / 60;
    uint8_t minute = minutes - hour * 60;
    if (second == 0) {
      logging::printf("%c%02u:%02u", sign, (unsigned) hour, (unsigned) minute);
    } else {
      logging::printf("%c%02u:%02u:%02u",
          sign, (unsigned) hour, (unsigned) minute, (unsigned) second);
    }
  }
 
#ifdef ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG
  static void printTransitions(
      const char* prefix,
      const TransitionTemplate* const* begin,
      const TransitionTemplate* const* end) {
    for (const TransitionTemplate* const* iter = begin; iter != end; ++iter) {
      logging::printf(prefix);
      (*iter)->log();
      logging::printf("\n");
    }
  }
#endif
};
 
template <typename D>
struct TransitionForSecondsTemplate {
  const TransitionTemplate<D>* curr;
 
  uint8_t fold;
 
  uint8_t num;
};
 
template <typename D>
struct TransitionForDateTimeTemplate {
  const TransitionTemplate<D>* prev;
  const TransitionTemplate<D>* curr;
 
  uint8_t num;
};
 
template<uint8_t SIZE, typename D>
class TransitionStorageTemplate {
  public:
    typedef TransitionTemplate<D> Transition;
 
    typedef TransitionForSecondsTemplate<D> TransitionForSeconds;
 
    typedef TransitionForDateTimeTemplate<D> TransitionForDateTime;
 
    TransitionStorageTemplate() {}
 
    void init() {
      for (uint8_t i = 0; i < SIZE; i++) {
        mTransitions[i] = &mPool[i];
      }
      mIndexPrior = 0;
      mIndexCandidates = 0;
      mIndexFree = 0;
    }
 
    Transition* getPrior() {
      return mTransitions[mIndexPrior];
    }
 
    void resetCandidatePool() {
      mIndexCandidates = mIndexPrior;
      mIndexFree = mIndexPrior;
    }
 
    Transition** getCandidatePoolBegin() {
      return &mTransitions[mIndexCandidates];
    }
    Transition** getCandidatePoolEnd() {
      return &mTransitions[mIndexFree];
    }
 
    Transition** getActivePoolBegin() {
      return &mTransitions[0];
    }
    Transition** getActivePoolEnd() {
      return &mTransitions[mIndexFree];
    }
 
    Transition* getFreeAgent() {
      if (mIndexFree < SIZE) {
        // Allocate a free transition.
        if (mIndexFree >= mAllocSize) {
          mAllocSize = mIndexFree + 1;
        }
        return mTransitions[mIndexFree];
      } else {
        // No more transition available in the buffer, so just return the last
        // one. This will probably cause a bug in the timezone calculations, but
        // I think this is better than triggering undefined behavior by running
        // off the end of the mTransitions buffer.
        return mTransitions[SIZE - 1];
      }
    }
 
    void addFreeAgentToActivePool() {
      if (mIndexFree >= SIZE) return;
      mIndexFree++;
      mIndexPrior = mIndexFree;
      mIndexCandidates = mIndexFree;
    }
 
    Transition** reservePrior() {
      getFreeAgent(); // allocate a new Transition
 
      mIndexCandidates++;
      mIndexFree++;
      return &mTransitions[mIndexPrior];
    }
 
    void setFreeAgentAsPriorIfValid() {
      Transition* ft = mTransitions[mIndexFree];
      Transition* prior = mTransitions[mIndexPrior];
      if ((prior->isValidPrior && prior->transitionTime < ft->transitionTime)
          || !prior->isValidPrior) {
        ft->isValidPrior = true;
        prior->isValidPrior = false;
        swap(mTransitions[mIndexPrior], mTransitions[mIndexFree]);
      }
    }
 
    void addPriorToCandidatePool() {
      mIndexCandidates--;
    }
 
    void addFreeAgentToCandidatePool() {
      if (mIndexFree >= SIZE) return;
 
      // This implementation makes pair-wise swaps to shift the current
      // Transition leftwards into its correctly sorted position. At first
      // glance, this seem inefficient compared to the alternative
      // implementation where we save the current Transition, then slide all the
      // elements to the left by one position rightwards. However,
      // MemoryBenchmark shows that this implementation is 46 bytes smaller on
      // an AVR processor.
      for (uint8_t i = mIndexFree; i > mIndexCandidates; i--) {
        Transition* curr = mTransitions[i];
        Transition* prev = mTransitions[i - 1];
        if (curr->transitionTime >= prev->transitionTime) break;
        mTransitions[i] = prev;
        mTransitions[i - 1] = curr;
      }
      mIndexFree++;
    }
 
    Transition* addActiveCandidatesToActivePool() {
      if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
        logging::printf("addActiveCandidatesToActivePool()\n");
      }
 
      // Shift active candidates to the left into the Active pool.
      uint8_t iActive = mIndexPrior;
      uint8_t iCandidate = mIndexCandidates;
      for (; iCandidate < mIndexFree; iCandidate++) {
        if (isCompareStatusActive(mTransitions[iCandidate]->compareStatus)) {
          if (iActive != iCandidate) {
            // Must use swap(), because we are moving pointers instead of the
            // actual Transition objects.
            swap(mTransitions[iActive], mTransitions[iCandidate]);
          }
          ++iActive;
        }
      }
 
      mIndexPrior = iActive;
      mIndexCandidates = iActive;
      mIndexFree = iActive;
 
      return mTransitions[iActive - 1];
    }
 
    TransitionForSeconds findTransitionForSeconds(acetime_t epochSeconds)
        const {
      if (ACE_TIME_EXTENDED_ZONE_PROCESSOR_DEBUG) {
        logging::printf(
            "findTransitionForSeconds(): mIndexFree: %d\n", mIndexFree);
      }
 
      const Transition* prev = nullptr;
      const Transition* curr = nullptr;
      const Transition* next = nullptr;
      for (uint8_t i = 0; i < mIndexFree; i++) {
        next = mTransitions[i];
        if (next->startEpochSeconds > epochSeconds) break;
        prev = curr;
        curr = next;
        next = nullptr;
      }
 
      uint8_t fold;
      uint8_t num;
      calcFoldAndOverlap(&fold, &num, prev, curr, next, epochSeconds);
      //fprintf(stderr, "prev=%p;curr=%p;next=%p;fold=%d;num=%d\n",
      //  prev, curr, next, fold, num);
      return TransitionForSeconds{curr, fold, num};
    }
 
    static void calcFoldAndOverlap(
        uint8_t* fold,
        uint8_t* num,
        const Transition* prev,
        const Transition* curr,
        const Transition* next,
        acetime_t epochSeconds) {
 
      if (curr == nullptr) {
        *fold = 0;
        *num = 0;
        return;
      }
 
      // Check if within forward overlap shadow from prev
      bool isOverlap;
      if (prev == nullptr) {
        isOverlap = false;
      } else {
        // Extract the shift from prev transition. Can be 0 in some cases where
        // the zone changed from DST of one zone to the STD into another zone,
        // causing the overall UTC offset to remain unchanged.
        acetime_t shiftSeconds = subtractDateTuple(
            curr->startDateTime, prev->untilDateTime);
        if (shiftSeconds >= 0) {
          // spring forward, or unchanged
          isOverlap = false;
        } else {
          // Check if within the forward overlap shadow from prev
          isOverlap = epochSeconds - curr->startEpochSeconds < -shiftSeconds;
        }
      }
      if (isOverlap) {
        *fold = 1; // epochSeconds selects the second match
        *num = 2;
        return;
      }
 
      // Check if within backward overlap shawdow from next
      if (next == nullptr) {
        isOverlap = false;
      } else {
        // Extract the shift to next transition. Can be 0 in some cases where
        // the zone changed from DST of one zone to the STD into another zone,
        // causing the overall UTC offset to remain unchanged.
        acetime_t shiftSeconds = subtractDateTuple(
            next->startDateTime, curr->untilDateTime);
        if (shiftSeconds >= 0) {
          // spring forward, or unchanged
          isOverlap = false;
        } else {
          // Check if within the backward overlap shadow from next
          isOverlap = next->startEpochSeconds - epochSeconds <= -shiftSeconds;
        }
      }
      if (isOverlap) {
        *fold = 0; // epochSeconds selects the first match
        *num = 2;
        return;
      }
 
      // Normal single match, no overlap.
      *fold = 0;
      *num = 1;
    }
 
    TransitionForDateTime findTransitionForDateTime(
        const LocalDateTime& ldt) const {
      // Convert LocalDateTime to DateTuple.
      DateTuple localDate{
          ldt.year(),
          ldt.month(),
          ldt.day(),
          ((ldt.hour() * int32_t(60) + ldt.minute()) * 60 + ldt.second()),
          extended::Info::ZoneContext::kSuffixW,
      };
 
      // Examine adjacent pairs of Transitions, looking for an exact match, gap,
      // or overlap.
      const Transition* prev = nullptr;
      const Transition* curr = nullptr;
      uint8_t num = 0;
      for (uint8_t i = 0; i < mIndexFree; i++) {
        curr = mTransitions[i];
 
        const DateTuple& startDateTime = curr->startDateTime;
        const DateTuple& untilDateTime = curr->untilDateTime;
        bool isExactMatch = (startDateTime <= localDate)
            && (localDate < untilDateTime);
 
        if (isExactMatch) {
          // Check for a previous exact match to detect an overlap.
          if (num == 1) {
            num++;
            break;
          }
 
          // Loop again to detect an overlap.
          num = 1;
        } else if (startDateTime > localDate) {
          // Exit loop since no more candidate transition.
          break;
        }
 
        prev = curr;
 
        // Set the curr to nullptr so that if the loop runs off the end of the
        // list of Transitions, the curr is marked as nullptr.
        curr = nullptr;
      }
 
      // Check if the prev was an exact match, and set the curr to be identical.
      // avoid confusion.
      if (num == 1) {
        curr = prev;
      }
 
      // This should get optimized by RVO.
      return TransitionForDateTime{prev, curr, num};
    }
 
    void log() const {
      logging::printf("TransitionStorage: ");
      logging::printf("SIZE=%d, mAllocSize=%d\n", SIZE, mAllocSize);
      int nActives = mIndexPrior;
      int nPrior = mIndexCandidates - mIndexPrior;
      int nCandidates = mIndexFree - mIndexCandidates;
      int nAllocFree = mAllocSize - mIndexFree;
      int nVirginFree = SIZE - mAllocSize;
 
      logging::printf("  Actives: %d\n", nActives);
      Transition::printTransitions(
          "    ", &mTransitions[0], &mTransitions[mIndexPrior]);
 
      logging::printf("  Prior: %d\n", nPrior);
      Transition::printTransitions(
          "    ", &mTransitions[mIndexPrior], &mTransitions[mIndexCandidates]);
 
      logging::printf("  Candidates: %d\n", nCandidates);
      Transition::printTransitions(
          "    ", &mTransitions[mIndexCandidates], &mTransitions[mIndexFree]);
 
      logging::printf("  Allocated Free: %d\n", nAllocFree);
      logging::printf("  Virgin Free: %d\n", nVirginFree);
    }
 
    void resetAllocSize() { mAllocSize = 0; }
 
    uint8_t getAllocSize() const { return mAllocSize; }
 
  private:
    friend class ::TransitionStorageTest_getFreeAgent;
    friend class ::TransitionStorageTest_getFreeAgent2;
    friend class ::TransitionStorageTest_addFreeAgentToActivePool;
    friend class ::TransitionStorageTest_reservePrior;
    friend class ::TransitionStorageTest_addPriorToCandidatePool;
    friend class ::TransitionStorageTest_addFreeAgentToCandidatePool;
    friend class ::TransitionStorageTest_setFreeAgentAsPriorIfValid;
    friend class ::TransitionStorageTest_addActiveCandidatesToActivePool;
    friend class ::TransitionStorageTest_findTransitionForDateTime;
    friend class ::TransitionStorageTest_resetCandidatePool;
 
    Transition* getTransition(uint8_t i) {
      return mTransitions[i];
    }
 
    Transition mPool[SIZE];
    Transition* mTransitions[SIZE];
    uint8_t mIndexPrior;
    uint8_t mIndexCandidates;
    uint8_t mIndexFree;
 
    uint8_t mAllocSize = 0;
};
 
} // namespace extended
} // namespace ace_time
 
#endif