Introduction
When programming advanced graphical interfaces developers often face the problem of how to physically arrange items on the screen. This typically includes a need to calculate the extent to which various graphical elements are distributed. If graphical elements are recursively filled with other elements similar to them, then calculating the size of the parent element boils down to calculating the bounding rectangle of the inner elements. A similar example is when maintaining scrollbars: then we need to know the dimensions of the design being scrolled which again ends up in analyzing locations and sizes of its contained visual elements.
All these cases heavily rely on the ability to calculate a minimum and a maximum over a changing set of numerical values. It is important to note that the set of values are changing due to the dynamic nature of the object model being presented on the graphical interface. In the previous article titled Maintaining Scrollbars in Document Editing Applications we have shown that a horizontal scrollbar's Maximum property can be calculated as the maximum width of all rows in the document. If the document is very large, being many megabytes in size, with the total number of lines ranging in millions, then calculating the maximum width of any line can be a time consuming task if the contents of the document is changing due to a user typing in new content all the time.
Of course it is simple to calculate a maximum value of one million numbers in one go. But that is not what we actually need. In fact, the longest line in a large document is not a static property. It is simple to realize that if the user types additional text at the end of the longest line, then with every keystroke the value of the maximum function effectively changes to the new length of that line. But the problem exists when the user tries to delete characters or complete words from the end of the longest line. In that case we might conclude that a maximum function value has reduced but we cannot easily conclude which line is the next longest. We do not want to iterate through a million lines to find the next maximum, because doing that on every keystroke would be time consuming and the user would notice that application runs slow. We want the better, faster way to do it.
Another example similar to the one with the horizontal scrollbar is when we need to calculate the bounding rectangle of the number of graphical elements. It is quite a common task in advanced interface programming. In the special case, when elements for which we are finding the bounding rectangle are changing, in particular changing their location and size, the bounding rectangle may also change in time. One such application is a flowchart editor in which we need an efficient method to calculate the minimum of left and top edges and maximum of right and bottom edges of the flowchart elements, thus getting the bounding rectangle of the whole flowchart.
One solution to the problem has been proposed in the article mentioned above and in this article that we are going to implement is that the solution in full detail is in the form of reusable classes – classes that can be used in any GUI application so that the developer can concentrate on dealing with actual graphical elements rather than calculating their locations.
Further in this article the design of these helper classes will be explained and then a full example will follow, showing how to use these classes in practice. Please feel free to download the source code attached to this article, as the source will not be shown in this text due to it's size.
DiscreteMinFunction Class Design
In this and the following section we will explain the design of two classes, one implementing a minimum function and another one implementing a maximum function. Both classes will rely on the SortedDictionary collection. We are going to make these classes generic, accepting a value type as a generic type parameter, so that both functions can be applied to many numerical types. That will ensure that every particular instance compiles strictly for a specific value type that we need, thus increasing the performance.
Also, we need a way to compare values of the generic type, and for that purpose we are going to require that the type implements IComparable interface. Please note that all numeric types like Int32, Int16, Double, even Boolean, meet these requirements. Consequently, requiring a generic type parameter to be a value type and to implement an IComparable interface is a sufficient set of requirements to be able to implement minimum and maximum functions for numerical types.
We will first introduce an interface named IAggregateFunction, which will be common for classes implementing minimum and maximum functions:
public interface IAggregateFunction<T> where T : struct
{
T AddValue(T value);
T RemoveValue(T value);
T UpdateValue(T value, T replaceWith);
T OutputValue { get; }
int Count { get; }
}
Basically, minimum and maximum function classes will operate as sets of values, and the output value of the function is calculated as an aggregate over the set. Both classes accept new values through the AddValue method, which returns the current function value after a new item has been added to the contained set. Also we need to dynamically remove values from the set and that is done by using the RemoveValue method. This method also returns new a function value after an item has been removed from the set. Method UpdateValue is used to change an item that was previously added to the set, and this method also returns a function value after the update. We can also obtain a current minimum or maximum value via the read only property OutputValue.
The first class is named DiscreteMinFunction and it implements, as its name implies, the minimum function. We are starting with the minimum function because the underlying structure, the SortedDictionary collection, sorts keys in the ascending order. Therefore, by picking up the first key from the collection we are actually picking the result of the minimum function.
The DiscreteMinFunction bases its operation on the following idea. We do not place all the values into the set (multiset, to be precise) and then calculate the minimum value over that set. Instead, we group values from the set and count how many instances of each of the values are present - this is actually a typical implementation of the multiset in practice. Hence, the SortedDictionary maps distinct values into their count. For example, if there are values 1, 1, 2, 1, 3, 2 entered into the collection, they will be mapped as 1 into 3, 2 into 2 and 3 into 1. This mapping tells that value 1 occurs three times in the set, value 2 two times and value 3 only once.
In this way, we are keeping the underlying structure as compact as possible. This is very important, because if we are having millions of lines in the document, it is not realistic to expect that all these lines will have distinct lengths. It is rather expectable to have only a limited number of distinct lengths appearing in the document, probably not more than an order of thousands rather than millions. Grouping of the same values together then significantly reduces total size of the data structure.
Now that we have decided how to map the data inside the class, we need one more thing to do before we proceed. It is not advisable to use the dictionary for a small amount of data, because accessing its internal structures can be disproportionally expensive compared to total amount of useful data processed. For that reason, when the total number of distinct values is small, e.g. not larger than 10, then we will not use the SortedDictionary, but rather a plain array. By doing that we are assured that all operations will be completed extremely quickly, because iterating through a short array is extremely fast and no special data structure should be used instead. Only when the number of distinct values stored in the set grows beyond 10 will we employ the SortedDictionary.
If later on the number of distinct values goes below half of the upper limit (which is below 6 in this case), we will return to the array again. The difference between the lower and upper bound at which we switch to another data structure is aimed to avoid an unfortunate situation when switchover is done too often, which would become very inefficient because that operation requires copying all values from one data structure into another. This concludes the design of a class which efficiently calculates a minimum value over a dynamically changing multiset.
DiscreteMinFunction Class Design
When designing the maximum function class, we should first note that SortedDictionary always orders the keys ascending and we cannot efficiently reach the last key in that collection. However, we can force the dictionary to sort the data in the opposite order. It is possible to change comparison methods for SortedDictionary by setting its Comparer property, but that might complicate our design and would not improve performance compared to the solution that will be proposed next.
To show how to solve the problem, just imagine that a sorted dictionary is used on keys of type integer. We can find the maximum key value very easily if we do not store actual values as keys, but rather their negative counterparts. In that case, what comes up as the smallest value, i.e. the first key in the dictionary, is rather a negative maximum value of all original values. We only need to negate the smallest key and that will give us the maximum value. For example, if we need to store values 1, 2 and 3, we would effectively store values -1, -2 and -3. The minimum of these three values is -3. So the maximum is obtained by negating it again, and that is value 3 as expected.
However, we cannot use this idea in a general case. First of all, we do not have access to an unary minus operator in .NET generics. Second, we do not know that numbers stored will be signed at all. Third, even if we do have signed numbers at hand, positive and negative intervals in 2's complement are not symmetrical, which has a consequence that the smallest negative value in any signed integer type does not have its positive counterpart in the same type. So this negation idea, however nice it is, does not produce any general solution to the problem. But on the other hand it gives a good starting point to develop a general solution. Here is the proposal of how to do that.
We can implement a helper generic structure called InvertedComparable, which implements IComparable. This structure contains a single value of its generic type and implements the CompareTo method to compare itself to another InvertedComparable structure. But this CompareTo operation is implemented in a bit strange way. It compares the two values contained in the two structures, but then returns the negated result of that comparison. What originally was a larger value now comes to be smaller, and vice versa. Here is the shortened implementation of the InvertedComparable structure.
public struct InvertedComparable<T> : IComparable
where T : struct, IComparable
{
public InvertedComparable(T value) { _value = value; }
public T Value { get { return _value; } }
public int CompareTo(object obj)
{
InvertedComparable<T> other = (InvertedComparable<T>)obj;
return -_value.CompareTo(other._value);
}
private T _value;
}
It becomes clear that the DiscreteMaxFunction class is effectively equal to a DiscreteMinFunction class, with only a small modification: it now looks for the minimum over InvertedComparable counterparts of actual values stored in the DiscreteMaxFunction class. Please feel free to browse the source code of the DiscreteMaxFunction class implementation for details.
Example
In this section we will design a full solution to a bounding rectangle problem, just to demonstrate how easy and natural is the use of DiscreteMinFunction and DiscreteMaxFunction classes in graphical user interface design.
Suppose that we are designing a flowchart drawing application. Flowchart consists of blocks which can be arranged on the drawing surface. Flowchart's boundaries are effectively decided by extreme positions of contained blocks. Suppose that flowchart and it's blocks implement these interfaces:
public interface IFlowchartBlock
{
Rectangle Rectangle { get; }
event EventHandler RectangleChanged;
}
public class BlockEventArgs: EventArgs
{
...
public IFlowchartBlock Block { get { ... } }
...
}
public interface IFlowchart
{
IList<FlowchartBlock> Blocks { get; }
event EventHandler<BlockEventArgs> BlockAdded;
event EventHandler<BlockEventArgs> BlockRemoved;
}
Now we want to track the bounding rectangle of all blocks contained in the flowchart and for that purpose we will use DiscreteMinFunction and DiscreteMaxFunction classes. We will instantiate the DiscreteMinFunction class twice - to keep track of the left and top coordinates of the flowchart blocks. Then we will instantiate DiscreteMaxFunction twice - to keep track of the right and bottom coordinates of the flowchart blocks. Corresponding coordinates of the bounding rectangles are then directly read from these aggregates.
To keep the whole solution dynamic, we need to handle the BlockMoved events on all flowchart blocks, as well as to handle BlockAdded and BlockRemoved events on the flowchart. All this looks quite straight-forward and here is the complete class which can be used to solve the problem.
public class BoundingRectangleTracker
{
// Constructor
public BoundingRectangleTracker(IFlowchart fc)
{
foreach (IFlowchartBlock fcb in fc.Blocks)
{
Rectangle rect = fcb.Rectangle;
_blockToRect.Add(fcb, rect);
_left.AddValue(rect.Left);
_top.AddValue(rect.Top);
_right.AddValue(rect.Right);
_bottom.AddValue(rect.Bottom);
fcb.RectangleChanged += new EventHandler(BlockMoved);
}
fc.BlockAdded += new EventHandler<BlockEventArgs>(BlockAdded);
fc.BlockRemoved += new EventHandler<BlockEventArgs>(BlockRemoved);
}
// Handles BlockAdded on the flowchart object
// Adds block to evidence
void BlockAdded(object sender, BlockEventArgs e)
{
Rectangle rect = e.Block.Rectangle;
_left.AddValue(rect.Left);
_top.AddValue(rect.Top);
_right.AddValue(rect.Right);
_bottom.AddValue(rect.Bottom);
_blockToRect.Add(e.Block, rect);
}
// Handles BlockRemoved on the flowchart object
// Removes block from evidence
void BlockRemoved(object sender, BlockEventArgs e)
{
Rectangle rect = e.Block.Rectangle;
_left.RemoveValue(rect.Left);
_top.RemoveValue(rect.Top);
_right.RemoveValue(rect.Right);
_bottom.RemoveValue(rect.Bottom);
_blockToRect.Remove(e.Block);
}
// Handles BlockMoved on the flowchart block object
// Updates evidence about block's size and location
void BlockMoved(object sender, EventArgs e)
{
IFlowchartBlock fcb = (IFlowchartBlock)sender;
Rectangle rect = _blockToRect[fcb];
Rectangle newRect = fcb.Rectangle;
_blockToRect[fcb] = newRect;
_left.UpdateValue(rect.Left, newRect.Left);
_top.UpdateValue(rect.Top, newRect.Top);
_right.UpdateValue(rect.Right, newRect.Right);
_bottom.UpdateValue(rect.Bottom, newRect.Bottom);
}
// Extracts current bounding rectangle coordinates from the evidence
public Rectangle BoundingRectangle
{
get
{
int x = _left.OutputValue;
int y = _top.OutputValue;
int width = _right.OutputValue - x;
int height = _bottom.OutputValue - y;
return new Rectangle(x, y, width, height);
}
}
// Minimum and maximum functions keeping track of
// bounding rectangle coordinates
private DiscreteMinFunction<int> _left =
new DiscreteMinFunction<int>();
private DiscreteMinFunction<int> _top =
new DiscreteMinFunction<int>();
private DiscreteMaxFunction<int> _right =
new DiscreteMaxFunction<int>();
private DiscreteMaxFunction<int> _bottom =
new DiscreteMaxFunction<int>();
// Last known locations and sizes of all blocks in the flowchart
private Dictionary<IFlowchartBlock, Rectangle> _blockToRect =
new Dictionary<IFlowchartBlock, Rectangle>();
}
Conclusion
This article has demonstrated why it is important to have minimum and maximum aggregate function implementations ready for use when designing a graphical interface containing elements that change their size and locations over time.
In addition to text, which explains the design of classes implementing these functions, complete source code of DiscreteMinFunction and DiscreteMaxFunction classes is provided. The source code has been fully tested and used in practical application design.
Example above shows how simple it is to incorporate these classes in your code, so that the code can remain free of cumbersome calculations and value comparisons. This significantly saves time to develop and test graphical editors in part which deals with size and locations of the graphical elements.
Performance measurement shows that DiscreteMinFunction and DiscreteMaxFunction classes consistently execute AddValue and RemoveValue methods in 10 microseconds time on average when containing one million distinct integer values. Tests have been performed on Intel Core2 Quad CPU Q8400 at 2.66 GHz.