Exercise index of this lecture   Alphabetic index   Course home   

Exercises and solutions
Collection Classes

12.1   Shuffle List  

Write a Shuffle operation that disorders the elements of a collection in a random fashion. A shuffle operation is useful in many context. There is no Shuffle operation in System.Collections.Generic.List<T>. In the similar Java libraries there is a shuffle method.

In which class do you want to place the Shuffle operation? You may consider to make use of extension methods.

You can decide on programming either a mutating or a non-mutating variant of the operation. Be sure to understand the difference between these two options.

Test the operation on List<Card>. The class Card (representing a playing card) is one of the classes we have seen earlier in the course.

Solution

Here is a class ListExtension with a Shuffle extension method:

using System;
using System.Collections.Generic;

public static class ListExtension{

  public static void Shuffle<T>(this List<T> lst){
   Random randomSupplier = new Random(unchecked((int)DateTime.Now.Ticks)); 
   for(int i = 0; i < lst.Count - 1; i++){
     int r = randomSupplier.Next(i+1, lst.Count);

     // Swap list element i and r in lst:
     T remember = lst[r];
     lst[r] = lst[i];
     lst[i] = remember;
    }
  }
}

class App{
    public static void Main(){
     List<int> list = new List<int>(new int[]{5, 3, 2, 7, -4, 0});

     ReportList(list);

     list.Sort();
     ReportList(list);
     Console.WriteLine();

     for(int i = 1; i < 10; i++){
       list.Shuffle();
       ReportList(list);
       Console.WriteLine();
     }
  }

  public static void ReportList<T>(List<T> list){
    foreach(T el in list)
      Console.Write("{0, 3}", el);
    Console.WriteLine();
  }

}

Shuffle is a void method, which mutates the list by use of the indexer of the list. The Shuffle method mutates the list: It changes the order of the elements in the list. (Alternatively, we could have programmed a non-mutating variant that returns a new list which is shuffled relative to the original list). In a for-loop it swaps element number i and a random element - say number r - where i < r < this.Count.

In the App class, which contains a Main method, we shuffle a sample list of integers nine times in a row. Before each shuffling, we sort the list.

In a sample execution, I got the following output:

  5  3  2  7 -4  0
 -4  0  2  3  5  7

  5  7  0 -4  2  3

  2  5  7  3 -4  0

  7  2  0  5  3 -4

  3  5 -4  0  2  7

  7  0  3 -4  5  2

 -4  3  2  0  7  5

  2  7  5 -4  0  3

  5  3  0  2  7 -4

  7  0  5  3 -4  2

12.2   Course and Project classes  

In the earlier exercise about courses and projects (found in the lecture about abstract classes and interfaces) we refined the program about BooleanCourse, GradedCourse, and Project to use a common superclass called Course. Revise your solution (or the model solution) such that the courses in the class Project are represented as a variable of type List<Course> instead of by use of four variables of type Course.

Reimplement and simplify the method Passed in class Project. Take advantage of the new representation of the courses in a project, such that the "3 out of 4 rule" (see the original exercise) is implemented in a more natural way.

Solution

Here is my solution:

using System;
using System.Collections.Generic;

public abstract class Course{      

  private string name;

  public Course(string name){      
    this.name = name;
  }

  public abstract bool Passed();

}

public class BooleanCourse: Course{

  private bool grade;

  public BooleanCourse(string name, bool grade): base(name){
    this.grade = grade;
  }

  public override bool Passed(){
    return grade;
  }

}

public class GradedCourse: Course{ 

  private int grade;

  public GradedCourse(string name, int grade): base(name){
    this.grade = grade;
  }  

  public override bool Passed(){
    return grade >= 2;
  }

}

public class Project{

  private List<Course> courses;     // Now a list of courses instead of
                                    // four variables of type Course

  public Project(Course c1, Course c2, Course c3, Course c4){
                                    // Could/should be generalized to one parameter of type List<Course>
    courses = new List<Course>();  

    courses.Add(c1); courses.Add(c2);
    courses.Add(c3); courses.Add(c4);
  }

  public bool Passed(){             // Reimplemented. Counts the number 
                                    // of passed courses
    List<Course> passedCourses = 
      courses.FindAll(delegate(Course c){return c.Passed();});

    return passedCourses.Count >= 3;
  }

}

public class Program {

  public static void Main(){
    Course c1 = new BooleanCourse("Math", true),        
           c2 = new BooleanCourse("Geography", true),
           c3 = new GradedCourse("Programming", 2),
           c4 = new GradedCourse("Algorithms", 4);

    Project p = new Project(c1, c2, c3, c4);

    Console.WriteLine("Project Passed: {0}", p.Passed());
  }

}

The comments in the source code points out the interesting details.

12.3   Switching from Dictionary to SortedDictionary  

The program on this slide instantiates a Dictionary<Person,BankAccount>. As recommended earlier in this lecture, we should work with the dictionary via a variable of the interface type IDictionary<K,V>.

You are now asked to replace Dictionary<Person,BankAccount> with SortedDictionary<Person,BankAccount> in the above mentioned program.

This causes a minor problem. Identify the problem, and fix it.

Can you tell the difference between the output of the program on this slide and the output of your revised program?

You can access the BankAccount and Person classes in the web version of the material.

Solution

We need to hand an IComparer instead of a IEqualityComparer to the SortedDictionary constructor. The reason is that a SortedDcitionary needs a ordering (like CompareTo), and not just equality.

using System;
using System.Collections.Generic;

class DictionaryDemo{

  public static void Main(){

    IDictionary<Person, BankAccount> bankMap = 
      new SortedDictionary<Person,BankAccount>(new NewPersonComparer());

    // Make bank accounts and person objects
    BankAccount ba1 =  new BankAccount("Kurt", 0.01),
                ba2 =  new BankAccount("Maria", 0.02),
                ba3 =  new BankAccount("Francoi", 0.03),
                ba4 =  new BankAccount("Unknown", 0.04),
                ba5 =  new BankAccount("Anna", 0.05);

    Person p1 = new Person("Kurt"),
           p2 = new Person("Maria"),
           p3 = new Person("Francoi"),
           p4 = new Person("Anna");

    ba1.Deposit(100); ba2.Deposit(200); ba3.Deposit(300); 

    // Populate the bankMap: 
    bankMap.Add(p1, ba1); 
    bankMap.Add(p2, ba2);
    bankMap.Add(p3, ba3);
    bankMap.Add(p4, ba5);
    ReportDictionary("Initial map", bankMap);

    // Print Kurt's entry in the map:
    Console.WriteLine("{0}\n", bankMap[p1]);

    // Mutate Kurt's entry in the map
    bankMap[p1] = ba4;
    ReportDictionary("bankMap[p1] = ba4;", bankMap);

    // Mutate Maria's entry in the map. PersonComparer crucial!
    ba4.Deposit(400);
    bankMap[new Person("Maria")] = ba4;
    ReportDictionary("ba4.Deposit(400);  bankMap[new Person(\"Maria\")] = ba4;", bankMap);

    // Add p3 yet another time to the map
    // Run-time error: An item with the same key has already been added.
/*  bankMap.Add(p3, ba1);
    ReportDictionary("bankMap.Add(p3, ba1);", bankMap); 
 */

    // Try getting values of some given keys
    BankAccount ba1Res = null,
                ba2Res = null;
    bool res1 = false,
         res2 = false;
    res1 = bankMap.TryGetValue(p2, out ba1Res);        
    res2 = bankMap.TryGetValue(new Person("Anders"), out ba2Res);
    Console.WriteLine("Account: {0}. Boolean result {1}", ba1Res, res1);
    Console.WriteLine("Account: {0}. Boolean result {1}", ba2Res, res2);
    Console.WriteLine();

    // Remove an entry from the map
    bankMap.Remove(p1);
    ReportDictionary("bankMap.Remove(p1);", bankMap);

    // Remove another entry - works because of PersonComparer
    bankMap.Remove(new Person("Francoi"));
    ReportDictionary("bankMap.Remove(new Person(\"Francoi\"));", bankMap);
  }

  public static void ReportDictionary<K, V>(string explanation, 
                                            IDictionary<K,V> dict){
    Console.WriteLine(explanation);
    foreach(KeyValuePair<K,V> kvp in dict)
      Console.WriteLine("{0}: {1}", kvp.Key, kvp.Value);
    Console.WriteLine(); 
  }
}

public class PersonComparer: IEqualityComparer<Person>{

  public bool Equals(Person p1, Person p2){
    return (p1.Name == p2.Name);
  }

  public int GetHashCode(Person p){
    return p.Name.GetHashCode();
  }
}

public class NewPersonComparer: IComparer<Person>{

  public int Compare(Person p1, Person p2){
    return (p1.Name.CompareTo(p2.Name));
  }
}

Here is the output of the program:

Initial map
Person: Francoi : Francoi's account holds 300 kroner
Person: Kurt : Kurt's account holds 100 kroner
Person: Maria : Maria's account holds 200 kroner

Kurt's account holds 100 kroner

bankMap[p1] = ba4;
Person: Francoi : Francoi's account holds 300 kroner
Person: Kurt : Unknown's account holds 0 kroner
Person: Maria : Maria's account holds 200 kroner

ba4.Deposit(400);  bankMap[new Person("Maria")] = ba4;
Person: Francoi : Francoi's account holds 300 kroner
Person: Kurt : Unknown's account holds 400 kroner
Person: Maria : Unknown's account holds 400 kroner

Account: Unknown's account holds 400 kroner. Boolean result True
Account: . Boolean result False

bankMap.Remove(p1);
Person: Francoi : Francoi's account holds 300 kroner
Person: Maria : Unknown's account holds 400 kroner

bankMap.Remove(new Person("Francoi"));
Person: Maria : Unknown's account holds 400 kroner

It should noticed that the entries in the sorted map are ordered by the persons name. This was not the case in the version of program, which relied on Dictionary<Person,BankAccount>.

12.4   Explicit use of iterator - instead of using foreach  

In this program we will make direct use of an iterator (an enumerator) instead of traversing with use of foreach.

In the animal collection program, which we have seen earlier in this lecture, we traverse the animal collections several times with use of foreach. Replace each use of foreach with an application of an iterator.

Solution

Here is my solution:

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;


class CollectionInterfaceDemo{

  public static void Main(){
    ICollection<Animal> lst = new Collection<Animal>();

    // Add elements to the end of the empty list:
    lst.Add(new Animal("Cat"));  lst.Add(new Animal("Dog", Sex.Female));
    lst.Add(new Animal("Mouse"));  lst.Add(new Animal("Rat"));
    lst.Add(new Animal("Mouse", Sex.Female));  lst.Add(new Animal("Rat"));
    lst.Add(new Animal("Herring", AnimalGroup.Fish, Sex.Female));  
    lst.Add(new Animal("Eagle", AnimalGroup.Bird, Sex.Male));   

    // Report in various ways on the animal collection:
    Print("Initial List", lst);
    ReportFemaleMale(lst);
    ReportGroup(lst);
  }

  public static void Print<T>(string explanation, ICollection<T> list){
    Console.WriteLine(explanation);
    IEnumerator<T> iterator = list.GetEnumerator();
    while(iterator.MoveNext()){
      Console.WriteLine("{0, 3}", iterator.Current);
    }
    Console.WriteLine(); Console.WriteLine();
  }

  public static void ReportFemaleMale(ICollection<Animal> list){
    int numberOfMales = 0,
        numberOfFemales = 0;

    IEnumerator<Animal> iterator = list.GetEnumerator();
    while(iterator.MoveNext()){
      if (iterator.Current.Sex == Sex.Male) numberOfMales++;
      else if (iterator.Current.Sex == Sex.Female) numberOfFemales++;
    }

    Console.WriteLine("Males: {0}, Females: {1}", 
                       numberOfMales, numberOfFemales);
  }

  public static void ReportGroup(ICollection<Animal> list){
    int numberOfMammals = 0,
        numberOfBirds = 0,
        numberOfFish = 0;

    IEnumerator<Animal> iterator = list.GetEnumerator();
    while(iterator.MoveNext()){
      if (iterator.Current.Group == AnimalGroup.Mammal) numberOfMammals++;
      else if (iterator.Current.Group == AnimalGroup.Bird) numberOfBirds++;
      else if (iterator.Current.Group == AnimalGroup.Fish) numberOfFish++;
    }

    Console.WriteLine("Mammals: {0}, Birds: {1}, Fish: {2}", 
                       numberOfMammals, numberOfBirds, numberOfFish);
  }

}

12.5   Using multiple interators  

In this exercise we will see how to make good use of two interators of a single collection. Our starting point will be the type Interval, and the iterator which we have programmed for this type earlier in this teaching material.

For a given interval I, generate a list of all possible pairs (e,f) where both e and f come from I. As an example, the interval new Interval(1,2) should give rise to the list (1, 1), (1, 2), (2, 1), and (2, 2). For the purpose of generating the list of all such pairs, request two iterators from the interval, and traverse the interval appropriately in two nested while loops.

Like in the previous exercise, it is suggested that you use the operations in IEnumerator. Such a solution gives the best understanding of the use of multiple iterators. It is, however, also possible to solve this exercise by nested foreach loops.

Solution

Here is the program that generates the list of all pairs of numbers from an interval:

using System;
using System.Collections;
using System.Collections.Generic;

public class app {

  public static void Main(){

    Interval iv1 = new Interval(1,2);

    IEnumerator e1 = iv1.GetEnumerator(),
                e2 = iv1.GetEnumerator();

    List<Pair<int,int>> pairs = new List<Pair<int,int>>();

    while (e1.MoveNext()){
      while (e2.MoveNext())
         pairs.Add(new Pair<int,int>((int)(e1.Current), (int)(e2.Current)));
      e2.Reset();
    }

    foreach(Pair<int,int> p in pairs)
      Console.WriteLine("({0}, {1})", p.First, p.Second);
  }
}

The program makes use of generic class Pair<T,S> which can be programmed in the following way:

using System;

public class Pair<T,S>{
  private T first;
  private S second;

  public Pair(T first, S second){
    this.first = first; this.second = second;
  }

  public T First{
     get {return first;}
  }

  public S Second{
     get {return second;}
  }
  
}

12.6   The iterator behind a yield  

Reprogram the iterator in class GivenCollection without using the yield return statement in the GetEnumerator method.

12.7   Infinite Collections of Integers  

In several respects, this exercise previews ideas from LINQ.

Program a class IntegersFrom which represent an inifinite sequence of integers (of type long) from a given starting point. The class must implement the interface IEnumerable<long>.

First, program a version without use of yield return, and next program a version which uses yield return. Compare the two versions. (It is surprisingly tricky to program the version which uses native iterators (enumerators) in C#, without using yield return. You may chose to study my implementation (in the solution) instead of spending time on programming the class yourself.)

As an alternative to the class IntegersFrom, make an extension method AdInifinitum (which means 'to inifinity') in the type long , which enumerates an infinite sequence of integers from a given starting point:

    public static IEnumerable AdInfinitum(this long from){...}

Make an additional extension method in the interface IEnumerable<long> which filters an infinite sequence of integers with use of a given predicate

   
  public static IEnumerable<long> Filter(this IEnumerable<long> source, 
                                         Func<long, bool> pred){...}

Use Filter to obtain all even integers, and all primes.

Finally, program an extension method in IEnumerable<long> that adds two infinite sequences of integers together (pair-by-pair):

    
  public static IEnumerable<long> Add(this IEnumerable<long> source,
                                      IEnumerable<long> other){...}

Add all natural numbers, lL.AdInfinitum(), to itself, and get all even numbers again.

Solution

My solution is here:

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;                 // only because we use Take in Main

    public class IntegersFrom : IEnumerable<long>
    {
        private long low;

        public IntegersFrom(long low)
        {
            this.low = low;
        }

        public long LowerLimit
        {
            get { return low; }
        }

        private class IntegerEnumerator : IEnumerator<long>
        {
            private IntegersFrom intfr;
            private long curint;

            public IntegerEnumerator(IntegersFrom intfr)
            {
                this.intfr = intfr;
            }

            public long Current { get { return curint; } }

            object IEnumerator.Current { get { return curint; } }  // !!

            public bool MoveNext() { curint++; return true; }

            public void Reset() { curint = intfr.low; }

            void IDisposable.Dispose(){}  // !!
        }

        public IEnumerator<long> GetEnumerator()
        {
            return new IntegerEnumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }


    }

    public class IntegersFromAlternative : IEnumerable<long>
    {
        private long low;

        public IntegersFromAlternative(long low)
        {
            this.low = low;
        }

        public long LowerLimit
        {
            get { return low; }
        }

        public IEnumerator<long> GetEnumerator(){
            for(long i = low; true; i++)
                yield return i;
        }

        IEnumerator IEnumerable.GetEnumerator()  // !!
        {
            return GetEnumerator();
        }
     

    }

    internal static class Extensions
    {
        public static IEnumerable<long> AdInfinitum(this long from)
        {
            for (long i = from; true; i++)
                yield return i;
        }

        public static IEnumerable<long> Filter(this IEnumerable<long> source, Func<long,bool> pred)
        {
            foreach (long i in source)
                if (pred(i)) yield return i;
        }

        public static IEnumerable<long> Add(this IEnumerable<long> source, IEnumerable<long> other)
        {
            IEnumerator<long> sourceEnum = source.GetEnumerator();
            IEnumerator<long> otherEnum = other.GetEnumerator();

            while (true)
            {
                yield return sourceEnum.Current + otherEnum.Current;
                sourceEnum.MoveNext();
                otherEnum.MoveNext();
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var itf1 = new IntegersFrom(1);
            var itf2 = new IntegersFromAlternative(1);

            // foreach (long i in itf1) { Console.WriteLine(i); }

            IEnumerable<long> natNums = 1L.AdInfinitum();

            // foreach (long i in natNums) { Console.WriteLine(i); }

            //foreach (long i in natNums.Filter(n => n % 2 == 0))
            //{
            //    Console.WriteLine(i);
            //}

            //var even100 = natNums.Filter(n => n % 2 == 0).Take(100);
            //foreach (long i in even100) Console.WriteLine(i);

            var evenNumbers = natNums.Add(natNums).Take(100);
            foreach (long i in evenNumbers) Console.WriteLine(i);

            Console.ReadLine();
        }
    }

Generated: Monday February 7, 2011, 12:21:46