In this chapter, we present the libraries developed during the internship. For each one, we introduce the palette of available components, the class hierarchy of the library and some collaboration diagrams that explain, based on examples, how the library works. Some algorithms are also briefly explained. Finally, we present examples of reuse of these libraries. But before this presentation, a short description of the formalism used is introduced.
Two annexes are also available in direct relation with the study. Annex A contains the source code of some methods written with the VSE language, which presents algorithms of general purpose that can easily be reused and adapted to another language. Annex B contains the dictionary of the libraries. There is an exhaustive list of all the methods and attributes of each class created in the libraries and for each one a brief description. The aim of this annex is to give complementary details to the presentation of this chapter.
The formalism used here is inspired from the Unified Modeling Language (UML) (see [OMG Web]). Some adaptations have been made according to the specificity of VSE. Hence, we present here the three different kinds of diagram we will use to explain a model or a library. There are the class hierarchy, the component hierarchy and the collaboration diagrams.
This diagram introduces the graph of inheritance of the classes. The inheritance relationship is symbolized as shown by Figure 33. The arrow represented the inheritance shows the superclass with its end extremity and the subclass with its start extremity. Finally, the boxes represent the classes. In the class hierarchy diagram, the attributes and the methods of each class are also represented (see Figure 34). Words in italic font are attribute descriptions, whereas the words in normal font are method descriptions. Our formalism describes an attribute by giving its name then its type, both separated by a colon. For readability reasons, only the name of the methods is given, with the same syntax as in the VSE language. A colon in the name of a method indicates that it needs an argument. However, to know the type of an argument, the reader must consult the dictionary of the libraries in annex B.
Figure 34 presents two ways to describe a class. The first, on the left, represents a class having both class and instance characteristics, whereas the other one represents a class with only instance characteristics. In the first case, the upper box is for the class methods and attributes and the lower one for the instance characteristics. In the second case, there is only one box for the instance attributes and methods.
In VSE, an attribute or an argument of a method can have a standard type, like integer or real, or can be a reference to an object of a given class. For instance, an attribute referencing a shape will have the type VSShape reference. In our presentation, we will never specify the term reference. It will be implicit that attributes and arguments representing objects are in fact object references, and not the objects themselves.
Figure 35 presents how our formalism represents some particular cases. The first is the notation for the overridden methods. We saw earlier that it is possible to modify or replace a method inherited from a superclass. In our formalism, when an asterisk is put after the name of a method in the class hierarchy diagram, that means the method has been overridden. The subclass brings new features, a new behavior for this method. However it does not specify if the method is totally replaced or just completed.
Another particular formalism is the representation of a collection of objects. During the presentation of VSE, we saw that the standard library provides classes to represent a collection of objects. The metaclass for that is VSContainer and two subclasses allow the instantiation of two kinds of object: a list (VSList) or a dictionary (VSDictionary). The access to the objects can be performed sequentially or directly by giving the position of the object in the list, or its key if it is in a dictionary. To represent a collection of objects, we choose the formalism presented by Figure 35. The attributes in this example represent respectively a list of integers and a dictionary of shapes. First the type of the container is indicated, and then, between brackets, the type of the collected objects is defined.
We have seen that a model has a hierarchy of components due to the fact that a component can be decomposed. Figure 37 shows the formalism chosen to represent this kind of decomposition. A component hierarchy deals with objects whereas the class hierarchy deals with classes. Then, we will see that a collaboration diagram can deal with both the classes and the objects. Hence, a different notation is used to represent a class or an object. Classes and objects are represented by a box, but the name of the objects is underlined. Figure 36 represents an object with the left box and a class with the other one. Moreover, to describe an object, both its name and its class are specified. First the name is written and then, separated by a colon, the name of the class is indicated.
Figure 37 presents an example of decomposition of components, representing a component hierarchy. An arrow formalizes the relationship of decomposition. The start extremity of the arrow points the object that is decomposed and the end extremity of the arrow points the object belonging to this decomposition.
A component can possess several times the same kind of object. For this reason, if is possible to indicate how many times the relationship exists. In our example, we see that the component France of the class Country has a capital and several other cities, all of the class City.
Collaboration diagrams present examples of the behavior of a part of a model. Usually it deals with instances, but sometimes classes are directly implied. A collaboration diagram shows the sequence of messages exchanged between objects and classes, considering a particular case. Hence, through several examples explained by collaboration diagrams, it is possible to present in details the behavior of a model or a library of components.
Figure 38 presents the formalism of a collaboration diagram. As the class hierarchy and component hierarchy diagrams, a box represents either an object or a class. Then, a sequence of message exchanges is represented. An arrow specifies a message passing. Its start extremity points the object or the class sending the message, and its end extremity points the entity receiving the message. Messages are numbered to indicate the chronology of the message exchanges. The name of the message is written near the arrow and the arguments are also showed using the formalism of the VSE language. Arrows with a discontinuous line represents a reference to an object. That means the object or class the arrow starts from references the other object, i.e. an attribute of the first object references the other one.
For the purpose of animation or not, the movement of dynamic objects in a layout can be complex to manage. In fact, there can be a lot of interactions between the dynamic objects. That means the designer will spend a long time to find a way to model the movement and validate it. The aim of this library is to provide a generic solution for the movement of dynamic objects in a layout, with as less programming as possible during the reuse step. This library can be used both for the purpose of animation and for a real need in the modeling.
To present this library, we first introduce briefly each template provided in the palette of the library. The templates allow the building of a graph, a network of spots, to describe the movement of dynamic objects in the layout of a component, and the control of these movements with as less programming as possible. Then, we will present some collaboration diagrams to explain more precisely the internal behavior of the library. Finally, we will discuss briefly about the algorithm used to allow a dynamic object to move by itself to its next destination.
This library appears to be time consuming, so the aim of such a detailed presentation of the internal behavior of the library is to bring information to show what has been done and what can be done to ameliorate, optimize the library. We will see that we have chosen here the assurance of no blocking of the dynamic objects opposed to fast algorithms. The names of the classes and types defined in this library begin with the letters SP.
The purpose of this library is the movement of dynamic objects in a layout. To use correctly the library, a dynamic object must belong to the SPDynamicObject class or one of its subclasses. It is a specialization of the standard VSDynamicObject class. The aim of this library is to provide a way to let dynamic objects moving autonomously. By autonomous we mean, giving the object a destination spot and a reference moving time, corresponding to its moving speed, the object is able to reach its target as soon as possible, following a given set of rules.
To control movements, a dynamic object has many attributes we describe here. First, it has a priority level that offers an object to have the priority upon another one to move. Then, a dynamic object belongs to a group identified by a number. It is a way to distinguish objects and apply different rules upon them. Another attribute a dynamic object possesses is a moving direction. It comes from the example of the airplane. The same way is used by the passengers to go to their seat during the boarding and to leave them during the landing. So, we will speak of normal direction and inverse direction. We will describe this notion later when explaining the SPLink component.
To define the rules of moving, the user must first build a graph, a network of spots. A spot represents a point where a dynamic object can move. To move from a spot to another, spots are linked. Two spots are linked means that there is a way for a dynamic object to move directly from one spot to another.
A spot is more precisely a point where a dynamic object can come. After its arrival, a dynamic object can undergo any kind of operation. The library provides different types of spot: SPMoveSpot, SPChangePrioritySpot, SPEntranceSpot, SPExitSpot and SPComponent. We describe them now.
It is a spot where arriving dynamic objects are automatically, and as soon as possible, moved to their next destination. There are three kinds of move spot provided by the library.
This component is a spot. When a dynamic object arrives on it, it is placed in a list of waiting objects to be served. These objects wait for undergoing an operation. That means the user of the library will have to define the operation to perform and when a dynamic object becomes available to move to another component.
A link associates two spots. It indicates that a dynamic object can move between them. However, two spots A and B are linked does not mean that a dynamic object can move both from A to B and from B to A. In fact, a link can be unidirectional or bidirectional. Figure 40 presents the two kinds of link represented by a line for the bidirectional link and an arrow for the unidirectional link. Let us explain now the notion of normal or inverse direction of a dynamic object. If we consider the unidirectional link, a dynamic object with a normal direction is allowed to move from A to B, but not from B to A. If the dynamic object has an inverse direction, it is allowed to move from B to A, but not from A to B. The example of the airplane is presented further and illustrates this possibility.
The notion of distance is introduced between two spots. For that, each link has a moving coefficient. An object using a link will move using a time corresponding to its reference moving time multiplied by the moving coefficient of the link. Usually, the reference moving time of a dynamic object represents the time to move along a unit of distance, i.e. its speed, and the moving coefficient of the link represents the distance between two spots. The moving time of a dynamic object is a random variable, whereas the moving coefficient of a link is a real number. Finally, a link belongs to a group. For that, it has an attribute, as the dynamic objects, that is a number and represents a group. The rule associated is that a dynamic object can only use the links belonging to its group. That allows moving different kinds of object through the same spots but using different ways.
A link can be associated with one or more SPAuthorization components. Such components have two statuses: "accepted" or "refused". A link can be used by a component only if all the authorizations associated with it are accepted. This comes from the lights at a road intersection. Vehicles stop when the light is red, i.e. the authorization is refused, and move when the light is green, i.e. the authorization is accepted. The user of the library will have to define the rules of acceptation and refusal of an authorization.
A link represents physically or logically a way between two spots. But it can appear that two links intersect as shown by Figure 41. In this case, the notion of interference is introduced. An interference regroups the links that can not be used at the same time. In our example, when a dynamic object uses the link 1, the link 2 is unusable, so an interference object will be created to associate these two links and forbid their mutual use. The priority of the dynamic objects is also considered with the interference. In our example, if we imagine a dynamic object in the source spot of the link 1 and another one in the source spot of the link 2. The object that will move is the one that has the highest priority.
The supervisor component is used to supervise the movement of dynamic objects in a graph. In fact, spots can be ordered to indicate to a supervisor about the objects arriving in it or leaving it. By this way, it is possible to collect data for further analysis, or simply detect a particular event. For instance, the user might want to stop the simulation after the arrival of a given number of dynamic objects in a particular component. Another example is the case of the airplane. It seems interesting to detect when all the passengers are seated. So, all the seats are ordered to inform a common supervisor when a passenger arrives to its seat.
Figure 44 presents the collaboration diagram in the case of a dynamic object DynObj1 arriving to a move spot Spot1. We suppose the spot is shallow. The case of a deep spot is not presented here. The messages exchanged are a bit different but the logic stills the same. The following messages are exchanged between the components. First the simulator informs the move spot and the dynamic object of the arrival.
When a dynamic object arrives at a SPComponent spot, the object is not placed directly in the list of the objects allowed to move to their next destination. They are placed in a list of waiting objects. Then, they undergo an operation, and after that, they are allowed to move to their next destination. Of course, this behavior must be completely defined by the user. Let us see what happens when a dynamic object arrives (see Figure 45). First the simulator informs the dynamic object and the spot of the arrival.
Figure 46 represents what happens when a dynamic object leaves a spot. First, the simulator informs the dynamic object and the spot of the departure.
When a spot is ordered to attract an object, it has to choose the dynamic object with the highest priority that wants to move to it. The method called to attract an object is attractObjectWithFirstCandidate:. The calling object can specify a privileged candidate to attract, i.e. if no dynamic object with a higher priority is found, it is this one that will move. When receiving the message, the attracting spot exchanges the following messages to each spot susceptible of having an object that wants to move to the considered attracting spot.
This previous sequence of messages is performed for each spot that can have an interesting dynamic object. Finally, the attracting spot will have the choice between dynamic objects of several spots with the same priority. Randomly, but uniformly, a dynamic object is chosen among them. Then, this dynamic object is moved (message 6).
Figure 48 presents the case when a link is ordered to move an object through the method moveObject:. But the problem is that some links can interfere, which means some dynamic objects in other spots can have a better priority than the dynamic object chosen to move. Before moving the object, the link must be sure that no dynamic object in the spots associated with some interfering link has a higher priority. Starting from the message moveObject:, the following messages are exchanged.
We present briefly the algorithm used to determine the shortest path a dynamic object can use to move from a spot to another. In fact, the library uses often this algorithm, so it needs to be as fast as possible. In fact, every time the method defineNextDestination of a dynamic object is called, this algorithm is run at least one time.
A classical algorithm has been adapted. First of all, the graph of spots used is constructed at the beginning of the simulation and never changes. During a search, spots are marked, but at each new search the spots need to be unmarked. That supposes a process to unmark each spot of the graph. That can take some time. The first adaptation is to add an attribute to each spot, a mark. It is a reference to an object of the class SPMark. This class has no particularity. The aim is to mark the spot with a new object at each new search. At the beginning of the search, a new object is created and its reference is used to mark the spots. In other word, if a spot has a mark reference different from the current mark, the spot is not marked.
Moreover, with VSE, the memory used by the objects is freed by a garbage collector, meaning that an object stills in the memory until nobody references it. So, the mark of a previous search stills in the memory until no spot references it. That means a same mark will be reused only if no spot uses the mark at the beginning of a search. Hence, there will be no conflict and the mark we have defined is surely unique.
Then, to avoid the use of lists, that are extremely time consuming with VSE, another attribute is added to each spot. It is an object of the class SPPathElement. This object contains the following information.
During the search, this information is updated. Hence, only one list is managed, a list of unexplored spots, but it is used as a queue, which is not very time consuming. At the end of the search, we just need to consider the destination spot and follow the path in the inverse direction through the path elements.
The principle of the algorithm is that knowing, for a given spot, its distance to the start point, it is possible to determine the distance to the start of each spot adjacent, supposing an arrival from the current spot considered. If this distance is better than the best distance known so far for the adjacent spot, the path element of the adjacent spot is updated. If the adjacent spot is unmarked, it is also put in a list of unexplored spots. The algorithm loops until this list is empty. At each iteration, a spot is removed from this list, marked and the process explained previously is performed. The first spot considered is the start spot given for the search.
Algorithm A.1 of annex A presents the method with the VSE language. The parameters the user must give are the start spot, the destination spot, and the group number of the dynamic object that will use the path, and also its moving direction. Finally, it is possible to find a path considering the current state of the graph, meaning considering that some spots or links are unusable.
This model represents the inside of an airplane as shown by Figure 49 and Figure 50. The purpose of this model is to simulate the movement of passengers in an airplane during the boarding, when the passengers enter the airplane and move to their seat, and during the landing, when the passengers leave their seat to go to the exit of the airplane. The spot library has been used to build the model and we will see now what has been added to the library to obtain the model.
When looking at the class hierarchy diagram (see Figure 51), we note that there is only four new classes. The purpose of three of them is obvious: Airplane, Passenger and Seat. They are induced by the nature of the system to model. But the class AirplaneSupervisor is not a natural approach and is due to the nature of the spot library.
The dynamic objects moving in the airplane are the passengers, so they must inherit from SPDynamicObject, but no particular behavior or attribute is added. This class is defined only for the clarity of the model. The seats are the destinations of the passengers, so they need to belong to the class SPSpot, and more precisely, they belong to the class SPComponent, because passengers need to wait when they arrive at their seat.
Then, the class Airplane is defined to represent the top-level component of the model and generate the passengers that will enter into the airplane. Finally, the model will simulate cyclically a boarding then a landing, so the detection of the following events must be done.
For this detection, a SPSupervisor object is needed. To use it, there is no choice but specializes it, because no behavior is defined when the supervisor receives messages from the spots. The supervisor will receive messages from the seats and from the exit spot of the airplane. Respectively, the passengers arriving to their seat and the passengers leaving the airplane are counted. When the number reaches the total number of passengers, respectively a landing or a boarding is ordered.
To start a boarding, 36 passengers are created and each one is assigned randomly to a seat, i.e. its FinalDestination attribute is set to this seat. The moving direction of the passengers is the normal direction. Then, each one of them is entered in the graph through the entrance spot. As expected, each passenger moves automatically to its seat. To start a landing, the moving direction of each passenger is set to the inverse direction. Then, the exit spot of the airplane is assigned as the final destination of each passenger. Finally, the move spots near the seats are ordered to attract an object. As expected, the passengers left their seat in a random order and use the links of the graph in their inverse direction until the exit spot of the airplane.
The purpose of this model is to simulate the movement of vehicles in the town of Blacksburg. Figure 52 and Figure 53 show two intersections. The first shows an intersection with stops and the other one shows an intersection with lights. The objects symbolized by a manufacture will generate vehicles that will move in the street, respecting priorities and lights. This model uses the spot library. Only few classes have been added.
As the airplane model, only four classes have been created (see Figure 54). Two of them seem completely natural: Light and Vehicle. The Light class inherits from the SPAuthorization class. In fact, a light is naturally an authorization or a refusal. In this model, the light is an object that just changes its status cyclically, from "accepted" to "refused", corresponding respectively to a green or red light. A Vehicle class has been created, only for the clarity of the model. It inherits from the SPDynamicObject class to be able to use the spot library.
Then, two classes less obvious have been developed. One to represent the top-level component of the model, i.e. the town of Blacksburg, and the other one to simulate the arrival of vehicles in the model. The VehicleGenerator class represents objects that will create continuously vehicles using a random variable for the inter-arrival time.
As shown by Figure 55, SPInterference objects are used to represent the intersection of several ways. SPChangePriority objects are also used for the stop intersection. A vehicle has a final destination, but the way it will use to move to this destination is not always known. A priori, we do not know which vehicle will have the priority upon another one. Hence, the idea with the SPChangePrioritySpot components is to put some spots of this kind on the road having the highest priority, just before the intersection and just after. The first ones will increase the priority of the vehicles passing on them and the other ones will surrender their normal priority to the vehicles. By this way, the vehicles having the lower priority will let the other vehicles pass. In our model, SPChangePriority objects are also put in the way of the lower priority vehicles to decrease their priority. It is not necessary, but it avoids controlling the default priority level at the vehicle generators. In Figure 52, the SPChangePrioritySpot objects are the darker move spots.
During the simulation, vehicles are regularly created and assigned randomly to a final destination, an exit spot representing the end of a street. Then, the vehicles enter the graph of spots. As expected, vehicles move to their final destination, respecting the lights and the spots. Finally, we can see that there is no visual collision of the vehicles.
This library provides a full set of components and classes that allows expressing a lot of various rules for the movement of dynamic objects in a layout. The user does not need a lot of time to model the movement of dynamic objects and can concentrate on other parts of the model. We never see any case where the objects still blocked, but there is no way to affirm that blocking never occurs. Finally, the main drawback of this library is the number of messages it generates and by this way, the number of times, the time consuming search of a shortest path is done. However, we think it is possible to ameliorate the whole mechanism, which is the reason of such a detailed presentation.
Usually, the time in a simulator, called simulation clock, is represented by a real number. Although it is sufficient for a lot of problems if not all, it can sometimes be interesting to manipulate the time in a calendar as we usually use to. The purpose of this library is to provide a representation of the simulation clock in the Gregorian calendar. There are two aspects in this library. The first is the class and its set of methods that allows the manipulation of dates in the Gregorian calendar. The other aspect is a mechanism to use the simulation clock as a date and time in this calendar. There are also components that allow displaying the simulation clock in the calendar. In the following of this section, we use the term "calendar" to designate a date and a time in the Gregorian calendar.
To present this library, we first introduce the components that allow the display of the simulation clock in the Gregorian calendar. We also present the formats available for the display. Then, we present the class GPCalendar that provides a set of methods to manipulate dates and the algorithms used in them. The reason for such a detailed presentation is that the class we have developed here can be easily translated in another language and we think it can be useful. Finally, we present the techniques used to test this library to convince ourselves of the correctness of the algorithms. The names of the classes and the types defined in this library begin with the letters GP, because this library will be integrated in the general-purpose library of VSE, a standard library that is provided with VSE.
As shown by Figure 56, the clock library provides four main kinds of component to display the time of the simulation in the Gregorian calendar. For each kind, a component without any image and one with a box picture are proposed. The user can change the font and the text and background colors of the component. He can also change easily the image of the clock. Hence, the user can customize the clock as he wants to integrate it in the layout of a component.
This component displays the date of the simulation clock. There are two formats provided, corresponding to the two main ways used to represent a date (see Figure 57).
This component displays only the time of the simulation clock. There are also two formats provided (see Figure 57).
Figure 58 presents the correspondence between an hour expressed in the military format and an hour expressed in the American format. Finally, the GTTime component allows the display or not of the second.
This component is similar to the previous one. It just allows also the display of the weekday of the simulation clock. For that, there are two formats (see Figure 57).
Every combination of the weekday format and the time format is possible.
This component regroups the characteristics of the GPDate and the GPDayAndTime components. It allows the display of the full information on the simulation clock in the Gregorian Calendar with any combination of the formats presented previously (see Figure 57). It offers also the possibility of displaying the information in one or two lines (see Figure 56).
All the clock components described previously belong to the class GPClockComponent. So it has been specialized with GPClock, GPDate, GPDayAndTime and GPTime, corresponding directly to the components of the palette. The GPClockComponent superclass can receive the message refresh. When an instance of this class receives the message, it refreshes its display. The four subclasses override this refresh method to perform their specific display.
The user will put clock components anywhere he wants in the component hierarchy of the model, and set the parameters of the simulation clock and the refreshing of the clock components. Then, the simulation starts (message 1).
The calendar used actually in America and Europe is the Gregorian calendar. The following presents an interesting brief historic on the birth of the Gregorian calendar, extracted from [Macey 94]. It also presents the rules adopted by the calendar that we must consider in the design of the clock library. Information about this calendar and some others is available at [Hermetic Web].
The oldest calendrical system whose details and uses are known is that of pre-Egypt. It was a calendar of 365 days, divided into twelve months of thirty days and five extra days.
(...) The Egyptians divided the time from sunrise to sunset, and from sunset to sunrise into twelve equal hours, making the length of the hours dependent on the time of the year and on the geographical latitudes. (...) The Sumerians, having realized the impracticality of unequal hours for astronomical purposes, divided the whole day into twelve equal hours. We have inherited the twenty-four-hour division from the Egyptians, and the equal hours from the Sumerians.
(...) In 48 BC, Julius Caesar recommended that the new calendar follows the old Egyptian one, but with the year lengthened to 365 1/4 days and the months arranged with respect to the solar year. Their lengths alternated between thirty-one and thirty days except for February, which had twenty-eight days. The Julian year thus became 365 days long, with an intercalary day inserted in February every four years. July, named after Julius Caesar, had thirty-one days, whereas August, named after Augustus Caesar, had only thirty days. Possibly because he regarded this as a slight, Augustus ordered his month increased to thirty-one days. To avoid three thirty-one-day months in a row, the lengths of the rest of the months were rearranged (...).
(...) Although work on the new calendar began soon after the Council of Trent, it was not until 1572, the first year of the reign of Pope Gregory XIII, that the reform was completed and the calendar promulgated. It was immediately adopted by Catholic but not by Protestant lands and towns. From 1582 until the mid-eighteenth century, Europe remained a kaleidoscope of calendars (...).
(...) The Gregorian year is 365.2425 mean solar days. To ensure this length, the leap year was manipulated: no centennial year is a leap year unless it is divisible by 400. This adjustment makes the Gregorian system gain on astronomical year no more than one day in 3,560 years, if second order corrections and unpredictable changes in the rate of the earth's rotation are neglected.
An instance of this class is an object that represents a date and a time in the Gregorian calendar. As we said before, we call such an object a calendar even if the term is not exactly adapted.
We briefly present here the methods provided in order to have an overview of the possibilities offered by the class. To have more details, it is advised to look at the dictionary in annex B containing a more detailed description of the methods and attributes of this library.
First, the class provides methods to convert the number of a month in a string of characters and vice-versa. The same thing is done for the weekdays. Here are the class methods allowing that.
When a calendar instance is created with VSE by the method new of the GPCalendar class, the object must be initialized by the standard method initialize. However, the GPCalendar provides other methods to initialize a calendar, calling also the method initialize. These methods are those beginning with initialize (see Figure 60). Some of them initialize a calendar from another one, by adding or not a number of time units. Others initialize a calendar from a string of characters representing a calendar, and some others by giving the full description of the calendar (for instance: year, month, day of month, hour, minute and second). A similar set of methods is provided to set a calendar, but without calling the method initialize, the calendar being already initialized. The names of these methods begin with set (see Figure 60).
There are also some methods to compare two calendars.
There are methods to advance or regress the time of a calendar. The names of these methods begin respectively by addNumberOf or subtractNumberOf. Finally, as there are methods to set a calendar from a string of characters, there are also methods to convert a calendar into a string of characters. The formats offered by the GPCalendar class are the same as the formats used for the clock components described previously. Here are the methods to convert a calendar into a string of characters.
Finally, there are methods to access different information about a calendar.
To be able to manipulate dates in the Gregorian calendar, some information is needed like the number of days in each month, according to the fact that the year considered is leap or not. We represents that with a matrix named MonthLengths initialized as following.
As presented previously, a leap year has 366 days, one more than a normal year and this day is added in the second month, February. To access an element of the matrix, two indexes must be specified: the kind of year and the number of the month, e.g. MonthLengths(LeapYear, 2) is 29.
Then, to be efficient in the manipulation of dates in the Gregorian calendar, we need another matrix called numberOfDaysSince1stJanuary. An element of this matrix represents, for a particular month and a given kind of year, the number of days between the 1st January and the 1st day of the month. The following shows the content of the matrix.
Algorithm A.2 of annex A shows how to build this matrix with the VSE language.
An easy way to manipulate a date is to represent it as an integer number, for instance the number of seconds since the 1/1/1 at 00:00:00. Unfortunately, to use such a representation, we need a computer that can represent large integers.
For instance, if we consider the date 7/1/1998 at 00:00:00. It is the day number 729,571 since the 1/1/1. In term of seconds, it is the second number:
which needs 34 bits in term of computer representation. That means, we need a technology based on a representation of the integer with at least 64 bits to be able to manipulate actual dates. Unfortunately, VSE represents integer numbers with 32 bits, and only signed numbers. That means VSE can represent integers between -2,147,483,649 and 2,147,483,648. Hence, the solution we adopted is to represent the date with two integer numbers: one to represent the day since the 1/1/1 and one to represent the second in the day. So, a couple (day ; second) can represent a calendar. Here are some examples.
Our problem in this paragraph is to find out if a year is leap or not. If we refer to the presentation of the Gregorian calendar, it appears that every four years, there is a leap year. The only precision we must say is that the first leap year since the 1/1/1 is the year 4. That means if the number of a year is a multiple of 4, this year is leap, unless, as presented previously, this year is a multiple of 100, but not a multiple of 400. We can formalize the solution of the question by:
Previously, we defined the couple (day ; second) as the representation of a calendar. We call the day of this couple the "absolute day number" of the calendar. We present here how to find the absolute day number of a calendar. We propose the following algorithm.
The symbol // represents the integer division operator, i.e. the result of this operator is only the integer part of the quotient of the division considered. The IsLeap() function determinates if the year is leap or not. The idea here is to consider the previous year of the calendar. Then, for each year from the year 1, 365 days are added. Then, for each previous year multiple of 4, a day is added. But for each previous year multiple of 100, the day added is then subtracted. And for each previous year multiple of 400, the day added, then subtracted is finally added again. Then, the number of days from the 1st January to the 1st of the month is added, due to the matrix NumberOfDaysSince1stJanuary and finally, the day in the month of the calendar is added. The result is the absolute day number of the calendar. Algorithm A.4 of annex A shows this method with the VSE language.
Previously, we defined the couple (day ; second) as the representation of a calendar. We call the second of this couple the "absolute second number" of the calendar. We present here how to find the absolute second number of a calendar. We propose the following formula.
Algorithm A.5 of annex A shows this method with the VSE language.
We present first how to obtain the year, the month, the day of year and the day of month of a calendar from its representation by a couple (day ; second). We propose the following algorithm to determine the year and the day of year of the calendar.
The function FloorIntegerPart conserves only the integer part of the real number given as argument. The idea of the algorithm is that the mean length of a year is about 365.2425.
Every 400 years, this mean is exactly the given number, but between them, there is a little difference, the mean is either upper or lower. So, the division of the absolute day number of a calendar by 365.2425 will give the number of passed years with a little error of precision.
We suppose that the error can not be more than one year.
We do not propose here a rigorous mathematical proof of that, but just an intuitive explanation that should convince anyone of the rightness of the assumption above. With our estimation, we consider the length of a year always equal to 365.2425 days. So, the year Y + 1 begins the day 365.2425 x Y with our representation. In the reality, the year Y + 1 as been preceded by cycles of 400 years, that means we can consider:
So, the year Y + 1 begins the day 365.2425 x 400 x Y1 + M x Y2, where M is the mean of the length of a year since the last 400 years cycle. We can give to M the following boundaries.
Because a year has at least 365 days, and less than every 4 years, a year is leap. Now, we are able to give a boundary for the real number of days in a 400 cycle.
We can now compare our approximate representation with the real one.
More clearly, -97 400 x M - 400 x 365.2425 3. That means our approximation of considering a year to have always a length of 365.2425 induces an error between 3 and 97 days. It is less than one year. So, with our approximation, we will make a confusion only between two following years. Our assumption (*) seems to be confirmed by these explanations.
Hence, the algorithm finds a first approximation of the number of passed years. Based on that, the number of the day in the year is determined. For that, the number of days of each passed year is subtracted from the absolute day number of the calendar. If the result is a valid number of days in the year, that means the approximation is right. So, the year of the calendar is the number of passed years plus 1 and the number of the day in the year is the one found.
There is two cases of invalid number of days in the year. The first is when the number is less that 1. In this case, the estimation is upper than the real value. So, the estimated year is decreased and the number of the day in the year is determined again. This time the values found are right. In a same way, if the number of the day is more than 365, there may be an error. The estimation may be lower than the real value. To be sure, the number of the day is determined in the case the estimation is increased of one year. If the number of days found is positive, the estimation was wrong, so the new values found are the right one, else the estimation was right so the old values are conserved.
Now, we explain how to find the month and the day of the month based on the results obtained by the previous algorithm. For that, we propose the following algorithm.
The first thing is to determine if the year is leap or not. Then, an approximation of the number of the month is found by dividing the day of the year by 32. By this way, the approximation is always lower or equal to the real value, with a precision of one month.
To prove it, we just have to verify that it works for the 365 days of a normal year and for the 366 days of a leap one. That means, for each day, to look if the month given by the formula DayOfYear // 32 + 1 is the right month or the one just before. But we propose also here an intuitive explanation for that. We consider that months have a constant length of 32 days. With this consideration, a simple division of the number of a day in the year will give us the month the day belongs to. We obviously introduce an error. However, the month found will always be equal or less than the right month because 32 is superior to the real length of every month of a year. The error is only of one month because the difference between the real lengths of the months and the representation with 32 days is only one day for January, 32 - 31, 4 days for February, (32 + 32) - (31 + 28), and progressively it increases until December, where the difference is 18 days. Like the approximation of the years explained previously, this is less than a month. So, the confusion made with our approximation will be only between two following months. Our assumption (**) seems to be confirmed by these explanations.
Based on this approximation, the day of the month is determined. If the day of the month is more that the number of days in the estimated month (found in the MonthLengths matrix), that means the estimation was wrong and the estimation must be increased of one month to be correct. If the estimation was wrong, the day of the month is determined again based on the new value of the month.
Finally, we present how to find the hour, the minute and the second of a calendar from the absolute second number. There is no particular difficulty because unlike the year and the month, the length of an hour or a minute is always the same. Here is the algorithm.
Algorithm A.6 of annex A shows the calculation presented in this subsection with the VSE language.
In this paragraph, we present how to find the weekday of a calendar, using its absolute day number. The numbering of the weekdays has the following signification.
We present now the formula used to find directly the weekday of a calendar.
The idea of this formula is that the modulo 7 of the absolute day number of a calendar is enough to find its weekday. For instance, if we consider the date 8/22/1998, which is a Saturday with the absolute day number 729623. Its modulo 7 is equal to 6. That means every calendar with an absolute day number modulo 7 equal to 6 is a Saturday. Then, the days with a modulo 7 equal to 0 are a Sunday and so on until Friday with a modulo 7 equal to 5. Our formula is just a way to obtain directly the weekday between 1 and 7, with the number symbolizing the weekdays as defined previously. In our formula, we consider the absolute day number of a calendar minus 1 (in order to start from 0). Then, we add to it the weekday number of the 1/1/1 day (named FirstWeekday) minus 1 (also in order to start from 0). Of course, we did not know the weekday of the day 1/1/1. To find it, we executed this algorithm with a calendar we known the weekday. We changed FirstWeekDay until the algorithm gave us the right result for the weekday of the chosen calendar. Algorithm A.6 of annex A shows this method with the VSE language.
The library offers the possibility of adding a given number of units to a calendar. We present here an algorithm to perform that. There is no real difficulty with it, but we must just be careful to avoid an overflow due to the limitation to 32 bits of the integer numbers representation. The following algorithm assures that there will be no overflow.
This algorithm adds the number NumberOfUnits of units to the calendar represented by the couple (DayNumber ; SecondNumber). We need to know, for each unit, the number of units in a day, UnitsPerDay, and the number of seconds in a unit, SecondsPerUnit.
The number of full days to add is determined by dividing the total number of units by the number of units in a day. Only the integer part of the division is considered. The fraction part remaining is converted to a number of seconds and added to the absolute second number of the calendar. The absolute day number of the calendar is incremented by the number of full days determined previously plus the integer part of the division of the number of seconds by 86,400, in the case there are more than 86,400 seconds. For the same reason, the number of seconds is finally modulated by 86,400. Algorithm A.7 of annex A shows this algorithm with the VSE language.
The library offers the possibility of subtracting a given number of units from a calendar. We present here an algorithm to perform that. As for the addition, there is no real difficulty with it, but we must just be careful to avoid the overflow due to the limitation to 32 bits of the integer numbers. The following algorithm assures that there will be no overflow.
This algorithm subtracts the number NumberOfUnits of units from the calendar represented by the couple (DayNumber ; SecondNumber). We need to know, for each unit, the number of units in a day, UnitsPerDay, and the number of seconds in a unit, SecondsPerUnit. The function CeilingIntegerPart returns the smallest integer superior or equal to the real number given as argument.
The number of full days to subtract is determined by dividing the total number of units by the number of units in a day. The integer just superior or equal to the quotient is considered. The fraction part corresponding to the difference between the quotient and this integer is converted to a number of seconds and added to the absolute second number of the calendar. The absolute day number of the calendar is decremented by the number of days determined previously plus the integer part of the division of the number of seconds by 86,400, in the case there are more than 86,400 seconds. For the same reason, the number of seconds is finally modulated by 86,400.
This library will be used as a standard library of VSE. That means users will use it supposing of the correctness of the performed algorithms. To reinforce our confidence in this library, we made different kinds of verification. We first use assertions in the logic of the methods developed in order to detect improper use of the methods. Then, we perform manually set of tests for each method to verify its behavior in particular cases like a leap year, the passing from a day to another, from a month to another...
Then, to verify the usual behavior of the library and sometimes some particular cases, we performed automatic testing. That means we define scenarios of use of some methods of the library and then, we establish assertions about the result. A program will generate randomly data for the scenarios and will verify the assertions.
For instance, we can consider the complementary methods addNumberOfSeconds: and subtractNumberOfSeconds: of the GPCalendar class. If we use the first one to add a given number of seconds to a calendar and then, if we subtract this same number of seconds from the calculated calendar, we should find the start calendar of the scenario. Hence, for the clock library, we have tried to imply all the methods of the GPCalendar class in such a testing and moreover, we have tried to imply them at least in two scenarios with different methods.
We performed also a comparison testing. We use the standard time library of the
C language. This library represents a calendar by a number of seconds with the type time_t
(see [Kernighan 88]). This number is the number of seconds passed since the 1/1/1970
at 00:00:00. Then, the function
Different Verification, Validation and Testing (VV&T) techniques have been used to assess of the credibility of this library. Moreover, we designed a class, GPCalendar, that we think is really easily portable and fast enough. We also think that the class is complete enough to provide the main services we can expect when manipulating dates. Finally, the clock components provided by the palette of the library and the mechanism of refreshing associated offers an extremely easy way to introduce the calendar in the model.