
 // -*- C++ -*-


 namespace Kite {

 /*! \class        RoutingEvent
  *  \brief        Manage TrackSegment routing requests.
  *
  *                The \RoutingEvent is the workhorse of Kite. A \RoutingEvent is
  *                associated to one \TrackSegment. One \TrackSegment could be
  *                associated to many \RoutingEvent in the queue, but only one
  *                of those is active (marked as unprocessed).
  *
  *  \see          ClassManipulator.
  *
  *  \section      secProcessAlgorithm  Description of the process() method
  *
\code
void  RoutingEvent::process ()
{
  if ( isProcessed() ) return;
  setProcessed  ();
  incRipupCount ();

  if ( getRipupCount() > MAX_RIPUP_COUNT ) {
    // We are *not* in ripup mode.
    // The event's segment has to be topologically modified.
    modifyTopology ( _segment );
  } else {
    // We are in ripup mode.
    // Other overlaping segments are to be removeds/pusheds. It can result in
    // segment breaking *if* other segment came from an already routed GCell.

    // optimal, constraint, perpandicular.
    computeAllIntervals ();

    // Find & order all candidates Tracks.
    candidates = computeCostOnCandidateTracks ();
    sort ( candidates );

    if ( candidates[0].isFree() ) {
      // Case -A.1- "Free Track".
      candidate[0].insert ( _segment );
    } else if (    candidates[0].isSoftOverlap()
                || candidates[0].isHardOverlap() ) {
      // Case -A.2- "Soft Overlap".
      // Case -A.3- "Hard Overlap".
      for ( size_t i=0 ; i<candidates.size() ; i++ ) {
        if ( candidates[0].insertInTrack ( _segment ) ) {
          break;
        }
      }
    } else {
      // Case -B- "Infinite Cost".
      // Attention: meaning's changed, *infinite* only in case of
      // conflict with a *fixed* other segment.
      modifyTopology ( _segment );
    }
  }

  // Restore Track coherency before processing any other event.
  Session::revalidate ();
}
\endcode
  *  \section      secRoutingIntervalToDo  ToDo
  *
  *                <ul>
  *                  <li>New \c isLocal() method on \TrackSegment. Tells if the \TrackSegment
  *                      is associated only to local AutoSegment.
  *                  <li>Increase the overlap cost of a \TrackSegment from an already routed
  *                      GCell routing set.
  *                </ul>
  *
  *
  *  \section      secRoutingEventInterval  The various intervals of a RoutingEvent
  *
  *                The three Intervals controlling a RoutingEvent : all those intervals
  *                defines the track range in which the \TrackSegment could be inserted.
  *                <ul>
  *                  <li>The <i>optimal</i> interval : where the \Net wirelength will be
  *                      minimal (comes from \c Katabatic::AutoSegment).
  *                  <li>The <i>constraint</i> interval : the interval outside of which
  *                      the \Net connexity would be broken. This is the bigger interval
  *                      but it must be strictly respected (also comes from
  *                      \c Katabatic::AutoSegment).
  *                  <li>The <i>perpandicular</i> interval : for each perpandicular
  *                      \TrackSegment connected, the intersection of the free interval
  *                      around them in their track.
  *
  *                      It is important to note that the \TrackSegment overlaping in the
  *                      target track is not removed from the track. It is it's perpandiculars
  *                      which are, along with a modification of theirs left axis weight and/or
  *                      right axis weight.
  *
  *                      Second remark: no overlap will be created (due to the non-removal of
  *                      overlaping \TrackSegments) because the insertion is delayed in case
  *                      of overlap.
  *                </ul>
  *                The perpandicular interval comes from perpandicular constraints on \TrackSegment
  *                of the <i>same</i> \c Net. The left/right axis weights comes from requests of
  *                <i>other</i> \c Nets.
  *
  *                \image html  RoutingEvent-1.png "RoutingEvent Intervals"
  *                \image latex RoutingEvent-1.pdf "RoutingEvent Intervals"   width=0.6\textwidth
  *
  *                Example of perpandicular interval computation :
  *
  *                \image html  RoutingEvent-2.png "Perpandicular Interval"
  *                \image latex RoutingEvent-2.pdf "Perpandicular Interval"
  *
  *
  *  \section      secRoutingEventRules  Rules governing RoutingEvents
  *
  *                \RoutingEvent respect the following rules:
  *                <ul>
  *                  <li>A \TrackSegment can only be displaced by it's associated \RoutingEvent.
  *                  <li>Corollary: the only \TrackSegment displaced while processing a
  *                      \RoutingEvent is the one associated to the event.
  *                  <li>Conflicts occurs between the \RoutingEvent \TrackSegment and already
  *                      placed others \TrackSegment.
  *
  *                        The conflict can be solved by displacing/modifying <i>others</i>
  *                      \TrackSegment or by modifying the to be inserted one. In the later
  *                      case, the newly created or modified \TrackSegment are (re)scheduleds
  *                      <i>before</i> the would be inserted. 
  *                  <li>Conflicting \TrackSegments are only removed from their \Track
  *                      but their axis remains unchanged. Movement requests are passed
  *                      through increase of the left/right axis weights, if needed.
  *                  <li>\TrackSegment are inserted only, and only if there is enough free space.
  *                      That is, if any kind of overlap occurs, it is <i>not</i> inserted
  *                      but <i>rescheduled</i>. The blocking \TrackSegments are then
  *                      rescheduled <i>after</i> the current one.
  *                  <li>Each \RoutingEvent processing takes place inside a one atomic
  *                      Session. That is, the coherency of the data-base is restored
  *                      immediatly afterward (both Kite &amp; Katabatic).
  *                </ul>
  *
  *  \remark       Be very careful to distinguish between Session commands, which affects
  *                \Track and \TrackSegment insertion/update/removal and schedule/re-schedule
  *                events, which relates to the negociation algorithm.
  *
  *                Re-ordering rules:
  *                <ol>
  *                  <li>In normal mode, that is, no maximum ripup has been reached, the
  *                      blocking <i>other</i> \TrackSegment are removed and the current
  *                      is rescheduled <i>before</i> them.
  *                  <li>In maximum ripup mode, some \TrackSegment has to give way.
  *                  <ul>
  *                    <li>If the current one is modified, it must be rescheduled <i>after</i>
  *                        it's modified bits are rescheduleds.
  *                    <li>If <i>others</i> are modifieds they must be rescheduled <i>after</i>
  *                        the current one (so it will grabs the place).
  *                  </ul>
  *                </ol>
  *
  *
  *  \section      secRoutingEventCycle  RoutingEvent life cycle
  *
  *                As an active \RoutingEvent is associated with one and only one \TrackSegment
  *                we can talk indeferently of \RoutingEvent lifecycle or \TrackSegment
  *                lifecycle.
  *
  *                Below is the ordered list of states that a \RoutingEvent could be in.
  *                The order correspond to increasing level of slackening/freedom.
  *                Transition between states occurs each time a maximum ripup is reached.
  *
  *                <table>
  *                  <tr>
  *                    <td align="center">&nbsp;\b Id&nbsp;</td>
  *                    <td align="center">\b Type</td>
  *                    <td align="center">&nbsp;\b Local&nbsp;</td>
  *                    <td align="center">&nbsp;\b Global&nbsp;</td>
  *                    <td align="center">\b Action</td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 1</td>
  *                    <td align="center">\c Minimize</td>
  *                    <td align="center">\e yes</td>
  *                    <td align="center">\e no</td>
  *                    <td>try to fit into a hole</td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 2</td>
  *                    <td align="center">\c DogLeg</td>
  *                    <td align="center">\e yes</td>
  *                    <td align="center">\e no</td>
  *                    <td>Dogleg : analyse overlap and try to solve it by breaking (self)</td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 3</td>
  *                    <td align="center">\c Desalignate</td>
  *                    <td align="center">\e yes</td>
  *                    <td align="center">\e yes</td>
  *                    <td>on a set of alignated \TrackSegment, suppress the
  *                        alignment constraints, thus making then independants
  *                    </td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 4</td>
  *                    <td align="center">\c Slacken</td>
  *                    <td align="center">\e yes</td>
  *                    <td align="center">\e yes</td>
  *                    <td>if the target/source constraint is less than the
  *                        GCell, adds perpandicular straps to free the \TrackSegment.
  *                        This occurs to free from terminal constraints
  *                    </td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 5</td>
  *                    <td align="center">\c ConflictSolve1</td>
  *                    <td align="center">\e yes</td>
  *                    <td align="center">\e yes</td>
  *                    <td>try to find in the history a reccurent dislodger,
  *                        and break (self) to accomodate it
  *                    </td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 6</td>
  *                    <td align="center">\c ConflictSolve2</td>
  *                    <td align="center">\e no</td>
  *                    <td align="center">\e yes</td>
  *                    <td>try to find a Track on which we can dislodge
  *                        an other \TrackSegment
  *                    </td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 7</td>
  *                    <td align="center">\c MoveUp</td>
  *                    <td align="center">\e no</td>
  *                    <td align="center">\e yes</td>
  *                    <td>try to go on upper layer.
  *                    </td>
  *                  </tr>
  *                  <tr>
  *                    <td align="center">\e 8</td>
  *                    <td align="center">\c Unimplemented</td>
  *                    <td align="center">\e no</td>
  *                    <td align="center">\e yes</td>
  *                    <td>we failed to place this \TrackSegment
  *                    </td>
  *                  </tr>
  *                </table>
  *
  *
  *  \section      secManageMaximumRipup  Managing the maximum ripup case
  *
\code
bool  State::manageMaximumRipup ()
{
  bool success = false;

  if ( !_segment->isGlobal() ) {
    // Candidates Tracks (ignore optimal & perpandiculars).
    candidates = computeAllIntervals ();
    overlap    = _segment->getInterval();

    for ( size_t i=0 ; i<candidates.size() ; i++ ) {
      others = otherSegmentsConflicts(candidates[i]);

      // Select Track with only one conflicting other.
      if ( others.size() == 1 ) {
        // Local vs. Local    => reject.
        // Local vs. Terminal => reject.
        if ( others[0]->isLocal() || others[0]->isTerminal() ) continue;

        // Local vs. Global (not routed yet).
        if ( others[i]->getOrder() >= _segment->getOrder() ) {
          success = modifyTopology(others[0]);
          break;
        }

        // Local vs. Global (already routed).
        success = relax(_others[0],overlap);
        if ( success ) break;
      }
    }
  }

  if ( !success ) {
    // Global vs. Local.
    // Failed Local vs. Any.
    success = modifyTopology(_segment);    
  }
  return success;
}
\endcode
  *
  *
  *  \section      secModifyTopology  Description of the modifyTopology() method
  *
\code
bool  Manipulator::modifyTopology ( TrackSegment* segment )
{
  bool success = false;

  if ( segment->isLocal() ) {
    if ( segment->canMinimize() {
      segment->minimize();
      success = true;
    }
    if ( segment->canDogLeg() ) {
      // Case -C.4- "Self Relax".
      segment->makeDogLeg();
      success = true;
    }    
  } else if ( segment->canDesalignate() ) {
    // Case -C.5- "Desalignate".
    segment->desalignate();
    success = true;
  } else if ( segment->canSlacken() ) {
    // Case -C.6- "Slacken".
    segment->slacken();
    success = true;
  } else {
    RipupHistory* history      = RipupHistory(segment);
    GCell*        dogLegGCell  = history.getDogLegGCell();
  
    if ( dogLegGCell ) {
      if ( segment->canDogLegAt(dogLegGCell) ) {
        segment->makeDogLeg(dogLegGCell)
        success = true;
      }
    } else {
      // Dislodgers seems to far in ripup history.
      // Recheck the Track, maybe they have vanish.
      Track* track = getTrack(segment);
      if ( track->getFreeInterval(segment) ) {
        track.insert ( segment );
        success = true;
      }
    }
  }
  
  if ( segment->canMoveUp() ) {
    segment->moveUp ();
    success = true;
  }

  if ( success ) {
    resetRipupCount(segment);
  } else {
    cerr << "[UNIMPLEMENTED] " << segment << endl;
  }

  return success;
}
\endcode
  *
  *
  *  \section      secHardSoftOverlap  Hard and soft overlap
  *
  *                Schematic execution of a \RoutingEvent leading to a set aside.
  *                <ol>
  *                  <li>The scheduler try to place the \TrackSegment on top of the
  *                      event queue, calling process().
  *                  <li>There is a soft overlap on the best candidate track, a set
  *                      aside is issued.
  *                  <li>Each \TrackSegment in conflict in the candidate track has the
  *                      \RoutingEvent bounds of it's perpandicular \TrackSegment modificated
  *                      according to the free space requested through setLeftBound() or setRightBound().
  *                  <li>If a perpandicular is already in a \Track is removed from it and scheduled for
  *                      immediate re-routing (it's event level is increased so it pops
  *                      out immediately from the queue).
  *                  <li>If the perpandicular is not routed yet, we are done.
  *
  *                      Note that this technique of modificating a \RoutingEvent yet to come is
  *                      kind a like seeing the future...
  *                </ol>
  *
  *                \image html  RoutingEvent-3.png "Set aside schematic"
  *                \image latex RoutingEvent-3.pdf "Set aside schematic"
  *
  *
  *  \section      setDetructionStrategy  Destruction Strategy
  *
  *                \RoutingEvent are not destroyed as soon as they have been processed by
  *                the scheduler. Instead, they are stored in the historical queue.
  *                They are two reasons for that behavior :
  *                <ul>
  *                  <li>\RoutingEvent are used to store algorithmic informations that
  *                      must persist until the negociation algorithm have fully
  *                      completed (<i>bound</i> interval in particular).
  *                  <li>When ripup phases takes place and maximum ripup count is
  *                      reached, the history can be used to find the whole set of
  *                      \TrackSegment in conflict an made an educated guess about
  *                      which one must be relaxed.
  *                </ul>
  *
  *  \important    This is the history queue which is responsible for freeing all the
  *                \RoutingEvent in his destructor.
  *
  *
  *  \section      secRoutingEventCase  Routing Event actions
  *
  *                <ul>
  *            <li><b>Free Track Case</b>
  *
  *                There is a sufficent free space in the candidate \Track to insert the
  *                \TrackSegment. The \TrackSegment is inserted.
  *
  *  \important    This is the only way for a \TrackSegment to be inserted into a \Track.
  *
  *                \image html  RoutingEvent-10.png
  *                \image latex RoutingEvent-10.pdf
  *
  *
  *            <li><b>Soft Overlap Case</b>
  *
  *                Already inserted \TrackSegment <b>a</b> &amp; <b>b</b> could be shrunk
  *                to make place for \TrackSegment <b>c</b>. Parallel overlaping \TrackSegment
  *                are not removed, their perpandiculars are with updated left/right axis weight.
  *
  *                The <b>a</b> perpandicular belongs the same GCell routing set so it
  *                is removed from is \Track to be displaced.
  *
  *                The <b>b</b> perdandicular belongs to a more prioritary GCell routing
  *                set, which has therefore be placed earlier so it can't be removed.
  *                Instead it is broken.
  *
  *                \image html  RoutingEvent-11.png
  *                \image latex RoutingEvent-11.pdf
  *
  *
  *            <li><b>Hard Overlap Case</b>
  *
  *                No way to shrunk overlaping \TrackSegment to make place for <b>c</b>.
  *                All parallel overlaping \TrackSegments must be removeds to be displaced
  *                on other \Tracks.
  *
  *                The <b>a</b> parallel belongs to a more prioritary GCell routing set
  *                so it can be removed, it is therefore broken.
  *
  *                The <b>b</b> parallel belongs the same GCell routing set so it can be
  *                removed to be displaced.
  *
  *                \image html  RoutingEvent-12.png
  *                \image latex RoutingEvent-12.pdf
  *
  *
  *            <li><b>Self Relax</b>
  *
  *                Instead of trying to displace overlaping \TrackSegments we break the
  *                current one.
  *
  *                \image html  RoutingEvent-13.png
  *                \image latex RoutingEvent-13.pdf
  *
  *
  *            <li><b>Self Desalignate</b>
  *
  *                Instead of trying to displace overlaping \TrackSegments we desalignate
  *                it's components (by supressing alignement constraints on it's
  *                AutoContacts). We do not create new Katabatic components but new
  *                \TrackSegments will appears.
  *
  *                \image html  RoutingEvent-14.png
  *                \image latex RoutingEvent-14.pdf
  *
  *
  *            <li><b>Self Slacken</b>
  *
  *                Instead of trying to displace overlaping \TrackSegments we slacken
  *                the current one. This is different than desalignate because we create
  *                new Katabatic component to relax any AutoContact transmitted constraints.
  *                This operation is most likely to be applied on \TrackSegments that are
  *                directly connecteds to terminals.
  *
  *                \image html  RoutingEvent-15.png
  *                \image latex RoutingEvent-15.pdf
  *
  *                </ul>
  */

 /*! \function     bool  RoutingEvent::isProcessed () const;
  *  \return       \true if this event has already been processed.
  *
  *  \remark       Note that inside a _setAside() a \RoutingEvent can be re-posted for
  *                a given \TrackSegment which has been processed yet. This can lead
  *                to two or more \RoutingEvent in the queue (as we cannot easily remove
  *                a \RoutingEvent already in the queue). We need this new \RoutingEvent
  *                because we want to reschedule with a new priority/slack.
  *                As we cannot remove the previous \RoutingEvent, we mark it as
  *                processed for it to be ignored by the scheduler.
  */

 /*! \function     TrackSegment* RoutingEvent::getSegment () const;
  *  \Return       The associated and unique \TrackSegment.
  */

 /*! \function     unsigned long  RoutingEvent::getPriority () const;
  *  \Return       The second criterion used to sort \RoutingEvents in the negociation queue.
  *                Currently, it is the <i>area</i> of the associated \TrackSegment, which in
  *                turn return the <i>slack</i> (not a very fortunate choice of name...).
  */

 /*! \function     unsigned int  RoutingEvent::getEventLevel () const;
  *  \Return       The first criterion used to sort \RoutingEvents in the negociation queue.
  *                It is used to re-schedule a \RoutingEvent and make the new event be
  *                processed <i>before</i> the original one, which is marked as
  *                <i>processed</i> to be ignored.
  *
  *  \see          setEventLevel().
  */

 /*! \function     RoutingEvent* RoutingEvent::getClone () const;
  *  \Return       An exact copy of the current \RoutingEvent.
  */

 /*! \function     RoutingEvent* RoutingEvent::reschedule ( RoutingEventQueue& queue );
  *  \param        queue  The \RoutingEvent queue.
  *  \return       The rescheduled \RoutingEvent. May be \NULL if it cannot be rescheduled.
  */

 /*! \function     void  RoutingEvent::setProcessed ( bool state=true );
  *  \param        state  The state into which the event is to be put.
  *
  *                Mark the event as processed. This arises in two cases :
  *                <ul>
  *                  <li>The event has really been processed by the process() member
  *                      function.
  *                  <li>There has been a fork from this event and it has been
  *                      superseded by a newly rescheduled one, so we have to
  *                      invalidate this one.
  *                </ul>
  */

 /*! \function     void  RoutingEvent::setEventLevel ( unsigned int level );
  *  \param        level  The new event level.
  *
  *  \see          getEventLevel().
  */

 /*! \function     void     RoutingEvent::process ( RoutingEventQueue& queue, RoutingEventHistory& history );
  *  \param        queue    The event queue from the negociate algorithm.
  *  \param        history  The event history.
  *
  *                Perform all the operations shared by all \RoutingEvent classes then
  *                calls the virtual _subProcess() functions.
  *
  *                Shared operations are :
  *                <ol>
  *                  <li>Invalidating all perpandicular \TrackSegments.
  *                  <li>Computing the free interval allowed by the free intervals
  *                      in perpandicular \Tracks holding the perpandicular \TrackSegments.
  *                  <li>Merging in the various constraints intervals : from the
  *                      \TrackSegment itself, from the free intervals in the
  *                      perpandicular \Tracks and from the \RoutingEvent bound
  *                      constraints.
  *                  <li>Finding the candidate \Tracks for the \RoutingEvent,
  *                      using \c Track_Spiral \Collection.
  *                </ol>
  *                The results of the shared operation are passed to derived classes
  *                trough the \c State internal structure.
  */

 /*  \function     bool  RoutingEvent::_setAside ( Track* track, size_t begin, size_t end, Net* net, Interval interval, RoutingEventQueue& queue );
  *  \param        track    The track in wich to make free space.
  *  \param        begin    The index of the first overlaping TrackSegment.
  *  \param        end      The index of the last overlaping TrackSegment.
  *  \param        net      The net for which we want to insert a TrackSegment.
  *  \param        interval The interval which must be made empty.
  *  \param        queue    The queue of RoutingEvent.
  *
  *                Manage the case of <i>soft overlap</i>. Create or enlarge a free space
  *                in \c track so it can contain the requested \interval. <code>[begin:end]</code> defines
  *                the range of indexes of overlaping \TrackSegment in \c track.
  *                Displace TrackSegment that are <b>perpandicular</b> to those overlaping,
  *                remove them from their \c Track if needed and issue an associated \RoutingEvent
  *                with an updated bound constraint. Note that the overlaping \TrackSegment
  *                themselves are <em>not</em> removed from the \c track.
  *
  *                A note on implementation :
  *                <ul>
  *                  <li>\c data1 : the DataNegociate of the to be inserted \TrackSegment.
  *                  <li>\c segment2 : the current overlaping \TrackSegment (from \c begin
  *                      to \c end).
  *                  <li>\c data2 : the DataNegociate of the overlaping \TrackSegment.
  *                  <li>\c segment3 : a \TrackSegment perpandicular to \c segment2.
  *                </ul>
  */

 /*  \function     void  RoutingEvent::_ripup ( Track* track, Net* net, Interval interval, size_t begin, size_t end, RoutingEventQueue& queue );
  *  \param        track    The track in wich to make free space.
  *  \param        net      The net for which we want to insert a TrackSegment.
  *  \param        interval The interval which must be made empty.
  *  \param        begin    The index of the first overlaping TrackSegment.
  *  \param        end      The index of the last overlaping TrackSegment.
  *  \param        queue    The queue of RoutingEvent.
  *
  *                Manage the case of <i>hard overlap</i>, that is bluntly remove
  *                any \TrackSegment overlaping \interval. Issue both a remove event
  *                (to \c Session) and a \RoutingEvent to re-process the dislodged
  *                \TrackSegment.
  */

 }  // End of Kite namespace. 
