A priority queue is a queue data structure where the element with the lowest (or highest) value is always at the front. A common analogy is to think of a queue of people ordered by some criteria such as age or height. Many programming languages include a priority queue in their standard library, including C++ and Java. However, the Microsoft .Net Framework does not include a priority queue, which is why I provide one here.
You might wonder why you can’t just use a sorted list to get the same effect as a priority queue. And the answer is, you can. A sorted list is a perfectly valid way to implement a priority queue. However, with a priority queue we are only interest in the smallest element at any time, and not any of the other elements, which means it is not necessary to maintain a total order of all the elements. Because of this, we can use an implementation that maintains only a partial order, which can provide better performance.
The most common such implementation is one that uses a binary heap. A binary heap is a binary tree with the property that any element in the tree is always smaller than both of its children. This guarantees that the smallest element is always on top, although the binary heap does not maintain a total order like a binary search tree. Efficient operations exist to maintain this heap property when inserting and deleting elements, making the binary heap perform better for priority queues than a sorted list. My PriorityQueue class for .Net uses a binary heap implementation.
The PriorityQueue<T> generic class that I provide here is written to conform to the conventions used by .Net’s built-in collection classes in the System.Collections.Generic namespace, particularly the Queue<T> class. The PriorityQueue<T> class implements IEnumerable<T> and ICollection.
The three main operations provided are Enqueue, which adds an item to the queue; Dequeue, which removes and returns the first element of the queue; and Peek, which returns the first element without removing it. In this implementation, these operations are O(log n), O(log n) and O(1) respectively. A special operation, AdjustFirstItem, allows you to change the value of the first item and re-evaluate its position in the queue, in less time than it would’ve taken to remove the element and add a new one (note that this is only possible with reference types that are not immutable).
The PriorityQueue<T> class provides several constructors, including one that allows you to create a priority queue from an existing list of elements with O(n) time complexity, faster than individually adding each element to the list with Enqueue.
You can put any type of element in the priority queue as long as it implements IComparable<T>, or you provide a custom IComparer<T> for the type. Note that the PriorityQueue<T> class will always put the smallest element at the front. If you want to have the largest element at the front, you can use the included InvertedComparer<T> class.
A short example of how to use the PriorityQueue<T> class is provided below.
PriorityQueue<int> queue = new PriorityQueue<int>(new[] { 4, 7, 3, 9, 12 }); // create a priority queue with the specified elements. int n = queue.Dequeue(); // returns and removes 3; the front element is now 4. queue.Enqueue(5); // the front element is still 4. queue.Enqueue(2); // the front element is now 2. n = queue.Peek(); // returns 2, but does not remove it.
Download the PriorityQueue<T> class for .Net (class library, sample application, and source code provided).
I have made available a new download: Ookii.Dialogs.
Ookii.Dialogs is a class library that provides a number of common dialogs for use in .Net applications. The dialogs provided are the task dialog, progress dialog, credential dialog, input dialog and Vista-style common file dialogs.
The download contains two class libraries, one for Windows Forms and one for Windows Presentation Foundation (WPF). The contents are nearly identical; only the input dialog is not available for WPF. Some utility classes are provided for Windows Forms; these are not available for WPF either.
Most of these dialogs are wrappers around Windows API functionality. The TaskDialog class wraps the task dialog API provided in Windows Vista and later. The ProgressDialog class wraps the IProgressDialog API available since Windows 2000. The CredentialDialog class wraps the CredUI API introduced in Windows XP, and the VistaOpenFileDialog, VistaSaveFileDialog and VistaFolderBrowserDialog classes wrap the IFileDialog API introduced in Windows Vista. Only the InputDialog is not a wrapper; this is a custom dialog that performs the same functionality as the old Visual Basic InputBox function. Visit the link above for more details on each dialog.
Each class has been designed to be not merely a wrapper around their respective native API, but to provide a programming interface that is natural to .Net developers, with full support for the component designer. The complete source code of the class libraries, as well as documentation and a sample application are provided.
The classes aim to give the best experience possible on each OS, where applicable. In the case of the CredentialDialog class, this means that the new Vista-style dialog is automatically used on operating systems that support it (Vista and newer). The Vista-style file dialog classes will automatically fall back to the old style dialogs when using Windows XP. This is also true of the VistaFolderBrowserDialog class for WPF, even though WPF itself doesn't provide a folder browser dialog; the VistaFolderBrowserDialog class is a full folder browser dialog implementation for WPF supporting XP and newer.
This library replaces the Ookii.VistaDialogs library, which contained only the Vista-style file dialogs and didn't offer any support for WPF.
This library is a collection of classes that I have developed for personal use over the years. Because of the difference in age of some of the code, and the many modifications made over time, there may be some inconsistencies.
Let me know what you think of it, if you use it.
There are many ways to randomize a list; perhaps the most common is to simply iterate over the list and swap each element with a random other element. Some libraries even include built-in methods for randomizing a list, but .Net isn’t one of those.
The introduction of LINQ in .Net 3.5 provides an easy way to manipulate lists and collections in all sorts of ways. So naturally one question that may come up is, can we use it to randomize a list? The answer is yes, you can. There’s probably more than one way to do it, but here’s one I like myself.
Random rnd = new Random(); var randomizedList = from item in list orderby rnd.Next() select item;
The orderby clause will use the specified expression to compare elements to determine their order. Here, it is using random values to do that comparison, so the end result is a randomized list.
Of course we can easily create an extension method to make things even easier (here I use an alternative syntax to use orderby, just to demonstrate how to do it with that):
public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source) { Random rnd = new Random(); return source.OrderBy<T, int>((item) => rnd.Next()); }
When you run an application created using .Net 2.0 or later on an x64 version of Windows, it will execute as a native 64 bit application. This is generally a good thing; your application gets to use the larger virtual address space and other advantages of x64 without you needing to change anything.
There are however a few consequences of running as a 64 bit process which need to be understood. There are three main differences when your application is running as a 64 bit process:
The first issue is relatively well known. A 64 bit process cannot load 32 bit DLLs, and .Net is no exception. This isn’t a problem if you use PInvoke to use native Windows APIs; all the Windows DLLs come in both 32 and 64 bit versions. But if you’re using a third party (or your own) native DLL or COM component, you need to be aware of this. Also some .Net libraries, such as Managed DirectX and XNA, indirectly depend on 32 bit DLLs and will therefore not work in a 64 bit process. If you try to run such an application on Windows x64, it will crash with a BadImageFormatException.
If your application depends on any external native DLLs and you cannot provide a 64 bit version of those DLLs, or if the application is otherwise incompatible with x64, you should change the target CPU of your executable to x86. For C# projects in Visual Studio 2008, you can find this setting on the “Build” tab of the project properties; the “Platform target” setting is the one you want. For Visual Basic projects, look under the “Compile” tab, click the “Advanced Compile Options…” button, and change the “Target CPU” setting. When you change this setting, the compiler adds an attribute to the executable to tell the CLR to always run the program as a 32 bit process. You can also set this setting to x64 or ia64 which means your application will fail to run on systems that don’t support those architectures.
The second issue is less well known, and it applies to Windows Vista and newer only. If you have UAC enabled your application will run with limited rights, and cannot write to many locations such as Program Files or HKEY_LOCAL_MACHINE in the registry. For compatibility, Windows will redirect attempts to write to these locations to a different folder in the user’s profile (in %LocalAppData%\VirtualStore, to be precise). For 32 bit processes, this behaviour is enabled by default (you can manually disable it using a manifest), but for 64 bit processes, it is always disabled (it cannot be enabled at all) so if you attempt to write to these locations, it will fail.
File and registry virtualisation can be disabled for 32 bit processes using a manifest, and to make your application behave consistently on both 32 and 64 bit systems I strongly recommend you do this. Visual Studio 2008 will automatically embed a manifest in your application that disables the virtualisation. If you are using Visual Studio 2005, you can use this method to embed the manifest.
The final issue has to do with Data Execution Prevention. XP and Vista will not apply DEP protection to a 32 bit process unless the executable is marked with the NXCOMPAT flag, but for 64 bit processes, DEP is always enabled. If you interop with native code which might be incompatible with DEP you need to be aware of this. Visual Studio 2008 (and Visual Studio 2005 as well, provided you’re using .Net 2.0 SP1) will mark the application with the NXCOMPAT flag so DEP will be enabled for 32 bit processes as well. If your application is not compatible with DEP, and you cannot fix it for some reason, you must set the platform target to x86 as described above, and remove the NXCOMPAT flag.
.Net Remoting is quite an old technology, and has been superseded by Windows Communication Foundation in .Net 3.0. However, that doesn’t mean it’s useless; you may have an old application that already uses it, or you may need to target clients that don’t have .Net 3.0, or maybe you’re even working with Mono, which currently doesn’t support WCF. In all these scenarios, using .Net Remoting is still perfectly valid.
.Net Remoting was introduced in .Net 1.0, and broad support for IPv6 was not introduced until .Net 2.0. For reasons of backwards compatibility, a .Net Remoting server still listens on IPv4 by default, even in .Net 2.0 and higher. Only if your networking configuration supports only IPv6 (IPv4 is disabled completely) will .Net Remoting automatically listen on IPv6.
It seems like that should be fine. After all, if your network supports IPv4, what is the problem with using it? It turns out there is one, and it’s quite subtle. If your network is configured to use both IPv6 and IPv4, and your Remoting clients are using host names to connect to the server, those host names will resolve to both an IPv6 and IPv4 address. Windows will then try to connect using IPv6 first – which fails because the server is listening only on IPv4 – causing a delay of a few seconds on the initial connection.
You can easily reproduce this problem by having a .Net Remoting client connect to a server on the local host on a computer running Vista with the default networking setup which has IPv6 enabled. If you use localhost in the well-known service URL it will attempt IPv6 first, causing a delay. If instead you use 127.0.0.1 it will be much quicker. However, using IP addresses instead of host names may not be practical, and disabling IPv6 is also a bit of a sledgehammer solution. A better idea is to make .Net Remoting listen on IPv6.
Although it can be rather hard to find out how to do this from the documentation, it turns out to be quite simple. If you use the app.config file to configure remoting you can use the bindTo attribute of the channel to listen on IPv6. If you just add that attribute, the server will no longer listen on IPv4 however; if you want both IPv4 and IPv6, you need to define two channels. An example is given below:
<system.runtime.remoting> <application> <service> <wellknown mode="Singleton" type="MyApplication.MyServer, MyAssembly" objectUri="MyServer" /> </service> <channels> <channel ref="tcp" name="tcp6" port="9000" bindTo="[::]" /> <channel ref="tcp" name="tcp4" port="9000" bindTo="0.0.0.0" /> </channels> </application> </system.runtime.remoting>
As you can see, the IPv6 addresses are enclosed in square brackets. By using [::], the server will listen on all IPv6 addresses; you can of course also specify an explicit IPv6 address to listen on, same as for IPv4. For example, [::1] would cause it to listen on the local host only. This example uses a TCP channel, but the same principle works for HTTP channels as well.
If you configure remoting programmatically, you can use the same approach:
IDictionary properties = new Hashtable(); properties["name"] = "tcp6"; properties["port"] = 9000; properties["bindTo"] = "[::]"; TcpServerChannel channel = new TcpServerChannel(properties, null); ChannelServices.RegisterChannel(channel, false);
Again, if you need it to listen on both IPv6 and IPv4, you need to configure two channels. The client does not need to be changed at all, for both methods of configuration.
A small note for people who are using Mono: on Linux, if you bind to an IPv6 address, it will automatically bind to the equivalent IPv4 address as well. In that case, you don’t need to specify two channels, just create a channel for IPv6 and it will listen on IPv4 too. This behaviour is exclusive to Linux, other flavours of Unix (e.g. FreeBSD) don’t do it.
Subscribe