Maintaining a cache structure with elements

Question

I have some code which is designed for the following purposes:

1. Implement a cache structure which stores cached elements, as well as a method for reloading those elements.
2. Ensure the new structure can use any type of IEnumerable to store the elements.
3. Implement a dynamic cache which inherits from the standard cache, as well as storing additional methods for appending new elements and determining which elements to drop.
4. Ensure the dynamic cache can only use List to store the cached elements, in order to make use of List<T>.AddRange and List<T>.RemoveAll.

This works, but seems unnecessarily complicated. I essentially have 5 classes and 1 interface to pull this off, and having to declare TEnumerable as IEnumerable<TElement> in the where clause of a class declaration feels odd at best.

Is there a simpler way to implement this?

internal interface ICache : IEnumerable
{
    bool Contains(object element);
}

internal class DynamicCache<TElement> : DynamicCache<List<TElement>, TElement> {
    internal DynamicCache(
        Func<List<TElement>> initElements
        , Func<List<TElement>> addElements
        , Predicate<TElement> dropElementsIf
    )
        : base(initElements, addElements, dropElementsIf) 
    {
    }
}

internal class DynamicCache<TEnumerable, TElement> : Cache<TEnumerable, TElement> where TEnumerable : List<TElement> {

    protected Func<TEnumerable> AddElements;
    protected Predicate<TElement> DropElementsIf;

    internal DynamicCache(
        Func<TEnumerable> initElements
        , Func<TEnumerable> addElements
        , Predicate<TElement> dropElementsIf
    )
        : base(initElements) 
    {
        this.AddElements = addElements;
        this.DropElementsIf = dropElementsIf;
    }

    protected override sealed void UpdateElements() {
        if (!isInitialized) {
            this.elements = InitElements();
            this.isInitialized = true;
        }
        else {
            this.elements.AddRange(AddElements());
            this.elements.RemoveAll(DropElementsIf);
        }
    }
}

internal class Cache<TElement> : Cache<IEnumerable<TElement>, TElement> {
    internal Cache(Func<IEnumerable<TElement>> initElements)
        : base(initElements)
    {
    }
}

internal class Cache<TEnumerable, TElement> : IEnumerable<TElement>, ICache where TEnumerable : IEnumerable<TElement> {

    protected TEnumerable elements;
    protected bool isInitialized;
    protected Func<TEnumerable> InitElements;

    internal Cache(Func<TEnumerable> initElements) {
        this.InitElements = initElements;
    }

    protected virtual void UpdateElements() {
        if (!isInitialized) {
            this.elements = InitElements();
            this.isInitialized = true;
        }
    }

    public IEnumerator<TElement> GetEnumerator() {
        UpdateElements();
        foreach (TElement element in this.elements) {
            yield return element;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return (IEnumerator)this.GetEnumerator();
    }

    public override string ToString() {
        StringBuilder sb = new StringBuilder();
        foreach (TElement element in this) {
            sb.Append(element.ToString() + "\n");
        }
        sb.Append("\n");
        return sb.ToString();
    }

    bool ICache.Contains(object element) {
        if (element is TElement) {
            return this.Contains((TElement)element);
        }
        return false;
    }

    internal bool Contains(TElement element) {
        UpdateElements();
        return this.elements.Contains(element);
    }
}

internal class Wrapper {
    internal int id {get; set;}
    internal string name {get; set;}
    public override string ToString() {
        return string.Format("Wrapper id: {0}, name: {1}", this.id, this.name);
    }
}

internal static class Builder {

    internal static int WrapperCount;

    static Builder() {
        WrapperCount = 0;
    }

    internal static IEnumerable<Wrapper> WrapperFactory(int count) {
        Wrapper[] wArray = new Wrapper[count];
        for (var i = 0; i < count; i++) {
            wArray[i] = Builder.SingleWrapperFactory();
        }
        return wArray;
    }

    internal static Wrapper SingleWrapperFactory() {
        return new Wrapper {
            id = WrapperCount,
            name = "Wrapper " + WrapperCount++            
        };
    }
}

void Main()
{
    // example Cache usage
    Cache<Wrapper> wCache = new Cache<Wrapper>(
        () => Builder.WrapperFactory(5) // Initialize with 5 Wrappers from the Builder
    );
    Debug.Write("Standard Cache Pass 1: \n" + wCache); // 0, 1, 2, 3, 4
    Debug.Write("Standard Cache Pass 2: \n" + wCache); // 0, 1, 2, 3, 4

    // example DynamicCache usage
    DynamicCache<Wrapper> wDynamicCache = new DynamicCache<Wrapper>(
        () => Builder.WrapperFactory(5).ToList() // Initialize with 5 Wrappers from the Builder
        , () => Builder.WrapperFactory(3).ToList() // Append 3 new Wrappers from the Builder on each iteration
        , (w) => w.id < Builder.WrapperCount - 5 // Remove items which have an id less than Builder.WrapperCount
    );
    Debug.Write("Dynamic Cache Pass 1: \n" + wDynamicCache); // 5, 6, 7, 8, 9
    Debug.Write("Dynamic Cache Pass 2: \n" + wDynamicCache); // 8, 9, 10, 11, 12
    Debug.Write("Dynamic Cache Pass 3: \n" + wDynamicCache); // 11, 12, 13, 14, 15
    Debug.Write("Dynamic Cache Pass 4: \n" + wDynamicCache); // 14, 15, 16, 17, 18

    ICache iCache = new Cache<string>(
        () => new HashSet<string> { "this", "is", "my", "new", "HashSet<string>", "to", "use", "in", "ICache" }    
    );
    Debug.Write("iCache.Contains(\"use\") : " + iCache.Contains("use"));
}

Answer 1

Interface design is wanting.

This looks like this was made by mistake:

internal interface ICache : IEnumerable
{
    bool Contains(object element);
}

It should implement IEnumerable<T> which already provides IEnumerable functionality.

internal interface ICache<TElement> : IEnumerable<TElement>
{
    bool Contains(TElement element);
}

This way you can do Cache<TEnumerable, TElement> : ICache<TElement> instead of class Cache<TEnumerable, TElement> : IEnumerable<TElement>, ICache. Which allows non-type-safe and redundant Contains(object) method.

More importantly though your ICache provides no additional functionality w.r.t any other IEnumerable<T>, given IEnumerable already has a Contains extension method.

Before writing some component, you should be able to write interfaces thereof, and test the required functionality against those interfaces.

In general:

• a cache is a specialized Key-Value store.
• They are used to improve read performance where reads outnumber updates by far, and write are relatively expensive.
• They exploit time locality (and sometimes space) locality.

The only way to access the elements in your cache is through enumerating them. Which precludes random access. For example you cannot get a Wrapper with a given id from the cache.

GetEnumerator modifies the underlying collection by calling UpdateElements();, and this ruins the other two properties. You cannot exploit there being many more reads than updates, because every read is an update. You cannot exploit time locality because even if you are reading the same elements over and over again you are updating the collection.

Consider this:

DynamicCache<Wrapper> wDynamicCache = //......

var wrapper = new Wrapper{id=10, name = "Wrapper 10"};
Console.WriteLine(wDynamicCache.Contains(wrapper)); // False
Console.WriteLine(wDynamicCache.Contains(wrapper)); // True
Console.WriteLine(wDynamicCache.Contains(wrapper)); // False

In order to exploit time (or other) locality is choosing the correct caching strategy. For example if some data feed is updated on average once a day, you might decide to not hit the source if cache contains a data read in the past 6 hours. Or you might want to have a fixed size cache which automatically evicts the least recently used when it is full and a value not contained therein is accessed.

But these types of common strategies cannot be implemented with a Predicate<TElement> dropElementsIf. You might try to wrap the data with last access time etc details, as you already did in your test; but this would leak to the interface, as TElement is now a wrapper with implementation details. For example changing caching strategy will require recompiling the code using the cache.

Some other problems not specific to caches:

• everytime Cache classes are accessed UpdateElements is called even though Cache classes are not dynamic by default.
• protected bool isInitialized; is present on Cache and also everytime Cache classes are accessed checked even if it consists of a fixed collection of elements.

• Every overriding method of UpdateElements must start with copied :

  if (!isInitialized) {
      this.elements = InitElements();
      this.isInitialized = true;
  }