Kurt Nørmark ©
Department of Computer Science, Aalborg University, Denmark

Abstract Previous lecture Next lecture Index References Contents

In this lecture we review the collection classes of the C# library. We concentrate our efforts on the generic, type parameterized collection classes. The main parts of the lecture are about the list classes and the dictionary classes. At the end of the lecture we compare with the older, non-generic collection classes.

Native arrays and custom made lists Fixed sized arrays - limited set of operations Variable sized linked lists - direct pointer manipulation First generation collection classes Elements of type Object - Flexible sizing - Rich repertoire of operations Type unsafe - Casting - Inhomogeneous collections Second generation collection classes The flexibility of the first generation collections remains Type safe - Generic - Type parameterized - Homogeneous

Reference First generation collection classes

Modern collection libraries blur the distinction between arrays and lists

Classes and Interfaces related to list and array-like collections in C#

References Similar dictionary overview Similar non-generic overview

The class and interface inheritance tree related to Lists

The Interface IEnumerable<T> Slide Annotated slide Contents Index References Textbook

The interface IEnumerable<T> facilitates traversal of all elements in a collection

Reference The non-generic IEnumerable interface

Operations in the interface IEnumerable<T>: IEnumerator<T> GetEnumerator ( )

Reference The Iterator Design Pattern

Operations in the interface IEnumerator<T>: T Current bool MoveNext( ) void Reset ( )

The Interface ICollection<T> Slide Annotated slide Contents Index References Textbook

ICollection<T> contributes with membership, add, and remove operations

Reference The interface IEnumerable<T>

Operations in the interface ICollection<T>: The operation prescribed in the superinterface IEnumerable<T> bool Contains(T element) void Add(T element) bool Remove(T element) void Clear() void CopyTo(T[] targetArray, int startIndex) int Count bool IsReadOnly

The Interface IList<T> Slide Annotated slide Contents Index References Textbook

IList<T> contributes with indexing capabilities

Reference The interface ICollection<T>

Operations in the interface IList<T>: Those prescribed in the superinterfaces ICollection<T> and IEnumerable<T> T this[int index] int IndexOf(T element) void Insert(int index, T element) void RemoveAt(int index)

Overview of the class Collection<T> Slide Annotated slide Contents Index References Textbook

The class Collection<T> offers a basic repertoire of list operations Collection<T> holds the operations prescribed by IEnumerable<T>, ICollection<T>, and Ilist<T> - and not much more The Collection<T> class is located in the namespace System.Collections.ObjectModel

References Tree of generic list types Similar overview of List<T>

Members of the class Collection<T> Constructors Collection(),   Collection(IList<T>) Via a collection initializer: new Collection<T> {t1, t2, ..., tn} Element access this[int] Measurement Count Element addition Add(T),   Insert(int, T) Element removal Remove(T),   RemoveAt(int),   Clear() Searching IndexOf(T) Boolean Queries Contains(T) Conversions CopyTo(T[],int)

Sample use of class Collection<T> Slide Annotated slide Contents Index References Textbook

Reference Similar program for List<T>

Program: Basic operations on a Collection of characters. A C# 3.0 Program.

using System; using System.Collections.ObjectModel; using System.Collections.Generic; class BasicCollectionDemo{ public static void Main(){ // Initialization - use of a collection initializer. After that add 2 elements. IList<char> lst = new Collection<char>{'a', 'b', 'c'}; lst.Add('d'); lst.Add('e'); ReportList("Initial List", lst); // Mutate existing elements in the list: lst[0] = 'z'; lst[1]++; ReportList("lst[0] = 'z'; lst[1]++;", lst); // Insert and push towards the end: lst.Insert(0,'n'); ReportList("lst.Insert(0,'n');", lst); // Insert at end - with Insert: lst.Insert(lst.Count,'x'); // equivalent to lst.Add('x'); ReportList("lst.Insert(lst.Count,'x');", lst); // Remove element 0 and pull toward the beginning: lst.RemoveAt(0); ReportList("lst.RemoveAt(0);", lst); // Remove first occurrence of 'c': lst.Remove('c'); ReportList("lst.Remove('c');", lst); // Remove remaining elements: lst.Clear(); ReportList("lst.Clear(); ", lst); } public static void ReportList<T>(string explanation, IList<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.Write("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }

Program: Output of the program with basic operations on a Collection of characters.

Initial List a b c d e lst[0] = 'z'; lst[1]++; z c c d e lst.Insert(0,'n'); n z c c d e lst.Insert(lst.Count,'x'); n z c c d e x lst.RemoveAt(0); z c c d e x lst.Remove('c'); z c d e x lst.Clear();

Lessons learned: The indexer   lst[idx] = expr   mutates an existing element in the collection The length of the collection is unchanged The Insert operation splices a new element into the collection Push subsequent elements towards the end of the collection Makes the collection longer The Remove and RemoveAt operations take elements out of the collections Pull subsequent elements towards the beginning of the collection Makes the collection shorter

Specialization of Collections Slide Annotated slide Contents Index References Textbook

I want to make my own specialized/extended collection. Which class should be selected as superclass of my collection class? The class constructed from Collection<T> is a useful starting point

Program: A class Animal.

using System; public enum AnimalGroup {Mammal, Bird, Fish}; public enum Sex {Male, Female}; public class Animal: IComparable<Animal>{ private string name; private AnimalGroup? group; private Sex sex; public Animal(string name): this(name, AnimalGroup.Mammal, Sex.Male){ } public Animal(string name, Sex sex): this(name, AnimalGroup.Mammal, sex){ } public Animal(string name, AnimalGroup group, Sex sex){ this.name = name; this.group = group; this.sex = sex; } public string Name{ get{ return name; } } public AnimalGroup? Group{ get{ return group; } } public Sex Sex{ get{ return sex; } } public override string ToString(){ return "Animal: " + name; } public int CompareTo(Animal other){ return this.name.CompareTo(other.name); } public override bool Equals(Object obj){ if (obj == null) return false; else if (this.GetType() != obj.GetType()) return false; else if (ReferenceEquals(this, obj)) return true; else if (this.name == ((Animal)obj).name) return true; else return false; } }

Program: A class AnimalFarm - a subclass of Collection<Animal> - testing protected members.

using System; using System.Collections.ObjectModel; public class AnimalFarm: Collection<Animal>{ protected override void InsertItem(int i, Animal a){ base.InsertItem(i,a); Console.WriteLine("**InsertItem: {0}, {1}", i, a); } protected override void SetItem(int i, Animal a){ base.SetItem(i,a); Console.WriteLine("**SetItem: {0}, {1}", i, a); } protected override void RemoveItem(int i){ base.RemoveItem(i); Console.WriteLine("**RemoveItem: {0}", i); } protected override void ClearItems(){ base.ClearItems(); Console.WriteLine("**ClearItems"); } }

Program: A sample client of AnimalFarm - revealing use of protected Collection<Animal> methods.

using System; using System.Collections.ObjectModel; class App{ public static void Main(){ AnimalFarm af = new AnimalFarm(); // Populating the farm with Add af.Add(new Animal("elephant")); af.Add(new Animal("giraffe")); af.Add(new Animal("tiger")); ReportList("Adding elephant, giraffe, and tiger with Add(...)", af); // Additional population with Insert af.Insert(0, new Animal("dog")); af.Insert(0, new Animal("cat")); ReportList("Inserting dog and cat at index 0 with Insert(0, ...)", af); // Mutate the animal farm: af[1] = new Animal("herring", AnimalGroup.Fish, Sex.Male); ReportList("After af[1] = herring", af); // Remove tiger af.Remove(new Animal("tiger")); ReportList("Removing tiger with Remove(...)", af); // Remove animal at index 2 af.RemoveAt(2); ReportList("Removing animal at index 2, with RemoveAt(2)", af); // Clear the farm af.Clear(); ReportList("Clear the farm with Clear()", af); } public static void ReportList<T>(string explanation, Collection<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }

Program: Output from sample client of AnimalFarm.

**InsertItem: 0, Animal: elephant **InsertItem: 1, Animal: giraffe **InsertItem: 2, Animal: tiger Adding elephant, giraffe, and tiger with Add(...) Animal: elephant Animal: giraffe Animal: tiger **InsertItem: 0, Animal: dog **InsertItem: 0, Animal: cat Inserting dog and cat at index 0 with Insert(0, ...) Animal: cat Animal: dog Animal: elephant Animal: giraffe Animal: tiger **SetItem: 1, Animal: herring After af[1] = herring Animal: cat Animal: herring Animal: elephant Animal: giraffe Animal: tiger **RemoveItem: 4 Removing tiger with Remove(...) Animal: cat Animal: herring Animal: elephant Animal: giraffe **RemoveItem: 2 Removing animal at index 2, with RemoveAt(2) Animal: cat Animal: herring Animal: giraffe **ClearItems Clear the farm with Clear()

The protected, virtual methods InsertItem, RemoveItem, SetItem, and ClearItems are called from all relevant methods in Collection<T> Overridden members in AnimalFarm control the actual insertions and removals in the collection

Specialization of Collections - a realistic example Slide Annotated slide Contents Index References Textbook

An AnimalFarm class with auto insertion of animals of opposite sex An AnimalFarm class in which removal and clearing is denied An AnimalFarm class that extends Collection<Animal> with GetGroup

Program: The class Animal - Unchanged.

using System; public enum AnimalGroup {Mammal, Bird, Fish}; public enum Sex {Male, Female}; public class Animal: IComparable<Animal>{ string name; AnimalGroup group; Sex sex; public Animal(string name): this(name, AnimalGroup.Mammal, Sex.Male){ } public Animal(string name, Sex sex): this(name, AnimalGroup.Mammal, sex){ } public Animal(string name, AnimalGroup group): this(name, group, Sex.Male){ } public Animal(string name, AnimalGroup group, Sex sex){ this.name = name; this.group = group; this.sex = sex; } public string Name{ get{ return name; } } public AnimalGroup Group{ get{ return group; } } public Sex Sex{ get{ return sex; } } public override string ToString(){ if (sex == Sex.Male) return "Animal: " + name + "(Male)"; else return "Animal: " + name + "(Female)"; } public int CompareTo(Animal other){ return this.name.CompareTo(other.name); } public override bool Equals(Object obj){ if (obj == null) return false; else if (this.GetType() != obj.GetType()) return false; else if (ReferenceEquals(this, obj)) return true; else if (this.name == ((Animal)obj).name) return true; else return false; } }

Program: The class AnimalFarm - a subclass of Collection<Animal>.

using System; using System.Collections.ObjectModel; public class AnimalFarm: Collection<Animal>{ // Auto insert animal of opposite sex protected override void InsertItem(int i, Animal a){ if(a.Sex == Sex.Male){ base.InsertItem(i,a); base.InsertItem(i, new Animal(a.Name, a.Group, Sex.Female)); } else { base.InsertItem(i,a); base.InsertItem(i,new Animal(a.Name, a.Group, Sex.Male)); } } // Prevent removal protected override void RemoveItem(int i){ Console.WriteLine("[Removal denied]"); } // Prevent clearing protected override void ClearItems(){ Console.WriteLine("[Clearing denied]"); } // Return all male animals in a given group public AnimalFarm GetGroup(AnimalGroup g){ AnimalFarm res = new AnimalFarm(); foreach(Animal a in this) if (a.Group == g && a.Sex == Sex.Male) res.Add(a); return res; } }

Program: A sample client of AnimalFarm.

using System; using System.Collections.ObjectModel; class App{ public static void Main(){ AnimalFarm af = new AnimalFarm(); // Populating the farm with Add af.Add(new Animal("elephant")); af.Add(new Animal("giraffe")); af.Add(new Animal("tiger")); ReportList("Adding elephant, giraffe, and tiger with Add(...)", af); // Additional population with Insert af.Insert(0, new Animal("blueJay", AnimalGroup.Bird)); af.Insert(0, new Animal("goldenEagle", AnimalGroup.Bird)); ReportList("Inserting blue jay and golden eagle at index 0 with Insert(0, ...)", af); // Extract birds: AnimalFarm birds = af.GetGroup(AnimalGroup.Bird); ReportList("The birds in farm - extraced with GetGroup", birds); // Remove tiger af.Remove(new Animal("tiger")); ReportList("Removing tiger with Remove(...)", af); // Remove animal at index 2 af.RemoveAt(2); ReportList("Removing animal at index 2, with RemoveAt(2)", af); // Clear the farm af.Clear(); ReportList("Clear the farm with Clear()", af); } public static void ReportList<T>(string explanation, Collection<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }

Program: Output from sample client of AnimalFarm.

Adding elephant, giraffe, and tiger with Add(...) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) Inserting blue jay and golden eagle at index 0 with Insert(0, ...) Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) The birds in farm - extraced with GetGroup Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) [Removal denied] Removing tiger with Remove(...) Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) [Removal denied] Removing animal at index 2, with RemoveAt(2) Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) [Clearing denied] Clear the farm with Clear() Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male)

Overview of the class List<T> Slide Annotated slide Contents Index References Textbook

The class List<T> offers a comprehensive repertoire of list operations

References Tree of generic list types Similar overview of Collection<T>

Members of the class List<T> Constructors List(),   List(IEnumerable<T>),   List(int) Via a collection initializer: new List<T> {t1, t2, ..., tn} Element access this[int],   GetRange(int, int) Measurement Count,   Capacity Element addition Add(T),   AddRange(IEnumerable<T>),   Insert(int, T), InsertRange(int, IEnumerable<T>) Element removal Remove(T),   RemoveAll(Predicate<T>),   RemoveAt(int),   RemoveRange(int, int),   Clear() Reorganization Reverse(),   Reverse(int, int), Sort(),   Sort(Comparison<T>), Sort(IComparer<T>),   Sort(int, int, IComparer<T>) Searching BinarySearch(T),   BinarySearch(int, int, T, IComparer<T>),   BinarySearch(T, IComparer<T>) Find(Predicate<T>),   FindAll(Predicate<T>),   FindIndex(Predicate<T>), FindLast(Predicate<T>),   FindLastIndex(Predicate<T>),   IndexOf(T),   LastIndexOf(T) Boolean queries Contains(T),   Exists(Predicate<T>),   TrueForAll(Predicate<T>) Conversions ConvertAll<TOutput>(Converter<T,TOutput>),   CopyTo(T[]),

Sample use of class List<T> Slide Annotated slide Contents Index References Textbook

Illustration of the Add, Insert, and Removal operations Illustration of list bulk operations

Reference Similar program for Collection<T>

Program: Basic operations on a List of characters. A C# 3.0 program.

using System; using System.Collections.Generic; /* Very similar to our illustration of class Collection<char> */ class BasicListDemo{ public static void Main(){ // List initialization and adding elements to the end of the list: List<char> lst = new List<char>{'a', 'b', 'c'}; lst.Add('d'); lst.Add('e'); ReportList("Initial list, followed by lst.Add('d'); lst.Add('e');", lst); // Mutate existing elements in the list lst[0] = 'z'; lst[1]++; ReportList("lst[0] = 'z'; lst[1]++;", lst); // Insert and push towards the end lst.Insert(0,'n'); ReportList("lst.Insert(0,'n');", lst); // Insert at end - with Insert lst.Insert(lst.Count,'x'); // equivalent to lst.Add('x'); ReportList("lst.Insert(lst.Count,'x');", lst); // Insert a new list into existing list, at position 2. lst.InsertRange(2, new List<char>{'1', '2', '3', '4'}); ReportList("lst.InsertRange(2, new List<char>{'1', '2', '3', '4'});", lst); // Remove element 0 and push toward the beginning lst.RemoveAt(0); ReportList("lst.RemoveAt(0);", lst); // Remove first occurrence of 'c' lst.Remove('c'); ReportList("lst.Remove('c');", lst); // Remove 2 elements, starting at element 1 lst.RemoveRange(1, 2); ReportList("lst.RemoveRange(1, 2);", lst); // Remove all remaining digits lst.RemoveAll(delegate(char ch){return Char.IsDigit(ch);}); ReportList("lst.RemoveAll(delegate(char ch){return Char.IsDigit(ch);});", lst); // Test of all remaining characters are letters if (lst.TrueForAll(delegate(char ch){return Char.IsLetter(ch);})) Console.WriteLine("All characters in lst are letters"); else Console.WriteLine("NOT All characters in lst are letters"); } public static void ReportList<T>(string explanation, List<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.Write("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }

Program: Output of the program with basic operations on a List of characters.

Initial list, followed by lst.Add('d'); lst.Add('e'); a b c d e lst[0] = 'z'; lst[1]++; z c c d e lst.Insert(0,'n'); n z c c d e lst.Insert(lst.Count,'x'); n z c c d e x lst.InsertRange(2, new List<char>{'1', '2', '3', '4'}); n z 1 2 3 4 c c d e x lst.RemoveAt(0); z 1 2 3 4 c c d e x lst.Remove('c'); z 1 2 3 4 c d e x lst.RemoveRange(1, 2); z 3 4 c d e x lst.RemoveAll(delegate(char ch){return Char.IsDigit(ch);}); z c d e x All characters in lst are letters

Observations The range operations operations, such as InsertRange where not present in Collection<T> InsertRange and RemoveRange Also known as bulk operations The delegate-parameterized operations were not present in Collection<T> RemoveAll and TrueForAll

Sample use of the Find operations in List<T> Slide Annotated slide Contents Index References Textbook

An illustration of Find, FindAll and IndexOf Linear search

Program: Struct Point - used as actual List type parameter.

using System; public struct Point { private readonly double x, y; public Point(double x, double y){ this.x = x; this.y = y; } public double Getx (){ return x; } public double Gety (){ return y; } public Point Move(double dx, double dy){ return new Point(x+dx, y+dy); } public override string ToString(){ return "Point:" + "(" + x + "," + y + ")" + ". "; } }

Program: Sample uses of List.Find.

using System; using System.Collections.Generic; class C{ public static void Main(){ System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US"); List<Point> pointLst = new List<Point>(); // Construct points and point list: pointLst.Add(new Point(0,0)); pointLst.Add(new Point(5, 9)); pointLst.Add(new Point(5,4)); pointLst.Add(new Point(7.1,-13)); pointLst.Add(new Point(5,-2)); pointLst.Add(new Point(14,-3.4)); ReportList("Initial point list", pointLst); // Find first point in list with x coordinate 5 Point p = pointLst.Find(delegate(Point q){return (q.Getx() == 5);}); Console.WriteLine("Found with delegate predicate: {0}\n", p); // Equivalent. Use predicate which is a static method p = pointLst.Find(new Predicate<Point>(FindX5)); Console.WriteLine("Found with static member predicate: {0}\n", p); // Find all points in list with x coordinate 5 List<Point> resLst = new List<Point>(); resLst = pointLst.FindAll(delegate(Point q){return (q.Getx() == 5);}); ReportList("All points with x coordinate 5", resLst); // Find index of a given point in pointLst. // Notice that Point happens to be a struct - thus value comparison Point searchPoint = new Point(5,4); Console.WriteLine("Index of {0} {1}", searchPoint, pointLst.IndexOf(searchPoint)); } public static bool FindX5(Point p){ return p.Getx() == 5; } public static void ReportList<T>(string explanation,List<T> list){ Console.WriteLine(explanation); int cnt = 0; foreach(T el in list){ Console.Write("{0, 3}", el); cnt++; if (cnt%4 == 0) Console.WriteLine(); } if (cnt%4 != 0) Console.WriteLine(); Console.WriteLine(); } }

Program: Output from the Find program.

Initial point list Point:(0,0). Point:(5,9). Point:(5,4). Point:(7.1,-13). Point:(5,-2). Point:(14,-3.4). Found with delegate predicate: Point:(5,9). Found with static member predicate: Point:(5,9). All points with x coordinate 5 Point:(5,9). Point:(5,4). Point:(5,-2). Index of Point:(5,4). 2

Lessons learned Use of an anonymous delegate together with Find is very useful Find, FindLast, and FindAll return elements from the list (not indexes)

Sample use of Sort in List<T> Slide Annotated slide Contents Index References Textbook

An illustration of three different overloads of Sort operations

Program: Four different activations of the List.Sort method.

using System; using System.Collections.Generic; class C{ public static void Main(){ List<int> listOriginal = new List<int>{5, 3, 2, 7, -4, 0}, list; // Sorting by means of the default comparer of int: list = new List<int>(listOriginal); ReportList(list); list.Sort(); ReportList(list); Console.WriteLine(); // Equivalent - explicit notatation of the Comparer: list = new List<int>(listOriginal); ReportList(list); list.Sort(Comparer<int>.Default); ReportList(list); Console.WriteLine(); // Equivalent - explicit instantiation of an IntComparer: list = new List<int>(listOriginal); ReportList(list); list.Sort(new IntComparer()); ReportList(list); Console.WriteLine(); // Similar - use of a delegate value for comparison: list = new List<int>(listOriginal); ReportList(list); list.Sort(delegate(int x, int y){ if (x < y) return -1; else if (x == y) return 0; else return 1;}); ReportList(list); Console.WriteLine(); } public static void ReportList<T>(List<T> list){ foreach(T el in list) Console.Write("{0, 3}", el); Console.WriteLine(); } } public class IntComparer: Comparer<int>{ public override int Compare(int x, int y){ if (x < y) return -1; else if (x == y) return 0; else return 1; } }

Program: Output of the sorting program.

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

Lessons learned Some types have a default comparer which is used by List.Sort() The default comparer of T can extracted by Comparer<T>.Default An anonymous delegate comparer is attractive if the default comparer of the type does not exist, of if it is inappropriate.

Exercise 12.3. 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.

Exercise 12.3. 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.

Sample use of BinarySearch in List<T> Slide Annotated slide Contents Index References Textbook

An illustration of two overloads of BinarySearch

Program: Sample uses of List.BinarySearch.

using System; using System.Collections.Generic; class BinarySearchDemo{ public static void Main(){ System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US"); List<Point> pointLst = new List<Point>(); // Point is a struct. // Construct points and point list: pointLst.Add(new Point(0,0)); pointLst.Add(new Point(5, 9)); pointLst.Add(new Point(5,4)); pointLst.Add(new Point(7.1,-13)); pointLst.Add(new Point(5,-2)); pointLst.Add(new Point(14,-3.4)); ReportList("The initial point list", pointLst); // Sort point list, using a specific point Comparer. // Notice the PointComparer: // Ordering according to sum of x and y coordinates IComparer<Point> pointComparer = new PointComparer(); pointLst.Sort(pointComparer); ReportList("The sorted point list", pointLst); int res; Point searchPoint; // Run-time error. // Failed to compare two elements in the array. // searchPoint = new Point(5,4); // res = pointLst.BinarySearch(searchPoint); // Console.WriteLine("BinarySearch for {0}: {1}", searchPoint, res); searchPoint = new Point(5,4); res = pointLst.BinarySearch(searchPoint, pointComparer); Console.WriteLine("BinarySearch for {0}: {1}", searchPoint, res); searchPoint = new Point(1,8); res = pointLst.BinarySearch(searchPoint, pointComparer); Console.WriteLine("BinarySearch for {0}: {1}", searchPoint, res); } public static void ReportList<T>(string explanation,List<T> list){ Console.WriteLine(explanation); int cnt = 0; foreach(T el in list){ Console.Write("{0, 3}", el); cnt++; if (cnt%4 == 0) Console.WriteLine(); } if (cnt%4 != 0) Console.WriteLine(); Console.WriteLine(); } } // Compare the sum of the x and y coordinates. // Somewhat non-traditional! public class PointComparer: Comparer<Point>{ public override int Compare(Point p1, Point p2){ double p1Sum = p1.Getx() + p1.Gety(); double p2Sum = p2.Getx() + p2.Gety(); if (p1Sum < p2Sum) return -1; else if (p1Sum == p2Sum) return 0; else return 1; } }

Program: Output from the BinarySearch program.

The initial point list Point:(0,0). Point:(5,9). Point:(5,4). Point:(7.1,-13). Point:(5,-2). Point:(14,-3.4). The sorted point list Point:(7.1,-13). Point:(0,0). Point:(5,-2). Point:(5,4). Point:(14,-3.4). Point:(5,9). BinarySearch for Point:(5,4). : 3 BinarySearch for Point:(1,8). : 3

Program: Searching for a non-existing Point.

using System; using System.Collections.Generic; class BinarySearchDemo{ public static void Main(){ System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US"); List<Point> pointLst = new List<Point>(); // Construct points and point list: pointLst.Add(new Point(0,0)); pointLst.Add(new Point(5, 9)); pointLst.Add(new Point(5,4)); pointLst.Add(new Point(7.1,-13)); pointLst.Add(new Point(5,-2)); pointLst.Add(new Point(14,-3.4)); ReportList("Initial point list", pointLst); // Sort point list, using a specific point Comparer: IComparer<Point> pointComparer = new PointComparer(); pointLst.Sort(pointComparer); ReportList("Sorted point list", pointLst); int res; Point searchPoint; searchPoint = new Point(1,1); res = pointLst.BinarySearch(searchPoint, pointComparer); Console.WriteLine("BinarySearch for {0}: {1}\n", searchPoint, res); if (res < 0){ // search point not found pointLst.Insert(~res, searchPoint); // Insert searchPoint such // that pointLst remains sorted Console.WriteLine("Inserting {0} at index {1}", searchPoint, ~res); ReportList("Point list after insertion", pointLst); } } public static void ReportList<T>(string explanation,List<T> list){ Console.WriteLine(explanation); int cnt = 0; foreach(T el in list){ Console.Write("{0, 3}", el); cnt++; if (cnt%4 == 0) Console.WriteLine(); } if (cnt%4 != 0) Console.WriteLine(); Console.WriteLine(); } } // Compare the sum of the x and y coordinates. // Somewhat non-traditional! public class PointComparer: Comparer<Point>{ public override int Compare(Point p1, Point p2){ double p1Sum = p1.Getx() + p1.Gety(); double p2Sum = p2.Getx() + p2.Gety(); if (p1Sum < p2Sum) return -1; else if (p1Sum == p2Sum) return 0; else return 1; } }

Program: Output from the BinarySearch program - non-existing Point.

Initial point list Point:(0,0). Point:(5,9). Point:(5,4). Point:(7.1,-13). Point:(5,-2). Point:(14,-3.4). Sorted point list Point:(7.1,-13). Point:(0,0). Point:(5,-2). Point:(5,4). Point:(14,-3.4). Point:(5,9). BinarySearch for Point:(1,1). : -3 Inserting Point:(1,1). at index 2 Point list after insertion Point:(7.1,-13). Point:(0,0). Point:(1,1). Point:(5,-2). Point:(5,4). Point:(14,-3.4). Point:(5,9).

Lessons learned Binary search can only be done on sorted lists In order to use binary search, we need - in general - to provide an explicit Comparer object Binary search returns a (non-negative) integer if the element is found The index of the located element Binary search returns a negative integer if the element is not found The complement of this number is a ghost index The index of the element if it had been in the list

Overview of the class LinkedList<T> Slide Annotated slide Contents Index References Textbook

The class LinkedList<T> uses and exposes an auxiliary class LinkedListNode<T>

Reference Tree of generic list types

Members of class LinkedList<T> Constructors LinkedList(),   LinkedList(IEnumerable<T>) Accessors (properties) First, Last, Count Element addition AddFirst(T),   AddFirst(LinkedListNode<T>),   AddLast(T), AddLast(LinkedListNode<T>),   AddBefore(LinkedListNode<T>, T),   AddBefore(LinkedListNode<T>, LinkedListNode<T>), AddAfter(LinkedListNode<T>, T), AddAfter(LinkedListNode<T>, LinkedListNode<T>),   Add(T) Element removal Remove(T),   Remove(LinkedListNode<T>),   RemoveFirst(), RemoveLast(),   Clear() Searching Find(T),   FindLast(T) Boolean queries Contains(T)

The class LinkedListNode<T> Slide Annotated slide Contents Index References Textbook

The class LinkedListNode<T> is sealed, generic class that represents a non-mutable node in a linked list A LinkedListNode can at most belong to a single linked list

Members of LinkedListNode<T> A single constructor LinkedListNode(T) Four properties Next     - getter Previous     - getter List     - getter Value     - getter and setter

LinkedListNode<T> is closely associated with LinkedList<T> There is no public interface for initialization of the properties

Sample use of class LinkedList<T> Slide Annotated slide Contents Index References Textbook

Program: Basic operations on a LinkedList of integers.

using System; using System.Collections.Generic; class LinkedListDemo{ public static void Main(){ LinkedList<int> lst = new LinkedList<int>( new int[]{5, 3, 2, 7, -4, 0}); ReportList("Initial LinkedList", lst); // Using Add. // Compile-time error: 'LinkedList<int>' does not contain a // definition for 'Add' // lst.Add(17); // ReportList("lst.Add(17);" lst); // Add is implemented as an explicit interface implementation ((ICollection<int>)lst).Add(17); ReportList("((ICollection<int>)lst).Add(17);", lst); // Using AddFirst and AddLast lst.AddFirst(-88); lst.AddLast(88); ReportList("lst.AddFirst(-88); lst.AddFirst(88);", lst); // Using Remove. lst.Remove(17); ReportList("lst.Remove(17);", lst); // Using RemoveFirst and RemoveLast lst.RemoveFirst(); lst.RemoveLast(); ReportList("lst.RemoveFirst(); lst.RemoveLast();", lst); // Using Clear lst.Clear(); ReportList("lst.Clear();", lst); } public static void ReportList<T>(string explanation, LinkedList<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.Write("{0, 4}", el); Console.WriteLine(); Console.WriteLine(); } }

Program: Output of the program with basic operations on a LinkedList.

Initial LinkedList 5 3 2 7 -4 0 ((ICollection<int>)lst).Add(17); 5 3 2 7 -4 0 17 lst.AddFirst(-88); lst.AddFirst(88); -88 5 3 2 7 -4 0 17 88 lst.Remove(17); -88 5 3 2 7 -4 0 88 lst.RemoveFirst(); lst.RemoveLast(); 5 3 2 7 -4 0 lst.Clear();

Program: Basic operations on a LinkedList of integers - using LinkedListNodes.

using System; using System.Collections.Generic; class LinkedListNodeDemo{ public static void Main(){ LinkedList<int> lst = new LinkedList<int>( new int[]{5, 3, 2, 7, -4, 0}); ReportList("Initial LinkedList", lst); LinkedListNode<int> node1, node2, node; node1 = lst.First; node2 = lst.Last; // Run-time error. // The LinkedListNode is already in the list. // Error message: The LinkedList node belongs a LinkedList. /* lst.AddLast(node1); */ // Move first node to last node in list lst.Remove(node1); lst.AddLast(node1); ReportList("node1 = lst.First; lst.Remove(node1); lst.AddLast(node1);", lst); // Navigate in list via LinkedListNode objects node1 = lst.First; Console.WriteLine("Third element in list: node1 = lst.First; node1.Next.Next.Value == {0}\n", node1.Next.Next.Value); // Add an integer after a LinkedListNode object lst.AddAfter(node1, 17); ReportList("lst.AddAfter(node1, 17);", lst); // Add a LinkedListNode object after another LinkedListNode object lst.AddAfter(node1, new LinkedListNode<int>(18)); ReportList("lst.AddAfter(node1, new LinkedListNode<int>(18));" , lst); // Navigate in LinkedListNode objects and add an int before a node: node = node1.Next.Next.Next; lst.AddBefore(node, 99); ReportList("node = node1.Next.Next.Next; lst.AddBefore(node, 99); " , lst); // Navigate in LinkedListNode objects and remove a node. node = node.Previous; lst.Remove(node); ReportList("node = node.Previous; lst.Remove(node);" , lst); } public static void ReportList<T>(string explanation, LinkedList<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.Write("{0, 4}", el); Console.WriteLine(); Console.WriteLine(); } }

Program: Output of the program with LinkedListNode operations on a LinkedList.

Initial LinkedList 5 3 2 7 -4 0 node1 = lst.First; lst.Remove(node1); lst.AddLast(node1); 3 2 7 -4 0 5 Third element in list: node1 = lst.First; node1.Next.Next.Value == 7 lst.AddAfter(node1, 17); 3 17 2 7 -4 0 5 lst.AddAfter(node1, new LinkedListNode<int>(18)); 3 18 17 2 7 -4 0 5 node = node1.Next.Next.Next; lst.AddBefore(node, 99); 3 18 17 99 2 7 -4 0 5 node = node.Previous; lst.Remove(node); 3 18 17 2 7 -4 0 5

Time complexity overview: Collection classes Slide Annotated slide Contents Index References Textbook

Assume that we work on a collection with n elements

Table. Time complexities of important operations in the classes Collection<T>, List<T>, and LinkedList<T>.

Operation Collection<T> List<T> LinkedList<T> this[i] O(1) O(1) - Count O(1) O(1) O(1) Add(e) O(1) or O(n) O(1) or O(n) O(1) Insert(i,e) O(n) O(n) - Remove(e) O(n) O(n) O(n) IndexOf(e) O(n) O(n) - Contains(e) O(n) O(n) O(n) BinarySearch(e) - O(log n) - Sort() - O(n log n) or O(n2) - AddBefore(lln) - - O(1) AddAfter(lln,e) - - O(1) Remove(lln) - - O(1) RemoveFirst() - - O(1) RemoveLast() - - O(1)

Reference Wikipedia: Big O Notation

Using Collections through Interfaces Slide Annotated slide Contents Index References Textbook

It is an advantage to use collections via interfaces instead of classes If possible, only use collection classes in instantiations, just after new This leads to programs with fewer bindings to concrete implementations of collections With this approach, it is easy to replace a collection class with another

Program: An animal program - firmly bound to Collections - a problematic choice.

using System; using System.Collections.Generic; using System.Collections.ObjectModel; class CollectionInterfaceDemo{ public static void Main(){ Collection<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, Collection<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } public static void ReportFemaleMale(Collection<Animal> list){ int numberOfMales = 0, numberOfFemales = 0; foreach(Animal a in list) if (a.Sex == Sex.Male) numberOfMales++; else if (a.Sex == Sex.Female) numberOfFemales++; Console.WriteLine("Males: {0}, Females: {1}", numberOfMales, numberOfFemales); } public static void ReportGroup(Collection<Animal> list){ int numberOfMammals = 0, numberOfBirds = 0, numberOfFish = 0; foreach(Animal a in list) if (a.Group == AnimalGroup.Mammal) numberOfMammals++; else if (a.Group == AnimalGroup.Bird) numberOfBirds++; else if (a.Group == AnimalGroup.Fish) numberOfFish++; Console.WriteLine("Mammals: {0}, Birds: {1}, Fish: {2}", numberOfMammals, numberOfBirds, numberOfFish); } }

Program: A program based on ICollection<Animal> - with a Collection<Animal>.

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); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } public static void ReportFemaleMale(ICollection<Animal> list){ int numberOfMales = 0, numberOfFemales = 0; foreach(Animal a in list) if (a.Sex == Sex.Male) numberOfMales++; else if (a.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; foreach(Animal a in list) if (a.Group == AnimalGroup.Mammal) numberOfMammals++; else if (a.Group == AnimalGroup.Bird) numberOfBirds++; else if (a.Group == AnimalGroup.Fish) numberOfFish++; Console.WriteLine("Mammals: {0}, Birds: {1}, Fish: {2}", numberOfMammals, numberOfBirds, numberOfFish); } }

Program: A program based on ICollection<Animal> - with a List<Animal>.

using System; using System.Collections.Generic; using System.Collections.ObjectModel; class CollectionInterfaceDemo{ public static void Main(){ ICollection<Animal> lst = new List<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); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } public static void ReportFemaleMale(ICollection<Animal> list){ int numberOfMales = 0, numberOfFemales = 0; foreach(Animal a in list) if (a.Sex == Sex.Male) numberOfMales++; else if (a.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; foreach(Animal a in list) if (a.Group == AnimalGroup.Mammal) numberOfMammals++; else if (a.Group == AnimalGroup.Bird) numberOfBirds++; else if (a.Group == AnimalGroup.Fish) numberOfFish++; Console.WriteLine("Mammals: {0}, Birds: {1}, Fish: {2}", numberOfMammals, numberOfBirds, numberOfFish); } }

Program: Output from animal collection programs.

Animal: Cat(Male) Animal: Dog(Female) Animal: Mouse(Male) Animal: Rat(Male) Animal: Mouse(Female) Animal: Rat(Male) Animal: Herring(Female) Animal: Eagle(Male) Males: 5, Females: 3 Mammals: 6, Birds: 1, Fish: 1

A dictionary implements an associative array

Dictionaries map keys to values a given key can - at most - be mapped to a single value are collections of key-value pairs implement an efficient connection from instances of keys to instances of values are typically implemented by means of hashtables

References Associative arrays Collection types

Overview of Generic Dictionaries in C# Slide Annotated slide Contents Index References Textbook

Classes and Interfaces related to Dictionary collections in C#

References Similar list overview Similar non-generic overview

The class and interface inheritance tree related to Dictionaries

Dictionaries are also known as maps

The interface IDictionary<K,V> Slide Annotated slide Contents Index References Textbook

The interface IDictionary<K,V> is a subinterface of ICollection<KeyValuePair<K,V>>

Reference The ICollection<T> interface

Operations in the interface IDictionary<K,V> The operations prescribed in ICollection<KeyValuePair<K,V>> The operations prescribed in IEnumerable<KeyValuePair<K,V>> V this[K key]     - both getter and setter; the setter adds or mutates void Add(K key, V value)     - only possible if key is not already present bool Remove(K key) bool ContainsKey(K key) bool TryGetValue(K key, out V value) ICollection<K>Keys     - getter ICollection<V>Values     - getter

Overview of the class Dictionary<K,V> Slide Annotated slide Contents Index References Textbook

Reference The generic dictionary tree

Members of class Dictionary<K,V> Constructors Dictionary(),   Dictionary(IDictionary<K,V>),   Dictionary(IEqualityComparer<K>),   Dictionary(int),   and more Value addition Add(K, V), this[K] = V         if K is not already in the dictionary Value mutation this[K] = V         if K is already in the dictionary Element removal Remove(K),   Clear() Value access this[K],   Values,   TryGetValue(K, out V) Key access Keys Boolean queries ContainsKey(K),   ContainsValue(V) Others Count Comparer

Sample use of class Dictionary<K,V> Slide Annotated slide Contents Index References Textbook

A dictionary that maps Persons to BankAccounts

Program: A class Person.

using System; public class Person{ private string name; private DateTime? dateOfBirth; public Person (string name){ this.name = name; this.dateOfBirth = null; } public Person (string name, DateTime? dateOfBirth){ this.name = name; this.dateOfBirth = dateOfBirth; } public string Name{ get {return name;} } public DateTime? DateOfBirth{ get {return dateOfBirth;} } public override string ToString(){ return "Person: " + name + " " + dateOfBirth; } }

Program: A class BankAccount.

using System; public class BankAccount { private double interestRate; private double balance; public BankAccount(double interestRate) { this.interestRate = interestRate; this.balance = 0.0; } public double Balance { get{ return balance; } } public void Withdraw (double amount) { balance -= amount; } public void Deposit (double amount) { balance += amount; } public void AddInterests() { balance = balance + balance * interestRate; } public override string ToString() { return "The account holds " + + balance + " kroner"; } }

Program: A program working with Dictionary<Person,BankAccount>.

using System; using System.Collections.Generic; class DictionaryDemo{ public static void Main(){ IDictionary<Person, BankAccount> bankMap = new Dictionary<Person,BankAccount>(new PersonComparer()); // Make bank accounts and person objects BankAccount ba1 = new BankAccount(0.01), ba2 = new BankAccount(0.02), ba3 = new BankAccount(0.03), ba4 = new BankAccount(0.04); Person p1 = new Person("Kurt"), p2 = new Person("Maria"), p3 = new Person("Francoi"); ba1.Deposit(100); ba2.Deposit(200); ba3.Deposit(300); // Populate the bankMap: bankMap.Add(p1, ba1); bankMap.Add(p2, ba2); bankMap.Add(p3, ba3); 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(); } }

Program: Output from the Dictionary<Person,BankAccount> program.

Initial map Person: Kurt : The account holds 100 kroner Person: Maria : The account holds 200 kroner Person: Francoi : The account holds 300 kroner The account holds 100 kroner bankMap[p1] = ba4; Person: Kurt : The account holds 0 kroner Person: Maria : The account holds 200 kroner Person: Francoi : The account holds 300 kroner ba4.Deposit(400); bankMap[new Person("Maria")] = ba4; Person: Kurt : The account holds 400 kroner Person: Maria : The account holds 400 kroner Person: Francoi : The account holds 300 kroner Account: The account holds 400 kroner. Boolean result True Account: . Boolean result False bankMap.Remove(p1); Person: Maria : The account holds 400 kroner Person: Francoi : The account holds 300 kroner bankMap.Remove(new Person("Francoi")); Person: Maria : The account holds 400 kroner

Exercise 12.4. 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.

Notes about Dictionary Classes Slide Annotated slide Contents Index References Textbook

Reference The generic dictionary tree

Class Dictionary<K,V> Based on a hash table Requires that the keys in type K can be compared by an Equals operation Key values should not be mutated The efficiency of class dictionary relies on a good hash function for the key type K Consider overriding the method GetHashCode in class K A dictionary is enumerated in terms of the struct KeyValuePair<K,V> Class SortedDictionary<K,V> Based on a binary search tree Requires an IComparer for keys of type K - for ordering purposes Provided when a sorted dictionary is constructed Class SortedList<K,V> Based on a sorted collection of key/value pairs A resizeable array Requires an IComparer for keys, just like SortedDictionary<K,V>. Requires less memory than SortedDictionary<K,V>.

Time complexity overview: Dictionary classes Slide Annotated slide Contents Index References Textbook

Assume that we work on a dictionary with n elements

Table. Time complexities of important operations in the classes Dictionary<K,V>, SortedDictionary<K,V>, and SortedList<K,V>.

Operation Dictionary<K,V> SortedDictionary<K,V> SortedList<K,V> this[key] O(1) O(log n) O(log n) or O(n) Add(key,value) O(1) or O(n) O(log n) O(n) Remove(key) O(1) O(log n) O(n) ContainsKey(key) O(1) O(log n) O(log n) ContainsValue(value) O(n) O(n) O(n)

Notes Add(key,value) in Dictionary<K,V>: Worst case if the hashtable must be enlarged Constant times indicate amortized complexity

The non-generic collection classes store data of type Object

The class and interface inheritance tree related to collections

References Similar generic List overview Similar generic Dictionary overview

Notes about non-generic Collections Slide Annotated slide Contents Index References Textbook

Class Array - in the System namespace The base class of all native C# arrays Contains lots of useful method - Still useful Class ArrayList - in System.Collections Replaced by List<T> in System.Collections.Generic Class Hashtable - in System.Collections Replaced by Dictionary<K, V> in System.Collections.Generic Interface ICollection - System.Collections Contains very few members - Count and CopyTo ICollection<T> is more comprehensive - Add, Remove, Count, CopyTo, and more Class BitArray Of non-generic nature - Still very useful Can be used for simple simulation of set of integers

The Iterator design pattern provides sequential access to an aggregated collection. Iterators are known as Enumerators in C#.

Reference Sample use of IEnumerator and IEnumerable

Qualities of Iterators Provides for a smaller client interface of the collection class All members associated with traversals have been refactored to the iterator class Makes it possible to have several simultaneous traversals Does not reveal the internal representation of the collection

In C# iterators are typically used indirectly, via foreach. Still, it is possible to used iterators directly.

Exercise 12.6. 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.

Exercise 12.6. 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.

Making iterators with yield return Slide Annotated slide Contents Index References Textbook

The yield return statement can be used to define iterators (enumerators) in an easy, high-level fashion

Program: A collection of up to three instance variables of type T - with an iterator.

using System; using System.Collections.Generic; using System.Collections; public class GivenCollection<T> : IEnumerable<T>{ private T first, second, third; private bool firstDefined, secondDefined, thirdDefined; public GivenCollection(){ this.firstDefined = false; this.secondDefined = false; this.thirdDefined = false; } public GivenCollection(T first){ this.first = first; this.firstDefined = true; this.secondDefined = false; this.thirdDefined = false; } public GivenCollection(T first, T second){ this.first = first; this.second = second; this.firstDefined = true; this.secondDefined = true; this.thirdDefined = false; } public GivenCollection(T first, T second, T third){ this.first = first; this.second = second; this.third = third; this.firstDefined = true; this.secondDefined = true; this.thirdDefined = true; } public int Count(){ int res; if (!firstDefined) res = 0; else if (!secondDefined) res = 1; else if (!thirdDefined) res = 2; else res = 3; return res; } public IEnumerator<T> GetEnumerator(){ if (firstDefined) yield return first; if (secondDefined) yield return second; // not else if (thirdDefined) yield return third; // not else } IEnumerator IEnumerable.GetEnumerator(){ return GetEnumerator(); } }

Program: A sample iteration of the three instance variable collection.

using System; class Client{ public static void Main(){ GivenCollection<int> gc = new GivenCollection<int>(7,5,3); Console.WriteLine("Number of elements in givenCollection: {0}", gc.Count()); foreach(int i in gc){ // Output: 7 5 3 Console.WriteLine(i); } } }

Exercise 12.7. The iterator behind a yield

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

References The IntSequence Composite The IntSequence Composite classes

Program: The abstract class IntSequence - Revisited.

public abstract class IntSequence: IEnumerable { public abstract IEnumerator GetEnumerator(); public abstract int? Min {get;} public abstract int? Max {get;} }

Program: The class IntInterval - Revisited.

public class IntInterval: IntSequence{ private int from, to; public IntInterval(int from, int to){ this.from = from; this.to = to; } public override int? Min{ get {return Math.Min(from,to);} } public override int? Max{ get {return Math.Max(from,to);} } public override IEnumerator GetEnumerator (){ if (from < to) for(int i = from; i <= to; i++) yield return i; else for(int i = from; i >= to; i--) yield return i; } }

Program: The class IntSingular - Revisited.

public class IntSingular: IntSequence{ private int it; public IntSingular(int it){ this.it = it; } public override int? Min{ get {return it;} } public override int? Max{ get {return it;} } public override IEnumerator GetEnumerator(){ yield return it; } }

Program: The class IntCompSeq - Revisited.

public class IntCompSeq: IntSequence{ private IntSequence s1, s2; public IntCompSeq(IntSequence s1, IntSequence s2) { this.s1 = s1; this.s2 = s2; } public override int? Min{ get {return (s1.Min < s2.Min) ? s1.Min : s2.Min;} } public override int? Max{ get {return (s1.Max > s2.Max) ? s1.Max : s2.Max;} } public override IEnumerator GetEnumerator (){ foreach(int i in s1) yield return i; foreach(int i in s2) yield return i; } }

Program: An application of the integer sequences.

using System; class SeqApp { public static void Main(){ IntSequence isq1 = new IntCompSeq( new IntCompSeq( new IntInterval(3,5), new IntSingular(17) ), new IntCompSeq( new IntInterval(12,7), new IntSingular(29) ) ); IntSequence isq2 = new IntCompSeq( new IntCompSeq( new IntInterval(3,3), new IntCompSeq(new IntInterval(1,5), new IntInterval(15,20))), new IntCompSeq( new IntCompSeq(new IntInterval(-1,-5), new IntInterval(-15,-20)), new IntInterval(12,7))); Console.WriteLine("Min: {0} Max: {1}", isq1.Min, isq1.Max); Console.WriteLine("Min: {0} Max: {1}", isq2.Min, isq2.Max); foreach(int i in isq1) Console.Write("{0,4}", i); Console.WriteLine(); foreach(int i in isq2) Console.Write("{0,4}", i); } }

Program: Output of the integer sequence application program.

Min: 3 Max: 29 Min: -20 Max: 20 3 4 5 17 12 11 10 9 8 7 29 3 1 2 3 4 5 15 16 17 18 19 20 -1 -2 -3 -4 -5 -15 -16 -17 -18 -19 -20 12 11 10 9 8 7

Reference The AnimalFarm Collection

Program: Animalfarm - GetGroup with yield return.

using System; using System.Collections.ObjectModel; using System.Collections.Generic; using System.Collections; public class AnimalFarm: Collection<Animal>{ // Return an iterator of all animals in group g public IEnumerable<Animal> GetGroup(AnimalGroup g){ foreach(Animal a in this) if (a.Group == g) yield return a; } // Additional methods }

Program: A sample client of AnimalFarm.

using System; using System.Collections.ObjectModel; class App{ public static void Main(){ AnimalFarm af = new AnimalFarm(); // Populating the farm with Add af.Add(new Animal("elephant", AnimalGroup.Mammal)); af.Add(new Animal("blueJay", AnimalGroup.Bird)); af.Add(new Animal("giraffe", AnimalGroup.Mammal)); af.Add(new Animal("tiger", AnimalGroup.Mammal)); af.Add(new Animal("goldenEagle", AnimalGroup.Bird)); foreach(Animal a in af.GetGroup(AnimalGroup.Bird)) Console.WriteLine("{0}", a); } }

Program: Program output.

Animal: blueJay(Male) Animal: goldenEagle(Male)

Iterator blocks and yield return Slide Annotated slide Contents Index References

Iterators are implemented by methods made with iterator blocks

Program: A method formed by an iterator block.

IEnumerator<Type> Method() { // iterator block Type t; ... yield return t; ... }

Characteristics The return type of the method must be an enumerator or an enumerable A method with an iterator block is not executed immediately when calling it Instead an enumerable object is created and returned Execution starts when MoveNext is activated on the enumerable object

The compiler transforms a method with an iterator block to an underlying state machine which manages the traversal

Exercise 12.8. 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.

Collected references Contents Index

First generation collection classes Similar non-generic overview Similar dictionary overview The non-generic IEnumerable interface The Iterator Design Pattern The interface IEnumerable<T> The interface ICollection<T> Similar overview of List<T> Tree of generic list types Similar program for List<T> Similar overview of Collection<T> Similar program for Collection<T> Wikipedia: Big O Notation Collection types Associative arrays Similar list overview The ICollection<T> interface The generic dictionary tree Similar generic Dictionary overview Similar generic List overview Sample use of IEnumerator and IEnumerable The IntSequence Composite classes The IntSequence Composite The AnimalFarm Collection

Chapter 12: Collection Classes
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: February 7, 2011, 12:21:16