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! :)

C# OOP: Creating a List using Composition

Greetings, and welcome to this new article at Programmer's Ranch!

I will be using this article and the next few to introduce you to Object Oriented Programming (OOP). In the articles so far, we've mostly put all the code in the Main() method. That might work for small programs, but as things get more complex, it's useful to model them as different components, or objects, that together make up something bigger. Think of a car - it's made up of the engine, steering wheel, and many other parts.

The .NET collections, of which we have seen a few, are a good example of the relationships between objects in OOP. Although .NET provides its own List class (see "C# Basics: Snake Game in ASCII Art (Part 2)"), in this article we will implement a list of our own and use it to learn OOP.

There are many different ways to implement a list; below is one of them:

The various items in the list are the purple boxes. Each item, apart from storing some kind of data (in this case a letter), keeps a reference to the next item in the list (the last one points to null).

For convenience, we also keep a reference to the first and last items in the list. This helps us when we need to process the list. For example, we could have used just a Head and left out the Tail, but then we'd have to go through the whole list sequentially if we had to use the last item in the list.

The above diagram shows what is actually in a list item. As I mentioned earlier, all we need is a Next reference pointing to the next item in the list, and the actual Data we are storing in the list item.

This design is enough to create the list. Create a new SharpDevelop console application, and start by adding a ListItem class. In this simple example you can add classes directly in Program.cs, but for more complex scenarios it's convenient to have classes in their own file (right click on project, Add -> New Item..., select Class and give it a name).

    class ListItem
    {
        public ListItem Next;
        public String Data;
       
        public ListItem(String data)
        {
            this.Next = null;
            this.Data = data;
        }
    }

The ListItem contains a reference to the next item in the list, and the actual data stored in the list item (as I said earlier). I am also using a constructor to initialise Next to null, and set Data to whatever value is provided.

The actual list itself is just as straightforward to create:

    class List
    {
        public ListItem Head;
        public ListItem Tail;
       
        public List()
        {
            this.Head = null;
            this.Tail = null;
        }
    }

The list contains a Head (first item) and a Tail (last item). Any items between them can be reached by following Next references from the head. In the List constructor, we initialise both Head and Tail to null since the list is empty.

We can now add some methods to the List to help us work with it. In particular we want to allow items to be added to the end of the list:

        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;
            }
        }

If the list is empty, we set both head and tail to the new item, since it is the only item in the list. Otherwise, the item is added to the end of the list. This means that item that was last becomes the one before the last, and the tail must be updated. Note that I could have simplified the code by taking this.Tail = item; out of the conditional, but I thought it's clearer for human consumption this way.

Let's also add a method that shows the contents of the list, so that we can check our work:

        public void Show()
        {
            ListItem currentItem = this.Head;
           
            while (currentItem != null)
            {
                Console.WriteLine(currentItem.Data);
                currentItem = currentItem.Next;
            }
        }

All we're doing here is starting at the head and visiting the items one by one. For each item, we write its data to the console, and then move to the next item until we hit a null (which would be at the tail).

In Main(), we can now write code to use our list:

        public static void Main(string[] args)
        {
            Console.Title = "C# OOP Composition using Lists";
           
            List shoppingList = new List();
           
            shoppingList.Add("sausages");
            shoppingList.Add("beans");
            shoppingList.Add("jam");
            shoppingList.Add("water");
           
            shoppingList.Show();
           
            Console.ReadLine();
        }

...and voilà:

Awesome. This article probably felt like an exercise in data structure design, and in a way that's true. However, we have used something called composition to create our list data structure. Our list contains ListItem data members. Another way to see it is that the list is made up (composed) of those ListItems.

Composition is probably the most basic part of working with OOP. Complex software is full of objects that contain other objects, and that's pretty intuitive, because so is the world.

The real challenge in designing complex systems using OOP (which is the part that most people get wrong) is getting the relationships between objects right. There are many other ways for objects to interact other than composition, and we will take a look at them in the coming articles.

C#: Value Types vs Reference Types

Hi all! :)

I'll be writing a few articles about Object Oriented Programming (OOP), but before I do that, there's something I need to explain. In this article, I will be discussing the difference between value types and reference types, as well as the use of the ref keyword.

Let us first create a new console application using SharpDevelop (or Visual Studio, if you prefer). In this application, we declare a struct that represents a monster in a game (if you don't remember structs, look back at "C# Basics: Snake Game in ASCII Art (Part 1)"):

    struct Monster
    {
        public string name;
        public int health;
    };

This struct goes under the namespace, at the same level as class Program. We can now make instances of Monster in the Main() method:

            Monster wolf = new Monster();
            wolf.name = "Rex";
            wolf.health = 100;
           
            Monster steve = new Monster();
            steve.name = "Steve Ballmer";
            steve.health = 10;

Next, we define a couple of methods that work on a monster and modify its attributes:

        public static void RenameMonster(Monster monster, String newName)
        {
            monster.name = newName;
        }
       
        public static void HurtMonster(Monster monster, int damage)
        {
            monster.health -= damage;
        }

In Main(), we can test this:

            Console.WriteLine("Monster's name before: {0}", wolf.name);
            RenameMonster(wolf, "Wolverine");
            Console.WriteLine("Monster's name after: {0}", wolf.name);
           
            Console.WriteLine("Monster's health before: {0}", wolf.health);
            HurtMonster(wolf, 5);
            Console.WriteLine("Monster's health after: {0}", wolf.health);
           
            Console.ReadLine();

The output, however, is not quite what we were expecting:

If we change the Monster from a struct to a class and re-run the program, on the other hand, it works correctly:

So, what exactly is happening here? A struct is an example of a value type. When you pass it as a parameter to a function, a copy of it is actually passed to the function. If you modify it within that function, you are actually modifying the copy. When the function returns, the struct still has its old values.

A class, on the other hand, is a reference type. When you pass an instance of a class (i.e. an object) as a parameter to a function, the object itself is passed. You can make changes to the class's members and they are retained even after the function returns.

Most simple data types (such as integers, floats, etc), as well as structs and enumerations, are value types. Classes and strings are reference types, although a string behaves pretty much like a value type when passed to a function (see an explanation on Stack Overflow, if you're interested).

[Sidenote for purists: in C#, functions are actually called "methods". I consider the term "method" to be more of an OOP thing, and what we're doing here isn't quite OOP.]

It is, however, possible to pass a value type by reference. Let's say you have this function:

        public static void Increment(int x)
        {
            x++;
        }

If we try to call this function on a variable as it is, we're back to square one:

However, we can use the ref keyword to mark parameters that we want to pass by reference:

        public static void Increment(ref int x)
        {
            x++;
        }

...and do the same in the calling code:

            Increment(ref x);

This gives the result we want:

Wonderful. The bottom line is that structs and classes are very similar, but there are a few subtle differences (such as value type vs reference type, stack allocation vs heap allocation, etc) that can affect the way your code works. The differences are particularly clear if you know what pointers are. We will be using classes a lot for Object Oriented Programming (OOP), so it's important to know a little bit about them.

In the next article, we will dive straight into OOP! :)

Indexing and Search (C#)

Hello once again, and welcome to this new article at Programmer's Ranch! :)

Today we're going to talking about indexing and search: what is it that allows you to search through thousands of documents in less than a second?

In order to understand how indexing works, we will use an example where we have the following three documents:

        doc1.txt contains:
        The Three Little Pigs

        doc2.txt contains:
        The Little Red Riding Hood

        doc3.txt contains:
        Beauty And The Beast

Now, let's say you want to find out which of these documents contain a particular word, e.g. "Little". The easiest way to do this would be to go through each word in each document, one by one, and see if the word "Little" is in that document. Conceptually, we're talking about this:

Doing this in C# is very easy:

            String[] documents = { "doc1.txt", "doc2.txt", "doc3.txt" };
           
            String keyword = Console.ReadLine();
           
            foreach (String document in documents)
            {
                if (File.ReadAllText(document).Contains(keyword))
                {
                    Console.WriteLine(document);
                }
            }

            Console.ReadKey(true);

Remember to put in a using System.IO; at the top, to be able to use File. If you press F5 and test this program, you'll see that it works:

However, this method isn't good because it will take longer as the documents get larger (more words) and more numerous (more documents).

The proper way to process search requests quickly is to build an index. This would look something like this:

The index stores a list of all words, each with a list of documents that contain it. If you compare it with the first diagram, you'll notice that we reversed the mapping of words and documents; this is why we call this an inverted index.

We can do this in C# by first building the index (remember to add using System.Collections.Generic; at the top):

            // Build the index
           
            String[] documents = { "doc1.txt", "doc2.txt", "doc3.txt" };
            Dictionary<String, List<String>> index = new Dictionary<String, List<String>>();
           
            foreach (String document in documents)
            {
                String documentStr = File.ReadAllText(document);
                String[] words = documentStr.Split();
               
                foreach (String word in words)
                {
                    if (!index.ContainsKey(word))
                        index[word] = new List<String>();
                   
                    index[word].Add(document);
                }
            }

...and then using the index to search the documents quickly and efficiently:

            // Query the index
           
            String keyword = Console.ReadLine();
           
            if (index.ContainsKey(keyword))
            {
                foreach (String document in index[keyword])
                {
                    Console.WriteLine(document);
                }
            }
            else
                Console.WriteLine("Not found!");

            Console.ReadKey(true);

In this way, there is no need to search every document for the keyword each time the user wants to search for a word. The keyword is simply located in the index (if it exists), and a list of documents that contain it is immediately available:

This was a simple proof of concept of how indexing and search works, but here are a few additional notes:

• The index is usually built as documents are added to it, and then stored in one or more files (unlike in this program, where the index is rebuilt every time the program is run - that's just to make the illustration easier).
• Words such as "and" and "the" which are very common are called stop words and are normally excluded from the index.
• It is common practice to make searches case insensitive, e.g. by converting indexed words and query keywords to lowercase.

This article presented the concept of indexing and how it is used to search for a single keyword. Although there are other techniques used in text search, indexing is definitely one of the most important, and has many applications including databases and text retrieval (e.g. search engines). A fundamental concept to remember is that the whole point of indexing is to make search fast!

Thanks for reading! :) Feel free to leave feedback (positive or negative) either in the comments or by contacting me. Remember to subscribe to the Programmer's Ranch Facebook page to stay up to date with articles as they are published!