IMAP: Downloading emails

Hello friends!

In yesterday's article, "Email: Protocols and Background", I explained how to set up an email client and server to study the email protocols, and also how to use Wireshark to observe how the clients and servers actually talk to each other using these protocols.

Today we'll begin learning IMAP, and use it to access our inbox and download emails.

As I explained in yesterday's article, IMAP is a protocol made up of text commands. You can open a socket (see "C# Network Programming: Simple HTTP Client"), send commands, and interpret the responses. Without needing to write any code, you can use the telnet program to open a raw connection and work using the command line. Connect to your hMailServer IMAP server using a command like this:

telnet serverIP 143

Obviously, replace serverIP with the actual IP address or hostname of the computer where hMailServer is installed. 143 is the port on which the IMAP server listens by default.

If telnet is not installed, you can install it on Windows 7 as follows. In the Start search box, find Programs and Features and open it. Select "Turn Windows features on or off" (it's a link on the left hand side). In the Windows Features window, tick the "Telnet Client" checkbox and click OK.

With telnet installed, connect to the IMAP server as described above. You should see the initial greeting from the hMailServer IMAP server:

* OK IMAPrev1

Now, type the following command and press ENTER:

01 capability

The response consists of a number of words that describe what functionality the IMAP server supports:

Next, login to the email account you created as part of yesterday's article. In my case the command looks like this:

02 login user@ranchtest.local pass

The response will tell you whether the login was successful or not.

In order to make this a little interesting, send a few emails to yourself via Thunderbird so you actually have something in your inbox. Next, access the inbox using the following command. The INBOX folder is standard in IMAP and always exists, even if you don't have anything in it.

03 select INBOX

You should be able to see a few things at this stage. First, whenever we send a command, we precede it with something like "01". This is called a tag, and can be any string (different clients use different formats ranging from numbers to random strings). When the server response to a command, the last line always starts with the same tag as the command - that way a client knows that the response for that command was received.

You'll probably also realise that telnet is a pain in the ass. If you make mistakes you can't backspace - that's because telnet sends everything you type, byte by byte. So each character is sent immediately and can't be undone. Last year I wrote a program called IMAPTalk which makes working with IMAP (and other protocols) much more convenient. Just download it and run it - no installation necessary. Just enter the hostname and connect:

If you turn on Auto-generate tags, you can actually leave out the tags and just type the commands - the tags will be filled in for you by IMAPTalk. If you repeat the commands we did above in IMAPTalk, it looks like this:

Better, no? If you look at the responses (in red), you'll notice there are a bunch of things I haven't explained yet. Don't worry about them just yet. The important thing you should take from the response to the SELECT command is this like:

* 3 EXISTS

That's telling us that there are 3 messages in the INBOX.

We can then retrieve them one by one using a FETCH command, while providing the message number:

04 fetch 1 BODY[]

The response is as follows:

You'll notice that there is a bunch of stuff in there, for such a short message. Part of it (the line starting with the * 1 FETCH) is IMAP, as are the last two lines. The stuff in between is the full email, known as the MIME. It consists of a header with a bunch of fields and values (you'll notice important stuff such as From, To, Date, etc), and after a double line break, the message itself. You can see this in Gmail by clicking on the arrow at the top-right of an opened email and clicking "Show original".

You can similarly retrieve the other messages in the inbox by replacing the 1 in the FETCH command with the message number. This is called the message sequence number, and can't be larger than the number of emails in the folder (in this case 3). If you provide a larger number you won't get an error, but you won't get any email data either.

So that's the easiest way to download emails manually using IMAP. We'll learn more about how messages are stored in IMAP folders, and more about the facilities offered by the IMAP protocol, in the coming articles. Come back again for more!

Email: Protocols and Background

Hullo!

You sure as hell know what email is, but do you know how it actually works? In today's article I'll talk about how it works, and how best to learn about it in detail.

One of my previous articles, "HTTP Requests in Wireshark", showed that the World Wide Web was based on a standard protocol, HTTP. Web browsers and web servers could talk to each other using this protocol.

It turns out that email is no different. Email clients (e.g. Outlook, Thunderbird, etc) and servers (e.g. Microsoft Exchange, hMailServer, etc) can talk to each other using three standard protocols: IMAP, POP and SMTP. SMTP is used for sending email, while IMAP and POP are used for retrieving email from a server. IMAP is more powerful and complex than POP; POP doesn't even support folders. Each of these protocols uses a set of text commands similar to stuff you might have used in the command line, except that in this case you do it over the network (you'll see how in a minute). The protocols also define ports on which servers should listen, e.g. IMAP uses ports 143 and 993 by default.

You could study these protocols by just reading their respective RFCs, but you can only really learn them properly by seeing them in action. To do this, you will need some software.

First, install a mail server. hMailServer is decent and free, so unless you have a better alternative, go with it. Ideally install this on another computer, otherwise you won't be able to capture requests in Wireshark if your client and server are on the same PC. While installing hMailServer, choose SQL Compact as storage (to keep it simple) and give it an admin password.

When you're done installing hMailServer, you need to create an account. Run hMailServer and enter the admin password to access the Administrator console:

Click on the Add domain... button and invent a domain name. By convention it should end in .local, since this isn't a real domain name. Click the Save button to save it.

Next, find the Accounts folder somewhere under the Domains node.

Click the Add... button. Enter a username and password and click Save to create your account. Notice how the domain is used as part of the email address, for example in my case the email address is user@ranchtest.local.

Great. Now, we need to test this account using an email client. Thunderbird is a popular choice and it's free, although there are many others you can use if you want. Install and run it. Skip the shit that appears upon running:

Press Alt to show the program menu, since Thunderbird seem to have fallen into the horrible practice of hiding it. From the Tools menu, click on Account Settings...:

From the drop-down list, select Add Mail Account...:

Enter your basic account credentials, and then click the Manual config button when it appears:

Now you need tell Thunderbird how to connect to your mail server. Under Server hostname, type the name or IP address of the computer where hMailServer is installed. Using the PC name is better since the IP address might change regularly. If you installed hMailServer on the same machine (not recommended, see above) you can use 127.0.0.1 or localhost as the Server hostname. Other than that, use port 143 for IMAP and port 25 for SMTP; no SSL and Normal password for Authentication. It should look like this:

Click the Re-test button to allow Thunderburd to test those settings. If all is ok, the Done button is enabled, click it to save the settings and create the account. When you do this, a warning appears:

It's a security warning because the client and server will talk to each other on an unencrypted channel. Since you're working on a local test environment, you don't have to worry about it. We actually want the messages to be unencrypted, so that we can capture them with Wireshark.

Finally, install Wireshark so that we can take a look at the email protocols. Set it up for capturing; I explained how to do this in my article "HTTP Requests in Wireshark". After starting the capture session, set the Filter to "imap".

Using Thunderbird, send an email to yourself:

The email is sent to the server via SMTP, and then downloaded to the client via IMAP. After a second you should see some activity in Wireshark. From Thunderbird, click Get Mail to retrieve the new email in your inbox.

In Wireshark, you can see the IMAP commands as well as the email data. You can view this conveniently by right clicking on one of the packets and selecting Follow TCP Stream:

This might seem a bit cryptic, but it's quite easy to learn. In future articles I'll cover the email protocols bit by bit. So check back later for more about email technology! :)

C# OOP: Encapsulation and Properties

Hi everyone!

Some recent articles have discussed different aspects of Object Oriented Programming. Today we'll talk about controlling access to members (variables or methods) of our classes.

Let's begin with a scenario. We have an accounting program that keeps track of a person's money. First, we need to use the following library:

using System.Collections.Generic;

Then we declare a Transaction class to contain the details of each transaction (deposits, withdrawals... basically anything that affects the amount of money in the account):

    class Transaction
    {
        public DateTime date;
        public String detail;
        public float amount;
       
        public Transaction(DateTime date, String detail, float amount)
        {
            this.date = date;
            this.detail = detail;
            this.amount = amount;
        }
    }

We also need an Account class to keep the overall account information, as well as a list of all the transactions in the account:

    class Account
    {
        public String name;
        public float balance;
        public List<Transaction> transactions;
       
        public Account(String name)
        {
            this.name = name;
            this.balance = 0.0f;
            this.transactions = new List<Transaction>();
        }
       
        public void Show()
        {
            Console.WriteLine("Account for {0}", name);
            Console.WriteLine();
           
            foreach (Transaction transaction in transactions)
            {
                Console.WriteLine("{0:yyyy-MM-dd}  {1, -30}  {2}",
                        transaction.date, transaction.detail, transaction.amount.ToString("0.00").PadLeft(8, ' '));
            }
           
            Console.WriteLine();
            Console.WriteLine("Balance: {0:0.00}", this.balance);
        }
    }

We can now see how this works with some sample code in Main():

            Console.Title = "C# Encapsulation with Accounting";
           
            Transaction trans1 = new Transaction(new DateTime(2013, 08, 07), "Deposit: My first salary", 20.0f);
            Transaction trans2 = new Transaction(new DateTime(2013, 08, 08), "Withdrawal... need cash", -15.0f);
            Transaction trans3 = new Transaction(new DateTime(2013, 08, 09), "Deposit: Birthday present", 10.0f);
           
            Account account = new Account("Bill Gates");
           
            account.transactions.Add(trans1);
            account.balance += trans1.amount;
            account.transactions.Add(trans2);
            account.balance += trans2.amount;
            account.transactions.Add(trans3);
            account.balance += trans3.amount;

            account.Show();
           
            Console.ReadKey(true);

So here we've created an account for Bill Gates and added three transactions. The Show() method gives us a picture of the account status and history:

That's great. But what if the guy writing the code in Main() forgets to update the account balance? The sum of the transactions won't agree with the value in the balance member variable. We could provide a method to take care of this in Account:

        public void AddTransaction(Transaction transaction)
        {
            transactions.Add(transaction);
            this.balance += transaction.amount;
        }

...and while this is certainly useful, it doesn't really solve the problem. Because while a programmer might use this method, there is nothing to keep him from updating transactions and balance separately, the old way, as illustrated earlier. Even worse, someone might actually tamper with them, potentially removing transactions or modifying the balance into something different.

The one thing we've been doing wrong all along is declaring all member variables and methods in our classes as public. When they're public, it means anyone can touch them. We can restrict access to members by using a protected or private access modifier instead of public (there are others, but they're not important at this stage).

Once we switch the member variables in the Account class to private:

        private String name;
        private float balance;
        private List<Transaction> transactions;

...then the program won't compile:

That's because we're accessing these private member variables directly from within Main(). When a variable is private, it means that only code within the same class can access it. So it's ok for the AddTransaction() method we added earlier to use the transactions member variable, but the code in Main() can't. Instead, the code in Main() must be refactored to use AddTransaction():

            account.AddTransaction(trans1);
            account.AddTransaction(trans2);
            account.AddTransaction(trans3);

With this change, it compiles just as well. So we've just seen how we can prevent users of a class from tampering with its internal state, and yet still do useful stuff with it via the methods it does expose as public. This is called encapsulation, and it effectively means "data hiding". In OOP it is usually the case that our classes provide a public interface by which other objects can use them, but they hide all the rest from public view.

Naturally, it is often the case that other objects want to access member variables for legitimate reasons. In that case, instead of making the member variable public, we add methods allowing access to them:

        public String GetName()
        {
            return this.name;
        }
       
        public void SetName(String value)
        {
            this.name = value;
        }
       
        public float GetBalance()
        {
            return this.balance;
        }

These are called getter and setter methods, because they allow you to retrieve and modify the variable. A setter can be omitted (as with the balance variable) if that variable is meant to be read-only.

Although using getter and setter methods is a great way of using encapsulation in any OOP language, C# provides the use of properties, which do the same thing but are arguably more elegant:

        public String Name
        {
            get
            {
                return this.name;
            }
            set
            {
                this.name = value;
            }
        }
       
        public float Balance
        {
            get
            {
                return this.balance;
            }
        }

Properties are actually converted to getter and setter methods during compilation, but this process is transparent to you (the programmer). Using them in code is pretty easy:

Console.WriteLine("{0} has {1} Euros in his account.", account.Name, account.Balance);

Right, so what about the protected access modifier? It's like private, but also allows subclasses to access a class's members. You should use it sparingly, or not at all. Scott Meyers explains why in his excellent book "Effective C++: 55 Specific Ways to Improve Your Programs and Designs". When you make something public, there are potentially infinitely many places from where it can be accessed and modified. So if you decide to change that variable (e.g. remove it and replace it with a computation), you have to refactor all those places. If something is protected, it can be accessed from any subclass, so there are still porentially infinitely many places from where it can be modified. If you want a subclass to access a variable, your best bet is to encapsulate it using a getter/setter pair or a property, and have the subclass access that.

To see this idea in action, let's remove the Account class's balance variable and replace it with a sum of the transaction amounts:

         public float Balance
        {
            get
            {
                float bal = 0.0f;
               
                foreach (Transaction transaction in this.transactions)
                {
                    bal += transaction.amount;
                }
               
                return bal;
            }
        }

So like this, any other classes accessing the Balance property may continue to do so without needing to refactor anything. In our case we only need to make some small changes in the Account class itself (no need to maintain a separate balance variable any more in the constructor and in AddTransaction(), and use the property instead of the variable in Show()). But if we had to refactor a hundred other classes to remove the balance variable, it would have been a very expensive change.

Cool. So in this article we learned why we should hide certain internal class data from outside code that might tamper with it - a practice called encapsulation. Encapsulation is so important that, together with inheritance and polymorphism, it is known as one of the Three Pillars of OOP. We also learned about access modifiers (public, protected, private), getter/setter methods, as well as properties - something unique to C#.

From these OOP articles you might begin to see what OOP is really about: the complex relationships between objects make designing OOP software quite a challenge. It's also quite fun. :)

I hope you enjoyed this article, and check back for more! :)

C: Hello World on Linux

Hello people!

Today I'm going to describe how you go about writing, compiling and executing C code using the Linux command line (also known as shell or terminal).

You will first need to make sure you have the tools necessary to compile C code. In particular you need gcc. You can get it by installing the build-essential package. On a Debian-based Linux distribution such as Ubuntu, you'd use the following command in the terminal:

sudo apt-get install build-essential

...and then, after entering the root password (if necessary), you proceed with the installation:

To actually write the C code, you can use the vi editor. Even better, you can make sure that you have the vim (vi improved) by using the following command:

sudo apt-get install vim

Then use the following command to edit a file called hello.c (it doesn't need to exist yet):

vi hello.c

This opens the vi editor. vi is very powerful but takes a little getting used to. You start off in command mode, and just about any letter you type has a particular meaning. If you press the 'I' key, you go into insert mode, and can type code to your heart's content. Do that, and enter the following code:

#include <stdio.h>

int main(int argc, char ** argv)
{
    printf("Hello world!\n");

    return 0;
}

Over here we're first including the stdio.h library, which allows us to do input/output (I/O) such as outputting text to the terminal. The actual code goes into the main() function, which returns an integer. You can ignore the argc and argv bits, and just use this as a template for your code, for the time being. We actually write something to the terminal using the printf() function. The only thing that might seem a little special here is the \n thing - it's an escape sequence that outputs a newline.

Once you're done typing the above, press ESC in vi to go back to command mode. Then type :wq and press enter - this saves the file (w) and quits (q).

Back in the terminal, type the following command to compile the code in hello.c:

gcc hello.c -o hello

The -o part means that the next argument (in this case "hello") is the name of the executable to be produced by gcc. On Linux, executables don't need to have extensions such as .exe, although it's perfectly fine to include them to make it easier to recognise them.

Finally, type ./hello and press ENTER to run the program. You should see "Hello world!" as the output, as above.

Note: just in case you can't run the program because of some permissions, try the following command:

chmod 777 hello

Great! This simple tutorial showed how to write C code using the vi editor, compile it using the gcc program, and execute it from within a Linux shell. Come back for more tutorials!

Unity3D: Changing game speed and pausing

Hi!

Today's article is a little break from the OOP tutorials. Instead, we revisit the Unity3D game development engine (at the time of writing, version 4.2 was recently released) and learn about controlling time. This allows us to easily pause the game, slow it down, or speed it up.

Create a new project and add a sphere to your scene via GameObject menu -> Create Other -> Sphere. Next, create a new C# script by right clicking in the Project panel, and selecting Create -> C# Script. Name it Ball, and drag it onto your Sphere in the Hierarchy panel. Double-click the script to open it in MonoDevelop.

We're going to make a very basic bouncing ball just to be able to see the effects of our change in speed. Start off with the following code for the Ball script:

public class Ball : MonoBehaviour
{
    private Vector3 velocity;
   
    // Use this for initialization
    void Start ()
    {
        this.velocity = new Vector3(1.0f, 1.0f, 0.0f);
    }
   
    // Update is called once per frame
    void Update ()
    {
        this.transform.position += this.velocity * Time.deltaTime;
       
        if (this.transform.position.x > 5.0f)
            velocity.x = -velocity.x;
        else if (this.transform.position.x < -5.0f)
            velocity.x = -velocity.x;
        else if (this.transform.position.y > 6.0f)
            velocity.y = -velocity.y;
        else if (this.transform.position.y < -5.0f)
            velocity.y = -velocity.y;
    }
}

This will make the ball bounce when it reaches the sides of the screen. This may vary depending on your monitor so use whichever values work best.

We've used Time.deltaTime before. Games look interactive because they generate a certain number of images (frames) per second, usually something between 30 and 60. Time.deltaTime is the time between one frame and the next; multiplying this by the velocity makes the ball move pretty uniformly.

Another important property of the Time class is Time.timeScale. This is a measure of how quickly scripts and animations run, and is set to 1.0f by default. We can change this to make the game run at different speeds. To try it out, add the following code to the Ball script's Update() method:

        if (Input.GetKeyDown(KeyCode.P))
            Time.timeScale = 0.0f;
        else if (Input.GetKeyDown(KeyCode.N))
            Time.timeScale = 1.0f;
        else if (Input.GetKeyDown(KeyCode.F))
            Time.timeScale = 2.0f;
        else if (Input.GetKeyDown(KeyCode.S))
            Time.timeScale = 0.5f;

What we're doing here is:

• If the player presses 'P' (pause), we set the time scale to zero, effectively stopping any movement in the game.
• If the player presses 'N' (normal speed), we set the time scale to the default of 1.0f.
• If the player presses 'F' (fast), we set the time scale to double the normal speed.
• If the player presses 'S' (slow), we set the time scale to half the normal speed.

This simple property allows you to not only pause the game, but also to play the game at different speeds. Several games including Starcraft and Warcraft 2 have settings that allow you to tweak the game speed in order to make it more challenging or less frenetic.

This article showed how a single line of code in Unity3D is enough to change the speed of a game or pause it. Although this was a very easy tutorial, I hope you will also find it very useful in any games you make!

C# OOP: Abstract classes, fruit, and polymorphism

Hello people from around the world!

The previous article, C# OOP: Queues and Stacks with Inheritance, introduced inheritance and showed that it can help you to reuse methods and variables within one class in another class that derives from it. As I explained in that article, when we say "Queue is a List", we mean it in the sense of "Dog is a mammal".

In practice, inheritance relationships can be a little more elaborate than that. Let's take a classic OOP example - shapes:

So we have a Shape, that is the parent to everything else. It defines a GetArea() method which is expected to be defined in each subclass. The area of a square is calculated based on its length, and that of a circle is calculated based on its radius, each area calculation is specific to that particular shape.

Also, we define a rectangle as a special case of a square. That might sound counterintuitive, but in OOP it makes sense. This is because a rectangle requires more specific attributes than a square (i.e. the width). If we did it the other way round, Square would inherit a width attribute that it doesn't really need.

Anyway, as you can see, it doesn't make any sense for you to have an instance of Shape. You can have an instance of Square, or Circle, or Rectangle, and calculate their area. But how would you calculate the area of a Shape? You can't, because a Shape does not exist.

Let me give you a different example: fruit. You have probably seen apples, oranges, bananas, and many other fruit. But have you ever seen something that is a generic fruit? Things like fruit and shapes are called abstract classes: they give you a general idea of what you can do with them, but they can only be subclassed. They cannot be instantiated.

Let's see a fruity example in action. Start a new SharpDevelop C# console application, and start off with the following class:

    abstract class Fruit
    {
        public String name;
        public abstract void Eat();
    }

Our Fruit has a name, which may be used directly by subclasses. It also declares a method called Eat(), which is abstract. An abstract method is intended to be implemented by subclasses (much like GetArea() in the Shape example), and does not contain any implementation. Abstract methods must be defined in abstract classes, such as Fruit. When a class is abstract, it cannot be instantiated, so trying something like this:

Fruit fruit = new Fruit();

...would cause a compile-time error:

Now, let's add some subclasses to spice things up:

    class Apple : Fruit
    {
        public Apple(String name)
        {
            this.name = name;
        }
       
        public override void Eat()
        {
            Console.WriteLine("You eat the {0}. Crunch crunch.", this.name);
        }
       
        public void Throw(String target)
        {
            Console.WriteLine("You throw the {0} at the {1}", this.name, target);
        }
    }
   
    class Orange : Fruit
    {
        public Orange(String name)
        {
            this.name = name;
        }
       
        public override void Eat()
        {
            Console.WriteLine("You eat the {0}. Squish squish.", this.name);
        }
       
        public void Squeeze()
        {
            Console.WriteLine("You squeeze the juicy orange into a cup.");
        }
    }

Each subclass conveniently has a constructor that sets the name variable inherited from the parent (Fruit). Each subclass also implements the Eat() method in its own way. The subclasses must provide an implementation for abstract methods they inherit (a compile-time error occurs if you don't). Finally, the Orange and Apple class each implement a method specific to them: Apple has a Throw() method, and Orange has a Squeeze() method. Note: If you're thinking that oranges can also be thrown, Aladdin would disagree:

You can now create instances of Apple or orange and use them as you like:

            Apple apple = new Apple("green apple");
            apple.Eat();
            apple.Throw("guard");

This gives you the following output:

An Apple is always a Fruit. Although you can't instantiate Fruit directly, you can use an Apple as a Fruit:

Fruit appleFruit = new Apple("green apple");

Since Eat() is originally declared in Fruit, you can call it on a Fruit variable without issues:

appleFruit.Eat();

You can't, however, call Throw() from a Fruit because Throw() is declared in Apple, not in Fruit. Doing this:

apple.Throw("guard");

...results in a compile-time error.

The ability to treat different types of Fruit (Apple, Orange) as if they were Fruit allows you to work with them (using the methods and variables provided by Fruit) without needing to know what subclass they are underneath:

            Fruit appleFruit = new Apple("green apple");
            Fruit redAppleFruit = new Apple("red apple");
            Fruit orangeFruit = new Orange("fresh orange");
           
            List<Fruit> myFruit = new List<Fruit>();
            myFruit.Add(appleFruit);
            myFruit.Add(redAppleFruit);
            myFruit.Add(orangeFruit);
           
            foreach (Fruit fruit in myFruit)
                fruit.Eat();

The resulting output is:

This approach is called Polymorphism, and as you can see, it has nothing to do with turning orcs into critters:

A practical example where I've used this is when making games using XNA. You can have many different DrawableGameComponents, each of which may implement its own Draw() method. You can then loop through all your game images (similar to what we did with Fruit) and call Draw() on each of them to draw them on the screen.

Fantastic. In this article we learned about abstract methods, abstract classes, and how to use them polymorphically. An abstract method is a method declaration, without the implementation, that must be implemented in subclasses. Abstract methods are declared in abstract classes, which cannot be instantiated. However, variables of an abstract class type may be used by assigning a subclass. Polymorphism is when we use members of the parent class so that we don't need to distinguish between different subclasses - instead we use the common functionality provided by the parent class.

We've covered quite a bit of ground in OOP, but there is still a lot more to learn: interfaces, overriding, overloading, and, most importantly, encapsulation. Future articles will touch upon these topics as well.

C# OOP: Queues and Stacks with Inheritance

Hi everyone! :)

In yesterday's article ("C# OOP: Creating a List using Composition") we used classes to create a List data structure. Today we're going to create a queue and a stack using the same principle.

The above diagram shows what a queue looks like in theory. (When I first drew this diagram, I made the mistake of putting the orange labels at the bottom. If you think about it for a minute, you'll realise why it's a horribly wrong thing to do.) There are a number of people in the queue, and they all get served one by one by the dude at the desk. Unless you're in Malta, the guy at the back typically doesn't get served before the guy at the front.

A queue is pretty much a special kind of list. It has the internal structure of a list, but supports two operations: Enqueue and Dequeue. Enqueue means adding an item to the end of the queue, while Dequeue means removing the item at the front of the queue and doing something with it.

We can start off with yesterday's code for the List:

    class ListItem
    {
        public ListItem Next;
        public String Data;
       
        public ListItem(String data)
        {
            this.Next = null;
            this.Data = data;
        }
    }
   
    class List
    {
        public ListItem Head;
        public ListItem Tail;
       
        public List()
        {
            this.Head = null;
            this.Tail = null;
        }
       
        public void Add(String data)
        {
            ListItem item = new ListItem(data);
           
            if (this.Head == null) // list is empty
            {
                this.Head = item;
                this.Tail = item;
            }
            else
            {
                // set (old) tail's Next to new item
                this.Tail.Next = item;
                // new item is the new tail
                this.Tail = item;
            }
        }
    }

Since a queue is so similar to a list, there isn't much point in simply rewriting lots of code to create the queue. As much as possible, we should reuse code. This is called the Don't Repeat Yourself (DRY) principle.

Let's start the queue based on this code:

    class Queue : List
    {
       
    }

This means that Queue is a List. This is just like saying Dog is a mammal: the dog inherits the characteristics of a mammal (it has fur, doesn't lay eggs, etc) and perhaps adds some particular characteristics of its own (barks, wags tail, drools, etc). In OOP, this actually means that the Queue inherits the data members and methods of the List. So in our Main() method, we can already use the Queue as if it were a List:

        public static void Main(string[] args)
        {
            Console.Title = "C# OOP Inheritance";
           
            Queue queue = new Queue();
            queue.Add("Bill Clinton");
            Console.WriteLine(queue.Head.Data);
           
            Console.ReadLine();
        }

In Queue, we can add the Enqueue() and Dequeue() methods that are queue-specific and don't belong in the List:

    class Queue : List
    {
        public void Enqueue(String data)
        {
            this.Add(data);
        }
       
        public String Dequeue()
        {
            if (this.Head == null)
            {
                return null;
            }
            else
            {
                // keep reference to the first guy in the queue
                String oldHead = this.Head.Data;
               
                // set head to the second guy in the queue
                this.Head = this.Head.Next;
               
                // return the guy who was first, for consumption
                return oldHead;
            }
        }
    }

For Enqueue(), we use the Add() method inherited from List, since it adds items to the end of the list and is enough to achieve what we need for Enqueue(). In Dequeue(), we return the first item in the queue, and the second item takes its place.

In Main(), we can try this out:

            Queue queue = new Queue();
            queue.Enqueue("Bill Clinton");
            queue.Enqueue("Paris Hilton");
            queue.Enqueue("Chuck Norris");
           
            String item = String.Empty;
            while (item != null)
            {
                item = queue.Dequeue();
                Console.WriteLine(item);
            }
           
            Console.ReadLine();

...and the result is...

That's great, but the extent of reusability of the List doesn't end here. Let's also create a Stack.

A stack is just what the name suggests: a bunch of things on top of each other. Books and Pringles make really good examples of stacks. You add things to the top of the stack, and remove them from the top. You can't remove items from the bottom of a stack without making a mess.

The stack supports two operations: Push (add item to top of stack) and Pop (remove item from top of stack - think Pringles). Again, we can inherit from the List and implement this particular functionality:

    class Stack : List
    {
        public void Push(String data)
        {
            this.Add(data);
        }
       
        public String Pop()
        {
            String data = null;
           
            if (this.Head == null) // stack is empty
            {
                data = null;
            }
            else if (this.Head.Next == null) // stack has just one item
            {
                data = this.Head.Data;
                this.Head = null;
                this.Tail = null;
            }
            else // stack has at least two items
            {
                ListItem currentItem = this.Head;
               
                while (currentItem.Next != this.Tail)
                    currentItem = currentItem.Next;
               
                data = this.Tail.Data;
                currentItem.Next = null;
                this.Tail = currentItem;
            }
           
            return data;
        }
    }

Uhhh... Pop() is a little more complicated than Dequeue() because we need to first navigate to the item before the tail, and we have to do that from the head since the Tail doesn't have any backwards pointers. We could make this more efficient by using a doubly linked list instead, but that's beside the point.

We can now test the Stack:

            Stack stack = new Stack();
            stack.Add("One");
            stack.Add("Two");
            stack.Add("Three");
            stack.Add("Four");
           
            String item = String.Empty;
            while (item != null)
            {
                item = stack.Pop();
                Console.WriteLine(item);
            }
           
            Console.ReadLine();

...which results in...

You'll notice that the output is in reverse order compared to how we added the items. That's because a stack is a Last In First Out (LIFO) data structure, while a queue is First In First Out (FIFO).

Fantastic. In this article we used inheritance to reuse functionality in the List and write specialised code for Queues and Stacks without duplicating code. Effectively we ended up with the following inheritance tree:

Queue and Stack are both Lists in the same way that Dogs and Cats are both Mammals. A better way of saying this is that Queue and Stack extend List (in fact Java uses the extends keyword instead of the colon operator used by C# and C++).

It is also important to know that in C#, all classes implicitly extend the Object class, which provides some methods such as ToString() and GetHashCode() to all classes. We'll learn more about these in the coming articles.

That's all for today... come back for the next article! :)