Method and apparatus for representing recurring events

Abstract

A method and apparatus for representing and storing the schedules of recurring events. The schedules are represented by recurrence rules generated according to a specific grammar. According to the grammar, each recurrence rule is composed of one or more recurrence commands. Each recurrence command corresponds to a cycle and includes a time interval indicator that specifies the duration of the cycle and a repeat quantity that determines the number of times the cycle is repeated in the schedule. Each recurrence command may also include an occurrence list that specifies at what times during a particular cycle the event occurs. The occurrence list may specify times in absolute or relative terms. Thus, the grammar supports recurrence rules for representing the schedule "first and tenth of every month" as well as the schedule "second Thursday and last Friday of every month". To represent schedules that terminate before the last event in the last cycle is completed, a symbol may be inserted into the occurrence list to distinguish the events that are performed on the last cycle from the events that are not performed on the last cycle. Complex schedules that involve cycles repeated within cycles are represented by multiple-command recurrence rules. The stored recurrence rules may be parsed to determine when events will occur. The grammar may be applied to a variety of applications, including calendar programs, video cassette recorders and home automation devices.

Claims

What is claimed is:

1. A method for representing a schedule of a recurring event in an electronic device, wherein the schedule includes one or more cycles, wherein each of said one or more cycles has a length, the method comprising causing the electronic device to perform the steps of:

a) for each cycle in said schedule, performing the steps of

a1) receiving a first input that specifies a unit of time used to measure the length of said cycle;

a2) receiving a second input that specifies a number of time units;

a3) generating a time-interval indicator representing the length of said cycle;

wherein said step of generating said time-interval indicator includes the steps of

generating a unit-type indicator corresponding to said unit of time;

generating a unit-frequency indicator corresponding to said number of time units;

a4) generating a repeat-quantity indicator representing how many times said cycle is repeated in said schedule;

a5) generating a recurrence command to represent said cycle, said recurrence command including said time-interval indicator and said repeat-quantity indicator; and

b) constructing a recurrence rule to represent said schedule, wherein said recurrence rule includes the recurrence command generated for each cycle of said one or more cycles.

2. The method of claim 1 further comprising the steps of:

invoking an operation at an initial occurrence time;

parsing said recurrence rule to determine subsequent occurrence times; and

invoking said operation at said subsequent occurrence times.

3. The method of claim 1 wherein:

said electronic device is a computer system;

said computer system includes a display device and a storage device;

the method includes the steps of

storing data representing said recurrence rule on said storage device; and

generating on said display device user interface controls for receiving said first input and said second input from a user.

4. The method of claim 3 wherein:

the method further comprises the steps of

executing a client application in said computer system; executing a server application in said computer system;

said client application performs said step of generating on said display device user interface controls;

said client application performs said step of receiving said first input;

said client application performs said step of receiving said second input;

said client application performs said step of constructing said recurrence rule to represent said schedule;

said client application transmits said recurrence rule to said server application; and

said server application performs said step of storing data representing said recurrence rule on said storage device.

5. The method of claim 1 wherein a given cycle of said one or more cycles includes a plurality of occurrences of said recurring event, wherein said plurality of occurrences do not occur according to a uniform interval, the method further comprising the step of:

receiving a third input indicating when said plurality of occurrences occur during said given cycle; and

wherein said step of generating said recurrence command to represent said given cycle includes generating an occurrence list representing when said plurality of occurrences occur.

6. The method of claim 5 wherein said occurrence list represents when at least one of said plurality of occurrences occurs with an absolute occurrence specifier.

7. The method of claim 6 wherein said occurrence list includes data representing a weekday and data representing a relative occurrence of said weekday within a month.

8. The method of claim 5 wherein said occurrence list represents when at least one of said plurality of occurrences occurs with a relative occurrence specifier.

9. The method of claim 1 wherein said step of constructing said recurrence rule includes placing said recurrence command in an order based on the length of the cycle represented by said recurrence command for each cycle of said one or more cycles.

10. The method of claim 1 wherein the cycle is repeated N times during said schedule, wherein N represents a non-negative integer, wherein said recurring event takes place on a relative occurrence of a certain weekday in a month, the method further comprising the steps of:

generating a repeat-quantity indicator representing the value of N; and

generating a relative occurrence specifier that indicates said relative occurrence of said certain weekday in said month.

11. A method for representing in an electronic device a schedule of a recurring event, wherein the schedule includes a cycle of a certain duration, wherein the cycle is repeated N times during the schedule, wherein N is at least two, wherein during the first N-1 iterations of the cycle said recurring event occurs at a first set of times and a second set of times, wherein during the Nth iteration of said cycle said recurring event occurs at said first set of times but not at said second set of times, the method comprising the steps of:

generating a time-interval indicator representing said certain duration;

generating a repeat-quantity indicator representing the value of N;

generating an occurrence list including data representing said first set of times and said second set of times;

inserting at least one symbol into said occurrence list to distinguish between said first set of times and said second set of times.

12. The method of claim 11 wherein said step of generating said occurrence list includes generating an occurrence list in which data indicating said first set of times precedes data indicating said second set of times, wherein said step of inserting one or more symbols includes inserting one or more symbols between the data indicating said first set of times and the data representing said second set of times.

13. An apparatus for storing a representation of a schedule of a recurring event, the apparatus comprising:

an input device for receiving input representing said schedule;

a processor coupled to said input device, said processor receiving said input from said input device and generating a recurrence rule based on a grammar, wherein said recurrence rule represents said schedule of said recurring event; and

a storage device coupled to said processor, said processor storing data representing said recurrence rule on said storage device;

wherein said recurrence rule includes one or more recurrence commands, wherein each recurrence command of said recurrence rule represents a repeating cycle in said schedule;

wherein said grammar includes rules for constructing time-interval indicators for representing cycles that repeat every N.sub.1 minutes, every N.sub.2 days, every N.sub.3 weeks, every N.sub.4 months on a relative day and week, every N.sub.5 months on an absolute day, every N.sub.6 years on one or more specific months, and every N.sub.7 years on one or more specific days of the year, where N.sub.1 -N.sub.7 are each any natural number.

14. The apparatus of claim 13 wherein said grammar includes rules for constructing repeat-quantity indicators for representing how many times a cycle repeats in said schedule.

15. The apparatus of claim 14 wherein said repeat-quantity indicators comprise a repeat-quantity symbol and a number.

16. The apparatus of claim 13 wherein said grammar includes rules for constructing occurrence lists, wherein said occurrence lists indicate times that said recurring event occurs during said repeating cycle.

17. The apparatus of claim 16 wherein said grammar includes rules for constructing occurrence lists that represent specific hours in a day, specific weekdays in a week, specific days in a month, specific months in a year and specific days in a year.

18. The apparatus of claim 16 wherein said grammar includes rules for constructing occurrence lists that represent relative occurrences of weekdays in a month.

19. The apparatus of claim 13 wherein said grammar includes rules for specifying any number of occurrences of said recurring event within a repeating cycle in said schedule.

20. The apparatus of claim 13 wherein said grammar includes a first rule for specifying an absolute end time and a second rule for determining an end time by specifying a number of repetitions of each repeating cycle in said schedule.

21. A method for representing a schedule of a recurring event in an electronic device, wherein the schedule includes a plurality of cycles, wherein each of said plurality of cycles has a length, the method comprising causing the electronic device to perform the steps of:

a) for each cycle in said schedule, performing the steps of

a1) generating a time-interval indicator representing the length of said cycle;

a2) generating a recurrence command to represent said cycle, said recurrence command including said time-interval indicator, and

b) constructing a recurrence rule to represent said schedule, wherein said recurrence rule includes the recurrence command generated for each cycle of said plurality of cycles; wherein:

said schedule includes a first cycle and a second cycle;

said schedule includes repeating one of said first cycle and said second cycle within the other of said first cycle and said second cycle;

said first cycle has a duration that does not vary;

said second cycle has a duration that varies based on a selective relative occurrence;

said step of a1) generating a time-interval indicator includes the steps of

generating a first time-interval indicator representing the length of said first cycle; and

generating a second time-interval indicator representing the length of said second cycle;

wherein said step of a2) generating a recurrence command includes

generating a first recurrence command to represent said first cycle; and

generating a second recurrence command to represent said second cycle;

wherein said step of b) constructing a recurrence rule includes constructing a recurrence rule that includes said first recurrence command and said second recurrence command.

22. The method of claim 21 wherein said selected relative occurrence is a relative occurrence of a weekday in a month.

Description

FIELD OF THE INVENTION

The present invention relates to a method and apparatus for generating and storing data representing recurring calendar events, and more specifically, to a method and apparatus for representing in a concise, parsable grammar the timing of events that recur according to complex timing patterns.

BACKGROUND OF THE INVENTION

Numerous software programs have been developed that allow users to store schedules of events into a computer. Typically, such programs also generate visual displays that illustrate the events that will occur during a specified time period (e.g. calendars). Using such programs, users may, for example, enter information about events that are scheduled to occur during a particular month. The software stores the information on a storage device. At any time thereafter, users may instruct the software to generate a calendar of the month. When generating the calendar, the software generates indications of the scheduled events on the appropriate days of the calendar.

Calendar applications that use a client/server model have been developed. With such applications, a user interacts with a client application to enter information about events, including when the events will occur. The client application transmits data representing the events to a server application. The server application stores data representing the events. Subsequently, the client application may transmit data representing a time period, such as a particular month or year, to the server application. The server application reads the stored event data, determines which events are scheduled to occur during the specified time period, and transmits data representing the appointments that are scheduled to occur during the specified time period back to the client application. The client application then generates a calendar of the specified time period along with visual indications of the events that will occur during the specified time period.

Some events occur on a regular basis. Rather than require a user to enter information for each occurrence of a recurring event, most calendar applications allow the user to specify a first occurrence of the event and a recurrence interval for the event. For example, a user may have to attend a certain meeting every Friday at 10:00 am. Rather than enter information for each occurrence of the meeting, the user can enter information about the first occurrence of the meeting and an indication that the meeting takes place on a weekly basis (the "recurrence interval").

When generating a calendar for a particular time period, calendar applications that support recurring events must calculate if and when the event will occur during the particular time period. The calendar application makes this determination based on the initial occurrence time and the recurrence interval. Typically, a calendar application makes this determination when a user requests a calendar display of a particular period.

Current calendar applications support many typical recurrence intervals. For example, some current calendar applications allow a user to specify that an event recurs daily, weekly, monthly, or Monday through Friday. However, events that recur at less typical intervals may require multiple entries. For example, to specify an event that occurs every Monday and Wednesday, a user may have to schedule the event as if it were two weekly events. That is, the user may have to input a first event entry to indicate that the event occurs weekly every Monday, and then a second event entry to indicate that the event occurs weekly every Wednesday. Events that recur at less regular patterns may be even more difficult to specify. Consider, for example, an event that occurs on the second Tuesday and the fourth Friday of every month.

Events that recur at smaller intervals within larger intervals may be impossible to specify using current calendar applications. For example, consider an event that occurs every Monday (weekly) of every third month (monthly). Similarly, consider an event that occurs every hour (hourly) of every Wednesday (weekly).

It is clearly desirable to provide a mechanism to represent complex schedules with single event entries. It is further desirable that the schedules be represented and stored in a concise fornat to minimize the storage space required for event schedule information.

SUMMARY OF THE INVENTION

According to one aspect of the invention, a method and apparatus for representing and storing the schedules of recurring events is provided. The schedules are represented by recurrence rules generated according to a grammar. According to the grammar, each recurrence rule is composed of one or more recurrence commands. Each recurrence command corresponds to a cycle in a schedule and includes a time interval indicator that specifies the duration of the cycle and a repeat quantity that specifies the number of times the cycle is repeated in the schedule.

Each recurrence command may also include an occurrence list that specifies at what times during a particular cycle the event occurs. The occurrence list may specify times in absolute or relative terms. For example, the grammar supports recurrence rules for representing the schedule "first and tenth of every month" as well as the schedule "second Thursday and last Friday of every month".

For schedules that terminate before the last event in the last cycle is completed, a symbol is inserted into the occurrence list to distinguish the events that are performed on the last cycle from the events that are not performed on the last cycle. Complex schedules that involve cycles repeated within cycles are represented by multiple-command recurrence rules.

The stored recurrence rules may be parsed to determine when events will occur. The grammar may be applied to a variety of applications, including calendar programs, video cassette recorders and home automation devices. By storing complex schedules as concise rules, electronic devices may save storage space and reduce schedule-related communication traffic.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1 is a block diagram illustrating a computer system upon which an embodiment of the invention may be implemented;

FIG. 2 is a block diagram illustrating a client/server calendar application according to one embodiment of the invention;

FIG. 3 illustrates an exemplary user interface for receiving information about a complex event schedule from a user; and

FIG. 4 illustrates a calendar generated by a calendar application based on recurrence rules according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A method and apparatus for representing recurring events are described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

Referring to FIG. 1, a computer system 100 upon which an embodiment of the present invention can be implemented is shown. Computer system 100 comprises a bus or other communication means 101 for communicating information, and a processing means 102 coupled with bus 101 for processing information computer system 100 further comprises a random access memory (RAM) or other dynamic storage device 104 (referred to as main memory), coupled to bus 101 for storing information and instructions to be executed by processor 102. Main memory 104 also may be used for storing temporary variables or other intermediate information during execution of instructions by processor 102. Computer system 100 also comprises a read only memory (ROM) and/or other static storage device 106 coupled to bus 101 for storing static information and instructions for processor 102. Data storage device 107 is coupled to bus 101 for storing information and instructions.

Furthermore, a data storage device 107 such as a magnetic disk or optical disk and its corresponding disk drive can be coupled to computer system 100. Computer system 100 can also be coupled via bus 101 to a display device 121, such as a cathode ray tube (CRT), for displaying information to a computer user. An alphanumeric input device 122, including alphanumeric and other keys, is typically coupled to bus 101 for communicating information and command selections to processor 102. Another type of user input device is cursor control 123, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 102 and for controlling cursor movement on display 121. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), which allows the device to specify positions in a plane.

In the currently preferred embodiment, computer system 100 is used for executing a calendar application. Processor 102 executes instructions stored in memory 104 which implement the calendar application. Execution of the instructions causes the calendar application to generate user interface controls on display 121 through which a user can enter information about recurring events, including the schedules of the recurring events.

When a user enters the schedule of a recurring event, the calendar application generates a recurrence rule that represents the schedule. In the preferred embodiment, recurrence rules are generated according to a concise, parsable grammar that will be described hereafter. The calendar application stores data representing the recurrence rules on storage device 107.

Using the grammar that will be described hereafter, even the schedules of events that recur according to complicated interval patterns can be represented with relatively concise recurrence rules. Consequently, by storing the schedules of events as recurrence rules according to the grammar, a significant amount of storage space may be saved. Further, in systems that implement client/server models of calendaring applications, the event scheduling information is often sent from the client application to the server application over a network. Therefore, by representing complex event schedules with concise rules, network traffic associated with the calendaring applications may be significantly reduced.

GRAMMAR FOR CONSTRUCTING RECURRENCE RULES

In the preferred embodiment of the invention, applications represent the schedules of recurring events in the form of recurrence rules. A recurrence rule is made up of one or more recurrence commands. Each recurrence command corresponds to a cycle within the represented schedule. Within a recurrence command, the duration of the corresponding cycle is represented by a time-interval indicator. Time-interval indicators as well as other components of recurrence commands are described in detail hereafter.

TIME-INTERVAL INDICATORS

A time-interval includes two components: a unit-type and a unit-frequency. The unit-type component expresses the granularity of the time-interval. Table 1 illustrates various unit-types supported in the preferred embodiment of the invention.

                  TABLE 1
    ______________________________________
    Unit-type
             Symbol  Meaning
    ______________________________________
    minuteop M       Defines a cycle that repeats on a
                     particular minute interval.
    daily    D       Defines a cycle that repeats on a daily basis.
    weekly   W       Defines a cycle that repeats on a weekly basis.
    monthlybypos
             MP      Defines a cycle that repeats on a monthly
                     basis on a relative day and week.
    monthlybyday
             MD      Defines a cycle that repeats on a monthly basis
                     on an absolute day.
    yearlybymonth
             YM      Defines a cycle that repeats on specific
                     months of the year.
    yearlybyday
             YD      Defines a cycle that repeats on specific days
                     of the year.
    ______________________________________

                  TABLE 2
    ______________________________________
    Time-interval Indicators
                      Meaning
    ______________________________________
    M5                Repeat every five minutes
    D1                Repeat daily
    D2                Repeat every other day
    D3                Repeat every third day
    W1                Repeat weekly
    W2                Repeat every other week
    W3                Repeat every third week
    ______________________________________

                  TABLE 3
    ______________________________________
    TERM/SYMBOL  MEANING
    ______________________________________
    {}           zero or more of the enclosed elements
    ›!           zero or one of the enclosed elements
    enddate      Controls when a repeating event terminates.
                 The enddate is the last time an event
                 can occur.
    unit-frequency
                 Controls the number of time units in an interval
    repeat-quantity
                 Controls the number of events a rule generates
    lastday      Can be used as a replacement to daynumber to
                 indicate the last day of the month. May be used
                 as an occurrence specifier in MD (monthly-by-
                 day) cycles.
    daynumber    A number representing a day of the month.
    month        A number representing a month of the year.
    day          A number representing a day of the year
    occurrence   Controls which week of the month a particular
                 weekday event occurs.
    weekday      A symbol representing a day of the week
    time         The time in hours and minutes using a 24 hour
                 clock.
    daytime      Controls which days (and hours) of the week a
                 weekly event occurs.
    weekdaytime  Used in monthly events to specify which
                 weeks, days and times an event occurs.
    ______________________________________


              TABLE 4
    ______________________________________
    start ::=  <minuteop>›<enddate>!.vertline.<daily>›<enddate>!.vertline.
               <weekly>›<enddate>!.vertline.<monthlybypos>›<enddate>!.vertline
               .
               <monthlybyday>›<enddate>!.vertline.<yearlybymonth>
               ›<enddate>!.vertline.<yearlybyday>›<enddate>!
    endmarker ::=
               $
    enddate ::=
               ISO 8601 (clause 5.4.1) string(e.g.
               19940712T101530Z) in UTC
    digits ::= natural numbers
    unit-frequency ::=
               <digits>
    repeat-quantity ::=
               #<digits>
    lastday ::=
               LD
    plus ::=   +
    minus ::=  -
    daynumber ::=
               <1-31>›endmarker>!.vertline.<lastday>
    daynumberlist ::=
               daynumber {<daynumber>}
    month ::=  <1-12>›<endmarker>!
    monthlist ::=
               <month> {<monthlist>}
    day ::=    <1-366>›<endmarker>!
    daylist ::=
               <day> {<daylist>}
    occurence ::=
               <1-5><plus>›<endmarker>!.vertline.<1-5><minus>
               ›<endmarker>!
    occurencelist ::=
               <occurence> {<occurencelist>}
    weekday ::=
               <SU.vertline.MO.vertline.TU.vertline.WE.vertline.TH.vertline.FR
               .vertline.SA>›<endmarker>!
    weekdaylist ::=
               <weekday> {<weekdaylist>}
    hhmm ::=   hours and minutes, where hh specifies two digits
               representing hours (00 to 23) and mm specifies
               two digits representing minutes (00 to 59).
    time ::=   <hhmm>›<endmarker>!
    timelist ::=
               <time> {<timelist>}
    daytime ::=
               <weekday> {<timelist>}
               {<daytime>}
    weekdaytime ::=
               <occurencelist> <weekdaylist> {<timelist>}
               {<weekdaytime>}
    minuteop ::=
               M<unit-frequency> ›<repeat-quantity>!
    daily ::=  D<unit-frequency>›<timelist>!›<repeat-quantity>!
               ›<minuteop>!
    weekly ::= W<unit-frequency>›<daytime>!
               ›<repeat-quantity>!›<minuteop>.vertline.
    monthlybypos ::=
               MP<unit-frequency>{<weekdaytime>!
               ›<repeat-quantity>!›<weekly>.vertline.
               <daily>.vertline.<minuteop>!
    monthlybyday ::=
               MD<unit-frequency>.about.<daynumberlist>!
               ›<repeat-quantity>!›<weekly>.vertline.<daily>.vertline.<minuteo
               p>!
    yearlybymonth ::=
               YM<unit-frequency>›<monthlist>!
               ›<repeat-quantity>!›<monthlybyday>.vertline.
               <monthlybypos>.vertline.<weekly>.vertline.<daily>.vertline.
               <minuteop>!
    yearlybyday ::=
               YD<unit-frequency>›<daylist>!›<repeat-quantity>!
               ›<monthlybyday>.vertline.<monthlybypos>.vertline.
               <weekly>.vertline.<daily>.vertline.
               <minuteop>!
    ______________________________________

• Inventors
  Kasso, Chris S.; Knutson, Martin Arthur; Tso, Yvonne Yuen-Yee; Dawson, Frank R.;
• Assignee
  Sun Microsystems, Inc. (Mountain View, CA); International Business Machines Corporation (Armonk, NY)
• Published
  Apr-6-1999
• Current US Classes:
  705/8
  705/9
  708/111
  708/112
• Application #
  395458
• International Classes
  G06F 007/60; G06G 007/52
• Field of Search
  395/201 395/207 395/208 364/705.07 364/705.08 368/1 368/9 368/10 368/243 368/244 368/250 368/251 368/327 705/1 705/7 705/8 705/9 705/11
• Examiner
  Weinhardt; Robert A.
• Agent
  Blakely Sokoloff Taylor & Zafman
• US Patent References:
  5260868
  5416473
  5491626