Getting Started

Choosing a representation for the Calendar

Let's think about how to represent the calendar itself. One possibility would be to represent it as a List of Appointments:

       #include <List.h>
       class Calendar {
           List<Appointment> appts;
       public:
           void add(const Appointment& a) {
               appts += a; // append to end of List
           }
       };

Another possibility is a Set of Appointments:

       #include <Set.h>
       class Calendar {
           Set<Appointment> appts;
       public:
           void add(const Appointment& a) {
               appts.insert(a); // insert into set
           }
       };

However, the classes List and Set do not lend themselves to efficient implementation of the required queries; a pass through the entire data structure would be required to find all the appointments for a given day.

Instead, we will use a data structure that can give direct access to the appointments for a single day. The Map(3C++) component provides class Map, which maps from a given key type to a given value type. Specifically, dates will be used for the keys, and the collection of Appointments for a given date will be used for the values:

   Map: date --> collection of Appointments on that date

This opens two problems: how to represent a date, and how to represent the collection of Appointments for a given date.

We will represent a date by the time at midnight on that date. For example, the time ``20 April 1984 00:00:00'' will represent the date of all times of the form ``20 April 1984 **:**:**'' Representing dates in this way will guarantee that all the Appointments falling on a given date have the same key in the above Map.

Here is the declaration of our Date type:

       class Date {
           Time midnight;
       public:
           Date(Time t) : midnight(midnight_before(t)) {}
           Date() {}
       };

Notice that the null constructor for Date simply invokes the null constructor for Time. This is acceptable since the manpage for Time(3C++) tells us that the default value for Time is midnight of January 1, 1970. Notice also that we do not make Date a (public) subclass of Time. This is because a Date conceptually is not a Time. For example, the Date ``20 April 1984'' does not conceptually denote a specific Time on that Date; the fact that we have chosen midnight to represent that Date is purely a representation detail.

The following function returns the midnight before a given Time:

       Time midnight_before(const Time& t) {
           return t - t.clock_part();
       }

Before we can declare a Map whose keys are of type Date, we must give Date a total order relation (the Map(3C++) manpage tells us this). Here it is:

       int operator<(Date a, Date b) {
           return a.midnight < b.midnight;
       }

Both this function and the Date output operator shown below will have to be made friends of Date, since they access Date's private member:

       class Date {
           friend int operator<(Date a, Date b);
           friend ostream& operator<<(ostream& os, Date d);
           // ...
       };

We will represent the collection of Appointments for a given Date by the following class:

       class Appts {
           // ...
       public:
           void add(const Appointment& a);
       };

We will complete the implementation of this class below.

Given the above definitions, our Calendar class looks like this:

       #include <Map.h>
       class Calendar {
           Map<Date,Appts> m;
       public:
           void add(const Appointment& a) {
               Date d(a.time);
               m[d].add(a);
           }
       };

Finally, we will also have need of the following definitions:

       typedef Mapiter<Date,Appts> Calendariter;
       class Calendar {
           Calendariter element(Date d) const {
               return m.element(d);
           }
           Calendariter first() const {
               return m.first();
           }
           const Appts& operator[](Date t) const {
               return ((Calendar*)this)->m[t];
           }
           // ...
       };

A Calendariter object provides a convenient way to march sequentially through the Appts stored in a Calendar. The first function returns an iterator over the Calendar starting at the given Date (if present in the Map). The second function returns an iterator starting at the beginning of the Calendar. The third function returns a reference to the Appts for the given Date. (The cast in the third is to convince the compiler this function really is const.)

The reason for each of these functions will become apparent below. Indeed, when developing this code, these functions were added when their utility became obvious, not when the class Calendar was first defined.