Common Behaviors of Collections

Introduction

Although you can create a collection class from scratch, most collections classes share some fundamental behaviors and characteristics that you can apply when creating a collection class. To give a skeleton of these default requirements, the .NET Framework provides a few interfaces that you can simply implement.

Introduction to the ICollection Interface

One of the primary pieces of information you should provide about the values in a collection is the number of items a list is (currently) holding. When creating a collection class, to prepare it to provide this valuable information, you can (should) implement an interface named ICollection. The ICollection interface is defined in the System.Collections namespace. The ICollection interface derives from the IEnumerable interface:

public interface ICollection : IEnumerable

The generic equivalent of the ICollection interface is defined in the System.Collections.Generic namespace. The ICollection<> interface inherits from the IEnumerable<> and the IEnumerable interfaces:

public interface ICollection<T> : IEnumerable<T>, 
								  IEnumerable

Therefore, to start a collection class, you can first implement one of these interfaces. Here is an example for the System.Collections.ICollection<> interface:

using System.Collections.Generic;

public class Itemization<T> : ICollection<T>
{
}

Thanks to the flexibility of arrays in the .NET Framework, you can create the items of the collection as an array and give it an initial size. Here is an example:

using System.Collections.Generic;

public class Itemization<T> : ICollection<T>
{
    private int size;
    private T[] items;

    public Itemization()
    {
        size = 0;
        items = new T[0];
    }
}

Implementing ICollection

To assist you with keeping track of the number of items in a collection, the ICollection<T> interface is equipped with an integral property named Count, which you must implement. To do this, you can create a private member variable that will actually keep a count of the number of items. The Count property can then be used to communicate this information to the clients of the class. Here is an example:

using System.Collections.Generic;

public class Itemization<T> : ICollection<T>
{
    private int size;

    public Itemization()
    {
        size = 0;
    }

    public virtual int Count
    {
        get { return size; }
    }
}

The ICollection<> interface also allows its implementer to copy some of its items to an array. To provide this functionality, the interface is equipped with a method named CopyTo, which you must implement. The syntax of this method is:

void CopyTo(T[] array, int arrayIndex);

This method takes two arguments. The first argument is the array that will receive the items. The second argument is the index of the item from where the copying operation will begin. Here is an example:

using System.Collections.Generic;

public class Itemization<T> : ICollection<T>
{
    private int size;
    private T[] items;

    public Itemization()
    {
        size = 0;
        items = new T[0];
    }

    public virtual int Count
    {
        get { return size; }
    }

    public void CopyTo(T[] array, int index)
    {
        T[] values = new T[size];

        for (int i = 0; i < size; i++)
            values[i] = items[i];

        array = values;
    }
}

The System.Collections.ICollection interface extends the IEnumerable interface. The System.Collections.Generic.ICollection<T> interface extends the IEnumerable and the IEnumerable<> interfaces. In the previous lesson, we saw that this means that you should be able to use foreach in your ICollection<>-based collections but you must create the functionality yourself, which is done by implementing the GetEnumerator() method. Because the ICollection<> interface inherits from IEnumerable<> that itself inherits from IEnumerable, you must implement two versions of the GetEnumerator() methods. As we saw already, their syntaxes are:

IEnumerator<T> GetEnumerator();
IEnumerator GetEnumerator();

Even if you don't want to support this feature, you still must provide at least a skeleton for these methods. Here is an example:

using System.Collections.Generic;

public class Itemization<T> : ICollection<T>
{
    private int size;
    private T[] items;

    public Itemization()
    {
        size = 0;
        items = new T[0];
    }

    public virtual int Count
    {
        get { return size; }
    }

    public void CopyTo(T[] array, int index)
    {
        T[] values = new T[size];

        for (int i = 0; i < size; i++)
            values[i] = items[i];

        array = values;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }
}

Introduction to the IList Interface

Overview

While the System.Collections.Generic.ICollection<> (and the System.Collections.ICollection) interface provides basic functionality, to assist you in laying out a foundation of a collection class as complete as possible, the .NET Framework provides an interface named IList<> (and its accompanying IList interface). The IList<> interface is defined in the System.Collections.Generic namespace and its non-generic equivalent of the same name is defined in the System.Collections namespace. To use the functionalities of the System.Collections.Generic.IList<> interface necessary to add, insert, get, and delete items from a collection, you must create a class that implements them.

Implementing IList

The System.Collections.IList interface starts as follows:

public interface IList : ICollection, IEnumerable

The System.Collections.Generic.IList<> interface starts as follows:

public interface IList<T> : ICollection<T>,
						    IEnumerable<T>, 
						    IEnumerable

As mentioned above, to create a collection, you can implement the IList<> interface. Here is an example of starting it:

using System.Collections.Generic;

public class Itemization<T> : IList<T>
{
}

This means that the IList<> interface extends the ICollection<>, the IEnumerable<>, and the IEnumerable interfaces. This also implies that you must implement the members of all these parent interfaces, including the Count, the IsReadOnly properties, the CopyTo(), and the GetEnumerator() methods as we saw above. From what we learned with the ICollection interface, here are examples of implementing these members for the System.Collections.IList<T> interface:

using System.Collections.Generic;

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    public Itemization()
    {
        size = 0;
        items = new T[0];
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        T[] values = new T[size];

        for (int i = 0; i < size; i++)
            values[i] = items[i];

        array = values;
    }

    public int Count
    {
        get { return size; }
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }
}

As you may know already, while you are implementing an interface, if you are working in Microsoft Visual Studio, it would keep displaying some warnings to remind you about some member(s) you haven't implemented yet. Fortunately, Microsoft Visual Studio can generate skeleton code for your implementation. This would accomplish two goals: 1) it would eliminate the warnings (and errors), 2) it would provide a type of default implementation or a member.

To ask Microsoft Visual Studio to generate code for your interface implementation, start the class in the Code Editor and specify its interface(s). Then:

Populating a Collection

A Read-Only Collection

Most collections are made to receive new values. If you want, you can create a list that cannot receive new values. To support this, the IList interface is equipped with a Boolean property named IsReadOnly. If a list is read-only, it would prevent the clients from adding items to it.

Here is an example of implementing the IsReadOnly property for the System.Collections.IList<T> interface:

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    public Itemization()
    {
        size = 0;
        items = new T[10];
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        T[] values = new T[size];

        for (int i = 0; i < size; i++)
            values[i] = items[i];

        array = values;
    }

    public int Count
    {
        get { return size; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }
}

Adding an Item

As it should be obvious, the primary operation to perform on a list is to populate it with at least one value or object. To support this operation, the IList<> interface is equipped with a method named Add. Its syntax is:

void Add(T item);

This method takes one argument as the value to add to the collection. If your collection is an array, you can first check that there is still enough room to add a new item. In reality, this is never an issue with the System.Collections.IList interface:

The Add() method could be defined as follows::

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    . . .
    
    public int Add(T item)
    {
        this.items[this.size] = item;
        this.size++;

        return size;
    }
}

By default, an array has a fixed size. If you try adding an item in a position higher than the maximum number of items, the compiler would throw an IndexOutOfRangeException exception. Fortunately, we saw that the Array class is equipped with a method named Resize. This allows you to increase the size of an array when you judge it necessary. As a consequence, you can have an array as big as possible.

Inserting an Item

When you call the Add() method, it adds the new value to the end of the list. Sometimes, you will want the new value to be inserted somewhere inside the list. To support this operation, both the System.Collections.IList and the System.Collections.Generic.IList interfaces provide a method named Insert. The syntax of the System.Collections.IList.Insert() method is:

void Insert(int index, object value);

The syntax of the System.Collections.Generic.IList.Insert() method is:

void Insert(int index, T value);

This method takes two arguments. The second argument is the value or object that will be inserted into the list. The argument must hold a valid value or object. Because the System.Collections.IList.Insert() method takes an object value, if your collection is using a different type of value, you may have to cast it to object. The first argument is the index of the item that will precede the new one.

As mentioned for the System.Collections.IList.Add() method, there are a few things you should know about this operation's success or failure:

The System.Collections.Generic.IList.Insert() method can be implemented as follows:

using System.Collections.Generic;

namespace Exercises.App_Code
{
    public class Itemization<T> : IList<T>
    {
        . . . No Change

        public void Insert(int index, T value)
        {
            // If the index is the same as the current number of items
            // then call Add() and proceed as if we want to add a new item
            if (index >= size)
            {
                Add(value);
                return;
            }

            // If the index is positive but less than the current size,
            // then you need to insert the item inside the collection.
            if ((index >= 0) && (index < size))
            {
                // First, push each item one position up to create
                // an empty space
                for (int i = (size - 1); i > index - 1; i--)
                    items[i + 1] = items[i];

                // Then put the new item in the indicated position
                items[index] = value;
                // Since the new item has been added, increase the 
                // current number of items
                size++;
            }
        }

        public void CopyTo(T[] array, int index)
        {
            . . . No Change
        }

        . . . No Change
    }
}

When calling the IList<>.Insert() method, if you pass an invalid index, the compiler would throw an ArgumentOutOfRangeException.

Locating an Item in the Collection

this Item of a Collection

While using a list, various operations require that you know the object you are currently accessing. To support this operation, the IList and the IList<> interfaces are equipped with an indexed property named Item that you must implement. The Item property of the System.Collection.Generic.IList interface is declared as follows:

T this[int index] { get; set; }

If you implement it right, this property can perform one of three operations:

Here is an example of implementing the indexed property of the IList<> interface:

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    . . .

    // The index property can be used to add an item to a collection,
    // or to get an item from the collection
    public T this[int index]
    {
        get
        {
            return this.items[index];
        }
        set
        {
            this.items[index] = value;
        }
    }
}

After creating this property, you can then access an item using its index and applying the [] operator on its instance.

Iterating Through a Collection

One of the most valuable operations to make available to a collection is the ability to visit each one of its members. As we saw already, this operation is supported by the GetEnumerator() method provided by the IEnumerable<T> interface that each collection class implements.

Checking Whether a Collection Contains a Certain Item

One of the routine operations you can perform on a list is to find out whether it contains a certain value. To assist you with this operation, the IList<> interface is equipped with a method named Contains. Its syntax is:

bool Contains(T item);

This method takes as argument the value to look for. If the value is found in the collection, the method returns true. If the value is not found in the collection, this method returns false. Here is an example of implementing this method:

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    . . .
    
    public bool Contains(T value)
    {
        for (int i = 0; i < Count; i++)
            if (items[i].Equals(value))
                return true;
        return false;
    }
}

This method calls the Equals() method of the objects that make up the list to find out whether the value argument exists in the collection. If this method produces a wrong result, especially if you are using your own class to represent the item, you should (must) override the Equals() method. Here is an example of a class that indicates that two Employee objects are the same if they have the same employee number (because two employees in the same company/collection should not have the same employee number):

using System.Collections.Generic;

public class Itemization<T> : IList<T>
{
    . . . No Change
}

public class Employee
{
    public long   EmployeeNumber { get; set; }
    public string FirstName      { get; set; }
    public string LastName       { get; set; }
    public double HourlySalary   { get; set; }

    public override bool Equals(object obj)
    {
        Employee empl = (Employee)obj;

        if (this.EmployeeNumber == empl.EmployeeNumber)
            return true;

        return false;
    }

    public override int GetHashCode()
    {
        return base.GetHashCode();
    }
}

Getting the Index of an Item

The Contains() method is used to check whether a particular value (already) exists in the collection. If you know that a certain item exists but you don't know its index inside the list, the IList<> interface can assist you through a method named IndexOf. Its syntax is:

int IndexOf(T item);

This method takes as argument the value to look for in the list. If the value is found in the collection, the method returns its index. If there is no value defined like that, the method returns -1. Here is an example of implementing this method:

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    . . .
    
    public int IndexOf(T value)
    {
        for (int i = 0; i < Count; i++)
            if (items[i].Equals(value))
                return i;
        return -1;
    }
}

Once again, this method calls the Equals() method of the objects that make up the collection. In most cases, you should make sure you override the Equals() method in the class that T represents.

Getting an Item from a Collection

Getting an item consists of finding and producing it, not necessarily its index or whether it exists. You can write code in your collection class to get the object or you can use a combination of the methods and properties we have already reviewed to locate and produce the item.

Deleting Items from a Collection

Deleting a Value by its Index

If a value is not necessary in your collection, you can delete it. Probably the simplest way to delete a value is to specify its position in the list. To support this operation, both the System.Collections.IList and the System.Collections.Generic.IList<> interfaces are equipped with a method named RemoveAt. The syntax of the RemoveAt() method is the same for both interfaces and it is:

void RemoveAt(int index);

This method takes as argument the index of the value to be removed. If the index is valid, the method removes the item at that position. If the index is not valid, the compiler would throw an ArgumentOutOfRangeException exception. Here is an example:

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    . . .
    
    // This method is used to delete an item based on its position
    public void RemoveAt(int index)
    {
        // First check that the user provided a positive index that
        // is lower than the current total number of items
        if ((index >= 0) && (index < size))
        {
            // If so, starting at that index, get the item ahead of
            // each position and assign it to the current item
            for (int i = index; i < size - 1; i++)
                items[i] = items[i + 1];

            // Since the last item is not useful anymore,
            // decrease the number of items
            size--;
        }
    }
}

If the item cannot be deleted for another reason, the compiler would throw a NotSupportedException exception.

Deleting an Item by its Value

The above method could delete the wrong value or object if you provide the wrong index. An alternative is to first precisely define the value or the object you want to get rid of, and then hand the value or object to the compiler that would remove it. To support this approach, the System.Collections.IList interface is equipped with a method named Remove. Its syntax is:

bool Remove(T item);

This method takes as argument the value to be deleted. This means that the compiler will first look for the value in the list. If it finds that value, it removes it. If there is no value like that, nothing would happen. Here is an example of implementing this method:

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    . . .
    
    // This method is used to delete an item
    public bool Remove(T value)
    {
        // First try to get the index of the item to find out if it exists
        int index = IndexOf(value);
        
        // If the item was found ...
        if (index >= 0)
        {
            // ... delete it, using its index
            RemoveAt(index);
            // Since the item has been removed, return true
            return true;
        }

        // If the item was not removed (for any reason), return false
        return false;
    }
}

Clearing a Collection

To let you remove all values or objects from a list, the IList<> interface is equipped with a method named Clear. Its syntax is:

void Clear();

Here is an example of implementing it:

using System;
using System.Collections.Generic;

public class Itemization<T> : IList<T>
{
    private int size;
    private T[] items;

    public Itemization()
    {
        size = 0;
        items = new T[10];
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        T[] values = new T[size];

        for (int i = 0; i < size; i++)
            values[i] = items[i];

        array = values;
    }

    public int Count
    {
        get { return size; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    private void CheckAndIncreaseIfNecessary()
    {
        if (size >= items.Length)
            Array.Resize<T>(ref items, items.Length + 5);
    }

    // The index property can be used to add an item to a collection,
    // or to retrieve an item from the collection
    public T this[int index]
    {
        get
        {
            return this.items[index];
        }
        set
        {
            this.items[index] = value;
        }
    }

    public void Add(T value)
    {
        // Check whether there is still room in the array.
        // If there is not enough room, then increase the capacity
        CheckAndIncreaseIfNecessary();

        // Add the item at the end
        this.items[this.size] = value;
        // Increase the current number of items
        this.size++;
    }

    public void Insert(int index, T value)
    {
        // If the index is the same as the current number of items
        // then call Add() and proceed as if we want to add a new item
        if (index >= size)
        {
            Add(value);
            return;
        }

        // If the index is positive but less than the current size,
        // then you need to insert the item inside the collection.
        if ((index >= 0) && (index < size))
        {
            // Firs, push each item one position up to create
            // an empty space
            for (int i = (size - 1); i > index - 1; i--)
                items[i + 1] = items[i];

            // Then put the new item in the indicated position
            items[index] = value;
            // Since the new item has been added, increase the 
            // current number of items
            size++;
        }
    }

    public bool Contains(T value)
    {
        for (int i = 0; i < Count; i++)
            if (items[i].Equals(value))
                return true;
        return false;
    }

    public int IndexOf(T value)
    {
        for (int i = 0; i < Count; i++)
            if (items[i].Equals(value))
                return i;
        return -1;
    }

    // This method is used to delete an item based on its position
    public void RemoveAt(int index)
    {
        // First check that the user provided a positive index that
        // is lower than the current total number of items
        if ((index >= 0) && (index < size))
        {
            // If so, starting at that index, get the item ahead of
            // each position and assign it to the current item
            for (int i = index; i < size - 1; i++)
                items[i] = items[i + 1];

            // Since the last item is not useful anymore,
            // decrease the number of items
            size--;
        }
    }

    // This method is used to delete an item
    public bool Remove(T value)
    {
        // First try to get the index of the item to find out if it exists
        int index = IndexOf(value);
        
        // If the item was found ...
        if (index >= 0)
        {
            // ... delete it, using its index
            RemoveAt(index);
            // Since the item has been removed, return true
            return true;
        }

        // If the item was not removed (for any reason), return false
        return false;
    }

    // This method is used to delete all items from a collection
    public void Clear()
    {
        // Visit each item in the collection and set it to the default value
        // (This is not really necessary)
        for (int i = 0; i < size; i++)
            items[i] = default(T);

        // Reset the number of items of the collection to 0
        size = 0;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        int counter = 0;

        while (counter < Count)
        {
            yield return items[counter];
            counter++;
        }
    }
}
Previous Copyright © 2008-2021, FunctionX Next