 |
ANNEX A: ALGORITHMS |
| A.1. SEARCH OF A SHORTEST PATH IN A GRAPH OF SPOTS |
The following listing is the instance method computeShortestPathOfGroup: from: to: withDirection: inMode: of the SPSpot class of the spot library.
returns
VSList reference
parameters
integer
groupNumber;
// Number of the group of links in which the path
//
is searched.
SPSpot reference sourceSpot;
// Start of the path.
SPSpot reference destinationSpot; //
End of the path.
SPMovingDirectionType movingDirection; // Indicates if the research
must be done using
//
the normal stream or the inverse stream.
SPShortestPathModeType mode;
// Mode in which the
shortest path is searched.
declarations
VSList reference unexploredElements;
// List of some unexplored elements of the
//
graph.
VSList reference shortestPath;
// List of elements representing the shortest
//
path between the source spot and the
//
destination spot.
SPPathElement reference currentElement; // Current
analyzed element.
SPSpot reference currentSpot;
// Current analyzed spot.
SPLink reference currentLink;
// Current analyzed link.
real
currentDistance;
// Distance from the given start of the
//
current analyzed spot.
VSIterator reference iteratorLinks;
// Iterator for the lists of links.
VSIterator reference iteratorSpots;
// Iterator for the lists of spots.
SPPathElement reference destinationElement; // Element representing the
final destination
//
spot.
SPMark reference mark;
// Mark
for this search.
logic
// Assertions.
assert not (destinationSpot is nil)
with message "[Spot - computeShortestPathOfGroup:from:to:withDirection:inMode:]
The final
destination can't be 'nil'.\n";
assert not (sourceSpot is nil)
with message "[Spot - computeShortestPathOfGroup:from:to:withDirection:inMode:]
The source
spot can't be 'nil'.\n";
// Preparation.
set destinationElement to nil;
set unexploredElements to [[VSList new] initialize];
set mark to [[SPMark new] initialize];
tell sourceSpot that markIs: mark;
set currentElement to [pathElement of sourceSpot];
tell currentElement that spotIs: sourceSpot;
tell currentElement that distanceFromStartIs: 0.00;
tell currentElement that accessLinkIs: nil;
tell currentElement that previousElementIs: nil;
// Searching of the shortest path.
tell unexploredElements to addObject: currentElement;
repeat while [count of unexploredElements] > 0 do
{
set currentElement to [firstObject of unexploredElements];
// The analyzed element represents the final destination spot.
if [spot of currentElement] is destinationSpot then
set destinationElement to currentElement;
// The analyzed element represents any other spot.
else
{
// Determination of the lists of the next spots.
if movingDirection is SPNormalDirection then
{
set iteratorLinks to [outgoingLinksOfGroup:
groupNumber of [spot of currentElement]];
set iteratorSpots to [nextSpotsOfGroup: groupNumber
of [spot of currentElement]];
}
else
{
set iteratorLinks to [incomingLinksOfGroup:
groupNumber of [spot of currentElement]];
set iteratorSpots to [previousSpotsOfGroup:
groupNumber of [spot of currentElement]];
}
// Assertions.
assert (iteratorLinks is nil and iteratorSpots is nil)
or not (iteratorLinks is nil or iteratorSpots is nil)
with message "[Spot -
computeShortestPathOfGroup:from:to:withDirection:inMode:] Problem
with the graph.\n";
// There could be next spots.
if not (iteratorLinks is nil) then
{
// For each next move spot.
repeat while [iteratorLinks hasMoreObjects] do
{
set currentLink to [nextObject of
iteratorLinks];
set currentSpot to [nextObject of
iteratorSpots];
set currentDistance to
([distanceFromStart of currentElement]
+ [movingCoefficient of currentLink]);
// The spot is accessible.
if (mode is SPWithoutConstraints)
or ((mode is SPWithConstraints) and
[currentLink isUsable]
and [currentSpot objectCanCome]) then
{
// The current spot is
already marked.
if [mark of currentSpot] is
mark then
{
if
[distanceFromStart of [pathElement of currentSpot]] > currentDistance then
{
tell
[pathElement of currentSpot] that accessLinkIs: currentLink;
tell
[pathElement of currentSpot] that previousElementIs: currentElement;
tell
[pathElement of currentSpot] that distanceFromStartIs: currentDistance;
}
}
// The current spot is not
already marked.
else
{
tell
currentSpot that markIs: mark;
tell
[pathElement of currentSpot] that spotIs: currentSpot;
tell
[pathElement of currentSpot] that accessLinkIs: currentLink;
tell
[pathElement of currentSpot] that previousElementIs: currentElement;
tell
[pathElement of currentSpot] that distanceFromStartIs: currentDistance;
tell
unexploredElements to addObject: [pathElement of currentSpot];
}
}
}
}
}
// The current element becomes an explored element.
tell unexploredElements to removeFirstObject;
}
// No path exists to access to the final destination.
if destinationElement is nil then
return nil;
// Assembling of the elements to build the shortest path.
set shortestPath to [[VSList new] initialize];
set currentElement to destinationElement;
repeat while not ([spot of currentElement] is sourceSpot) do
{
tell shortestPath to insertObject: currentElement atIndex: 1;
set currentElement to [previousElement of currentElement];
}
// Return of the found path.
return shortestPath;
| A.2. PREPARATION TO THE MANIPULATION OF A GREGORIAN CALENDAR |
The following listing is the class method prepare of the GPCalendar class of the clock library.
returns
nothing
parameters
none
declarations
integer currentMonth;
// Current month treated.
VSList reference normalYearMonthLengths; // List of the lengths of
each month for
//
a normal year.
VSList reference leapYearMonthLengths; // List of the
lengths of each month for a leap
//
year.
VSList reference normalYearNumbersOfDays; // List of the numbers of days
between the 1st
//
January and the 1st day of each month for a
//
normal year.
VSList reference leapYearNumbersOfDays; // List of the numbers
of days between the 1st
//
January and the 1st day of each month for a
//
leap year.
integer normalYearSumDays;
// Sum of the number of days between the 1st
//
January and the 1st day of the current month
//
for a normal year.
integer leapYearSumDays;
// Sum of the number of days between the 1st
//
January and the 1st day of the current month
//
for a leap year.
logic
// If the initialization has not already been performed.
if normalYearMonthLengths is nil then
{
// Initialization of the list of the month lengths for a normal year.
set normalYearMonthLengths to [[VSList new] initialize];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 28];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 30];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 30];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 30];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 30];
tell normalYearMonthLengths to addObject: [VSValue integerValue: 31];
// Initialization of the list of the month lengths for a leap year.
set leapYearMonthLengths to [[VSList new] initialize];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 29];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 30];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 30];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 30];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 30];
tell leapYearMonthLengths to addObject: [VSValue integerValue: 31];
// Memorization of the previous lists.
set monthLengths to [[VSList new] initialize];
tell monthLengths to addObject: normalYearMonthLengths;
tell monthLengths to addObject: leapYearMonthLengths;
// Preparation of the tables for the conversion of time.
// Each table contains, for each month, the sum of the
// number of days of the previous months.
// This represents the number of days between the 1st
// January of the year and the 1st day of the month.
set normalYearNumbersOfDays to [[VSList new] initialize];
set leapYearNumbersOfDays to [[VSList new] initialize];
set normalYearSumDays to 0;
set leapYearSumDays to 0;
set currentMonth to GPJanuary;
repeat while currentMonth <= GPDecember do
{
tell normalYearNumbersOfDays to addObject: [VSValue
integerValue: normalYearSumDays];
tell leapYearNumbersOfDays to addObject: [VSValue integerValue:
leapYearSumDays];
add [[objectAtIndex: currentMonth of normalYearMonthLengths]
asInteger] to
normalYearSumDays;
add [[objectAtIndex: currentMonth of leapYearMonthLengths]
asInteger] to
leapYearSumDays;
add 1 to currentMonth;
}
// Memorization of the tables.
set numbersOfDaysSince1stJanuary to [[VSList new] initialize];
tell numbersOfDaysSince1stJanuary to addObject: normalYearNumbersOfDays;
tell numbersOfDaysSince1stJanuary to addObject: leapYearNumbersOfDays;
// Creation of the list of names for the months.
set monthNames to [[VSList new] initialize];
tell monthNames to addObject: GPJanuaryString;
tell monthNames to addObject: GPFebruaryString;
tell monthNames to addObject: GPMarchString;
tell monthNames to addObject: GPAprilString;
tell monthNames to addObject: GPMayString;
tell monthNames to addObject: GPJuneString;
tell monthNames to addObject: GPJulyString;
tell monthNames to addObject: GPAugustString;
tell monthNames to addObject: GPSeptemberString;
tell monthNames to addObject: GPOctoberString;
tell monthNames to addObject: GPNovemberString;
tell monthNames to addObject: GPDecemberString;
// Creation of the list of short names for the days of the week.
set weekDayShortNames to [[VSList new] initialize];
tell weekDayShortNames to addObject: GPSundayShortString;
tell weekDayShortNames to addObject: GPMondayShortString;
tell weekDayShortNames to addObject: GPTuesdayShortString;
tell weekDayShortNames to addObject: GPWednesdayShortString;
tell weekDayShortNames to addObject: GPThursdayShortString;
tell weekDayShortNames to addObject: GPFridayShortString;
tell weekDayShortNames to addObject: GPSaturdayShortString;
// Creation of the list of long names for the days of the week.
set weekDayLongNames to [[VSList new] initialize];
tell weekDayLongNames to addObject: GPSundayLongString;
tell weekDayLongNames to addObject: GPMondayLongString;
tell weekDayLongNames to addObject: GPTuesdayLongString;
tell weekDayLongNames to addObject: GPWednesdayLongString;
tell weekDayLongNames to addObject: GPThursdayLongString;
tell weekDayLongNames to addObject: GPFridayLongString;
tell weekDayLongNames to addObject: GPSaturdayLongString;
}
| A.3. DETERMINATION OF THE KIND OF YEAR OF A CALENDAR |
The following listing is the instance method leapYear of the GPCalendar class of the clock library.
returns
boolean
parameters
none
declarations
none
logic
return ((year mod 4 is 0) and not (year mod 100 is 0)) or (year mod 400 is 0);
| A.4. DETERMINATION OF THE ABSOLUTE DAY NUMBER OF A CALENDAR |
The following listing is the instance method dayNumber of the GPCalendar class of the clock library.
returns
integer
parameters
none
declarations
integer previousYear;
//
The year before the current date.
VSList reference numbersOfDaysSinceBeginningYear; // List of the numbers of
days between
//
the 1st January and the 1st of the
//
current month.
logic
// Determination of the table to use for the conversion according to the fact that the
year
// is leap or not.
if [leapYear] then
set numbersOfDaysSinceBeginningYear to
[objectAtIndex: GPLeapYear of numbersOfDaysSince1stJanuary];
else
set numbersOfDaysSinceBeginningYear to
[objectAtIndex: GPNormalYear of numbersOfDaysSince1stJanuary];
// Computing of the day number. 1 represents the 1st January of year 1, so the day
number is
// between 1 and +oo.
set previousYear to (year - 1);
return (dayOfMonth + [[objectAtIndex: month of numbersOfDaysSinceBeginningYear]
asInteger]
+ 365 * previousYear + previousYear / 4 - previousYear / 100 + previousYear /
400);
| A.5. DETERMINATION OF THE ABSOLUTE SECOND NUMBER OF A CALENDAR |
The following listing is the instance method secondNumber of the GPCalendar class of the clock library.
returns
integer
parameters
none
declarations
none
logic
// Computing of the second number. It is the number of the second in a day.
// 0 represents the second 00:00:00 of the day.
// So the second number is between 0 and 24 * 60 * 60 - 1 = 86399.
return ((hour * 60 + minute) * 60 + second));
| A.6. DETERMINATION OF THE CALENDAR AND THE WEEKDAY OF A COUPLE (DAY ; SECOND) |
The following listing is the instance method setWithDayNumber: secondNumber: of the GPCalendar class of the clock library.
returns
nothing
parameters
integer dayNumber; // Day number representing the date.
integer secondNumber; // Second number representing the date.
declarations
VSList reference numbersOfDaysSinceBeginningYear; // List of the numbers of
days between
//
the 1st January and the 1st day of
//
each month.
VSList reference numbersOfDaysInMonth;
// List of the numbers of
days in each
//
month.
integer tempo;
//
Intermediate variable for the
//
conversion.
logic
// Assertions.
assert dayNumber > 0 with message "Invalid day number.";
assert secondNumber >= 0 and secondNumber < 86400 with message "Invalid
day number.";
// Approximates the year minus 1.
set year to RealToTruncatedInt(dayNumber / 365.2425);
// Determines the number of the day in the year according to the approximation.
set dayOfYear to (dayNumber - (365 * year + year / 4 - year / 100 + year / 400));
// The approximation could be wrong.
if dayOfYear >= 366 then
{
// Determines the number of days between the 1st January
// of the next year and the day number.
add 1 to year;
set tempo to (dayNumber - (365 * year + year / 4 - year / 100 + year /
400));
// The approximation is wrong.
if tempo > 0 then
{
set dayOfYear to tempo;
add 1 to year;
}
}
else
{
// The approximation is wrong, upper than the right value.
if dayOfYear <= 0 then
{
subtract 1 from year;
set dayOfYear to (dayNumber - (365 * year + year / 4 - year /
100 + year / 400));
}
// Determines the year of the calendar.
add 1 to year;
}
// Determination of the table to use for the conversion
// according to the fact that the year is leap or not.
if [leapYear] then
{
set numbersOfDaysSinceBeginningYear to
[objectAtIndex: GPLeapYear of numbersOfDaysSince1stJanuary];
set numbersOfDaysInMonth to [objectAtIndex: GPLeapYear of monthLengths];
}
else
{
set numbersOfDaysSinceBeginningYear to
[objectAtIndex: GPNormalYear of numbersOfDaysSince1stJanuary];
set numbersOfDaysInMonth to [objectAtIndex: GPNormalYear of monthLengths];
}
// Approximates the month.
set month to dayOfYear / 32 + 1;
// Determines the number of the day in the approximated month.
set dayOfMonth to
(dayOfYear - [[objectAtIndex: month of numbersOfDaysSinceBeginningYear] asInteger]);
// The approximation is wrong.
if dayOfMonth > [[objectAtIndex: month of numbersOfDaysInMonth] asInteger] then
{
subtract [[objectAtIndex: month of numbersOfDaysInMonth] asInteger] from
dayOfMonth;
add 1 to month;
}
// Determines the number of the day in the week.
set dayOfWeek to ([dayNumber] + GPFirstWeekDay - 2) mod 7 + 1;
// Determines the hour, the minute and the second.
set hour to (secondNumber / 3600);
modulate secondNumber by 3600;
set minute to (secondNumber / 60);
set second to (secondNumber mod 60);
| A.7. ADDITION OF N HOURS TO A CALENDAR |
The following listing is the instance method addNumberOfHours: of the GPCalendar class of the clock library.
returns
nothing
parameters
real numberOfHours; // Number of hours to increment to the current
calendar.
declarations
integer days; // Intermediate value representing a number
of days.
integer seconds; // Intermediate value representing a number of seconds.
logic
set days to RealToTruncatedInt(numberOfHours / 24);
set seconds to ([secondNumber] + RealToTruncatedInt((numberOfHours - days * 24) *
3600));
tell self to setWithDayNumber: ([dayNumber] + days + seconds / 86400)
secondNumber: (seconds mod 86400);
| A.8. SUBTRACTION OF N HOURS FROM A CALENDAR |
The following listing is the instance method subtractNumberOfHours: of the GPCalendar class of the clock library.
returns
nothing
parameters
real numberOfHours; // Number of hours to decrement to the current
calendar.
declarations
integer days; // Intermediate value representing a number
of days.
integer seconds; // Intermediate value representing a number of seconds.
logic
set days to RealToCeilInt(numberOfHours / 24);
set seconds to ([secondNumber] + RealToCeilInt((days * 24 - numberOfHours) * 3600));
tell self to setWithDayNumber: ([dayNumber] - days + seconds / 86400)
secondNumber: (seconds mod 86400);
|