One problem related to composite pattern is how to implement operations over child collections. Composite classes have children and leaf classes not. There are many ways how to solve the problem of where and how to keep child nodes collection. In this posting I go through different options and analyze those solutions through different code examples.
Problem
Leaf classes in composite pattern inherit also methods and properties that are used by composite classes. Leaf classes cannot always throw exception when some composite class method is called. For some cases we need leaf classes to return similar data to one that composite class returns. How to make leaf classes behave like composite classes with not much overhead?
We will use media folder example code from my composite pattern posting and we try to add playlists support to our sample application.
Adding playlists support
We will extend our media item base class with new members:
- Id – media item ID used for unique identification,
- GetItems() – returns list of media item child nodes.
- Find() – return list of media item child nodes that meet the criteria.
If we write general Find() method then we can use it also for other purposes. We need GetItems() method for search over media items hierarchy.
public abstract class MediaItem
{
public virtual int Id { get; set; }
public virtual string Title { get; protected set; }
public abstract void Play();
public abstract void Add(MediaItem item);
public abstract void Remove(MediaItem item);
public abstract int Count();
public abstract bool IsComposite { get; }
public abstract IEnumerable<MediaItem> GetChildren();
public abstract IEnumerable<MediaItem> Find(Func<MediaItem, bool> finder);
}
As media folders may contain subfolders with media files we need something that makes also subfolder searchable through LINQ. Instead of inventing the wheel we use simple code from David Jade’s blog post Using LINQ to Objects for recursion:
static public class LinqExtensions
{
static public IEnumerable<T> Descendants<T>(this IEnumerable<T> source,
Func<T, IEnumerable<T>> DescendBy)
{
foreach (T value in source)
{
yield return value;
foreach (T child in DescendBy(value).Descendants<T>(DescendBy))
{
yield return child;
}
}
}
}
Using Descendants<T>() extension method with Func that returns child nodes from media items we can write queries over all media items in hierarchy. So, our code for playlists will look like this:
var playlist = new int[] { 1, 3, 6 };
var items = folder.Find(i => playlist.Contains(i.Id) && !i.IsComposite);
foreach (var item in items)
Console.WriteLine(item.Title);
We come back to this code later.
Child node collections
Now we have to decide what we will do with child node collections. There are several options:
- Define child node collection in MediaItem class.
- Define child node collection in composite classes.
- Use empty collection with leaf classes.
Read-only collections. We will use read-only collections in public surface of media items. If we want to apply reference back to parent object then we must change the parent reference when child is moved from one parent to another. This is why we have add and remove operations as methods.
Defining child node collection in base class
If we define child collections in MediaItem class then all leaf classes have these collections too. They do nothing with these classes but still they have those classes instantiated. If we have many leaf objects then those lists just waste memory.
Defining child nodes collection in composite classes
If collctions for child nodes are defined only in composite implementations then leafs are free of collections. The question is now what should leaf classes do when GetItems() is called. We can throw exception:
public override IEnumerable<MediaItem> GetChildren()
{
throw new NotImplementedException();
}
But this is not good idea because then we have to check if class is leaf or not and our LINQ queries are not so generic anymore – we cannot write searches over all media items. We can also return null:
public override IEnumerable<MediaItem> GetChildren()
{
return null;
}
Now we havenew problem – our LINQ method doesn’t expect child nodes collection to be null. It just breaks. Of course, we can make the extension method more safe and ignore nulls but then we end up with hacks specific to our implementation problems.
Using empty collections with leaf classes
We can make leaf classes return empty collections when child nodes are asked:
public override IEnumerable<MediaItem> GetChildren()
{
return new ReadOnlyCollection<MediaItem>(new List<MediaItem>());
}
This solution doesn’t force MediaItem to keep references to lists but creating two new objects per method call may lead to poor performance. Here is one trick we can do: we can use singleton pattern for dummy list that leaf classes return.
We define this dummy list in static scope of MediaItem class. There’s no danger of threading issues as we show this dummy class as read-only collection. There are now operations that will change the data in base collection:
protected static readonly IReadOnlyCollection<MediaItem> Dummy;
static MediaItem()
{
var dummyList = new List<MediaItem>();
Dummy = new ReadOnlyCollection<MediaItem>(dummyList);
}
And here is GetChildren() method for leaf classes:
public override IEnumerable<MediaItem> GetChildren()
{
return Dummy;
}
Now leaf classes return list when child nodes are asked and there’s no performance hit as this is the same list instance for all GetChildren() calls.
New media library code
Here is the full code for new media library.
public abstract class MediaItem
{
public virtual int Id { get; set; }
public virtual string Title { get; protected set; }
public abstract void Play();
public abstract void Add(MediaItem item);
public abstract void Remove(MediaItem item);
public abstract int Count();
public abstract bool IsComposite { get; }
public abstract IEnumerable<MediaItem> GetChildren();
public IEnumerable<MediaItem> Find(Func<MediaItem, bool> finder)
{
return GetChildren().Descendants(i => i.GetChildren()).Where(finder);
}
protected static readonly IReadOnlyCollection<MediaItem> Dummy;
static MediaItem()
{
var dummyList = new List<MediaItem>();
Dummy = new ReadOnlyCollection<MediaItem>(dummyList);
}
}
public class MediaFolder : MediaItem
{
private readonly IList<MediaItem> _items;
private readonly IReadOnlyCollection<MediaItem> _children;
public MediaFolder(string title)
{
Title = title;
_items = new Collection<MediaItem>();
_children = new ReadOnlyCollection<MediaItem>(_items);
}
public override void Play()
{
foreach (var item in _items)
item.Play();
}
public override void Add(MediaItem item)
{
_items.Add(item);
}
public override void Remove(MediaItem item)
{
_items.Remove(item);
}
public override int Count()
{
return _items.Count;
}
public override bool IsComposite
{
get { return true; }
}
public override IEnumerable<MediaItem> GetChildren()
{
return _children;
}
}
public class MusicItem : MediaItem
{
private readonly string _path;
public MusicItem(string path, string title)
{
_path = path;
Title = title;
}
public override void Play()
{
// load file and play it
}
public override void Add(MediaItem item)
{
throw new NotImplementedException();
}
public override void Remove(MediaItem item)
{
throw new NotImplementedException();
}
public override int Count()
{
throw new NotImplementedException();
}
public override bool IsComposite
{
get { return false; }
}
public override IEnumerable<MediaItem> GetChildren()
{
return Dummy;
}
}
static public class LinqExtensions
{
static public IEnumerable<T> Descendants<T>(this IEnumerable<T> source,
Func<T, IEnumerable<T>> DescendBy)
{
foreach (T value in source)
{
yield return value;
foreach (T child in DescendBy(value).Descendants<T>(DescendBy))
{
yield return child;
}
}
}
}
To test if our playlists work we will use the following code:
class Program
{
static void Main(string[] args)
{
var folder = new MediaFolder("Home");
var balladsFolder = new MediaFolder("Ballads");
balladsFolder.Add(new MusicItem("", "Mötley Crue - Without You") { Id = 1 });
balladsFolder.Add(new MusicItem("", "Napalm Death - Evolved As One") { Id = 2 });
balladsFolder.Add(new MusicItem("", "Poison - Something To Believe In") { Id = 3 });
folder.Add(balladsFolder);
var thrashFolder = new MediaFolder("Thrash");
thrashFolder.Add(new MusicItem("", "Kreator - Violent Revolution") { Id = 4 });
thrashFolder.Add(new MusicItem("", "Exodus - War Is My Shepherd") { Id = 5 });
thrashFolder.Add(new MusicItem("", "Metallica - Whiplash") { Id = 6 });
folder.Add(thrashFolder);
Console.WriteLine("\r\nPlaylist:");
var playlist = new int[] { 1, 3, 6 };
var items = folder.Find(i => playlist.Contains(i.Id) && !i.IsComposite);
foreach (var item in items)
Console.WriteLine(item.Title);
Console.WriteLine(" \r\nPress any key to continue ...");
Console.ReadLine();
}
}
Running this code we get the following result:
Wrapping up
Dealing with child nodes collections in composite pattern needs some analysis to make good implementation decisions. In this example we made composite classes use their internal collections. Leaf classes are using static dummy list that is defined in base class. Instead of creating new empty instances in GetChildren() method we use one static readonly instance as we don’t allow direct modification of child nodes collection. Our solution is pretty good as we can also use LINQ to Objects queries over whole folder structure.
View Comments (0)