From 080f1697e97e13461ec6df4d31c8924d01257a1b Mon Sep 17 00:00:00 2001 From: Roy Ben Shabat Date: Tue, 9 Apr 2019 01:47:48 +0300 Subject: MERGE --- .../Tango.Scripting.Editors/Utils/Boxes.cs | 21 + .../Tango.Scripting.Editors/Utils/BusyManager.cs | 55 ++ .../Utils/CallbackOnDispose.cs | 35 + .../Tango.Scripting.Editors/Utils/CharRope.cs | 172 ++++ .../Utils/CompressingTreeList.cs | 882 +++++++++++++++++++++ .../Tango.Scripting.Editors/Utils/Constants.cs | 15 + .../Tango.Scripting.Editors/Utils/DelayedEvents.cs | 48 ++ .../Tango.Scripting.Editors/Utils/Deque.cs | 174 ++++ .../Tango.Scripting.Editors/Utils/Empty.cs | 17 + .../Utils/ExtensionMethods.cs | 214 +++++ .../Tango.Scripting.Editors/Utils/FileReader.cs | 208 +++++ .../Utils/ImmutableStack.cs | 114 +++ .../Utils/NullSafeCollection.cs | 31 + .../Utils/ObserveAddRemoveCollection.cs | 63 ++ .../Utils/PixelSnapHelpers.cs | 92 +++ .../Utils/PropertyChangedWeakEventManager.cs | 26 + .../Tango.Scripting.Editors/Utils/Rope.cs | 789 ++++++++++++++++++ .../Tango.Scripting.Editors/Utils/RopeNode.cs | 605 ++++++++++++++ .../Utils/RopeTextReader.cs | 105 +++ .../Tango.Scripting.Editors/Utils/StringSegment.cs | 107 +++ .../Utils/TextFormatterFactory.cs | 71 ++ .../Tango.Scripting.Editors/Utils/ThrowUtil.cs | 56 ++ .../Utils/WeakEventManagerBase.cs | 86 ++ .../Tango.Scripting.Editors/Utils/Win32.cs | 85 ++ 24 files changed, 4071 insertions(+) create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Boxes.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/BusyManager.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CallbackOnDispose.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CharRope.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/CompressingTreeList.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Constants.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/DelayedEvents.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Empty.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ExtensionMethods.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/FileReader.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ImmutableStack.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/NullSafeCollection.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ObserveAddRemoveCollection.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PixelSnapHelpers.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/PropertyChangedWeakEventManager.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Rope.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeNode.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/RopeTextReader.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/StringSegment.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/TextFormatterFactory.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/ThrowUtil.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/WeakEventManagerBase.cs create mode 100644 Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Win32.cs (limited to 'Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils') 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 +{ + /// + /// Reuse the same instances for boxed booleans. + /// + 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 +{ + /// + /// 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. + /// + static class BusyManager + { + public struct BusyLock : IDisposable + { + public static readonly BusyLock Failed = new BusyLock(null); + + readonly List objectList; + + public BusyLock(List 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 _activeObjects; + + public static BusyLock Enter(object obj) + { + List activeObjects = _activeObjects; + if (activeObjects == null) + activeObjects = _activeObjects = new List(); + 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 +{ + /// + /// Invokes an action when it is disposed. + /// + /// + /// This class ensures the callback is invoked at most once, + /// even when Dispose is called on multiple threads. + /// + 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 +{ + /// + /// Poor man's template specialization: extension methods for Rope<char>. + /// + public static class CharRope + { + /// + /// Creates a new rope from the specified text. + /// + public static Rope Create(string text) + { + if (text == null) + throw new ArgumentNullException("text"); + return new Rope(InitFromString(text)); + } + + /// + /// Retrieves the text for a portion of the rope. + /// Runs in O(lg N + M), where M=. + /// + /// offset or length is outside the valid range. + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public static string ToString(this Rope 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); + } + + /// + /// 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=. + /// + /// offset or length is outside the valid range. + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public static void WriteTo(this Rope 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); + } + + /// + /// Appends text to this rope. + /// Runs in O(lg N + M). + /// + /// newElements is null. + public static void AddText(this Rope rope, string text) + { + InsertText(rope, rope.Length, text); + } + + /// + /// Inserts text into this rope. + /// Runs in O(lg N + M). + /// + /// newElements is null. + /// index or length is outside the valid range. + public static void InsertText(this Rope 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 InitFromString(string text) + { + if (text.Length == 0) { + return RopeNode.emptyRopeNode; + } + RopeNode node = RopeNode.CreateNodes(text.Length); + FillNode(node, text, 0); + return node; + } + + static void FillNode(RopeNode 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 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); + } + } + } + + /// + /// Gets the index of the first occurrence of any element in the specified array. + /// + /// The target rope. + /// Array of characters being searched. + /// Start index of the search. + /// Length of the area to search. + /// The first index where any character was found; or -1 if no occurrence was found. + public static int IndexOfAny(this Rope 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 +{ + /// + /// 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. + /// + /// + /// 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). + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", + Justification = "It's an IList implementation")] + public sealed class CompressingTreeList : IList + { + // 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; + } + } + + /// + /// Gets the inorder predecessor of the node. + /// + 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; + } + } + } + + /// + /// Gets the inorder successor of the node. + /// + 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 comparisonFunc; + Node root; + + /// + /// Creates a new CompressingTreeList instance. + /// + /// A function that checks two values for equality. If this + /// function returns true, a single node may be used to store the two values. + public CompressingTreeList(Func comparisonFunc) + { + if (comparisonFunc == null) + throw new ArgumentNullException("comparisonFunc"); + this.comparisonFunc = comparisonFunc; + } + #endregion + + #region InsertRange + /// + /// Inserts times at position + /// . + /// + 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 + /// + /// Removes items starting at position + /// . + /// + 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 + /// + /// Sets indices starting at to + /// + /// + 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 implementation + /// + /// Gets or sets an item by index. + /// + 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); + } + } + + /// + /// Gets the number of items in the list. + /// + public int Count { + get { + if (root != null) + return root.totalCount; + else + return 0; + } + } + + bool ICollection.IsReadOnly { + get { + return false; + } + } + + /// + /// Gets the index of the specified . + /// + 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; + } + + /// + /// Gets the the first index so that all values from the result index to + /// are equal. + /// + 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; + } + + /// + /// Gets the first index after so that the value at the result index is not + /// equal to the value at . + /// That is, this method returns the exclusive end index of the run of equal values. + /// + 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; + } + + /// + /// Gets the number of elements after that have the same value as each other. + /// + [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; + } + + /// + /// Applies the conversion function to all elements in this CompressingTreeList. + /// + public void Transform(Func 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; + } + } + + + /// + /// Inserts the specified at + /// + public void Insert(int index, T item) + { + InsertRange(index, 1, item); + } + + /// + /// Removes one item at + /// + public void RemoveAt(int index) + { + RemoveRange(index, 1); + } + + /// + /// Adds the specified to the end of the list. + /// + public void Add(T item) + { + InsertRange(this.Count, 1, item); + } + + /// + /// Removes all items from this list. + /// + public void Clear() + { + root = null; + } + + /// + /// Gets whether this list contains the specified item. + /// + public bool Contains(T item) + { + return IndexOf(item) >= 0; + } + + /// + /// Copies all items in this list to the specified array. + /// + 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; + } + } + + /// + /// Removes the specified item from this list. + /// + public bool Remove(T item) + { + int index = IndexOf(item); + if (index >= 0) { + RemoveAt(index); + return true; + } else { + return false; + } + } + #endregion + + #region IEnumerable + /// + /// Gets an enumerator for this list. + /// + public IEnumerator 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 ""; + 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 + { + /// + /// Multiply with this constant to convert from points to device-independent pixels. + /// + 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 +{ + /// + /// Maintains a list of delayed events to raise. + /// + 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 eventCalls = new Queue(); + + 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 +{ + /// + /// Double-ended queue. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] + [Serializable] + public sealed class Deque : ICollection + { + T[] arr = Empty.Array; + int size, head, tail; + + /// + public int Count { + get { return size; } + } + + /// + public void Clear() + { + arr = Empty.Array; + size = 0; + head = 0; + tail = 0; + } + + /// + /// Gets/Sets an element inside the deque. + /// + 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; + } + } + + /// + /// Adds an element to the end of the deque. + /// + [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++; + } + + /// + /// Pops an element from the end of the deque. + /// + 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; + } + + /// + /// Adds an element to the front of the deque. + /// + 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++; + } + + /// + /// Pops an element from the end of the deque. + /// + 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; + } + + /// + public IEnumerator 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.IsReadOnly { + get { return false; } + } + + void ICollection.Add(T item) + { + PushBack(item); + } + + /// + public bool Contains(T item) + { + EqualityComparer comparer = EqualityComparer.Default; + foreach (T element in this) + if (comparer.Equals(item, element)) + return true; + return false; + } + + /// + 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.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 +{ + /// + /// Provides immutable empty list instances. + /// + static class Empty + { + public static readonly T[] Array = new T[0]; + //public static readonly ReadOnlyCollection ReadOnlyCollection = new ReadOnlyCollection(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 + /// + /// Epsilon used for IsClose() 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 + /// + public const double Epsilon = 0.01; + + /// + /// Returns true if the doubles are close (difference smaller than 0.01). + /// + public static bool IsClose(this double d1, double d2) + { + if (d1 == d2) // required for infinities + return true; + return Math.Abs(d1 - d2) < Epsilon; + } + + /// + /// Returns true if the doubles are close (difference smaller than 0.01). + /// + public static bool IsClose(this Size d1, Size d2) + { + return IsClose(d1.Width, d2.Width) && IsClose(d1.Height, d2.Height); + } + + /// + /// Returns true if the doubles are close (difference smaller than 0.01). + /// + public static bool IsClose(this Vector d1, Vector d2) + { + return IsClose(d1.X, d2.X) && IsClose(d1.Y, d2.Y); + } + + /// + /// Forces the value to stay between mininum and maximum. + /// + /// minimum, if value is less than minimum. + /// Maximum, if value is greater than maximum. + /// Otherwise, value. + public static double CoerceValue(this double value, double minimum, double maximum) + { + return Math.Max(Math.Min(value, maximum), minimum); + } + + /// + /// Forces the value to stay between mininum and maximum. + /// + /// minimum, if value is less than minimum. + /// Maximum, if value is greater than maximum. + /// Otherwise, value. + public static int CoerceValue(this int value, int minimum, int maximum) + { + return Math.Max(Math.Min(value, maximum), minimum); + } + #endregion + + #region CreateTypeface + /// + /// Creates typeface from the framework element. + /// + 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(this ICollection collection, IEnumerable elements) + { + foreach (T e in elements) + collection.Add(e); + } + + /// + /// Creates an IEnumerable with a single value. + /// + public static IEnumerable Sequence(T value) + { + yield return value; + } + #endregion + + #region XML reading + /// + /// Gets the value of the attribute, or null if the attribute does not exist. + /// + public static string GetAttributeOrNull(this XmlElement element, string attributeName) + { + XmlAttribute attr = element.GetAttributeNode(attributeName); + return attr != null ? attr.Value : null; + } + + /// + /// Gets the value of the attribute as boolean, or null if the attribute does not exist. + /// + public static bool? GetBoolAttribute(this XmlElement element, string attributeName) + { + XmlAttribute attr = element.GetAttributeNode(attributeName); + return attr != null ? (bool?)XmlConvert.ToBoolean(attr.Value) : null; + } + + /// + /// Gets the value of the attribute as boolean, or null if the attribute does not exist. + /// + 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 +{ + /// + /// Class that can open text files with auto-detection of the encoding. + /// + public static class FileReader + { + /// + /// Gets if the given encoding is a Unicode encoding (UTF). + /// + /// + /// 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. + /// + 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; + } + } + + /// + /// Reads the content of the given stream. + /// + /// The stream to read. + /// The stream must support seeking and must be positioned at its beginning. + /// The encoding to use if the encoding cannot be auto-detected. + /// The file content as string. + public static string ReadFileContent(Stream stream, Encoding defaultEncoding) + { + using (StreamReader reader = OpenStream(stream, defaultEncoding)) { + return reader.ReadToEnd(); + } + } + + /// + /// Reads the content of the file. + /// + /// The file name. + /// The encoding to use if the encoding cannot be auto-detected. + /// The file content as string. + public static string ReadFileContent(string fileName, Encoding defaultEncoding) + { + using (FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read)) { + return ReadFileContent(fs, defaultEncoding); + } + } + + /// + /// Opens the specified file for reading. + /// + /// The file to open. + /// The encoding to use if the encoding cannot be auto-detected. + /// Returns a StreamReader that reads from the stream. Use + /// to get the encoding that was used. + 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; + } + } + + /// + /// Opens the specified stream for reading. + /// + /// The stream to open. + /// The encoding to use if the encoding cannot be auto-detected. + /// Returns a StreamReader that reads from the stream. Use + /// to get the encoding that was used. + 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 +{ + /// + /// An immutable stack. + /// + /// Using 'foreach' on the stack will return the items from top to bottom (in the order they would be popped). + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1711:IdentifiersShouldNotHaveIncorrectSuffix")] + [Serializable] + public sealed class ImmutableStack : IEnumerable + { + /// + /// Gets the empty stack instance. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes", Justification = "ImmutableStack is immutable")] + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static readonly ImmutableStack Empty = new ImmutableStack(); + + readonly T value; + readonly ImmutableStack next; + + private ImmutableStack() + { + } + + private ImmutableStack(T value, ImmutableStack next) + { + this.value = value; + this.next = next; + } + + /// + /// Pushes an item on the stack. This does not modify the stack itself, but returns a new + /// one with the value pushed. + /// + public ImmutableStack Push(T item) + { + return new ImmutableStack(item, this); + } + + /// + /// Gets the item on the top of the stack. + /// + /// The stack is empty. + public T Peek() + { + if (IsEmpty) + throw new InvalidOperationException("Operation not valid on empty stack."); + return value; + } + + internal T UnsafePeek() + { + Debug.Assert(!IsEmpty); + return value; + } + + /// + /// Gets the stack with the top item removed. + /// + /// The stack is empty. + public ImmutableStack Pop() + { + if (IsEmpty) + throw new InvalidOperationException("Operation not valid on empty stack."); + return next; + } + + /// + /// Gets if this stack is empty. + /// + public bool IsEmpty { + get { return next == null; } + } + + /// + /// Gets an enumerator that iterates through the stack top-to-bottom. + /// + public IEnumerator GetEnumerator() + { + ImmutableStack t = this; + while (!t.IsEmpty) { + yield return t.value; + t = t.next; + } + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { + return this.GetEnumerator(); + } + + /// + 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 +{ + /// + /// A collection that cannot contain null values. + /// + [Serializable] + public class NullSafeCollection : Collection where T : class + { + /// + protected override void InsertItem(int index, T item) + { + if (item == null) + throw new ArgumentNullException("item"); + base.InsertItem(index, item); + } + + /// + 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 +{ + /// + /// 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. + /// + sealed class ObserveAddRemoveCollection : Collection + { + readonly Action onAdd, onRemove; + + public ObserveAddRemoveCollection(Action onAdd, Action 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 +{ + /// + /// Contains static helper methods for aligning stuff on a whole number of pixels. + /// + public static class PixelSnapHelpers + { + /// + /// Gets the pixel size on the screen containing visual. + /// This method does not take transforms on visual into account. + /// + 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); + } + } + + /// + /// Aligns on the next middle of a pixel. + /// + /// The value that should be aligned + /// The size of one pixel + 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); + } + + /// + /// Aligns the borders of rect on the middles of pixels. + /// + 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; + } + + /// + /// Rounds to whole number of pixels. + /// + public static Point Round(Point point, Size pixelSize) + { + return new Point(Round(point.X, pixelSize.Width), Round(point.Y, pixelSize.Height)); + } + + /// + /// Rounds val to whole number of pixels. + /// + 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)); + } + + /// + /// Rounds to a whole number of pixels. + /// + public static double Round(double value, double pixelSize) + { + return pixelSize * Math.Round(value / pixelSize); + } + + /// + /// Rounds to an whole odd number of pixels. + /// + 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 +{ + /// + /// WeakEventManager for INotifyPropertyChanged.PropertyChanged. + /// + public sealed class PropertyChangedWeakEventManager : WeakEventManagerBase + { + /// + protected override void StartListening(INotifyPropertyChanged source) + { + source.PropertyChanged += DeliverEvent; + } + + /// + 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 +{ + /// + /// A kind of List<T>, but more efficient for random insertions/removal. + /// Also has cheap Clone() and SubRope() implementations. + /// + /// + /// 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. + /// + [Serializable] + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")] + public sealed class Rope : IList, ICloneable + { + internal RopeNode root; + + internal Rope(RopeNode root) + { + this.root = root; + root.CheckInvariants(); + } + + /// + /// Creates a new rope representing the empty string. + /// + public Rope() + { + // we'll construct the empty rope as a clone of an imaginary static empty rope + this.root = RopeNode.emptyRopeNode; + root.CheckInvariants(); + } + + /// + /// Creates a rope from the specified input. + /// This operation runs in O(N). + /// + /// input is null. + public Rope(IEnumerable input) + { + if (input == null) + throw new ArgumentNullException("input"); + Rope inputRope = input as Rope; + 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, then T must be char + ((Rope)(object)this).root = CharRope.InitFromString(text); + } else { + T[] arr = ToArray(input); + this.root = RopeNode.CreateFromArray(arr, 0, arr.Length); + } + } + this.root.CheckInvariants(); + } + + /// + /// Creates a rope from a part of the array. + /// This operation runs in O(N). + /// + /// input is null. + public Rope(T[] array, int arrayIndex, int count) + { + VerifyArrayWithRange(array, arrayIndex, count); + this.root = RopeNode.CreateFromArray(array, arrayIndex, count); + this.root.CheckInvariants(); + } + + /// + /// Creates a new rope that lazily initalizes its content. + /// + /// The length of the rope that will be lazily loaded. + /// + /// The callback that provides the content for this rope. + /// 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. + /// + /// + /// 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 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. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")] + public Rope(int length, Func> 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.emptyRopeNode; + } else { + this.root = new FunctionNode(length, initializer); + } + this.root.CheckInvariants(); + } + + static T[] ToArray(IEnumerable input) + { + T[] arr = input as T[]; + return arr ?? input.ToArray(); + } + + /// + /// 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). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public Rope 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(root); + } + + object ICloneable.Clone() + { + return this.Clone(); + } + + /// + /// Resets the rope to an empty list. + /// Runs in O(1). + /// + public void Clear() + { + root = RopeNode.emptyRopeNode; + OnChanged(); + } + + /// + /// Gets the length of the rope. + /// Runs in O(1). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public int Length { + get { return root.length; } + } + + /// + /// Gets the length of the rope. + /// Runs in O(1). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public int Count { + get { return root.length; } + } + + /// + /// Inserts another rope into this rope. + /// Runs in O(lg N + lg M), plus a per-node cost as if newElements.Clone() was called. + /// + /// newElements is null. + /// index or length is outside the valid range. + public void InsertRange(int index, Rope 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(); + } + + /// + /// 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. + /// + /// newElements is null. + /// index or length is outside the valid range. + public void InsertRange(int index, IEnumerable newElements) + { + if (newElements == null) + throw new ArgumentNullException("newElements"); + Rope newElementsRope = newElements as Rope; + if (newElementsRope != null) { + InsertRange(index, newElementsRope); + } else { + T[] arr = ToArray(newElements); + InsertRange(index, arr, 0, arr.Length); + } + } + + /// + /// 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. + /// + /// newElements is null. + /// index or length is outside the valid range. + 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(); + } + } + + /// + /// 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. + /// + /// newElements is null. + public void AddRange(IEnumerable newElements) + { + InsertRange(this.Length, newElements); + } + + /// + /// Appends another rope to the end of this rope. + /// Runs in O(lg N + lg M), plus a per-node cost as if newElements.Clone() was called. + /// + /// newElements is null. + public void AddRange(Rope newElements) + { + InsertRange(this.Length, newElements); + } + + /// + /// 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. + /// + /// array is null. + public void AddRange(T[] array, int arrayIndex, int count) + { + InsertRange(this.Length, array, arrayIndex, count); + } + + /// + /// Removes a range of elements from the rope. + /// Runs in O(lg N). + /// + /// offset or length is outside the valid range. + public void RemoveRange(int index, int count) + { + VerifyRange(index, count); + if (count > 0) { + root = root.RemoveRange(index, count); + OnChanged(); + } + } + + /// + /// Copies a range of the specified array into the rope, overwriting existing elements. + /// Runs in O(lg N + M). + /// + 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(); + } + } + + /// + /// 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 this.Clone() was called. + /// + /// offset or length is outside the valid range. + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public Rope GetRange(int index, int count) + { + VerifyRange(index, count); + Rope newRope = Clone(); + int endIndex = index + count; + newRope.RemoveRange(endIndex, newRope.Length - endIndex); + newRope.RemoveRange(0, index); + return newRope; + } + + /* + #region Equality + /// + /// Gets whether the two ropes have the same content. + /// Runs in O(N + M). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + 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; + } + } + } + + /// + /// Gets whether two ropes have the same content. + /// Runs in O(N + M). + /// + public override bool Equals(object obj) + { + return Equals(obj as Rope); + } + + /// + /// Calculates the hash code of the rope's content. + /// Runs in O(N). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + 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 + */ + + /// + /// Concatenates two ropes. The input ropes are not modified. + /// Runs in O(lg N + lg M). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static Rope Concat(Rope left, Rope right) + { + if (left == null) + throw new ArgumentNullException("left"); + if (right == null) + throw new ArgumentNullException("right"); + left.root.Publish(); + right.root.Publish(); + return new Rope(RopeNode.Concat(left.root, right.root)); + } + + /// + /// Concatenates multiple ropes. The input ropes are not modified. + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static Rope Concat(params Rope[] ropes) + { + if (ropes == null) + throw new ArgumentNullException("ropes"); + Rope result = new Rope(); + foreach (Rope r in ropes) + result.AddRange(r); + return result; + } + + #region Caches / Changed event + internal struct RopeCacheEntry + { + internal readonly RopeNode node; + internal readonly int nodeStartIndex; + + internal RopeCacheEntry(RopeNode 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 lastUsedNodeStack; + + internal void OnChanged() + { + lastUsedNodeStack = null; + + root.CheckInvariants(); + } + #endregion + + #region GetChar / SetChar + /// + /// 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). + /// + /// Offset is outside the valid range (0 to Length-1). + /// + /// The getter counts as a read access and may be called concurrently to other read accesses. + /// + 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 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 FindNodeUsingCache(int index) + { + Debug.Assert(index >= 0 && index < this.Length); + + // thread safety: fetch stack into local variable + ImmutableStack stack = lastUsedNodeStack; + ImmutableStack oldStack = stack; + + if (stack == null) { + stack = ImmutableStack.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)); + } + } + + /// + /// Creates a string from the rope. Runs in O(N). + /// + /// 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(). + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public override string ToString() + { + Rope charRope = this as Rope; + 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.IsReadOnly { + get { return false; } + } + + /// + /// Finds the first occurance of item. + /// Runs in O(N). + /// + /// The index of the first occurance of item, or -1 if it cannot be found. + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public int IndexOf(T item) + { + var comparer = EqualityComparer.Default; + int index = 0; + foreach (T element in this) { + if (comparer.Equals(item, element)) + return index; + index++; + } + return -1; + } + + /// + /// Inserts the item at the specified index in the rope. + /// Runs in O(lg N). + /// + public void Insert(int index, T item) + { + InsertRange(index, new[] { item }, 0, 1); + } + + /// + /// Removes a single item from the rope. + /// Runs in O(lg N). + /// + public void RemoveAt(int index) + { + RemoveRange(index, 1); + } + + /// + /// Appends the item at the end of the rope. + /// Runs in O(lg N). + /// + public void Add(T item) + { + InsertRange(this.Length, new[] { item }, 0, 1); + } + + /// + /// Searches the item in the rope. + /// Runs in O(N). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public bool Contains(T item) + { + return IndexOf(item) >= 0; + } + + /// + /// Copies the whole content of the rope into the specified array. + /// Runs in O(N). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public void CopyTo(T[] array, int arrayIndex) + { + CopyTo(0, array, arrayIndex, this.Length); + } + + /// + /// Copies the a part of the rope into the specified array. + /// Runs in O(lg N + M). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + 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); + } + + /// + /// Removes the first occurance of an item from the rope. + /// Runs in O(N). + /// + public bool Remove(T item) + { + int index = IndexOf(item); + if (index >= 0) { + RemoveAt(index); + return true; + } + return false; + } + + /// + /// 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. + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public IEnumerator GetEnumerator() + { + this.root.Publish(); + return Enumerate(root); + } + + /// + /// Creates an array and copies the contents of the rope into it. + /// Runs in O(N). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public T[] ToArray() + { + T[] arr = new T[this.Length]; + CopyTo(arr, 0); + return arr; + } + + /// + /// Creates an array and copies the contents of the rope into it. + /// Runs in O(N). + /// + /// + /// This method counts as a read access and may be called concurrently to other read accesses. + /// + public T[] ToArray(int startIndex, int count) + { + VerifyRange(startIndex, count); + T[] arr = new T[count]; + CopyTo(startIndex, arr, 0, count); + return arr; + } + + static IEnumerator Enumerate(RopeNode node) + { + Stack> stack = new Stack>(); + 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 + + [Serializable] + class RopeNode + { + internal const int NodeSize = 256; + + internal static readonly RopeNode emptyRopeNode = new RopeNode { isShared = true, contents = new T[RopeNode.NodeSize] }; + + // Fields for pointers to sub-nodes. Only non-null for concat nodes (height>=1) + internal RopeNode 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); + 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 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 { + length = this.length, + contents = newContents + }; + } else { + return new RopeNode { + left = this.left, + right = this.right, + length = this.length, + height = this.height + }; + } + } + + internal RopeNode 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 CreateFromArray(T[] arr, int index, int length) + { + if (length == 0) { + return emptyRopeNode; + } + RopeNode node = CreateNodes(length); + return node.StoreElements(0, arr, index, length); + } + + internal static RopeNode CreateNodes(int totalLength) + { + int leafCount = (totalLength + NodeSize - 1) / NodeSize; + return CreateNodes(leafCount, totalLength); + } + + static RopeNode CreateNodes(int leafCount, int totalLength) + { + Debug.Assert(leafCount > 0); + Debug.Assert(totalLength > 0); + RopeNode result = new RopeNode(); + 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; + } + + /// + /// 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. + /// + 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 a = left; + RopeNode b = right.left; + RopeNode c = right.right; + // reuse right concat node, if possible + this.left = right.isShared ? new RopeNode() : 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 a = left.left; + RopeNode b = left.right; + RopeNode c = right; + // reuse left concat node, if possible + this.right = left.isShared ? new RopeNode() : 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.Array; + #endif + } + this.left = null; + right.CopyTo(0, this.contents, lengthOnLeftSide, this.right.length); + this.right = null; + } + } + + /// + /// Copies from the array to this node. + /// + internal RopeNode StoreElements(int index, T[] array, int arrayIndex, int count) + { + RopeNode 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; + } + + /// + /// Copies from this node to the array. + /// + 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 SetElement(int offset, T value) + { + RopeNode 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 Concat(RopeNode left, RopeNode 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 concatNode = new RopeNode(); + concatNode.left = left; + concatNode.right = right; + concatNode.length = left.length + right.length; + concatNode.Rebalance(); + return concatNode; + } + } + + /// + /// Splits this leaf node at offset and returns a new node with the part of the text after offset. + /// + RopeNode SplitAfter(int offset) + { + Debug.Assert(!isShared && height == 0 && contents != null); + RopeNode newPart = new RopeNode(); + 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 Insert(int offset, RopeNode 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 result = CloneIfShared(); + if (result.height == 0) { + // leaf node: we'll need to split this node + RopeNode left = result; + RopeNode 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 Insert(int offset, T[] array, int arrayIndex, int count) + { + Debug.Assert(count > 0); + + if (this.length + count < RopeNode.NodeSize) { + RopeNode 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 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 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 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 + + /// + /// 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. + /// + internal virtual RopeNode GetContentNode() + { + throw new InvalidOperationException("Called GetContentNode() on non-FunctionNode."); + } + } + + sealed class FunctionNode : RopeNode + { + Func> initializer; + RopeNode cachedResults; + + public FunctionNode(int length, Func> 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 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> initializerCopy = this.initializer; + this.initializer = null; + Rope resultRope = initializerCopy(); + if (resultRope == null) + throw new InvalidOperationException("Rope initializer returned null."); + RopeNode 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 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 +{ + /// + /// TextReader implementation that reads text from a rope. + /// + public sealed class RopeTextReader : TextReader + { + Stack> stack = new Stack>(); + RopeNode currentNode; + int indexInsideNode; + + /// + /// 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. + /// + public RopeTextReader(Rope 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); + } + + /// + public override int Peek() + { + if (currentNode == null) + return -1; + return currentNode.contents[indexInsideNode]; + } + + /// + 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(); + } + } + + /// + 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 +{ + /// + /// Represents a string with a segment. + /// Similar to System.ArraySegment<T>, but for strings instead of arrays. + /// + public struct StringSegment : IEquatable + { + readonly string text; + readonly int offset; + readonly int count; + + /// + /// Creates a new StringSegment. + /// + 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; + } + + /// + /// Creates a new StringSegment. + /// + public StringSegment(string text) + { + if (text == null) + throw new ArgumentNullException("text"); + this.text = text; + this.offset = 0; + this.count = text.Length; + } + + /// + /// Gets the string used for this segment. + /// + public string Text { + get { return text; } + } + + /// + /// Gets the start offset of the segment with the text. + /// + public int Offset { + get { return offset; } + } + + /// + /// Gets the length of the segment. + /// + public int Count { + get { return count; } + } + + #region Equals and GetHashCode implementation + /// + public override bool Equals(object obj) + { + if (obj is StringSegment) + return Equals((StringSegment)obj); // use Equals method below + else + return false; + } + + /// + public bool Equals(StringSegment other) + { + // add comparisions for all members here + return object.ReferenceEquals(this.text, other.text) && offset == other.offset && count == other.count; + } + + /// + public override int GetHashCode() + { + return text.GetHashCode() ^ offset ^ count; + } + + /// + /// Equality operator. + /// + public static bool operator ==(StringSegment left, StringSegment right) + { + return left.Equals(right); + } + + /// + /// Inequality operator. + /// + 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 +{ + /// + /// Creates TextFormatter instances that with the correct TextFormattingMode, if running on .NET 4.0. + /// + static class TextFormatterFactory + { + /// + /// Creates a using the formatting mode used by the specified owner object. + /// + public static TextFormatter Create(DependencyObject owner) + { + if (owner == null) + throw new ArgumentNullException("owner"); + return TextFormatter.Create(TextOptions.GetTextFormattingMode(owner)); + } + + /// + /// Returns whether the specified dependency property affects the text formatter creation. + /// Controls should re-create their text formatter for such property changes. + /// + public static bool PropertyChangeAffectsTextFormatter(DependencyProperty dp) + { + return dp == TextOptions.TextFormattingModeProperty; + } + + /// + /// Creates formatted text. + /// + /// The owner element. The text formatter setting are read from this element. + /// The text. + /// The typeface to use. If this parameter is null, the typeface of the will be used. + /// The font size. If this parameter is null, the font size of the will be used. + /// The foreground color. If this parameter is null, the foreground of the will be used. + /// A FormattedText object using the specified settings. + 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 +{ + /// + /// Contains exception-throwing helper methods. + /// + static class ThrowUtil + { + /// + /// Throws an ArgumentNullException if is null; otherwise + /// returns val. + /// + /// + /// Use this method to throw an ArgumentNullException when using parameters for base + /// constructor calls. + /// + /// public VisualLineText(string text) : base(ThrowUtil.CheckNotNull(text, "text").Length) + /// + /// + public static T CheckNotNull(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 +{ + /// + /// WeakEventManager with AddListener/RemoveListener and CurrentManager implementation. + /// Helps implementing the WeakEventManager pattern with less code. + /// + public abstract class WeakEventManagerBase : WeakEventManager + where TManager : WeakEventManagerBase, new() + where TEventSource : class + { + /// + /// Creates a new WeakEventManagerBase instance. + /// + protected WeakEventManagerBase() + { + Debug.Assert(GetType() == typeof(TManager)); + } + + /// + /// Adds a weak event listener. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static void AddListener(TEventSource source, IWeakEventListener listener) + { + CurrentManager.ProtectedAddListener(source, listener); + } + + /// + /// Removes a weak event listener. + /// + [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")] + public static void RemoveListener(TEventSource source, IWeakEventListener listener) + { + CurrentManager.ProtectedRemoveListener(source, listener); + } + + /// + protected sealed override void StartListening(object source) + { + if (source == null) + throw new ArgumentNullException("source"); + StartListening((TEventSource)source); + } + + /// + protected sealed override void StopListening(object source) + { + if (source == null) + throw new ArgumentNullException("source"); + StopListening((TEventSource)source); + } + + /// + /// Attaches the event handler. + /// + protected abstract void StartListening(TEventSource source); + + /// + /// Detaches the event handler. + /// + protected abstract void StopListening(TEventSource source); + + /// + /// Gets the current manager. + /// + [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 +{ + /// + /// Wrapper around Win32 functions. + /// + static class Win32 + { + /// + /// Gets the caret blink time. + /// + public static TimeSpan CaretBlinkTime { + get { return TimeSpan.FromMilliseconds(SafeNativeMethods.GetCaretBlinkTime()); } + } + + /// + /// Creates an invisible Win32 caret for the specified Visual with the specified size (coordinates local to the owner visual). + /// + 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; + } + } + + /// + /// Sets the position of the caret previously created using . position is relative to the owner visual. + /// + 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; + } + } + + /// + /// Destroys the caret previously created using . + /// + 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(); + } + } +} -- cgit v1.3.1