joi, 29 noiembrie 2007

Headache Installing Visual Studio 2008

Last night I've tried to install Visual Studio ‚Orcas' RTM, but the setup kept crashing at the fisrt step of the installation (installation of the 3.5 framework). Digging into the setup log files I've traced the problem to the installation of the 3.0 framework SP1. After some trials and misses (I've even uninstalled the MacAfee antivirus), I've downloaded the framework 3.5 setup redistributable (the full install package). The setup went flawlessly, and after it ended I was able to install the new Visual Studio.

I hope this information will help someone in need.

Stumble Upon Toolbar

miercuri, 28 noiembrie 2007

Implementing a Double Linked List in C# - part II

In the previous post we've discussed the domain and the requirements of an implementation of a double linked list. It is now time descend the ladder of abstraction to the level where we can construct an usable artifact.

We'll start by analyzing the domain description and requirements, as we try to synthesize some sort of blueprint for the implementation. Right from the beginning we discover our two main entities: the list, and the nodes. It's pretty obvious we'll have different classes for each of them. Let's begin with the nodes.

The node has two major concerns: it has to hold data, and it has to retain references to it's left and right neighbors. As we've decided that any data can be stored into our list, and presuming the users of the list are kind enough to group multiple fields of data into types, we can make our nodes generic. Anything else is not important at this time.

On the other hand, the list has a bit more concerns. First of all, it has to hold some reference to the data. This is done by the means of the two sentinels. When a list is created, the sentinels hold a reference with each other. As nodes are inserted the references are changed, in such a way as to form a chain o references starting form the left sentinel, and ending with the right sentinel.

The list also has to know the number of nodes stored in the list (excluding the sentinels). We have to do this, without counting the nodes every time this value will be needed. This implies that we must control the process of altering the structure of the list in order to keep an updated count of its elements.

The main source of errors, as far as we are concerned at the moment, are boundary crossings. This can be easily solved by checking the value of received indexes, and throwing the appropriate exceptions.

As we have decided that the list must behave as a collection, it is time to decide on an interface that we'll implement, in order to provide the users of the list with a familiar experience. Searching the MSDN documentation, the IList<T> springs into attention, as it covers most of our needs. Actually, all the necessary functionality of the list will come from implementing this interface. Any other added functionality will only have the purpose of easing the use of the list.

At this moment we can start sketching the implementation of the list. Take note that the comments and documentation were removed for the sake of brevity.

The Node class is short and self explanatory:
public class Node<T>
public T Data;
public Node<T> Previous;
public Node<T> Next;

Next we start constructing the list:

public class DoubleLinkedList<T> : IList<T>
private int count;
private readonly Node<T> leftSentinel;
private readonly Node<T> rightSentinel;

The sentinels and node count will be initialized in the constructor. Remember that the list starts with the two sentinels referencing each other:

public DoubleLinkedList()
leftSentinel = new Node<T>();

rightSentinel = new Node<T>();

leftSentinel.Next = rightSentinel;
rightSentinel.Previous = leftSentinel;

count = 0;

The insert algorithm works in the following steps:

  • Check boundaries.
  • Search the n'th node. If there are no nodes, or the specified index is next to the last existing node, return the right sentinel.
  • Insert the new value into a new node between the node found above, and its left neighbor.
  • Increment the node count.

We will separate the last two steps of the algorithm into a helper method, AddBefore, as we will use them in another insert method, which will add an item directly at the end of the list.

private void AddBefore(Node <T> node, T item)
Node<T> newNode = new
newNode.Next = node;
newNode.Previous = newNode.Previous;
newNode.Data = item;
node.Previous.Next = newNode;
node.Previous = newNode;

The search method can be reused in some other cases(item retrieval and removal), so we'll move the boundary check inside it:

private Node<T> Find(int index)
if (index < 0 || index >= count)
throw new ArgumentOutOfRangeException("index");

Node<T> currentNode = rightSentinel.Next;

while (index > 0)
currentNode = currentNode.Next;

return currentNode;

Now we can finish the implementation of the two insert methods:

public void Insert(int index, T item)
Node<T> nextNode = index == count ?
rightSentinel : Find(index);
AddBefore(nextNode, item);

public void Add(T item)
AddBefore(rightSentinel, item);

Unfortunately, it seems that the posts in this series are getting longer than expected, so I'll have continue the implementation on the next episode.

P.S.: As I've mentioned in the first post, additional requirements will be specified en route:

  • thread safety;

  • serialization;

  • performance;

  • implement the filter, map and reduce algorithms.

Stumble Upon Toolbar

marți, 27 noiembrie 2007

First post: Implementing a Double Linked List in C# - part I

Hello World!

The first blog post is dedicated to a basic, but important data structure: the double linked list. It is intended to be an academic exercise, rather than a practical one.

Acknowledgement: I'm not a native English speaker, and despite Word's spell & grammar checker, please indulge my language faults. Still, constructive criticism is appreciated!

I've separated the plan of this project into 3 parts: the description of the domain of the problem at hand, definition of the requirements and, finally, the design. The article will be separated into two parts, leaving the design into the second part. A third, bonus, part might be included into the series.

First let's describe the DOMAIN of the problem

Wikipedia comes to our help with a definition of a double linked list (approx.): the (double) linked list is a data structure. It consists of a sequence of nodes, each containing arbitrary data fields and two references, to the next and previous nodes.

Some implementations provide two special nodes, called sentinels. These nodes are placed at the beginning and end of the list, and do not contain any data. Their purpose is to provide a uniform way of treating the insertion and removal of standard nodes.

The main purpose of the linked lists is to be a base for other data structures, like stacks and queues. The main benefit over conventional arrays is that they support the insertion and removal of elements, without creating a new instance of the structure. The advantage of the double linked list over other linked lists is that they can be traversed backwards as well as forwards.

In the .Net world, support for sequential data structures, besides arrays, is provided through collections. Collections are defined by a set of interfaces, which provide a uniform set of patterns for manipulating collections, and the concrete implementations of several types of collections: lists, dictionaries, hash tables and so on.

Another feature of the .Net framework, available from the v2.0 version, is generics. They enable the user to generalize the definition of types, by leaving a part of the implementation of the type to be provided when the type will be consumed. This will enable the list to contain any type of data, as long as it is of the same type (of course, a collection of object objects will hold any data, but that's not the point).

REQUIREMENTS prescription

The requirements for our double linked list represent what is expected from it. They fall into two categories, what is expected from a double linked list, and what is expected from a collection. The two categories are overlapping. The list of requirements is by no means exhaustive, and might be improved in the course of the implementation.

A double linked list should:
  • Provide storage for data into nodes.
  • Permit the insertion of new node(s) when the list is empty as well as when the list has existing items.
  • Permit the removal of a specified item.
  • Return the number of existing nodes.
  • Return a specific node.
  • Provide a consistent mechanism for dealing with errors.
  • Provide the next and previous nodes for a given node.

A collection should:

  • Provide for data into items.
  • Permit the addition of new item(s).
  • Permit the removal of item(s).
  • Iterate over its values.
  • Permit the retrieval of a specified item.
  • Permit the alteration of the order of its item (ex. Sorting).

This ends the first two parts of our plan. Next time we will see how we can get from a list o requirements to an usable artifact.

Stumble Upon Toolbar