TimeIntervalCollection.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Core / CSharp / System / Windows / Media / Animation / TimeIntervalCollection.cs / 1305600 / TimeIntervalCollection.cs

                            //------------------------------------------------------------------------------ 
//  Microsoft Windows Client Platform
//  Copyright (c) Microsoft Corporation, 2003
//
//  File:       TimeIntervalCollection.cs 
//-----------------------------------------------------------------------------
 
// Semantics 
// =========
// 
// DEFINITION:
// A TimeIntervalCollection (TIC) is a set of points on the time line, which may
// range from negative infinity (not including negative infinity itself) up to positive
// infinity (potentially including positive infinity).  It may also include a point Null, 
// which does not belong on the time line.  This non-domain point is considered to
// represent a state of 'Stopped'. 
// 
//
// OPERATIONS: 
// For any given time point P, a TIC must know whether it contains P or not.
// For any open interval (A,B), a TIC must know whether it has a non-empty intersection with (A,B).
// For any given TICs T and S, we must be able to determine if T and S have an non-empty intersection.
// 
//
// GENERAL DATA REPRESENTATION: 
// A TIC is represented by a set of nodes ordered on the real time line. 
// Each node is indexed, and has an associated time _nodeTime[x] and two flags:
//   _nodeIsPoint[x] specifies whether the time point at _nodeTime[x] is included in the TIC, and 
//   _nodeIsInterval[x] specifies whether the open interval (_nodeTime[x], _nodeTime[x+1])
// is included in the TIC.  If the node at x is the last node, and _nodeIsInterval[x] == true,
// then the TIC includes all points in the open interval (_nodeTime[x], Infinity).
// The presence of the Null point is denoted by the boolean _containsNullPoint. 
//
// Example #1: 
//   TIC includes closed-open interval [3,6) and point 7. 
//
//   Time:    3       6       7     infinity 
//        ---[X]=====[ ]-----[X]-------...
//   Index:   0       1       2
//
//       _nodeTime[0] = 3           _nodeTime[1] = 6            _nodeTime[2] = 7 
//    _nodeIsPoint[0] = true     _nodeIsPoint[1] = false     _nodeIsPoint[2] = true
// _nodeIsInterval[0] = true  _nodeIsInterval[1] = false  _nodeIsInterval[2] = false 
// 
// Example #2:
//   TIC includes point 0, the open interval (3,8), and the interval (8,infinity]; does not include point 8. 
//
//   Time:    0       3       8     infinity
//        ---[X]-----[ ]=====[ ]=======...
//   Index:   0       1       2 
//
//       _nodeTime[0] = 0            _nodeTime[1] = 3            _nodeTime[2] = 8 
//    _nodeIsPoint[0] = true      _nodeIsPoint[1] = false     _nodeIsPoint[2] = false 
// _nodeIsInterval[0] = false  _nodeIsInterval[1] = true   _nodeIsInterval[2] = true
// 
// RULES FOR LEGAL DATA REPRESENTATION:
// In order to keep the TIC and its algorithms optimized, we enforce the following rules:
//
// 1) All nodes are stored in strictly increasing _nodeTime order.  E.g. nodes remain sorted and 
//      each node has a unique _nodeTime.
// 
// 2) No unnecessary nodes are present: for any x < xMax, in the boolean sequence: 
//
//      _nodeIsPoint[x], _nodeIsInterval[x], _nodeIsPoint[x+1], _nodeIsInterval[x+1] 
//           [ ]----------------------------------[ ]--------------------------------
//
//    we maintain the following invariants:
//    [A] Out of the last three, at least one is true. 
//        Otherwise we don't need node X+1 to represent the same TIC.
//        If all are false, we have an illegal EMPTY node. 
//    [B] Out of the last three, at least one is false. 
//        Otherwise we don't need node X+1 to represent the same TIC.
//        If all are true, we have an illegal SATURATED node. 
//    [C] For the first index x=0, at least one out of _nodeIsPoint[x] or _nodeIsInterval[x] is true.
//        Otherwise we don't need node 0 to represent the same TIC,
//        and we have another case of an illegal EMPTY node.
// 
// 3) As a consequence of legal data representation, the TIC contains no points prior to the time
//     of its first node, e.g. if time T < _nodeTime[0] then T is not in the TIC. 
// 
//
// NOTE: 
// Please refer to the above comments and rules when reading documentation for specific methods below.
//

 
#if DEBUG
#define TRACE 
#endif // DEBUG 

using System; 
using System.Collections;
using System.Diagnostics;
using MS.Internal;
 
namespace System.Windows.Media.Animation
{ 
    ///  
    /// A list of timing events observed internally by a TimelineClock object.
    ///  
    internal struct TimeIntervalCollection
    {
        #region External interface
 
        #region Methods
 
        ///  
        /// Creates an empty collection
        ///  
        private TimeIntervalCollection(bool containsNullPoint)
        {
            Debug.Assert(_minimumCapacity >= 2);
 
            _containsNullPoint = containsNullPoint;
 
            _count = 0; 
            _current = 0;
            _invertCollection = false; 

            _nodeTime = null;
            _nodeIsPoint = null;
            _nodeIsInterval = null; 
        }
 
        ///  
        /// Creates a collection containing a single time point.
        ///  
        private TimeIntervalCollection(TimeSpan point)
            : this(false)
        {
            InitializePoint(point); 
        }
 
        ///  
        /// Reuses an existing collection so it now contains a single time point.
        ///  
        private void InitializePoint(TimeSpan point)
        {
            Debug.Assert(IsEmpty);  // We should start with a new or Clear()-ed collection first
 
            EnsureAllocatedCapacity(_minimumCapacity);
 
            _nodeTime[0] = point; 
            _nodeIsPoint[0] = true;
            _nodeIsInterval[0] = false; 
            Debug.Assert(_nodeIsInterval[0] == false);

            _count = 1;
        } 

        ///  
        /// Creates a collection that spans from a single point to infinity. 
        /// 
        private TimeIntervalCollection(TimeSpan point, bool includePoint) 
            : this(false)
        {
            InitializePoint(point);
 
            _nodeIsPoint[0] = includePoint;
            _nodeIsInterval[0] = true; 
        } 

        ///  
        /// Creates a collection containing a single interval.
        /// If from == to and the interval is not open-open, then a single point is created.
        /// 
        ///  
        /// The first endpoint time.
        ///  
        ///  
        /// Specifies whether the point from is included in the TIC.
        ///  
        /// 
        /// The last endpoint time.
        /// 
        ///  
        /// Specifies whether the point to is included in the TIC.
        ///  
        private TimeIntervalCollection(TimeSpan from, bool includeFrom, TimeSpan to, bool includeTo) 
            : this(false)
        { 
            EnsureAllocatedCapacity(_minimumCapacity);

            _nodeTime[0] = from;
 
            if (from == to)  // Create single point
            { 
                if (includeFrom || includeTo)  // Make sure we aren't trying to create a point from an open-open interval 
                {
                    _nodeIsPoint[0] = true; 
                    _count = 1;
                }
                else  // We are trying to create an open interval (x, x), so just create an empty TIC
                { 
                    Debug.Assert(_count == 0);  // The boolean constructor already did the job for us
                } 
            } 
            else  // from != to
            { 
                if (from < to)
                {
                    _nodeIsPoint[0] = includeFrom;
                    _nodeIsInterval[0] = true; 

                    _nodeTime[1] = to; 
                    _nodeIsPoint[1] = includeTo; 
                }
                else  // We are given reversed coordinates 
                {
                    _nodeTime[0] = to;
                    _nodeIsPoint[0] = includeTo;
                    _nodeIsInterval[0] = true; 

                    _nodeTime[1] = from; 
                    _nodeIsPoint[1] = includeFrom; 
                }
 
                _count = 2;
            }
        }
 
        /// 
        /// Removes all time intervals from the collection. 
        ///  
        internal void Clear()
        { 
            // Deallocate ONLY if we have previously expanded beyond default length to avoid redundant
            // reallocation.  If we called Clear, we are likely to reuse the collection soon.
            if (_nodeTime != null && _nodeTime.Length > _minimumCapacity)
            { 
                _nodeTime = null;
                _nodeIsPoint = null; 
                _nodeIsInterval = null; 
            }
 
            _containsNullPoint = false;

            _count = 0;
            _current = 0; 
            _invertCollection = false;
        } 
 
        // Used for optimizing slip computation in Clock
        internal bool IsSingleInterval 
        {
            get
            {
                return (_count < 2) || (_count == 2 && _nodeIsInterval[0]); 
            }
        } 
 
        // Used for optimizing slip computation in Clock
        internal TimeSpan FirstNodeTime 
        {
            get
            {
                Debug.Assert(_count > 0); 
                return _nodeTime[0];
            } 
        } 

        // Used for optimizing slip computation in Clock 
        // This method will discard nodes beyond the first two nodes.
        // The only scenario where this method is called on a larger-than-size-2 TIC is
        // when the parent of a Media wraps around in a Repeat.  Then we only enter
        // the Media's active period on the wraparound part of the TIC, so it is the only important 
        // part to leave.
        // Example: the parent has Duration=10 and RepeatBehavior=Forever.  It went from 9ms to 2ms (wraparound). 
        // Our default TIC is {[0, 2], (9, 10)}.  Slipping this by 1 will change it to {[1, 2]}.  It is apparent 
        // that this is the only part of the parent that actually overlaps our active zone.
        internal TimeIntervalCollection SlipBeginningOfConnectedInterval(TimeSpan slipTime) 
        {
            if (slipTime == TimeSpan.Zero)  // The no-op case
            {
                return this; 
            }
 
            TimeIntervalCollection slippedCollection; 
            if (_count < 2 || slipTime > _nodeTime[1] - _nodeTime[0])
            { 
                // slipTime > the connected duration, which basically eliminates the parent TIC interval for us;
                // This would only happen when media "outruns" the parent container, producing negative slip.
                slippedCollection = TimeIntervalCollection.Empty;
            } 
            else
            { 
                // Just shift the first node by slipAmount; the constructor handles the a==b case. 
                slippedCollection = new TimeIntervalCollection(_nodeTime[0] + slipTime, _nodeIsPoint[0],
                                                               _nodeTime[1]           , _nodeIsPoint[1]); 
            }

            if (this.ContainsNullPoint)
            { 
                slippedCollection.AddNullPoint();
            } 
            return slippedCollection; 
        }
 
        // Used for DesiredFrameRate adjustments in Clock
        internal TimeIntervalCollection SetBeginningOfConnectedInterval(TimeSpan beginTime)
        {
#if DEBUG 
            Debug.Assert(IsSingleInterval);
#endif 
            Debug.Assert(0 < _count && _count <= 2); 

            if (_count == 1) 
            {
                return new TimeIntervalCollection(_nodeTime[0], _nodeIsPoint[0],
                                                  beginTime,    true);
            } 
            else  // _count == 2
            { 
                Debug.Assert(beginTime <= _nodeTime[1]); 
                return new TimeIntervalCollection(beginTime,    false,
                                                  _nodeTime[1], _nodeIsPoint[1]); 
            }
        }

        ///  
        /// Creates a collection containing a single time point
        ///  
        static internal TimeIntervalCollection CreatePoint(TimeSpan time) 
        {
            return new TimeIntervalCollection(time); 
        }

        /// 
        /// Creates a collection containing a closed-open time interval [from, to) 
        /// 
        static internal TimeIntervalCollection CreateClosedOpenInterval(TimeSpan from, TimeSpan to) 
        { 
            return new TimeIntervalCollection(from, true, to, false);
        } 

        /// 
        /// Creates a collection containing an open-closed time interval (from, to]
        ///  
        static internal TimeIntervalCollection CreateOpenClosedInterval(TimeSpan from, TimeSpan to)
        { 
            return new TimeIntervalCollection(from, false, to, true); 
        }
 
        /// 
        /// Creates a collection containing a closed time interval [from, infinity)
        /// 
        static internal TimeIntervalCollection CreateInfiniteClosedInterval(TimeSpan from) 
        {
            return new TimeIntervalCollection(from, true); 
        } 

        ///  
        /// Creates an empty collection
        /// 
        static internal TimeIntervalCollection Empty
        { 
            get
            { 
                return new TimeIntervalCollection(); 
            }
        } 

        /// 
        /// Creates a collection with the null point
        ///  
        static internal TimeIntervalCollection CreateNullPoint()
        { 
            return new TimeIntervalCollection(true); 
        }
 
        /// 
        /// Adds the null point to an existing collection
        /// 
        internal void AddNullPoint() 
        {
            _containsNullPoint = true; 
        } 

 
        /// 
        /// Returns whether the time point is contained in the collection
        /// 
        // RUNNING TIME: O(log2(_count)) worst-case 
        // IMPLEMENTATION FOR CONTAINS(TIME) OPERATION:
        // To determine if point at time T is contained in the TIC, do the following: 
        // 
        //   1) Find the largest index x, such that _nodeTime[x] <= T
        // 
        //   2) IF no such x exists, then _nodeTime[x] > T for every valid x;
        //        then T comes earlier than any node and cannot be in the TIC by Rule #3 above.
        //        Diagram: ----T----[0]----[1]----[2]---...
        // 
        //   3) ELSE IF x exists and _nodeTime[x] == T, then T happens to coincide with a TIC node.
        //        We check if TIC contains _nodeTime[x] by querying and RETURNING _nodeIsPoint[x]. 
        //        Diagram -----[ ]----[T,x]----[ ]----... 
        //
        //   4) ELSE x exists and _nodeTime[x] < T, then T happens to fall after a TIC node at x, but before 
        //        the next TIC node if any later nodes exist.  We check if TIC contains the open interval
        //        (_nodeTime[x], _nodeTime[x+1]) or (_nodeTime[x], infinity) if node x was the last node.
        //        We do this by querying and RETURNING _nodeIsInterval[x].
        //        Diagram: -----[x]----T----[x+1]----[x+2]--.... 
        //          =OR=   -----[x]----T----infinity
        // 
        internal bool Contains(TimeSpan time) 
        {
            int index = Locate(time);  // Find the previous or equal time 

            if (index < 0)  // Queried time lies before the earliest interval's begin time
            {
                return false; 
            }
            else if (_nodeTime[index] == time)  // Queried time falls exactly onto a node 
            { 
                return _nodeIsPoint[index];
            } 
            else  // Queried time comes after the node
            {
                Debug.Assert(_nodeTime[index] < time);
 
                return _nodeIsInterval[index];
            } 
        } 

 
        /// 
        /// Returns whether the open interval (from, to) has an intersection with this collection
        /// 
        // RUNNING TIME: O(log2(_count)) worst-case 
        // IMPLEMENTATION FOR INTERSECTS(FROM,TO) OPERATION:
        // We want to determine if the open interval (From,To), abbreviated (F,T), has a non-zero intersection 
        // with the TIC.  Assert F= 0.  F comes right at or after _nodeTime[fromIndex] and before 
        //         any next node; T comes strictly after _nodeTime[fromIndex] (because we asserted F= 0) && _nodeIsInterval[toIndex] 
        //
        //         Notice that this clause is good to short-circuit early, because it traps cases of 
        //         complete mismatches, where the interval is not in the TIC's normal range.
        //
        //   4) ELSE IF the difference between fromIndex and toIndex is exactly 1 (e.g. fromIndex+1 == toIndex), then:
        // 
        //       * Suppose fromIndex is -1, thus F falls before the first node.
        //         Then toIndex is at least 0, thus T falls at least aligned with the first node. 
        //         Now it matters whether T is at or after the first node.  If T is at the first node, 
        //         then all points in (F,T) lie *before* the first node and we have no possible intersection,
        //         so we have to return FALSE.  Else T is after the first node, then some point in (F,T) lies 
        //         exactly on the first node, and some points lie after it.  By rule #2C, one of these two parts
        //         must be contained in the TIC.  So then we return TRUE.
        //
        //         This is simplified as RETURN (_nodeTime[toIndex] < T) 
        //
        //         Diagram (lowercase t denotes toIndex): 
        //                     (F)=======(T) 
        //                  -------------[t]-----[ ]----.....
        // 
        //                     (F)=========(T)
        //                  ----------[t]--------[ ]----.....
        //
        //       * Else fromIndex is non-negative, thus F falls at or right after node at [fromIndex]. 
        //         Then toIndex falls at least at or right after node at [fromIndex+1].
        //         (F,T) now must overlap the open interval (_nodeTime[fromIndex], _nodeTime[toIndex]), 
        //         and IFF _nodeTime[toIndex] < T then it will also overlap the point at _nodeTime[toIndex] 
        //         and part of the open interval (_nodeTime[toIndex], nextNodeTime_or_Infinity).  In the
        //         first case we merely check _nodeIsInterval[fromIndex].  In the second case, we invoke 
        //         rule #2B and conclude that an intersection must exist somewhere between all three parts.
        //         Hence we RETURN _nodeIsInterval[fromIndex] || (_nodeTime[toIndex] < T).
        //
        //         Diagram (lowercase t denotes toIndex; t denotes toIndex): 
        //                        (F)=======(T)
        //                  --[f]-----------[t]-----[ ]----..... 
        // 
        //                     (F)===========(T)
        //                  ---[f]------[t]--------[ ]----..... 
        //
        //         The entire clause can now be further simplified as the following statement:
        //         RETURN (_nodeTime[toIndex] < T) || (fromIndex >= 0 && _nodeIsInterval[fromIndex])
        // 
        //   5) ELSE the difference between fromIndex and toIndex is greater than 1 (e.g. fromIndex+1 < toIndex), then:
        // 
        //       * Suppose fromIndex is -1, thus F falls before the first node. 
        //         Then toIndex is at least 1, thus T falls at least aligned with the second node.
        //         Then (F,T) overlaps at least point _nodeTime[0] and open interval (_nodeTime[0], _nodeTime[1]). 
        //         By rule #2C above, at least one of those two must be in the TIC, hence some point in (F,T)
        //         is also in the TIC, we have a non-null intersection and RETURN TRUE.
        //
        //         Diagram (lowercase t denotes toIndex): 
        //                      (F)=========(T)
        //                  ----------[ ]---[t]----[ ]----..... 
        // 
        //                      (F)=============(T)
        //                  --------[ ]-----[t]------[ ]----..... 
        //
        //       * Else fromIndex is non-negative, thus F falls at or right after node at [fromIndex].
        //         Then toIndex falls at least at or after node at [fromIndex+2].
        //         Then the following parts of the TIC must partially overlap the interval: 
        //            (A) open interval (_nodeTime[fromIndex], _nodeTime[fromIndex+1])
        //            (B) point at _nodeTime[fromIndex+1] 
        //            (C) open interval (_nodeTime[fromIndex+1], _nodeTime[fromIndex+2]) 
        //         By rule #2B, at least one of the consecutive parts in the above sequence must be included in the TIC.
        //         Therefore, a point in the interval (F,T) must be contained in the TIC, and we RETURN TRUE. 
        //
        //         Diagram (lowercase f denotes fromIndex; t denotes toIndex):
        //                         (F)=========(T)
        //                  --[f]--------[ ]---[t]----[ ]----..... 
        //
        //                      (F)============(T) 
        //                  ----[f]----[ ]-----[t]------[ ]----..... 
        //
        //       Both sub-clauses lead to the same result, so we uniformly RETURN TRUE when reaching this clause. 
        //
        internal bool Intersects(TimeSpan from, TimeSpan to)
        {
            if (from == to)  // The open interval (x, x) is null and has no intersections 
            {
                return false; 
            } 
            else if (from > to)  // If to and from are reversed, swap them back
            { 
                TimeSpan temp = from;
                from = to;
                to = temp;
            } 

            int fromIndex = Locate(from);  // Find the nearest indices for to and from 
            int   toIndex = Locate(to); 

            Debug.Assert(fromIndex <= toIndex); 

            if (fromIndex == toIndex)
            {
                // Since we are testing an *open* interval, the only way we can intersect is by checking 
                // if the interior of the arc is part of the TIC.
                return (toIndex >= 0) && _nodeIsInterval[toIndex]; 
            } 
            // The interval only overlaps one TIC node; fromIndex may be -1 here
            else if (fromIndex + 1 == toIndex) 
            {
                Debug.Assert(toIndex >= 0); // Since fromIndex!=toIndex, toIndex must be >= 0

                // By rule #2B and C, if we fall across an arc boundary, we must therefore intersect the TIC. 
                return (to > _nodeTime[toIndex]) || (fromIndex >= 0 && _nodeIsInterval[fromIndex]);
            } 
            else 
            {
                Debug.Assert(fromIndex + 1 < toIndex); 

                // We must fall across an arc boundary, and by rule #2B we must therefore intersect the TIC.
                return true;
            } 
        }
 
        ///  
        /// Returns whether this collection has a non-empty intersection with the other collection
        ///  
        // RUNNING TIME: O(_count) worst-case
        // IMPLEMENTATION FOR INTERSECTS(OTHER) OPERATION:
        //
        //  We implement intersection by "stacking" the two TICs atop each other and seeing if 
        //  there is any point or interval common to both.  We do this by having two indexers,
        //  index1 and index2, traverse the lengths of both TICs simultaneously.  We maintain 
        //  the following invariant: each indexer, when "projected" onto the other TIC than the one 
        //  it actually indexes into, falls less than a node ahead of the other indexer.
        //  To rephrase intuitively, the indexers never fall out of step by having one get 
        //  too far ahead of the other.
        //
        //  Example:
        // 
        //  this    ----[0]----[1]--------------------[2]----[3]-----------[4]---------[5]------...
        //  other   --------------------[0]----[1]------------------[2]----------------[3]------... 
        //                      ^index1 
        //                               ^index2
        // 
        //  Our invariant means that one of the indexed nodes either coincides exactly with
        //  the other, as is the case for nodes this[4] and other[2] in the above example,
        //  or "projects" into the other node's subsequent interval; in the above example,
        //  other[index2] projects onto the interval of this[index1]. 
        //
        //  At each iteration, we check for an intersection at: 
        //    A) the latter of the indexed nodes, and 
        //    B) the interval right after the latter indexed node
        // 
        //  3 possible scenarios:
        //  CASE I.   index1 < index2  intersects if _nodeIsInterval[index1] && (_nodeIsPoint[index2] || _nodeIsInterval[index2])
        //  CASE II.  index1 > index2  intersects if _nodeIsInterval[index2] && (_nodeIsPoint[index1] || _nodeIsInterval[index1])
        //  CASE III. index1 = index2  intersects if (_nodeIsPoint[index1] && _nodeIsPoint[index2]) || (_nodeIsInterval[index1] && _nodeIsInterval[index2]) 
        //
        //  We say that in Case I, index1 is dominant in the sense that index2 points to a node on index1's "turf"; 
        //  We move index2 through index1's entire interval to check for intersections against it.  Once index2 passes 
        //  index1's interval, we advance index1 as well.  Then we again check which scenario we end up in.
        // 
        //  Case II is treated anti-symmetrically to Case I.
        //
        //  Case III is special, because we cannot treat it the same as Case I or II.  This is becasue we have to check
        //  for a point-point intersection, and check which indexer should be advanced next.  It is possible that both 
        //  indexers need to be advanced if the next 2 nodes are also equal.
        // 
        //  We continue advancing the pointers until we find an intersection or run out of nodes on either of the TICs. 
        //
        internal bool Intersects(TimeIntervalCollection other) 
        {
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled

            if (this.ContainsNullPoint && other.ContainsNullPoint)  // Short-circuit null point intersections 
            {
                return true; 
            } 
            else if (this.IsEmptyOfRealPoints || other.IsEmptyOfRealPoints)  // Only intersection with an empty TIC is at null points, which case is already handled
            { 
                return false;
            }
            else  // Both TICs are non-empty and don't intersect at the null point
            { 
                return IntersectsHelper(other);
            } 
        } 

        // This method was made separate to detect intersections with inverses when needed 
        private bool IntersectsHelper(TimeIntervalCollection other)
        {
            // Make sure the indexers are starting next to each other
            IntersectsHelperPrepareIndexers(ref this, ref other); 

            // The outer loop does not bail, rather we return directly from inside the loop 
            bool intersectionFound = false; 
            while (true)
            { 
                // The inner loops iterate through the subset of a TIC

                // CASE I.
                // In this case, index1 is the dominant indexer: index2 is on its turf and we keep advancing index2 and checking for intesections 
                // After this helper, index2 will no longer be ahead of index1
                if ((this.CurrentNodeTime < other.CurrentNodeTime) && 
                    IntersectsHelperUnequalCase(ref this, ref other, ref intersectionFound)) 
                {
                    return intersectionFound; 
                }


                // CASE II. 
                // In this case, index2 is the dominant indexer: index1 is on its turf and we keep advancing index1 and checking for intesections
                // After this helper, index1 will no longer be ahead of index2 
                if ((this.CurrentNodeTime > other.CurrentNodeTime) && 
                    IntersectsHelperUnequalCase(ref other, ref this, ref intersectionFound))
                { 
                    return intersectionFound;
                }

 
                // CASE III.
                // In this case, neither indexer is dominant: they are pointing to the same point in time 
                // We keep doing this until the indices are no longer equal 
                while (this.CurrentNodeTime == other.CurrentNodeTime)
                { 
                    if (IntersectsHelperEqualCase(ref this, ref other, ref intersectionFound))
                    {
                        return intersectionFound;
                    } 
                }
            } 
        } 

        // Make sure the indexers are starting next to each other 
        static private void IntersectsHelperPrepareIndexers(ref TimeIntervalCollection tic1, ref TimeIntervalCollection tic2)
        {
            Debug.Assert(!tic1.IsEmptyOfRealPoints);  // We shouldn't reach here if either TIC is empty
            Debug.Assert(!tic2.IsEmptyOfRealPoints); 

            tic1.MoveFirst();  // Point _current to the first node in both TICs 
            tic2.MoveFirst(); 

            // First bring tic1._current and tic2._current within an interval of each other 
            if (tic1.CurrentNodeTime < tic2.CurrentNodeTime)
            {
                // Keep advancing tic1._current as far as possible while keeping _nodeTime[tic1._current] < _nodeTime[tic2._current]
                while (!tic1.CurrentIsAtLastNode && (tic1.NextNodeTime <= tic2.CurrentNodeTime)) 
                {
                    tic1.MoveNext(); 
                } 
            }
            else if (tic2.CurrentNodeTime < tic1.CurrentNodeTime) 
            {
                // Keep advancing tic2._current as far as possible while keeping _nodeTime[tic1._current] > _nodeTime[tic2._current]
                while (!tic2.CurrentIsAtLastNode && (tic2.NextNodeTime <= tic1.CurrentNodeTime))
                { 
                    tic2.MoveNext();
                } 
            } 
        }
 
        // Returns true if we know at this point whether an intersection is possible between tic1 and tic2
        // The fact of whether an intersection was found is stored in the ref parameter intersectionFound
        static private bool IntersectsHelperUnequalCase(ref TimeIntervalCollection tic1, ref TimeIntervalCollection tic2, ref bool intersectionFound)
        { 
            Debug.Assert(!intersectionFound);  // If an intersection was already found, we should not reach this far
 
            if (tic1.CurrentNodeIsInterval)  // If we are within an interval in tic1, we immediately have an intersection 
            {
                // If we have gotten into this method, tic1._current comes earlier than does tic2._current; 
                // Suppose the following assert is false; then by Rule #2A, tic2's previous interval must be included;
                // If this was the case, then tic2's previous interval overlapped tic1's current interval.  Since it's
                // included, we would have encountered an intersection before even reaching this method!  Then you
                // should not even be here now.  Else suppose we are at tic2's first node, then the below Assert 
                // follows directly from Rule #3.
                Debug.Assert(tic2.CurrentNodeIsPoint || tic2.CurrentNodeIsInterval); 
 
                intersectionFound = true;
                return true; 
            }
            else if (tic1.CurrentIsAtLastNode)  // // If we are already at the end of tic1, we ran out of nodes that may have an intersection
            {
                intersectionFound = false; 
                return true;
            } 
            else  // Else we are inside a non-included interval in tic1, no intersection is possible, but keep advancing tic2._current 
            {
                while (!tic2.CurrentIsAtLastNode && (tic2.NextNodeTime <= tic1.NextNodeTime)) 
                {
                    tic2.MoveNext();
                }
 
                // If nextNodeTime1 is null, we should never get here because the IF statement would have caught it and quit
                Debug.Assert(!tic1.CurrentIsAtLastNode);  // Thus tic1._current can be safely advanced now 
 
                // Now tic1._current can be safely advanced forward
                tic1.MoveNext(); 

                // If we broke out of Case I, its conditional should no longer hold true:
                Debug.Assert(tic1.CurrentNodeTime >= tic2.CurrentNodeTime);
 
                // Enforce our invariant: neither index gets too far ahead of the other.
                Debug.Assert(tic2.CurrentIsAtLastNode || (tic1.CurrentNodeTime < tic2.NextNodeTime)); 
                Debug.Assert(tic1.CurrentIsAtLastNode || (tic2.CurrentNodeTime < tic1.NextNodeTime)); 

                // Tell the main algorithm to continue working 
                return false;
            }
        }
 
        // Returns true if we know at this point whether an intersection is possible between tic1 and tic2
        // The fact of whether an intersection was found is stored in the ref parameter intersectionFound 
        static private bool IntersectsHelperEqualCase(ref TimeIntervalCollection tic1, ref TimeIntervalCollection tic2, ref bool intersectionFound) 
        {
            // If the nodes match exactly, check if the points are both included, or if the intervals are both included 
            if ((tic1.CurrentNodeIsPoint && tic2.CurrentNodeIsPoint) ||
                (tic1.CurrentNodeIsInterval && tic2.CurrentNodeIsInterval))
            {
                intersectionFound = true; 
                return true;
            } 
            // We did not find an intersection, but advance whichever index has a closer next node 
            else if (!tic1.CurrentIsAtLastNode && (
                tic2.CurrentIsAtLastNode || (tic1.NextNodeTime < tic2.NextNodeTime))) 
            {
                tic1.MoveNext();
            }
            else if (!tic2.CurrentIsAtLastNode && ( 
                     tic1.CurrentIsAtLastNode || (tic2.NextNodeTime < tic1.NextNodeTime)))
            { 
                tic2.MoveNext(); 
            }
            else if (!tic1.CurrentIsAtLastNode && !tic2.CurrentIsAtLastNode) 
            {
                // If both indices have room to advance, and we haven't yet advanced either one, it must be the next nodes are also exactly equal
                Debug.Assert(tic1.NextNodeTime == tic2.NextNodeTime);
 
                // It is necessary to advance both indices simultaneously, otherwise we break our invariant - one will be too far ahead
                tic1.MoveNext(); 
                tic2.MoveNext(); 
            }
            else  // The only way we could get here is if both indices are pointing to the last nodes 
            {
                Debug.Assert(tic1.CurrentIsAtLastNode && tic2.CurrentIsAtLastNode);

                // We have exhausted all the nodes and not found an intersection; bail 
                intersectionFound = false;
                return true; 
            } 

            // Enforce our invariant: neither index gets too far ahead of the other. 
            Debug.Assert(tic2.CurrentIsAtLastNode || (tic1.CurrentNodeTime < tic2.NextNodeTime));
            Debug.Assert(tic1.CurrentIsAtLastNode || (tic2.CurrentNodeTime < tic1.NextNodeTime));

            // Tell the main algorithm to continue working 
            return false;
        } 
 
        /// 
        /// Returns whether this collection has a non-empty intersection with the inverse of the other collection 
        /// 
        internal bool IntersectsInverseOf(TimeIntervalCollection other)
        {
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled 

            if (this.ContainsNullPoint && !other.ContainsNullPoint)  // Intersection at null points 
            { 
                return true;
            } 
            if (this.IsEmptyOfRealPoints)  // We are empty, and have no null point; we have nothing to intersect
            {
                return false;
            } 
            else if (other.IsEmptyOfRealPoints ||  // We are non-empty, and other is the inverse of empty (e.g. covers all real numbers, so we must intersect), OR...
                     this._nodeTime[0] < other._nodeTime[0])  // Neither TIC is empty, and we start first; this means the inverted "other" by necessity 
                                                              // overlaps our first node, so it must intersect either our node or subsequent interval. 
            {
                return true; 
            }
            else  // Neither TIC is empty, and other starts no later than we do; then use regular intersection logic with inverted boolean flags
            {
                other.SetInvertedMode(true); 

                bool returnValue = IntersectsHelper(other); 
 
                other.SetInvertedMode(false);  // Make sure we don't leave other TIC in an inverted state!
 
                return returnValue;
            }
        }
 

        ///  
        /// Returns whether this collection has a non-empty intersection with a potentially infinite 
        /// periodic collection defined by a set of parameters.
        ///  
        /// 
        /// The periodic TIC, or PTIC, represents the subset of the active period in a timeline where time
        /// flows non-linearly.  Specifically, it contains the points of reversal in autoreversing timelines,
        /// and the accel and decel periods in timelines with acceleration. 
        /// 
        /// Begin time of the periodic collection. 
        /// Length of a single iteration in the periodic collection. 
        /// Ratio by which to scale down the periodic collection.
        /// Ratio of the length of the accelerating portion of the iteration. 
        /// Ratio of the length of the decelerating portion of the iteration.
        /// Indicates whether reversed arcs should follow after forward arcs.
        internal bool IntersectsPeriodicCollection(TimeSpan beginTime,  Duration period, double appliedSpeedRatio,
                                                   double accelRatio, double decelRatio, 
                                                   bool isAutoReversed)
        { 
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled 

            if ( IsEmptyOfRealPoints                                      // If we have no real points, no intersection with the PTIC is possible 
              || (period == TimeSpan.Zero)                                // The PTIC has no nonzero period, we define such intersections nonexistent
              || (accelRatio == 0 && decelRatio == 0 && !isAutoReversed)  // The PTIC has no non-linear points, no intersection possible
              || !period.HasTimeSpan                                      // We have an indefinite period, e.g. we are not periodic
              || appliedSpeedRatio > period.TimeSpan.Ticks)               // If the speed ratio is high enough the period will effectively be 0 
            {
                return false; 
            } 

            // By now, we know that: 
            // (A) Both we and the PTIC are non-empty
            // (B) We are a subset of the active period, which is the superset of the PTIC

            // Find the smallest n such that _nodeTime[n+1] > beginTime; n can be the last index, so that _nodeTime[n+1] is infinity 

            MoveFirst(); 
 
            Debug.Assert(beginTime <= CurrentNodeTime);  // The PTIC is clipped by the active period, and we are a subset of the active period
            Debug.Assert(CurrentIsAtLastNode || beginTime < NextNodeTime); 

            long beginTimeInTicks = beginTime.Ticks;

            long periodInTicks = (long)((double)period.TimeSpan.Ticks / appliedSpeedRatio); 

            // PeriodInTicks may overflow if appliedSpeedRatio is sufficiently small. 
            // The best we can do is clamp the value to MaxValue. 
            if (periodInTicks < 0)
            { 
                periodInTicks = Int64.MaxValue / 2;
            }

            long doublePeriod = 2 * periodInTicks; 

            long accelPeriod = (long)(accelRatio * (double)periodInTicks); 
            long decelPeriod = (long)((1.0 - decelRatio) * (double)periodInTicks);  // This is where deceleration BEGINS. 

            // We walk through the TIC and convert from TIC's coordinates into wrapped-around PTIC coordinates: 
            //
            //  *======o   Linear   *============o  ...(wraparound to front)
            //   Accel *============o    Decel
            //         ^            ^            ^ 
            //    accelPeriod  decelPeriod  periodInTicks
 
            while (_current < _count) 
            {
                long projectedCurrentNodeTime; 
                bool isOnReversingArc = false;

                if (isAutoReversed)  // If autoreversed, our effective period is doubled and we check for reversed arcs
                { 
                    projectedCurrentNodeTime = ((CurrentNodeTime.Ticks - beginTimeInTicks) % doublePeriod);
                    if (projectedCurrentNodeTime >= periodInTicks) 
                    { 
                        projectedCurrentNodeTime = doublePeriod - projectedCurrentNodeTime;  // We are on a reversed arc
                        isOnReversingArc = true; 
                    }
                }
                else  // Default, non-autoreversed case
                { 
                    projectedCurrentNodeTime = (CurrentNodeTime.Ticks - beginTimeInTicks) % periodInTicks;
                } 
 

                if ((0 < projectedCurrentNodeTime && projectedCurrentNodeTime < accelPeriod)  // If we fall strictly into the accel zone, or... 
                 || (decelPeriod < projectedCurrentNodeTime))                    // We fall strictly into the decel zone
                                                                                 // (note we KNOW that projectedCNT < periodInTicks by definition of modulo)
                {
                    return true; 
                }
                else if ((projectedCurrentNodeTime == 0 || projectedCurrentNodeTime == decelPeriod) 
                      && CurrentNodeIsPoint)  // We fall exactly onto the beginning of an accel or decel zone, point intersection 
                {
                    return true; 
                }
                else if (CurrentNodeIsInterval)
                {
                    if ((projectedCurrentNodeTime == 0 && accelPeriod > 0) 
                     || (projectedCurrentNodeTime == decelPeriod && (decelPeriod < periodInTicks)))
                    // We fall exactly onto the beginning of an accel or decel zone and have the interval intersect 
                    { 
                        return true;
                    } 
                    else  // Else our node falls into the linear zone, but our interval may overlap a later Accel/Decel zone.
                          // Check if the interval is just long enough to stretch to the next non-linear zone.
                    {
                        long projectedTimeUntilIntersection; 
                        if (isOnReversingArc)
                        { 
                            projectedTimeUntilIntersection = projectedCurrentNodeTime - accelPeriod; 
                        }
                        else 
                        {
                            projectedTimeUntilIntersection = decelPeriod - projectedCurrentNodeTime;
                        }
 
                        if (CurrentIsAtLastNode
                          || (NextNodeTime.Ticks - CurrentNodeTime.Ticks >= projectedTimeUntilIntersection)) 
                          // We have an intersection, so long as we aren't clipped by endTime 
                        {
                            return true; 
                        }
                    }
                }
 
                // We haven't found any intersection at the present node and interval, advance to the next node
                MoveNext(); 
            } 

            return false;  // We have exhausted all nodes and found no intersection. 
        }

        /// 
        /// Returns whether this collection has intersections with multiple distinct periods of a 
        /// potentially infinite periodic collection defined by a set of parameters.
        ///  
        ///  
        /// The periodic TIC, or PTIC, represents the subset of the active period in a timeline where time
        /// flows non-linearly.  Specifically, it contains the points of reversal in autoreversing timelines, 
        /// and the accel and decel periods in timelines with acceleration.
        /// 
        /// Begin time of the periodic collection.
        /// Length of a single iteration in the periodic collection. 
        /// Ratio by which to scale down the periodic collection.
        internal bool IntersectsMultiplePeriods(TimeSpan beginTime, Duration period, double appliedSpeedRatio) 
        { 
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled
 
            if (_count < 2                                    // If we have 0-1 real points, no intersection with multiple periods is possible
              || (period == TimeSpan.Zero)                    // The PTIC has no nonzero period, we define such intersections nonexistent
              || !period.HasTimeSpan                          // We have an indefinite period, e.g. we are not periodic
              || appliedSpeedRatio > period.TimeSpan.Ticks)   // If the speed ratio is high enough the period will effectively be 0 
            {
                return false; 
            } 

            long periodInTicks = (long)((double)period.TimeSpan.Ticks / appliedSpeedRatio); 

            // PeriodInTicks may overflow if appliedSpeedRatio is sufficiently small;
            // In this case we will effectively have a single huge period, so nothing to detect here.
            if (periodInTicks <= 0) 
            {
                return false; 
            } 
            else  // Normal case, compare the period in which the first and last nodes fall
            { 
                long firstNodePeriod = (FirstNodeTime - beginTime).Ticks / periodInTicks;
                TimeSpan lastNodeTime = _nodeTime[_count - 1];
                long lastNodePeriod = (lastNodeTime - beginTime).Ticks / periodInTicks;
 
                return (firstNodePeriod != lastNodePeriod);
            } 
        } 

        ///  
        /// Used for projecting the end of a fill period.  When calling, we already know that we intersect the fill period
        /// but not the active period.
        /// 
        ///  
        /// Returns a collection which is the projection of the argument point onto the defined periodic function.
        ///  
        /// An empty output projection, passed by reference to allow TIC reuse. 
        /// Begin time of the periodic function.
        /// The end (expiration) time of the periodic function. 
        /// Length of a single iteration in the periodic collection.
        /// Ratio by which to scale down the periodic collection.
        /// Ratio of the length of the accelerating portion of the iteration.
        /// Ratio of the length of the decelerating portion of the iteration. 
        /// Indicates whether reversed arcs should follow after forward arcs.
        internal void ProjectPostFillZone(ref TimeIntervalCollection projection, 
                                          TimeSpan beginTime, TimeSpan endTime, Duration period, 
                                          double appliedSpeedRatio, double accelRatio, double decelRatio,
                                          bool isAutoReversed) 
        {
            Debug.Assert(projection.IsEmpty);  // Make sure the projection was properly cleared first
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled
            Debug.Assert(beginTime <= endTime);     // Ensure legitimate begin/end clipping parameters 

            Debug.Assert(!IsEmptyOfRealPoints);  // We assume this function is ONLY called when this collection overlaps the postfill zone.  So we cannot be empty. 
            Debug.Assert(!period.HasTimeSpan || period.TimeSpan > TimeSpan.Zero || beginTime == endTime);  // Check the consistency of degenerate case where simple duration is zero; expiration time should equal beginTime 
            Debug.Assert(!_nodeIsInterval[_count - 1]);  // We should not have an infinite domain set
 
            long outputInTicks;

            if (beginTime == endTime)  // Degenerate case when our active period is a single point; project only that point
            { 
                outputInTicks = 0;
            } 
            else  // The case of non-zero active duration 
            {
                outputInTicks = (long)(appliedSpeedRatio * (double)(endTime - beginTime).Ticks); 

                if (period.HasTimeSpan)  // Case of finite simple duration; in the infinite case we are already done
                {
                    long periodInTicks = period.TimeSpan.Ticks;  // Start by folding the point into its place inside a simple duration 

                    if (isAutoReversed) 
                    { 
                        long doublePeriod = periodInTicks << 1;  // Fast multiply by 2
                        outputInTicks = outputInTicks % doublePeriod; 

                        if (outputInTicks > periodInTicks)
                        {
                            outputInTicks = doublePeriod - outputInTicks; 
                        }
                    } 
                    else 
                    {
                        outputInTicks = outputInTicks % periodInTicks; 
                        if (outputInTicks == 0)
                        {
                            outputInTicks = periodInTicks;  // If we are at the end, stick to the max value
                        } 
                    }
 
                    if (accelRatio + decelRatio > 0)  // Now if we have acceleration, warp the point by the correct amount 
                    {
                        double dpPeriod = (double)periodInTicks; 
                        double inversePeriod = 1 / dpPeriod;
                        double halfMaxRate = 1 / (2 - accelRatio - decelRatio);  // Constants to simplify
                        double t;
 
                        long accelEnd = (long)(dpPeriod * accelRatio);
                        long decelStart = periodInTicks - (long)(dpPeriod * decelRatio); 
 
                        if (outputInTicks < accelEnd)  // We are in accel zone
                        { 
                            t = (double)outputInTicks;
                            outputInTicks = (long)(halfMaxRate * inversePeriod * t * t / accelRatio);
                        }
                        else if (outputInTicks <= decelStart)  // We are in the linear zone 
                        {
                            t = (double)outputInTicks; 
                            outputInTicks = (long)(halfMaxRate * (2 * t - accelRatio)); 
                        }
                        else  // We are in decel zone 
                        {
                            t = (double)(periodInTicks - outputInTicks);
                            outputInTicks = periodInTicks - (long)(halfMaxRate * inversePeriod * t * t / decelRatio);
                        } 
                    }
                } 
            } 

            projection.InitializePoint(TimeSpan.FromTicks(outputInTicks)); 
        }


        ///  
        /// Returns a collection which is the projection of this collection onto the defined periodic function.
        ///  
        ///  
        /// The object on which this method is called is a timeline's parent's collection of intervals.
        /// The periodic collection passed via parameters describes the active/fill periods of the timeline. 
        /// The output is the projection of (this) object using the parameter function of the timeline.
        ///
        /// We assume this function is ONLY called when this collection overlaps the active zone.
        /// 
        /// The periodic function maps values from domain to range within its activation period of [beginTime, endTime);
        /// in the fill period [endTime, endTime+fillDuration) everything maps to a constant post-fill value, and outside of 
        /// those periods every value maps to null. 
        ///
        /// The projection process can be described as three major steps: 
        ///
        /// (1) NORMALIZE this collection: offset the TIC's coordinates by BeginTime and scale by SpeedRatio.
        ///
        /// (2) FOLD this collection.  This means we convert from parent-time coordinate space into the space of 
        ///     a single simpleDuration for the child.  This is equivalent to "cutting up" the parent TIC into
        ///     equal-length segments (of length Period) and overlapping them -- taking their union.  This lets us 
        ///     know exactly which values inside the simpleDuration we have reached on the child.  In the case of 
        ///     autoreversed timelines, we do the folding similiar to folding a strip of paper -- alternating direction.
        /// 
        /// (3) WARP the resulting collection.  We now convert from simpleDuration domain coordinates into
        ///     coordinates in the range of the timeline function.  We do this by applying the "warping" effects of
        ///     acceleration, and deceleration.
        /// 
        /// In the special case of infinite simple duration, we essentially are done after performing NORMALIZE,
        /// because no periodicity or acceleration is present. 
        /// 
        /// In the ultimate degenerate case of zero duration, we terminate early and project the zero point.
        /// 
        /// 
        /// An empty output projection, passed by reference to allow TIC reuse.
        /// Begin time of the periodic function.
        /// The end (expiration) time of the periodic function.  Null indicates positive infinity. 
        /// The fill time appended at the end of the periodic function.  Zero indicates no fill period.  Forever indicates infinite fill period.
        /// Length of a single iteration in the periodic collection. 
        /// Ratio by which to scale down the periodic collection. 
        /// Ratio of the length of the accelerating portion of the iteration.
        /// Ratio of the length of the decelerating portion of the iteration. 
        /// Indicates whether reversed arcs should follow after forward arcs.
        internal void ProjectOntoPeriodicFunction(ref TimeIntervalCollection projection,
                                                  TimeSpan beginTime, Nullable endTime,
                                                  Duration fillDuration, Duration period, 
                                                  double appliedSpeedRatio, double accelRatio, double decelRatio,
                                                  bool isAutoReversed) 
        { 
            Debug.Assert(projection.IsEmpty);
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled 
            Debug.Assert(!endTime.HasValue || beginTime <= endTime);     // Ensure legitimate begin/end clipping parameters

            Debug.Assert(!IsEmptyOfRealPoints);  // We assume this function is ONLY called when this collection overlaps the active zone.  So we cannot be empty.
            Debug.Assert(!endTime.HasValue || endTime >= _nodeTime[0]);  // EndTime must come at or after our first node (it can be infinite) 
            Debug.Assert(_nodeTime[_count - 1] >= beginTime);  // Our last node must come at least at begin time (since we must intersect the active period)
            Debug.Assert(endTime.HasValue || fillDuration == TimeSpan.Zero);   // Either endTime is finite, or it's infinite hence we cannot have any fill zone 
            Debug.Assert(!period.HasTimeSpan || period.TimeSpan > TimeSpan.Zero || (endTime.HasValue && beginTime == endTime));  // Check the consistency of degenerate case where simple duration is zero; expiration time should equal beginTime 
            Debug.Assert(!_nodeIsInterval[_count - 1]);  // We should not have an infinite domain set
 
            // We initially project all intervals into a single period of the timeline, creating a union of the projected segments.
            // Then we warp the time coordinates of the resulting TIC from domain to range, applying the effects of speed/accel/decel

            bool nullPoint = _containsNullPoint  // Start by projecting the null point directly, then check whether we fall anywhere outside of the active and fill period 

             || _nodeTime[0] < beginTime  // If we intersect space before beginTime, or... 
 
              || (endTime.HasValue && fillDuration.HasTimeSpan  // ...the active and fill periods don't stretch forever, and...
               && (_nodeTime[_count - 1] > endTime.Value + fillDuration.TimeSpan  // ...we intersect space after endTime+fill, or... 
                || (_nodeTime[_count - 1] == endTime.Value + fillDuration.TimeSpan  // ...as we fall right onto the end of fill zone...
                 && _nodeIsPoint[_count - 1] && (endTime > beginTime || fillDuration.TimeSpan > TimeSpan.Zero))));  // ...we may have a point intersection with the stopped zone

            // Now consider the main scenarios: 

            if (endTime.HasValue && beginTime == endTime)  // Degenerate case when our active period is a single point; project only the point 
            { 
                projection.InitializePoint(TimeSpan.Zero);
            } 
            else  // The case of non-zero active duration
            {
                bool includeFillPeriod = !fillDuration.HasTimeSpan || fillDuration.TimeSpan > TimeSpan.Zero;  // This variable represents whether we have a non-zero fill zone
 
                if (period.HasTimeSpan)  // We have a finite TimeSpan period and non-zero activation duration
                { 
                    TimeIntervalCollection tempCollection = new TimeIntervalCollection(); 

                    ProjectionNormalize(ref tempCollection, beginTime, endTime, includeFillPeriod, appliedSpeedRatio); 

                    long periodInTicks = period.TimeSpan.Ticks;
                    Nullable activeDuration;
                    bool includeMaxPoint; 

                    if (endTime.HasValue) 
                    { 
                        activeDuration = endTime.Value - beginTime;
                        includeMaxPoint = includeFillPeriod && (activeDuration.Value.Ticks % periodInTicks == 0);  // Fill starts at a boundary 
                    }
                    else
                    {
                        activeDuration = null; 
                        includeMaxPoint = false;
                    } 
 
                    projection.EnsureAllocatedCapacity(_minimumCapacity);
                    tempCollection.ProjectionFold(ref projection, activeDuration, periodInTicks, isAutoReversed, includeMaxPoint); 

                    if (accelRatio + decelRatio > 0)
                    {
                        projection.ProjectionWarp(periodInTicks, accelRatio, decelRatio); 
                    }
                } 
                else  // Infinite period degenerate case; we perform straight 1-1 linear mapping, offset by begin time and clipped 
                {
                    ProjectionNormalize(ref projection, beginTime, endTime, includeFillPeriod, appliedSpeedRatio); 
                }
            }

            projection._containsNullPoint = nullPoint;  // Ensure we have the null point properly set 
        }
 
        ///  
        /// Performs the NORMALIZE operation, as described in the comments to the general projection function.
        /// Clip begin and end times, normalize by beginTime, scale by speedRatio. 
        /// 
        /// The normalized collection to create.
        /// Begin time of the active period for clipping.
        /// End time of the active period for clipping. 
        /// The ratio by which to scale begin and end time.
        /// Whether a non-zero fill period exists. 
        private void ProjectionNormalize(ref TimeIntervalCollection projection, 
                                         TimeSpan beginTime, Nullable endTime, bool includeFillPeriod, double speedRatio)
        { 
            Debug.Assert(!IsEmptyOfRealPoints);
            Debug.Assert(projection.IsEmpty);

            projection.EnsureAllocatedCapacity(this._nodeTime.Length); 

            this.MoveFirst(); 
            projection.MoveFirst(); 

            // Get to the non-clipped zone; we must overlap the active zone, so we should terminate at some point. 
            while (!CurrentIsAtLastNode && NextNodeTime <= beginTime)
            {
                MoveNext();
            } 

            if (CurrentNodeTime < beginTime)  // This means we have an interval clipped by beginTime 
            { 
                if (CurrentNodeIsInterval)
                { 
                    projection._count++;
                    projection.CurrentNodeTime = TimeSpan.Zero;
                    projection.CurrentNodeIsPoint = true;
                    projection.CurrentNodeIsInterval = true; 
                    projection.MoveNext();
                } 
                this.MoveNext(); 
            }
 
            while(_current < _count && (!endTime.HasValue || CurrentNodeTime < endTime))  // Copy the main set of segments, transforming them
            {
                double timeOffset = (double)((this.CurrentNodeTime - beginTime).Ticks);
 
                projection._count++;
                projection.CurrentNodeTime = TimeSpan.FromTicks((long)(speedRatio * timeOffset)); 
                projection.CurrentNodeIsPoint = this.CurrentNodeIsPoint; 
                projection.CurrentNodeIsInterval = this.CurrentNodeIsInterval;
 
                projection.MoveNext();
                this.MoveNext();
            }
 
            Debug.Assert(_current > 0);  // The only way _current could stay at zero is if the collection begins at (or past) the end of active period
            if (_current < _count  // We have an interval reaching beyond the active zone, clip that interval 
             && (_nodeIsInterval[_current - 1] 
              || (CurrentNodeTime == endTime.Value && CurrentNodeIsPoint && includeFillPeriod)))
            { 
                Debug.Assert(endTime.HasValue && CurrentNodeTime >= endTime.Value);

                double timeOffset = (double)((endTime.Value - beginTime).Ticks);
 
                projection._count++;
                projection.CurrentNodeTime = TimeSpan.FromTicks((long)(speedRatio * timeOffset)); 
                projection.CurrentNodeIsPoint = includeFillPeriod && (CurrentNodeTime > endTime.Value || CurrentNodeIsPoint); 
                projection.CurrentNodeIsInterval = false;
            } 
        }

        /// 
        /// Performs the FOLD operation, as described in the comments to the general projection function. 
        /// We assume this method is only called with a finite, non-zero period length.
        /// The TIC is normalized so beginTime = 0. 
        /// NOTE: projection should have allocated arrays. 
        /// 
        /// The output projection. 
        /// The duration of the active period.
        /// The length of a simple duration in ticks.
        /// Whether we have auto-reversing.
        /// Whether the fill zone forces the max point to be included. 
        private void ProjectionFold(ref TimeIntervalCollection projection, Nullable activeDuration,
                                    long periodInTicks, bool isAutoReversed, bool includeMaxPoint) 
        { 
            Debug.Assert(!IsEmptyOfRealPoints);  // The entire projection process assumes we are not empty (have an intersection with the active zone).
            Debug.Assert(periodInTicks > 0);  // We do not handle the degenerate case here. 

            // Find the smallest n such that _nodeTime[n+1] > beginTime; if n is the last index, then consider _nodeTime[n+1] to be infinity
            MoveFirst();
            Debug.Assert(CurrentNodeTime >= TimeSpan.Zero);  // Verify that we are already clipped 

            bool quitFlag = false; 
 
            // As we walk, we maintain the invarant that the interval BEFORE _current is not included.
            // Otherwise we handle the interval and skip the interval's last node. 

            // Process the remaining points and segments
            do
            { 
                if (CurrentNodeIsInterval)  // Project the interval starting here
                { 
                    quitFlag = ProjectionFoldInterval(ref projection, activeDuration, periodInTicks, isAutoReversed, includeMaxPoint);  // Project and break up the clipped segment 
                    _current += NextNodeIsInterval ? 1 : 2;  // Step over the next node if it's merely the end of this interval
                } 
                else  // This must be a lone point; the previous interval is no included by our invariant
                {
                    Debug.Assert(CurrentNodeIsPoint);
                    ProjectionFoldPoint(ref projection, activeDuration, periodInTicks, isAutoReversed, includeMaxPoint); 
                    _current++;
                } 
 
            } while (!quitFlag && (_current < _count));
            // While we haven't run out of indices, and haven't moved past endTime 
        }

        /// 
        /// Take a single projection point and insert into the output collection. 
        /// NOTE: projection should have allocated arrays.
        ///  
        /// The output collection. 
        /// The duration of the active period.
        /// The length of a simple duration in ticks. 
        /// Whether autoreversing is enabled
        /// Whether the fill zone forces the max point to be included.
        private void ProjectionFoldPoint(ref TimeIntervalCollection projection, Nullable activeDuration,
                                         long periodInTicks, bool isAutoReversed, bool includeMaxPoint) 
        {
            Debug.Assert(CurrentNodeIsPoint);  // We should only call this method when we project a legitimate point 
            Debug.Assert(!CurrentNodeIsInterval); 

            long currentProjection; 
            if (isAutoReversed)  // Take autoreversing into account
            {
                long doublePeriod = periodInTicks << 1;
                currentProjection = CurrentNodeTime.Ticks % doublePeriod; 

                if (currentProjection > periodInTicks) 
                { 
                    currentProjection = doublePeriod - currentProjection;
                } 
            }
            else  // No autoReversing
            {
                if (includeMaxPoint && activeDuration.HasValue && CurrentNodeTime == activeDuration) 
                {
                    currentProjection = periodInTicks;  // Exceptional end case: we are exactly at the last point 
                } 
                else
                { 
                    currentProjection = CurrentNodeTime.Ticks % periodInTicks;
                }
            }
 
            projection.MergePoint(TimeSpan.FromTicks(currentProjection));
        } 
 
        /// 
        /// Take a single projection segment [CurrentNodeTime, NextNodeTime], break it into parts and merge the 
        /// folded parts into this collection.
        /// NOTE: the TIC is normalized so beginTime = TimeSpan.Zero and we are already clipped.
        /// NOTE: projection should have allocated arrays.
        ///  
        /// The output projection.
        /// The duration of the active period. 
        /// The length of a simple duration in ticks. 
        /// Whether autoreversing is enabled
        /// Whether the fill zone forces the max point to be included. 
        private bool ProjectionFoldInterval(ref TimeIntervalCollection projection, Nullable activeDuration,
                                            long periodInTicks, bool isAutoReversed, bool includeMaxPoint)
        {
            // Project the begin point for the segment, then look if we are autoreversing or not. 
            long intervalLength = (NextNodeTime - CurrentNodeTime).Ticks;
            long timeBeforeNextPeriod, currentProjection; 
 
            // Now see how the segment falls across periodic boundaries:
            // Case 1: segment stretches across a full period (we can exit early, since we cover the entire range of values) 
            // Case 2: NON-AUTEREVERSED: segment stretches across two partial periods (we need to split into two segments and insert them into the projection)
            // Case 2: AUTOREVERSED: we need to pick the larger half of the partial period and project only that half, since it fully overlaps the other.
            // Case 3: segment is fully contained within a single period (just add the segment into the projection)
            // These cases are handled very differently for AutoReversing and non-AutoReversing timelines. 

            if (isAutoReversed)  // In the autoreversed case, we "fold" the segment onto itself and eliminate the redundant parts 
            { 
                bool beginOnReversingArc;
                long doublePeriod = periodInTicks << 1; 
                currentProjection = CurrentNodeTime.Ticks % doublePeriod;

                if (currentProjection < periodInTicks)  // We are on a forward-moving segment
                { 
                    beginOnReversingArc = false;
                    timeBeforeNextPeriod = periodInTicks - currentProjection; 
                } 
                else  // We are on a reversing segment, adjust the values accordingly
                { 
                    beginOnReversingArc = true;
                    currentProjection = doublePeriod - currentProjection;
                    timeBeforeNextPeriod = currentProjection;
                } 

                Debug.Assert(timeBeforeNextPeriod > 0); 
 
                long timeAfterNextPeriod = intervalLength - timeBeforeNextPeriod;  // How much of our interval protrudes into the next period(s); this may be negative if we don't reach it.
                // See which part of the segment -- before or after part -- "dominates" when we fold them unto each other. 
                if (timeAfterNextPeriod > 0)  // Case 1 or 2: we reach into the next period but don't know if we completely cover it
                {
                    bool collectionIsSaturated;
 
                    if (timeBeforeNextPeriod >= timeAfterNextPeriod)  // Before "dominates"
                    { 
                        bool includeTime = CurrentNodeIsPoint; 

                        if (timeBeforeNextPeriod == timeAfterNextPeriod)  // Corner case where before and after overlap exactly, find the IsPoint union 
                        {
                            includeTime = includeTime || NextNodeIsPoint;
                        }
 
                        if (beginOnReversingArc)
                        { 
                            projection.MergeInterval(TimeSpan.Zero,                         true, 
                                                     TimeSpan.FromTicks(currentProjection), includeTime);
                            collectionIsSaturated = includeTime && (currentProjection == periodInTicks); 
                        }
                        else
                        {
                            projection.MergeInterval(TimeSpan.FromTicks(currentProjection), includeTime, 
                                                     TimeSpan.FromTicks(periodInTicks),     true);
                            collectionIsSaturated = includeTime && (currentProjection == 0); 
                        } 
                    }
                    else  // After "dominates" 
                    {
                        if (beginOnReversingArc)
                        {
                            long clippedTime = timeAfterNextPeriod < periodInTicks ? timeAfterNextPeriod : periodInTicks; 

                            projection.MergeInterval(TimeSpan.Zero,                   true, 
                                                     TimeSpan.FromTicks(clippedTime), NextNodeIsPoint); 
                            collectionIsSaturated = NextNodeIsPoint && (clippedTime == periodInTicks);
                        } 
                        else
                        {
                            long clippedTime = timeAfterNextPeriod < periodInTicks ? periodInTicks - timeAfterNextPeriod : 0;
 
                            projection.MergeInterval(TimeSpan.FromTicks(clippedTime),   NextNodeIsPoint,
                                                     TimeSpan.FromTicks(periodInTicks), true); 
                            collectionIsSaturated = NextNodeIsPoint && (clippedTime == 0); 
                        }
                    } 
                    return collectionIsSaturated;  // See if we just saturated the collection
                }
                else  // Case 3: timeAfterNextPeriod < 0, we are fully contained in the current period
                { 
                    // No need to split anything, insert the interval directly
                    if (beginOnReversingArc)  // Here the nodes are reversed 
                    { 
                        projection.MergeInterval(TimeSpan.FromTicks(currentProjection - intervalLength), NextNodeIsPoint,
                                                 TimeSpan.FromTicks(currentProjection),                  CurrentNodeIsPoint); 
                    }
                    else
                    {
                        projection.MergeInterval(TimeSpan.FromTicks(currentProjection),                  CurrentNodeIsPoint, 
                                                 TimeSpan.FromTicks(currentProjection + intervalLength), NextNodeIsPoint);
                    } 
                    return false;  // Keep computing the projection 
                }
            } 
            else  // No AutoReversing
            {
                currentProjection = CurrentNodeTime.Ticks % periodInTicks;
                timeBeforeNextPeriod = periodInTicks - currentProjection; 

                // The only way to get 0 is if we clipped by endTime which equals CurrentNodeTime, which should not have been allowed 
                Debug.Assert(intervalLength > 0); 

                if (intervalLength > periodInTicks)  // Case 1. We may stretch across a whole arc, even if we start from the end and wrap back around 
                {
                    // Quickly transform the collection into a saturated collection
                    projection._nodeTime[0] = TimeSpan.Zero;
                    projection._nodeIsPoint[0] = true; 
                    projection._nodeIsInterval[0] = true;
 
                    projection._nodeTime[1] = TimeSpan.FromTicks(periodInTicks); 
                    projection._nodeIsPoint[1] = includeMaxPoint;
                    projection._nodeIsInterval[1] = false; 

                    _count = 2;
                    return true;  // Bail early, we have the result ready
                } 
                else if (intervalLength >= timeBeforeNextPeriod)  // Case 2. We stretch until the next period begins (but not long enough to cover the length of a full period)
                { 
                    // Split the segment into two projected segments by wrapping around the period boundary 
                    projection.MergeInterval(TimeSpan.FromTicks(currentProjection),                     CurrentNodeIsPoint,
                                             TimeSpan.FromTicks(periodInTicks),                         false); 
                    if (intervalLength > timeBeforeNextPeriod)  // See if we have a legitimate interval in the second clipped part
                    {
                        projection.MergeInterval(TimeSpan.Zero,                                             true,
                                                 TimeSpan.FromTicks(intervalLength - timeBeforeNextPeriod), NextNodeIsPoint); 
                    }
                    else if (NextNodeIsPoint)  // We only seem to have a point, wrapped around at zero (or in the exceptional case, at the max) 
                    { 
                        if (includeMaxPoint && activeDuration.HasValue && NextNodeTime == activeDuration)  // Exceptional end case: we are exactly at the last point
                        { 
                            projection.MergePoint(TimeSpan.FromTicks(periodInTicks));
                        }
                        else
                        { 
                            projection.MergePoint(TimeSpan.Zero);
                        } 
                    } 
                    return false;  // Keep computing the projection
                } 
                else  // Case 3: We fall within a single period
                {
                    // No need to split anything, insert the interval directly
                    projection.MergeInterval(TimeSpan.FromTicks(currentProjection),                    CurrentNodeIsPoint, 
                                             TimeSpan.FromTicks(currentProjection + intervalLength),   NextNodeIsPoint);
                    return false;  // Keep computing the projection 
                } 
            }
        } 

        /// 
        /// Merges a point into this collection so it becomes the union of itself and the point.
        /// Consequentialy, this does nothing if the point is already a subset of the collection; 
        /// Otherwise adjusts the collection so that the result obeys the rules of a proper TIC.
        /// NOTE: _current will shift so as to be the same distance from the end as before. 
        ///  
        /// The point to merge.
        private void MergePoint(TimeSpan point) 
        {
            int index = Locate(point);

            if (index >= 0 && _nodeTime[index] == point)  // Point coincides with an existing node 
            {
                if(!_nodeIsPoint[index])  // The node is not already in the TIC 
                { 
                    // See if we need to insert the node, or cancel out the node when it "saturates" an interval-point-interval segment
                    if (index == 0 || !_nodeIsInterval[index - 1] || !_nodeIsInterval[index]) 
                    {
                        _nodeIsPoint[index] = true;
                    }
                    else  // Else we should cancel the node as it is redundant (===O=== saturated case) 
                    {
                        for (int n = index; n + 1 < _count; n++)  // Shift over the contents 
                        { 
                            _nodeTime[n]       = _nodeTime[n + 1];
                            _nodeIsPoint[n]    = _nodeIsPoint[n + 1]; 
                            _nodeIsInterval[n] = _nodeIsInterval[n + 1];
                        }
                        _count--;
                    } 
                }
            } 
            else if (index == -1 || !_nodeIsInterval[index])  // Point falls within the interior of a non-included interval 
            {
                Debug.Assert(index == -1 || _nodeTime[index] < point); 

                // Then we need to insert a point into the collection
                EnsureAllocatedCapacity(_count + 1);
 
                for (int n = _count - 1; n > index; n--)  // Shift over the contents
                { 
                    _nodeTime[n + 1]       = _nodeTime[n]; 
                    _nodeIsPoint[n + 1]    = _nodeIsPoint[n];
                    _nodeIsInterval[n + 1] = _nodeIsInterval[n]; 
                }
                _nodeTime[index + 1]       = point;  // Insert the node
                _nodeIsPoint[index + 1]    = true;
                _nodeIsInterval[index + 1] = false; 

                _count++; 
            } 
        }
 
        /// 
        /// Merges an interval into this collection so it becomes the union of itself and the interval.
        /// Consequentialy, this does nothing if the interval is already a subset of the collection;
        /// Otherwise adjusts the collection so that the result obeys the rules of a proper TIC. 
        /// 
        /// Start of the interval. 
        /// Whether the start point is included. 
        /// End of the interval.
        /// Whether the end point is included. 
        private void MergeInterval(TimeSpan from, bool includeFrom,
                                   TimeSpan to,   bool includeTo)
        {
            Debug.Assert(from < to);  // Our code should never call MergeInterval for a point or reversed interval 

            if (IsEmptyOfRealPoints)  // We have no points yet, simply create a new collection with those points 
            { 
                _nodeTime[0] = from;
                _nodeIsPoint[0] = includeFrom; 
                _nodeIsInterval[0] = true;

                _nodeTime[1] = to;
                _nodeIsPoint[1] = includeTo; 
                _nodeIsInterval[1] = false;
 
                _count = 2; 
            }
            else  // We are not empty, hence there must be existing intervals allocated and assigned 
            {
                Debug.Assert(_nodeTime.Length >= _minimumCapacity);  // Assert that we indeed have memory allocated

                int fromIndex = Locate(from);  // Find the nearest nodes to the left of from and to (possibly equal) 
                int toIndex   = Locate(to);
 
                // From a structural standpoint, we do the following: 
                //  before  ----o---o----?----o---o---?----o----  (? means there may or may not be a node here)
                //                       F            T 
                //  after   ----o---o----?------------?----o----  (? means the node may be added, kept, or removed here)

                // The array reshuffling takes place as following:
                // 1) Check if more memory is needed, then dynamically resize and move the contents to new arrays 
                // 2) Perform in-place blitting depending whether we contract or expand the array
 
                bool insertNodeAtFrom = false; 
                bool insertNodeAtTo   = false;
 
                int netIncreaseInNodes = fromIndex - toIndex;  // The default is we remove all the "intermediate" nodes
                int nextInsertionIndex = fromIndex + 1;  // Place to begin inserting new nodes if needed; by default start from [fromIndex+1]
                int lastNodeToDelete   = toIndex;  // By default, delete nodes up through [toIndex]
 
                // If FROM falls within an interval, and we don't have IntervalIncluded, create a node here.
                //   Otherwise don't create that node. 
                // Else FROM coincides with a node; if we have PreviousIntervalIncluded && (CoincidingNode||includeStart), cancel the saturated node. 
                //   Otherwise keep that node.
 
                if (fromIndex == -1 || _nodeTime[fromIndex] < from)  // We don't fall exactly onto a preexisting node
                {
                    // Keep the node at fromIndex; see if we need to insert a new node
 
                    if (fromIndex == -1 || !_nodeIsInterval[fromIndex])
                    { 
                        insertNodeAtFrom = true; 
                        netIncreaseInNodes++;  // We previously assumed we don't insert any new nodes
                    } 
                }
                else  // We fall exactly onto a preexisting node; in this case, it is redundant to insert another node here.
                {
                    Debug.Assert(_nodeTime[fromIndex] == from); 

                    if (fromIndex > 0 && _nodeIsInterval[fromIndex - 1]  // Delete the node at fromIndex, it will become saturated 
                      && (includeFrom || _nodeIsPoint[fromIndex])) 
                    {
                        netIncreaseInNodes--;  // We previously assumed that we would NOT delete the node at fromIndex 
                        nextInsertionIndex--;
                    }
                    else  // Keep the node at fromIndex
                    { 
                        _nodeIsPoint[fromIndex] = includeFrom || _nodeIsPoint[fromIndex];  // Update the node's IsPoint status
                    } 
                } 

                // If TO falls within an interval, and we don't have IntervalIncluded, create a node here. 
                //   Otherwise don't create that node.
                // Else TO coincides with a node; if we have (IncludeCoincidingNode||includeEnd) && IntervalIncluded, allow the node to be deleted
                //   Otherwise arrange to keep that node (this is not what we do by default).
                if (toIndex == -1 || _nodeTime[toIndex] < to)  // We don't fall exactly onto a preexisting node 
                {
                    // The previous node is strictly smaller, so it is redundant and we allow it to be deleted. 
                    // We don't decrement netIncreaseInNodes here because we assumed that we delete the node at toIndex 

                    if (toIndex == -1 || !_nodeIsInterval[toIndex])  // If we aren't inside an included interval, insert a node 
                    {
                        insertNodeAtTo = true;
                        netIncreaseInNodes++;  // We previously assumed we don't insert any new nodes
                    } 
                }
                else  // We fall exactly onto a preexisting node; in this case, it is redundant to insert another node here. 
                { 
                    Debug.Assert(_nodeTime[toIndex] == to);
                    Debug.Assert(fromIndex < toIndex); 

                    // The default is we delete the node at toIndex, unless it does not saturate the resulting TIC.

                    if (!_nodeIsInterval[toIndex] || (!includeTo && !_nodeIsPoint[toIndex])) // Keep the node at toIndex, it is not going to be saturated 
                    {
                        // We previously assumed that we WOULD delete the node at toIndex, now it turns out we should keep it 
                        netIncreaseInNodes++; 
                        lastNodeToDelete--;
 
                        _nodeIsPoint[toIndex] = includeTo || _nodeIsPoint[toIndex];  // Update the node's IsPoint status
                    }
                }
 
                // Eliminate all nodes with index FROM <= index <= TOINDEX, observing deletion rules:
                // 
                //        Index:   fromIndex==toIndex 
                // ShouldDelete:       no(default)
                // 
                //        Index:    fromIndex      toIndex
                // ShouldDelete:   no(default)   yes(default)
                //
                //        Index:    fromIndex    a    b    c     toIndex 
                // ShouldDelete:   no(default)  yes  yes  yes  yes(default)
                // 
 
                // The effect of the move on the array is that we make the transition:
                //   AAA[DDDD]BBB  -->  AAA[II]BBB 
                // Where we can have any number of D's (deleted nodes) and from 0 to 2 I's (inserted nodes).
                // What we need to find is how many A's and B's we have, and which way to shift them.

                Debug.Assert(_count + netIncreaseInNodes >= 2);  // We should never shrink past size 2 

                if (netIncreaseInNodes > 0)  // We need to grow the array 
                { 
                    EnsureAllocatedCapacity(_count + netIncreaseInNodes);  // Make sure we have enough space allocated
                    for (int n = _count - 1; n > lastNodeToDelete; n--) 
                    {
                        _nodeTime[n + netIncreaseInNodes]       = _nodeTime[n];
                        _nodeIsPoint[n + netIncreaseInNodes]    = _nodeIsPoint[n];
                        _nodeIsInterval[n + netIncreaseInNodes] = _nodeIsInterval[n]; 
                    }
                } 
                else if (netIncreaseInNodes < 0)  // We need to shrink the array 
                {
                    // Copy the elements 
                    for (int n = lastNodeToDelete + 1; n < _count; n++)
                    {
                        _nodeTime[n + netIncreaseInNodes]       = _nodeTime[n];  // Note that netIncreaseInNodes is negative here
                        _nodeIsPoint[n + netIncreaseInNodes]    = _nodeIsPoint[n]; 
                        _nodeIsInterval[n + netIncreaseInNodes] = _nodeIsInterval[n];
                    } 
                } 

                _count += netIncreaseInNodes;  // Update the array size 

                if (insertNodeAtFrom)
                {
                    _nodeTime[nextInsertionIndex]       = from; 
                    _nodeIsPoint[nextInsertionIndex]    = includeFrom;
                    _nodeIsInterval[nextInsertionIndex] = true;  // We are inserting an interval, so this is true 
 
                    nextInsertionIndex++;
                } 

                if (insertNodeAtTo)
                {
                    _nodeTime[nextInsertionIndex]       = to; 
                    _nodeIsPoint[nextInsertionIndex]    = includeTo;
                    _nodeIsInterval[nextInsertionIndex] = false;  // We are terminating an interval, so this is false 
                } 
            }
        } 


        private void EnsureAllocatedCapacity(int requiredCapacity)
        { 
            if (_nodeTime == null)
            { 
                Debug.Assert(_nodeIsPoint == null); 
                Debug.Assert(_nodeIsInterval == null);
 
                _nodeTime = new TimeSpan[requiredCapacity];
                _nodeIsPoint = new bool[requiredCapacity];
                _nodeIsInterval = new bool[requiredCapacity];
            } 
            else if (_nodeTime.Length < requiredCapacity)  // We may need to grow by up to 2 units
            { 
                Debug.Assert(_nodeIsPoint != null); 
                Debug.Assert(_nodeIsInterval != null);
 
                int newCapacity = _nodeTime.Length << 1;  // Dynamically grow by a factor of 2

                TimeSpan[] newNodeTime   = new TimeSpan[newCapacity];
                bool[] newNodeIsPoint    = new bool[newCapacity]; 
                bool[] newNodeIsInterval = new bool[newCapacity];
 
                for (int n = 0; n < _count; n++) 
                {
                    newNodeTime[n]       = _nodeTime[n]; 
                    newNodeIsPoint[n]    = _nodeIsPoint[n];
                    newNodeIsInterval[n] = _nodeIsInterval[n];
                }
 
                _nodeTime       = newNodeTime;
                _nodeIsPoint    = newNodeIsPoint; 
                _nodeIsInterval = newNodeIsInterval; 
            }
        } 


        /// 
        /// Apply the effects of Accel, Decel to the nodes in this TIC. 
        /// This should ONLY get called when the period in finite and non-zero, and accel+decel > 0.
        ///  
        /// The length of a simple duration in ticks. 
        /// The accelerating fraction of the simple duration.
        /// The decelerating fraction of the simple duration. 
        private void ProjectionWarp(long periodInTicks, double accelRatio, double decelRatio)
        {
            Debug.Assert(periodInTicks > 0);
            Debug.Assert(accelRatio + decelRatio > 0); 

            double dpPeriod = (double)periodInTicks; 
            double inversePeriod = 1 / dpPeriod; 
            double halfMaxRate = 1 / (2 - accelRatio - decelRatio);  // Constants to simplify
 
            TimeSpan accelEnd = TimeSpan.FromTicks((long)(dpPeriod * accelRatio));
            TimeSpan decelStart = TimeSpan.FromTicks(periodInTicks - (long)(dpPeriod * decelRatio));

            double t;  // Current progress, which ranges from 0 to 1 

            MoveFirst(); 
 
            // Perform accel warping
            while (_current < _count && CurrentNodeTime < accelEnd) 
            {
                t = (double)_nodeTime[_current].Ticks;
                _nodeTime[_current] = TimeSpan.FromTicks((long)(halfMaxRate * inversePeriod * t * t / accelRatio));
                MoveNext(); 
            }
 
            // Perform linear zone warping 
            while (_current < _count && CurrentNodeTime <= decelStart)  // We bias the edge points towards the simpler linear computation, which yields the same result
            { 
                t = (double)_nodeTime[_current].Ticks;
                _nodeTime[_current] = TimeSpan.FromTicks((long)(halfMaxRate * (2 * t - (accelRatio * dpPeriod))));
                MoveNext();
            } 

            // Perform decel warping 
            while (_current < _count) 
            {
                t = (double)(periodInTicks - _nodeTime[_current].Ticks);  // We actually use the complement from 100% progress 
                _nodeTime[_current] = TimeSpan.FromTicks(periodInTicks - (long)(halfMaxRate * inversePeriod * t * t / decelRatio));
                MoveNext();
            }
        } 

#if TEST_TIMING_CODE 
        ///  
        /// Creates several collections and runs test operations on them
        ///  
        static internal void RunDiagnostics()
        {
            TimeIntervalCollection t = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.85));
            TimeIntervalCollection t2; 

            // Case 1      --x--*----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.70)); 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t)); 
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.70)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            // Empty
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0, 0, false)); 
            // Accel only
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.3, 0, false));
            // Decel only
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0),
                                                         TimeSpan.FromSeconds(1.0), 1, 0, 0.3, false)); 
            // Accel+decel
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.1, 0.3, false)); 
            // Accel+decel+autoreverse (boundary case 1)
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.3, 0.1, true));
            // Accel+decel+autoreverse (boundary case 2)
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0),
                                                         TimeSpan.FromSeconds(1.0), 1, 0.301, 0.1, true)); 
            // Accel+decel+autoreverse disabled for check
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.3, 0.1, false)); 
            // Insufficient decel to provoke intersection
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.1, 0.2, false));
            // Autoreverse-only
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(1.7),
                                                         TimeSpan.FromSeconds(1.0), 1, 0, 0, true)); 
            // Large decel zone
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.1, 0.5, false)); 

            // Case 2      -----x----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.85));
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t.Contains(TimeSpan.FromSeconds(3.85))); 
            Debug.Assert(!t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 
 
            // Case 3      -----*--x--
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.95)); 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            t.Clear(); 

            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.70)));  // No intersection with empty set 
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.85)));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.95)));

            t = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)); 

            // Case 1      --x--*=====.----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.7)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.70)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 2      -----x=====.----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.85)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t.Contains(TimeSpan.FromSeconds(3.85)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 

            // Case 3      -----*==x==.----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.90)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t.Contains(TimeSpan.FromSeconds(3.90)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 

            // Case 4      -----*=====x----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.95)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 5      -----*=====.--x-- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(4.00)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(4.00)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            //// Case 1      --x--*=====.-----    (x is the starting point for t2) 
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.75));
 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.85)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.90)); 
 
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.95));
 
            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(!t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(4.0)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(!t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));

            //// Case 2      -----x=====.-----    (x is the starting point for t2)
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.90));
 
            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(!t.IntersectsInverseOf(t2)); 
            Debug.Assert(!t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(4.0));
 
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(!t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 3      -----*==x==.-----    (x is the starting point for t2)

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.87), TimeSpan.FromSeconds(3.90)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(!t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.87), TimeSpan.FromSeconds(3.95));
 
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.87), TimeSpan.FromSeconds(4.0));

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            // Case 4      -----*=====x-----    (x is the starting point for t2)

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.95), TimeSpan.FromSeconds(4.0));
 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t)); 
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 5      -----*=====.--x--    (x is the starting point for t2)

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.98), TimeSpan.FromSeconds(4.0)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t)); 
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));

            // Merge testing
            t = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3), TimeSpan.FromSeconds(5.5)); 
            t.MergePoint(TimeSpan.FromSeconds(8));
            t.MergePoint(TimeSpan.FromSeconds(12)); 
            t.MergeInterval(TimeSpan.FromSeconds(14.5), true, TimeSpan.FromSeconds(19), true); 

            //t2 = t.ProjectOntoPeriodicFunction(beginTime, endTime, 
            //                                   fillDuration, period,
            //                                   appliedSpeedRatio, accelRatio, decelRatio, isAutoReversed);
            t2.Clear();
            t.ProjectOntoPeriodicFunction(ref t2, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4), 
                                               Duration.Forever, Duration.Forever,
                                               1, 0, 0, false); 
            t2.Clear(); 
            t.ProjectOntoPeriodicFunction(ref t2, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4),
                                               Duration.Forever, TimeSpan.FromSeconds(10), 
                                               1, 0, 0, false);
            t2.Clear();
            t.ProjectOntoPeriodicFunction(ref t2, TimeSpan.FromSeconds(0), TimeSpan.FromSeconds(17),
                                               Duration.Forever, TimeSpan.FromSeconds(4), 
                                               1, 0, 0, true);
        } 
#endif 

 
        #endregion // Methods
        #endregion // External interface

        #region Private 

        ///  
        /// Sets _current to the largest index N where nodeTime[N] is less or equal to time. 
        /// Returns -1 if no such index N exists.
        ///  
        /// 
        /// Uses a binary search to curb worst-case time to log2(_count)
        /// 
        private int Locate(TimeSpan time) 
        {
            if (_count == 0 || time < _nodeTime[0]) 
            { 
                return -1;
            } 
            else  // time is at least at the first node
            {
                Debug.Assert(_count > 0);  // Count cannot be negative
 
                int current;
                int left = 0; 
                int right = _count - 1; 

                // Maintain invariant: T[left] < time < T[right] 
                while (left + 1 < right)  // Compute until we have at most 1-unit long interval
                {
                    current = (left + right) >> 1;  // Fast divide by 2
                    if (time < _nodeTime[current]) 
                    {
                        right = current; 
                    } 
                    else  // time >= nodeTime[current]
                    { 
                        left = current;
                    }
                }
 
                if (time < _nodeTime[right])
                { 
                    return left; 
                }
                else  // This case should only be reached when we are at or past the last node 
                {
                    Debug.Assert(right == _count - 1);
                    return right;
                } 
            }
        } 
 
        internal bool IsEmptyOfRealPoints
        { 
            get
            {
                return (_count == 0);
            } 
        }
 
        internal bool IsEmpty 
        {
            get 
            {
                return (_count == 0 && !_containsNullPoint);
            }
        } 

        private void MoveFirst() 
        { 
            _current = 0;
        } 

        private void MoveNext()
        {
            _current++; 
            Debug.Assert(_current <= _count);
        } 
 
        private bool CurrentIsAtLastNode
        { 
            get
            {
                return (_current + 1 == _count);
            } 
        }
 
        private TimeSpan CurrentNodeTime 
        {
            get 
            {
                Debug.Assert(_current < _count);
                return _nodeTime[_current];
            } 
            set
            { 
                Debug.Assert(_current < _count); 
                _nodeTime[_current] = value;
            } 
        }

        private bool CurrentNodeIsPoint
        { 
            get
            { 
                Debug.Assert(_current < _count); 
                return _nodeIsPoint[_current] ^ _invertCollection;
            } 
            set
            {
                Debug.Assert(_current < _count);
                _nodeIsPoint[_current] = value; 
            }
        } 
 
        private bool CurrentNodeIsInterval
        { 
            get
            {
                Debug.Assert(_current < _count);
                return _nodeIsInterval[_current] ^ _invertCollection; 
            }
            set 
            { 
                Debug.Assert(_current < _count);
                _nodeIsInterval[_current] = value; 
            }
        }

        private TimeSpan NextNodeTime 
        {
            get 
            { 
                Debug.Assert(_current + 1 < _count);
                return _nodeTime[_current + 1]; 
            }
        }

        private bool NextNodeIsPoint 
        {
            get 
            { 
                Debug.Assert(_current + 1 < _count);
                return _nodeIsPoint[_current + 1] ^ _invertCollection; 
            }
        }

        private bool NextNodeIsInterval 
        {
            get 
            { 
                Debug.Assert(_current + 1 < _count);
                return _nodeIsInterval[_current + 1] ^ _invertCollection; 
            }
        }

        internal bool ContainsNullPoint 
        {
            get 
            { 
                return _containsNullPoint ^ _invertCollection;
            } 
        }

        private void SetInvertedMode(bool mode)
        { 
            Debug.Assert(_invertCollection != mode);  // Make sure we aren't redundantly setting the mode
            _invertCollection = mode; 
        } 

        #endregion // Private 

        #region Data

        private TimeSpan[]   _nodeTime;   // An interval's begin time 
        private bool[]    _nodeIsPoint;   // Whether [begin time] is included in the interval
        private bool[] _nodeIsInterval;   // Whether the open interval (begin time)--(next begin time, or infinity) is included 
 
        private bool _containsNullPoint;  // The point representing off-domain (Stopped) state
 
        private int _count;               // How many nodes are stored in the TIC
        private int _current;             // Enumerator pointing to the current node
        private bool _invertCollection;   // A flag used for operating on the inverse of a TIC
 
        private const int _minimumCapacity = 4;  // This should be at least 2 for dynamic growth to work correctly (by 2 each time)
 
        #endregion // Data 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
//------------------------------------------------------------------------------ 
//  Microsoft Windows Client Platform
//  Copyright (c) Microsoft Corporation, 2003
//
//  File:       TimeIntervalCollection.cs 
//-----------------------------------------------------------------------------
 
// Semantics 
// =========
// 
// DEFINITION:
// A TimeIntervalCollection (TIC) is a set of points on the time line, which may
// range from negative infinity (not including negative infinity itself) up to positive
// infinity (potentially including positive infinity).  It may also include a point Null, 
// which does not belong on the time line.  This non-domain point is considered to
// represent a state of 'Stopped'. 
// 
//
// OPERATIONS: 
// For any given time point P, a TIC must know whether it contains P or not.
// For any open interval (A,B), a TIC must know whether it has a non-empty intersection with (A,B).
// For any given TICs T and S, we must be able to determine if T and S have an non-empty intersection.
// 
//
// GENERAL DATA REPRESENTATION: 
// A TIC is represented by a set of nodes ordered on the real time line. 
// Each node is indexed, and has an associated time _nodeTime[x] and two flags:
//   _nodeIsPoint[x] specifies whether the time point at _nodeTime[x] is included in the TIC, and 
//   _nodeIsInterval[x] specifies whether the open interval (_nodeTime[x], _nodeTime[x+1])
// is included in the TIC.  If the node at x is the last node, and _nodeIsInterval[x] == true,
// then the TIC includes all points in the open interval (_nodeTime[x], Infinity).
// The presence of the Null point is denoted by the boolean _containsNullPoint. 
//
// Example #1: 
//   TIC includes closed-open interval [3,6) and point 7. 
//
//   Time:    3       6       7     infinity 
//        ---[X]=====[ ]-----[X]-------...
//   Index:   0       1       2
//
//       _nodeTime[0] = 3           _nodeTime[1] = 6            _nodeTime[2] = 7 
//    _nodeIsPoint[0] = true     _nodeIsPoint[1] = false     _nodeIsPoint[2] = true
// _nodeIsInterval[0] = true  _nodeIsInterval[1] = false  _nodeIsInterval[2] = false 
// 
// Example #2:
//   TIC includes point 0, the open interval (3,8), and the interval (8,infinity]; does not include point 8. 
//
//   Time:    0       3       8     infinity
//        ---[X]-----[ ]=====[ ]=======...
//   Index:   0       1       2 
//
//       _nodeTime[0] = 0            _nodeTime[1] = 3            _nodeTime[2] = 8 
//    _nodeIsPoint[0] = true      _nodeIsPoint[1] = false     _nodeIsPoint[2] = false 
// _nodeIsInterval[0] = false  _nodeIsInterval[1] = true   _nodeIsInterval[2] = true
// 
// RULES FOR LEGAL DATA REPRESENTATION:
// In order to keep the TIC and its algorithms optimized, we enforce the following rules:
//
// 1) All nodes are stored in strictly increasing _nodeTime order.  E.g. nodes remain sorted and 
//      each node has a unique _nodeTime.
// 
// 2) No unnecessary nodes are present: for any x < xMax, in the boolean sequence: 
//
//      _nodeIsPoint[x], _nodeIsInterval[x], _nodeIsPoint[x+1], _nodeIsInterval[x+1] 
//           [ ]----------------------------------[ ]--------------------------------
//
//    we maintain the following invariants:
//    [A] Out of the last three, at least one is true. 
//        Otherwise we don't need node X+1 to represent the same TIC.
//        If all are false, we have an illegal EMPTY node. 
//    [B] Out of the last three, at least one is false. 
//        Otherwise we don't need node X+1 to represent the same TIC.
//        If all are true, we have an illegal SATURATED node. 
//    [C] For the first index x=0, at least one out of _nodeIsPoint[x] or _nodeIsInterval[x] is true.
//        Otherwise we don't need node 0 to represent the same TIC,
//        and we have another case of an illegal EMPTY node.
// 
// 3) As a consequence of legal data representation, the TIC contains no points prior to the time
//     of its first node, e.g. if time T < _nodeTime[0] then T is not in the TIC. 
// 
//
// NOTE: 
// Please refer to the above comments and rules when reading documentation for specific methods below.
//

 
#if DEBUG
#define TRACE 
#endif // DEBUG 

using System; 
using System.Collections;
using System.Diagnostics;
using MS.Internal;
 
namespace System.Windows.Media.Animation
{ 
    ///  
    /// A list of timing events observed internally by a TimelineClock object.
    ///  
    internal struct TimeIntervalCollection
    {
        #region External interface
 
        #region Methods
 
        ///  
        /// Creates an empty collection
        ///  
        private TimeIntervalCollection(bool containsNullPoint)
        {
            Debug.Assert(_minimumCapacity >= 2);
 
            _containsNullPoint = containsNullPoint;
 
            _count = 0; 
            _current = 0;
            _invertCollection = false; 

            _nodeTime = null;
            _nodeIsPoint = null;
            _nodeIsInterval = null; 
        }
 
        ///  
        /// Creates a collection containing a single time point.
        ///  
        private TimeIntervalCollection(TimeSpan point)
            : this(false)
        {
            InitializePoint(point); 
        }
 
        ///  
        /// Reuses an existing collection so it now contains a single time point.
        ///  
        private void InitializePoint(TimeSpan point)
        {
            Debug.Assert(IsEmpty);  // We should start with a new or Clear()-ed collection first
 
            EnsureAllocatedCapacity(_minimumCapacity);
 
            _nodeTime[0] = point; 
            _nodeIsPoint[0] = true;
            _nodeIsInterval[0] = false; 
            Debug.Assert(_nodeIsInterval[0] == false);

            _count = 1;
        } 

        ///  
        /// Creates a collection that spans from a single point to infinity. 
        /// 
        private TimeIntervalCollection(TimeSpan point, bool includePoint) 
            : this(false)
        {
            InitializePoint(point);
 
            _nodeIsPoint[0] = includePoint;
            _nodeIsInterval[0] = true; 
        } 

        ///  
        /// Creates a collection containing a single interval.
        /// If from == to and the interval is not open-open, then a single point is created.
        /// 
        ///  
        /// The first endpoint time.
        ///  
        ///  
        /// Specifies whether the point from is included in the TIC.
        ///  
        /// 
        /// The last endpoint time.
        /// 
        ///  
        /// Specifies whether the point to is included in the TIC.
        ///  
        private TimeIntervalCollection(TimeSpan from, bool includeFrom, TimeSpan to, bool includeTo) 
            : this(false)
        { 
            EnsureAllocatedCapacity(_minimumCapacity);

            _nodeTime[0] = from;
 
            if (from == to)  // Create single point
            { 
                if (includeFrom || includeTo)  // Make sure we aren't trying to create a point from an open-open interval 
                {
                    _nodeIsPoint[0] = true; 
                    _count = 1;
                }
                else  // We are trying to create an open interval (x, x), so just create an empty TIC
                { 
                    Debug.Assert(_count == 0);  // The boolean constructor already did the job for us
                } 
            } 
            else  // from != to
            { 
                if (from < to)
                {
                    _nodeIsPoint[0] = includeFrom;
                    _nodeIsInterval[0] = true; 

                    _nodeTime[1] = to; 
                    _nodeIsPoint[1] = includeTo; 
                }
                else  // We are given reversed coordinates 
                {
                    _nodeTime[0] = to;
                    _nodeIsPoint[0] = includeTo;
                    _nodeIsInterval[0] = true; 

                    _nodeTime[1] = from; 
                    _nodeIsPoint[1] = includeFrom; 
                }
 
                _count = 2;
            }
        }
 
        /// 
        /// Removes all time intervals from the collection. 
        ///  
        internal void Clear()
        { 
            // Deallocate ONLY if we have previously expanded beyond default length to avoid redundant
            // reallocation.  If we called Clear, we are likely to reuse the collection soon.
            if (_nodeTime != null && _nodeTime.Length > _minimumCapacity)
            { 
                _nodeTime = null;
                _nodeIsPoint = null; 
                _nodeIsInterval = null; 
            }
 
            _containsNullPoint = false;

            _count = 0;
            _current = 0; 
            _invertCollection = false;
        } 
 
        // Used for optimizing slip computation in Clock
        internal bool IsSingleInterval 
        {
            get
            {
                return (_count < 2) || (_count == 2 && _nodeIsInterval[0]); 
            }
        } 
 
        // Used for optimizing slip computation in Clock
        internal TimeSpan FirstNodeTime 
        {
            get
            {
                Debug.Assert(_count > 0); 
                return _nodeTime[0];
            } 
        } 

        // Used for optimizing slip computation in Clock 
        // This method will discard nodes beyond the first two nodes.
        // The only scenario where this method is called on a larger-than-size-2 TIC is
        // when the parent of a Media wraps around in a Repeat.  Then we only enter
        // the Media's active period on the wraparound part of the TIC, so it is the only important 
        // part to leave.
        // Example: the parent has Duration=10 and RepeatBehavior=Forever.  It went from 9ms to 2ms (wraparound). 
        // Our default TIC is {[0, 2], (9, 10)}.  Slipping this by 1 will change it to {[1, 2]}.  It is apparent 
        // that this is the only part of the parent that actually overlaps our active zone.
        internal TimeIntervalCollection SlipBeginningOfConnectedInterval(TimeSpan slipTime) 
        {
            if (slipTime == TimeSpan.Zero)  // The no-op case
            {
                return this; 
            }
 
            TimeIntervalCollection slippedCollection; 
            if (_count < 2 || slipTime > _nodeTime[1] - _nodeTime[0])
            { 
                // slipTime > the connected duration, which basically eliminates the parent TIC interval for us;
                // This would only happen when media "outruns" the parent container, producing negative slip.
                slippedCollection = TimeIntervalCollection.Empty;
            } 
            else
            { 
                // Just shift the first node by slipAmount; the constructor handles the a==b case. 
                slippedCollection = new TimeIntervalCollection(_nodeTime[0] + slipTime, _nodeIsPoint[0],
                                                               _nodeTime[1]           , _nodeIsPoint[1]); 
            }

            if (this.ContainsNullPoint)
            { 
                slippedCollection.AddNullPoint();
            } 
            return slippedCollection; 
        }
 
        // Used for DesiredFrameRate adjustments in Clock
        internal TimeIntervalCollection SetBeginningOfConnectedInterval(TimeSpan beginTime)
        {
#if DEBUG 
            Debug.Assert(IsSingleInterval);
#endif 
            Debug.Assert(0 < _count && _count <= 2); 

            if (_count == 1) 
            {
                return new TimeIntervalCollection(_nodeTime[0], _nodeIsPoint[0],
                                                  beginTime,    true);
            } 
            else  // _count == 2
            { 
                Debug.Assert(beginTime <= _nodeTime[1]); 
                return new TimeIntervalCollection(beginTime,    false,
                                                  _nodeTime[1], _nodeIsPoint[1]); 
            }
        }

        ///  
        /// Creates a collection containing a single time point
        ///  
        static internal TimeIntervalCollection CreatePoint(TimeSpan time) 
        {
            return new TimeIntervalCollection(time); 
        }

        /// 
        /// Creates a collection containing a closed-open time interval [from, to) 
        /// 
        static internal TimeIntervalCollection CreateClosedOpenInterval(TimeSpan from, TimeSpan to) 
        { 
            return new TimeIntervalCollection(from, true, to, false);
        } 

        /// 
        /// Creates a collection containing an open-closed time interval (from, to]
        ///  
        static internal TimeIntervalCollection CreateOpenClosedInterval(TimeSpan from, TimeSpan to)
        { 
            return new TimeIntervalCollection(from, false, to, true); 
        }
 
        /// 
        /// Creates a collection containing a closed time interval [from, infinity)
        /// 
        static internal TimeIntervalCollection CreateInfiniteClosedInterval(TimeSpan from) 
        {
            return new TimeIntervalCollection(from, true); 
        } 

        ///  
        /// Creates an empty collection
        /// 
        static internal TimeIntervalCollection Empty
        { 
            get
            { 
                return new TimeIntervalCollection(); 
            }
        } 

        /// 
        /// Creates a collection with the null point
        ///  
        static internal TimeIntervalCollection CreateNullPoint()
        { 
            return new TimeIntervalCollection(true); 
        }
 
        /// 
        /// Adds the null point to an existing collection
        /// 
        internal void AddNullPoint() 
        {
            _containsNullPoint = true; 
        } 

 
        /// 
        /// Returns whether the time point is contained in the collection
        /// 
        // RUNNING TIME: O(log2(_count)) worst-case 
        // IMPLEMENTATION FOR CONTAINS(TIME) OPERATION:
        // To determine if point at time T is contained in the TIC, do the following: 
        // 
        //   1) Find the largest index x, such that _nodeTime[x] <= T
        // 
        //   2) IF no such x exists, then _nodeTime[x] > T for every valid x;
        //        then T comes earlier than any node and cannot be in the TIC by Rule #3 above.
        //        Diagram: ----T----[0]----[1]----[2]---...
        // 
        //   3) ELSE IF x exists and _nodeTime[x] == T, then T happens to coincide with a TIC node.
        //        We check if TIC contains _nodeTime[x] by querying and RETURNING _nodeIsPoint[x]. 
        //        Diagram -----[ ]----[T,x]----[ ]----... 
        //
        //   4) ELSE x exists and _nodeTime[x] < T, then T happens to fall after a TIC node at x, but before 
        //        the next TIC node if any later nodes exist.  We check if TIC contains the open interval
        //        (_nodeTime[x], _nodeTime[x+1]) or (_nodeTime[x], infinity) if node x was the last node.
        //        We do this by querying and RETURNING _nodeIsInterval[x].
        //        Diagram: -----[x]----T----[x+1]----[x+2]--.... 
        //          =OR=   -----[x]----T----infinity
        // 
        internal bool Contains(TimeSpan time) 
        {
            int index = Locate(time);  // Find the previous or equal time 

            if (index < 0)  // Queried time lies before the earliest interval's begin time
            {
                return false; 
            }
            else if (_nodeTime[index] == time)  // Queried time falls exactly onto a node 
            { 
                return _nodeIsPoint[index];
            } 
            else  // Queried time comes after the node
            {
                Debug.Assert(_nodeTime[index] < time);
 
                return _nodeIsInterval[index];
            } 
        } 

 
        /// 
        /// Returns whether the open interval (from, to) has an intersection with this collection
        /// 
        // RUNNING TIME: O(log2(_count)) worst-case 
        // IMPLEMENTATION FOR INTERSECTS(FROM,TO) OPERATION:
        // We want to determine if the open interval (From,To), abbreviated (F,T), has a non-zero intersection 
        // with the TIC.  Assert F= 0.  F comes right at or after _nodeTime[fromIndex] and before 
        //         any next node; T comes strictly after _nodeTime[fromIndex] (because we asserted F= 0) && _nodeIsInterval[toIndex] 
        //
        //         Notice that this clause is good to short-circuit early, because it traps cases of 
        //         complete mismatches, where the interval is not in the TIC's normal range.
        //
        //   4) ELSE IF the difference between fromIndex and toIndex is exactly 1 (e.g. fromIndex+1 == toIndex), then:
        // 
        //       * Suppose fromIndex is -1, thus F falls before the first node.
        //         Then toIndex is at least 0, thus T falls at least aligned with the first node. 
        //         Now it matters whether T is at or after the first node.  If T is at the first node, 
        //         then all points in (F,T) lie *before* the first node and we have no possible intersection,
        //         so we have to return FALSE.  Else T is after the first node, then some point in (F,T) lies 
        //         exactly on the first node, and some points lie after it.  By rule #2C, one of these two parts
        //         must be contained in the TIC.  So then we return TRUE.
        //
        //         This is simplified as RETURN (_nodeTime[toIndex] < T) 
        //
        //         Diagram (lowercase t denotes toIndex): 
        //                     (F)=======(T) 
        //                  -------------[t]-----[ ]----.....
        // 
        //                     (F)=========(T)
        //                  ----------[t]--------[ ]----.....
        //
        //       * Else fromIndex is non-negative, thus F falls at or right after node at [fromIndex]. 
        //         Then toIndex falls at least at or right after node at [fromIndex+1].
        //         (F,T) now must overlap the open interval (_nodeTime[fromIndex], _nodeTime[toIndex]), 
        //         and IFF _nodeTime[toIndex] < T then it will also overlap the point at _nodeTime[toIndex] 
        //         and part of the open interval (_nodeTime[toIndex], nextNodeTime_or_Infinity).  In the
        //         first case we merely check _nodeIsInterval[fromIndex].  In the second case, we invoke 
        //         rule #2B and conclude that an intersection must exist somewhere between all three parts.
        //         Hence we RETURN _nodeIsInterval[fromIndex] || (_nodeTime[toIndex] < T).
        //
        //         Diagram (lowercase t denotes toIndex; t denotes toIndex): 
        //                        (F)=======(T)
        //                  --[f]-----------[t]-----[ ]----..... 
        // 
        //                     (F)===========(T)
        //                  ---[f]------[t]--------[ ]----..... 
        //
        //         The entire clause can now be further simplified as the following statement:
        //         RETURN (_nodeTime[toIndex] < T) || (fromIndex >= 0 && _nodeIsInterval[fromIndex])
        // 
        //   5) ELSE the difference between fromIndex and toIndex is greater than 1 (e.g. fromIndex+1 < toIndex), then:
        // 
        //       * Suppose fromIndex is -1, thus F falls before the first node. 
        //         Then toIndex is at least 1, thus T falls at least aligned with the second node.
        //         Then (F,T) overlaps at least point _nodeTime[0] and open interval (_nodeTime[0], _nodeTime[1]). 
        //         By rule #2C above, at least one of those two must be in the TIC, hence some point in (F,T)
        //         is also in the TIC, we have a non-null intersection and RETURN TRUE.
        //
        //         Diagram (lowercase t denotes toIndex): 
        //                      (F)=========(T)
        //                  ----------[ ]---[t]----[ ]----..... 
        // 
        //                      (F)=============(T)
        //                  --------[ ]-----[t]------[ ]----..... 
        //
        //       * Else fromIndex is non-negative, thus F falls at or right after node at [fromIndex].
        //         Then toIndex falls at least at or after node at [fromIndex+2].
        //         Then the following parts of the TIC must partially overlap the interval: 
        //            (A) open interval (_nodeTime[fromIndex], _nodeTime[fromIndex+1])
        //            (B) point at _nodeTime[fromIndex+1] 
        //            (C) open interval (_nodeTime[fromIndex+1], _nodeTime[fromIndex+2]) 
        //         By rule #2B, at least one of the consecutive parts in the above sequence must be included in the TIC.
        //         Therefore, a point in the interval (F,T) must be contained in the TIC, and we RETURN TRUE. 
        //
        //         Diagram (lowercase f denotes fromIndex; t denotes toIndex):
        //                         (F)=========(T)
        //                  --[f]--------[ ]---[t]----[ ]----..... 
        //
        //                      (F)============(T) 
        //                  ----[f]----[ ]-----[t]------[ ]----..... 
        //
        //       Both sub-clauses lead to the same result, so we uniformly RETURN TRUE when reaching this clause. 
        //
        internal bool Intersects(TimeSpan from, TimeSpan to)
        {
            if (from == to)  // The open interval (x, x) is null and has no intersections 
            {
                return false; 
            } 
            else if (from > to)  // If to and from are reversed, swap them back
            { 
                TimeSpan temp = from;
                from = to;
                to = temp;
            } 

            int fromIndex = Locate(from);  // Find the nearest indices for to and from 
            int   toIndex = Locate(to); 

            Debug.Assert(fromIndex <= toIndex); 

            if (fromIndex == toIndex)
            {
                // Since we are testing an *open* interval, the only way we can intersect is by checking 
                // if the interior of the arc is part of the TIC.
                return (toIndex >= 0) && _nodeIsInterval[toIndex]; 
            } 
            // The interval only overlaps one TIC node; fromIndex may be -1 here
            else if (fromIndex + 1 == toIndex) 
            {
                Debug.Assert(toIndex >= 0); // Since fromIndex!=toIndex, toIndex must be >= 0

                // By rule #2B and C, if we fall across an arc boundary, we must therefore intersect the TIC. 
                return (to > _nodeTime[toIndex]) || (fromIndex >= 0 && _nodeIsInterval[fromIndex]);
            } 
            else 
            {
                Debug.Assert(fromIndex + 1 < toIndex); 

                // We must fall across an arc boundary, and by rule #2B we must therefore intersect the TIC.
                return true;
            } 
        }
 
        ///  
        /// Returns whether this collection has a non-empty intersection with the other collection
        ///  
        // RUNNING TIME: O(_count) worst-case
        // IMPLEMENTATION FOR INTERSECTS(OTHER) OPERATION:
        //
        //  We implement intersection by "stacking" the two TICs atop each other and seeing if 
        //  there is any point or interval common to both.  We do this by having two indexers,
        //  index1 and index2, traverse the lengths of both TICs simultaneously.  We maintain 
        //  the following invariant: each indexer, when "projected" onto the other TIC than the one 
        //  it actually indexes into, falls less than a node ahead of the other indexer.
        //  To rephrase intuitively, the indexers never fall out of step by having one get 
        //  too far ahead of the other.
        //
        //  Example:
        // 
        //  this    ----[0]----[1]--------------------[2]----[3]-----------[4]---------[5]------...
        //  other   --------------------[0]----[1]------------------[2]----------------[3]------... 
        //                      ^index1 
        //                               ^index2
        // 
        //  Our invariant means that one of the indexed nodes either coincides exactly with
        //  the other, as is the case for nodes this[4] and other[2] in the above example,
        //  or "projects" into the other node's subsequent interval; in the above example,
        //  other[index2] projects onto the interval of this[index1]. 
        //
        //  At each iteration, we check for an intersection at: 
        //    A) the latter of the indexed nodes, and 
        //    B) the interval right after the latter indexed node
        // 
        //  3 possible scenarios:
        //  CASE I.   index1 < index2  intersects if _nodeIsInterval[index1] && (_nodeIsPoint[index2] || _nodeIsInterval[index2])
        //  CASE II.  index1 > index2  intersects if _nodeIsInterval[index2] && (_nodeIsPoint[index1] || _nodeIsInterval[index1])
        //  CASE III. index1 = index2  intersects if (_nodeIsPoint[index1] && _nodeIsPoint[index2]) || (_nodeIsInterval[index1] && _nodeIsInterval[index2]) 
        //
        //  We say that in Case I, index1 is dominant in the sense that index2 points to a node on index1's "turf"; 
        //  We move index2 through index1's entire interval to check for intersections against it.  Once index2 passes 
        //  index1's interval, we advance index1 as well.  Then we again check which scenario we end up in.
        // 
        //  Case II is treated anti-symmetrically to Case I.
        //
        //  Case III is special, because we cannot treat it the same as Case I or II.  This is becasue we have to check
        //  for a point-point intersection, and check which indexer should be advanced next.  It is possible that both 
        //  indexers need to be advanced if the next 2 nodes are also equal.
        // 
        //  We continue advancing the pointers until we find an intersection or run out of nodes on either of the TICs. 
        //
        internal bool Intersects(TimeIntervalCollection other) 
        {
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled

            if (this.ContainsNullPoint && other.ContainsNullPoint)  // Short-circuit null point intersections 
            {
                return true; 
            } 
            else if (this.IsEmptyOfRealPoints || other.IsEmptyOfRealPoints)  // Only intersection with an empty TIC is at null points, which case is already handled
            { 
                return false;
            }
            else  // Both TICs are non-empty and don't intersect at the null point
            { 
                return IntersectsHelper(other);
            } 
        } 

        // This method was made separate to detect intersections with inverses when needed 
        private bool IntersectsHelper(TimeIntervalCollection other)
        {
            // Make sure the indexers are starting next to each other
            IntersectsHelperPrepareIndexers(ref this, ref other); 

            // The outer loop does not bail, rather we return directly from inside the loop 
            bool intersectionFound = false; 
            while (true)
            { 
                // The inner loops iterate through the subset of a TIC

                // CASE I.
                // In this case, index1 is the dominant indexer: index2 is on its turf and we keep advancing index2 and checking for intesections 
                // After this helper, index2 will no longer be ahead of index1
                if ((this.CurrentNodeTime < other.CurrentNodeTime) && 
                    IntersectsHelperUnequalCase(ref this, ref other, ref intersectionFound)) 
                {
                    return intersectionFound; 
                }


                // CASE II. 
                // In this case, index2 is the dominant indexer: index1 is on its turf and we keep advancing index1 and checking for intesections
                // After this helper, index1 will no longer be ahead of index2 
                if ((this.CurrentNodeTime > other.CurrentNodeTime) && 
                    IntersectsHelperUnequalCase(ref other, ref this, ref intersectionFound))
                { 
                    return intersectionFound;
                }

 
                // CASE III.
                // In this case, neither indexer is dominant: they are pointing to the same point in time 
                // We keep doing this until the indices are no longer equal 
                while (this.CurrentNodeTime == other.CurrentNodeTime)
                { 
                    if (IntersectsHelperEqualCase(ref this, ref other, ref intersectionFound))
                    {
                        return intersectionFound;
                    } 
                }
            } 
        } 

        // Make sure the indexers are starting next to each other 
        static private void IntersectsHelperPrepareIndexers(ref TimeIntervalCollection tic1, ref TimeIntervalCollection tic2)
        {
            Debug.Assert(!tic1.IsEmptyOfRealPoints);  // We shouldn't reach here if either TIC is empty
            Debug.Assert(!tic2.IsEmptyOfRealPoints); 

            tic1.MoveFirst();  // Point _current to the first node in both TICs 
            tic2.MoveFirst(); 

            // First bring tic1._current and tic2._current within an interval of each other 
            if (tic1.CurrentNodeTime < tic2.CurrentNodeTime)
            {
                // Keep advancing tic1._current as far as possible while keeping _nodeTime[tic1._current] < _nodeTime[tic2._current]
                while (!tic1.CurrentIsAtLastNode && (tic1.NextNodeTime <= tic2.CurrentNodeTime)) 
                {
                    tic1.MoveNext(); 
                } 
            }
            else if (tic2.CurrentNodeTime < tic1.CurrentNodeTime) 
            {
                // Keep advancing tic2._current as far as possible while keeping _nodeTime[tic1._current] > _nodeTime[tic2._current]
                while (!tic2.CurrentIsAtLastNode && (tic2.NextNodeTime <= tic1.CurrentNodeTime))
                { 
                    tic2.MoveNext();
                } 
            } 
        }
 
        // Returns true if we know at this point whether an intersection is possible between tic1 and tic2
        // The fact of whether an intersection was found is stored in the ref parameter intersectionFound
        static private bool IntersectsHelperUnequalCase(ref TimeIntervalCollection tic1, ref TimeIntervalCollection tic2, ref bool intersectionFound)
        { 
            Debug.Assert(!intersectionFound);  // If an intersection was already found, we should not reach this far
 
            if (tic1.CurrentNodeIsInterval)  // If we are within an interval in tic1, we immediately have an intersection 
            {
                // If we have gotten into this method, tic1._current comes earlier than does tic2._current; 
                // Suppose the following assert is false; then by Rule #2A, tic2's previous interval must be included;
                // If this was the case, then tic2's previous interval overlapped tic1's current interval.  Since it's
                // included, we would have encountered an intersection before even reaching this method!  Then you
                // should not even be here now.  Else suppose we are at tic2's first node, then the below Assert 
                // follows directly from Rule #3.
                Debug.Assert(tic2.CurrentNodeIsPoint || tic2.CurrentNodeIsInterval); 
 
                intersectionFound = true;
                return true; 
            }
            else if (tic1.CurrentIsAtLastNode)  // // If we are already at the end of tic1, we ran out of nodes that may have an intersection
            {
                intersectionFound = false; 
                return true;
            } 
            else  // Else we are inside a non-included interval in tic1, no intersection is possible, but keep advancing tic2._current 
            {
                while (!tic2.CurrentIsAtLastNode && (tic2.NextNodeTime <= tic1.NextNodeTime)) 
                {
                    tic2.MoveNext();
                }
 
                // If nextNodeTime1 is null, we should never get here because the IF statement would have caught it and quit
                Debug.Assert(!tic1.CurrentIsAtLastNode);  // Thus tic1._current can be safely advanced now 
 
                // Now tic1._current can be safely advanced forward
                tic1.MoveNext(); 

                // If we broke out of Case I, its conditional should no longer hold true:
                Debug.Assert(tic1.CurrentNodeTime >= tic2.CurrentNodeTime);
 
                // Enforce our invariant: neither index gets too far ahead of the other.
                Debug.Assert(tic2.CurrentIsAtLastNode || (tic1.CurrentNodeTime < tic2.NextNodeTime)); 
                Debug.Assert(tic1.CurrentIsAtLastNode || (tic2.CurrentNodeTime < tic1.NextNodeTime)); 

                // Tell the main algorithm to continue working 
                return false;
            }
        }
 
        // Returns true if we know at this point whether an intersection is possible between tic1 and tic2
        // The fact of whether an intersection was found is stored in the ref parameter intersectionFound 
        static private bool IntersectsHelperEqualCase(ref TimeIntervalCollection tic1, ref TimeIntervalCollection tic2, ref bool intersectionFound) 
        {
            // If the nodes match exactly, check if the points are both included, or if the intervals are both included 
            if ((tic1.CurrentNodeIsPoint && tic2.CurrentNodeIsPoint) ||
                (tic1.CurrentNodeIsInterval && tic2.CurrentNodeIsInterval))
            {
                intersectionFound = true; 
                return true;
            } 
            // We did not find an intersection, but advance whichever index has a closer next node 
            else if (!tic1.CurrentIsAtLastNode && (
                tic2.CurrentIsAtLastNode || (tic1.NextNodeTime < tic2.NextNodeTime))) 
            {
                tic1.MoveNext();
            }
            else if (!tic2.CurrentIsAtLastNode && ( 
                     tic1.CurrentIsAtLastNode || (tic2.NextNodeTime < tic1.NextNodeTime)))
            { 
                tic2.MoveNext(); 
            }
            else if (!tic1.CurrentIsAtLastNode && !tic2.CurrentIsAtLastNode) 
            {
                // If both indices have room to advance, and we haven't yet advanced either one, it must be the next nodes are also exactly equal
                Debug.Assert(tic1.NextNodeTime == tic2.NextNodeTime);
 
                // It is necessary to advance both indices simultaneously, otherwise we break our invariant - one will be too far ahead
                tic1.MoveNext(); 
                tic2.MoveNext(); 
            }
            else  // The only way we could get here is if both indices are pointing to the last nodes 
            {
                Debug.Assert(tic1.CurrentIsAtLastNode && tic2.CurrentIsAtLastNode);

                // We have exhausted all the nodes and not found an intersection; bail 
                intersectionFound = false;
                return true; 
            } 

            // Enforce our invariant: neither index gets too far ahead of the other. 
            Debug.Assert(tic2.CurrentIsAtLastNode || (tic1.CurrentNodeTime < tic2.NextNodeTime));
            Debug.Assert(tic1.CurrentIsAtLastNode || (tic2.CurrentNodeTime < tic1.NextNodeTime));

            // Tell the main algorithm to continue working 
            return false;
        } 
 
        /// 
        /// Returns whether this collection has a non-empty intersection with the inverse of the other collection 
        /// 
        internal bool IntersectsInverseOf(TimeIntervalCollection other)
        {
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled 

            if (this.ContainsNullPoint && !other.ContainsNullPoint)  // Intersection at null points 
            { 
                return true;
            } 
            if (this.IsEmptyOfRealPoints)  // We are empty, and have no null point; we have nothing to intersect
            {
                return false;
            } 
            else if (other.IsEmptyOfRealPoints ||  // We are non-empty, and other is the inverse of empty (e.g. covers all real numbers, so we must intersect), OR...
                     this._nodeTime[0] < other._nodeTime[0])  // Neither TIC is empty, and we start first; this means the inverted "other" by necessity 
                                                              // overlaps our first node, so it must intersect either our node or subsequent interval. 
            {
                return true; 
            }
            else  // Neither TIC is empty, and other starts no later than we do; then use regular intersection logic with inverted boolean flags
            {
                other.SetInvertedMode(true); 

                bool returnValue = IntersectsHelper(other); 
 
                other.SetInvertedMode(false);  // Make sure we don't leave other TIC in an inverted state!
 
                return returnValue;
            }
        }
 

        ///  
        /// Returns whether this collection has a non-empty intersection with a potentially infinite 
        /// periodic collection defined by a set of parameters.
        ///  
        /// 
        /// The periodic TIC, or PTIC, represents the subset of the active period in a timeline where time
        /// flows non-linearly.  Specifically, it contains the points of reversal in autoreversing timelines,
        /// and the accel and decel periods in timelines with acceleration. 
        /// 
        /// Begin time of the periodic collection. 
        /// Length of a single iteration in the periodic collection. 
        /// Ratio by which to scale down the periodic collection.
        /// Ratio of the length of the accelerating portion of the iteration. 
        /// Ratio of the length of the decelerating portion of the iteration.
        /// Indicates whether reversed arcs should follow after forward arcs.
        internal bool IntersectsPeriodicCollection(TimeSpan beginTime,  Duration period, double appliedSpeedRatio,
                                                   double accelRatio, double decelRatio, 
                                                   bool isAutoReversed)
        { 
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled 

            if ( IsEmptyOfRealPoints                                      // If we have no real points, no intersection with the PTIC is possible 
              || (period == TimeSpan.Zero)                                // The PTIC has no nonzero period, we define such intersections nonexistent
              || (accelRatio == 0 && decelRatio == 0 && !isAutoReversed)  // The PTIC has no non-linear points, no intersection possible
              || !period.HasTimeSpan                                      // We have an indefinite period, e.g. we are not periodic
              || appliedSpeedRatio > period.TimeSpan.Ticks)               // If the speed ratio is high enough the period will effectively be 0 
            {
                return false; 
            } 

            // By now, we know that: 
            // (A) Both we and the PTIC are non-empty
            // (B) We are a subset of the active period, which is the superset of the PTIC

            // Find the smallest n such that _nodeTime[n+1] > beginTime; n can be the last index, so that _nodeTime[n+1] is infinity 

            MoveFirst(); 
 
            Debug.Assert(beginTime <= CurrentNodeTime);  // The PTIC is clipped by the active period, and we are a subset of the active period
            Debug.Assert(CurrentIsAtLastNode || beginTime < NextNodeTime); 

            long beginTimeInTicks = beginTime.Ticks;

            long periodInTicks = (long)((double)period.TimeSpan.Ticks / appliedSpeedRatio); 

            // PeriodInTicks may overflow if appliedSpeedRatio is sufficiently small. 
            // The best we can do is clamp the value to MaxValue. 
            if (periodInTicks < 0)
            { 
                periodInTicks = Int64.MaxValue / 2;
            }

            long doublePeriod = 2 * periodInTicks; 

            long accelPeriod = (long)(accelRatio * (double)periodInTicks); 
            long decelPeriod = (long)((1.0 - decelRatio) * (double)periodInTicks);  // This is where deceleration BEGINS. 

            // We walk through the TIC and convert from TIC's coordinates into wrapped-around PTIC coordinates: 
            //
            //  *======o   Linear   *============o  ...(wraparound to front)
            //   Accel *============o    Decel
            //         ^            ^            ^ 
            //    accelPeriod  decelPeriod  periodInTicks
 
            while (_current < _count) 
            {
                long projectedCurrentNodeTime; 
                bool isOnReversingArc = false;

                if (isAutoReversed)  // If autoreversed, our effective period is doubled and we check for reversed arcs
                { 
                    projectedCurrentNodeTime = ((CurrentNodeTime.Ticks - beginTimeInTicks) % doublePeriod);
                    if (projectedCurrentNodeTime >= periodInTicks) 
                    { 
                        projectedCurrentNodeTime = doublePeriod - projectedCurrentNodeTime;  // We are on a reversed arc
                        isOnReversingArc = true; 
                    }
                }
                else  // Default, non-autoreversed case
                { 
                    projectedCurrentNodeTime = (CurrentNodeTime.Ticks - beginTimeInTicks) % periodInTicks;
                } 
 

                if ((0 < projectedCurrentNodeTime && projectedCurrentNodeTime < accelPeriod)  // If we fall strictly into the accel zone, or... 
                 || (decelPeriod < projectedCurrentNodeTime))                    // We fall strictly into the decel zone
                                                                                 // (note we KNOW that projectedCNT < periodInTicks by definition of modulo)
                {
                    return true; 
                }
                else if ((projectedCurrentNodeTime == 0 || projectedCurrentNodeTime == decelPeriod) 
                      && CurrentNodeIsPoint)  // We fall exactly onto the beginning of an accel or decel zone, point intersection 
                {
                    return true; 
                }
                else if (CurrentNodeIsInterval)
                {
                    if ((projectedCurrentNodeTime == 0 && accelPeriod > 0) 
                     || (projectedCurrentNodeTime == decelPeriod && (decelPeriod < periodInTicks)))
                    // We fall exactly onto the beginning of an accel or decel zone and have the interval intersect 
                    { 
                        return true;
                    } 
                    else  // Else our node falls into the linear zone, but our interval may overlap a later Accel/Decel zone.
                          // Check if the interval is just long enough to stretch to the next non-linear zone.
                    {
                        long projectedTimeUntilIntersection; 
                        if (isOnReversingArc)
                        { 
                            projectedTimeUntilIntersection = projectedCurrentNodeTime - accelPeriod; 
                        }
                        else 
                        {
                            projectedTimeUntilIntersection = decelPeriod - projectedCurrentNodeTime;
                        }
 
                        if (CurrentIsAtLastNode
                          || (NextNodeTime.Ticks - CurrentNodeTime.Ticks >= projectedTimeUntilIntersection)) 
                          // We have an intersection, so long as we aren't clipped by endTime 
                        {
                            return true; 
                        }
                    }
                }
 
                // We haven't found any intersection at the present node and interval, advance to the next node
                MoveNext(); 
            } 

            return false;  // We have exhausted all nodes and found no intersection. 
        }

        /// 
        /// Returns whether this collection has intersections with multiple distinct periods of a 
        /// potentially infinite periodic collection defined by a set of parameters.
        ///  
        ///  
        /// The periodic TIC, or PTIC, represents the subset of the active period in a timeline where time
        /// flows non-linearly.  Specifically, it contains the points of reversal in autoreversing timelines, 
        /// and the accel and decel periods in timelines with acceleration.
        /// 
        /// Begin time of the periodic collection.
        /// Length of a single iteration in the periodic collection. 
        /// Ratio by which to scale down the periodic collection.
        internal bool IntersectsMultiplePeriods(TimeSpan beginTime, Duration period, double appliedSpeedRatio) 
        { 
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled
 
            if (_count < 2                                    // If we have 0-1 real points, no intersection with multiple periods is possible
              || (period == TimeSpan.Zero)                    // The PTIC has no nonzero period, we define such intersections nonexistent
              || !period.HasTimeSpan                          // We have an indefinite period, e.g. we are not periodic
              || appliedSpeedRatio > period.TimeSpan.Ticks)   // If the speed ratio is high enough the period will effectively be 0 
            {
                return false; 
            } 

            long periodInTicks = (long)((double)period.TimeSpan.Ticks / appliedSpeedRatio); 

            // PeriodInTicks may overflow if appliedSpeedRatio is sufficiently small;
            // In this case we will effectively have a single huge period, so nothing to detect here.
            if (periodInTicks <= 0) 
            {
                return false; 
            } 
            else  // Normal case, compare the period in which the first and last nodes fall
            { 
                long firstNodePeriod = (FirstNodeTime - beginTime).Ticks / periodInTicks;
                TimeSpan lastNodeTime = _nodeTime[_count - 1];
                long lastNodePeriod = (lastNodeTime - beginTime).Ticks / periodInTicks;
 
                return (firstNodePeriod != lastNodePeriod);
            } 
        } 

        ///  
        /// Used for projecting the end of a fill period.  When calling, we already know that we intersect the fill period
        /// but not the active period.
        /// 
        ///  
        /// Returns a collection which is the projection of the argument point onto the defined periodic function.
        ///  
        /// An empty output projection, passed by reference to allow TIC reuse. 
        /// Begin time of the periodic function.
        /// The end (expiration) time of the periodic function. 
        /// Length of a single iteration in the periodic collection.
        /// Ratio by which to scale down the periodic collection.
        /// Ratio of the length of the accelerating portion of the iteration.
        /// Ratio of the length of the decelerating portion of the iteration. 
        /// Indicates whether reversed arcs should follow after forward arcs.
        internal void ProjectPostFillZone(ref TimeIntervalCollection projection, 
                                          TimeSpan beginTime, TimeSpan endTime, Duration period, 
                                          double appliedSpeedRatio, double accelRatio, double decelRatio,
                                          bool isAutoReversed) 
        {
            Debug.Assert(projection.IsEmpty);  // Make sure the projection was properly cleared first
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled
            Debug.Assert(beginTime <= endTime);     // Ensure legitimate begin/end clipping parameters 

            Debug.Assert(!IsEmptyOfRealPoints);  // We assume this function is ONLY called when this collection overlaps the postfill zone.  So we cannot be empty. 
            Debug.Assert(!period.HasTimeSpan || period.TimeSpan > TimeSpan.Zero || beginTime == endTime);  // Check the consistency of degenerate case where simple duration is zero; expiration time should equal beginTime 
            Debug.Assert(!_nodeIsInterval[_count - 1]);  // We should not have an infinite domain set
 
            long outputInTicks;

            if (beginTime == endTime)  // Degenerate case when our active period is a single point; project only that point
            { 
                outputInTicks = 0;
            } 
            else  // The case of non-zero active duration 
            {
                outputInTicks = (long)(appliedSpeedRatio * (double)(endTime - beginTime).Ticks); 

                if (period.HasTimeSpan)  // Case of finite simple duration; in the infinite case we are already done
                {
                    long periodInTicks = period.TimeSpan.Ticks;  // Start by folding the point into its place inside a simple duration 

                    if (isAutoReversed) 
                    { 
                        long doublePeriod = periodInTicks << 1;  // Fast multiply by 2
                        outputInTicks = outputInTicks % doublePeriod; 

                        if (outputInTicks > periodInTicks)
                        {
                            outputInTicks = doublePeriod - outputInTicks; 
                        }
                    } 
                    else 
                    {
                        outputInTicks = outputInTicks % periodInTicks; 
                        if (outputInTicks == 0)
                        {
                            outputInTicks = periodInTicks;  // If we are at the end, stick to the max value
                        } 
                    }
 
                    if (accelRatio + decelRatio > 0)  // Now if we have acceleration, warp the point by the correct amount 
                    {
                        double dpPeriod = (double)periodInTicks; 
                        double inversePeriod = 1 / dpPeriod;
                        double halfMaxRate = 1 / (2 - accelRatio - decelRatio);  // Constants to simplify
                        double t;
 
                        long accelEnd = (long)(dpPeriod * accelRatio);
                        long decelStart = periodInTicks - (long)(dpPeriod * decelRatio); 
 
                        if (outputInTicks < accelEnd)  // We are in accel zone
                        { 
                            t = (double)outputInTicks;
                            outputInTicks = (long)(halfMaxRate * inversePeriod * t * t / accelRatio);
                        }
                        else if (outputInTicks <= decelStart)  // We are in the linear zone 
                        {
                            t = (double)outputInTicks; 
                            outputInTicks = (long)(halfMaxRate * (2 * t - accelRatio)); 
                        }
                        else  // We are in decel zone 
                        {
                            t = (double)(periodInTicks - outputInTicks);
                            outputInTicks = periodInTicks - (long)(halfMaxRate * inversePeriod * t * t / decelRatio);
                        } 
                    }
                } 
            } 

            projection.InitializePoint(TimeSpan.FromTicks(outputInTicks)); 
        }


        ///  
        /// Returns a collection which is the projection of this collection onto the defined periodic function.
        ///  
        ///  
        /// The object on which this method is called is a timeline's parent's collection of intervals.
        /// The periodic collection passed via parameters describes the active/fill periods of the timeline. 
        /// The output is the projection of (this) object using the parameter function of the timeline.
        ///
        /// We assume this function is ONLY called when this collection overlaps the active zone.
        /// 
        /// The periodic function maps values from domain to range within its activation period of [beginTime, endTime);
        /// in the fill period [endTime, endTime+fillDuration) everything maps to a constant post-fill value, and outside of 
        /// those periods every value maps to null. 
        ///
        /// The projection process can be described as three major steps: 
        ///
        /// (1) NORMALIZE this collection: offset the TIC's coordinates by BeginTime and scale by SpeedRatio.
        ///
        /// (2) FOLD this collection.  This means we convert from parent-time coordinate space into the space of 
        ///     a single simpleDuration for the child.  This is equivalent to "cutting up" the parent TIC into
        ///     equal-length segments (of length Period) and overlapping them -- taking their union.  This lets us 
        ///     know exactly which values inside the simpleDuration we have reached on the child.  In the case of 
        ///     autoreversed timelines, we do the folding similiar to folding a strip of paper -- alternating direction.
        /// 
        /// (3) WARP the resulting collection.  We now convert from simpleDuration domain coordinates into
        ///     coordinates in the range of the timeline function.  We do this by applying the "warping" effects of
        ///     acceleration, and deceleration.
        /// 
        /// In the special case of infinite simple duration, we essentially are done after performing NORMALIZE,
        /// because no periodicity or acceleration is present. 
        /// 
        /// In the ultimate degenerate case of zero duration, we terminate early and project the zero point.
        /// 
        /// 
        /// An empty output projection, passed by reference to allow TIC reuse.
        /// Begin time of the periodic function.
        /// The end (expiration) time of the periodic function.  Null indicates positive infinity. 
        /// The fill time appended at the end of the periodic function.  Zero indicates no fill period.  Forever indicates infinite fill period.
        /// Length of a single iteration in the periodic collection. 
        /// Ratio by which to scale down the periodic collection. 
        /// Ratio of the length of the accelerating portion of the iteration.
        /// Ratio of the length of the decelerating portion of the iteration. 
        /// Indicates whether reversed arcs should follow after forward arcs.
        internal void ProjectOntoPeriodicFunction(ref TimeIntervalCollection projection,
                                                  TimeSpan beginTime, Nullable endTime,
                                                  Duration fillDuration, Duration period, 
                                                  double appliedSpeedRatio, double accelRatio, double decelRatio,
                                                  bool isAutoReversed) 
        { 
            Debug.Assert(projection.IsEmpty);
            Debug.Assert(!_invertCollection);  // Make sure we never leave inverted mode enabled 
            Debug.Assert(!endTime.HasValue || beginTime <= endTime);     // Ensure legitimate begin/end clipping parameters

            Debug.Assert(!IsEmptyOfRealPoints);  // We assume this function is ONLY called when this collection overlaps the active zone.  So we cannot be empty.
            Debug.Assert(!endTime.HasValue || endTime >= _nodeTime[0]);  // EndTime must come at or after our first node (it can be infinite) 
            Debug.Assert(_nodeTime[_count - 1] >= beginTime);  // Our last node must come at least at begin time (since we must intersect the active period)
            Debug.Assert(endTime.HasValue || fillDuration == TimeSpan.Zero);   // Either endTime is finite, or it's infinite hence we cannot have any fill zone 
            Debug.Assert(!period.HasTimeSpan || period.TimeSpan > TimeSpan.Zero || (endTime.HasValue && beginTime == endTime));  // Check the consistency of degenerate case where simple duration is zero; expiration time should equal beginTime 
            Debug.Assert(!_nodeIsInterval[_count - 1]);  // We should not have an infinite domain set
 
            // We initially project all intervals into a single period of the timeline, creating a union of the projected segments.
            // Then we warp the time coordinates of the resulting TIC from domain to range, applying the effects of speed/accel/decel

            bool nullPoint = _containsNullPoint  // Start by projecting the null point directly, then check whether we fall anywhere outside of the active and fill period 

             || _nodeTime[0] < beginTime  // If we intersect space before beginTime, or... 
 
              || (endTime.HasValue && fillDuration.HasTimeSpan  // ...the active and fill periods don't stretch forever, and...
               && (_nodeTime[_count - 1] > endTime.Value + fillDuration.TimeSpan  // ...we intersect space after endTime+fill, or... 
                || (_nodeTime[_count - 1] == endTime.Value + fillDuration.TimeSpan  // ...as we fall right onto the end of fill zone...
                 && _nodeIsPoint[_count - 1] && (endTime > beginTime || fillDuration.TimeSpan > TimeSpan.Zero))));  // ...we may have a point intersection with the stopped zone

            // Now consider the main scenarios: 

            if (endTime.HasValue && beginTime == endTime)  // Degenerate case when our active period is a single point; project only the point 
            { 
                projection.InitializePoint(TimeSpan.Zero);
            } 
            else  // The case of non-zero active duration
            {
                bool includeFillPeriod = !fillDuration.HasTimeSpan || fillDuration.TimeSpan > TimeSpan.Zero;  // This variable represents whether we have a non-zero fill zone
 
                if (period.HasTimeSpan)  // We have a finite TimeSpan period and non-zero activation duration
                { 
                    TimeIntervalCollection tempCollection = new TimeIntervalCollection(); 

                    ProjectionNormalize(ref tempCollection, beginTime, endTime, includeFillPeriod, appliedSpeedRatio); 

                    long periodInTicks = period.TimeSpan.Ticks;
                    Nullable activeDuration;
                    bool includeMaxPoint; 

                    if (endTime.HasValue) 
                    { 
                        activeDuration = endTime.Value - beginTime;
                        includeMaxPoint = includeFillPeriod && (activeDuration.Value.Ticks % periodInTicks == 0);  // Fill starts at a boundary 
                    }
                    else
                    {
                        activeDuration = null; 
                        includeMaxPoint = false;
                    } 
 
                    projection.EnsureAllocatedCapacity(_minimumCapacity);
                    tempCollection.ProjectionFold(ref projection, activeDuration, periodInTicks, isAutoReversed, includeMaxPoint); 

                    if (accelRatio + decelRatio > 0)
                    {
                        projection.ProjectionWarp(periodInTicks, accelRatio, decelRatio); 
                    }
                } 
                else  // Infinite period degenerate case; we perform straight 1-1 linear mapping, offset by begin time and clipped 
                {
                    ProjectionNormalize(ref projection, beginTime, endTime, includeFillPeriod, appliedSpeedRatio); 
                }
            }

            projection._containsNullPoint = nullPoint;  // Ensure we have the null point properly set 
        }
 
        ///  
        /// Performs the NORMALIZE operation, as described in the comments to the general projection function.
        /// Clip begin and end times, normalize by beginTime, scale by speedRatio. 
        /// 
        /// The normalized collection to create.
        /// Begin time of the active period for clipping.
        /// End time of the active period for clipping. 
        /// The ratio by which to scale begin and end time.
        /// Whether a non-zero fill period exists. 
        private void ProjectionNormalize(ref TimeIntervalCollection projection, 
                                         TimeSpan beginTime, Nullable endTime, bool includeFillPeriod, double speedRatio)
        { 
            Debug.Assert(!IsEmptyOfRealPoints);
            Debug.Assert(projection.IsEmpty);

            projection.EnsureAllocatedCapacity(this._nodeTime.Length); 

            this.MoveFirst(); 
            projection.MoveFirst(); 

            // Get to the non-clipped zone; we must overlap the active zone, so we should terminate at some point. 
            while (!CurrentIsAtLastNode && NextNodeTime <= beginTime)
            {
                MoveNext();
            } 

            if (CurrentNodeTime < beginTime)  // This means we have an interval clipped by beginTime 
            { 
                if (CurrentNodeIsInterval)
                { 
                    projection._count++;
                    projection.CurrentNodeTime = TimeSpan.Zero;
                    projection.CurrentNodeIsPoint = true;
                    projection.CurrentNodeIsInterval = true; 
                    projection.MoveNext();
                } 
                this.MoveNext(); 
            }
 
            while(_current < _count && (!endTime.HasValue || CurrentNodeTime < endTime))  // Copy the main set of segments, transforming them
            {
                double timeOffset = (double)((this.CurrentNodeTime - beginTime).Ticks);
 
                projection._count++;
                projection.CurrentNodeTime = TimeSpan.FromTicks((long)(speedRatio * timeOffset)); 
                projection.CurrentNodeIsPoint = this.CurrentNodeIsPoint; 
                projection.CurrentNodeIsInterval = this.CurrentNodeIsInterval;
 
                projection.MoveNext();
                this.MoveNext();
            }
 
            Debug.Assert(_current > 0);  // The only way _current could stay at zero is if the collection begins at (or past) the end of active period
            if (_current < _count  // We have an interval reaching beyond the active zone, clip that interval 
             && (_nodeIsInterval[_current - 1] 
              || (CurrentNodeTime == endTime.Value && CurrentNodeIsPoint && includeFillPeriod)))
            { 
                Debug.Assert(endTime.HasValue && CurrentNodeTime >= endTime.Value);

                double timeOffset = (double)((endTime.Value - beginTime).Ticks);
 
                projection._count++;
                projection.CurrentNodeTime = TimeSpan.FromTicks((long)(speedRatio * timeOffset)); 
                projection.CurrentNodeIsPoint = includeFillPeriod && (CurrentNodeTime > endTime.Value || CurrentNodeIsPoint); 
                projection.CurrentNodeIsInterval = false;
            } 
        }

        /// 
        /// Performs the FOLD operation, as described in the comments to the general projection function. 
        /// We assume this method is only called with a finite, non-zero period length.
        /// The TIC is normalized so beginTime = 0. 
        /// NOTE: projection should have allocated arrays. 
        /// 
        /// The output projection. 
        /// The duration of the active period.
        /// The length of a simple duration in ticks.
        /// Whether we have auto-reversing.
        /// Whether the fill zone forces the max point to be included. 
        private void ProjectionFold(ref TimeIntervalCollection projection, Nullable activeDuration,
                                    long periodInTicks, bool isAutoReversed, bool includeMaxPoint) 
        { 
            Debug.Assert(!IsEmptyOfRealPoints);  // The entire projection process assumes we are not empty (have an intersection with the active zone).
            Debug.Assert(periodInTicks > 0);  // We do not handle the degenerate case here. 

            // Find the smallest n such that _nodeTime[n+1] > beginTime; if n is the last index, then consider _nodeTime[n+1] to be infinity
            MoveFirst();
            Debug.Assert(CurrentNodeTime >= TimeSpan.Zero);  // Verify that we are already clipped 

            bool quitFlag = false; 
 
            // As we walk, we maintain the invarant that the interval BEFORE _current is not included.
            // Otherwise we handle the interval and skip the interval's last node. 

            // Process the remaining points and segments
            do
            { 
                if (CurrentNodeIsInterval)  // Project the interval starting here
                { 
                    quitFlag = ProjectionFoldInterval(ref projection, activeDuration, periodInTicks, isAutoReversed, includeMaxPoint);  // Project and break up the clipped segment 
                    _current += NextNodeIsInterval ? 1 : 2;  // Step over the next node if it's merely the end of this interval
                } 
                else  // This must be a lone point; the previous interval is no included by our invariant
                {
                    Debug.Assert(CurrentNodeIsPoint);
                    ProjectionFoldPoint(ref projection, activeDuration, periodInTicks, isAutoReversed, includeMaxPoint); 
                    _current++;
                } 
 
            } while (!quitFlag && (_current < _count));
            // While we haven't run out of indices, and haven't moved past endTime 
        }

        /// 
        /// Take a single projection point and insert into the output collection. 
        /// NOTE: projection should have allocated arrays.
        ///  
        /// The output collection. 
        /// The duration of the active period.
        /// The length of a simple duration in ticks. 
        /// Whether autoreversing is enabled
        /// Whether the fill zone forces the max point to be included.
        private void ProjectionFoldPoint(ref TimeIntervalCollection projection, Nullable activeDuration,
                                         long periodInTicks, bool isAutoReversed, bool includeMaxPoint) 
        {
            Debug.Assert(CurrentNodeIsPoint);  // We should only call this method when we project a legitimate point 
            Debug.Assert(!CurrentNodeIsInterval); 

            long currentProjection; 
            if (isAutoReversed)  // Take autoreversing into account
            {
                long doublePeriod = periodInTicks << 1;
                currentProjection = CurrentNodeTime.Ticks % doublePeriod; 

                if (currentProjection > periodInTicks) 
                { 
                    currentProjection = doublePeriod - currentProjection;
                } 
            }
            else  // No autoReversing
            {
                if (includeMaxPoint && activeDuration.HasValue && CurrentNodeTime == activeDuration) 
                {
                    currentProjection = periodInTicks;  // Exceptional end case: we are exactly at the last point 
                } 
                else
                { 
                    currentProjection = CurrentNodeTime.Ticks % periodInTicks;
                }
            }
 
            projection.MergePoint(TimeSpan.FromTicks(currentProjection));
        } 
 
        /// 
        /// Take a single projection segment [CurrentNodeTime, NextNodeTime], break it into parts and merge the 
        /// folded parts into this collection.
        /// NOTE: the TIC is normalized so beginTime = TimeSpan.Zero and we are already clipped.
        /// NOTE: projection should have allocated arrays.
        ///  
        /// The output projection.
        /// The duration of the active period. 
        /// The length of a simple duration in ticks. 
        /// Whether autoreversing is enabled
        /// Whether the fill zone forces the max point to be included. 
        private bool ProjectionFoldInterval(ref TimeIntervalCollection projection, Nullable activeDuration,
                                            long periodInTicks, bool isAutoReversed, bool includeMaxPoint)
        {
            // Project the begin point for the segment, then look if we are autoreversing or not. 
            long intervalLength = (NextNodeTime - CurrentNodeTime).Ticks;
            long timeBeforeNextPeriod, currentProjection; 
 
            // Now see how the segment falls across periodic boundaries:
            // Case 1: segment stretches across a full period (we can exit early, since we cover the entire range of values) 
            // Case 2: NON-AUTEREVERSED: segment stretches across two partial periods (we need to split into two segments and insert them into the projection)
            // Case 2: AUTOREVERSED: we need to pick the larger half of the partial period and project only that half, since it fully overlaps the other.
            // Case 3: segment is fully contained within a single period (just add the segment into the projection)
            // These cases are handled very differently for AutoReversing and non-AutoReversing timelines. 

            if (isAutoReversed)  // In the autoreversed case, we "fold" the segment onto itself and eliminate the redundant parts 
            { 
                bool beginOnReversingArc;
                long doublePeriod = periodInTicks << 1; 
                currentProjection = CurrentNodeTime.Ticks % doublePeriod;

                if (currentProjection < periodInTicks)  // We are on a forward-moving segment
                { 
                    beginOnReversingArc = false;
                    timeBeforeNextPeriod = periodInTicks - currentProjection; 
                } 
                else  // We are on a reversing segment, adjust the values accordingly
                { 
                    beginOnReversingArc = true;
                    currentProjection = doublePeriod - currentProjection;
                    timeBeforeNextPeriod = currentProjection;
                } 

                Debug.Assert(timeBeforeNextPeriod > 0); 
 
                long timeAfterNextPeriod = intervalLength - timeBeforeNextPeriod;  // How much of our interval protrudes into the next period(s); this may be negative if we don't reach it.
                // See which part of the segment -- before or after part -- "dominates" when we fold them unto each other. 
                if (timeAfterNextPeriod > 0)  // Case 1 or 2: we reach into the next period but don't know if we completely cover it
                {
                    bool collectionIsSaturated;
 
                    if (timeBeforeNextPeriod >= timeAfterNextPeriod)  // Before "dominates"
                    { 
                        bool includeTime = CurrentNodeIsPoint; 

                        if (timeBeforeNextPeriod == timeAfterNextPeriod)  // Corner case where before and after overlap exactly, find the IsPoint union 
                        {
                            includeTime = includeTime || NextNodeIsPoint;
                        }
 
                        if (beginOnReversingArc)
                        { 
                            projection.MergeInterval(TimeSpan.Zero,                         true, 
                                                     TimeSpan.FromTicks(currentProjection), includeTime);
                            collectionIsSaturated = includeTime && (currentProjection == periodInTicks); 
                        }
                        else
                        {
                            projection.MergeInterval(TimeSpan.FromTicks(currentProjection), includeTime, 
                                                     TimeSpan.FromTicks(periodInTicks),     true);
                            collectionIsSaturated = includeTime && (currentProjection == 0); 
                        } 
                    }
                    else  // After "dominates" 
                    {
                        if (beginOnReversingArc)
                        {
                            long clippedTime = timeAfterNextPeriod < periodInTicks ? timeAfterNextPeriod : periodInTicks; 

                            projection.MergeInterval(TimeSpan.Zero,                   true, 
                                                     TimeSpan.FromTicks(clippedTime), NextNodeIsPoint); 
                            collectionIsSaturated = NextNodeIsPoint && (clippedTime == periodInTicks);
                        } 
                        else
                        {
                            long clippedTime = timeAfterNextPeriod < periodInTicks ? periodInTicks - timeAfterNextPeriod : 0;
 
                            projection.MergeInterval(TimeSpan.FromTicks(clippedTime),   NextNodeIsPoint,
                                                     TimeSpan.FromTicks(periodInTicks), true); 
                            collectionIsSaturated = NextNodeIsPoint && (clippedTime == 0); 
                        }
                    } 
                    return collectionIsSaturated;  // See if we just saturated the collection
                }
                else  // Case 3: timeAfterNextPeriod < 0, we are fully contained in the current period
                { 
                    // No need to split anything, insert the interval directly
                    if (beginOnReversingArc)  // Here the nodes are reversed 
                    { 
                        projection.MergeInterval(TimeSpan.FromTicks(currentProjection - intervalLength), NextNodeIsPoint,
                                                 TimeSpan.FromTicks(currentProjection),                  CurrentNodeIsPoint); 
                    }
                    else
                    {
                        projection.MergeInterval(TimeSpan.FromTicks(currentProjection),                  CurrentNodeIsPoint, 
                                                 TimeSpan.FromTicks(currentProjection + intervalLength), NextNodeIsPoint);
                    } 
                    return false;  // Keep computing the projection 
                }
            } 
            else  // No AutoReversing
            {
                currentProjection = CurrentNodeTime.Ticks % periodInTicks;
                timeBeforeNextPeriod = periodInTicks - currentProjection; 

                // The only way to get 0 is if we clipped by endTime which equals CurrentNodeTime, which should not have been allowed 
                Debug.Assert(intervalLength > 0); 

                if (intervalLength > periodInTicks)  // Case 1. We may stretch across a whole arc, even if we start from the end and wrap back around 
                {
                    // Quickly transform the collection into a saturated collection
                    projection._nodeTime[0] = TimeSpan.Zero;
                    projection._nodeIsPoint[0] = true; 
                    projection._nodeIsInterval[0] = true;
 
                    projection._nodeTime[1] = TimeSpan.FromTicks(periodInTicks); 
                    projection._nodeIsPoint[1] = includeMaxPoint;
                    projection._nodeIsInterval[1] = false; 

                    _count = 2;
                    return true;  // Bail early, we have the result ready
                } 
                else if (intervalLength >= timeBeforeNextPeriod)  // Case 2. We stretch until the next period begins (but not long enough to cover the length of a full period)
                { 
                    // Split the segment into two projected segments by wrapping around the period boundary 
                    projection.MergeInterval(TimeSpan.FromTicks(currentProjection),                     CurrentNodeIsPoint,
                                             TimeSpan.FromTicks(periodInTicks),                         false); 
                    if (intervalLength > timeBeforeNextPeriod)  // See if we have a legitimate interval in the second clipped part
                    {
                        projection.MergeInterval(TimeSpan.Zero,                                             true,
                                                 TimeSpan.FromTicks(intervalLength - timeBeforeNextPeriod), NextNodeIsPoint); 
                    }
                    else if (NextNodeIsPoint)  // We only seem to have a point, wrapped around at zero (or in the exceptional case, at the max) 
                    { 
                        if (includeMaxPoint && activeDuration.HasValue && NextNodeTime == activeDuration)  // Exceptional end case: we are exactly at the last point
                        { 
                            projection.MergePoint(TimeSpan.FromTicks(periodInTicks));
                        }
                        else
                        { 
                            projection.MergePoint(TimeSpan.Zero);
                        } 
                    } 
                    return false;  // Keep computing the projection
                } 
                else  // Case 3: We fall within a single period
                {
                    // No need to split anything, insert the interval directly
                    projection.MergeInterval(TimeSpan.FromTicks(currentProjection),                    CurrentNodeIsPoint, 
                                             TimeSpan.FromTicks(currentProjection + intervalLength),   NextNodeIsPoint);
                    return false;  // Keep computing the projection 
                } 
            }
        } 

        /// 
        /// Merges a point into this collection so it becomes the union of itself and the point.
        /// Consequentialy, this does nothing if the point is already a subset of the collection; 
        /// Otherwise adjusts the collection so that the result obeys the rules of a proper TIC.
        /// NOTE: _current will shift so as to be the same distance from the end as before. 
        ///  
        /// The point to merge.
        private void MergePoint(TimeSpan point) 
        {
            int index = Locate(point);

            if (index >= 0 && _nodeTime[index] == point)  // Point coincides with an existing node 
            {
                if(!_nodeIsPoint[index])  // The node is not already in the TIC 
                { 
                    // See if we need to insert the node, or cancel out the node when it "saturates" an interval-point-interval segment
                    if (index == 0 || !_nodeIsInterval[index - 1] || !_nodeIsInterval[index]) 
                    {
                        _nodeIsPoint[index] = true;
                    }
                    else  // Else we should cancel the node as it is redundant (===O=== saturated case) 
                    {
                        for (int n = index; n + 1 < _count; n++)  // Shift over the contents 
                        { 
                            _nodeTime[n]       = _nodeTime[n + 1];
                            _nodeIsPoint[n]    = _nodeIsPoint[n + 1]; 
                            _nodeIsInterval[n] = _nodeIsInterval[n + 1];
                        }
                        _count--;
                    } 
                }
            } 
            else if (index == -1 || !_nodeIsInterval[index])  // Point falls within the interior of a non-included interval 
            {
                Debug.Assert(index == -1 || _nodeTime[index] < point); 

                // Then we need to insert a point into the collection
                EnsureAllocatedCapacity(_count + 1);
 
                for (int n = _count - 1; n > index; n--)  // Shift over the contents
                { 
                    _nodeTime[n + 1]       = _nodeTime[n]; 
                    _nodeIsPoint[n + 1]    = _nodeIsPoint[n];
                    _nodeIsInterval[n + 1] = _nodeIsInterval[n]; 
                }
                _nodeTime[index + 1]       = point;  // Insert the node
                _nodeIsPoint[index + 1]    = true;
                _nodeIsInterval[index + 1] = false; 

                _count++; 
            } 
        }
 
        /// 
        /// Merges an interval into this collection so it becomes the union of itself and the interval.
        /// Consequentialy, this does nothing if the interval is already a subset of the collection;
        /// Otherwise adjusts the collection so that the result obeys the rules of a proper TIC. 
        /// 
        /// Start of the interval. 
        /// Whether the start point is included. 
        /// End of the interval.
        /// Whether the end point is included. 
        private void MergeInterval(TimeSpan from, bool includeFrom,
                                   TimeSpan to,   bool includeTo)
        {
            Debug.Assert(from < to);  // Our code should never call MergeInterval for a point or reversed interval 

            if (IsEmptyOfRealPoints)  // We have no points yet, simply create a new collection with those points 
            { 
                _nodeTime[0] = from;
                _nodeIsPoint[0] = includeFrom; 
                _nodeIsInterval[0] = true;

                _nodeTime[1] = to;
                _nodeIsPoint[1] = includeTo; 
                _nodeIsInterval[1] = false;
 
                _count = 2; 
            }
            else  // We are not empty, hence there must be existing intervals allocated and assigned 
            {
                Debug.Assert(_nodeTime.Length >= _minimumCapacity);  // Assert that we indeed have memory allocated

                int fromIndex = Locate(from);  // Find the nearest nodes to the left of from and to (possibly equal) 
                int toIndex   = Locate(to);
 
                // From a structural standpoint, we do the following: 
                //  before  ----o---o----?----o---o---?----o----  (? means there may or may not be a node here)
                //                       F            T 
                //  after   ----o---o----?------------?----o----  (? means the node may be added, kept, or removed here)

                // The array reshuffling takes place as following:
                // 1) Check if more memory is needed, then dynamically resize and move the contents to new arrays 
                // 2) Perform in-place blitting depending whether we contract or expand the array
 
                bool insertNodeAtFrom = false; 
                bool insertNodeAtTo   = false;
 
                int netIncreaseInNodes = fromIndex - toIndex;  // The default is we remove all the "intermediate" nodes
                int nextInsertionIndex = fromIndex + 1;  // Place to begin inserting new nodes if needed; by default start from [fromIndex+1]
                int lastNodeToDelete   = toIndex;  // By default, delete nodes up through [toIndex]
 
                // If FROM falls within an interval, and we don't have IntervalIncluded, create a node here.
                //   Otherwise don't create that node. 
                // Else FROM coincides with a node; if we have PreviousIntervalIncluded && (CoincidingNode||includeStart), cancel the saturated node. 
                //   Otherwise keep that node.
 
                if (fromIndex == -1 || _nodeTime[fromIndex] < from)  // We don't fall exactly onto a preexisting node
                {
                    // Keep the node at fromIndex; see if we need to insert a new node
 
                    if (fromIndex == -1 || !_nodeIsInterval[fromIndex])
                    { 
                        insertNodeAtFrom = true; 
                        netIncreaseInNodes++;  // We previously assumed we don't insert any new nodes
                    } 
                }
                else  // We fall exactly onto a preexisting node; in this case, it is redundant to insert another node here.
                {
                    Debug.Assert(_nodeTime[fromIndex] == from); 

                    if (fromIndex > 0 && _nodeIsInterval[fromIndex - 1]  // Delete the node at fromIndex, it will become saturated 
                      && (includeFrom || _nodeIsPoint[fromIndex])) 
                    {
                        netIncreaseInNodes--;  // We previously assumed that we would NOT delete the node at fromIndex 
                        nextInsertionIndex--;
                    }
                    else  // Keep the node at fromIndex
                    { 
                        _nodeIsPoint[fromIndex] = includeFrom || _nodeIsPoint[fromIndex];  // Update the node's IsPoint status
                    } 
                } 

                // If TO falls within an interval, and we don't have IntervalIncluded, create a node here. 
                //   Otherwise don't create that node.
                // Else TO coincides with a node; if we have (IncludeCoincidingNode||includeEnd) && IntervalIncluded, allow the node to be deleted
                //   Otherwise arrange to keep that node (this is not what we do by default).
                if (toIndex == -1 || _nodeTime[toIndex] < to)  // We don't fall exactly onto a preexisting node 
                {
                    // The previous node is strictly smaller, so it is redundant and we allow it to be deleted. 
                    // We don't decrement netIncreaseInNodes here because we assumed that we delete the node at toIndex 

                    if (toIndex == -1 || !_nodeIsInterval[toIndex])  // If we aren't inside an included interval, insert a node 
                    {
                        insertNodeAtTo = true;
                        netIncreaseInNodes++;  // We previously assumed we don't insert any new nodes
                    } 
                }
                else  // We fall exactly onto a preexisting node; in this case, it is redundant to insert another node here. 
                { 
                    Debug.Assert(_nodeTime[toIndex] == to);
                    Debug.Assert(fromIndex < toIndex); 

                    // The default is we delete the node at toIndex, unless it does not saturate the resulting TIC.

                    if (!_nodeIsInterval[toIndex] || (!includeTo && !_nodeIsPoint[toIndex])) // Keep the node at toIndex, it is not going to be saturated 
                    {
                        // We previously assumed that we WOULD delete the node at toIndex, now it turns out we should keep it 
                        netIncreaseInNodes++; 
                        lastNodeToDelete--;
 
                        _nodeIsPoint[toIndex] = includeTo || _nodeIsPoint[toIndex];  // Update the node's IsPoint status
                    }
                }
 
                // Eliminate all nodes with index FROM <= index <= TOINDEX, observing deletion rules:
                // 
                //        Index:   fromIndex==toIndex 
                // ShouldDelete:       no(default)
                // 
                //        Index:    fromIndex      toIndex
                // ShouldDelete:   no(default)   yes(default)
                //
                //        Index:    fromIndex    a    b    c     toIndex 
                // ShouldDelete:   no(default)  yes  yes  yes  yes(default)
                // 
 
                // The effect of the move on the array is that we make the transition:
                //   AAA[DDDD]BBB  -->  AAA[II]BBB 
                // Where we can have any number of D's (deleted nodes) and from 0 to 2 I's (inserted nodes).
                // What we need to find is how many A's and B's we have, and which way to shift them.

                Debug.Assert(_count + netIncreaseInNodes >= 2);  // We should never shrink past size 2 

                if (netIncreaseInNodes > 0)  // We need to grow the array 
                { 
                    EnsureAllocatedCapacity(_count + netIncreaseInNodes);  // Make sure we have enough space allocated
                    for (int n = _count - 1; n > lastNodeToDelete; n--) 
                    {
                        _nodeTime[n + netIncreaseInNodes]       = _nodeTime[n];
                        _nodeIsPoint[n + netIncreaseInNodes]    = _nodeIsPoint[n];
                        _nodeIsInterval[n + netIncreaseInNodes] = _nodeIsInterval[n]; 
                    }
                } 
                else if (netIncreaseInNodes < 0)  // We need to shrink the array 
                {
                    // Copy the elements 
                    for (int n = lastNodeToDelete + 1; n < _count; n++)
                    {
                        _nodeTime[n + netIncreaseInNodes]       = _nodeTime[n];  // Note that netIncreaseInNodes is negative here
                        _nodeIsPoint[n + netIncreaseInNodes]    = _nodeIsPoint[n]; 
                        _nodeIsInterval[n + netIncreaseInNodes] = _nodeIsInterval[n];
                    } 
                } 

                _count += netIncreaseInNodes;  // Update the array size 

                if (insertNodeAtFrom)
                {
                    _nodeTime[nextInsertionIndex]       = from; 
                    _nodeIsPoint[nextInsertionIndex]    = includeFrom;
                    _nodeIsInterval[nextInsertionIndex] = true;  // We are inserting an interval, so this is true 
 
                    nextInsertionIndex++;
                } 

                if (insertNodeAtTo)
                {
                    _nodeTime[nextInsertionIndex]       = to; 
                    _nodeIsPoint[nextInsertionIndex]    = includeTo;
                    _nodeIsInterval[nextInsertionIndex] = false;  // We are terminating an interval, so this is false 
                } 
            }
        } 


        private void EnsureAllocatedCapacity(int requiredCapacity)
        { 
            if (_nodeTime == null)
            { 
                Debug.Assert(_nodeIsPoint == null); 
                Debug.Assert(_nodeIsInterval == null);
 
                _nodeTime = new TimeSpan[requiredCapacity];
                _nodeIsPoint = new bool[requiredCapacity];
                _nodeIsInterval = new bool[requiredCapacity];
            } 
            else if (_nodeTime.Length < requiredCapacity)  // We may need to grow by up to 2 units
            { 
                Debug.Assert(_nodeIsPoint != null); 
                Debug.Assert(_nodeIsInterval != null);
 
                int newCapacity = _nodeTime.Length << 1;  // Dynamically grow by a factor of 2

                TimeSpan[] newNodeTime   = new TimeSpan[newCapacity];
                bool[] newNodeIsPoint    = new bool[newCapacity]; 
                bool[] newNodeIsInterval = new bool[newCapacity];
 
                for (int n = 0; n < _count; n++) 
                {
                    newNodeTime[n]       = _nodeTime[n]; 
                    newNodeIsPoint[n]    = _nodeIsPoint[n];
                    newNodeIsInterval[n] = _nodeIsInterval[n];
                }
 
                _nodeTime       = newNodeTime;
                _nodeIsPoint    = newNodeIsPoint; 
                _nodeIsInterval = newNodeIsInterval; 
            }
        } 


        /// 
        /// Apply the effects of Accel, Decel to the nodes in this TIC. 
        /// This should ONLY get called when the period in finite and non-zero, and accel+decel > 0.
        ///  
        /// The length of a simple duration in ticks. 
        /// The accelerating fraction of the simple duration.
        /// The decelerating fraction of the simple duration. 
        private void ProjectionWarp(long periodInTicks, double accelRatio, double decelRatio)
        {
            Debug.Assert(periodInTicks > 0);
            Debug.Assert(accelRatio + decelRatio > 0); 

            double dpPeriod = (double)periodInTicks; 
            double inversePeriod = 1 / dpPeriod; 
            double halfMaxRate = 1 / (2 - accelRatio - decelRatio);  // Constants to simplify
 
            TimeSpan accelEnd = TimeSpan.FromTicks((long)(dpPeriod * accelRatio));
            TimeSpan decelStart = TimeSpan.FromTicks(periodInTicks - (long)(dpPeriod * decelRatio));

            double t;  // Current progress, which ranges from 0 to 1 

            MoveFirst(); 
 
            // Perform accel warping
            while (_current < _count && CurrentNodeTime < accelEnd) 
            {
                t = (double)_nodeTime[_current].Ticks;
                _nodeTime[_current] = TimeSpan.FromTicks((long)(halfMaxRate * inversePeriod * t * t / accelRatio));
                MoveNext(); 
            }
 
            // Perform linear zone warping 
            while (_current < _count && CurrentNodeTime <= decelStart)  // We bias the edge points towards the simpler linear computation, which yields the same result
            { 
                t = (double)_nodeTime[_current].Ticks;
                _nodeTime[_current] = TimeSpan.FromTicks((long)(halfMaxRate * (2 * t - (accelRatio * dpPeriod))));
                MoveNext();
            } 

            // Perform decel warping 
            while (_current < _count) 
            {
                t = (double)(periodInTicks - _nodeTime[_current].Ticks);  // We actually use the complement from 100% progress 
                _nodeTime[_current] = TimeSpan.FromTicks(periodInTicks - (long)(halfMaxRate * inversePeriod * t * t / decelRatio));
                MoveNext();
            }
        } 

#if TEST_TIMING_CODE 
        ///  
        /// Creates several collections and runs test operations on them
        ///  
        static internal void RunDiagnostics()
        {
            TimeIntervalCollection t = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.85));
            TimeIntervalCollection t2; 

            // Case 1      --x--*----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.70)); 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t)); 
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.70)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            // Empty
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0, 0, false)); 
            // Accel only
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.3, 0, false));
            // Decel only
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0),
                                                         TimeSpan.FromSeconds(1.0), 1, 0, 0.3, false)); 
            // Accel+decel
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.1, 0.3, false)); 
            // Accel+decel+autoreverse (boundary case 1)
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.3, 0.1, true));
            // Accel+decel+autoreverse (boundary case 2)
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0),
                                                         TimeSpan.FromSeconds(1.0), 1, 0.301, 0.1, true)); 
            // Accel+decel+autoreverse disabled for check
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.3, 0.1, false)); 
            // Insufficient decel to provoke intersection
            Debug.Assert(!t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.1, 0.2, false));
            // Autoreverse-only
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(1.7),
                                                         TimeSpan.FromSeconds(1.0), 1, 0, 0, true)); 
            // Large decel zone
            Debug.Assert(t2.IntersectsPeriodicCollection(TimeSpan.FromSeconds(2.0), 
                                                         TimeSpan.FromSeconds(1.0), 1, 0.1, 0.5, false)); 

            // Case 2      -----x----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.85));
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t.Contains(TimeSpan.FromSeconds(3.85))); 
            Debug.Assert(!t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 
 
            // Case 3      -----*--x--
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.95)); 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            t.Clear(); 

            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.70)));  // No intersection with empty set 
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.85)));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.95)));

            t = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)); 

            // Case 1      --x--*=====.----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.7)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.70)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 2      -----x=====.----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.85)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t.Contains(TimeSpan.FromSeconds(3.85)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 

            // Case 3      -----*==x==.----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.90)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t.Contains(TimeSpan.FromSeconds(3.90)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 

            // Case 4      -----*=====x----- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(3.95)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 5      -----*=====.--x-- 
            t2 = TimeIntervalCollection.CreatePoint(TimeSpan.FromSeconds(4.00)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t.Contains(TimeSpan.FromSeconds(4.00)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            //// Case 1      --x--*=====.-----    (x is the starting point for t2) 
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.75));
 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.85)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t));
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.90)); 
 
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(3.95));
 
            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(!t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.7), TimeSpan.FromSeconds(4.0)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(!t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));

            //// Case 2      -----x=====.-----    (x is the starting point for t2)
 
            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.90));
 
            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(!t.IntersectsInverseOf(t2)); 
            Debug.Assert(!t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(4.0));
 
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(!t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 3      -----*==x==.-----    (x is the starting point for t2)

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.87), TimeSpan.FromSeconds(3.90)); 

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(!t2.IntersectsInverseOf(t));

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.87), TimeSpan.FromSeconds(3.95));
 
            Debug.Assert(t.Intersects(t2));
            Debug.Assert(t2.Intersects(t)); 
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(!t2.IntersectsInverseOf(t)); 

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.87), TimeSpan.FromSeconds(4.0));

            Debug.Assert(t.Intersects(t2)); 
            Debug.Assert(t2.Intersects(t));
            Debug.Assert(t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));
 
            // Case 4      -----*=====x-----    (x is the starting point for t2)

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.95), TimeSpan.FromSeconds(4.0));
 
            Debug.Assert(!t.Intersects(t2));
            Debug.Assert(!t2.Intersects(t)); 
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95))); 
            Debug.Assert(t.IntersectsInverseOf(t2));
            Debug.Assert(t2.IntersectsInverseOf(t)); 

            // Case 5      -----*=====.--x--    (x is the starting point for t2)

            t2 = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3.98), TimeSpan.FromSeconds(4.0)); 

            Debug.Assert(!t.Intersects(t2)); 
            Debug.Assert(!t2.Intersects(t)); 
            Debug.Assert(!t2.Intersects(TimeSpan.FromSeconds(3.85), TimeSpan.FromSeconds(3.95)));
            Debug.Assert(t.IntersectsInverseOf(t2)); 
            Debug.Assert(t2.IntersectsInverseOf(t));

            // Merge testing
            t = TimeIntervalCollection.CreateClosedOpenInterval(TimeSpan.FromSeconds(3), TimeSpan.FromSeconds(5.5)); 
            t.MergePoint(TimeSpan.FromSeconds(8));
            t.MergePoint(TimeSpan.FromSeconds(12)); 
            t.MergeInterval(TimeSpan.FromSeconds(14.5), true, TimeSpan.FromSeconds(19), true); 

            //t2 = t.ProjectOntoPeriodicFunction(beginTime, endTime, 
            //                                   fillDuration, period,
            //                                   appliedSpeedRatio, accelRatio, decelRatio, isAutoReversed);
            t2.Clear();
            t.ProjectOntoPeriodicFunction(ref t2, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4), 
                                               Duration.Forever, Duration.Forever,
                                               1, 0, 0, false); 
            t2.Clear(); 
            t.ProjectOntoPeriodicFunction(ref t2, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4),
                                               Duration.Forever, TimeSpan.FromSeconds(10), 
                                               1, 0, 0, false);
            t2.Clear();
            t.ProjectOntoPeriodicFunction(ref t2, TimeSpan.FromSeconds(0), TimeSpan.FromSeconds(17),
                                               Duration.Forever, TimeSpan.FromSeconds(4), 
                                               1, 0, 0, true);
        } 
#endif 

 
        #endregion // Methods
        #endregion // External interface

        #region Private 

        ///  
        /// Sets _current to the largest index N where nodeTime[N] is less or equal to time. 
        /// Returns -1 if no such index N exists.
        ///  
        /// 
        /// Uses a binary search to curb worst-case time to log2(_count)
        /// 
        private int Locate(TimeSpan time) 
        {
            if (_count == 0 || time < _nodeTime[0]) 
            { 
                return -1;
            } 
            else  // time is at least at the first node
            {
                Debug.Assert(_count > 0);  // Count cannot be negative
 
                int current;
                int left = 0; 
                int right = _count - 1; 

                // Maintain invariant: T[left] < time < T[right] 
                while (left + 1 < right)  // Compute until we have at most 1-unit long interval
                {
                    current = (left + right) >> 1;  // Fast divide by 2
                    if (time < _nodeTime[current]) 
                    {
                        right = current; 
                    } 
                    else  // time >= nodeTime[current]
                    { 
                        left = current;
                    }
                }
 
                if (time < _nodeTime[right])
                { 
                    return left; 
                }
                else  // This case should only be reached when we are at or past the last node 
                {
                    Debug.Assert(right == _count - 1);
                    return right;
                } 
            }
        } 
 
        internal bool IsEmptyOfRealPoints
        { 
            get
            {
                return (_count == 0);
            } 
        }
 
        internal bool IsEmpty 
        {
            get 
            {
                return (_count == 0 && !_containsNullPoint);
            }
        } 

        private void MoveFirst() 
        { 
            _current = 0;
        } 

        private void MoveNext()
        {
            _current++; 
            Debug.Assert(_current <= _count);
        } 
 
        private bool CurrentIsAtLastNode
        { 
            get
            {
                return (_current + 1 == _count);
            } 
        }
 
        private TimeSpan CurrentNodeTime 
        {
            get 
            {
                Debug.Assert(_current < _count);
                return _nodeTime[_current];
            } 
            set
            { 
                Debug.Assert(_current < _count); 
                _nodeTime[_current] = value;
            } 
        }

        private bool CurrentNodeIsPoint
        { 
            get
            { 
                Debug.Assert(_current < _count); 
                return _nodeIsPoint[_current] ^ _invertCollection;
            } 
            set
            {
                Debug.Assert(_current < _count);
                _nodeIsPoint[_current] = value; 
            }
        } 
 
        private bool CurrentNodeIsInterval
        { 
            get
            {
                Debug.Assert(_current < _count);
                return _nodeIsInterval[_current] ^ _invertCollection; 
            }
            set 
            { 
                Debug.Assert(_current < _count);
                _nodeIsInterval[_current] = value; 
            }
        }

        private TimeSpan NextNodeTime 
        {
            get 
            { 
                Debug.Assert(_current + 1 < _count);
                return _nodeTime[_current + 1]; 
            }
        }

        private bool NextNodeIsPoint 
        {
            get 
            { 
                Debug.Assert(_current + 1 < _count);
                return _nodeIsPoint[_current + 1] ^ _invertCollection; 
            }
        }

        private bool NextNodeIsInterval 
        {
            get 
            { 
                Debug.Assert(_current + 1 < _count);
                return _nodeIsInterval[_current + 1] ^ _invertCollection; 
            }
        }

        internal bool ContainsNullPoint 
        {
            get 
            { 
                return _containsNullPoint ^ _invertCollection;
            } 
        }

        private void SetInvertedMode(bool mode)
        { 
            Debug.Assert(_invertCollection != mode);  // Make sure we aren't redundantly setting the mode
            _invertCollection = mode; 
        } 

        #endregion // Private 

        #region Data

        private TimeSpan[]   _nodeTime;   // An interval's begin time 
        private bool[]    _nodeIsPoint;   // Whether [begin time] is included in the interval
        private bool[] _nodeIsInterval;   // Whether the open interval (begin time)--(next begin time, or infinity) is included 
 
        private bool _containsNullPoint;  // The point representing off-domain (Stopped) state
 
        private int _count;               // How many nodes are stored in the TIC
        private int _current;             // Enumerator pointing to the current node
        private bool _invertCollection;   // A flag used for operating on the inverse of a TIC
 
        private const int _minimumCapacity = 4;  // This should be at least 2 for dynamic growth to work correctly (by 2 each time)
 
        #endregion // Data 
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK