Caching using a Generic Step Function

Suppose we have decided to take up the challenge of the Yes option in my last blog entry Simulating Connectivity in a Disconnected World and we need to have a cache to achieve acceptable performance. An ordinary cache which can only cache single values based on a key isn’t enough because we also want to cache the sorted lists.

Suppose for example we execute the query ”Find First 20 Clients where ClientName > ‘C’ order by ClientName and the 20th client we find is “Capital Associates”. Then we’d like to be able add the list of 20 clients that we found to the cache using a cache key of Range(’C’, ‘Capital Associates’)).

So now our cache looks something like a mathematical step function where we have assigned a value to range of keys.  In this case the value we have assigned is a list of key value pairs.

Using C# interfaces lets explore how we might make this vague idea more explicit. Lets start with the idea expressed by Range(C’,’Capital Associates’) first. Ranges are bounded by a lower and upper bound so lets begin there.

First we describe the common behavior of lower and upper bounds in an interface IBound.  Note that I am making these immutable by only providing getters and not setters.

public interface IBound<T>
where T : IComparable
    bool HasValue {get;}
    bool IncludesValue {get;}
    T Value {get;}
    bool IsUnbounded {get;}
    bool IsEmpty{get;}

Next we describe the specifics of lower and upper bounds.  We can define a ILowerBound as IComparable based on set inclusion by saying that lower bound X is less than lower bound Y if the set of points satisfying X contains the set of points satisfying Y.

  1. Unbounded  is the smallest possible lower bound  
  2. LowerBound(>= X) is smaller than LowerBound(> X)
  3. If X  <  Y then LowerBound(X) < LowerBound(Y)
  4. Empty is the largest possible lower bound

We can define a IRange as a lower bound intersected with an upper bound.  

public interface ILowerBound<T> : IBound<T>, IComparable
where T : IComparable
    bool Contains(T value);
    IUpperBound<T> Complement();
    ILowerBound<T> Union(ILowerBound<T> lowerBound);
    ILowerBound<T> Intersect(ILowerBound<T> lowerBound);
    IRange<T> Intersect(IUpperBound<T> upperBound);

public interface IUpperBound<T> : Bound<T>, IComparable
where T : IComparable
    bool Contains(T value);
    ILowerBound Complement();
    IUpperBound<T> Union(IUpperBound<T> upperBound);
    IUpperBound<T> Intersect(IUpperBound<T> upperBound);
    IRange<T> Intersect(ILowerBound<T> lowerBound);

 public interfaces IRange<T>
where T : IComparable
    bool Contains(T value);
    ILowerBound<T> LowerBound { get;}
    IUpperBound<T> UpperBound { get;}
    IRange<T> Intersect(IRange<T> range);
    IRange<T> Minus(IRange<T> range);
    bool IsEmpty { get; set;}
    bool IsUnbounded { get; set;}
    bool Contains(IRange<T> range);

Next we are going to need a way to represent the results of the query.  I will define a PointFunction to represent the query results and as a tool for implementing the step function.  We will need functionality similar to a SortedList where we sort the list by the key but will also need the added functionality of finding the first key satisfying a lower bound (TryGetFirstKey), the last key satisfying an upper bound (TryGetLastKey), and the ability to remove a range of values (RemoveValues).

public interface IPointFunction<TKey, TValue>
where TKey : IComparable
    TValue this[TKey key] { get; set;}
    bool HasValue(TKey key);
    void SetValue(TKey key, TValue value);
    void RemoveValue(TKey key);
    TValue GetValue(TKey key);
    bool TryGetValue(TKey key, out TValue value);
    bool TryGetFirstKey(ILowerBound<TKey> lowerBound, out TKey key);
    bool TryGetLastKey(IUpperBound<TKey> upperBound, out TKey key);
    void RemoveValues(IRange<TKey> range);

With the preliminaries out of the way we can finally define an interface for a step function. I can inherit from IPointFunction and just need to add a little functionality associated with setting the value for a range of keys.

public interface IStepFunction : IPointFunction
where TKey : IComparable
    TValue this[IRange range] {set;}
    void SetValue(IRange range, TValue value);
    IRange<TKey> GetRange(TKey key);


One Response to “Caching using a Generic Step Function”

  1. Bill Hamaker’s Blog » Blog Archive » Implementing a Generic Step Function Says:

    […] Bill Hamaker’s Blog Just another weblog « Caching using a Generic Step Function […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: