 // -*- C++ -*-

 namespace Kite {


 // -------------------------------------------------------------------
 // Class :  "SegmentAction".

 /*! \class        SegmentAction
  *  \brief        Store request for an event to be generated on a TrackElement
  *
  *                When an event on a Kite::TrackElement is being processed (with the
  *                SegmentFsm helper), it may generate events on TrackElement already
  *                placed and belonging either to the same net or other ones.
  *                Those events are not generated and queued immediatly but
  *                instead SegmentAction, requesting the event generation are created
  *                and stored into a simple vector in SegmentFsm. The last operation of
  *                the SegmentFsm object is to call the SegmentAction::doAction() method
  *                on all the action to actually generate and queue the events.
  */
 
 //! \enum         SegmentAction::Type
 //!               Indicates the kind of action to be performed on the segment. In the following
 //!               \b flags and \b masks descriptions, we uses the term <em>reference segment</em>
 //!               for the TrackElement which is associated with the currently processed RoutingEvent
 //!               (also referenced in SegmentFsm).
 //!
 //!               Here is the list of the availables actions that can be performed when (re)scheduling
 //!               a RoutingEvent. It is here that we uses the RoutingEvent level feature to perform
 //!               a local reordering of the top of the queue. Reordering is used to allows
 //!               perpandiculars to be routed \e before the reference segment (instead of after)
 //!               or \e other segments in conflict.
 //!
 //!                 - SegmentAction::SelfInsert<br>
 //!                   <b>Action:</b> The reference segment is to be inserted in a Track (placed).<br>
 //!                   <b>Event Level:</b> Unchanged.
 //!
 //!                 - SegmentAction::SelfRipup<br>
 //!                   <b>Action:</b> The reference segment is to be ripped up.<br>
 //!                   <b>Event Level:</b> Unchanged.
 //!
 //!                 - SegmentAction::SelfRipupPerpand<br>
 //!                   <b>Action:</b> Ripup a segment which is a perpandicular to the reference
 //!                   segment. Ordering considerations: this perpandicular will be put back into
 //!                   the RoutingEvent queue with a lower level (priority) than the reference
 //!                   segment, so it will be processed again \e after the reference segment.<br>
 //!                   <b>Event Level:</b> Unchanged.
 //!
 //!                 - SegmentAction::SelfRipupPerpandWithAxisHint<br>
 //!                   <b>Action:</b> Ripup a segment which is a perpandicular to the reference
 //!                   segment, supplies an axis hint and put it back into the RoutingEvent queue so
 //!                   that it will be processed \e before the reference segment.<br>
 //!                   <b>Event Level:</b> Increased to SegmentAction::EventLevel4.
 //!
 //!                 - SegmentAction::OtherRipup<br>
 //!                   <b>Action:</b> Ripping up a segment from another net and in the same direction
 //!                   as the reference segment.<br>
 //!                   <b>Event Level:</b> Unchanged.
 //!
 //!                 - SegmentAction::OtherRipupPerpandAndPushAside<br>
 //!                   <b>Action:</b> Ripping up a segment from another net and in perpandicular
 //!                   direction. The level is elevated so it's priority is greater than the
 //!                   reference segment this it will be reprocessed first. An axis hint is also
 //!                   supplied in order to make room for the reference segment.<br>
 //!                   <b>Event Level:</b> Increased to SegmentAction::EventLevel3.
 //!
 //!                 - SegmentAction::OtherRipupPerpandAndPacking<br>
 //!                   <b>Action:</b> Ripping up a segment from another net and in perpandicular
 //!                   direction. The level is elevated so it's priority is greater than the
 //!                   reference segment this it will be reprocessed first. The generated event
 //!                   is in packing mode only.<br>
 //!                   <b>Event Level:</b> Increased to SegmentAction::EventLevel4.
 
 //! \var          SegmentAction::Self
 //!               <b>[Flag]</b> The segment associated to the action is the reference segment
 //!               <em>or segments from the same net</em>.
 
 //! \var          SegmentAction::Other
 //!               <b>[Flag]</b> The segment associated to the action is \b not from the same
 //!               net as the reference segment. 
 
 //! \var          SegmentAction::Perpandicular
 //!               <b>[Flag]</b> The action concern a perpandicular to the reference segment. 
 
 //! \var          SegmentAction::Ripup
 //!               <b>[Flag]</b> Request that the segment is to be ripped up.
 
 //! \var          SegmentAction::RipedByLocal
 //!               <b>[Flag]</b> Indicate that the segment has been ripped up by a local one.
 
 //! \var          SegmentAction::ResetRipup
 //!               <b>[Flag]</b> The ripup count is to be reset.
 
 //! \var          SegmentAction::ToRipupLimit
 //!               <b>[Flag]</b> The ripup count is directly increased to the ripup limit,
 //!               triggering a state change the next time the segment will be processed.
 
 //! \var          SegmentAction::Insert
 //!               <b>[Flag]</b> Request that the segment is to be inserted in the given track.
 //!               It is the task of SegmentFsm to determine that there is sufficent space to do so.
 
 //! \var          SegmentAction::AxisHint
 //!               <b>[Flag]</b> An axis hint has been supplied, and is to be passed to
 //!               the generated RoutingEvent.
 
 //! \var          SegmentAction::PackingMode
 //!               <b>[Flag]</b> Whether the RoutingEvent should be processed in \e packing
 //!               mode or \e negociated mode (transmitted to the RoutingEvent).
 
 //! \var          SegmentAction::ToState
 //!               <b>[Flag]</b> Force the change of state of the RoutingEvent
 //!               (i.e. DataNegociate). Normally the state change is done through the
 //!               increase of the ripup count in DataNegociate.
 
 //! \var          SegmentAction::EventLevel1
 //!               <b>[Flag]</b> Increase the level to <em>at least</em> \b 1.
 
 //! \var          SegmentAction::EventLevel2
 //!               <b>[Flag]</b> Increase the level to <em>at least</em> \b 2.
 
 //! \var          SegmentAction::EventLevel3
 //!               <b>[Flag]</b> Increase the level to <em>at least</em> \b 3.
 
 //! \var          SegmentAction::EventLevel4
 //!               <b>[Flag]</b> Increase the level to <em>at least</em> \b 4.
 
 //! \var          SegmentAction::EventLevel5
 //!               <b>[Flag]</b> Increase the level to <em>at least</em> \b 5.
 
 //! \var          SegmentAction::SelfInsert
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \var          SegmentAction::SelfRipup
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \var          SegmentAction::SelfRipupPerpand
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \var          SegmentAction::SelfRipupPerpandWithAxisHint
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \var          SegmentAction::OtherRipup
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \var          SegmentAction::OtherRipupPerpandAndPushAside
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \var          SegmentAction::OtherRipupPerpandAndPacking
 //!               <b>[Mask]</b>, see SegmentAction::Type.
 
 //! \function     SegmentAction::SegmentAction ( TrackElement* segment, unsigned int type, DbU::Unit axisHint=0, unsigned int toState =0 );
 //! \param        segment   On what the action is to be performed.
 //! \param        type      Defines the type of action, see SegmentAction::Type.
 //! \param        axisHint  Specifies a preferred axis.
 //! \param        toState   The DataNegociate::SlackState into which the segment is to be set.
 //!
 //!               Create segment action.
 
 //! \function     TrackElement* SegmentAction::getSegment () const;
 //! \sreturn      The associated \c segment.
 
 //! \function     SegmentAction::Type  SegmentAction::getType () const;
 //! \sreturn      The action to be performed.
 
 //! \function     void  SegmentAction::setAxisHint ( DbU::Unit axis );
 //!               The axis preferred position to be transmitted to the generated event.
 //!               The transmition will be effective \e only if the SegmentAction::Type::AxisHint
 //!               flag is set.
 
 //! \function     unsigned int  SegmentAction::setFlag ( unsigned int flags );
 //!               Allow to change the action type by indivually setting up the flags.
 
 //! \function     void  SegmentAction::doAction ( RoutingEventQueue& queue );
 //!               Actually perform the action. That is, build and queue the appropriate
 //!               event for the segment.


 // -------------------------------------------------------------------
 // Class :  "SegmentFsm".
 
 /*! \class        SegmentFsm
  *  \brief        Pseudo-decorator to process a RoutingEvent
  *
  *                The SegmentFsm class actually perform the placement of the Kite::TrackElement
  *                of the Kite::RoutingEvent. It structured around three goals:
  *                  - Implement the finite state machine for the Kite::DataNegociate state.
  *                  - Provide a kind of decoration on the RoutingEvent/TrackElement
  *                    (it do not abide by the definition from Design Patterns).
  *                  - Cache a lot of on-the-fly computed datas needed during the
  *                    SegmentFsm lifetime and the Manipulator(s) it may uses.
  *
  *
  *  \section      secUpdate  Update Mechanism
  *
  *                The constructor of SegmentFsm triggers the update of the RoutingEvent
  *                and through it DataNegociate.
  *
  *
  *  \section      secSlackening  Slackening / FSM Transitions
  *
  *                A transition occurs in the FSM whenener all the availables ripup methods
  *                for a segment have failed. Failure means that the topology of the net
  *                itself must be altered to allow a greater level of flexibility.
  *                Modifying the net topology means to give the current segment some
  *                more slack.              
  *
  *                Availables slackening operations:
  *                  -# DataNegociate::RipupPerpandiculars (Manipulator) place the segments before any of
  *                     it's perpandiculars are placed to allow a maximum track choice.
  *                  -# DataNegociate::Minimize (Manipulator) try to fit the segment in a hole in a track,
  *                     perform a hole detection.
  *                  -# DataNegociate::Dogleg (Manipulator) create a dogleg matching <em>the first track
  *                     candidate</em> with a non-nul overlap.
  *                  -# DataNegociate::Slacken (Manipulator) \red{to be reviewed.}                   
  *                  -# DataNegociate::ConflictSolveByHistory (SegmentFsm) try to find a break point on
  *                     the segment, based on the ripup history.
  *                  -# DataNegociate::ConflictSolveByPlaceds (SegmentFsm) try to find a break point on
  *                     the segment, based on the current position of segments on the
  *                     candidate tracks.
  *                  -# DataNegociate::MoveUp (Manipulator) try to move up the segment.
  *
  *                Simple slackening operations are defined in Manipulator and complex ones
  *                directly in SegmentFsm.
  *
  *
  *  \section      secNonSlackening  Non-Slackening Operations
  *
  *                In addition, some operation that do not modifies the topology are
  *                availables:
  *                  -# Manipulator::forceOverLocals() mostly for global segments to ripup
  *                     a track from all it's locals.
  *                  -# SegmentFsm::insertInTrack() automates the three subsequent ripup
  *                     trials.
  */
 
 //! \enum         SegmentFsm::State
 //!               Indicates what the SegmentFsm has done the processed TrackElement,
 //!               possible values are:
 //!                 - SegmentFsm::MissingData, this is an error condition, the TrackElement
 //!                   do not have associated DataNegociate structure. Nothing is done.
 //!
 //!                 - SegmentFsm::EmptyTrackList, no Track is available for placement
 //!                   (free or used). 
 //!
 //!                 - SegmentFsm::SelfInserted, the TrackElement can be successfully
 //!                   inserted in a Track (i.e. without overlap).
 //!
 //!                 - SegmentFsm::SelfMaximumSlack, nothing can be done to further slacken
 //!                   the TrackElement, it is at maximum ripup of the last possible state
 //!                   (no more topological modifications are possibles).
 //!
 //!                 - SegmentFsm::OtherRipup, the TrackElement can be inserted but it
 //!                   needs the ripup of some others.
 
 //! \var          SegmentFsm::MissingData
 //!               <b>[Flag]</b>, see SegmentFsm::SegmentFsmValue.
 
 //! \var          SegmentFsm::EmptyTrackList
 //!               <b>[Flag]</b>, see SegmentFsm::SegmentFsmValue.
 
 //! \var          SegmentFsm::Inserted
 //!               <b>[Flag]</b>, the TrackElement can be inserted in a Track.
 
 //! \var          SegmentFsm::Self
 //!               <b>[Flag]</b>, the action is related to the processed TrackSegment.
 
 //! \var          SegmentFsm::Other
 //!               <b>[Flag]</b>, the action is \b not related to the processed TrackSegment,
 //!               that is, others are being topologically modificated or riped up.
 
 //! \var          SegmentFsm::Ripup
 //!               <b>[Flag]</b>, segement, that are not the processed one are being ripped up.
 
 //! \var          SegmentFsm::MaximumSlack
 //!               <b>[Flag]</b>, the processed segment as reached it's maximum ripup count on
 //!               the last possible slackening state.
 
 //! \var          SegmentFsm::SelfInserted
 //!               <b>[Mask]</b>, see SegmentFsm::SegmentFsmValue.
 
 //! \var          SegmentFsm::OtherRipup
 //!               <b>[Mask]</b>, see SegmentFsm::SegmentFsmValue.
 
 //! \var          SegmentFsm::SelfMaximumSlack
 //!               <b>[Mask]</b>, see SegmentFsm::SegmentFsmValue.
 
 //! \function     SegmentFsm::SegmentFsm ( RoutingEvent* event, RoutingEventQueue& queue, RoutingEventHistory& history );
 //! \param        event    The RoutingEvent to be processed.
 //! \param        queue    The RoutingEvent queue.
 //! \param        history  The complete history of RoutingEvent.
 //!
 //!               Construct a SegmentFsm from a RoutingEvent. The constructor is in charge of
 //!               computing all the cached values.
 
 //! \function     bool  SegmentFsm::isFullBlocked () const;
 //! \sreturn      \true if there are Tracks avalaibles but the constraints are such that none
 //!               is actually usable. 
 
 //! \function     RoutingEvent* SegmentFsm::getEvent () const;
 //! \sreturn      The currently processed RoutingEvent (\e cached).
 
 //! \function     RoutingEventQueue& SegmentFsm::getQueue () const;
 //! \sreturn      The RoutingEvent queue (\e cached).
 
 //! \function     RoutingEventHistory& SegmentFsm::getHistory () const;
 //! \sreturn      The RoutingEvent history (\e cached).
 
 //! \function     DataNegociate* SegmentFsm::getData ();
 //! \sreturn      The DataNegociate of the TrackElement (\e cached).
 
 //! \function     unsigned int  SegmentFsm::getState () const;
 //! \sreturn      The state (SegmentFsm::SegmentFsmValues) which the SegmentFsm has computed for the
 //!               RoutingEvent. This is \b not the state of the DataNegociate
 
 //! \function     Interval& SegmentFsm::getConstraint ();
 //! \sreturn      The interval into which the segment axis can be set (computed from
 //!               the topological constraints and the placement constraints on the
 //!               already placed perpandiculars).
 
 //! \function     Interval& SegmentFsm::getOptimal ();
 //! \sreturn      The interval for an optimal placement of the segment axis.
 
 //! \function     vector<TrackCost>& SegmentFsm::getCosts ();
 //! \sreturn      The table of cost for all the candidates Tracks of the segment.
 //!               The table is sorted in increasing cost order (see TrackCost).
 
 //! \function     TrackCost& SegmentFsm::getCost ( size_t i );
 //! \sreturn      The cost at index \c i in the table.
 
 //! \function     Track* SegmentFsm::getTrack ( size_t i );
 //! \sreturn      The Track for cost at index \c i in the table.
 
 //! \function     size_t  SegmentFsm::getBegin ( size_t i );
 //! \sreturn      The overlapping \e begin index in Track for cost at index \c i in the table.
 
 //! \function     size_t  SegmentFsm::getEnd ( size_t i );
 //! \sreturn      The overlapping \e end index in Track for cost at index \c i in the table.
 
 //! \function     vector<SegmentAction*>& SegmentFsm::getActions ();
 //! \sreturn      The table of SegmentAction, that is the delayed requests for RoutingEvent
 //!               creation.
 
 //! \function     unsigned int  SegmentFsm::setState ( unsigned int state );
 //! \sreturn      Sets the state of the state...
 
 //! \function     void  SegmentFsm::addAction ( TrackElement* segment, unsigned int type, DbU::Unit axisHint=0, unsigned int toState=0 );
 //!               Request the creation of a new delayed RoutingEvent, for the meaning of
 //!               the parameters, see SegmentAction::SegmentAction.
 
 //! \function     bool  SegmentFsm::doActions ();
 //!               Actually generate RoutingEvent(s) from the SegmentAction(s).
 
 //! \function     void  SegmentFsm::clearActions ();
 //!               Clear the the table of requested actions, whithout generating them.
 
 //! \function     void  SegmentFsm::clearActions ();
 //!               Clear the the table of requested actions, whithout generating them.
 
 //! \function     bool  SegmentFsm::insertInTrack ( size_t i );
 //!               Try to insert the TrackElement in the Track at index \c i (in the
 //!               cost table). Return \true if the insertion is possible.
 //!
 //!               The insertion is not done at this stage, but a set of ripup actions is
 //!               emitted to allow insertion the next time the segment will be processed.
 //!
 //!               Three subsequent trials are done before giving up on inserting
 //!               the segment:
 //!                 -# Manipulator::insertInTrack(), try to push asides the neighbors.
 //!                 -# Manipulator::shrinkToTrack(), try squeeze the segment in an existing
 //!                    free space.
 //!                 -# Manipulator::forceToTrack(), perform a complete ripup of all the
 //!                    neighbors and their perpandiculars.
 //!
 //!               The event keeps track of the insertion attempt step (see RoutingEvent::getInsertState()).
 
 //! \function     bool  SegmentFsm::conflictSolveByHistory ();
 //! \sreturn      \true if a suitable dogleg has been created in the segment.
 //!
 //!               Initially, global segments may be very long, and a placement solution
 //!               in which each one is placed on a track of it's own may not be realisable.
 //!               In that case, at least one of the global segment must be broken.
 //!               The figure below illustrate the case: <b>(a)</b>, <b>(b)</b>, <b>(c)</b> form a 
 //!               first cluster and <b>(d)</b>, <b>(e)</b>, <b>(f)</b> form a second one. Due to the
 //!               constraints of the segments the remaining free track cannot be the same
 //!               in both clusters. The only solution to place <b>(g)</b> is to break it into
 //!               two sub-globals. The whole point of the conflict solve is to correctly
 //!               detect the cluster and choose the breaking point.
 //!
 //!               \image html  ConflictSolve-1.png "Conflict Between Globals"
 //!
 //!               This variant of the conflict solve method try to guess the track span
 //!               for which there is a conflict by looking at the event history.
 //!
 //!               \image html  ConflictSolveByHistory-1.png "Building Conflicting Intervals"
 //!
 //!               <b>Dislodger Definition:</b>
 //!
 //!               A segment is said to be a dislodger if it matches the two following criterions:
 //!                 - It's span intersect the to be inserted segment span.
 //!                 - It has been placed on a track inside the perpandicular span of the
 //!                   to be placed segment.
 //!               
 //!               For the time beeing we limit the search to the last three dislodgers, to not
 //!               waste too much time looking back the event history. We merge overlapping
 //!               intervals into one (see the undocumented class \c UnionIntervals and
 //!               \c RipupHistory in \c SegmentFsm.cpp).
 //!
 //!               \red{For the time beeing we only look on the track into which}
 //!               \red{the to be inserted segment wants to be placed.}
 //!               
 //!               Then we try to break the to be placed segment, first under the lower bound
 //!               (source) of the conflicting interval then, in case of failure under
 //!               the upper bound (target).
 //!
 //!               \image html  ConflictSolveByHistory-2.png "Interval Breaking"
 
 //! \function     bool  SegmentFsm::conflictSolveByPlaceds ();
 //! \sreturn      \true if a suitable dogleg has been created in the segment \e or a
 //!               dislodger has been moved up.
 //!
 //!               This methods achieve the same goal as SegmentFsm::conflictSolveByHistory()
 //!               but uses a different strategy.
 //!
 //!               Instead of looking through the history to find dislodgers it analyses
 //!               the placed segments in all the candidates tracks for the to be placed
 //!               segment. Unlike it's sibling method, which creates only one dogleg, as
 //!               it uses the Manipulator::relax() method, it may creates up to two doglegs.
 //!
 //!               <b>Synthetic Description</b>
 //!
 //!                 -# For each track, find the dislodgers, merge the overlaps into one
 //!                    interval and store the length of the longuest overlap (aka conflict).
 //!                 -# Sort the tracks according to decreasing longuest overlap/confict.
 //!                 -# For each track in the sorted list, look for a dislodger under the middle
 //!                    of the to be placed segment. If no dislodger is present at this place
 //!                    go to the next track. Otherwise:
 //!                      - <em>The dislodger is local</em>, then try to relax the to placed
 //!                        segment around the dislodger.
 //!                      - <em>The dislodger is global</em>, try to move it up, if it is not
 //!                        possible, fallback to the relax approach.
 //!                 -# Quit on the first successful move up or relax. 
 //!                 -# If there is no candidate tracks, this means the vertical constraints
 //!                    are too tight, in that case, ripup the perpandiculars (fallback plan).
 //!
 //!               <b>Interval Accounting</b>
 //!
 //!               Only global conflicting segments are took into account. Local segments
 //!               may be took into account if they overlap global ones (all part of the
 //!               same net). All overlapping segments are merged into one big conflict
 //!               interval. The whole length of a conflict interval is took into account
 //!               event if it's overlap with the to be placed segment is only partial.
 //!
 //!               <b>Track Ordering (lexicographic)</b>
 //!
 //!                 -# The longuest (in one interval) conflict length.
 //!                 -# The longuest cumulative conflict length (all interval summed up).
 //!
 //!               Interval accounting and Track ordering is managed through the undocumented
 //!               \c Cs1Candidate class implemented in \c SegmentFsm.cpp.
 //!
 //!               \image html  ConflictSolveByPlaceds-1.png "Candidates Track Ordering"
 
 //! \function     bool  SegmentFsm::desaturate ();
 //!               Try to create a suitable empty space in a cost Track by moving up
 //!               TrackElement in conflict.
 
 //! \function     bool  SegmentFsm::slackenTopology ( unsigned int flags=0 );
 //!               Modificate the topology of the TrackElement to slacken it.
 //!               It is the implementation of the slakening finite state machine.
 
 //! \function     bool  SegmentFsm::solveFullBlockages ();
 //!               Try to solve a fully blocked configuration.

 }
