aboutsummaryrefslogtreecommitdiffstats
path: root/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Rope.cs
blob: d27edd19983492ad28926a168cc3a1833f4e59d5 (plain) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)

using System;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Text;
using System.Windows;

using Tango.Scripting.Editors.Document;

namespace Tango.Scripting.Editors.Highlighting
{
	/// <summary>
	/// Allows copying HTML text to the clipboard.
	/// </summary>
	public static class HtmlClipboard
	{
		/// <summary>
		/// Builds a header for the CF_HTML clipboard format.
		/// </summary>
		static string BuildHeader(int startHTML, int endHTML, int startFragment, int endFragment)
		{
			StringBuilder b = new StringBuilder();
			b.AppendLine("Version:0.9");
			b.AppendLine("StartHTML:" + startHTML.ToString("d8", CultureInfo.InvariantCulture));
			b.AppendLine("EndHTML:" + endHTML.ToString("d8", CultureInfo.InvariantCulture));
			b.AppendLine("StartFragment:" + startFragment.ToString("d8", CultureInfo.InvariantCulture));
			b.AppendLine("EndFragment:" + endFragment.ToString("d8", CultureInfo.InvariantCulture));
			return b.ToString();
		}
		
		/// <summary>
		/// Sets the TextDataFormat.Html on the data object to the specified html fragment.
		/// This helper methods takes care of creating the necessary CF_HTML header.
		/// </summary>
		public static void SetHtml(DataObject dataObject, string htmlFragment)
		{
			if (dataObject == null)
				throw new ArgumentNullException("dataObject");
			if (htmlFragment == null)
				throw new ArgumentNullException("htmlFragment");
			
			string htmlStart = @"<!DOCTYPE HTML PUBLIC ""-//W3C//DTD HTML 4.0 Transitional//EN"">" + Environment.NewLine
				+ "<HTML>" + Environment.NewLine
				+ "<BODY>" + Environment.NewLine
				+ "<!--StartFragment-->" + Environment.NewLine;
			string htmlEnd = "<!--EndFragment-->" + Environment.NewLine + "</BODY>" + Environment.NewLine + "</HTML>" + Environment.NewLine;
			string dummyHeader = BuildHeader(0, 0, 0, 0);
			// the offsets are stored as UTF-8 bytes (see CF_HTML documentation)
			int startHTML = dummyHeader.Length;
			int startFragment = startHTML + htmlStart.Length;
			int endFragment = startFragment + Encoding.UTF8.GetByteCount(htmlFragment);
			int endHTML = endFragment + htmlEnd.Length;
			string cf_html = BuildHeader(startHTML, endHTML, startFragment, endFragment) + htmlStart + htmlFragment + htmlEnd;
			Debug.WriteLine(cf_html);
			dataObject.SetText(cf_html, TextDataFormat.Html);
		}
		
		/// <summary>
		/// Creates a HTML fragment from a part of a document.
		/// </summary>
		/// <param name="document">The document to create HTML from.</param>
		/// <param name="highlighter">The highlighter used to highlight the document. <c>null</c> is valid and will create HTML without any highlighting.</param>
pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Runtime.Serialization;
using System.Text;

namespace Tango.Scripting.Editors.Utils
{
	/// <summary>
	/// A kind of List&lt;T&gt;, but more efficient for random insertions/removal.
	/// Also has cheap Clone() and SubRope() implementations.
	/// </summary>
	/// <remarks>
	/// This class is not thread-safe: multiple concurrent write operations or writes concurrent to reads have undefined behaviour.
	/// Concurrent reads, however, are safe.
	/// However, clones of a rope are safe to use on other threads even though they share data with the original rope.
	/// </remarks>
	[Serializable]
	[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
	public sealed class Rope<T> : IList<T>, ICloneable
	{
		internal RopeNode<T> root;
		
		internal Rope(RopeNode<T> root)
		{
			this.root = root;
			root.CheckInvariants();
		}
		
		/// <summary>
		/// Creates a new rope representing the empty string.
		/// </summary>
		public Rope()
		{
			// we'll construct the empty rope as a clone of an imaginary static empty rope
			this.root = RopeNode<T>.emptyRopeNode;
			root.CheckInvariants();
		}
		
		/// <summary>
		/// Creates a rope from the specified input.
		/// This operation runs in O(N).
		/// </summary>
		/// <exception cref="ArgumentNullException">input is null.</exception>
		public Rope(IEnumerable<T> input)
		{
			if (input == null)
				throw new ArgumentNullException("input");
			Rope<T> inputRope = input as Rope<T>;
			if (inputRope != null) {
				// clone ropes instead of copying them
				inputRope.root.Publish();
				this.root = inputRope.root;
			} else {
				string text = input as string;
				if (text != null) {
					// if a string is IEnumerable<T>, then T must be char
					((Rope<char>)(object)this).root = CharRope.InitFromString(text);
				} else {
					T[] arr = ToArray(input);
					this.root = RopeNode<T>.CreateFromArray(arr, 0, arr.Length);
				}
			}
			this.root.CheckInvariants();
		}
		
		/// <summary>
		/// Creates a rope from a part of the array.
		/// This operation runs in O(N).
		/// </summary>
		/// <exception cref="ArgumentNullException">input is null.</exception>
		public Rope(T[] array, int arrayIndex, int count)
		{
			VerifyArrayWithRange(array, arrayIndex, count);
			this.root = RopeNode<T>.CreateFromArray(array, arrayIndex, count);
			this.root.CheckInvariants();
		}
		
		/// <summary>
		/// Creates a new rope that lazily initalizes its content.
		/// </summary>
		/// <param name="length">The length of the rope that will be lazily loaded.</param>
		/// <param name="initializer">
		/// The callback that provides the content for this rope.
		/// <paramref name="initializer"/> will be called exactly once when the content of this rope is first requested.
		/// It must return a rope with the specified length.
		/// Because the initializer function is not called when a rope is cloned, and such clones may be used on another threads,
		/// it is possible for the initializer callback to occur on any thread.
		/// </param>
		/// <remarks>
		/// Any modifications inside the rope will also cause the content to be initialized.
		/// However, insertions at the beginning and the end, as well as inserting this rope into another or
		/// using the <see cref="Concat(Rope{T},Rope{T})"/> method, allows constructions of larger ropes where parts are
		/// lazily loaded.
		/// However, even methods like Concat may sometimes cause the initializer function to be called, e.g. when
		/// two short ropes are concatenated.
		/// </remarks>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
		public Rope(int length, Func<Rope<T>> initializer)
		{
			if (initializer == null)
				throw new ArgumentNullException("initializer");
			if (length < 0)
				throw new ArgumentOutOfRangeException("length", length, "Length must not be negative");
			if (length == 0) {
				this.root = RopeNode<T>.emptyRopeNode;
			} else {
				this.root = new FunctionNode<T>(length, initializer);
			}
			this.root.CheckInvariants();
		}
		
		static T[] ToArray(IEnumerable<T> input)
		{
			T[] arr = input as T[];
			return arr ?? input.ToArray();
		}
		
		/// <summary>
		/// Clones t
generated by cgit v1.3.1 (git 2.54.0) at 2026-07-28 04:11:02 +0000
the rope (doing this doesn't increase the complexity of the modification operations); /// the remainder of Clone() runs in O(1). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public Rope<T> Clone() { // The Publish() call actually modifies this rope instance; but this modification is thread-safe // as long as the tree structure doesn't change during the operation. root.Publish(); return new Rope<T>(root); } object ICloneable.Clone() { return this.Clone(); } /// <summary> /// Resets the rope to an empty list. /// Runs in O(1). /// </summary> public void Clear() { root = RopeNode<T>.emptyRopeNode; OnChanged(); } /// <summary> /// Gets the length of the rope. /// Runs in O(1). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public int Length { get { return root.length; } } /// <summary> /// Gets the length of the rope. /// Runs in O(1). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public int Count { get { return root.length; } } /// <summary> /// Inserts another rope into this rope. /// Runs in O(lg N + lg M), plus a per-node cost as if <c>newElements.Clone()</c> was called. /// </summary> /// <exception cref="ArgumentNullException">newElements is null.</exception> /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> public void InsertRange(int index, Rope<T> newElements) { if (index < 0 || index > this.Length) { throw new ArgumentOutOfRangeException("index", index, "0 <= index <= " + this.Length.ToString(CultureInfo.InvariantCulture)); } if (newElements == null) throw new ArgumentNullException("newElements"); newElements.root.Publish(); root = root.Insert(index, newElements.root); OnChanged(); } /// <summary> /// Inserts new elemetns into this rope. /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. /// </summary> /// <exception cref="ArgumentNullException">newElements is null.</exception> /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> public void InsertRange(int index, IEnumerable<T> newElements) { if (newElements == null) throw new ArgumentNullException("newElements"); Rope<T> newElementsRope = newElements as Rope<T>; if (newElementsRope != null) { InsertRange(index, newElementsRope); } else { T[] arr = ToArray(newElements); InsertRange(index, arr, 0, arr.Length); } } /// <summary> /// Inserts new elements into this rope. /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. /// </summary> /// <exception cref="ArgumentNullException">newElements is null.</exception> /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> public void InsertRange(int index, T[] array, int arrayIndex, int count) { if (index < 0 || index > this.Length) { throw new ArgumentOutOfRangeException("index", index, "0 <= index <= " + this.Length.ToString(CultureInfo.InvariantCulture)); } VerifyArrayWithRange(array, arrayIndex, count); if (count > 0) { root = root.Insert(index, array, arrayIndex, count); OnChanged(); } } /// <summary> /// Appends multiple elements to the end of this rope. /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. /// </summary> /// <exception cref="ArgumentNullException">newElements is null.</exception> public void AddRange(IEnumerable<T> newElements) { InsertRange(this.Length, newElements); } /// <summary> /// Appends another rope to the end of this rope. /// Runs in O(lg N + lg M), plus a per-node cost as if <c>newElements.Clone()</c> was called. /// </summary> /// <exception cref="ArgumentNullException">newElements is null.</exception> public void AddRange(Rope<T> newElements) { InsertRange(this.Length, newElements); } /// <summary> /// Appends new elements to the end of this rope. /// Runs in O(lg N + M), where N is the length of this rope and M is the number of new elements. /// </summary> /// <exception cref="ArgumentNullException">array is null.</exception> public void AddRange(T[] array, int arrayIndex, int count) { InsertRange(this.Length, array, arrayIndex, count); } /// <summary> /// Removes a range of elements from the rope. /// Runs in O(lg N). /// </summary> /// <exception cref="ArgumentOutOfRangeException">offset or length is outside the valid range.</exception> public void RemoveRange(int index, int count) { VerifyRange(index, count); if (count > 0) { root = root.RemoveRange(index, count); OnChanged(); } } /// <summary> /// Copies a range of the specified array into the rope, overwriting existing elements. /// Runs in O(lg N + M). /// </summary> public void SetRange(int index, T[] array, int arrayIndex, int count) { VerifyRange(index, count); VerifyArrayWithRange(array, arrayIndex, count); if (count > 0) { root = root.StoreElements(index, array, arrayIndex, count); OnChanged(); } } /// <summary> /// Creates a new rope and initializes it with a part of this rope. /// Runs in O(lg N) plus a per-node cost as if <c>this.Clone()</c> was called. /// </summary> /// <exception cref="ArgumentOutOfRangeException">offset or length is outside the valid range.</exception> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public Rope<T> GetRange(int index, int count) { VerifyRange(index, count); Rope<T> newRope = Clone(); int endIndex = index + count; newRope.RemoveRange(endIndex, newRope.Length - endIndex); newRope.RemoveRange(0, index); return newRope; } /* #region Equality /// <summary> /// Gets whether the two ropes have the same content. /// Runs in O(N + M). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public bool Equals(Rope other) { if (other == null) return false; // quick detection for ropes that are clones of each other: if (other.root == this.root) return true; if (other.Length != this.Length) return false; using (RopeTextReader a = new RopeTextReader(this, false)) { using (RopeTextReader b = new RopeTextReader(other, false)) { int charA, charB; do { charA = a.Read(); charB = b.Read(); if (charA != charB) return false; } while (charA != -1); return true; } } } /// <summary> /// Gets whether two ropes have the same content. /// Runs in O(N + M). /// </summary> public override bool Equals(object obj) { return Equals(obj as Rope); } /// <summary> /// Calculates the hash code of the rope's content. /// Runs in O(N). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public override int GetHashCode() { int hashcode = 0; using (RopeTextReader reader = new RopeTextReader(this, false)) { unchecked { int val; while ((val = reader.Read()) != -1) { hashcode = hashcode * 31 + val; } } } return hashcode; } #endregion */ /// <summary> /// Concatenates two ropes. The input ropes are not modified. /// Runs in O(lg N + lg M). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] public static Rope<T> Concat(Rope<T> left, Rope<T> right) { if (left == null) throw new ArgumentNullException("left"); if (right == null) throw new ArgumentNullException("right"); left.root.Publish(); right.root.Publish(); return new Rope<T>(RopeNode<T>.Concat(left.root, right.root)); } /// <summary> /// Concatenates multiple ropes. The input ropes are not modified. /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] public static Rope<T> Concat(params Rope<T>[] ropes) { if (ropes == null) throw new ArgumentNullException("ropes"); Rope<T> result = new Rope<T>(); foreach (Rope<T> r in ropes) result.AddRange(r); return result; } #region Caches / Changed event internal struct RopeCacheEntry { internal readonly RopeNode<T> node; internal readonly int nodeStartIndex; internal RopeCacheEntry(RopeNode<T> node, int nodeStartOffset) { this.node = node; this.nodeStartIndex = nodeStartOffset; } internal bool IsInside(int offset) { return offset >= nodeStartIndex && offset < nodeStartIndex + node.length; } } // cached pointer to 'last used node', used to speed up accesses by index that are close together [NonSerialized] volatile ImmutableStack<RopeCacheEntry> lastUsedNodeStack; internal void OnChanged() { lastUsedNodeStack = null; root.CheckInvariants(); } #endregion #region GetChar / SetChar /// <summary> /// Gets/Sets a single character. /// Runs in O(lg N) for random access. Sequential read-only access benefits from a special optimization and runs in amortized O(1). /// </summary> /// <exception cref="ArgumentOutOfRangeException">Offset is outside the valid range (0 to Length-1).</exception> /// <remarks> /// The getter counts as a read access and may be called concurrently to other read accesses. /// </remarks> public T this[int index] { get { // use unsigned integers - this way negative values for index overflow and can be tested for with the same check if (unchecked((uint)index >= (uint)this.Length)) { throw new ArgumentOutOfRangeException("index", index, "0 <= index < " + this.Length.ToString(CultureInfo.InvariantCulture)); } RopeCacheEntry entry = FindNodeUsingCache(index).UnsafePeek(); return entry.node.contents[index - entry.nodeStartIndex]; } set { if (index < 0 || index >= this.Length) { throw new ArgumentOutOfRangeException("index", index, "0 <= index < " + this.Length.ToString(CultureInfo.InvariantCulture)); } root = root.SetElement(index, value); OnChanged(); /* Here's a try at implementing the setter using the cached node stack (UNTESTED code!). * However I don't use the code because it's complicated and doesn't integrate correctly with change notifications. * Instead, I'll use the much easier to understand recursive solution. * Oh, and it also doesn't work correctly with function nodes. ImmutableStack<RopeCacheEntry> nodeStack = FindNodeUsingCache(offset); RopeCacheEntry entry = nodeStack.Peek(); if (!entry.node.isShared) { entry.node.contents[offset - entry.nodeStartOffset] = value; // missing: clear the caches except for the node stack cache (e.g. ToString() cache?) } else { RopeNode oldNode = entry.node; RopeNode newNode = oldNode.Clone(); newNode.contents[offset - entry.nodeStartOffset] = value; for (nodeStack = nodeStack.Pop(); !nodeStack.IsEmpty; nodeStack = nodeStack.Pop()) { RopeNode parentNode = nodeStack.Peek().node; RopeNode newParentNode = parentNode.CloneIfShared(); if (newParentNode.left == oldNode) { newParentNode.left = newNode; } else { Debug.Assert(newParentNode.right == oldNode); newParentNode.right = newNode; } if (parentNode == newParentNode) { // we were able to change the existing node (it was not shared); // there's no reason to go further upwards ClearCacheOnModification(); return; } else { oldNode = parentNode; newNode = newParentNode; } } // we reached the root of the rope. Debug.Assert(root == oldNode); root = newNode; ClearCacheOnModification(); }*/ } } internal ImmutableStack<RopeCacheEntry> FindNodeUsingCache(int index) { Debug.Assert(index >= 0 && index < this.Length); // thread safety: fetch stack into local variable ImmutableStack<RopeCacheEntry> stack = lastUsedNodeStack; ImmutableStack<RopeCacheEntry> oldStack = stack; if (stack == null) { stack = ImmutableStack<RopeCacheEntry>.Empty.Push(new RopeCacheEntry(root, 0)); } while (!stack.UnsafePeek().IsInside(index)) stack = stack.Pop(); while (true) { RopeCacheEntry entry = stack.UnsafePeek(); // check if we've reached a leaf or function node if (entry.node.height == 0) { if (entry.node.contents == null) { // this is a function node - go down into its subtree entry = new RopeCacheEntry(entry.node.GetContentNode(), entry.nodeStartIndex); // entry is now guaranteed NOT to be another function node } if (entry.node.contents != null) { // this is a node containing actual content, so we're done break; } } // go down towards leaves if (index - entry.nodeStartIndex >= entry.node.left.length) stack = stack.Push(new RopeCacheEntry(entry.node.right, entry.nodeStartIndex + entry.node.left.length)); else stack = stack.Push(new RopeCacheEntry(entry.node.left, entry.nodeStartIndex)); } // write back stack to volatile cache variable // (in multithreaded access, it doesn't matter which of the threads wins - it's just a cache) if (oldStack != stack) { // no need to write when we the cache variable didn't change lastUsedNodeStack = stack; } // this method guarantees that it finds a leaf node Debug.Assert(stack.Peek().node.contents != null); return stack; } #endregion #region ToString / WriteTo internal void VerifyRange(int startIndex, int length) { if (startIndex < 0 || startIndex > this.Length) { throw new ArgumentOutOfRangeException("startIndex", startIndex, "0 <= startIndex <= " + this.Length.ToString(CultureInfo.InvariantCulture)); } if (length < 0 || startIndex + length > this.Length) { throw new ArgumentOutOfRangeException("length", length, "0 <= length, startIndex(" + startIndex + ")+length <= " + this.Length.ToString(CultureInfo.InvariantCulture)); } } internal static void VerifyArrayWithRange(T[] array, int arrayIndex, int count) { if (array == null) throw new ArgumentNullException("array"); if (arrayIndex < 0 || arrayIndex > array.Length) { throw new ArgumentOutOfRangeException("startIndex", arrayIndex, "0 <= arrayIndex <= " + array.Length.ToString(CultureInfo.InvariantCulture)); } if (count < 0 || arrayIndex + count > array.Length) { throw new ArgumentOutOfRangeException("count", count, "0 <= length, arrayIndex(" + arrayIndex + ")+count <= " + array.Length.ToString(CultureInfo.InvariantCulture)); } } /// <summary> /// Creates a string from the rope. Runs in O(N). /// </summary> /// <returns>A string consisting of all elements in the rope as comma-separated list in {}. /// As a special case, Rope&lt;char&gt; will return its contents as string without any additional separators or braces, /// so it can be used like StringBuilder.ToString().</returns> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public override string ToString() { Rope<char> charRope = this as Rope<char>; if (charRope != null) { return charRope.ToString(0, this.Length); } else { StringBuilder b = new StringBuilder(); foreach (T element in this) { if (b.Length == 0) b.Append('{'); else b.Append(", "); b.Append(element.ToString()); } b.Append('}'); return b.ToString(); } } internal string GetTreeAsString() { #if DEBUG return root.GetTreeAsString(); #else return "Not available in release build."; #endif } #endregion bool ICollection<T>.IsReadOnly { get { return false; } } /// <summary> /// Finds the first occurance of item. /// Runs in O(N). /// </summary> /// <returns>The index of the first occurance of item, or -1 if it cannot be found.</returns> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public int IndexOf(T item) { var comparer = EqualityComparer<T>.Default; int index = 0; foreach (T element in this) { if (comparer.Equals(item, element)) return index; index++; } return -1; } /// <summary> /// Inserts the item at the specified index in the rope. /// Runs in O(lg N). /// </summary> public void Insert(int index, T item) { InsertRange(index, new[] { item }, 0, 1); } /// <summary> /// Removes a single item from the rope. /// Runs in O(lg N). /// </summary> public void RemoveAt(int index) { RemoveRange(index, 1); } /// <summary> /// Appends the item at the end of the rope. /// Runs in O(lg N). /// </summary> public void Add(T item) { InsertRange(this.Length, new[] { item }, 0, 1); } /// <summary> /// Searches the item in the rope. /// Runs in O(N). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public bool Contains(T item) { return IndexOf(item) >= 0; } /// <summary> /// Copies the whole content of the rope into the specified array. /// Runs in O(N). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public void CopyTo(T[] array, int arrayIndex) { CopyTo(0, array, arrayIndex, this.Length); } /// <summary> /// Copies the a part of the rope into the specified array. /// Runs in O(lg N + M). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public void CopyTo(int index, T[] array, int arrayIndex, int count) { VerifyRange(index, count); VerifyArrayWithRange(array, arrayIndex, count); this.root.CopyTo(index, array, arrayIndex, count); } /// <summary> /// Removes the first occurance of an item from the rope. /// Runs in O(N). /// </summary> public bool Remove(T item) { int index = IndexOf(item); if (index >= 0) { RemoveAt(index); return true; } return false; } /// <summary> /// Retrieves an enumerator to iterate through the rope. /// The enumerator will reflect the state of the rope from the GetEnumerator() call, further modifications /// to the rope will not be visible to the enumerator. /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public IEnumerator<T> GetEnumerator() { this.root.Publish(); return Enumerate(root); } /// <summary> /// Creates an array and copies the contents of the rope into it. /// Runs in O(N). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public T[] ToArray() { T[] arr = new T[this.Length]; CopyTo(arr, 0); return arr; } /// <summary> /// Creates an array and copies the contents of the rope into it. /// Runs in O(N). /// </summary> /// <remarks> /// This method counts as a read access and may be called concurrently to other read accesses. /// </remarks> public T[] ToArray(int startIndex, int count) { VerifyRange(startIndex, count); T[] arr = new T[count]; CopyTo(startIndex, arr, 0, count); return arr; } static IEnumerator<T> Enumerate(RopeNode<T> node) { Stack<RopeNode<T>> stack = new Stack<RopeNode<T>>(); while (node != null) { // go to leftmost node, pushing the right parts that we'll have to visit later while (node.contents == null) { if (node.height == 0) { // go down into function nodes node = node.GetContentNode(); continue; } Debug.Assert(node.right != null); stack.Push(node.right); node = node.left; } // yield contents of leaf node for (int i = 0; i < node.length; i++) { yield return node.contents[i]; } // go up to the next node not visited yet if (stack.Count > 0) node = stack.Pop(); else node = null; } } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this.GetEnumerator(); } } }
generated by cgit v1.3.1 (git 2.54.0) at 2026-07-28 04:11:02 +0000