6. DESIGN OF LIBRARIES
OF REUSABLE COMPONENTS
 
 
INTRODUCTION
 

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.

 
FORMALISM
 

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.

 
Class Hierarchy Diagram
 

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 33: Formalism of the Inheritance Relationship.

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.

Figure 34: Formalism of a Class.

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.

Figure 35: Formalism of Some Specific Attributes and Methods.

 
 
Component Hierarchy Diagram
 

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 36: Formalism of an Object.

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.

Figure 37: Formalism of a Component Hierarchy Diagram.

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 Diagram
 

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: Formalism of a Collaboration Diagram.

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.

 
THE SPOT LIBRARY
 
 
Introduction
 

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.

 
Palette
 

Figure 39: Palette of the Spot Library.

 
 
The SPDynamicObject Component

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.

 
Graph of Spots

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.

 
The SPSpot Component

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.

 
The SPMoveSpot Component

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.

  • SPChangePrioritySpot, that is a move spot where the priority level of a dynamic object is changed to a another one. The aim of this component comes from the road intersection problem with the case of a stop. Placed at the right places, spots of this kind will increase the priority of the vehicles arriving from the road with priority.

  • SPEntranceSpot, that is a move spot through which a dynamic object enters into a graph of spots.

  • SPExitSpot, that is a move spot through which a dynamic object leaves a graph of spots. It is associated with a shape. A dynamic object arriving at an exit spot moves automatically to the associated shape outside the graph.

 
The SPComponent Component

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.

 
The SPLink 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.

Figure 40: Unidirectional and Bidirectional Links.

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.

 
The SPAuthorization Component

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.

 
The SPInterference Component

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.

Figure 41: Intersection of Links.

 
 
The SPSupervisor Component

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.

 
Class Hierarchy
 

Figure 42: Class Hierarchy of the Spot Library - Part I.

 

Figure 43: Class Hierarchy of the Spot Library - Part II.

 
 
Collaboration Diagrams
 
 
Arrival of a SPDynamicObject at a SPMoveSpot

Figure 44: Spot Library - Collaboration Diagram 1.

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.

  • 1. Simulator  [DynObj1 movedToComponent: Spot1]
    The simulator automatically sends this message to the dynamic object when it arrives at the move spot. The dynamic object just updates its attributes.

  • 2. Simulator  [Spot1 dynObjArrived: DynObj1]
    The simulator automatically sends this message when a dynamic object arrives at the move spot. The spot informs its supervisors that a dynamic object has arrived (message 3), adds the dynamic object to the list of the objects allowed to move to their next destination (message 4) and tells the link that its activity is ended (message 8).

  • 3. Spot1  [Supervisor1 object: DynObj1 arrivedAtSpot: Spot1]
    The spot informs all its supervisors of the arrival of the dynamic object. In this example, there is only one supervisor.

  • 4. Spot1  [Spot1 declareMovableObject: DynObj1]
    The dynamic object is added to the list of the objects allowed to move to their next destination. Immediately, the spot tries to move the object to its next destination (message 5), because a move spot is just a point the dynamic objects passes through. The less time they stay in a move spot, the better.

  • 5. Spot1  [Spot1 tryToMoveObject: DynObj1]
    The spot tries to move the object to its next destination. For that, the dynamic object must first of all determine its next destination (message 6). Then, the destination spot defined is ordered to attract an object with the privileged candidate DynObj1 (message 7). If no dynamic object with a higher priority wants to move to the same spot, DynObj1 will move to the spot, else the logic of the tryToMoveObject: method is reiterated, i.e. the dynamic object chooses again its next destination and so on.

  • 6. Spot1  [DynObj1 defineNextDestination]
    The dynamic object finds its best next destination. For that, the shortest path between the dynamic object and its final destination is found. If the next spot in this path is available, the dynamic object chooses this spot as next destination. Else, if it is not available, the dynamic object looks at each next spot it can reach. If one of the next spots is its final destination, it waits for the destination to be available, else it selects the available spot that is the nearest to the final destination, but avoids the ones that have the current spot in their shortest path to the final destination. That avoids a dynamic object to move cyclically between two spots.

  • 7. Spot1  [Spot3 attractObjectWithFirstCandidate: DynObj1]
    The spot tries to attract an object. For that, it chooses a dynamic object with the highest priority that can come from the adjacent spots. This method is detailed further in another collaboration diagram about the attraction of an object, because it induces a lot of messages to the neighbor spots.

  • 8. Spot1  [Link1 endActivity]
    When the dynamic object arrives at the spot, the link it has used must be freed. For that, the message endActivity is sent to the used link. The link becomes available and it orders its source and destination spots to attract an object, because the fact the link was used may has blocked a dynamic object in one of these spots. In the same way, the spots of the links implied in an interference with this link are asked to attract also an object, because an object can still be blocked.

  • 9. Link1  [Spot2 attractObjectWithFirstCandidate: nil]
    Spot2 is ordered to attract an object without any privileged candidate.

  • 10. Link1  [Spot1 attractObjectWithFirstCandidate: nil]

 
Arrival of a SPDynamicObject at a SPComponent

Figure 45: Spot Library - Collaboration Diagram 2.

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.

  • 1. Simulator  [DynObj1 movedToComponent: Spot1]
    Exactly the same things happen as for the move spot. The simulator automatically sends this message to the dynamic object when it arrives at the move spot.

  • 2. Simulator  [Spot1 dynObjArrived: DynObj1]
    It is similar to the case of the move spot. The simulator automatically sends this message when a dynamic object arrives at the move spot. The spot informs its supervisors that a dynamic object has arrived. But in this case there is no supervisor. Then, it adds the dynamic object to the list of the objects waiting for undergoing an operation (message 3), which is the difference with a move spot. Finally, it tells the used link that its activity is ended (it is not represented here because it is exactly the same as the case of the move spot).

  • 3. Spot1  [Spot1 declareWaitingObject: DynObj1]
    The dynamic object is added to the list of the waiting objects for undergoing an operation.

  • 4. Object1  [Spot1 removeWaitingObject: DynObj1]
    The dynamic object DynObj1 will undergo an operation, expressed somewhere in the model. After the operation, the Spot1 receives the order of remove the object DynObj1 from the list of the waiting objects.

  • 5. Object1  [Spot1 declareWaitingObject: DynObj1]
    The dynamic object is now placed in the list of the objects allowed to move to their next destination. Exactly the same process as for the move spot is performed, i.e. the Spot1 is ordered to try to move the object (message 6).

  • 6. Spot1  [Spot1 tryToMoveObject: DynObj1]
    This method is not detailed and corresponds exactly to the previous case of the move spot.

 
Departure of a SPDynamicObject From a SPSpot

Figure 46: Spot Library - Collaboration Diagram 3.

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.

  • 1. Simulator  [DynObj1 departedFromComponent: Spot1]
    This method is called when the dynamic object has left the spot. It updates the attributes of the dynamic object, and tells the left spot to remove the object from the list of the objects allowed to move to their next destination (message 2).

  • 2. DynObj1  [Spot1 removeMovableObject: DynObj1]

  • 3. Simulator  [Spot1 dynObjDeparted: DynObj1]
    The simulator automatically calls this method when a dynamic object has left the spot. The spot decreases the number of dynamic objects in it (message 4), informs its supervisors of the departure (message 5), and then tries to attract another object (message 6).

  • 4. Spot1  [Spot1 decreaseNumberOfObjects]
    An object has left the spot, so the number of objects must be decreased.

  • 5. Spot1  [Supervisor1 object: DynObj1 departedFromSpot: Spot1]
    The supervisor is informed of the departure of the dynamic object from the spot.

  • 6. Spot1  [Spot1 attractObjectWithFirstCandidate: nil]
    Spot1 is ordered to attract an object without any privileged candidate.

 
Attraction of a SPDynamicObject

Figure 47: Spot Library - Collaboration Diagram 4.

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.

  • 1. Spot1  [Spot2 whoCanMoveTo: Spot1]
    For each adjacent spot, the attracting spot asks which dynamic object in the adjacent spot has the highest priority and wants to move to the attracting spot. So, the adjacent spot looks each dynamic object it possesses and asks the dynamic object its next destination (message 2) and its priority. If the next destination of the object is not Spot1, the spot destination of the object is ordered to attract an object (message 3) with the dynamic object as privileged candidate.

  • 2. Spot2  [DynObj1 defineNextDestination]
    The dynamic object DynObj1 selects its next destination. See the previous collaboration diagrams for more explanations.

  • 3. Spot2  [Spot3 attractObjectWithFirstCandidate: DynObj1]
    The next destination of the dynamic object DynObj1 is not the attracting spot, so the next destination spot is asked to attract a dynamic object, because the dynamic object considered can have been blocked by the attracting spot, and now it wants to move to another spot.

  • 4. Spot2  [DynObj2 defineNextDestination]
    The next destination of DynObj2 is the attracting spot, so this object can be a candidate.

  • 5. Spot2  [DynObj3 defineNextDestination]
    The next destination of DynObj3 is the attracting spot, but DynObj2 has a higher priority so the best candidate is DynObj2.

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).

  • 6. Spot1  [Link1 moveObject: DynObj2]
    When a dynamic object defines its next destination by the defineNextDestination method, it also defines which link it must use. Hence, when a spot chooses a dynamic object to move, it knows which link to use to move the object. This is detailed in the next collaboration diagram.

 
Movement of a SPDynamicObject Through a SPLink

Figure 48: Spot Library - Collaboration Diagram 5.

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.

  • 1. Spot2  [Link1 moveObject: DynObj1]
    For each couple of spots associated with an interfering link, the message whoCanComeTo: (messages 2 and 3) is sent. As explained previously, this message can induce an attraction by another spot and makes a lot of changes in the graph. So when the messages 2 or 3 return their answer, Link1 must verify that DynObj1 did not move, that its destination stills available and that itself, the link, stills usable.

    In the case of a positive verification, the messages 2 and 3 can return a better candidate DynObj2 than DynObj1. In this case, the destination of this new candidate, Spot1 for instance, is asked to attract an object with the privileged candidate DynObj2 (message 4). Lots of changes can occur then as explained in the previous collaboration diagrams. So after this message 4, the same verifications as after the messages 2 and 3 must be performed.

    In the case of a failure of the verification, a message will be sent to the spot where DynObj1 is located, in order to try to move the object (message 5). The destination of DynObj1 is also ordered to attract another object because maybe another object can come to it instead of DynObj1 (message 6).

    If, after all the candidates tested and moved, DynObj1 stills in Spot1, if Spot2 and Link1 stills available, Link1 will reserve a place in the destination spot (message 7), reserve the link (message 8) and move DynObj1 (message 9).

  • 2. Link1  [Spot3 whoCanMoveTo: Spot1]

  • 3. Link1  [Spot1 whoCanMoveTo: Spot3]

  • 4. Link1  [Spot1 attractObjectWithFirstCandidate: DynObj2]

  • 5. Link1  [Spot1 tryToMoveObject: DynObj1]

  • 6. Link1  [Spot2 attractObjectWithFirstCandidate: nil]

  • 7. Link1  [Spot2 increaseNumberOfObjects]
    This method increases the number of objects in the spot. When this number reaches the capacity of the spot, the boolean number objectCanCome is set to false, meaning that no other object can come to the spot.

  • 8. Link1  [Link1 startActivity]
    The link is reserved. No other dynamic object can use it. By the same way, the interfering links can not be used, because before using them, it will be tested if one of the interfering links, especially Link1, is used.

  • 9. Link1  [DynObj1 moveTo: Spot2 takingTime: t]
    The dynamic object is finally moved to its next destination. The time needed to move is determined as following. The attribute movingTime is a random variable and represents the reference moving time (the speed) of the dynamic object. So a realization of it is taken and multiplied by the moving coefficient (the length) of the link.

 
Search of a Shortest Path in a Graph of Spots
 

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.

  • The shortest distance found so far to the start spot.

  • The path element of the spot used to access the current spot by the shortest path found so far.

  • The link used to access the current spot by the shortest path found so far.

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.

 
Airplane Model
 

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.

Figure 49: Inside of an Airplane.

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.

Figure 50: Component Hierarchy of the Airplane Model.

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.

Figure 51: Class Hierarchy of the Airplane Model.

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.

  • All the passengers are seated.

  • All the passengers have left the airplane.

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.

 
Road Traffic Model
 

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.

Figure 52: Stop Intersection.

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.

Figure 53: Light Intersection.

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.

Figure 54: Class Hierarchy of the Road Traffic Model.

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.

Figure 55: Component Hierarchy of the Road Traffic Model.

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.

 
Conclusion
 

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.

 
THE CLOCK LIBRARY
 
 
 
Introduction
 

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.

 
The Clock Components
 
 
Introduction

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.

Figure 56: Palette of the Clock Library.

 

Figure 57: Class Hierarchy of the Clock Library - Part I.

 
 
The GPDate 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).

  • The "day first" format: 24 September 1998.

  • The "month first" format: September 24, 1998.

 
The GPTime Component

This component displays only the time of the simulation clock. There are also two formats provided (see Figure 57).

  • The "American" format: 10:00:00 PM. The hour is expressed between 1 to 12. To represent the first twelve hours, the letters AM (Ante Meridiem) are added, and for the last twelve ones, the letters PM (Post Meridiem) are used.

  • The "military" format: 22:00:00. The hour is expressed between 0 and 23.

Figure 58: Correspondence Between Military and American Time Formats.

Military Format American Format
0 12 AM
1 1 AM
... ...
11 11 AM
12 12 PM
13 1 PM
... ...
23 11 PM

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.

 
The GPDayAndTime Component

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).

  • The "long name" format: Wednesday.

  • The "short name" format: Wed..

Every combination of the weekday format and the time format is possible.

 
The GPClock Component

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).

 
The Clocks Refreshing Mechanism
 

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.

Figure 59: Clocks Refreshing Mechanism.

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).

  • 1. Simulator  [GPClocksManager replicationStarted]
    A replication starts. The message replicationStarted is sent to all the classes (message 1) and to all the objects (messages 10, 12, 14 and 16). The class GPClocksManager first finds the top-level component by asking the model of the simulation (message 2). Then, the parameters of the simulation clock and the clock components refreshing are consulted through the top-level (see Figure 57) and are stored in the GPClocksManager.

    The parameters are first defined by the user in the top-level component, and then in the GPClocksManager. The reason for such a copy is that the user can manually, visually initialize the attributes with the inspector tool of VSE, but only for an object and not for a class. The best solution would be to consider the parameters as input data of the model. By this way, it would be possible to initialize them visually in the window of the input data of VSE. However, the actual version of VSE does not allow defining input data in a library.

    After the recuperation of the parameters, the manager creates an instance of its class. This object will be used to represent the cyclic refreshing of the clock components. In fact, the object will engage a first time in an activity (message 9). At the end of the activity (message 18), the object will order the GPClocksManager class to refresh the clocks, and will reengage itself in an activity for a period corresponding to the period of the refreshing, and so on, until the end of the simulation.

  • 2. GPClocksManager  [VSEModel topLevelComponent]
    The VSEModel object represents the simulation model. Here, it returns a reference to the top-level component of the model. The GPClocksManager will use it to get the parameters.

  • 3. GPClocksManager  [TopLevel startDateAndTime]
    This parameter the class gets is a string representing the calendar when the simulation starts. In other words, the time 0.00 corresponds to this calendar.

  • 4. GPClocksManager  [TopLevel endDateAndTime]
    This parameter the class gets is a string representing the calendar when the simulation ends. The GPClocksManager schedules the message endReplication for the VSEModel object for this date. It will stop the simulation at this date.

  • 5. GPClocksManager  [TopLevel clockUnit]
    This parameter the class gets indicates the unit in which the simulation clock is considered. For instance, if the clock unit is the minute, the current time of the simulation 3.00 and the start calendar is the 1/1/1998 at 00:00:00, that means the current calendar is 1/1/1998 at 00:03:00.

  • 6. GPClocksManager  [TopLevel clocksRefreshingPeriod]
    This parameter the class gets is the period with which the clock components are refreshed.

  • 7. GPClocksManager  [TopLevel automaticClocksRefreshing]
    This parameter the class gets indicates if the refreshing of the clock components is automatic, based on the refreshing period. In fact, the user can choose to use one of the events he generates in the logic of his model to send a refreshClocks message to the GPClocksManager class. It should be less time consuming.

  • 8. GPClocksManager  [GPClocksManager new]
    As explained previously, the class creates an object to represent the cyclic refreshing of the clock components.

  • 9. GPClocksManager  
      [ClocksManager engageInActivity: x forTime: 0.00]

    The class generates the first refreshing of the clocks.

  • 10. Simulator  [Clock1 replicationStarted]
    This message is automatically sent at the start of a replication. It generates the message 11.

  • 11. Clock1  [GPClocksManager registerClockComponent: Clock1]
    The component registers itself to the GPClocksManager class. By this way, the class will automatically refresh it.

  • 12. Simulator  [Date1 replicationStarted]
    This message is automatically sent at the start of a replication. It generates the message 13.

  • 13. Date1  [GPClocksManager registerClockComponent: Date1]
    The component registers itself to the GPClocksManager class. By this way, the class will automatically refresh it.

  • 14. Simulator  [DateAndTime1 replicationStarted]
    This message is automatically sent at the start of a replication. It generates the message 15.

  • 15. DateAndTime1 
       [GPClocksManager registerClockComponent: DateAndTime1]

    The component registers itself to the GPClocksManager class. By this way, the class will automatically refresh it.

  • 16. Simulator  [Time1 replicationStarted]
    This message is automatically sent at the start of a replication. It generates the message 17.

  • 17. Time1  [GPClocksManager registerClockComponent: Time1]
    The component registers itself to the GPClocksManager class. By this way, the class will automatically refresh it.

  • 18. Simulator  [ClocksManager stoppedEngagement: x]
    At the end of its activity, the ClocksManager component receives this message. That means the clocks must be refreshed. It orders the GPClocksManager to do that (message 19). Then, the component engages itself again in an activity (message 25).

  • 19. ClocksManager  [GPClocksManager refreshClocks]
    The class looks if the model is actually animated (message 20). If the animation is deactivated, no message is performed. Else, each component registered is ordered to refresh its display (message 21 to 24).

  • 20. GPClocksManager  [VSEModel isBeingAnimated]
    Indicates if the animation is activated in the simulator.

  • 21. GPClocksManager  [Clock1 refresh]

  • 22. GPClocksManager  [Date1 refresh]

  • 23. GPClocksManager  [DayAndTime1 refresh]

  • 24. GPClocksManager  [Time1 refresh]

  • 25. ClocksManager  [ClocksManager engageInActivity: x
                        forTime: clocksRefreshingPeriod]

    The GPClocksManager starts a new activity, waiting for the next refreshing of the clock components.

 
The GPCalendar Class
 
 
Introduction to the Gregorian Calendar

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.

 
Presentation of the GPCalendar Class

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.

Figure 60: Class Hierarchy of the Clock Library - Part II.

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.

  • MonthNameFromNumber:

  • MonthNumberFromName:

  • WeekDayLongNameFromNumber:

  • WeekDayNumberFromLongName:

  • WeekDayNumberFromShortName:

  • WeekDayShortNameFromNumber:

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.

  • CompareTo:

  • IsAfter:

  • IsAfterOrEqualTo:

  • IsBefore

  • IsBeforeOrEqualTo:

  • IsEqualTo:

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.

  • DateInFormat:

  • DateInFormat:timeInFormat:withSecond:

  • DateInFormat:weekDayInFormat:timeInFormat:withSecond:

  • TimeInFormat:withSecond:

  • WeekDayInFormat:timeInFormat:withSecond:

Finally, there are methods to access different information about a calendar.

  • Year: number of the year (1 to +oo ), the year 1 represents the first year after Christ.

  • Month: number of the month in the year (1 = January to 12 = December).

  • DayOfYear: number of the day in the year (1 to 366).

  • DayOfMonth: number of the day in the month (1 to 31).

  • DayOfWeek: number of the day in the week (1 = Sunday to 7 = Saturday).

  • Hour: number of the hour in the day (0 to 23).

  • Minute: number of the minute in the hour (0 to 59).

  • Second: number of the second in the minute (0 to 59).

  • LeapYear: indicates if the year is leap.

  • DayNumber: number of the day since 1/1/1 (1 to +oo).

  • SecondNumber: number of the second in the day (0 to 86,399).

 
Preparation to the Manipulation of the Gregorian 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.

MonthLengths(NormalYear) =
{31,28,31,30,31,30,31,31,30,31,30,31}

MonthLengths(LeapYear) =
{31,29,31,30,31,30,31,31,30,31,30,31}

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.

NumberOfDaysSince1stJanuary(NormalYear) =
{0,31,59,90,120,151,181,212,243,273,304,334}

NumberOfDaysSince1stJanuary(LeapYear) =
{0,31,60,91,121,152,182,213,244,274,305,335}

Algorithm A.2 of annex A shows how to build this matrix with the VSE language.

 
Representation of a Calendar

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:

729,571 x 86,400 = 63,034,934,400

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.

  • 1/1/1 at 00:00:00 is represented by (1 ; 0).

  • 1/2/1 at 00:05:00 is represented by (2 ; 300).

  • 2/1/1 at 01:00:00 is represented by (32 ; 3,600).

 
Determination of the Kind of Year of a Calendar

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:

If Year % 400 = 0 Then Answer  True
Else If Year % 4 = 0 And Not Year % 100 = 0 Then
 Answer  True
Else Answer  False

The symbol % represents the modulo operator and the symbol    represents the affectation operator. Algorithm A.3 of annex A shows this method with the VSE language.

 
Determination of the Absolute Day Number of a Calendar

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.

PreviousYear  Year - 1

If IsLeap(Year) Then YearKind  LeapYear
Else YearKind  NormalYear

DayNumber  DayOfMonth
             + NumberOfDaysSince1stJanuary(YearKind,Month)
             + 365 x PreviousYear + PreviousYear // 4
             - PreviousYear // 100 + Year // 400

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.

 
Determination of the Absolute Second Number of a Calendar

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.

SecondNumber  (Hour x 60 + Minute) x 60 + Second

Algorithm A.5 of annex A shows this method with the VSE language.

 
Determination of the Calendar Represented by a Couple (day ; second)

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.

Year  FloorIntegerPart(DayNumber / 365.2425)

DayOfYear  DayNumber - (365 x Year + Year // 4
             - Year // 100 + Year // 400)

If DayOfYear > 365 Then
 Year  Year + 1

 Tempo  DayNumber - (365 x Year + Year // 4
          - Year // 100 + Year // 400)

 If Tempo > 0 Then
  DayOfYear  Tempo
  Year  Year + 1
 End If
Else
 If DayOfYear < 1 Then
  Year  Year - 1

  DayOfYear  DayNumber - (365 x Year + Year // 4
               - Year // 100 + Year // 400)
 End If

 Year  Year + 1
End If

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.

365.2425 = 365 + 1 / 4 - 1 / 100 + 1 / 400

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.

-1  Estimation - Real Value  1 (*)

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:

Y = 400 x Y1 + Y2, with Y1  0 and 0  Y2  400

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.

365  M  365.25

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.

400 x 365  400 x M  400 x 365.25

We can now compare our approximate representation with the real one.

(400 x M - 400 x 365.2425)  (400 x 365 - 400 x 365.2425)
(400 x M - 400 x 365.2425)  (400 x 365.25 - 400 x 365.2425)

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.

If IsLeap(Year) Then YearKind  LeapYear
Else YearKind  NormalYear

Month  DayOfYear // 32 + 1

DayOfMonth  DayOfYear -
              NumberOfDaysSince1stJanuary(YearKind,Month)

If DayOfMonth > MonthLengths(YearKind,Month) Then
 DayOfMonth  DayOfMonth - MonthLengths(YearKind,Month)
 Month  Month + 1
End If

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.

 Real Value - Estimation  1 (**)

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.

Hour  SecondNumber / 3600
SecondNumber  SecondNumber % 3600
Minute  SecondNumber / 60
Second  SecondNumber % 60

Algorithm A.6 of annex A shows the calculation presented in this subsection with the VSE language.

 
Determination of the Weekday of a Calendar

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.

1 = Sunday, 2 = Monday ... 7 = Saturday

We present now the formula used to find directly the weekday of a calendar.

Weekday  ((DayNumber - 1) + (FirstWeekday - 1)) % 7 + 1

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.

 
Addition of n Days, Hours, Minute or Seconds to a Calendar

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.

Days  FloorIntegerPart(NumberOfUnits / UnitsPerDay)

Seconds  SecondNumber + FloorIntegerPart ((NumberOfUnits
           - Days x UnitsPerDay) x SecondsPerUnit)

DayNumber  DayNumber + Days + Seconds // 86400
SecondNumber  SecondNumber % 86400

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.

Unit UnitsPerDay SecondsPerUnit
Day 1 86,400
Hour 24 3,600
Minute 1,440 60
Second 86,400 1

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.

 
Subtraction of n Days, Hours, Minute or Seconds From a Calendar

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.

Days  CeilingIntegerPart(NumberOfUnits / UnitsPerDay)

Seconds  SecondNumber + CeilingIntegerPart ((Days x UnitsPerDay
           - NumberOfUnits) x SecondsPerUnit)

DayNumber  DayNumber - Days + Seconds // 86400
SecondNumber  SecondNumber % 86400

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.

 
Testing
 

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 gmtime() returns, for a number of seconds, a data structure representing the calendar. This structure contains the same kind of data as the GPCalendar class, such as the year, the month, the day in the month... So, we wrote a program in the C language, with the Borland C++ 3.1 application, that generates randomly a set of numbers of seconds and uses the function gmtime() to obtain information about the calendar. This second number and the information of the associated calendar are stored in a file. Then, in VSE, a program reads this file and initializes, for each number of seconds, a calendar with the method initializeWithNumberOfSeconds: since:, meaning it initializes a calendar by adding the number of seconds to a reference calendar corresponding to 1/1/1970 at 00:00:00. Then, information of the calendar is compared with those stored in the file.

 
Conclusion
 

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.

 
 
Copyright (c) 1999-2016 - Bruno Bachelet - bruno@nawouak.net - http://www.nawouak.net
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation. See this license for more details (http://www.gnu.org).