The MRU List

One of the truisms of search is that if you search for something once, you’re likely to search for it again. In addition, some things are searched for much more often than others. It makes sense, then to cache the results for the most common searches so that you don’t have to query the database or other backing store in order to return results. That way you can satisfy the most common requests very quickly, reducing the load on your back-end database.

The problem, of course, is that you can’t cache all search results. If you could, you wouldn’t need a database to hold the information. The question becomes one of how to determine which results you should store in memory. One method that works very well is the Most Recently Used (MRU) list.

The idea is to keep some small number of the most recently requested results in memory. When somebody performs a search, the program checks the MRU list first. If the results are found in the MRU list, then those results moved to the front of the list. If the requested results are not in the list, then the program queries the database to obtain the results, places those new results at the front of the list, and removes the results from the back of the list--the least recently used results.

Because items are moved back to the front of the list each time they’re requested, the most frequently requested results will remain in the list, and things that are requested infrequently will fall off the back of the list.

This technique works well when searches follow the common pattern: a few terms being much more frequently requested than others. If searches are randomly distributed, the MRU list is not at all affected, because it’s likely that the requested results won’t be in the cache.

The .NET LinkedList class is an excellent choice for implementing an MRU list because moving things around in the list is a constant-time operation. That is, it takes the same amount of time to insert or remove an item in a list of 10,000 items as it does in a list of 10 items.

The MRU List interface requires a way to determine if an item is in the list, and a way to add something to the list. Also, the constructor should let you say how many items the list should hold. That’s really all there is to it, but implementation is just a little bit tricky.

We can build the MRU list as a generic class with two type parameters: the type of object to be stored in the linked list, and the type of key used to search for items. The key is important because the LinkedList.Find method searches the list looking for a particular object reference, rather than a key value. We’ll have to implement our own key search.

The constructor requires two parameters: an integer that specifies the maximum number of items that the MRU list can hold, and a comparison function that can compare a key value against a list object to determine if the object matches the key. The final interface looks like this:


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

namespace MostRecentlyUsedList
{
public delegate bool MruEqualityComparer(K key, T item);

public class MruList
{
private LinkedList items;
private int maxCapacity;
private MruEqualityComparer compareFunc;

public MruList(int maxCap, MruEqualityComparer compFunc)
{
maxCapacity = maxCap;
compareFunc = compFunc;
items = new LinkedList();
}

public T Find(K key)
{
LinkedListNode node = FindNode(key);
if (node != null)
{
items.Remove(node);
items.AddFirst(node);
return node.Value;
}
return default(T);
}

private LinkedListNode FindNode(K key)
{
LinkedListNode node = items.First;
while (node != null)
{
if (compareFunc(key, node.Value))
return node;
node = node.Next;
}
return null;
}

public void Add(T item)
{
// remove items until the list is no longer full.
while (items.Count >= maxCapacity)
{
items.RemoveLast();
}
items.AddFirst(item);
}


}
}


static class Program
{
static private MruList mru;
///

/// The main entry point for the application.
///

[STAThread]
static void Main()
{

mru = new MruList(1000, KeyCompare);

for (int count = 0; count < 1000; count++)
{
mru.Add(new SearchResult("Jim" + count, count));
}
FindItem("Jim999");

}

static private bool KeyCompare(string key, SearchResult item)
{
return key.Equals(item.Name);
}

static private void FindItem(string key)
{
SearchResult rslt = mru.Find(key);
if (rslt == null)
{
Console.WriteLine("’{0}’ not found", key);
}
else
{
Console.WriteLine("’{0}’ is {1}", rslt.Name, rslt.Age);
}

}


}


class SearchResult
{
private string _name;
private int _age;

public SearchResult(string n, int a)
{
_name = n;
_age = a;
}

public string Name
{
get { return _name; }
}

public int Age
{
get { return _age; }
}
}

The MRU List

One of the truisms of search is that if you search for something once, you’re likely to search for it again. In addition, some things are searched for much more often than others. It makes sense, then to cache the results for the most common searches so that you don’t have to query the database or other backing store in order to return results. That way you can satisfy the most common requests very quickly, reducing the load on your back-end database.

The problem, of course, is that you can’t cache all search results. If you could, you wouldn’t need a database to hold the information. The question becomes one of how to determine which results you should store in memory. One method that works very well is the Most Recently Used (MRU) list.

The idea is to keep some small number of the most recently requested results in memory. When somebody performs a search, the program checks the MRU list first. If the results are found in the MRU list, then those results moved to the front of the list. If the requested results are not in the list, then the program queries the database to obtain the results, places those new results at the front of the list, and removes the results from the back of the list--the least recently used results.

Because items are moved back to the front of the list each time they’re requested, the most frequently requested results will remain in the list, and things that are requested infrequently will fall off the back of the list.

This technique works well when searches follow the common pattern: a few terms being much more frequently requested than others. If searches are randomly distributed, the MRU list is not at all affected, because it’s likely that the requested results won’t be in the cache.

The .NET LinkedList class is an excellent choice for implementing an MRU list because moving things around in the list is a constant-time operation. That is, it takes the same amount of time to insert or remove an item in a list of 10,000 items as it does in a list of 10 items.

The MRU List interface requires a way to determine if an item is in the list, and a way to add something to the list. Also, the constructor should let you say how many items the list should hold. That’s really all there is to it, but implementation is just a little bit tricky.

We can build the MRU list as a generic class with two type parameters: the type of object to be stored in the linked list, and the type of key used to search for items. The key is important because the LinkedList.Find method searches the list looking for a particular object reference, rather than a key value. We’ll have to implement our own key search.

The constructor requires two parameters: an integer that specifies the maximum number of items that the MRU list can hold, and a comparison function that can compare a key value against a list object to determine if the object matches the key. The final interface looks like this:


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

namespace MostRecentlyUsedList
{
public delegate bool MruEqualityComparer(K key, T item);

public class MruList
{
private LinkedList items;
private int maxCapacity;
private MruEqualityComparer compareFunc;

public MruList(int maxCap, MruEqualityComparer compFunc)
{
maxCapacity = maxCap;
compareFunc = compFunc;
items = new LinkedList();
}

public T Find(K key)
{
LinkedListNode node = FindNode(key);
if (node != null)
{
items.Remove(node);
items.AddFirst(node);
return node.Value;
}
return default(T);
}

private LinkedListNode FindNode(K key)
{
LinkedListNode node = items.First;
while (node != null)
{
if (compareFunc(key, node.Value))
return node;
node = node.Next;
}
return null;
}

public void Add(T item)
{
// remove items until the list is no longer full.
while (items.Count >= maxCapacity)
{
items.RemoveLast();
}
items.AddFirst(item);
}


}
}


static class Program
{
static private MruList mru;
///

/// The main entry point for the application.
///

[STAThread]
static void Main()
{

mru = new MruList(1000, KeyCompare);

for (int count = 0; count < 1000; count++)
{
mru.Add(new SearchResult("Jim" + count, count));
}
FindItem("Jim999");

}

static private bool KeyCompare(string key, SearchResult item)
{
return key.Equals(item.Name);
}

static private void FindItem(string key)
{
SearchResult rslt = mru.Find(key);
if (rslt == null)
{
Console.WriteLine("’{0}’ not found", key);
}
else
{
Console.WriteLine("’{0}’ is {1}", rslt.Name, rslt.Age);
}

}


}


class SearchResult
{
private string _name;
private int _age;

public SearchResult(string n, int a)
{
_name = n;
_age = a;
}

public string Name
{
get { return _name; }
}

public int Age
{
get { return _age; }
}
}

Factory Method

Definition
Define an interface for creating an object, but let subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclasses.

using System;
using System.Collections;

namespace GangOfFour.Factory
{
///

/// MainApp startup class for Real-World
/// Factory Method Design Pattern.
///

class MainApp
{
///

/// Entry point into console application.
///

static void Main()
{
// Note: constructors call Factory Method
Document[] documents = new Document[2];
documents[0] = new Resume();
documents[1] = new Report();

// Display document pages
foreach (Document document in documents)
{
Console.WriteLine("\n" + document.GetType().Name+ "--");
foreach (Page page in document.Pages)
{
Console.WriteLine(" " + page.GetType().Name);
}
}

// Wait for user
Console.Read();
}
}

// "Product"

abstract class Page
{
}

// "ConcreteProduct"

class SkillsPage : Page
{
}

// "ConcreteProduct"

class EducationPage : Page
{
}

// "ConcreteProduct"

class ExperiencePage : Page
{
}

// "ConcreteProduct"

class IntroductionPage : Page
{
}

// "ConcreteProduct"

class ResultsPage : Page
{
}

// "ConcreteProduct"

class ConclusionPage : Page
{
}

// "ConcreteProduct"

class SummaryPage : Page
{
}

// "ConcreteProduct"

class BibliographyPage : Page
{
}

// "Creator"

abstract class Document
{
private ArrayList pages = new ArrayList();

// Constructor calls abstract Factory method
public Document()
{
this.CreatePages();
}

public ArrayList Pages
{
get{ return pages; }
}

// Factory Method
public abstract void CreatePages();
}

// "ConcreteCreator"

class Resume : Document
{
// Factory Method implementation
public override void CreatePages()
{
Pages.Add(new SkillsPage());
Pages.Add(new EducationPage());
Pages.Add(new ExperiencePage());
}
}

// "ConcreteCreator"

class Report : Document
{
// Factory Method implementation
public override void CreatePages()
{
Pages.Add(new IntroductionPage());
Pages.Add(new ResultsPage());
Pages.Add(new ConclusionPage());
Pages.Add(new SummaryPage());
Pages.Add(new BibliographyPage());
}
}
}

Factory Method:when and where use it:
Class constructors exist so that clients can create an instance of a class. There are situations however, where the client does not, or should not, know which of several possible classes to instantiate. The Factory Method allows the client to use an interface for creating an object while still retaining control over which class to instantiate.
The key objective of the Factory Method is extensibility. Factory Methods are frequently used in applications that manage, maintain, or manipulate collections of objects that are different but at the same time have many characteristics in common. A document management system for example is more extensible if you reference your documents as a collections of IDocuments. These documents may be Text files, Word documents, Visio diagrams, or legal papers. They all have an author, a title, a type, a size, a location, a page count, etc. If a new type of document is introduced it simply has to implement the IDocument interface and it will fit in with the rest of the documents. To support this new document type the Factory Method code may or may not have to be adjusted (depending on how it was implemented - with or without parameters).

Factory Method in .NET Framework
The Factory Method is commonly used in .NET. An example is the System.Convert class which exposes many static methods that, given an instance of a type, returns another new type. For example, Convert.ToBoolean accepts a string and returns
boolean with value true or false depending on the string value (“true” or “false”).
In .NET the Factory Method is typically implemented as a static method which creates an instance of a particular type determined at compile time. In other words, these methods don’t return base classes or interface types of which the true type is only known at runtime. This is exactly where Abstact Factory and Factory Method differ; Abstract Factory methods are virtual or abstract and return abstract classes or interfaces. Factory Methods are abstract and return class types.

Abstract Facotry

Definition
Provide an interface for creating families of related or dependent objects without specifying their concrete classes.
Frequency of use: high

using System;

namespace DoFactory.GangOfFour.Adapter
{

class MainApp
{
///

/// Entry point into console application.
///

static void Main()
{
// Non-adapted chemical compound
Compound unknown = new Compound(Chemical.Unknown);
unknown.Display();

// Adapted chemical compounds
Compound water = new RichCompound(Chemical.Water);
water.Display();

Compound benzene = new RichCompound(Chemical.Benzene);
benzene.Display();

Compound alcohol = new RichCompound(Chemical.Alcohol);
alcohol.Display();

// Wait for user
Console.Read();
}
}

// "Target"

class Compound
{
private Chemical name;
private float boilingPoint;
private float meltingPoint;
private double molecularWeight;
private string molecularFormula;

// Constructor
public Compound(Chemical name)
{
this.name = name;
}

public virtual void Display()
{
Console.WriteLine("\nCompound: {0} -- ", Name);
}

// Properties
public Chemical Name
{
get{ return name; }
}

public float BoilingPoint
{
get{ return boilingPoint; }
set{ boilingPoint = value; }
}

public float MeltingPoint
{
get{ return meltingPoint; }
set{ meltingPoint = value; }
}

public double MolecularWeight
{
get{ return molecularWeight; }
set{ molecularWeight = value; }
}

public string MolecularFormula
{
get{ return molecularFormula; }
set{ molecularFormula = value; }
}
}

// "Adapter"

class RichCompound : Compound
{
private ChemicalDatabank bank;

// Constructor
public RichCompound(Chemical name) : base(name)
{
}

public override void Display()
{
// Adaptee
bank = new ChemicalDatabank();

// Adaptee request methods
BoilingPoint = bank.GetCriticalPoint(Name, State.Boiling);
MeltingPoint = bank.GetCriticalPoint(Name, State.Melting);
MolecularWeight = bank.GetMolecularWeight(Name);
MolecularFormula = bank.GetMolecularStructure(Name);

base.Display();
Console.WriteLine(" Formula: {0}", MolecularFormula);
Console.WriteLine(" Weight : {0}", MolecularWeight);
Console.WriteLine(" Melting Pt: {0}", MeltingPoint);
Console.WriteLine(" Boiling Pt: {0}", BoilingPoint);
}
}

// "Adaptee"

class ChemicalDatabank
{
// The Databank 'legacy API'
public float GetCriticalPoint(Chemical compound, State point)
{
float temperature = 0.0F;

// Melting Point
if (point == State.Melting)
{
switch (compound)
{
case Chemical.Water : temperature = 0.0F; break;
case Chemical.Benzene : temperature = 5.5F; break;
case Chemical.Alcohol : temperature = -114.1F; break;
}
}
// Boiling Point
else if (point == State.Boiling)
{
switch (compound)
{
case Chemical.Water : temperature = 100.0F; break;
case Chemical.Benzene : temperature = 80.1F; break;
case Chemical.Alcohol : temperature = 78.3F; break;
}
}
return temperature;
}

public string GetMolecularStructure(Chemical compound)
{
string structure = "";

switch (compound)
{
case Chemical.Water : structure = "H20"; break;
case Chemical.Benzene : structure = "C6H6"; break;
case Chemical.Alcohol : structure = "C2H6O2"; break;
}
return structure;
}

public double GetMolecularWeight(Chemical compound)
{
double weight = 0.0;
switch (compound)
{
case Chemical.Water : weight = 18.015; break;
case Chemical.Benzene : weight = 78.1134; break;
case Chemical.Alcohol : weight = 46.0688; break;
}
return weight;
}
}

// Enumerations

public enum Chemical
{
Unknown,
Water,
Benzene,
Alcohol
}

public enum State
{
Boiling,
Melting
}
}


.NET optimized sample code
The .NET optimized code demonstrates the same code as above but uses more modern, built-in .NET features. In this example, abstract classes have been replaced by interfaces because the abstract classes do not contain implementation code. Continents are represented as enumerations. The AnimalWorld constructor dynamically creates the desired abstract factory using the Continent enumerated values.
Code in project: DoFactory.GangOfFour.Abstract.NetOptimized
Abstract Factory: when and where use it
The Abstract Factory pattern provides a client with a class that creates objects that are related by a common theme. The classic example is that of a GUI component factory which creates UI controls for different windowing systems, such as, Windows, Motif, or MacOS. If you’re familiar with Java Swing you’ll recognize it as a good example of the use of the Abstract Factory pattern to build UI interfaces that are independent of their hosting platform. From a design pattern perspective, Java Swing succeeded, but applications built on this platform perform poorly and are not very interactive or responsive compared to native Windows or native Motif applications.
Over time the meaning of the Abtract Factory pattern has changed somewhat compared to the original GoF definition. Today, when developers talk about the Abstract Factory pattern they do not only mean the creation of a ‘family of related or dependent’ objects but also include the creation of individual object instances.
Next are some reasons and benefits for creating objects using an Abstract Factory rather than calling constructors directly:
Constructors are limited in their control over the overall creation process. If your application needs more control consider using a Factory. These include scenarios that involve object caching, sharing or re-using of objects, and applications that maintain object and type counts.

There are times when the client does not know exactly what type to construct. It is easier to code against a base type or interface and a factory can take parameters or other context-based information to make this decision for the client. An example of this are the provider specific ADO.NET objects (DbConnection, DbCommand, DbDataAdapter, etc).
Constructors don’t communicate their intention very well because they must be named after their class (or Sub New in VB.NET). Having numerous overloaded constructors may make it hard for the client developer to decide which constructor to use. Replacing constructors with intention-revealing creation methods are sometimes preferred. An example follows:
Several overloaded constructors. Which one should you use?

// C#
public Vehicle (int passengers)
public Vehicle (int passengers, int horsePower)
public Vehicle (int wheels, bool trailer)
public Vehicle (string type)
' VB.NET
public Sub New (Byval passengers As Integer)
public Sub New (Byval passengers As Integer, _
Byval horsePower As Integer)
public Sub New (Byval wheels As Integer wheels, _
Byval trailer As Boolean)
public Sub New (Byval type As String)
The Factory pattern makes code more expressive and developers more productive
// C#
public Vehicle CreateCar (int passengers)
public Vehicle CreateSuv (int passengers, int horsePower)
public Vehicle CreateTruck (int wheels, bool trailer)
public Vehicle CreateBoat ()
public Vehicle CreateBike ()
' VB.NET
public Function CreateCar (Byval passengers As Integer) As Vehicle
public Function CreateSuv (Byval passengers As Integer, _
Byval horsePower As Integer) As Vehicle
public Function CreateTruck (Byval wheels As Integer, _
Byval trailer As Boolean) As Vehicle
public Function CreateBoat () As Vehicle
public Function CreateBike () As Vehicle

Abstract Factory in the .NET Framework
ADO.NET 2.0 includes two new Abstract Factory classes that offer provider independent data access techniques. They are: DbProviderFactory and DbProviderFactories. The DbProviderFactory class creates the ‘true’ (i.e. the database specific) classes you need, such as SqlClientConnection, SqlClientCommand, and SqlClientDataAdapter. Each managed provider (such as SqlClient, OleDb, ODBC, and Oracle) has its own DbProviderFactory class. DbProviderFactory objects are created by the DbProviderFactories class, which itself is a factory class. In fact, it is a factory of factories -- it manufactures different factories, one for each provider.
When Microsoft talks about Abstract Factories they mean types that expose factory methods as virtual or abstract instance functions and return an abstract class or interface. Below is an example from .NET:
// C#
public abstract class StreamFactory
{
public abstract Stream CreateStream();
}
' VB.NET
Public MustInherit Class StreamFactory
Public MustOverride Function CreateStream() As Stream
End Class
In this scenario your factory type inherits from StreamFactory and is used to dynamically select the actual Stream type being created:
// C#
public class MemoryStreamFactory : StreamFactory
{
...
}
' VB.NET
Public Class MemoryStreamFactory
Inherits StreamFactory
...
End Class

The naming convention in .NET is to appends the word ‘Factory’ to the name of
that is being created. For example, a class that manufactures widget objects would
named WidgetFactory. A search through the libraries for the word ‘Factory’ reveals numerous classes that are implementations of the Factory design pattern.