3 posts tagged “.net”
For archive purposes, I am posing a custom, generic, sortable, event-driven, doubly-linked list. In the future I will run some tests on it to see if it beats the current linked list implementation provided by the .NET framework. For those unsure of what a linked list is, here is a small tutorial on it.
Collections
When programming a computer, it is very common to store many items of the same type. Some different types of storing methods include array's, lists, and linked lists. The array is probably the most common for those attempting to store items. When an array of items is specified, the computer goes into memory and searches for a place to allocate the array. If it cannot allocate the entire array, it will keep searching. until it can.
Note: I put 5 spaces in the array definition. This is because of a manifest placed in the array, however, the inter workings of memory is beyond the scope of this article.
Now the problem with the array rises when someone runs out of room in their array. If they have an array that is 5 items large, and they want to hold a 6th, they must now re-define an entirely new array that can hold the new information. This requires the computer to go through and find another spot in memory that is big enough, place the new array in there, and then copy the elements from the original array to the new array. This problem is where a linked list comes in handy.
The Linked List
When a linked list is used, every item is stored in a chain of items. The linked list works by housing the references to the next (and previous in doubly linked lists) items in the chain. To do this, it is common to house your value inside a node. That node contains a reference in memory to the next node. Thus, you can define nodes anywhere you want in memory as long as you link to it making it easy to add and remove any amount of elements in the chain. The code would look something like this if you are trying to store integers:
public class LinkedList
{
Node firstNode;
public class Node
{
Node previous;
Node next;
int value;
}
}
Problems
With anything in computer science, there are downfalls to using Linked Lists. In order to get to an element in the linked list, you must traverse the entire list until you get to that element. This can be time consuming if there are a lot of nodes. Another problem is if you lose a reference to one of the nodes, you break the entire list. However, in a lot of circumstances, it is very useful to be able to add and remove items on the fly just by changing references.
Source
Here is an example doubly linked list example that I wrote. Thank dusda for the event driven idea. It is a doubly linked list that will convert to an array if needed. It supports any data type, and automatically sorts if specified. There is even support for getting an item by it's location (index). I hope you all find it useful.
using System;
namespace Systepic.Collections
{
/// <summary>
/// Event Handler designed to be thrown
/// when a collection's list items change.
/// </summary>
/// <param name="sender">The list that
/// fired the event.</param>
/// <param name="e">Information about
/// what the event did.</param>
public delegate void CollectionEventHandler(
Object sender, CollectionEventArgs e);
/// <summary>
/// Class inheriting from EventArgs designed
/// to hold information about the state change
/// of a collection.
/// </summary>
public class CollectionEventArgs : EventArgs
{
public CollectionEventArgs():base(){}
}
/// <summary>
/// A generic sortable linked list.
/// </summary>
/// <typeparam name="T">The type
/// that the linked list is. The type
/// should be a valuetype or a string
/// in order to be sorted.</typeparam>
public class LinkedList<T>
{
/// <summary>
/// An event fired whenever the collection
/// contents change.
/// </summary>
public event CollectionEventHandler ListChanged;
/// <summary>
/// The initial node to iterate in the list.
/// </summary>
private Node<T> firstNode;
/// <summary>
/// The number of items in the linked list.
/// </summary>
private int count;
/// <summary>
/// Whether or not it is a sorted list.
/// </summary>
private bool sorted;
/// <summary>
/// Create a new unsorted
/// linked list.
/// </summary>
public LinkedList() : this(false) { }
/// <summary>
/// Create a new linked list that
/// can be a sorted linked list.
/// </summary>
/// <param name="sorted">Whether or not
/// the linked list should be sorted.</param>
public LinkedList(bool sorted)
{
this.count = 0;
this.sorted = sorted;
}
/// <summary>
/// Adds an item to the end of the current
/// linked list. If the linked list is a
/// sorted list, the list is re-sorted.
/// </summary>
/// <param name="item">The item that should
/// be added to the linked list.</param>
/// <returns>Whether or not the item was
/// added successfully.</returns>
public bool Add(T item)
{
// Add if there is none
if (this.count == 0)
this.firstNode = new Node<T>(item);
else
{
Node<T> temp = this.firstNode;
for (int x = 1; x < this.count; ++x)
temp = temp.Next;
// Add a new item to the list
temp.Next = new Node<T>(
item, temp, null);
}
// increment the counter.
++count;
if (this.sorted) this.Sort();
// fire the event
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
// Call the insertAt method.
return true;
}
/// <summary>
/// Insert an item at a specified index in
/// the linked list. If the linked list is
/// a sorted list, the list is re-sorted.
/// </summary>
/// <param name="item">The item to add to the
/// linked list.</param>
/// <param name="index">The 0 based index of where
/// it should be added at.</param>
/// <returns>Whether or not the item was added
/// successfully.</returns>
public bool InsertAt(T item, int index)
{
// make sure the index is valid
if (index < 0)
throw new IndexOutOfRangeException();
if (index >= this.count)
throw new IndexOutOfRangeException();
// make sure there is an actual place to insert
if (count == 0)
return false;
// Create temp node to store info
Node<T> tempNode = new Node<T>(item);
// Create a temporary for iteration
Node<T> temp = this.firstNode;
// get to the specified index
for (int x = 1; x <= index; ++x)
temp = temp.Next;
// get the current reference.
if (index > 0)
{
Node<T> prev = temp.Previous;
prev.Next = tempNode;
tempNode.Previous = prev;
}
// set the references
tempNode.Next = temp;
temp.Previous = tempNode;
if (index == 0)
this.firstNode = tempNode;
// update the list information
++count;
if(this.sorted) this.Sort();
// fire event
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
return true;
}
/// <summary>
/// Find a particular item and remove
/// it from the linked list.
/// </summary>
/// <param name="item">The item to find
/// in the list.</param>
/// <returns>Whether or not the item
/// was removed successfully.</returns>
public bool Remove(T item)
{
// make sure we can remove
if (count < 1)
return false;
Node<T> temp = this.firstNode;
// Iterate and find item
for (int x = 1; x <= this.count; ++x)
{
if ((item as object) == (temp.Value as object))
{
// Change the references
if (temp.HasNext && temp.HasPrevious)
{
temp.Previous.Next = temp.Next;
temp.Next.Previous = temp.Previous;
}
else if (temp.HasNext)
temp.Next.Previous = null;
else if (temp.HasPrevious)
temp.Previous.Next = null;
else
temp = null;
// Reset the first Node if we
// removed it.
if (x == 1 && temp != null)
this.firstNode = temp.Next;
// Handle the counter
--count;
}
if (temp != null && temp.HasNext)
temp = temp.Next;
}
// Resort the algorithm if it is
// a sorted algorithm
if (this.sorted) this.Sort();
// fire event
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
return true;
}
/// <summary>
/// Sorts a list using insertion sort. Although
/// this algorithm is considered slow, since the
/// list is always almost sorted, the time to sort
/// the list is really fast whereas most high speed
/// algorithms will not beat this in this particular
/// instance because they handle near-sorted
/// algorithms the same as unsorted.
/// </summary>
/// <returns>Whether or not the
/// list was sorted successfully.</returns>
public bool Sort()
{
if (this.firstNode.Value is IComparable)
{
// check index out of range
if (this.firstNode.Next == null)
return true;
// get the base comparison
Node<T> baseNode = this.firstNode.Next;
// traverse the nodes
for (int x = 2; x <= this.count; ++x)
{
if ((baseNode.Previous.Value as
IComparable).CompareTo(
baseNode.Value) == 1)
{
Node<T> comp = this.firstNode;
bool found = false;
for (int y = 1; y < x && found != true; ++y)
{
if ((baseNode.Value as
IComparable).CompareTo(comp.Value) != 1)
{
// We need to change the references
// to all of the nodes to re-order them.
if (baseNode.HasNext)
{
baseNode.Next.Previous =
baseNode.Previous;
baseNode.Previous.Next =
baseNode.Next;
}
else
baseNode.Previous.Next = null;
baseNode.Next = comp;
if (comp.HasPrevious)
{
comp.Previous.Next =
baseNode;
baseNode.Previous =
comp.Previous;
}
else
baseNode.Previous = null;
comp.Previous = baseNode;
// the references are set... make
// sure the first node gets reset
// if needed.
if (y == 1)
this.firstNode = baseNode;
found = true;
}
// Set the next node
if (comp.HasNext)
comp = comp.Next;
}
}
// Set the next node
if (baseNode.HasNext)
baseNode = baseNode.Next;
}
return true;
}
else
return false;
}
/// <summary>
/// Clears all of the items in the
/// list by removing the reference
/// to the first node. The remaining
/// nodes no longer have references to
/// the application and will be collected
/// by the GC.
/// </summary>
public void Clear()
{
// kill the reference
this.firstNode = null;
// reset the count
this.count = 0;
// let everyone know.
if (this.ListChanged != null)
this.ListChanged(this,
new CollectionEventArgs());
}
/// <summary>
/// Converts the linked list to
/// an array.
/// </summary>
/// <returns>An array of the items
/// in the linked list ordered by
/// their location in the list top
/// down.</returns>
public T[] ToArray()
{
if (this.count < 1)
return default(T[]);
T[] newArray = new T[this.count];
// create a temp node
Node<T> temp = this.firstNode;
newArray[0] = temp.Value;
// iterate and get the node
for (int x = 1; x < this.count; ++x)
{
temp = temp.Next;
newArray[x] = temp.Value;
}
return newArray;
}
/// <summary>
/// Allows the use of this linked list
/// like it is an array. Get an item
/// in the linked list by it's location
/// in the list.
/// </summary>
/// <param name="index">The 0 based location
/// of the item to get in the list.</param>
/// <returns>The item at the specified
/// location.</returns>
public T this[int index]
{
get
{
// make sure we can do it before traversal.
if (index + 1 > count)
throw new IndexOutOfRangeException();
// create a temp node
Node<T> temp = this.firstNode;
// iterate and get the node
for (int x = 1; x <= index; ++x)
temp = temp.Next;
// return the node value
return temp.Value;
}
set
{
// make sure we can do it before traversal.
if(index + 1 > count)
throw new IndexOutOfRangeException();
// create a temp node
Node<T> temp = this.firstNode;
// iterate and get the node
for (int x = 0; x < index; ++x)
temp = temp.Next;
// set the node to value
temp.Value = value;
}
}
/// <summary>
/// How many nodes are contained in the
/// Linked List.
/// </summary>
public int Length
{
get { return this.count; }
}
/// <summary>
/// Whether or not this list sorts
/// automatically.
/// </summary>
public bool IsSorted
{
get { return this.sorted; }
set { this.sorted = value; }
}
/// <summary>
/// Generic node with pre and post references
/// for use in a linked list.
/// </summary>
/// <typeparam name="U">The type of
/// information contained within the node.</typeparam>
private class Node<U>
{
/// <summary>
/// The node reference to the node
/// before this node reference.
/// </summary>
Node<U> pre;
/// <summary>
/// The node reference to the node after
/// this node reference.
/// </summary>
Node<U> post;
/// <summary>
/// The generic information stored within
/// the node.
/// </summary>
U assignment;
/// <summary>
/// Create a new node with references
/// to both sides of the node.
/// </summary>
/// <param name="info">What the node actually
/// contains.</param>
/// <param name="previous">The node before this
/// node.</param>
/// <param name="next">The node after this
/// node.</param>
public Node(U info, Node<U> previous, Node<U> next)
{
this.assignment = info;
this.pre = previous;
this.post = next;
}
/// <summary>
/// Create a new node with no references
/// to nodes.
/// </summary>
/// <param name="info">The information
/// that the node actually contains.</param>
public Node(U info) : this(info, null, null) { }
/// <summary>
/// The node before this node in the chain.
/// </summary>
public Node<U> Previous
{
get { return this.pre; }
set { this.pre = value; }
}
/// <summary>
/// The node after this node in the chain.
/// </summary>
public Node<U> Next
{
get { return this.post; }
set { this.post = value; }
}
/// <summary>
/// Whether or not the node has a node
/// reference to the previous node.
/// </summary>
public bool HasPrevious
{
get { return (this.pre == null) ? false : true; }
}
/// <summary>
/// Whether or not the node has a node
/// reference to the next node.
/// </summary>
public bool HasNext
{
get { return (this.post == null) ? false : true; }
}
/// <summary>
/// The actual value stored in this node.
/// </summary>
public U Value
{
get { return this.assignment; }
set { this.assignment = value; }
}
}
}
}
Dusda
and I have been working on an XNA project to replace our DirectX
project. Again, since my updates fail to compare to my experiences, the
viewers of this blog have no idea what I am talking about (Except for
the house members). XNA is Microsoft's release of a framework to
develop Xbox 360 and Windows game applications. Beings that Dusda
and I had a directx assignment due, our professor decided that a
collaborative effort between Dusda and I in XNA would be appropriate.
Unfortunatly for us, we had never used it before since it just
released, so we have been pulling all nighters for the duration of the
week in order to complete the assignment while still studying enough
for the exams. We are almost complete, and the product will be kind of
fun. Nothing flashy as we didn't have the time, but I am sure this is
not the last time I develop in it. So today, it is presentations for an
AJAX, remoting, and COM+ services application that my team wrote, and Dusda and I will be finishing up Theta Wars.
Problem
I was working on a remoting project for an assignment and we came
across a problem in 2.0. As of 2.0 you cannot make cross-thread calls
to a windows forms control. This means that if you are doing an
asyncronous call, most likely, unless your polling the async result, it
will come back on a different thread and you cannot change a windows
form or the controls on it without coming back to the origonal thread.
This is fine if you are making all of your asyncronous calls on the
actual form (You just need to call the Invoke method), but if you are
seperating the asyncronous logic from the presentation layer (Which is
recommended), any results processed from that logic can be difficult to
update in windows forms. Fortunatly, there is a solution within the
AsyncOperation class. I recommend looking into this class if you are
doing anything thread related, but I created a wrapper around the class
to make it a bit easier to use. Hopefully, it will be as useful to you
as it was for me.
How it works
My wrapper simply operates the AsyncOperation class. When you
instantiate the object, you instantiate a copy of the AsyncOperation
class which will hold a reference to the initial thread you
instantiated it on. This means you can make cross-thread calls to it,
and it will execute the code on the origonal thread it was instantiated
on. So, if you instantiate this class within your dll's constructor,
any events or code that you execute that need to work on the windows
forms thread you just call in an anonymous delegate under the
Syncronize method.
Place this class somewhere in your project.
using System;
using System.ComponentModel;
using System.Threading;/// <summary>
/// Class that allows multithread syncronization
/// from asyncronous calls. Anything wrapped with
/// the syncronize method will be executed on the
/// same thread as where the AsyncSyncronizer
/// is instantiated.
/// </summary>
/// <example>
/// Instantiate on thread you want to use
/// AsyncSyncronizer sync = new AsyncSyncronizer();
///
/// // Run on the code you would like to execute.
/// this.sync.Syncronize(
/// delegate
/// {
/// /*Code to Execute*/
/// });
///</example>
public class AsyncSyncronizer
{
/// <summary>
/// Delegate pointing to code executed
/// within the Syncronize method.
/// </summary>
public delegate void AsyncDelegate();/// <summary>
/// Async operation which will push execution
/// to the proper thread.
/// </summary>
private AsyncOperation operation;/// <summary>
/// Creates an object of the AsyncSyncronizer
/// Everything wrapped within the Syncronize
/// method will be executed by default on the
/// thread this is instantiated on. In order to change
/// the thread, run SetThread.
/// </summary>
public AsyncSyncronizer()
{
// Set to this thread.
this.SetThread();
}/// <summary>
/// Sets the thread code will by syncronized to
/// to the current thread running.
/// </summary>
public void SetThread()
{
this.operation =
AsyncOperationManager.CreateOperation(null);
}/// <summary>
/// Runs code within this method on the
/// thread either set by set thread or
/// where the object was instantiated.
/// </summary>
/// <param name="render">The code
/// to execute on the specified thread.</param>
public void Syncronize(
AsyncDelegate render)
{
this.operation.Post(new SendOrPostCallback(delegate(object state)
{
render();
}), null);
this.operation.OperationCompleted();
}
}