struct Note {

  // uint16_t indicates that the type is an unsigned (>= 0) 16-bit integer. We use this instead of things like short
  // or int because it guarantees that the 16-bit integer will be chosen.
  Note(const uint16_t& frequency, const unsigned long offset, const unsigned long duration): m_frequency(frequency), m_offset(offset), m_duration(duration) {
    if (frequency < 31) {
      // Under normal circumstances you would want to throw this string, but unfortunately that is not possible in
      // the Arduino subset of C++.
      Serial.println("ERROR: Frequency less than 31 Hz provided");
    }
  }
  
  const uint16_t& frequency() const { return m_frequency; }
  const unsigned long& offset() const { return m_offset; }
  const unsigned long& duration() const { return m_duration; }

  // This function is special in two ways: it overloads an operator and it is a friend. Operator overloading implements
  // the behavior of the given operator (in this case, the > operator) for the given signature (comparing two Notes).
  // This allows us to do something like note1 > note2 and get a sensible result.
  // friend indicates that this actually isn't a member function, but that wherever else it's defined it can access
  // private members of the instance.
  friend bool operator>(const Note& lhs, const Note& rhs);

private:

  uint16_t m_frequency;
  unsigned long m_offset;
  unsigned long m_duration;

};

// This is our actual implementation of >. It's declared inline to encourage the compiler to basically substitute the
// comparison in for efficiency.
// The const reference means we won't copy the note when trying to compare it, saving memory.
inline bool operator>(const Note& lhs, const Note& rhs) { return lhs.m_offset > rhs.m_offset; }

// Thanks to this for guiding me in creating what is basically a custom std::array for Notes: 
// https://arduino.stackexchange.com/a/69178
// This is what is known as a template declaration. Templates are probably one of the most complicated parts of C++,
// so I will keep my explanation brief. Basically, a template declaration indicates to the compiler that the following
// struct/class/variable/whatever declaration is a template for actual structures that will be compiled, subject to
// the given parameters. This particular one takes a single parameter called N of type size_t which indicates the
// length of the melody. When you declare a variable of type Melody<6> in a different file, that will tell the compiler
// to compile a version of this code where 6 is substituted for N in all the instances below.
// If you'd like to learn more, start with the Wikipedia page: https://en.wikipedia.org/wiki/Template_metaprogramming
template <size_t N>
struct Melody {

  // Unfortunately, using C arrays is weird. Thanks to this SO answer for resolving an issue I had:
  // https://stackoverflow.com/a/68745603
  Melody(const Note (&notes)[N]) : m_notes(notes) {
    setup();
  }

  static size_t length() { return N; }

  // The following two member function headers merely declare a method instead of implementing it. The implementation
  // is given in melody.ino. The reason why these are separated is because it speeds up compilation when modifying a
  // single .ino file, it's easier for someone using this header file to read what's going on, and it allows us to
  // change the implementation details while keeping them hidden from the client.
  const Note& operator[](const size_t& index) const;
  // The & indicates that we are returning a reference to the Note. If the client assigns the result of the subscript
  // operator to a variable and modifies it, it will also modify the note in the melody.
  // The const in the previous one prevents that, but it still saves memory by not copying the original Note.
  Note& operator[](const size_t& index);

  // The following member functions will cause Melody objects to be treated as iterators, which means we can use
  // enhanced for loops (for (Note note : melody)) on them.
  const Note* cbegin() const;
  Note* begin();
  // The const at the beginning indicates the result cannot be modified. The const at the end promises to the compiler
  // that the Melody itself won't be modified when calling this member function.
  const Note* cend() const;
  Note* end();

private:

  void setup();

  Note m_notes[N];

};

// This function is not a member of the struct, but it will still be #included.
template <size_t length>
void playMelody(uint8_t buzzerPin, const Melody<length>& melody);

// Because we're no longer inside the Melody struct, we need to enter its namespace by typing out the name of the struct,
// resolving its template arguments, and then using :: to find the thing we want.
template <size_t N>
void Melody<N>::setup() {
  sortInPlace(m_notes);
}

template <size_t N>
const Note& Melody<N>::operator[](const size_t& index) const {
  return m_notes[index]; 
}

template <size_t N>
Note& Melody<N>::operator[](const size_t& index) {
    return m_notes[index];
}

template <size_t N>
const Note* Melody<N>::cbegin() const { return &m_notes[0]; }

template <size_t N>
Note* Melody<N>::begin() { return &m_notes[0]; }

template <size_t N>
const Note* Melody<N>::cend() const { return &m_notes[N]; }

template <size_t N>
Note* Melody<N>::end() { return &m_notes[N]; }

template <size_t length>
void playMelody(uint8_t buzzerPin, const Melody<length>& melody) {
  delay(melody.cbegin()->offset());
  // This is called the iterator pattern for "for" loops, and it's much safer than using raw indices.
  for (Note* note = melody.begin(); note < melody.end() - 1; note++) {
    Serial.println(note->frequency());
    tone(buzzerPin, note->frequency(), note->duration());
    // delay() suspends execution for the given number of milliseconds. In this case, we're calculating the differences
    // in offsets to determine the space between adjacent notes.
    delay((note + 1)->offset() - note->offset());
  }
  tone(buzzerPin, (melody.cend() - 1)->frequency(), (melody.cend() - 1)->duration());
  delay((melody.cend() - 1)->duration());
  noTone(buzzerPin);
}

// If the melody has no notes, then do nothing.
template <>
void playMelody<0>(uint8_t, const Melody<0>&) {}

/// Sorts the given Note array in place.
template <size_t N>
void sortInPlace(Note (&notes)[N]) {
  for (size_t i = 1; i < N; i++) {
    for (int j = i; j >= 0; j--) {
      if (notes[j - 1] > notes[j]) {
        swap(notes[j - 1], notes[j]);
      }
    }
  }
}

template <typename T>
void swap(T& a, T& b) {
  T tmp = a;
  a = b;
  b = tmp;
}

// The double braces here are necessary.
const Melody<45> THRILLER = {{
  {415, 250, 142},
  {494, 500, 142},
  {415, 750, 142},
  {554, 1000, 335},
  {494, 1375, 978},
  {494, 3000, 443},
  {466, 3500, 443},
  {415, 4000, 443},
  {415, 4750, 208},
  {415, 5000, 250},
  {370, 5250, 208},
  {370, 5500, 142},
  {311, 5750, 125},
  {330, 5875, 297},
  {277, 6250, 142},
  {370, 6500, 142},
  {311, 6750, 107},
  {415, 6875, 375},
  {370, 7250, 142},
  {370, 7500, 142},
  {311, 7750, 125},
  {370, 7875, 297},
  {415, 8250, 142},
  {494, 8500, 142},
  {415, 8750, 142},
  {554, 9000, 335},
  {494, 9375, 978},
  {494, 11000, 443},
  {466, 11500, 443},
  {415, 12000, 443},
  {415, 12750, 208},
  {415, 13000, 250},
  {370, 13250, 208},
  {370, 13500, 142},
  {330, 13750, 107},
  {277, 13875, 297},
  {277, 14250, 142},
  {311, 14500, 142},
  {330, 14750, 142},
  {330, 15250, 142},
  {277, 15500, 142},
  {415, 16000, 142},
  {330, 16250, 142},
  {494, 16750, 228},
  {554, 17000, 1458}
}};

const int BUZZER_PIN = 8;

// Ensures the melody plays only once
bool shouldPlayMelody = true;

void setup() {
  // put your setup code here, to run once:
  // Where was Serial.begin included from, you may ask? The answer is the header file declaring it is automatically
  // #included at the top as a feature of the Arduino system.
  Serial.begin(9600);
}

void loop() {
  // put your main code here, to run repeatedly:
  if (shouldPlayMelody) {
    // The playMelody function was #included from melody.hpp. If the implementation is changed down the road, we don't
    // need to do anything in this file unless the signature changed.
    playMelody(BUZZER_PIN, THRILLER);
    shouldPlayMelody = false;
  }
}