Code Coverage Statistics for Source File

c:\Tools\SD3\src\Libraries\ICSharpCode.TextEditor\Project\Src\Document\LineManager\LineSegmentTree.cs

Sequence Point Coverage N/A 0 of 0	Branch Coverage N/A 0 of 0	Lines 477

Sequence Point Coverage

N/A

0 of 0

Branch Coverage

N/A

0 of 0

Lines

477

Highlight: Uncovered Code Covered Code


// <file>
//     <copyright see="prj:///doc/copyright.txt"/>
//     <license see="prj:///doc/license.txt"/>
//     <owner name="Daniel Grunwald" email="daniel@danielgrunwald.de"/>
//     <version>$Revision: 2683 $</version>
// </file>

using System;
using System.Collections.Generic;
using System.Diagnostics;
using ICSharpCode.TextEditor.Util;

namespace ICSharpCode.TextEditor.Document
{
	/// <summary>
	/// Data structure for efficient management of the line segments (most operations are O(lg n)).
	/// This implements an augmented red-black tree where each node has fields for the number of
	/// nodes in its subtree (like an order statistics tree) for access by index(=line number).
	/// Additionally, each node knows the total length of all segments in its subtree.
	/// This means we can find nodes by offset in O(lg n) time. Since the offset itself is not stored in
	/// the line segment but computed from the lengths stored in the tree, we adjusting the offsets when
	/// text is inserted in one line means we just have to increment the totalLength of the affected line and
	/// its parent nodes - an O(lg n) operation.
	/// However this means getting the line number or offset from a LineSegment is not a constant time
	/// operation, but takes O(lg n).
	/// 
	/// NOTE: The tree is never empty, Clear() causes it to contain an empty segment.
	/// </summary>
	sealed class LineSegmentTree : IList<LineSegment>
	{
		internal struct RBNode
		{
			internal LineSegment lineSegment;
			internal int count;
			internal int totalLength;
			
			public RBNode(LineSegment lineSegment)
			{
				this.lineSegment = lineSegment;
				this.count = 1;
				this.totalLength = lineSegment.TotalLength;
			}
			
			public override string ToString()
			{
				return "[RBNode count=" + count + " totalLength="+totalLength
					+ " lineSegment.LineNumber=" + lineSegment.LineNumber
					+ " lineSegment.Offset=" + lineSegment.Offset
					+ " lineSegment.TotalLength=" + lineSegment.TotalLength
					+ " lineSegment.DelimiterLength=" + lineSegment.DelimiterLength + "]";
			}
		}
		
		struct MyHost : IRedBlackTreeHost<RBNode>
		{
			public int Compare(RBNode x, RBNode y)
			{
				throw new NotImplementedException();
			}
			
			public bool Equals(RBNode a, RBNode b)
			{
				throw new NotImplementedException();
			}
			
			public void UpdateAfterChildrenChange(RedBlackTreeNode<RBNode> node)
			{
				int count = 1;
				int totalLength = node.val.lineSegment.TotalLength;
				if (node.left != null) {
					count += node.left.val.count;
					totalLength += node.left.val.totalLength;
				}
				if (node.right != null) {
					count += node.right.val.count;
					totalLength += node.right.val.totalLength;
				}
				if (count != node.val.count || totalLength != node.val.totalLength) {
					node.val.count = count;
					node.val.totalLength = totalLength;
					if (node.parent != null) UpdateAfterChildrenChange(node.parent);
				}
			}
			
			public void UpdateAfterRotateLeft(RedBlackTreeNode<RBNode> node)
			{
				UpdateAfterChildrenChange(node);
				UpdateAfterChildrenChange(node.parent);
			}
			
			public void UpdateAfterRotateRight(RedBlackTreeNode<RBNode> node)
			{
				UpdateAfterChildrenChange(node);
				UpdateAfterChildrenChange(node.parent);
			}
		}
		
		readonly AugmentableRedBlackTree<RBNode, MyHost> tree = new AugmentableRedBlackTree<RBNode, MyHost>(new MyHost());
		
		RedBlackTreeNode<RBNode> GetNode(int index)
		{
			if (index < 0 || index >= tree.Count)
				throw new ArgumentOutOfRangeException("index", index, "index should be between 0 and " + (tree.Count-1));
			RedBlackTreeNode<RBNode> node = tree.root;
			while (true) {
				if (node.left != null && index < node.left.val.count) {
					node = node.left;
				} else {
					if (node.left != null) {
						index -= node.left.val.count;
					}
					if (index == 0)
						return node;
					index--;
					node = node.right;
				}
			}
		}
		
		static int GetIndexFromNode(RedBlackTreeNode<RBNode> node)
		{
			int index = (node.left != null) ? node.left.val.count : 0;
			while (node.parent != null) {
				if (node == node.parent.right) {
					if (node.parent.left != null)
						index += node.parent.left.val.count;
					index++;
				}
				node = node.parent;
			}
			return index;
		}
		
		RedBlackTreeNode<RBNode> GetNodeByOffset(int offset)
		{
			if (offset < 0 || offset > this.TotalLength)
				throw new ArgumentOutOfRangeException("offset", offset, "offset should be between 0 and " + this.TotalLength);
			if (offset == this.TotalLength) {
				if (tree.root == null)
					throw new InvalidOperationException("Cannot call GetNodeByOffset while tree is empty.");
				return tree.root.RightMost;
			}
			RedBlackTreeNode<RBNode> node = tree.root;
			while (true) {
				if (node.left != null && offset < node.left.val.totalLength) {
					node = node.left;
				} else {
					if (node.left != null) {
						offset -= node.left.val.totalLength;
					}
					offset -= node.val.lineSegment.TotalLength;
					if (offset < 0)
						return node;
					node = node.right;
				}
			}
		}
		
		static int GetOffsetFromNode(RedBlackTreeNode<RBNode> node)
		{
			int offset = (node.left != null) ? node.left.val.totalLength : 0;
			while (node.parent != null) {
				if (node == node.parent.right) {
					if (node.parent.left != null)
						offset += node.parent.left.val.totalLength;
					offset += node.parent.val.lineSegment.TotalLength;
				}
				node = node.parent;
			}
			return offset;
		}
		
		public LineSegment GetByOffset(int offset)
		{
			return GetNodeByOffset(offset).val.lineSegment;
		}
		
		/// <summary>
		/// Gets the total length of all line segments. Runs in O(1).
		/// </summary>
		public int TotalLength {
			get {
				if (tree.root == null)
					return 0;
				else
					return tree.root.val.totalLength;
			}
		}
		
		/// <summary>
		/// Updates the length of a line segment. Runs in O(lg n).
		/// </summary>
		public void SetSegmentLength(LineSegment segment, int newTotalLength)
		{
			if (segment == null)
				throw new ArgumentNullException("segment");
			RedBlackTreeNode<RBNode> node = segment.treeEntry.it.node;
			segment.TotalLength = newTotalLength;
			default(MyHost).UpdateAfterChildrenChange(node);
			#if DEBUG
			CheckProperties();
			#endif
		}
		
		public void RemoveSegment(LineSegment segment)
		{
			tree.RemoveAt(segment.treeEntry.it);
			#if DEBUG
			CheckProperties();
			#endif
		}
		
		public LineSegment InsertSegmentAfter(LineSegment segment, int length)
		{
			LineSegment newSegment = new LineSegment();
			newSegment.TotalLength = length;
			newSegment.DelimiterLength = segment.DelimiterLength;
			
			newSegment.treeEntry = InsertAfter(segment.treeEntry.it.node, newSegment);
			return newSegment;
		}
		
		Enumerator InsertAfter(RedBlackTreeNode<RBNode> node, LineSegment newSegment)
		{
			RedBlackTreeNode<RBNode> newNode = new RedBlackTreeNode<RBNode>(new RBNode(newSegment));
			if (node.right == null) {
				tree.InsertAsRight(node, newNode);
			} else {
				tree.InsertAsLeft(node.right.LeftMost, newNode);
			}
			#if DEBUG
			CheckProperties();
			#endif
			return new Enumerator(new RedBlackTreeIterator<RBNode>(newNode));
		}
		
		/// <summary>
		/// Gets the number of items in the collections. Runs in O(1).
		/// </summary>
		public int Count {
			get { return tree.Count; }
		}
		
		/// <summary>
		/// Gets or sets an item by index. Runs in O(lg n).
		/// </summary>
		public LineSegment this[int index] {
			get {
				return GetNode(index).val.lineSegment;
			}
			set {
				throw new NotSupportedException();
			}
		}
		
		bool ICollection<LineSegment>.IsReadOnly {
			get { return true; }
		}
		
		/// <summary>
		/// Gets the index of an item. Runs in O(lg n).
		/// </summary>
		public int IndexOf(LineSegment item)
		{
			int index = item.LineNumber;
			if (index < 0 || index >= this.Count)
				return -1;
			if (item != this[index])
				return -1;
			return index;
		}
		
		void IList<LineSegment>.RemoveAt(int index)
		{
			throw new NotSupportedException();
		}
		
		#if DEBUG
		[Conditional("DATACONSISTENCYTEST")]
		void CheckProperties()
		{
			if (tree.root == null) {
				Debug.Assert(this.Count == 0);
			} else {
				Debug.Assert(tree.root.val.count == this.Count);
				CheckProperties(tree.root);
			}
		}
		
		void CheckProperties(RedBlackTreeNode<RBNode> node)
		{
			int count = 1;
			int totalLength = node.val.lineSegment.TotalLength;
			if (node.left != null) {
				CheckProperties(node.left);
				count += node.left.val.count;
				totalLength += node.left.val.totalLength;
			}
			if (node.right != null) {
				CheckProperties(node.right);
				count += node.right.val.count;
				totalLength += node.right.val.totalLength;
			}
			Debug.Assert(node.val.count == count);
			Debug.Assert(node.val.totalLength == totalLength);
		}
		
		public string GetTreeAsString()
		{
			return tree.GetTreeAsString();
		}
		#endif
		
		public LineSegmentTree()
		{
			Clear();
		}
		
		/// <summary>
		/// Clears the list. Runs in O(1).
		/// </summary>
		public void Clear()
		{
			tree.Clear();
			LineSegment emptySegment = new LineSegment();
			emptySegment.TotalLength = 0;
			emptySegment.DelimiterLength = 0;
			tree.Add(new RBNode(emptySegment));
			emptySegment.treeEntry = GetEnumeratorForIndex(0);
			#if DEBUG
			CheckProperties();
			#endif
		}
		
		/// <summary>
		/// Tests whether an item is in the list. Runs in O(n).
		/// </summary>
		public bool Contains(LineSegment item)
		{
			return IndexOf(item) >= 0;
		}
		
		/// <summary>
		/// Copies all elements from the list to the array.
		/// </summary>
		public void CopyTo(LineSegment[] array, int arrayIndex)
		{
			if (array == null) throw new ArgumentNullException("array");
			foreach (LineSegment val in this)
				array[arrayIndex++] = val;
		}
		
		IEnumerator<LineSegment> IEnumerable<LineSegment>.GetEnumerator()
		{
			return this.GetEnumerator();
		}
		
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}
		
		public Enumerator GetEnumerator()
		{
			return new Enumerator(tree.GetEnumerator());
		}
		
		public Enumerator GetEnumeratorForIndex(int index)
		{
			return new Enumerator(new RedBlackTreeIterator<RBNode>(GetNode(index)));
		}
		
		public Enumerator GetEnumeratorForOffset(int offset)
		{
			return new Enumerator(new RedBlackTreeIterator<RBNode>(GetNodeByOffset(offset)));
		}
		
		public struct Enumerator : IEnumerator<LineSegment>
		{
			/// <summary>
			/// An invalid enumerator value. Calling MoveNext on the invalid enumerator
			/// will always return false, accessing Current will throw an exception.
			/// </summary>
			public static readonly Enumerator Invalid = default(Enumerator);
			
			internal RedBlackTreeIterator<RBNode> it;
			
			internal Enumerator(RedBlackTreeIterator<RBNode> it)
			{
				this.it = it;
			}
			
			/// <summary>
			/// Gets the current value. Runs in O(1).
			/// </summary>
			public LineSegment Current {
				get {
					return it.Current.lineSegment;
				}
			}
			
			public bool IsValid {
				get {
					return it.IsValid;
				}
			}
			
			/// <summary>
			/// Gets the index of the current value. Runs in O(lg n).
			/// </summary>
			public int CurrentIndex {
				get {
					if (it.node == null)
						throw new InvalidOperationException();
					return GetIndexFromNode(it.node);
				}
			}
			
			/// <summary>
			/// Gets the offset of the current value. Runs in O(lg n).
			/// </summary>
			public int CurrentOffset {
				get {
					if (it.node == null)
						throw new InvalidOperationException();
					return GetOffsetFromNode(it.node);
				}
			}
			
			object System.Collections.IEnumerator.Current {
				get {
					return it.Current.lineSegment;
				}
			}
			
			public void Dispose()
			{
			}
			
			/// <summary>
			/// Moves to the next index. Runs in O(lg n), but for k calls, the combined time is only O(k+lg n).
			/// </summary>
			public bool MoveNext()
			{
				return it.MoveNext();
			}
			
			/// <summary>
			/// Moves to the previous index. Runs in O(lg n), but for k calls, the combined time is only O(k+lg n).
			/// </summary>
			public bool MoveBack()
			{
				return it.MoveBack();
			}
			
			void System.Collections.IEnumerator.Reset()
			{
				throw new NotSupportedException();
			}
		}
		
		void IList<LineSegment>.Insert(int index, LineSegment item)
		{
			throw new NotSupportedException();
		}
		
		void ICollection<LineSegment>.Add(LineSegment item)
		{
			throw new NotSupportedException();
		}
		
		bool ICollection<LineSegment>.Remove(LineSegment item)
		{
			throw new NotSupportedException();
		}
	}
}

L	V	Source
1		// <file>
2		// <copyright see="prj:///doc/copyright.txt"/>
3		// <license see="prj:///doc/license.txt"/>
4		// <owner name="Daniel Grunwald" email="daniel@danielgrunwald.de"/>
5		// <version>$Revision: 2683 $</version>
6		// </file>
7
8		using System;
9		using System.Collections.Generic;
10		using System.Diagnostics;
11		using ICSharpCode.TextEditor.Util;
12
13		namespace ICSharpCode.TextEditor.Document
14		{
15		/// <summary>
16		/// Data structure for efficient management of the line segments (most operations are O(lg n)).
17		/// This implements an augmented red-black tree where each node has fields for the number of
18		/// nodes in its subtree (like an order statistics tree) for access by index(=line number).
19		/// Additionally, each node knows the total length of all segments in its subtree.
20		/// This means we can find nodes by offset in O(lg n) time. Since the offset itself is not stored in
21		/// the line segment but computed from the lengths stored in the tree, we adjusting the offsets when
22		/// text is inserted in one line means we just have to increment the totalLength of the affected line and
23		/// its parent nodes - an O(lg n) operation.
24		/// However this means getting the line number or offset from a LineSegment is not a constant time
25		/// operation, but takes O(lg n).
26		///
27		/// NOTE: The tree is never empty, Clear() causes it to contain an empty segment.
28		/// </summary>
29		sealed class LineSegmentTree : IList<LineSegment>
30		{
31		internal struct RBNode
32		{
33		internal LineSegment lineSegment;
34		internal int count;
35		internal int totalLength;
36
37		public RBNode(LineSegment lineSegment)
38		{
39		this.lineSegment = lineSegment;
40		this.count = 1;
41		this.totalLength = lineSegment.TotalLength;
42		}
43
44		public override string ToString()
45		{
46		return "[RBNode count=" + count + " totalLength="+totalLength
47		+ " lineSegment.LineNumber=" + lineSegment.LineNumber
48		+ " lineSegment.Offset=" + lineSegment.Offset
49		+ " lineSegment.TotalLength=" + lineSegment.TotalLength
50		+ " lineSegment.DelimiterLength=" + lineSegment.DelimiterLength + "]";
51		}
52		}
53
54		struct MyHost : IRedBlackTreeHost<RBNode>
55		{
56		public int Compare(RBNode x, RBNode y)
57		{
58		throw new NotImplementedException();
59		}
60
61		public bool Equals(RBNode a, RBNode b)
62		{
63		throw new NotImplementedException();
64		}
65
66		public void UpdateAfterChildrenChange(RedBlackTreeNode<RBNode> node)
67		{
68		int count = 1;
69		int totalLength = node.val.lineSegment.TotalLength;
70		if (node.left != null) {
71		count += node.left.val.count;
72		totalLength += node.left.val.totalLength;
73		}
74		if (node.right != null) {
75		count += node.right.val.count;
76		totalLength += node.right.val.totalLength;
77		}
78		if (count != node.val.count \|\| totalLength != node.val.totalLength) {
79		node.val.count = count;
80		node.val.totalLength = totalLength;
81		if (node.parent != null) UpdateAfterChildrenChange(node.parent);
82		}
83		}
84
85		public void UpdateAfterRotateLeft(RedBlackTreeNode<RBNode> node)
86		{
87		UpdateAfterChildrenChange(node);
88		UpdateAfterChildrenChange(node.parent);
89		}
90
91		public void UpdateAfterRotateRight(RedBlackTreeNode<RBNode> node)
92		{
93		UpdateAfterChildrenChange(node);
94		UpdateAfterChildrenChange(node.parent);
95		}
96		}
97
98		readonly AugmentableRedBlackTree<RBNode, MyHost> tree = new AugmentableRedBlackTree<RBNode, MyHost>(new MyHost());
99
100		RedBlackTreeNode<RBNode> GetNode(int index)
101		{
102		if (index < 0 \|\| index >= tree.Count)
103		throw new ArgumentOutOfRangeException("index", index, "index should be between 0 and " + (tree.Count-1));
104		RedBlackTreeNode<RBNode> node = tree.root;
105		while (true) {
106		if (node.left != null && index < node.left.val.count) {
107		node = node.left;
108		} else {
109		if (node.left != null) {
110		index -= node.left.val.count;
111		}
112		if (index == 0)
113		return node;
114		index--;
115		node = node.right;
116		}
117		}
118		}
119
120		static int GetIndexFromNode(RedBlackTreeNode<RBNode> node)
121		{
122		int index = (node.left != null) ? node.left.val.count : 0;
123		while (node.parent != null) {
124		if (node == node.parent.right) {
125		if (node.parent.left != null)
126		index += node.parent.left.val.count;
127		index++;
128		}
129		node = node.parent;
130		}
131		return index;
132		}
133
134		RedBlackTreeNode<RBNode> GetNodeByOffset(int offset)
135		{
136		if (offset < 0 \|\| offset > this.TotalLength)
137		throw new ArgumentOutOfRangeException("offset", offset, "offset should be between 0 and " + this.TotalLength);
138		if (offset == this.TotalLength) {
139		if (tree.root == null)
140		throw new InvalidOperationException("Cannot call GetNodeByOffset while tree is empty.");
141		return tree.root.RightMost;
142		}
143		RedBlackTreeNode<RBNode> node = tree.root;
144		while (true) {
145		if (node.left != null && offset < node.left.val.totalLength) {
146		node = node.left;
147		} else {
148		if (node.left != null) {
149		offset -= node.left.val.totalLength;
150		}
151		offset -= node.val.lineSegment.TotalLength;
152		if (offset < 0)
153		return node;
154		node = node.right;
155		}
156		}
157		}
158
159		static int GetOffsetFromNode(RedBlackTreeNode<RBNode> node)
160		{
161		int offset = (node.left != null) ? node.left.val.totalLength : 0;
162		while (node.parent != null) {
163		if (node == node.parent.right) {
164		if (node.parent.left != null)
165		offset += node.parent.left.val.totalLength;
166		offset += node.parent.val.lineSegment.TotalLength;
167		}
168		node = node.parent;
169		}
170		return offset;
171		}
172
173		public LineSegment GetByOffset(int offset)
174		{
175		return GetNodeByOffset(offset).val.lineSegment;
176		}
177
178		/// <summary>
179		/// Gets the total length of all line segments. Runs in O(1).
180		/// </summary>
181		public int TotalLength {
182		get {
183		if (tree.root == null)
184		return 0;
185		else
186		return tree.root.val.totalLength;
187		}
188		}
189
190		/// <summary>
191		/// Updates the length of a line segment. Runs in O(lg n).
192		/// </summary>
193		public void SetSegmentLength(LineSegment segment, int newTotalLength)
194		{
195		if (segment == null)
196		throw new ArgumentNullException("segment");
197		RedBlackTreeNode<RBNode> node = segment.treeEntry.it.node;
198		segment.TotalLength = newTotalLength;
199		default(MyHost).UpdateAfterChildrenChange(node);
200		#if DEBUG
201		CheckProperties();
202		#endif
203		}
204
205		public void RemoveSegment(LineSegment segment)
206		{
207		tree.RemoveAt(segment.treeEntry.it);
208		#if DEBUG
209		CheckProperties();
210		#endif
211		}
212
213		public LineSegment InsertSegmentAfter(LineSegment segment, int length)
214		{
215		LineSegment newSegment = new LineSegment();
216		newSegment.TotalLength = length;
217		newSegment.DelimiterLength = segment.DelimiterLength;
218
219		newSegment.treeEntry = InsertAfter(segment.treeEntry.it.node, newSegment);
220		return newSegment;
221		}
222
223		Enumerator InsertAfter(RedBlackTreeNode<RBNode> node, LineSegment newSegment)
224		{
225		RedBlackTreeNode<RBNode> newNode = new RedBlackTreeNode<RBNode>(new RBNode(newSegment));
226		if (node.right == null) {
227		tree.InsertAsRight(node, newNode);
228		} else {
229		tree.InsertAsLeft(node.right.LeftMost, newNode);
230		}
231		#if DEBUG
232		CheckProperties();
233		#endif
234		return new Enumerator(new RedBlackTreeIterator<RBNode>(newNode));
235		}
236
237		/// <summary>
238		/// Gets the number of items in the collections. Runs in O(1).
239		/// </summary>
240		public int Count {
241		get { return tree.Count; }
242		}
243
244		/// <summary>
245		/// Gets or sets an item by index. Runs in O(lg n).
246		/// </summary>
247		public LineSegment this[int index] {
248		get {
249		return GetNode(index).val.lineSegment;
250		}
251		set {
252		throw new NotSupportedException();
253		}
254		}
255
256		bool ICollection<LineSegment>.IsReadOnly {
257		get { return true; }
258		}
259
260		/// <summary>
261		/// Gets the index of an item. Runs in O(lg n).
262		/// </summary>
263		public int IndexOf(LineSegment item)
264		{
265		int index = item.LineNumber;
266		if (index < 0 \|\| index >= this.Count)
267		return -1;
268		if (item != this[index])
269		return -1;
270		return index;
271		}
272
273		void IList<LineSegment>.RemoveAt(int index)
274		{
275		throw new NotSupportedException();
276		}
277
278		#if DEBUG
279		[Conditional("DATACONSISTENCYTEST")]
280		void CheckProperties()
281		{
282		if (tree.root == null) {
283		Debug.Assert(this.Count == 0);
284		} else {
285		Debug.Assert(tree.root.val.count == this.Count);
286		CheckProperties(tree.root);
287		}
288		}
289
290		void CheckProperties(RedBlackTreeNode<RBNode> node)
291		{
292		int count = 1;
293		int totalLength = node.val.lineSegment.TotalLength;
294		if (node.left != null) {
295		CheckProperties(node.left);
296		count += node.left.val.count;
297		totalLength += node.left.val.totalLength;
298		}
299		if (node.right != null) {
300		CheckProperties(node.right);
301		count += node.right.val.count;
302		totalLength += node.right.val.totalLength;
303		}
304		Debug.Assert(node.val.count == count);
305		Debug.Assert(node.val.totalLength == totalLength);
306		}
307
308		public string GetTreeAsString()
309		{
310		return tree.GetTreeAsString();
311		}
312		#endif
313
314		public LineSegmentTree()
315		{
316		Clear();
317		}
318
319		/// <summary>
320		/// Clears the list. Runs in O(1).
321		/// </summary>
322		public void Clear()
323		{
324		tree.Clear();
325		LineSegment emptySegment = new LineSegment();
326		emptySegment.TotalLength = 0;
327		emptySegment.DelimiterLength = 0;
328		tree.Add(new RBNode(emptySegment));
329		emptySegment.treeEntry = GetEnumeratorForIndex(0);
330		#if DEBUG
331		CheckProperties();
332		#endif
333		}
334
335		/// <summary>
336		/// Tests whether an item is in the list. Runs in O(n).
337		/// </summary>
338		public bool Contains(LineSegment item)
339		{
340		return IndexOf(item) >= 0;
341		}
342
343		/// <summary>
344		/// Copies all elements from the list to the array.
345		/// </summary>
346		public void CopyTo(LineSegment[] array, int arrayIndex)
347		{
348		if (array == null) throw new ArgumentNullException("array");
349		foreach (LineSegment val in this)
350		array[arrayIndex++] = val;
351		}
352
353		IEnumerator<LineSegment> IEnumerable<LineSegment>.GetEnumerator()
354		{
355		return this.GetEnumerator();
356		}
357
358		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
359		{
360		return this.GetEnumerator();
361		}
362
363		public Enumerator GetEnumerator()
364		{
365		return new Enumerator(tree.GetEnumerator());
366		}
367
368		public Enumerator GetEnumeratorForIndex(int index)
369		{
370		return new Enumerator(new RedBlackTreeIterator<RBNode>(GetNode(index)));
371		}
372
373		public Enumerator GetEnumeratorForOffset(int offset)
374		{
375		return new Enumerator(new RedBlackTreeIterator<RBNode>(GetNodeByOffset(offset)));
376		}
377
378		public struct Enumerator : IEnumerator<LineSegment>
379		{
380		/// <summary>
381		/// An invalid enumerator value. Calling MoveNext on the invalid enumerator
382		/// will always return false, accessing Current will throw an exception.
383		/// </summary>
384		public static readonly Enumerator Invalid = default(Enumerator);
385
386		internal RedBlackTreeIterator<RBNode> it;
387
388		internal Enumerator(RedBlackTreeIterator<RBNode> it)
389		{
390		this.it = it;
391		}
392
393		/// <summary>
394		/// Gets the current value. Runs in O(1).
395		/// </summary>
396		public LineSegment Current {
397		get {
398		return it.Current.lineSegment;
399		}
400		}
401
402		public bool IsValid {
403		get {
404		return it.IsValid;
405		}
406		}
407
408		/// <summary>
409		/// Gets the index of the current value. Runs in O(lg n).
410		/// </summary>
411		public int CurrentIndex {
412		get {
413		if (it.node == null)
414		throw new InvalidOperationException();
415		return GetIndexFromNode(it.node);
416		}
417		}
418
419		/// <summary>
420		/// Gets the offset of the current value. Runs in O(lg n).
421		/// </summary>
422		public int CurrentOffset {
423		get {
424		if (it.node == null)
425		throw new InvalidOperationException();
426		return GetOffsetFromNode(it.node);
427		}
428		}
429
430		object System.Collections.IEnumerator.Current {
431		get {
432		return it.Current.lineSegment;
433		}
434		}
435
436		public void Dispose()
437		{
438		}
439
440		/// <summary>
441		/// Moves to the next index. Runs in O(lg n), but for k calls, the combined time is only O(k+lg n).
442		/// </summary>
443		public bool MoveNext()
444		{
445		return it.MoveNext();
446		}
447
448		/// <summary>
449		/// Moves to the previous index. Runs in O(lg n), but for k calls, the combined time is only O(k+lg n).
450		/// </summary>
451		public bool MoveBack()
452		{
453		return it.MoveBack();
454		}
455
456		void System.Collections.IEnumerator.Reset()
457		{
458		throw new NotSupportedException();
459		}
460		}
461
462		void IList<LineSegment>.Insert(int index, LineSegment item)
463		{
464		throw new NotSupportedException();
465		}
466
467		void ICollection<LineSegment>.Add(LineSegment item)
468		{
469		throw new NotSupportedException();
470		}
471
472		bool ICollection<LineSegment>.Remove(LineSegment item)
473		{
474		throw new NotSupportedException();
475		}
476		}
477		}