TraDemGen Logo  1.00.0
C++ Simulated Travel Demand Generation Library
 All Classes Namespaces Files Functions Variables Typedefs Friends Pages
DemandStream.cpp
Go to the documentation of this file.
1 // //////////////////////////////////////////////////////////////////////
2 // Import section
3 // //////////////////////////////////////////////////////////////////////
4 // STL
5 #include <cassert>
6 #include <sstream>
7 #include <cmath>
8 #include <iomanip>
9 // Boost
10 #include <boost/make_shared.hpp>
11 // StdAir
12 #include <stdair/basic/BasConst_General.hpp>
13 #include <stdair/basic/BasConst_Inventory.hpp>
14 #include <stdair/basic/BasConst_Request.hpp>
15 #include <stdair/bom/BookingRequestStruct.hpp>
16 #include <stdair/service/Logger.hpp>
17 // TraDemGen
20 
21 namespace TRADEMGEN {
22 
23  // ////////////////////////////////////////////////////////////////////
24  DemandStream::DemandStream()
25  : _key (stdair::DEFAULT_ORIGIN, stdair::DEFAULT_DESTINATION,
26  stdair::DEFAULT_DEPARTURE_DATE, stdair::DEFAULT_CABIN_CODE),
27  _parent (NULL),
28  _demandCharacteristics (ArrivalPatternCumulativeDistribution_T(),
34  0.5, 50, 0.5, 50,
36  0.0,
38  _posProMass (DEFAULT_POS_PROBALILITY_MASS),
39  _firstDateTimeRequest (true) {
40  assert (false);
41  }
42 
43  // ////////////////////////////////////////////////////////////////////
44  DemandStream::DemandStream (const DemandStream&)
45  : _key (stdair::DEFAULT_ORIGIN, stdair::DEFAULT_DESTINATION,
46  stdair::DEFAULT_DEPARTURE_DATE, stdair::DEFAULT_CABIN_CODE),
47  _parent (NULL),
48  _demandCharacteristics (ArrivalPatternCumulativeDistribution_T(),
54  0.5, 50, 0.5, 50,
56  0.0,
58  _posProMass (DEFAULT_POS_PROBALILITY_MASS),
59  _firstDateTimeRequest (true) {
60  assert (false);
61  }
62 
63  // ////////////////////////////////////////////////////////////////////
64  DemandStream::DemandStream (const Key_T& iKey) :
65  _key (iKey) {
66  }
67 
68  // ////////////////////////////////////////////////////////////////////
70  }
71 
72  // ////////////////////////////////////////////////////////////////////
73  std::string DemandStream::toString() const {
74  std::ostringstream oStr;
75  oStr << _key.toString();
76  return oStr.str();
77  }
78 
79  // ////////////////////////////////////////////////////////////////////
80  void DemandStream::
82  const POSProbabilityMassFunction_T& iPOSProbMass,
83  const ChannelProbabilityMassFunction_T& iChannelProbMass,
84  const TripTypeProbabilityMassFunction_T& iTripTypeProbMass,
85  const StayDurationProbabilityMassFunction_T& iStayDurationProbMass,
86  const FrequentFlyerProbabilityMassFunction_T& iFrequentFlyerProbMass,
87  const stdair::ChangeFeesRatio_T& iChangeFeeProb,
88  const stdair::Disutility_T& iChangeFeeDisutility,
89  const stdair::NonRefundableRatio_T& iNonRefundableProb,
90  const stdair::Disutility_T& iNonRefundableDisutility,
91  const PreferredDepartureTimeContinuousDistribution_T& iPreferredDepartureTimeContinuousDistribution,
92  const stdair::WTP_T& iMinWTP,
93  const ValueOfTimeContinuousDistribution_T& iValueOfTimeContinuousDistribution,
94  const DemandDistribution& iDemandDistribution,
95  stdair::BaseGenerator_T& ioSharedGenerator,
96  const stdair::RandomSeed_T& iRequestDateTimeSeed,
97  const stdair::RandomSeed_T& iDemandCharacteristicsSeed,
98  const POSProbabilityMass_T& iDefaultPOSProbablityMass) {
99 
100  setDemandCharacteristics (iArrivalPattern, iPOSProbMass,
101  iChannelProbMass, iTripTypeProbMass,
102  iStayDurationProbMass, iFrequentFlyerProbMass,
103  iChangeFeeProb, iChangeFeeDisutility,
104  iNonRefundableProb, iNonRefundableDisutility,
105  iPreferredDepartureTimeContinuousDistribution,
106  iMinWTP, iValueOfTimeContinuousDistribution);
107 
108  setDemandDistribution (iDemandDistribution);
110  setRequestDateTimeRandomGeneratorSeed (iRequestDateTimeSeed);
111  setDemandCharacteristicsRandomGeneratorSeed (iDemandCharacteristicsSeed);
112  setPOSProbabilityMass (iDefaultPOSProbablityMass);
113 
114  //
115  init (ioSharedGenerator);
116  }
117 
118  // ////////////////////////////////////////////////////////////////////
119  std::string DemandStream::display() const {
120  std::ostringstream oStr;
121 
122  oStr << "Demand stream key: " << _key.toString() << std::endl;
123 
124  //
126 
127  //
128  oStr << _demandDistribution.describe() << " => "
129  << _totalNumberOfRequestsToBeGenerated << " to be generated"
130  << std::endl;
131 
132  //
133  oStr << "Random generation context: " << _randomGenerationContext
134  << std::endl;
135 
136  //
137  oStr << "Random generator for date-time: "
138  << _requestDateTimeRandomGenerator << std::endl;
139  oStr << "Random generator for demand characteristics: "
141 
142  //
143  oStr << _posProMass.displayProbabilityMass() << std::endl;
144 
145  return oStr.str();
146  }
147 
148  // ////////////////////////////////////////////////////////////////////
149  void DemandStream::init (stdair::BaseGenerator_T& ioSharedGenerator) {
150 
151  // Generate the number of requests
152  const stdair::RealNumber_T lMu = _demandDistribution._meanNumberOfRequests;
153  const stdair::RealNumber_T lSigma =
155 
156  stdair::NormalDistribution_T lDistrib (lMu, lSigma);
157  stdair::NormalGenerator_T lNormalGen (ioSharedGenerator, lDistrib);
158 
159  const stdair::RealNumber_T lRealNumberOfRequestsToBeGenerated =lNormalGen();
160 
161  const stdair::NbOfRequests_T lIntegerNumberOfRequestsToBeGenerated =
162  std::floor (lRealNumberOfRequestsToBeGenerated + 0.5);
163 
164  _totalNumberOfRequestsToBeGenerated = lIntegerNumberOfRequestsToBeGenerated;
165 
166  _stillHavingRequestsToBeGenerated = true;
167  _firstDateTimeRequest = true;
168  }
169 
170  // ////////////////////////////////////////////////////////////////////
171  const bool DemandStream::
172  stillHavingRequestsToBeGenerated (const stdair::DemandGenerationMethod& iDemandGenerationMethod) const {
173 
174  const stdair::DemandGenerationMethod::EN_DemandGenerationMethod& lENDemandGenerationMethod =
175  iDemandGenerationMethod.getMethod();
176  if (lENDemandGenerationMethod == stdair::DemandGenerationMethod::STA_ORD) {
177  bool hasStillHavingRequestsToBeGenerated = true;
178 
179  // Check whether enough requests have already been generated
180  const stdair::Count_T lNbOfRequestsGeneratedSoFar =
182 
183  const stdair::Count_T lRemainingNumberOfRequestsToBeGenerated =
184  _totalNumberOfRequestsToBeGenerated - lNbOfRequestsGeneratedSoFar;
185 
186  if (lRemainingNumberOfRequestsToBeGenerated <= 0) {
187  hasStillHavingRequestsToBeGenerated = false;
188  }
189 
190  return hasStillHavingRequestsToBeGenerated;
191  } else {
192  return _stillHavingRequestsToBeGenerated;
193  }
194  }
195 
196  // ////////////////////////////////////////////////////////////////////
198 
199  // Prepare arrival pattern.
200  const ContinuousFloatDuration_T& lArrivalPattern =
202 
203  const stdair::Time_T lHardcodedReferenceDepartureTime =
204  boost::posix_time::hours (8);
205 
206  // Prepare departure date time.
207  const stdair::DateTime_T lDepartureDateTime =
208  boost::posix_time::ptime (_key.getPreferredDepartureDate(),
209  lHardcodedReferenceDepartureTime);
210 
211  // If no request has been generated so far...
212  if (_firstDateTimeRequest) {
213  const stdair::Probability_T lProbabilityFirstRequest = 0;
214 
215  // Get the lower bound of the arrival pattern (correponding
216  // to a cumulative probability of 0).
217  _dateTimeLastRequest =
218  lArrivalPattern.getValue (lProbabilityFirstRequest);
219 
220  _firstDateTimeRequest = false;
221  }
222 
223  // Sanity check.
224  assert (_firstDateTimeRequest == false);
225 
226  // If the date time of the last request is equal to the lower bound of
227  // the last daily rate interval (default value is -1, meaning one day
228  // before departure), we stopped generating request by returning a
229  // request date time after departure date time.
230  if (_dateTimeLastRequest == DEFAULT_LAST_LOWER_BOUND_ARRIVAL_PATTERN) {
231  _stillHavingRequestsToBeGenerated = false;
232 
233  // Get a positive number of days.
234  const stdair::Duration_T lDifferenceBetweenDepartureAndThisLowerBound =
236 
237  // Calculate a request date-time after the departure date time to end
238  // the demand generation algorithm.
239  const stdair::DateTime_T oDateTimeThisRequest =
240  lDepartureDateTime + lDifferenceBetweenDepartureAndThisLowerBound;
241 
242  return oDateTimeThisRequest;
243  }
244 
245  // Get the upper bound of the current daily rate interval.
246  stdair::FloatDuration_T lUpperBound =
247  lArrivalPattern.getUpperBound (_dateTimeLastRequest);
248 
249  // Compute the daily rate demand.
250  double lDailyRate =lArrivalPattern.getDerivativeValue(_dateTimeLastRequest);
251  // Get the expected average number of requests.
252  const double lDemandMean = _demandDistribution._meanNumberOfRequests;
253  // Multiply the daily rate by the expected average number of requests.
254  lDailyRate *= lDemandMean;
255 
256  // Generate an exponential variable.
257  const stdair::FloatDuration_T lExponentialVariable =
258  _requestDateTimeRandomGenerator.generateExponential (lDailyRate);
259 
260  // Compute the new date time request.
261  const stdair::FloatDuration_T lDateTimeThisRequest =
262  _dateTimeLastRequest + lExponentialVariable;
263 
264  stdair::DateTime_T oDateTimeThisRequest;
265 
266  // Verify if this request is in the given daily rate interval.
267  if (lDateTimeThisRequest < lUpperBound) {
268 
269  // Conversion.
270  const stdair::Duration_T lDifferenceBetweenDepartureAndThisRequest =
271  convertFloatIntoDuration (lDateTimeThisRequest);
272 
273  // The request date-time is derived from departure date and arrival pattern.
274  oDateTimeThisRequest = lDepartureDateTime
275  + lDifferenceBetweenDepartureAndThisRequest;
276 
277  // Remember this date time request.
278  _dateTimeLastRequest = lDateTimeThisRequest;
279 
280  // Update the counter of requests generated so far.
282 
283  const double lRefDateTimeThisRequest = lDateTimeThisRequest + double(28800.001/86400.0);
284  STDAIR_LOG_NOTIFICATION (boost::gregorian::to_iso_string(_key.getPreferredDepartureDate()) << ";" << std::setprecision(10) << lRefDateTimeThisRequest);
285  } else {
286 
287  // The current request is not in the given daily rate interval.
288  // Change the daily rate.
289  _dateTimeLastRequest = lUpperBound;
290 
291  // Generate a date time request in the new daily rate interval.
292  oDateTimeThisRequest = generateTimeOfRequestPoissonProcess ();
293  }
294 
295  return oDateTimeThisRequest;
296  }
297 
298  // ////////////////////////////////////////////////////////////////////
300 
317  //
318  // Calculate the result of the formula above step by step.
319  //
320 
321  // 1) Get the number of requests generated so far.
322  // (equal to k - 1)
323  const stdair::Count_T& lNbOfRequestsGeneratedSoFar =
325 
326  // 2) Deduce the number of requests not generated yet.
327  // (equal to n - k + 1)
328  const stdair::Count_T lRemainingNumberOfRequestsToBeGenerated =
329  _totalNumberOfRequestsToBeGenerated - lNbOfRequestsGeneratedSoFar;
330 
331  // Assert that there are still requests to be generated.
332  assert (lRemainingNumberOfRequestsToBeGenerated > 0);
333 
334  // 3) Inverse the number of requests not generated yet.
335  // 1/(n - k + 1)
336  const double lRemainingRate =
337  1.0 / static_cast<double> (lRemainingNumberOfRequestsToBeGenerated);
338 
339  // 4) Get the cumulative probality so far and take its complement.
340  // (equal to 1 - x(k-1))
341  const stdair::Probability_T& lCumulativeProbabilitySoFar =
343  const stdair::Probability_T lComplementOfCumulativeProbabilitySoFar =
344  1.0 - lCumulativeProbabilitySoFar;
345 
346  // 5) Draw a random variable y and calculate the factor equal to
347  // (1 - y)^(1/(n - k + 1)).
348  const stdair::Probability_T& lVariate = _requestDateTimeRandomGenerator();
349  double lFactor = std::pow (1.0 - lVariate, lRemainingRate);
350  if (lFactor >= 1.0 - 1e-6){
351  lFactor = 1.0 - 1e-6;
352  }
353 
354  // 6) Apply the whole formula above to calculate the cumulative probability
355  // of the new request.
356  // (equal to 1 - (1 - x(k-1))(1 - y)^(1/(n - k + 1)))
357  const stdair::Probability_T lCumulativeProbabilityThisRequest =
358  1.0 - lComplementOfCumulativeProbabilitySoFar * lFactor;
359 
360  // Now that the cumulative proportion of events generated has been
361  // calculated, we deduce from the arrival pattern the arrival time of the
362  // k-th event.
363  const stdair::FloatDuration_T lNumberOfDaysBetweenDepartureAndThisRequest =
364  _demandCharacteristics._arrivalPattern.getValue (lCumulativeProbabilityThisRequest);
365 
366  const stdair::Duration_T lDifferenceBetweenDepartureAndThisRequest =
367  convertFloatIntoDuration (lNumberOfDaysBetweenDepartureAndThisRequest);
368 
369  const stdair::Time_T lHardcodedReferenceDepartureTime =
370  boost::posix_time::hours (8);
371 
372  const stdair::DateTime_T lDepartureDateTime =
373  boost::posix_time::ptime (_key.getPreferredDepartureDate(),
374  lHardcodedReferenceDepartureTime);
375 
376  // The request date-time is derived from departure date and arrival pattern.
377  const stdair::DateTime_T oDateTimeThisRequest =
378  lDepartureDateTime + lDifferenceBetweenDepartureAndThisRequest;
379 
380  // Update random generation context
381  _randomGenerationContext.setCumulativeProbabilitySoFar (lCumulativeProbabilityThisRequest);
382 
383  // Update the counter of requests generated so far.
385 
386  // DEBUG
387  // STDAIR_LOG_DEBUG (lCumulativeProbabilityThisRequest << "; "
388  // << lNumberOfDaysBetweenDepartureAndThisRequest);
389 
390  // NOTIFICATION
391  double lRefNumberOfDaysBetweenDepartureAndThisRequest =
392  lNumberOfDaysBetweenDepartureAndThisRequest + double(1.0/3.0);
393  STDAIR_LOG_NOTIFICATION (boost::gregorian::to_iso_string(_key.getPreferredDepartureDate()) << ";" << std::setprecision(10) << lRefNumberOfDaysBetweenDepartureAndThisRequest);
394 
395  return oDateTimeThisRequest;
396  }
397 
398  // ////////////////////////////////////////////////////////////////////
399 
400  const stdair::Duration_T DemandStream::
401  convertFloatIntoDuration (const stdair::FloatDuration_T iNumberOfDays) {
402 
403  // Convert the number of days in number of seconds + number of milliseconds
404  const stdair::FloatDuration_T lNumberOfSeconds =
405  iNumberOfDays * stdair::SECONDS_IN_ONE_DAY;
406 
407  // Get the number of seconds.
408  const stdair::IntDuration_T lIntNumberOfSeconds =
409  std::floor (lNumberOfSeconds);
410 
411  // Get the number of milliseconds.
412  const stdair::FloatDuration_T lNumberOfMilliseconds =
413  (lNumberOfSeconds - lIntNumberOfSeconds)
414  * stdair::MILLISECONDS_IN_ONE_SECOND;
415 
416  // +1 is a trick to ensure that the next Event is strictly later
417  // than the current one
418  const stdair::IntDuration_T lIntNumberOfMilliseconds =
419  std::floor (lNumberOfMilliseconds) + 1;
420 
421  // Convert the number of seconds and milliseconds into a duration.
422  const stdair::Duration_T lDifferenceBetweenDepartureAndThisRequest =
423  boost::posix_time::seconds (lIntNumberOfSeconds)
424  + boost::posix_time::millisec (lIntNumberOfMilliseconds);
425 
426  return lDifferenceBetweenDepartureAndThisRequest;
427  }
428 
429  // ////////////////////////////////////////////////////////////////////
430  const stdair::AirportCode_T DemandStream::generatePOS() {
431 
432  // Generate a random number between 0 and 1.
433  const stdair::Probability_T& lVariate = _demandCharacteristicsRandomGenerator();
434  const stdair::AirportCode_T& oPOS = _demandCharacteristics.getPOSValue (lVariate);
435 
436  return oPOS;
437  }
438 
439  // ////////////////////////////////////////////////////////////////////
440  const stdair::ChannelLabel_T DemandStream::generateChannel() {
441  // Generate a random number between 0 and 1.
442  const stdair::Probability_T lVariate =
444 
446  }
447 
448  // ////////////////////////////////////////////////////////////////////
449  const stdair::TripType_T DemandStream::generateTripType() {
450  // Generate a random number between 0 and 1.
451  const stdair::Probability_T lVariate =
453 
455  }
456 
457  // ////////////////////////////////////////////////////////////////////
458  const stdair::DayDuration_T DemandStream::generateStayDuration() {
459  // Generate a random number between 0 and 1.
460  const stdair::Probability_T lVariate =
462 
464  }
465 
466  // ////////////////////////////////////////////////////////////////////
467  const stdair::FrequentFlyer_T DemandStream::generateFrequentFlyer() {
468  // Generate a random number between 0 and 1.
469  const stdair::Probability_T lVariate =
471 
473  }
474 
475  // ////////////////////////////////////////////////////////////////////
476  const stdair::ChangeFees_T DemandStream::generateChangeFees() {
477  // Generate a random number between 0 and 1.
478  const stdair::Probability_T lVariate =
480  if (lVariate < _demandCharacteristics._changeFeeProb) {
481  return true;
482  }
483  return false;
484  }
485 
486  // ////////////////////////////////////////////////////////////////////
487  const stdair::NonRefundable_T DemandStream::generateNonRefundable() {
488  // Generate a random number between 0 and 1.
489  const stdair::Probability_T lVariate =
492  return true;
493  }
494  return false;
495  }
496 
497  // ////////////////////////////////////////////////////////////////////
498  const stdair::Duration_T DemandStream::generatePreferredDepartureTime() {
499  // Generate a random number between 0 and 1.
500  const stdair::Probability_T lVariate =
502  const stdair::IntDuration_T lNbOfSeconds = _demandCharacteristics.
503  _preferredDepartureTimeCumulativeDistribution.getValue (lVariate);
504 
505  const stdair::Duration_T oTime = boost::posix_time::seconds (lNbOfSeconds);
506 
507  return oTime;
508  }
509 
510  // ////////////////////////////////////////////////////////////////////
511  const stdair::WTP_T DemandStream::
512  generateWTP (stdair::RandomGeneration& ioGenerator,
513  const stdair::Date_T& iDepartureDate,
514  const stdair::DateTime_T& iDateTimeThisRequest,
515  const stdair::DayDuration_T& iDurationOfStay) {
516  const stdair::Date_T lDateThisRequest = iDateTimeThisRequest.date();
517  const stdair::DateOffset_T lAP = iDepartureDate - lDateThisRequest;
518  const stdair::DayDuration_T lAPInDays = lAP.days();
519 
520  stdair::RealNumber_T lProb = -lAPInDays;
521  stdair::RealNumber_T lFrat5Coef =
523 
524  const stdair::WTP_T lWTP = _demandCharacteristics._minWTP
525  * (1.0 + (lFrat5Coef - 1.0) * log(ioGenerator()) / log(0.5));
526 
527  return lWTP;
528  }
529 
530  // ////////////////////////////////////////////////////////////////////
531  const stdair::PriceValue_T DemandStream::generateValueOfTime() {
532  // Generate a random number between 0 and 1.
533  const stdair::Probability_T lVariate =
535 
537  }
538 
539  // ////////////////////////////////////////////////////////////////////
540  stdair::BookingRequestPtr_T DemandStream::
541  generateNextRequest (stdair::RandomGeneration& ioGenerator,
542  const stdair::DemandGenerationMethod& iDemandGenerationMethod) {
543 
544  // Origin
545  const stdair::AirportCode_T& lOrigin = _key.getOrigin();
546  // Destination
547  const stdair::AirportCode_T& lDestination = _key.getDestination();
548  // Preferred departure date
549  const stdair::Date_T& lPreferredDepartureDate =
551  // Preferred cabin
552  const stdair::CabinCode_T& lPreferredCabin = _key.getPreferredCabin();
553  // Party size
554  const stdair::NbOfSeats_T lPartySize = stdair::DEFAULT_PARTY_SIZE;
555  // POS
556  const stdair::AirportCode_T lPOS = generatePOS();
557 
558  // Compute the request date time with the correct algorithm.
559  stdair::DateTime_T lDateTimeThisRequest;
560  const stdair::DemandGenerationMethod::EN_DemandGenerationMethod& lENDemandGenerationMethod =
561  iDemandGenerationMethod.getMethod();
562  switch(lENDemandGenerationMethod) {
563  case stdair::DemandGenerationMethod::POI_PRO:
564  lDateTimeThisRequest = generateTimeOfRequestPoissonProcess(); break;
565  case stdair::DemandGenerationMethod::STA_ORD:
566  lDateTimeThisRequest = generateTimeOfRequestStatisticsOrder(); break;
567  default: assert (false); break;
568  }
569 
570  // Booking channel.
571  const stdair::ChannelLabel_T lChannelLabel = generateChannel();
572  // Trip type.
573  const stdair::TripType_T lTripType = generateTripType();
574  // Stay duration.
575  const stdair::DayDuration_T lStayDuration = generateStayDuration();
576  // Frequet flyer type.
577  const stdair::FrequentFlyer_T lFrequentFlyer = generateFrequentFlyer();
578  // Change fees
579  const stdair::ChangeFees_T lChangeFees = generateChangeFees();
580  // Change fee disutility
581  const stdair::Disutility_T lChangeFeeDisutility =
583  // Non refundable
584  const stdair::NonRefundable_T lNonRefundable = generateNonRefundable();
585  // Non refundable disutility
586  const stdair::Disutility_T lNonRefundableDisutility =
588  // Preferred departure time.
589  const stdair::Duration_T lPreferredDepartureTime =
591  // Value of time
592  const stdair::PriceValue_T lValueOfTime = generateValueOfTime();
593  // WTP
594  const stdair::WTP_T lWTP = generateWTP (ioGenerator,lPreferredDepartureDate,
595  lDateTimeThisRequest,lStayDuration);
596 
597  // TODO: move the creation of the structure out of the BOM layer
598  // (into the command layer, e.g., within the DemandManager command).
599 
600  // Create the booking request
601  stdair::BookingRequestStruct lBookingRequestStruct (describeKey(), lOrigin,
602  lDestination, lPOS,
603  lPreferredDepartureDate,
604  lDateTimeThisRequest,
605  lPreferredCabin, lPartySize,
606  lChannelLabel, lTripType,
607  lStayDuration, lFrequentFlyer,
608  lPreferredDepartureTime,
609  lWTP, lValueOfTime, lChangeFees,
610  lChangeFeeDisutility, lNonRefundable,
611  lNonRefundableDisutility);
612 
613  stdair::BookingRequestPtr_T oBookingRequest_ptr =
614  boost::make_shared<stdair::BookingRequestStruct> (lBookingRequestStruct);
615 
616  // DEBUG
617  // STDAIR_LOG_DEBUG ("\n[BKG] " << oBookingRequest_ptr->describe());
618 
619  return oBookingRequest_ptr;
620  }
621 
622  // ////////////////////////////////////////////////////////////////////
623  void DemandStream::reset (stdair::BaseGenerator_T& ioSharedGenerator) {
625  init (ioSharedGenerator);
626  }
627 
628 }