Implementing a Generic Step Function

In my last blog entry Caching using a Generic Step Function I specified an interface for a step function.  So now I want to move on to describing one neat way to actually implement one.   The trick that I will use is to first do it for a special case which I will call SimpleStepFunction<TKey, TValue> and then show how an arbitrary step function  can be defined using SimpleStepFunction<LowerBound<TKey>,Box<TValue>>.  Here I have defined a generic single value container class Box<T> and make use of the fact that LowerBound<TKey> is IComparable.

The special case SimpleStepFunction<TKey, TValue> has the following restrictions

1. TKey has a minimum value which is smaller than all other values.
2. The step function is defined for all values.  We don’t have implement RemoveValue or HasValue.
3. Values are only set for half open ranges of the form (>= X and < Y).

With these restrictions a step function can be represented simply by a sorted list of key value pairs where the first key is the minimum value of TKey.    If we have already implemented a PointFunction<TKey> as described in the previous blog entry then we can implement SimpleStepFunction as follows.

public class SimpleStepFunction<TKey, TValue>
    where TKey : IComparable
{
    // private fields
    private PointFunction<TKey, TValue> _pointFunction;
    // constructors
    public SimpleStepFunction(TKey minKey, TValue value)
    {
    _pointFunction = new PointFunction<TKey, TValue>();
    _pointFunction.SetValue(minKey, value);
    }
    // methods
    public TValue GetValue(TKey key)
    {
    TKey lastKey = default(TKey);
    UpperBound<TKey> upper = new UpperBound<TKey>(key, false);
    _pointFunction.TryGetLastKey(upper, out lastKey);
    return _pointFunction.GetValue(lastKey);
    }    public void SetValue(Range<TKey> range, TValue value)
    {
    TKey lastKey = default(TKey);
    // if necessary insert a new value at the upper end of range
    if (range.UpperBound.HasValue &&
       !_pointFunction.HasValue(range.UpperBound.Value))
   {
   _pointFunction.TryGetLastKey(range.UpperBound, out lastKey);
   TValue lastValue = _pointFunction.GetValue(lastKey);
   _pointFunction.SetValue(range.UpperBound.Value, lastValue);
   }
   // if necessary insert the value at the lower end of range
    _pointFunction.TryGetLastKey(range.LowerBound.Complement(), out lastKey);
    if (!_pointFunction.GetValue(lastKey).Equals(value))
    {
    _pointFunction.SetValue(range.LowerBound.Value, value);
    }
    // remove any existing values inside the range
    LowerBound<TKey> lower = new LowerBound<TKey>(range.LowerBound.Value, false);
    _pointFunction.RemoveValues(new Range<TKey>(lower, range.UpperBound));
    }
}

Now that I have defined SimpleStepFunction I can show a partial implemention of StepFunction.

public class StepFunction<TKey, TValue>
 where TKey : IComparable
{
 // private fields
 private SimpleStepFunction<LowerBound<TKey>, Box<TValue>>
  _stepFunction;
 // constructor
 public StepFunction() { }
 // methods
 public bool HasValue(TKey key)
 {
  LowerBound<TKey> lower = new LowerBound<TKey>(key, true);
  return _stepFunction.GetValue(lower).HasValue;
 }
 public TValue GetValue(TKey key)
 {
  LowerBound<TKey> lower = new LowerBound<TKey>(key, true);
  return _stepFunction.GetValue(lower).Value;
 }
 public void SetValue(Range<TKey> range, TValue value)
 {
  LowerBound<LowerBound<TKey>> lower =
   new LowerBound<LowerBound<TKey>>(range.LowerBound, true);
  UpperBound<UpperBound<TKey>> upper =
   new UpperBound<UpperBound<TKey>>(range.UpperBound, true);
  Range<LowerBound<TKey>> r = new Range<LowerBound<TKey>>(lower);
  _stepFunction.SetValue(r, new SingleValue<TValue>(value));
 }
 public void RemoveValues(Range<TKey> range)
 {
  LowerBound<LowerBound<TKey>> lower =
   new LowerBound<LowerBound<TKey>>(range.LowerBound, true);
  UpperBound<UpperBound<TKey>> upper =
   new UpperBound<UpperBound<TKey>>(range.UpperBound, true);
  Range<LowerBound<TKey>> r = new Range<LowerBound<TKey>>(lower);
  _stepFunction.SetValue(r, new Box<TValue>());
 }
}