A very simple implementation of LRU caching utility like the one in python functools

example2LRU_Cache.chpl

private use Map only;
private use List only;
private use Crypto only;

record ordered_map {

    /* Type of map keys.*/
    type keyType;

    /* Type of map values*/
    type valType;

    var dictionary : Map.map(keyType, valType, parSafe = true);     // the map is responsible of inserting and deletion
    var keysOrder : List.list(keyType);                             // it is enough to make parallel safe to make it all safe?

    proc init(type keyType, type valType) {        
        this.keyType = keyType;
        this.valType = valType;
    }

    proc insert(k: keyType, v: valType) {
        var success = dictionary.add(k, v);         
        if success {
            keysOrder.append(k);
        } else {              
            keysOrder.remove(k);                    // we want this key on the front if we insert it again
            keysOrder.insert(1, k);                 // to have the "LRU" value on the front and least used value at the back
        }                                           // "L" in "LRU" stands for last not least for now
        return success;
    }

    proc available(k: keyType) : bool {
        return dictionary.contains(k);
    }

    proc remove(k: keyType) : bool {
        var success = dictionary.remove(k);
        if success {
            var h = keysOrder.remove(k);
        }
        return success;
    }

    proc removeLast() : bool {                     // when our cache is full
        var lastElement = keysOrder.pop();
        var success = dictionary.remove(lastElement);
        return success;
    }

    proc this(k: keyType) {
        return dictionary[k];
    }

    proc printValues() {                        // for debugging
        for i in this.keysOrder {
            writeln(i);
        }
    }
}


// this implementation is a perfect example of why I need a mentor


class lru_cache {
    
    // the function whose inputs and outputs to be cached
    var function;                                   

    // the max size of the cache
    var size: int;

    // to keep track of how much we have cached
    var counter : int;

    // type of the output to make the map ... needs improvement because the API looks ugly because of that
    type outputs;

    // the dictionary 
    var dictionary : ordered_map(string, outputs);

    // hashing utility ... usage of MD5 algorithm is arbitrary-ish, I see all people use it to blueprint their code with SHA-family
    var hashingObject = new Crypto.Hash(Crypto.Digest.MD5);      


    // The user need to have the function as input
    // and the size of the cache
    // here where it gets ugly ... the user need to input an example of output
    // so I can deduce the type of outputs and build the ordered_map

    proc init(f, s, exampleOut) {   // f is the function, s is the size of the cache, counter is counter :D, exampleOut is example of an arbitrary output
        function = f;
        size = s;
        counter = 0;
        outputs = exampleOut.type;  // to ge the type of the output
    }

    // we don't have args and kwards like in python but we have tuple expansion
    // the user need to feed the call function with input as TUPLE. bad API design?

    proc call(i) where isTuple(i) == true {                     // or we can override "this" special method? and act as if we have the feature of returning function objects => check issue #15234
        var cryptoBuffer = new Crypto.CryptoBuffer(i:string);      
        var hashed = ((hashingObject.getDigest(cryptoBuffer)).buff):string;

        if dictionary.available(hashed) {
            dictionary.insert(hashed, dictionary[hashed]);       // to make it at the front of list
            return dictionary[hashed];
        } else {
            var newResult = function((...i));
            dictionary.insert(hashed, newResult);
            counter = counter + 1;                              // doesn't do anything rn
            return newResult;
        }
    }
}




// the variable b is here to demonstrate that lru_cache class can handle functions with multiple arguments
// it doesn't do anything. and the function is recursive to test that out

proc fibonacci(n: int, b: int) : int {      // cannot be generic ... design decision as I found out in the issue #15234
    if n <= 1 {
        return 1;
    } else {
        return fibonacci(n-1, b) + fibonacci(n-2, b);
    }
}

var a = fibonacci(43,10);           // the second variable "10" is just a dummy variable

var cachingObject = new lru_cache(fibonacci, 100, 5);       // the constructor takes the function, and the size of the cache "dummy variable for now", and output of the function to get its type

// let's see the difference in times 
use Time;

var startTime1 = getCurrentTime();
var output1 = cachingObject.call((30,10));  // the input MUST be passed as tuple, because we need to have a way to refer to the input as a whole
writeln(getCurrentTime() - startTime1);     // and we don't have *args or *kwargs like in python

var startTime2 = getCurrentTime();
var output2 = cachingObject.call((30,10));
writeln(getCurrentTime() - startTime2);     // this is literally a time of accessing array 


// If we overrided "this" method and named the "cachingObject" as fibonacci
// The API would be much much nicer and the user would call it instead of
// cachingObject.call((30,10)) ==> fibonacci((30,10)), this as close as it could get to python without function decorators

// now the only issue would be removing the annoying output example that must be fed to the object initializer
// this would need time to work on