diff options
| author | Roy Ben Shabat <Roy.mail.net@gmail.com> | 2019-04-09 01:47:48 +0300 |
|---|---|---|
| committer | Roy Ben Shabat <Roy.mail.net@gmail.com> | 2019-04-09 01:47:48 +0300 |
| commit | 080f1697e97e13461ec6df4d31c8924d01257a1b (patch) | |
| tree | b1fe0285de7bc9bc52e9e2195e66fe022bf8f5b3 /Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils | |
| parent | 1608e69a417bc5e40a607c3958c4a60f19f66f1a (diff) | |
| download | Tango-080f1697e97e13461ec6df4d31c8924d01257a1b.tar.gz Tango-080f1697e97e13461ec6df4d31c8924d01257a1b.zip | |
MERGE
Diffstat (limited to 'Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils')
24 files changed, 4071 insertions, 0 deletions
diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Boxes.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Boxes.cs new file mode 100644 index 000000000..517948bae --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Boxes.cs @@ -0,0 +1,21 @@ +// 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; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Reuse the same instances for boxed booleans. + /// </summary> + static class Boxes + { + public static readonly object True = true; + public static readonly object False = false; + + public static object Box(bool value) + { + return value ? True : False; + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/BusyManager.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/BusyManager.cs new file mode 100644 index 000000000..8551ff49e --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/BusyManager.cs @@ -0,0 +1,55 @@ +// 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.Collections.Generic; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// This class is used to prevent stack overflows by representing a 'busy' flag + /// that prevents reentrance when another call is running. + /// However, using a simple 'bool busy' is not thread-safe, so we use a + /// thread-static BusyManager. + /// </summary> + static class BusyManager + { + public struct BusyLock : IDisposable + { + public static readonly BusyLock Failed = new BusyLock(null); + + readonly List<object> objectList; + + public BusyLock(List<object> objectList) + { + this.objectList = objectList; + } + + public bool Success { + get { return objectList != null; } + } + + public void Dispose() + { + if (objectList != null) { + objectList.RemoveAt(objectList.Count - 1); + } + } + } + + [ThreadStatic] static List<object> _activeObjects; + + public static BusyLock Enter(object obj) + { + List<object> activeObjects = _activeObjects; + if (activeObjects == null) + activeObjects = _activeObjects = new List<object>(); + for (int i = 0; i < activeObjects.Count; i++) { + if (activeObjects[i] == obj) + return BusyLock.Failed; + } + activeObjects.Add(obj); + return new BusyLock(activeObjects); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CallbackOnDispose.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CallbackOnDispose.cs new file mode 100644 index 000000000..a6eebf2f1 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CallbackOnDispose.cs @@ -0,0 +1,35 @@ +// 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.Threading; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Invokes an action when it is disposed. + /// </summary> + /// <remarks> + /// This class ensures the callback is invoked at most once, + /// even when Dispose is called on multiple threads. + /// </remarks> + sealed class CallbackOnDispose : IDisposable + { + Action action; + + public CallbackOnDispose(Action action) + { + Debug.Assert(action != null); + this.action = action; + } + + public void Dispose() + { + Action a = Interlocked.Exchange(ref action, null); + if (a != null) { + a(); + } + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CharRope.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CharRope.cs new file mode 100644 index 000000000..844ab9544 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CharRope.cs @@ -0,0 +1,172 @@ +// 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.Globalization; +using System.Text; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Poor man's template specialization: extension methods for Rope<char>. + /// </summary> + public static class CharRope + { + /// <summary> + /// Creates a new rope from the specified text. + /// </summary> + public static Rope<char> Create(string text) + { + if (text == null) + throw new ArgumentNullException("text"); + return new Rope<char>(InitFromString(text)); + } + + /// <summary> + /// Retrieves the text for a portion of the rope. + /// Runs in O(lg N + M), where M=<paramref name="length"/>. + /// </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 static string ToString(this Rope<char> rope, int startIndex, int length) + { + if (rope == null) + throw new ArgumentNullException("rope"); + if (length == 0) + return string.Empty; + char[] buffer = new char[length]; + rope.CopyTo(startIndex, buffer, 0, length); + return new string(buffer); + } + + /// <summary> + /// Retrieves the text for a portion of the rope and writes it to the specified string builder. + /// Runs in O(lg N + M), where M=<paramref name="length"/>. + /// </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 static void WriteTo(this Rope<char> rope, StringBuilder output, int startIndex, int length) + { + if (rope == null) + throw new ArgumentNullException("rope"); + if (output == null) + throw new ArgumentNullException("output"); + rope.VerifyRange(startIndex, length); + rope.root.WriteTo(startIndex, output, length); + } + + /// <summary> + /// Appends text to this rope. + /// Runs in O(lg N + M). + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + public static void AddText(this Rope<char> rope, string text) + { + InsertText(rope, rope.Length, text); + } + + /// <summary> + /// Inserts text into this rope. + /// Runs in O(lg N + M). + /// </summary> + /// <exception cref="ArgumentNullException">newElements is null.</exception> + /// <exception cref="ArgumentOutOfRangeException">index or length is outside the valid range.</exception> + public static void InsertText(this Rope<char> rope, int index, string text) + { + if (rope == null) + throw new ArgumentNullException("rope"); + rope.InsertRange(index, text.ToCharArray(), 0, text.Length); + /*if (index < 0 || index > rope.Length) { + throw new ArgumentOutOfRangeException("index", index, "0 <= index <= " + rope.Length.ToString(CultureInfo.InvariantCulture)); + } + if (text == null) + throw new ArgumentNullException("text"); + if (text.Length == 0) + return; + rope.root = rope.root.Insert(index, text); + rope.OnChanged();*/ + } + + internal static RopeNode<char> InitFromString(string text) + { + if (text.Length == 0) { + return RopeNode<char>.emptyRopeNode; + } + RopeNode<char> node = RopeNode<char>.CreateNodes(text.Length); + FillNode(node, text, 0); + return node; + } + + static void FillNode(RopeNode<char> node, string text, int start) + { + if (node.contents != null) { + text.CopyTo(start, node.contents, 0, node.length); + } else { + FillNode(node.left, text, start); + FillNode(node.right, text, start + node.left.length); + } + } + + internal static void WriteTo(this RopeNode<char> node, int index, StringBuilder output, int count) + { + if (node.height == 0) { + if (node.contents == null) { + // function node + node.GetContentNode().WriteTo(index, output, count); + } else { + // leaf node: append data + output.Append(node.contents, index, count); + } + } else { + // concat node: do recursive calls + if (index + count <= node.left.length) { + node.left.WriteTo(index, output, count); + } else if (index >= node.left.length) { + node.right.WriteTo(index - node.left.length, output, count); + } else { + int amountInLeft = node.left.length - index; + node.left.WriteTo(index, output, amountInLeft); + node.right.WriteTo(0, output, count - amountInLeft); + } + } + } + + /// <summary> + /// Gets the index of the first occurrence of any element in the specified array. + /// </summary> + /// <param name="rope">The target rope.</param> + /// <param name="anyOf">Array of characters being searched.</param> + /// <param name="startIndex">Start index of the search.</param> + /// <param name="length">Length of the area to search.</param> + /// <returns>The first index where any character was found; or -1 if no occurrence was found.</returns> + public static int IndexOfAny(this Rope<char> rope, char[] anyOf, int startIndex, int length) + { + if (rope == null) + throw new ArgumentNullException("rope"); + if (anyOf == null) + throw new ArgumentNullException("anyOf"); + rope.VerifyRange(startIndex, length); + + while (length > 0) { + var entry = rope.FindNodeUsingCache(startIndex).UnsafePeek(); + char[] contents = entry.node.contents; + int startWithinNode = startIndex - entry.nodeStartIndex; + int nodeLength = Math.Min(entry.node.length, startWithinNode + length); + for (int i = startIndex - entry.nodeStartIndex; i < nodeLength; i++) { + char element = contents[i]; + foreach (char needle in anyOf) { + if (element == needle) + return entry.nodeStartIndex + i; + } + } + length -= nodeLength - startWithinNode; + startIndex = entry.nodeStartIndex + nodeLength; + } + return -1; + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CompressingTreeList.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CompressingTreeList.cs new file mode 100644 index 000000000..42f5007c9 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CompressingTreeList.cs @@ -0,0 +1,882 @@ +// 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.Collections.Generic; +using System.Diagnostics; +using System.Text; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// A IList{T} implementation that has efficient insertion and removal (in O(lg n) time) + /// and that saves memory by allocating only one node when a value is repeated in adjacent indices. + /// Based on this "compression", it also supports efficient InsertRange/SetRange/RemoveRange operations. + /// </summary> + /// <remarks> + /// Current memory usage: 5*IntPtr.Size + 12 + sizeof(T) per node. + /// Use this class only if lots of adjacent values are identical (can share one node). + /// </remarks> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", + Justification = "It's an IList<T> implementation")] + public sealed class CompressingTreeList<T> : IList<T> + { + // Further memory optimization: this tree could work without parent pointers. But that + // requires changing most of tree manipulating logic. + // Also possible is to remove the count field and calculate it as totalCount-left.totalCount-right.totalCount + // - but that would make tree manipulations more difficult to handle. + + #region Node definition + sealed class Node + { + internal Node left, right, parent; + internal bool color; + internal int count, totalCount; + internal T value; + + public Node(T value, int count) + { + this.value = value; + this.count = count; + this.totalCount = count; + } + + internal Node LeftMost { + get { + Node node = this; + while (node.left != null) + node = node.left; + return node; + } + } + + internal Node RightMost { + get { + Node node = this; + while (node.right != null) + node = node.right; + return node; + } + } + + /// <summary> + /// Gets the inorder predecessor of the node. + /// </summary> + internal Node Predecessor { + get { + if (left != null) { + return left.RightMost; + } else { + Node node = this; + Node oldNode; + do { + oldNode = node; + node = node.parent; + // go up until we are coming out of a right subtree + } while (node != null && node.left == oldNode); + return node; + } + } + } + + /// <summary> + /// Gets the inorder successor of the node. + /// </summary> + internal Node Successor { + get { + if (right != null) { + return right.LeftMost; + } else { + Node node = this; + Node oldNode; + do { + oldNode = node; + node = node.parent; + // go up until we are coming out of a left subtree + } while (node != null && node.right == oldNode); + return node; + } + } + } + + public override string ToString() + { + return "[TotalCount=" + totalCount + " Count=" + count + " Value=" + value + "]"; + } + } + #endregion + + #region Fields and Constructor + readonly Func<T, T, bool> comparisonFunc; + Node root; + + /// <summary> + /// Creates a new CompressingTreeList instance. + /// </summary> + /// <param name="comparisonFunc">A function that checks two values for equality. If this + /// function returns true, a single node may be used to store the two values.</param> + public CompressingTreeList(Func<T, T, bool> comparisonFunc) + { + if (comparisonFunc == null) + throw new ArgumentNullException("comparisonFunc"); + this.comparisonFunc = comparisonFunc; + } + #endregion + + #region InsertRange + /// <summary> + /// Inserts <paramref name="item"/> <paramref name="count"/> times at position + /// <paramref name="index"/>. + /// </summary> + public void InsertRange(int index, int count, T item) + { + if (index < 0 || index > this.Count) + throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + this.Count); + if (count < 0) + throw new ArgumentOutOfRangeException("count", count, "Value must not be negative"); + if (count == 0) + return; + unchecked { + if (this.Count + count < 0) + throw new OverflowException("Cannot insert elements: total number of elements must not exceed int.MaxValue."); + } + + if (root == null) { + root = new Node(item, count); + } else { + Node n = GetNode(ref index); + // check if we can put the value into the node n: + if (comparisonFunc(n.value, item)) { + n.count += count; + UpdateAugmentedData(n); + } else if (index == n.count) { + // this can only happen when appending at the end + Debug.Assert(n == root.RightMost); + InsertAsRight(n, new Node(item, count)); + } else if (index == 0) { + // insert before: + // maybe we can put the value in the previous node? + Node p = n.Predecessor; + if (p != null && comparisonFunc(p.value, item)) { + p.count += count; + UpdateAugmentedData(p); + } else { + InsertBefore(n, new Node(item, count)); + } + } else { + Debug.Assert(index > 0 && index < n.count); + // insert in the middle: + // split n into a new node and n + n.count -= index; + InsertBefore(n, new Node(n.value, index)); + // then insert the new item in between + InsertBefore(n, new Node(item, count)); + UpdateAugmentedData(n); + } + } + CheckProperties(); + } + + void InsertBefore(Node node, Node newNode) + { + if (node.left == null) { + InsertAsLeft(node, newNode); + } else { + InsertAsRight(node.left.RightMost, newNode); + } + } + #endregion + + #region RemoveRange + /// <summary> + /// Removes <paramref name="count"/> items starting at position + /// <paramref name="index"/>. + /// </summary> + public void RemoveRange(int index, int count) + { + if (index < 0 || index > this.Count) + throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + this.Count); + if (count < 0 || index + count > this.Count) + throw new ArgumentOutOfRangeException("count", count, "0 <= length, index(" + index + ")+count <= " + this.Count); + if (count == 0) + return; + + Node n = GetNode(ref index); + if (index + count < n.count) { + // just remove inside a single node + n.count -= count; + UpdateAugmentedData(n); + } else { + // keep only the part of n from 0 to index + Node firstNodeBeforeDeletedRange; + if (index > 0) { + count -= (n.count - index); + n.count = index; + UpdateAugmentedData(n); + firstNodeBeforeDeletedRange = n; + n = n.Successor; + } else { + Debug.Assert(index == 0); + firstNodeBeforeDeletedRange = n.Predecessor; + } + while (n != null && count >= n.count) { + count -= n.count; + Node s = n.Successor; + RemoveNode(n); + n = s; + } + if (count > 0) { + Debug.Assert(n != null && count < n.count); + n.count -= count; + UpdateAugmentedData(n); + } + if (n != null) { + Debug.Assert(n.Predecessor == firstNodeBeforeDeletedRange); + if (firstNodeBeforeDeletedRange != null && comparisonFunc(firstNodeBeforeDeletedRange.value, n.value)) { + firstNodeBeforeDeletedRange.count += n.count; + RemoveNode(n); + UpdateAugmentedData(firstNodeBeforeDeletedRange); + } + } + } + + CheckProperties(); + } + #endregion + + #region SetRange + /// <summary> + /// Sets <paramref name="count"/> indices starting at <paramref name="index"/> to + /// <paramref name="item"/> + /// </summary> + public void SetRange(int index, int count, T item) + { + RemoveRange(index, count); + InsertRange(index, count, item); + } + #endregion + + #region GetNode + Node GetNode(ref int index) + { + Node node = root; + while (true) { + if (node.left != null && index < node.left.totalCount) { + node = node.left; + } else { + if (node.left != null) { + index -= node.left.totalCount; + } + if (index < node.count || node.right == null) + return node; + index -= node.count; + node = node.right; + } + } + } + #endregion + + #region UpdateAugmentedData + void UpdateAugmentedData(Node node) + { + int totalCount = node.count; + if (node.left != null) totalCount += node.left.totalCount; + if (node.right != null) totalCount += node.right.totalCount; + if (node.totalCount != totalCount) { + node.totalCount = totalCount; + if (node.parent != null) + UpdateAugmentedData(node.parent); + } + } + #endregion + + #region IList<T> implementation + /// <summary> + /// Gets or sets an item by index. + /// </summary> + public T this[int index] { + get { + if (index < 0 || index >= this.Count) + throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1)); + return GetNode(ref index).value; + } + set { + RemoveAt(index); + Insert(index, value); + } + } + + /// <summary> + /// Gets the number of items in the list. + /// </summary> + public int Count { + get { + if (root != null) + return root.totalCount; + else + return 0; + } + } + + bool ICollection<T>.IsReadOnly { + get { + return false; + } + } + + /// <summary> + /// Gets the index of the specified <paramref name="item"/>. + /// </summary> + public int IndexOf(T item) + { + int index = 0; + if (root != null) { + Node n = root.LeftMost; + while (n != null) { + if (comparisonFunc(n.value, item)) + return index; + index += n.count; + n = n.Successor; + } + } + Debug.Assert(index == this.Count); + return -1; + } + + /// <summary> + /// Gets the the first index so that all values from the result index to <paramref name="index"/> + /// are equal. + /// </summary> + public int GetStartOfRun(int index) + { + if (index < 0 || index >= this.Count) + throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1)); + int indexInRun = index; + GetNode(ref indexInRun); + return index - indexInRun; + } + + /// <summary> + /// Gets the first index after <paramref name="index"/> so that the value at the result index is not + /// equal to the value at <paramref name="index"/>. + /// That is, this method returns the exclusive end index of the run of equal values. + /// </summary> + public int GetEndOfRun(int index) + { + if (index < 0 || index >= this.Count) + throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1)); + int indexInRun = index; + int runLength = GetNode(ref indexInRun).count; + return index - indexInRun + runLength; + } + + /// <summary> + /// Gets the number of elements after <paramref name="index"/> that have the same value as each other. + /// </summary> + [Obsolete("This method may be confusing as it returns only the remaining run length after index. " + + "Use GetStartOfRun/GetEndOfRun instead.")] + public int GetRunLength(int index) + { + if (index < 0 || index >= this.Count) + throw new ArgumentOutOfRangeException("index", index, "Value must be between 0 and " + (this.Count - 1)); + return GetNode(ref index).count - index; + } + + /// <summary> + /// Applies the conversion function to all elements in this CompressingTreeList. + /// </summary> + public void Transform(Func<T, T> converter) + { + if (root == null) + return; + Node prevNode = null; + for (Node n = root.LeftMost; n != null; n = n.Successor) { + n.value = converter(n.value); + if (prevNode != null && comparisonFunc(prevNode.value, n.value)) { + n.count += prevNode.count; + UpdateAugmentedData(n); + RemoveNode(prevNode); + } + prevNode = n; + } + } + + + /// <summary> + /// Inserts the specified <paramref name="item"/> at <paramref name="index"/> + /// </summary> + public void Insert(int index, T item) + { + InsertRange(index, 1, item); + } + + /// <summary> + /// Removes one item at <paramref name="index"/> + /// </summary> + public void RemoveAt(int index) + { + RemoveRange(index, 1); + } + + /// <summary> + /// Adds the specified <paramref name="item"/> to the end of the list. + /// </summary> + public void Add(T item) + { + InsertRange(this.Count, 1, item); + } + + /// <summary> + /// Removes all items from this list. + /// </summary> + public void Clear() + { + root = null; + } + + /// <summary> + /// Gets whether this list contains the specified item. + /// </summary> + public bool Contains(T item) + { + return IndexOf(item) >= 0; + } + + /// <summary> + /// Copies all items in this list to the specified array. + /// </summary> + public void CopyTo(T[] array, int arrayIndex) + { + if (array == null) + throw new ArgumentNullException("array"); + if (array.Length < this.Count) + throw new ArgumentException("The array is too small", "array"); + if (arrayIndex < 0 || arrayIndex + this.Count > array.Length) + throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "Value must be between 0 and " + (array.Length - this.Count)); + foreach (T v in this) { + array[arrayIndex++] = v; + } + } + + /// <summary> + /// Removes the specified item from this list. + /// </summary> + public bool Remove(T item) + { + int index = IndexOf(item); + if (index >= 0) { + RemoveAt(index); + return true; + } else { + return false; + } + } + #endregion + + #region IEnumerable<T> + /// <summary> + /// Gets an enumerator for this list. + /// </summary> + public IEnumerator<T> GetEnumerator() + { + if (root != null) { + Node n = root.LeftMost; + while (n != null) { + for (int i = 0; i < n.count; i++) { + yield return n.value; + } + n = n.Successor; + } + } + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { + return GetEnumerator(); + } + #endregion + + #region Red/Black Tree + internal const bool RED = true; + internal const bool BLACK = false; + + void InsertAsLeft(Node parentNode, Node newNode) + { + Debug.Assert(parentNode.left == null); + parentNode.left = newNode; + newNode.parent = parentNode; + newNode.color = RED; + UpdateAugmentedData(parentNode); + FixTreeOnInsert(newNode); + } + + void InsertAsRight(Node parentNode, Node newNode) + { + Debug.Assert(parentNode.right == null); + parentNode.right = newNode; + newNode.parent = parentNode; + newNode.color = RED; + UpdateAugmentedData(parentNode); + FixTreeOnInsert(newNode); + } + + void FixTreeOnInsert(Node node) + { + Debug.Assert(node != null); + Debug.Assert(node.color == RED); + Debug.Assert(node.left == null || node.left.color == BLACK); + Debug.Assert(node.right == null || node.right.color == BLACK); + + Node parentNode = node.parent; + if (parentNode == null) { + // we inserted in the root -> the node must be black + // since this is a root node, making the node black increments the number of black nodes + // on all paths by one, so it is still the same for all paths. + node.color = BLACK; + return; + } + if (parentNode.color == BLACK) { + // if the parent node where we inserted was black, our red node is placed correctly. + // since we inserted a red node, the number of black nodes on each path is unchanged + // -> the tree is still balanced + return; + } + // parentNode is red, so there is a conflict here! + + // because the root is black, parentNode is not the root -> there is a grandparent node + Node grandparentNode = parentNode.parent; + Node uncleNode = Sibling(parentNode); + if (uncleNode != null && uncleNode.color == RED) { + parentNode.color = BLACK; + uncleNode.color = BLACK; + grandparentNode.color = RED; + FixTreeOnInsert(grandparentNode); + return; + } + // now we know: parent is red but uncle is black + // First rotation: + if (node == parentNode.right && parentNode == grandparentNode.left) { + RotateLeft(parentNode); + node = node.left; + } else if (node == parentNode.left && parentNode == grandparentNode.right) { + RotateRight(parentNode); + node = node.right; + } + // because node might have changed, reassign variables: + parentNode = node.parent; + grandparentNode = parentNode.parent; + + // Now recolor a bit: + parentNode.color = BLACK; + grandparentNode.color = RED; + // Second rotation: + if (node == parentNode.left && parentNode == grandparentNode.left) { + RotateRight(grandparentNode); + } else { + // because of the first rotation, this is guaranteed: + Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right); + RotateLeft(grandparentNode); + } + } + + void RemoveNode(Node removedNode) + { + if (removedNode.left != null && removedNode.right != null) { + // replace removedNode with it's in-order successor + + Node leftMost = removedNode.right.LeftMost; + RemoveNode(leftMost); // remove leftMost from its current location + + // and overwrite the removedNode with it + ReplaceNode(removedNode, leftMost); + leftMost.left = removedNode.left; + if (leftMost.left != null) leftMost.left.parent = leftMost; + leftMost.right = removedNode.right; + if (leftMost.right != null) leftMost.right.parent = leftMost; + leftMost.color = removedNode.color; + + UpdateAugmentedData(leftMost); + if (leftMost.parent != null) UpdateAugmentedData(leftMost.parent); + return; + } + + // now either removedNode.left or removedNode.right is null + // get the remaining child + Node parentNode = removedNode.parent; + Node childNode = removedNode.left ?? removedNode.right; + ReplaceNode(removedNode, childNode); + if (parentNode != null) UpdateAugmentedData(parentNode); + if (removedNode.color == BLACK) { + if (childNode != null && childNode.color == RED) { + childNode.color = BLACK; + } else { + FixTreeOnDelete(childNode, parentNode); + } + } + } + + void FixTreeOnDelete(Node node, Node parentNode) + { + Debug.Assert(node == null || node.parent == parentNode); + if (parentNode == null) + return; + + // warning: node may be null + Node sibling = Sibling(node, parentNode); + if (sibling.color == RED) { + parentNode.color = RED; + sibling.color = BLACK; + if (node == parentNode.left) { + RotateLeft(parentNode); + } else { + RotateRight(parentNode); + } + + sibling = Sibling(node, parentNode); // update value of sibling after rotation + } + + if (parentNode.color == BLACK + && sibling.color == BLACK + && GetColor(sibling.left) == BLACK + && GetColor(sibling.right) == BLACK) + { + sibling.color = RED; + FixTreeOnDelete(parentNode, parentNode.parent); + return; + } + + if (parentNode.color == RED + && sibling.color == BLACK + && GetColor(sibling.left) == BLACK + && GetColor(sibling.right) == BLACK) + { + sibling.color = RED; + parentNode.color = BLACK; + return; + } + + if (node == parentNode.left && + sibling.color == BLACK && + GetColor(sibling.left) == RED && + GetColor(sibling.right) == BLACK) + { + sibling.color = RED; + sibling.left.color = BLACK; + RotateRight(sibling); + } + else if (node == parentNode.right && + sibling.color == BLACK && + GetColor(sibling.right) == RED && + GetColor(sibling.left) == BLACK) + { + sibling.color = RED; + sibling.right.color = BLACK; + RotateLeft(sibling); + } + sibling = Sibling(node, parentNode); // update value of sibling after rotation + + sibling.color = parentNode.color; + parentNode.color = BLACK; + if (node == parentNode.left) { + if (sibling.right != null) { + Debug.Assert(sibling.right.color == RED); + sibling.right.color = BLACK; + } + RotateLeft(parentNode); + } else { + if (sibling.left != null) { + Debug.Assert(sibling.left.color == RED); + sibling.left.color = BLACK; + } + RotateRight(parentNode); + } + } + + void ReplaceNode(Node replacedNode, Node newNode) + { + if (replacedNode.parent == null) { + Debug.Assert(replacedNode == root); + root = newNode; + } else { + if (replacedNode.parent.left == replacedNode) + replacedNode.parent.left = newNode; + else + replacedNode.parent.right = newNode; + } + if (newNode != null) { + newNode.parent = replacedNode.parent; + } + replacedNode.parent = null; + } + + void RotateLeft(Node p) + { + // let q be p's right child + Node q = p.right; + Debug.Assert(q != null); + Debug.Assert(q.parent == p); + // set q to be the new root + ReplaceNode(p, q); + + // set p's right child to be q's left child + p.right = q.left; + if (p.right != null) p.right.parent = p; + // set q's left child to be p + q.left = p; + p.parent = q; + UpdateAugmentedData(p); + UpdateAugmentedData(q); + } + + void RotateRight(Node p) + { + // let q be p's left child + Node q = p.left; + Debug.Assert(q != null); + Debug.Assert(q.parent == p); + // set q to be the new root + ReplaceNode(p, q); + + // set p's left child to be q's right child + p.left = q.right; + if (p.left != null) p.left.parent = p; + // set q's right child to be p + q.right = p; + p.parent = q; + UpdateAugmentedData(p); + UpdateAugmentedData(q); + } + + static Node Sibling(Node node) + { + if (node == node.parent.left) + return node.parent.right; + else + return node.parent.left; + } + + static Node Sibling(Node node, Node parentNode) + { + Debug.Assert(node == null || node.parent == parentNode); + if (node == parentNode.left) + return parentNode.right; + else + return parentNode.left; + } + + static bool GetColor(Node node) + { + return node != null ? node.color : BLACK; + } + #endregion + + #region CheckProperties + [Conditional("DATACONSISTENCYTEST")] + internal void CheckProperties() + { + #if DEBUG + if (root != null) { + CheckProperties(root); + + // check red-black property: + int blackCount = -1; + CheckNodeProperties(root, null, RED, 0, ref blackCount); + + // ensure that the tree is compressed: + Node p = root.LeftMost; + Node n = p.Successor; + while (n != null) { + Debug.Assert(!comparisonFunc(p.value, n.value)); + p = n; + n = p.Successor; + } + } + #endif + } + + #if DEBUG + void CheckProperties(Node node) + { + Debug.Assert(node.count > 0); + int totalCount = node.count; + if (node.left != null) { + CheckProperties(node.left); + totalCount += node.left.totalCount; + } + if (node.right != null) { + CheckProperties(node.right); + totalCount += node.right.totalCount; + } + Debug.Assert(node.totalCount == totalCount); + } + + /* + 1. A node is either red or black. + 2. The root is black. + 3. All leaves are black. (The leaves are the NIL children.) + 4. Both children of every red node are black. (So every red node must have a black parent.) + 5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.) + */ + void CheckNodeProperties(Node node, Node parentNode, bool parentColor, int blackCount, ref int expectedBlackCount) + { + if (node == null) return; + + Debug.Assert(node.parent == parentNode); + + if (parentColor == RED) { + Debug.Assert(node.color == BLACK); + } + if (node.color == BLACK) { + blackCount++; + } + if (node.left == null && node.right == null) { + // node is a leaf node: + if (expectedBlackCount == -1) + expectedBlackCount = blackCount; + else + Debug.Assert(expectedBlackCount == blackCount); + } + CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount); + CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount); + } + #endif + #endregion + + #region GetTreeAsString + internal string GetTreeAsString() + { + #if DEBUG + if (root == null) + return "<empty tree>"; + StringBuilder b = new StringBuilder(); + AppendTreeToString(root, b, 0); + return b.ToString(); + #else + return "Not available in release build."; + #endif + } + + #if DEBUG + static void AppendTreeToString(Node node, StringBuilder b, int indent) + { + if (node.color == RED) + b.Append("RED "); + else + b.Append("BLACK "); + b.AppendLine(node.ToString()); + indent += 2; + if (node.left != null) { + b.Append(' ', indent); + b.Append("L: "); + AppendTreeToString(node.left, b, indent); + } + if (node.right != null) { + b.Append(' ', indent); + b.Append("R: "); + AppendTreeToString(node.right, b, indent); + } + } + #endif + #endregion + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Constants.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Constants.cs new file mode 100644 index 000000000..0344ada80 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Constants.cs @@ -0,0 +1,15 @@ +// 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; + +namespace Tango.Scripting.Editors.Utils +{ + static class Constants + { + /// <summary> + /// Multiply with this constant to convert from points to device-independent pixels. + /// </summary> + public const double PixelPerPoint = 4 / 3.0; + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/DelayedEvents.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/DelayedEvents.cs new file mode 100644 index 000000000..8afc9f2ee --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/DelayedEvents.cs @@ -0,0 +1,48 @@ +// 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.Collections.Generic; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Maintains a list of delayed events to raise. + /// </summary> + sealed class DelayedEvents + { + struct EventCall + { + EventHandler handler; + object sender; + EventArgs e; + + public EventCall(EventHandler handler, object sender, EventArgs e) + { + this.handler = handler; + this.sender = sender; + this.e = e; + } + + public void Call() + { + handler(sender, e); + } + } + + Queue<EventCall> eventCalls = new Queue<EventCall>(); + + public void DelayedRaise(EventHandler handler, object sender, EventArgs e) + { + if (handler != null) { + eventCalls.Enqueue(new EventCall(handler, sender, e)); + } + } + + public void RaiseEvents() + { + while (eventCalls.Count > 0) + eventCalls.Dequeue().Call(); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs new file mode 100644 index 000000000..66496d68f --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs @@ -0,0 +1,174 @@ +// 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.Collections.Generic; +using System.Diagnostics; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Double-ended queue. + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] + [Serializable] + public sealed class Deque<T> : ICollection<T> + { + T[] arr = Empty<T>.Array; + int size, head, tail; + + /// <inheritdoc/> + public int Count { + get { return size; } + } + + /// <inheritdoc/> + public void Clear() + { + arr = Empty<T>.Array; + size = 0; + head = 0; + tail = 0; + } + + /// <summary> + /// Gets/Sets an element inside the deque. + /// </summary> + public T this[int index] { + get { + ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1); + return arr[(head + index) % arr.Length]; + } + set { + ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1); + arr[(head + index) % arr.Length] = value; + } + } + + /// <summary> + /// Adds an element to the end of the deque. + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1702:CompoundWordsShouldBeCasedCorrectly", MessageId = "PushBack")] + public void PushBack(T item) + { + if (size == arr.Length) + SetCapacity(Math.Max(4, arr.Length * 2)); + arr[tail++] = item; + if (tail == arr.Length) tail = 0; + size++; + } + + /// <summary> + /// Pops an element from the end of the deque. + /// </summary> + public T PopBack() + { + if (size == 0) + throw new InvalidOperationException(); + if (tail == 0) + tail = arr.Length - 1; + else + tail--; + T val = arr[tail]; + arr[tail] = default(T); // allow GC to collect the element + size--; + return val; + } + + /// <summary> + /// Adds an element to the front of the deque. + /// </summary> + public void PushFront(T item) + { + if (size == arr.Length) + SetCapacity(Math.Max(4, arr.Length * 2)); + if (head == 0) + head = arr.Length - 1; + else + head--; + arr[head] = item; + size++; + } + + /// <summary> + /// Pops an element from the end of the deque. + /// </summary> + public T PopFront() + { + if (size == 0) + throw new InvalidOperationException(); + T val = arr[head]; + arr[head] = default(T); // allow GC to collect the element + head++; + if (head == arr.Length) head = 0; + size--; + return val; + } + + void SetCapacity(int capacity) + { + T[] newArr = new T[capacity]; + CopyTo(newArr, 0); + head = 0; + tail = (size == capacity) ? 0 : size; + arr = newArr; + } + + /// <inheritdoc/> + public IEnumerator<T> GetEnumerator() + { + if (head < tail) { + for (int i = head; i < tail; i++) + yield return arr[i]; + } else { + for (int i = head; i < arr.Length; i++) + yield return arr[i]; + for (int i = 0; i < tail; i++) + yield return arr[i]; + } + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { + return this.GetEnumerator(); + } + + bool ICollection<T>.IsReadOnly { + get { return false; } + } + + void ICollection<T>.Add(T item) + { + PushBack(item); + } + + /// <inheritdoc/> + public bool Contains(T item) + { + EqualityComparer<T> comparer = EqualityComparer<T>.Default; + foreach (T element in this) + if (comparer.Equals(item, element)) + return true; + return false; + } + + /// <inheritdoc/> + public void CopyTo(T[] array, int arrayIndex) + { + if (array == null) + throw new ArgumentNullException("array"); + if (head < tail) { + Array.Copy(arr, head, array, arrayIndex, tail - head); + } else { + int num1 = arr.Length - head; + Array.Copy(arr, head, array, arrayIndex, num1); + Array.Copy(arr, 0, array, arrayIndex + num1, tail); + } + } + + bool ICollection<T>.Remove(T item) + { + throw new NotSupportedException(); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Empty.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Empty.cs new file mode 100644 index 000000000..1f890dd7a --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Empty.cs @@ -0,0 +1,17 @@ +// 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.Collections.ObjectModel; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Provides immutable empty list instances. + /// </summary> + static class Empty<T> + { + public static readonly T[] Array = new T[0]; + //public static readonly ReadOnlyCollection<T> ReadOnlyCollection = new ReadOnlyCollection<T>(Array); + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ExtensionMethods.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ExtensionMethods.cs new file mode 100644 index 000000000..d9b00ed33 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ExtensionMethods.cs @@ -0,0 +1,214 @@ +// 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.Collections.Generic; +using System.Diagnostics; +using System.Windows; +using System.Windows.Controls; +using System.Windows.Media; +using System.Xml; + +namespace Tango.Scripting.Editors.Utils +{ + static class ExtensionMethods + { + #region Epsilon / IsClose / CoerceValue + /// <summary> + /// Epsilon used for <c>IsClose()</c> implementations. + /// We can use up quite a few digits in front of the decimal point (due to visual positions being relative to document origin), + /// and there's no need to be too accurate (we're dealing with pixels here), + /// so we will use the value 0.01. + /// Previosly we used 1e-8 but that was causing issues: + /// http://community.sharpdevelop.net/forums/t/16048.aspx + /// </summary> + public const double Epsilon = 0.01; + + /// <summary> + /// Returns true if the doubles are close (difference smaller than 0.01). + /// </summary> + public static bool IsClose(this double d1, double d2) + { + if (d1 == d2) // required for infinities + return true; + return Math.Abs(d1 - d2) < Epsilon; + } + + /// <summary> + /// Returns true if the doubles are close (difference smaller than 0.01). + /// </summary> + public static bool IsClose(this Size d1, Size d2) + { + return IsClose(d1.Width, d2.Width) && IsClose(d1.Height, d2.Height); + } + + /// <summary> + /// Returns true if the doubles are close (difference smaller than 0.01). + /// </summary> + public static bool IsClose(this Vector d1, Vector d2) + { + return IsClose(d1.X, d2.X) && IsClose(d1.Y, d2.Y); + } + + /// <summary> + /// Forces the value to stay between mininum and maximum. + /// </summary> + /// <returns>minimum, if value is less than minimum. + /// Maximum, if value is greater than maximum. + /// Otherwise, value.</returns> + public static double CoerceValue(this double value, double minimum, double maximum) + { + return Math.Max(Math.Min(value, maximum), minimum); + } + + /// <summary> + /// Forces the value to stay between mininum and maximum. + /// </summary> + /// <returns>minimum, if value is less than minimum. + /// Maximum, if value is greater than maximum. + /// Otherwise, value.</returns> + public static int CoerceValue(this int value, int minimum, int maximum) + { + return Math.Max(Math.Min(value, maximum), minimum); + } + #endregion + + #region CreateTypeface + /// <summary> + /// Creates typeface from the framework element. + /// </summary> + public static Typeface CreateTypeface(this FrameworkElement fe) + { + return new Typeface((FontFamily)fe.GetValue(TextBlock.FontFamilyProperty), + (FontStyle)fe.GetValue(TextBlock.FontStyleProperty), + (FontWeight)fe.GetValue(TextBlock.FontWeightProperty), + (FontStretch)fe.GetValue(TextBlock.FontStretchProperty)); + } + #endregion + + #region AddRange / Sequence + public static void AddRange<T>(this ICollection<T> collection, IEnumerable<T> elements) + { + foreach (T e in elements) + collection.Add(e); + } + + /// <summary> + /// Creates an IEnumerable with a single value. + /// </summary> + public static IEnumerable<T> Sequence<T>(T value) + { + yield return value; + } + #endregion + + #region XML reading + /// <summary> + /// Gets the value of the attribute, or null if the attribute does not exist. + /// </summary> + public static string GetAttributeOrNull(this XmlElement element, string attributeName) + { + XmlAttribute attr = element.GetAttributeNode(attributeName); + return attr != null ? attr.Value : null; + } + + /// <summary> + /// Gets the value of the attribute as boolean, or null if the attribute does not exist. + /// </summary> + public static bool? GetBoolAttribute(this XmlElement element, string attributeName) + { + XmlAttribute attr = element.GetAttributeNode(attributeName); + return attr != null ? (bool?)XmlConvert.ToBoolean(attr.Value) : null; + } + + /// <summary> + /// Gets the value of the attribute as boolean, or null if the attribute does not exist. + /// </summary> + public static bool? GetBoolAttribute(this XmlReader reader, string attributeName) + { + string attributeValue = reader.GetAttribute(attributeName); + if (attributeValue == null) + return null; + else + return XmlConvert.ToBoolean(attributeValue); + } + #endregion + + #region DPI independence + public static Rect TransformToDevice(this Rect rect, Visual visual) + { + Matrix matrix = PresentationSource.FromVisual(visual).CompositionTarget.TransformToDevice; + return Rect.Transform(rect, matrix); + } + + public static Rect TransformFromDevice(this Rect rect, Visual visual) + { + Matrix matrix = PresentationSource.FromVisual(visual).CompositionTarget.TransformFromDevice; + return Rect.Transform(rect, matrix); + } + + public static Size TransformToDevice(this Size size, Visual visual) + { + Matrix matrix = PresentationSource.FromVisual(visual).CompositionTarget.TransformToDevice; + return new Size(size.Width * matrix.M11, size.Height * matrix.M22); + } + + public static Size TransformFromDevice(this Size size, Visual visual) + { + Matrix matrix = PresentationSource.FromVisual(visual).CompositionTarget.TransformFromDevice; + return new Size(size.Width * matrix.M11, size.Height * matrix.M22); + } + + public static Point TransformToDevice(this Point point, Visual visual) + { + Matrix matrix = PresentationSource.FromVisual(visual).CompositionTarget.TransformToDevice; + return new Point(point.X * matrix.M11, point.Y * matrix.M22); + } + + public static Point TransformFromDevice(this Point point, Visual visual) + { + Matrix matrix = PresentationSource.FromVisual(visual).CompositionTarget.TransformFromDevice; + return new Point(point.X * matrix.M11, point.Y * matrix.M22); + } + #endregion + + #region System.Drawing <-> WPF conversions + public static System.Drawing.Point ToSystemDrawing(this Point p) + { + return new System.Drawing.Point((int)p.X, (int)p.Y); + } + + public static Point ToWpf(this System.Drawing.Point p) + { + return new Point(p.X, p.Y); + } + + public static Size ToWpf(this System.Drawing.Size s) + { + return new Size(s.Width, s.Height); + } + + public static Rect ToWpf(this System.Drawing.Rectangle rect) + { + return new Rect(rect.Location.ToWpf(), rect.Size.ToWpf()); + } + #endregion + + [Conditional("DEBUG")] + public static void CheckIsFrozen(Freezable f) + { + if (f != null && !f.IsFrozen) + Debug.WriteLine("Performance warning: Not frozen: " + f.ToString()); + } + + [Conditional("DEBUG")] + public static void Log(bool condition, string format, params object[] args) + { + if (condition) { + string output = DateTime.Now.ToString("hh:MM:ss") + ": " + string.Format(format, args) + Environment.NewLine + Environment.StackTrace; + Console.WriteLine(output); + Debug.WriteLine(output); + } + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/FileReader.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/FileReader.cs new file mode 100644 index 000000000..b44c589d7 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/FileReader.cs @@ -0,0 +1,208 @@ +// 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.IO; +using System.Text; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Class that can open text files with auto-detection of the encoding. + /// </summary> + public static class FileReader + { + /// <summary> + /// Gets if the given encoding is a Unicode encoding (UTF). + /// </summary> + /// <remarks> + /// Returns true for UTF-7, UTF-8, UTF-16 LE, UTF-16 BE, UTF-32 LE and UTF-32 BE. + /// Returns false for all other encodings. + /// </remarks> + public static bool IsUnicode(Encoding encoding) + { + if (encoding == null) + throw new ArgumentNullException("encoding"); + switch (encoding.CodePage) { + case 65000: // UTF-7 + case 65001: // UTF-8 + case 1200: // UTF-16 LE + case 1201: // UTF-16 BE + case 12000: // UTF-32 LE + case 12001: // UTF-32 BE + return true; + default: + return false; + } + } + + /// <summary> + /// Reads the content of the given stream. + /// </summary> + /// <param name="stream">The stream to read. + /// The stream must support seeking and must be positioned at its beginning.</param> + /// <param name="defaultEncoding">The encoding to use if the encoding cannot be auto-detected.</param> + /// <returns>The file content as string.</returns> + public static string ReadFileContent(Stream stream, Encoding defaultEncoding) + { + using (StreamReader reader = OpenStream(stream, defaultEncoding)) { + return reader.ReadToEnd(); + } + } + + /// <summary> + /// Reads the content of the file. + /// </summary> + /// <param name="fileName">The file name.</param> + /// <param name="defaultEncoding">The encoding to use if the encoding cannot be auto-detected.</param> + /// <returns>The file content as string.</returns> + public static string ReadFileContent(string fileName, Encoding defaultEncoding) + { + using (FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read)) { + return ReadFileContent(fs, defaultEncoding); + } + } + + /// <summary> + /// Opens the specified file for reading. + /// </summary> + /// <param name="fileName">The file to open.</param> + /// <param name="defaultEncoding">The encoding to use if the encoding cannot be auto-detected.</param> + /// <returns>Returns a StreamReader that reads from the stream. Use + /// <see cref="StreamReader.CurrentEncoding"/> to get the encoding that was used.</returns> + public static StreamReader OpenFile(string fileName, Encoding defaultEncoding) + { + if (fileName == null) + throw new ArgumentNullException("fileName"); + FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read); + try { + return OpenStream(fs, defaultEncoding); + // don't use finally: the stream must be kept open until the StreamReader closes it + } catch { + fs.Dispose(); + throw; + } + } + + /// <summary> + /// Opens the specified stream for reading. + /// </summary> + /// <param name="stream">The stream to open.</param> + /// <param name="defaultEncoding">The encoding to use if the encoding cannot be auto-detected.</param> + /// <returns>Returns a StreamReader that reads from the stream. Use + /// <see cref="StreamReader.CurrentEncoding"/> to get the encoding that was used.</returns> + public static StreamReader OpenStream(Stream stream, Encoding defaultEncoding) + { + if (stream == null) + throw new ArgumentNullException("stream"); + if (stream.Position != 0) + throw new ArgumentException("stream is not positioned at beginning.", "stream"); + if (defaultEncoding == null) + throw new ArgumentNullException("defaultEncoding"); + + if (stream.Length >= 2) { + // the autodetection of StreamReader is not capable of detecting the difference + // between ISO-8859-1 and UTF-8 without BOM. + int firstByte = stream.ReadByte(); + int secondByte = stream.ReadByte(); + switch ((firstByte << 8) | secondByte) { + case 0x0000: // either UTF-32 Big Endian or a binary file; use StreamReader + case 0xfffe: // Unicode BOM (UTF-16 LE or UTF-32 LE) + case 0xfeff: // UTF-16 BE BOM + case 0xefbb: // start of UTF-8 BOM + // StreamReader autodetection works + stream.Position = 0; + return new StreamReader(stream); + default: + return AutoDetect(stream, (byte)firstByte, (byte)secondByte, defaultEncoding); + } + } else { + if (defaultEncoding != null) { + return new StreamReader(stream, defaultEncoding); + } else { + return new StreamReader(stream); + } + } + } + + static StreamReader AutoDetect(Stream fs, byte firstByte, byte secondByte, Encoding defaultEncoding) + { + int max = (int)Math.Min(fs.Length, 500000); // look at max. 500 KB + const int ASCII = 0; + const int Error = 1; + const int UTF8 = 2; + const int UTF8Sequence = 3; + int state = ASCII; + int sequenceLength = 0; + byte b; + for (int i = 0; i < max; i++) { + if (i == 0) { + b = firstByte; + } else if (i == 1) { + b = secondByte; + } else { + b = (byte)fs.ReadByte(); + } + if (b < 0x80) { + // normal ASCII character + if (state == UTF8Sequence) { + state = Error; + break; + } + } else if (b < 0xc0) { + // 10xxxxxx : continues UTF8 byte sequence + if (state == UTF8Sequence) { + --sequenceLength; + if (sequenceLength < 0) { + state = Error; + break; + } else if (sequenceLength == 0) { + state = UTF8; + } + } else { + state = Error; + break; + } + } else if (b >= 0xc2 && b < 0xf5) { + // beginning of byte sequence + if (state == UTF8 || state == ASCII) { + state = UTF8Sequence; + if (b < 0xe0) { + sequenceLength = 1; // one more byte following + } else if (b < 0xf0) { + sequenceLength = 2; // two more bytes following + } else { + sequenceLength = 3; // three more bytes following + } + } else { + state = Error; + break; + } + } else { + // 0xc0, 0xc1, 0xf5 to 0xff are invalid in UTF-8 (see RFC 3629) + state = Error; + break; + } + } + fs.Position = 0; + switch (state) { + case ASCII: + case Error: + // when the file seems to be ASCII or non-UTF8, + // we read it using the user-specified encoding so it is saved again + // using that encoding. + if (IsUnicode(defaultEncoding)) { + // the file is not Unicode, so don't read it using Unicode even if the + // user has choosen Unicode as the default encoding. + + // If we don't do this, SD will end up always adding a Byte Order Mark + // to ASCII files. + defaultEncoding = Encoding.Default; // use system encoding instead + } + return new StreamReader(fs, defaultEncoding); + default: + return new StreamReader(fs); + } + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ImmutableStack.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ImmutableStack.cs new file mode 100644 index 000000000..18a835fd2 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ImmutableStack.cs @@ -0,0 +1,114 @@ +// 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.Collections.Generic; +using System.Diagnostics; +using System.Text; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// An immutable stack. + /// + /// Using 'foreach' on the stack will return the items from top to bottom (in the order they would be popped). + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1711:IdentifiersShouldNotHaveIncorrectSuffix")] + [Serializable] + public sealed class ImmutableStack<T> : IEnumerable<T> + { + /// <summary> + /// Gets the empty stack instance. + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes", Justification = "ImmutableStack is immutable")] + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>(); + + readonly T value; + readonly ImmutableStack<T> next; + + private ImmutableStack() + { + } + + private ImmutableStack(T value, ImmutableStack<T> next) + { + this.value = value; + this.next = next; + } + + /// <summary> + /// Pushes an item on the stack. This does not modify the stack itself, but returns a new + /// one with the value pushed. + /// </summary> + public ImmutableStack<T> Push(T item) + { + return new ImmutableStack<T>(item, this); + } + + /// <summary> + /// Gets the item on the top of the stack. + /// </summary> + /// <exception cref="InvalidOperationException">The stack is empty.</exception> + public T Peek() + { + if (IsEmpty) + throw new InvalidOperationException("Operation not valid on empty stack."); + return value; + } + + internal T UnsafePeek() + { + Debug.Assert(!IsEmpty); + return value; + } + + /// <summary> + /// Gets the stack with the top item removed. + /// </summary> + /// <exception cref="InvalidOperationException">The stack is empty.</exception> + public ImmutableStack<T> Pop() + { + if (IsEmpty) + throw new InvalidOperationException("Operation not valid on empty stack."); + return next; + } + + /// <summary> + /// Gets if this stack is empty. + /// </summary> + public bool IsEmpty { + get { return next == null; } + } + + /// <summary> + /// Gets an enumerator that iterates through the stack top-to-bottom. + /// </summary> + public IEnumerator<T> GetEnumerator() + { + ImmutableStack<T> t = this; + while (!t.IsEmpty) { + yield return t.value; + t = t.next; + } + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { + return this.GetEnumerator(); + } + + /// <inheritdoc/> + public override string ToString() + { + StringBuilder b = new StringBuilder("[Stack"); + foreach (T val in this) { + b.Append(' '); + b.Append(val); + } + b.Append(']'); + return b.ToString(); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/NullSafeCollection.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/NullSafeCollection.cs new file mode 100644 index 000000000..8a37c54ae --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/NullSafeCollection.cs @@ -0,0 +1,31 @@ +// 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.Collections.ObjectModel; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// A collection that cannot contain null values. + /// </summary> + [Serializable] + public class NullSafeCollection<T> : Collection<T> where T : class + { + /// <inheritdoc/> + protected override void InsertItem(int index, T item) + { + if (item == null) + throw new ArgumentNullException("item"); + base.InsertItem(index, item); + } + + /// <inheritdoc/> + protected override void SetItem(int index, T item) + { + if (item == null) + throw new ArgumentNullException("item"); + base.SetItem(index, item); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ObserveAddRemoveCollection.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ObserveAddRemoveCollection.cs new file mode 100644 index 000000000..091de0d91 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ObserveAddRemoveCollection.cs @@ -0,0 +1,63 @@ +// 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.Collections.ObjectModel; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// A collection where adding and removing items causes a callback. + /// It is valid for the onAdd callback to throw an exception - this will prevent the new item from + /// being added to the collection. + /// </summary> + sealed class ObserveAddRemoveCollection<T> : Collection<T> + { + readonly Action<T> onAdd, onRemove; + + public ObserveAddRemoveCollection(Action<T> onAdd, Action<T> onRemove) + { + this.onAdd = onAdd; + this.onRemove = onRemove; + } + + protected override void ClearItems() + { + if (onRemove != null) { + foreach (T val in this) + onRemove(val); + } + base.ClearItems(); + } + + protected override void InsertItem(int index, T item) + { + if (onAdd != null) + onAdd(item); + base.InsertItem(index, item); + } + + protected override void RemoveItem(int index) + { + if (onRemove != null) + onRemove(this[index]); + base.RemoveItem(index); + } + + protected override void SetItem(int index, T item) + { + if (onRemove != null) + onRemove(this[index]); + try { + if (onAdd != null) + onAdd(item); + } catch { + // When adding the new item fails, just remove the old one + // (we cannot keep the old item since we already successfully called onRemove for it) + base.RemoveAt(index); + throw; + } + base.SetItem(index, item); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PixelSnapHelpers.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PixelSnapHelpers.cs new file mode 100644 index 000000000..abd859533 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PixelSnapHelpers.cs @@ -0,0 +1,92 @@ +// 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.Windows; +using System.Windows.Media; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Contains static helper methods for aligning stuff on a whole number of pixels. + /// </summary> + public static class PixelSnapHelpers + { + /// <summary> + /// Gets the pixel size on the screen containing visual. + /// This method does not take transforms on visual into account. + /// </summary> + public static Size GetPixelSize(Visual visual) + { + if (visual == null) + throw new ArgumentNullException("visual"); + PresentationSource source = PresentationSource.FromVisual(visual); + if (source != null) { + Matrix matrix = source.CompositionTarget.TransformFromDevice; + return new Size(matrix.M11, matrix.M22); + } else { + return new Size(1, 1); + } + } + + /// <summary> + /// Aligns <paramref name="value"/> on the next middle of a pixel. + /// </summary> + /// <param name="value">The value that should be aligned</param> + /// <param name="pixelSize">The size of one pixel</param> + public static double PixelAlign(double value, double pixelSize) + { + // 0 -> 0.5 + // 0.1 -> 0.5 + // 0.5 -> 0.5 + // 0.9 -> 0.5 + // 1 -> 1.5 + return pixelSize * (Math.Round((value / pixelSize) + 0.5) - 0.5); + } + + /// <summary> + /// Aligns the borders of rect on the middles of pixels. + /// </summary> + public static Rect PixelAlign(Rect rect, Size pixelSize) + { + rect.X = PixelAlign(rect.X, pixelSize.Width); + rect.Y = PixelAlign(rect.Y, pixelSize.Height); + rect.Width = Round(rect.Width, pixelSize.Width); + rect.Height = Round(rect.Height, pixelSize.Height); + return rect; + } + + /// <summary> + /// Rounds <paramref name="point"/> to whole number of pixels. + /// </summary> + public static Point Round(Point point, Size pixelSize) + { + return new Point(Round(point.X, pixelSize.Width), Round(point.Y, pixelSize.Height)); + } + + /// <summary> + /// Rounds val to whole number of pixels. + /// </summary> + public static Rect Round(Rect rect, Size pixelSize) + { + return new Rect(Round(rect.X, pixelSize.Width), Round(rect.Y, pixelSize.Height), + Round(rect.Width, pixelSize.Width), Round(rect.Height, pixelSize.Height)); + } + + /// <summary> + /// Rounds <paramref name="value"/> to a whole number of pixels. + /// </summary> + public static double Round(double value, double pixelSize) + { + return pixelSize * Math.Round(value / pixelSize); + } + + /// <summary> + /// Rounds <paramref name="value"/> to an whole odd number of pixels. + /// </summary> + public static double RoundToOdd(double value, double pixelSize) + { + return Round(value - pixelSize, pixelSize * 2) + pixelSize; + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PropertyChangedWeakEventManager.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PropertyChangedWeakEventManager.cs new file mode 100644 index 000000000..9b70c8f54 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PropertyChangedWeakEventManager.cs @@ -0,0 +1,26 @@ +// 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.ComponentModel; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// WeakEventManager for INotifyPropertyChanged.PropertyChanged. + /// </summary> + public sealed class PropertyChangedWeakEventManager : WeakEventManagerBase<PropertyChangedWeakEventManager, INotifyPropertyChanged> + { + /// <inheritdoc/> + protected override void StartListening(INotifyPropertyChanged source) + { + source.PropertyChanged += DeliverEvent; + } + + /// <inheritdoc/> + protected override void StopListening(INotifyPropertyChanged source) + { + source.PropertyChanged -= DeliverEvent; + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Rope.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Rope.cs new file mode 100644 index 000000000..d27edd199 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Rope.cs @@ -0,0 +1,789 @@ +// 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<T>, 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 the rope. + /// This operation runs in linear time to the number of rope nodes touched since the last clone was created. + /// If you count the per-node cost to the operation modifying 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<char> 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(); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeNode.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeNode.cs new file mode 100644 index 000000000..87f060c1b --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeNode.cs @@ -0,0 +1,605 @@ +// 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.Runtime.Serialization; + +using System.Text; + +namespace Tango.Scripting.Editors.Utils +{ + // Class used to represent a node in the tree. + // There are three types of nodes: + // Concat nodes: height>0, left!=null, right!=null, contents==null + // Leaf nodes: height==0, left==null, right==null, contents!=null + // Function nodes: height==0, left==null, right==null, contents==null, are of type FunctionNode<T> + + [Serializable] + class RopeNode<T> + { + internal const int NodeSize = 256; + + internal static readonly RopeNode<T> emptyRopeNode = new RopeNode<T> { isShared = true, contents = new T[RopeNode<T>.NodeSize] }; + + // Fields for pointers to sub-nodes. Only non-null for concat nodes (height>=1) + internal RopeNode<T> left, right; + internal volatile bool isShared; // specifies whether this node is shared between multiple ropes + // the total length of all text in this subtree + internal int length; + // the height of this subtree: 0 for leaf nodes; 1+max(left.height,right.height) for concat nodes + internal byte height; + + // The character data. Only non-null for leaf nodes (height=0) that aren't function nodes. + internal T[] contents; + + internal int Balance { + get { return right.height - left.height; } + } + + [Conditional("DATACONSISTENCYTEST")] + internal void CheckInvariants() + { + if (height == 0) { + Debug.Assert(left == null && right == null); + if (contents == null) { + Debug.Assert(this is FunctionNode<T>); + Debug.Assert(length > 0); + Debug.Assert(isShared); + } else { + Debug.Assert(contents != null && contents.Length == NodeSize); + Debug.Assert(length >= 0 && length <= NodeSize); + } + } else { + Debug.Assert(left != null && right != null); + Debug.Assert(contents == null); + Debug.Assert(length == left.length + right.length); + Debug.Assert(height == 1 + Math.Max(left.height, right.height)); + Debug.Assert(Math.Abs(this.Balance) <= 1); + + // this is an additional invariant that forces the tree to combine small leafs to prevent excessive memory usage: + Debug.Assert(length > NodeSize); + // note that this invariant ensures that all nodes except for the empty rope's single node have at least length 1 + + if (isShared) + Debug.Assert(left.isShared && right.isShared); + left.CheckInvariants(); + right.CheckInvariants(); + } + } + + internal RopeNode<T> Clone() + { + if (height == 0) { + // If a function node needs cloning, we'll evaluate it. + if (contents == null) + return GetContentNode().Clone(); + T[] newContents = new T[NodeSize]; + contents.CopyTo(newContents, 0); + return new RopeNode<T> { + length = this.length, + contents = newContents + }; + } else { + return new RopeNode<T> { + left = this.left, + right = this.right, + length = this.length, + height = this.height + }; + } + } + + internal RopeNode<T> CloneIfShared() + { + if (isShared) + return Clone(); + else + return this; + } + + internal void Publish() + { + if (!isShared) { + if (left != null) + left.Publish(); + if (right != null) + right.Publish(); + // it's important that isShared=true is set at the end: + // Publish() must not return until the whole subtree is marked as shared, even when + // Publish() is called concurrently. + isShared = true; + } + } + + internal static RopeNode<T> CreateFromArray(T[] arr, int index, int length) + { + if (length == 0) { + return emptyRopeNode; + } + RopeNode<T> node = CreateNodes(length); + return node.StoreElements(0, arr, index, length); + } + + internal static RopeNode<T> CreateNodes(int totalLength) + { + int leafCount = (totalLength + NodeSize - 1) / NodeSize; + return CreateNodes(leafCount, totalLength); + } + + static RopeNode<T> CreateNodes(int leafCount, int totalLength) + { + Debug.Assert(leafCount > 0); + Debug.Assert(totalLength > 0); + RopeNode<T> result = new RopeNode<T>(); + result.length = totalLength; + if (leafCount == 1) { + result.contents = new T[NodeSize]; + } else { + int rightSide = leafCount / 2; + int leftSide = leafCount - rightSide; + int leftLength = leftSide * NodeSize; + result.left = CreateNodes(leftSide, leftLength); + result.right = CreateNodes(rightSide, totalLength - leftLength); + result.height = (byte)(1 + Math.Max(result.left.height, result.right.height)); + } + return result; + } + + /// <summary> + /// Balances this node and recomputes the 'height' field. + /// This method assumes that the children of this node are already balanced and have an up-to-date 'height' value. + /// </summary> + internal void Rebalance() + { + // Rebalance() shouldn't be called on shared nodes - it's only called after modifications! + Debug.Assert(!isShared); + // leaf nodes are always balanced (we don't use 'height' to detect leaf nodes here + // because Balance is supposed to recompute the height). + if (left == null) + return; + + // ensure we didn't miss a MergeIfPossible step + Debug.Assert(this.length > NodeSize); + + // We need to loop until it's balanced. Rotations might cause two small leaves to combine to a larger one, + // which changes the height and might mean we need additional balancing steps. + while (Math.Abs(this.Balance) > 1) { + // AVL balancing + // note: because we don't care about the identity of concat nodes, this works a little different than usual + // tree rotations: in our implementation, the "this" node will stay at the top, only its children are rearranged + if (this.Balance > 1) { + if (right.Balance < 0) { + right = right.CloneIfShared(); + right.RotateRight(); + } + this.RotateLeft(); + // If 'this' was unbalanced by more than 2, we've shifted some of the inbalance to the left node; so rebalance that. + this.left.Rebalance(); + } else if (this.Balance < -1) { + if (left.Balance > 0) { + left = left.CloneIfShared(); + left.RotateLeft(); + } + this.RotateRight(); + // If 'this' was unbalanced by more than 2, we've shifted some of the inbalance to the right node; so rebalance that. + this.right.Rebalance(); + } + } + + Debug.Assert(Math.Abs(this.Balance) <= 1); + this.height = (byte)(1 + Math.Max(left.height, right.height)); + } + + void RotateLeft() + { + Debug.Assert(!isShared); + + /* Rotate tree to the left + * + * this this + * / \ / \ + * A right ===> left C + * / \ / \ + * B C A B + */ + RopeNode<T> a = left; + RopeNode<T> b = right.left; + RopeNode<T> c = right.right; + // reuse right concat node, if possible + this.left = right.isShared ? new RopeNode<T>() : right; + this.left.left = a; + this.left.right = b; + this.left.length = a.length + b.length; + this.left.height = (byte)(1 + Math.Max(a.height, b.height)); + this.right = c; + + this.left.MergeIfPossible(); + } + + void RotateRight() + { + Debug.Assert(!isShared); + + /* Rotate tree to the right + * + * this this + * / \ / \ + * left C ===> A right + * / \ / \ + * A B B C + */ + RopeNode<T> a = left.left; + RopeNode<T> b = left.right; + RopeNode<T> c = right; + // reuse left concat node, if possible + this.right = left.isShared ? new RopeNode<T>() : left; + this.right.left = b; + this.right.right = c; + this.right.length = b.length + c.length; + this.right.height = (byte)(1 + Math.Max(b.height, c.height)); + this.left = a; + + this.right.MergeIfPossible(); + } + + void MergeIfPossible() + { + Debug.Assert(!isShared); + + if (this.length <= NodeSize) { + // Convert this concat node to leaf node. + // We know left and right cannot be concat nodes (they would have merged already), + // but they could be function nodes. + this.height = 0; + int lengthOnLeftSide = this.left.length; + if (this.left.isShared) { + this.contents = new T[NodeSize]; + left.CopyTo(0, this.contents, 0, lengthOnLeftSide); + } else { + // must be a leaf node: function nodes are always marked shared + Debug.Assert(this.left.contents != null); + // steal buffer from left side + this.contents = this.left.contents; + #if DEBUG + // In debug builds, explicitly mark left node as 'damaged' - but no one else should be using it + // because it's not shared. + this.left.contents = Empty<T>.Array; + #endif + } + this.left = null; + right.CopyTo(0, this.contents, lengthOnLeftSide, this.right.length); + this.right = null; + } + } + + /// <summary> + /// Copies from the array to this node. + /// </summary> + internal RopeNode<T> StoreElements(int index, T[] array, int arrayIndex, int count) + { + RopeNode<T> result = this.CloneIfShared(); + // result cannot be function node after a call to Clone() + if (result.height == 0) { + // leaf node: + Array.Copy(array, arrayIndex, result.contents, index, count); + } else { + // concat node: + if (index + count <= result.left.length) { + result.left = result.left.StoreElements(index, array, arrayIndex, count); + } else if (index >= this.left.length) { + result.right = result.right.StoreElements(index - result.left.length, array, arrayIndex, count); + } else { + int amountInLeft = result.left.length - index; + result.left = result.left.StoreElements(index, array, arrayIndex, amountInLeft); + result.right = result.right.StoreElements(0, array, arrayIndex + amountInLeft, count - amountInLeft); + } + result.Rebalance(); // tree layout might have changed if function nodes were replaced with their content + } + return result; + } + + /// <summary> + /// Copies from this node to the array. + /// </summary> + internal void CopyTo(int index, T[] array, int arrayIndex, int count) + { + if (height == 0) { + if (this.contents == null) { + // function node + this.GetContentNode().CopyTo(index, array, arrayIndex, count); + } else { + // leaf node + Array.Copy(this.contents, index, array, arrayIndex, count); + } + } else { + // concat node + if (index + count <= this.left.length) { + this.left.CopyTo(index, array, arrayIndex, count); + } else if (index >= this.left.length) { + this.right.CopyTo(index - this.left.length, array, arrayIndex, count); + } else { + int amountInLeft = this.left.length - index; + this.left.CopyTo(index, array, arrayIndex, amountInLeft); + this.right.CopyTo(0, array, arrayIndex + amountInLeft, count - amountInLeft); + } + } + } + + internal RopeNode<T> SetElement(int offset, T value) + { + RopeNode<T> result = CloneIfShared(); + // result of CloneIfShared() is leaf or concat node + if (result.height == 0) { + result.contents[offset] = value; + } else { + if (offset < result.left.length) { + result.left = result.left.SetElement(offset, value); + } else { + result.right = result.right.SetElement(offset - result.left.length, value); + } + result.Rebalance(); // tree layout might have changed if function nodes were replaced with their content + } + return result; + } + + internal static RopeNode<T> Concat(RopeNode<T> left, RopeNode<T> right) + { + if (left.length == 0) + return right; + if (right.length == 0) + return left; + + if (left.length + right.length <= NodeSize) { + left = left.CloneIfShared(); + // left is guaranteed to be leaf node after cloning: + // - it cannot be function node (due to clone) + // - it cannot be concat node (too short) + right.CopyTo(0, left.contents, left.length, right.length); + left.length += right.length; + return left; + } else { + RopeNode<T> concatNode = new RopeNode<T>(); + concatNode.left = left; + concatNode.right = right; + concatNode.length = left.length + right.length; + concatNode.Rebalance(); + return concatNode; + } + } + + /// <summary> + /// Splits this leaf node at offset and returns a new node with the part of the text after offset. + /// </summary> + RopeNode<T> SplitAfter(int offset) + { + Debug.Assert(!isShared && height == 0 && contents != null); + RopeNode<T> newPart = new RopeNode<T>(); + newPart.contents = new T[NodeSize]; + newPart.length = this.length - offset; + Array.Copy(this.contents, offset, newPart.contents, 0, newPart.length); + this.length = offset; + return newPart; + } + + internal RopeNode<T> Insert(int offset, RopeNode<T> newElements) + { + if (offset == 0) { + return Concat(newElements, this); + } else if (offset == this.length) { + return Concat(this, newElements); + } + + // first clone this node (converts function nodes to leaf or concat nodes) + RopeNode<T> result = CloneIfShared(); + if (result.height == 0) { + // leaf node: we'll need to split this node + RopeNode<T> left = result; + RopeNode<T> right = left.SplitAfter(offset); + return Concat(Concat(left, newElements), right); + } else { + // concat node + if (offset < result.left.length) { + result.left = result.left.Insert(offset, newElements); + } else { + result.right = result.right.Insert(offset - result.left.length, newElements); + } + result.length += newElements.length; + result.Rebalance(); + return result; + } + } + + internal RopeNode<T> Insert(int offset, T[] array, int arrayIndex, int count) + { + Debug.Assert(count > 0); + + if (this.length + count < RopeNode<char>.NodeSize) { + RopeNode<T> result = CloneIfShared(); + // result must be leaf node (Clone never returns function nodes, too short for concat node) + int lengthAfterOffset = result.length - offset; + T[] resultContents = result.contents; + for (int i = lengthAfterOffset; i >= 0; i--) { + resultContents[i + offset + count] = resultContents[i + offset]; + } + Array.Copy(array, arrayIndex, resultContents, offset, count); + result.length += count; + return result; + } else if (height == 0) { + // TODO: implement this more efficiently? + return Insert(offset, CreateFromArray(array, arrayIndex, count)); + } else { + // this is a concat node (both leafs and function nodes are handled by the case above) + RopeNode<T> result = CloneIfShared(); + if (offset < result.left.length) { + result.left = result.left.Insert(offset, array, arrayIndex, count); + } else { + result.right = result.right.Insert(offset - result.left.length, array, arrayIndex, count); + } + result.length += count; + result.Rebalance(); + return result; + } + } + + internal RopeNode<T> RemoveRange(int index, int count) + { + Debug.Assert(count > 0); + + // produce empty node when one node is deleted completely + if (index == 0 && count == this.length) + return emptyRopeNode; + + int endIndex = index + count; + RopeNode<T> result = CloneIfShared(); // convert function node to concat/leaf + if (result.height == 0) { + int remainingAfterEnd = result.length - endIndex; + for (int i = 0; i < remainingAfterEnd; i++) { + result.contents[index + i] = result.contents[endIndex + i]; + } + result.length -= count; + } else { + if (endIndex <= result.left.length) { + // deletion is only within the left part + result.left = result.left.RemoveRange(index, count); + } else if (index >= result.left.length) { + // deletion is only within the right part + result.right = result.right.RemoveRange(index - result.left.length, count); + } else { + // deletion overlaps both parts + int deletionAmountOnLeftSide = result.left.length - index; + result.left = result.left.RemoveRange(index, deletionAmountOnLeftSide); + result.right = result.right.RemoveRange(0, count - deletionAmountOnLeftSide); + } + // The deletion might have introduced empty nodes. Those must be removed. + if (result.left.length == 0) + return result.right; + if (result.right.length == 0) + return result.left; + + result.length -= count; + result.MergeIfPossible(); + result.Rebalance(); + } + return result; + } + + #region Debug Output + #if DEBUG + internal virtual void AppendTreeToString(StringBuilder b, int indent) + { + b.AppendLine(ToString()); + indent += 2; + if (left != null) { + b.Append(' ', indent); + b.Append("L: "); + left.AppendTreeToString(b, indent); + } + if (right != null) { + b.Append(' ', indent); + b.Append("R: "); + right.AppendTreeToString(b, indent); + } + } + + public override string ToString() + { + if (contents != null) { + char[] charContents = contents as char[]; + if (charContents != null) + return "[Leaf length=" + length + ", isShared=" + isShared + ", text=\"" + new string(charContents, 0, length) + "\"]"; + else + return "[Leaf length=" + length + ", isShared=" + isShared + "\"]"; + } else { + return "[Concat length=" + length + ", isShared=" + isShared + ", height=" + height + ", Balance=" + this.Balance + "]"; + } + } + + internal string GetTreeAsString() + { + StringBuilder b = new StringBuilder(); + AppendTreeToString(b, 0); + return b.ToString(); + } + #endif + #endregion + + /// <summary> + /// Gets the root node of the subtree from a lazily evaluated function node. + /// Such nodes are always marked as shared. + /// GetContentNode() will return either a Concat or Leaf node, never another FunctionNode. + /// </summary> + internal virtual RopeNode<T> GetContentNode() + { + throw new InvalidOperationException("Called GetContentNode() on non-FunctionNode."); + } + } + + sealed class FunctionNode<T> : RopeNode<T> + { + Func<Rope<T>> initializer; + RopeNode<T> cachedResults; + + public FunctionNode(int length, Func<Rope<T>> initializer) + { + Debug.Assert(length > 0); + Debug.Assert(initializer != null); + + this.length = length; + this.initializer = initializer; + // Function nodes are immediately shared, but cannot be cloned. + // This ensures we evaluate every initializer only once. + this.isShared = true; + } + + internal override RopeNode<T> GetContentNode() + { + lock (this) { + if (this.cachedResults == null) { + if (this.initializer == null) + throw new InvalidOperationException("Trying to load this node recursively; or: a previous call to a rope initializer failed."); + Func<Rope<T>> initializerCopy = this.initializer; + this.initializer = null; + Rope<T> resultRope = initializerCopy(); + if (resultRope == null) + throw new InvalidOperationException("Rope initializer returned null."); + RopeNode<T> resultNode = resultRope.root; + resultNode.Publish(); // result is shared between returned rope and the rope containing this function node + if (resultNode.length != this.length) + throw new InvalidOperationException("Rope initializer returned rope with incorrect length."); + if (resultNode.height == 0 && resultNode.contents == null) { + // ResultNode is another function node. + // We want to guarantee that GetContentNode() never returns function nodes, so we have to + // go down further in the tree. + this.cachedResults = resultNode.GetContentNode(); + } else { + this.cachedResults = resultNode; + } + } + return this.cachedResults; + } + } + + #if DEBUG + internal override void AppendTreeToString(StringBuilder b, int indent) + { + RopeNode<T> resultNode; + lock (this) { + b.AppendLine(ToString()); + resultNode = cachedResults; + } + indent += 2; + if (resultNode != null) { + b.Append(' ', indent); + b.Append("C: "); + resultNode.AppendTreeToString(b, indent); + } + } + + public override string ToString() + { + return "[FunctionNode length=" + length + " initializerRan=" + (initializer == null) + "]"; + } + #endif + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeTextReader.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeTextReader.cs new file mode 100644 index 000000000..43c8fc57b --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeTextReader.cs @@ -0,0 +1,105 @@ +// 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.Collections.Generic; +using System.Diagnostics; +using System.IO; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// TextReader implementation that reads text from a rope. + /// </summary> + public sealed class RopeTextReader : TextReader + { + Stack<RopeNode<char>> stack = new Stack<RopeNode<char>>(); + RopeNode<char> currentNode; + int indexInsideNode; + + /// <summary> + /// Creates a new RopeTextReader. + /// Internally, this method creates a Clone of the rope; so the text reader will always read through the old + /// version of the rope if it is modified. <seealso cref="Rope{T}.Clone()"/> + /// </summary> + public RopeTextReader(Rope<char> rope) + { + if (rope == null) + throw new ArgumentNullException("rope"); + + // We force the user to iterate through a clone of the rope to keep the API contract of RopeTextReader simple + // (what happens when a rope is modified while iterating through it?) + rope.root.Publish(); + + // special case for the empty rope: + // leave currentNode initialized to null (RopeTextReader doesn't support empty nodes) + if (rope.Length != 0) { + currentNode = rope.root; + GoToLeftMostLeaf(); + } + } + + void GoToLeftMostLeaf() + { + while (currentNode.contents == null) { + if (currentNode.height == 0) { + // this is a function node - move to its contained rope + currentNode = currentNode.GetContentNode(); + continue; + } + Debug.Assert(currentNode.right != null); + stack.Push(currentNode.right); + currentNode = currentNode.left; + } + Debug.Assert(currentNode.height == 0); + } + + /// <inheritdoc/> + public override int Peek() + { + if (currentNode == null) + return -1; + return currentNode.contents[indexInsideNode]; + } + + /// <inheritdoc/> + public override int Read() + { + if (currentNode == null) + return -1; + char result = currentNode.contents[indexInsideNode++]; + if (indexInsideNode >= currentNode.length) + GoToNextNode(); + return result; + } + + void GoToNextNode() + { + if (stack.Count == 0) { + currentNode = null; + } else { + indexInsideNode = 0; + currentNode = stack.Pop(); + GoToLeftMostLeaf(); + } + } + + /// <inheritdoc/> + public override int Read(char[] buffer, int index, int count) + { + if (currentNode == null) + return 0; + int amountInCurrentNode = currentNode.length - indexInsideNode; + if (count < amountInCurrentNode) { + Array.Copy(currentNode.contents, indexInsideNode, buffer, index, count); + indexInsideNode += count; + return count; + } else { + // read to end of current node + Array.Copy(currentNode.contents, indexInsideNode, buffer, index, amountInCurrentNode); + GoToNextNode(); + return amountInCurrentNode; + } + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/StringSegment.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/StringSegment.cs new file mode 100644 index 000000000..f2fad60cf --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/StringSegment.cs @@ -0,0 +1,107 @@ +// 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; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Represents a string with a segment. + /// Similar to System.ArraySegment<T>, but for strings instead of arrays. + /// </summary> + public struct StringSegment : IEquatable<StringSegment> + { + readonly string text; + readonly int offset; + readonly int count; + + /// <summary> + /// Creates a new StringSegment. + /// </summary> + public StringSegment(string text, int offset, int count) + { + if (text == null) + throw new ArgumentNullException("text"); + if (offset < 0 || offset > text.Length) + throw new ArgumentOutOfRangeException("offset"); + if (offset + count > text.Length) + throw new ArgumentOutOfRangeException("count"); + this.text = text; + this.offset = offset; + this.count = count; + } + + /// <summary> + /// Creates a new StringSegment. + /// </summary> + public StringSegment(string text) + { + if (text == null) + throw new ArgumentNullException("text"); + this.text = text; + this.offset = 0; + this.count = text.Length; + } + + /// <summary> + /// Gets the string used for this segment. + /// </summary> + public string Text { + get { return text; } + } + + /// <summary> + /// Gets the start offset of the segment with the text. + /// </summary> + public int Offset { + get { return offset; } + } + + /// <summary> + /// Gets the length of the segment. + /// </summary> + public int Count { + get { return count; } + } + + #region Equals and GetHashCode implementation + /// <inheritdoc/> + public override bool Equals(object obj) + { + if (obj is StringSegment) + return Equals((StringSegment)obj); // use Equals method below + else + return false; + } + + /// <inheritdoc/> + public bool Equals(StringSegment other) + { + // add comparisions for all members here + return object.ReferenceEquals(this.text, other.text) && offset == other.offset && count == other.count; + } + + /// <inheritdoc/> + public override int GetHashCode() + { + return text.GetHashCode() ^ offset ^ count; + } + + /// <summary> + /// Equality operator. + /// </summary> + public static bool operator ==(StringSegment left, StringSegment right) + { + return left.Equals(right); + } + + /// <summary> + /// Inequality operator. + /// </summary> + public static bool operator !=(StringSegment left, StringSegment right) + { + return !left.Equals(right); + } + #endregion + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/TextFormatterFactory.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/TextFormatterFactory.cs new file mode 100644 index 000000000..dd6fe8b9e --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/TextFormatterFactory.cs @@ -0,0 +1,71 @@ +// 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.Globalization; +using System.Reflection; +using System.Windows; +using System.Windows.Controls; +using System.Windows.Media; +using System.Windows.Media.TextFormatting; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Creates TextFormatter instances that with the correct TextFormattingMode, if running on .NET 4.0. + /// </summary> + static class TextFormatterFactory + { + /// <summary> + /// Creates a <see cref="TextFormatter"/> using the formatting mode used by the specified owner object. + /// </summary> + public static TextFormatter Create(DependencyObject owner) + { + if (owner == null) + throw new ArgumentNullException("owner"); + return TextFormatter.Create(TextOptions.GetTextFormattingMode(owner)); + } + + /// <summary> + /// Returns whether the specified dependency property affects the text formatter creation. + /// Controls should re-create their text formatter for such property changes. + /// </summary> + public static bool PropertyChangeAffectsTextFormatter(DependencyProperty dp) + { + return dp == TextOptions.TextFormattingModeProperty; + } + + /// <summary> + /// Creates formatted text. + /// </summary> + /// <param name="element">The owner element. The text formatter setting are read from this element.</param> + /// <param name="text">The text.</param> + /// <param name="typeface">The typeface to use. If this parameter is null, the typeface of the <paramref name="element"/> will be used.</param> + /// <param name="emSize">The font size. If this parameter is null, the font size of the <paramref name="element"/> will be used.</param> + /// <param name="foreground">The foreground color. If this parameter is null, the foreground of the <paramref name="element"/> will be used.</param> + /// <returns>A FormattedText object using the specified settings.</returns> + public static FormattedText CreateFormattedText(FrameworkElement element, string text, Typeface typeface, double? emSize, Brush foreground) + { + if (element == null) + throw new ArgumentNullException("element"); + if (text == null) + throw new ArgumentNullException("text"); + if (typeface == null) + typeface = element.CreateTypeface(); + if (emSize == null) + emSize = TextBlock.GetFontSize(element); + if (foreground == null) + foreground = TextBlock.GetForeground(element); + return new FormattedText( + text, + CultureInfo.CurrentCulture, + FlowDirection.LeftToRight, + typeface, + emSize.Value, + foreground, + null, + TextOptions.GetTextFormattingMode(element) + ); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ThrowUtil.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ThrowUtil.cs new file mode 100644 index 000000000..69dbb5ad0 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ThrowUtil.cs @@ -0,0 +1,56 @@ +// 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.Globalization; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Contains exception-throwing helper methods. + /// </summary> + static class ThrowUtil + { + /// <summary> + /// Throws an ArgumentNullException if <paramref name="val"/> is null; otherwise + /// returns val. + /// </summary> + /// <example> + /// Use this method to throw an ArgumentNullException when using parameters for base + /// constructor calls. + /// <code> + /// public VisualLineText(string text) : base(ThrowUtil.CheckNotNull(text, "text").Length) + /// </code> + /// </example> + public static T CheckNotNull<T>(T val, string parameterName) where T : class + { + if (val == null) + throw new ArgumentNullException(parameterName); + return val; + } + + public static int CheckNotNegative(int val, string parameterName) + { + if (val < 0) + throw new ArgumentOutOfRangeException(parameterName, val, "value must not be negative"); + return val; + } + + public static int CheckInRangeInclusive(int val, string parameterName, int lower, int upper) + { + if (val < lower || val > upper) + throw new ArgumentOutOfRangeException(parameterName, val, "Expected: " + lower.ToString(CultureInfo.InvariantCulture) + " <= " + parameterName + " <= " + upper.ToString(CultureInfo.InvariantCulture)); + return val; + } + + public static InvalidOperationException NoDocumentAssigned() + { + return new InvalidOperationException("Document is null"); + } + + public static InvalidOperationException NoValidCaretPosition() + { + return new InvalidOperationException("Could not find a valid caret position in the line"); + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/WeakEventManagerBase.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/WeakEventManagerBase.cs new file mode 100644 index 000000000..87e4de515 --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/WeakEventManagerBase.cs @@ -0,0 +1,86 @@ +// 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.Windows; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// WeakEventManager with AddListener/RemoveListener and CurrentManager implementation. + /// Helps implementing the WeakEventManager pattern with less code. + /// </summary> + public abstract class WeakEventManagerBase<TManager, TEventSource> : WeakEventManager + where TManager : WeakEventManagerBase<TManager, TEventSource>, new() + where TEventSource : class + { + /// <summary> + /// Creates a new WeakEventManagerBase instance. + /// </summary> + protected WeakEventManagerBase() + { + Debug.Assert(GetType() == typeof(TManager)); + } + + /// <summary> + /// Adds a weak event listener. + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static void AddListener(TEventSource source, IWeakEventListener listener) + { + CurrentManager.ProtectedAddListener(source, listener); + } + + /// <summary> + /// Removes a weak event listener. + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static void RemoveListener(TEventSource source, IWeakEventListener listener) + { + CurrentManager.ProtectedRemoveListener(source, listener); + } + + /// <inheritdoc/> + protected sealed override void StartListening(object source) + { + if (source == null) + throw new ArgumentNullException("source"); + StartListening((TEventSource)source); + } + + /// <inheritdoc/> + protected sealed override void StopListening(object source) + { + if (source == null) + throw new ArgumentNullException("source"); + StopListening((TEventSource)source); + } + + /// <summary> + /// Attaches the event handler. + /// </summary> + protected abstract void StartListening(TEventSource source); + + /// <summary> + /// Detaches the event handler. + /// </summary> + protected abstract void StopListening(TEventSource source); + + /// <summary> + /// Gets the current manager. + /// </summary> + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1721:PropertyNamesShouldNotMatchGetMethods")] + protected static TManager CurrentManager { + get { + Type managerType = typeof(TManager); + TManager manager = (TManager)GetCurrentManager(managerType); + if (manager == null) { + manager = new TManager(); + SetCurrentManager(managerType, manager); + } + return manager; + } + } + } +} diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Win32.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Win32.cs new file mode 100644 index 000000000..421c35c5a --- /dev/null +++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Win32.cs @@ -0,0 +1,85 @@ +// 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.Runtime.InteropServices; +using System.Security; +using System.Windows; +using System.Windows.Interop; +using System.Windows.Media; + +namespace Tango.Scripting.Editors.Utils +{ + /// <summary> + /// Wrapper around Win32 functions. + /// </summary> + static class Win32 + { + /// <summary> + /// Gets the caret blink time. + /// </summary> + public static TimeSpan CaretBlinkTime { + get { return TimeSpan.FromMilliseconds(SafeNativeMethods.GetCaretBlinkTime()); } + } + + /// <summary> + /// Creates an invisible Win32 caret for the specified Visual with the specified size (coordinates local to the owner visual). + /// </summary> + public static bool CreateCaret(Visual owner, Size size) + { + if (owner == null) + throw new ArgumentNullException("owner"); + HwndSource source = PresentationSource.FromVisual(owner) as HwndSource; + if (source != null) { + Vector r = owner.PointToScreen(new Point(size.Width, size.Height)) - owner.PointToScreen(new Point(0, 0)); + return SafeNativeMethods.CreateCaret(source.Handle, IntPtr.Zero, (int)Math.Ceiling(r.X), (int)Math.Ceiling(r.Y)); + } else { + return false; + } + } + + /// <summary> + /// Sets the position of the caret previously created using <see cref="CreateCaret"/>. position is relative to the owner visual. + /// </summary> + public static bool SetCaretPosition(Visual owner, Point position) + { + if (owner == null) + throw new ArgumentNullException("owner"); + HwndSource source = PresentationSource.FromVisual(owner) as HwndSource; + if (source != null) { + Point pointOnRootVisual = owner.TransformToAncestor(source.RootVisual).Transform(position); + Point pointOnHwnd = pointOnRootVisual.TransformToDevice(source.RootVisual); + return SafeNativeMethods.SetCaretPos((int)pointOnHwnd.X, (int)pointOnHwnd.Y); + } else { + return false; + } + } + + /// <summary> + /// Destroys the caret previously created using <see cref="CreateCaret"/>. + /// </summary> + public static bool DestroyCaret() + { + return SafeNativeMethods.DestroyCaret(); + } + + [SuppressUnmanagedCodeSecurity] + static class SafeNativeMethods + { + [DllImport("user32.dll")] + public static extern int GetCaretBlinkTime(); + + [DllImport("user32.dll")] + [return: MarshalAs(UnmanagedType.Bool)] + public static extern bool CreateCaret(IntPtr hWnd, IntPtr hBitmap, int nWidth, int nHeight); + + [DllImport("user32.dll")] + [return: MarshalAs(UnmanagedType.Bool)] + public static extern bool SetCaretPos(int x, int y); + + [DllImport("user32.dll")] + [return: MarshalAs(UnmanagedType.Bool)] + public static extern bool DestroyCaret(); + } + } +} |
