Feature request: Limit maximum size of Collection (e.g. LRUMap/LRUList) #806

avocadowastaken · 2016-03-07T14:43:48Z

I use List/Map collections in my Redux store, and have problem with maintaining map sizes (i need last 5-6 records only)

First attempt to resolve this problem was to create helper function:

static sliceMap(map, maxSize = 5) {
    if (!ImmutableUtils.isImmutable(map)) {
        return map;
    }

    if (map.size <= maxSize) {
        return map;
    }

    return map.slice(map.size - maxSize);
}

And use it like

let newMap = ImmutableUtils.sliceMap(oldMap);

But It's not good solution for me, as i have to call this method every time when i need to mutate map

Second attempt was to create new class and extend it with map, override set/setIn, but super methods will always return new map instance, so it was just pointless

So the only solution that is see to create new collections like: LRUMap, LRUList and else inspired by https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/LRUMap.html

EDIT

Found final solution for my problem

let data = Immutable.OrderedMap(); data.toString();

// "OrderedMap {}" - we need OrderedMap (for ... you know ... ordering)
data = data.set(1, 1).set(2, 2).set(3, 3).set(4, 4).set(5, 5).set(6, 6).takeLast(5); data.toString();
// "OrderedMap { 2: 2, 3: 3, 4: 4, 5: 5, 6: 6 }" - look good enough
data = data.set(2, 3).takeLast(5); data.toString();
// "OrderedMap { 2: 3, 3: 3, 4: 4, 5: 5, 6: 6 }" - here we got problem, key '2' took it's previous position
data = data.delete(2).set(2, 3).takeLast(5); data.toString();
// "OrderedMap { 3: 3, 4: 4, 5: 5, 6: 6, 2: 3 }" - that's better
data = data.delete(3).set(3, 4).takeLast(5); data.toString();
// "OrderedMap { 4: 4, 5: 5, 6: 6, 2: 3, 3: 4 }" - yep
data = data.delete(7).set(7, 7).takeLast(5); data.toString();
// "OrderedMap { 5: 5, 6: 6, 2: 3, 3: 4, 7: 7 }" - finally

// working example

static handleFetchSuccess(state, {response, id}) {
        return state
            .update('dataLoading', item => item.delete(id))
            .update('data', item => item.delete(id).set(id, fromJS(response)).takeLast(10));
}

The text was updated successfully, but these errors were encountered:

leebyron · 2016-04-16T01:07:58Z

These are very different data-structures. I'm unlikely to build them anytime soon, but if someone is interested in contributing, the first step is to consult existing research in persistently immutable cache mechanisms to determine next steps.

Closing this issue though, as it's not something that's on the near-term roadmap.

avocadowastaken · 2016-04-16T09:17:08Z

@leebyron Thanks for your response,

Implementing LRU will require update Collection every time when user gets data from it, so it's impossible to keep Collection immutable in this case.

My bad, did't do researches before asking question, but still, what about LimitedMap?

I really interested in this feature and after some researches of immutable-js I have a solution proposal:

import { LimitedMap } from 'immutable';

const ShortMap = new LimitedMap(5, 'ShortMap');
let shortMap = new ShortMap({1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f'});

shortMap.toString(); // "ShortMap { "2": "b", "3": "c", "4": "d", "5": "e", "6": "f" }"

As you can see, definition look like you did it for Records,
That's allow to define own Map/List/ Set classes with limited sizes.

So I wanted to know your opinion about that. Should I create PR to start implementation, or it's better to keep it as separate lib? (e.g. 'immutable-limited-collections')

Here LimitedMap example

In OrderedMap.js export its prototype

var IS_ORDERED_MAP_SENTINEL = '@@__IMMUTABLE_ORDERED_MAP__@@';

export var OrderedMapPrototype = OrderedMap.prototype;
OrderedMapPrototype[IS_ORDERED_MAP_SENTINEL] = true;
OrderedMapPrototype[DELETE] = OrderedMapPrototype.remove;
OrderedMapPrototype.removeIn = OrderedMapPrototype.deleteIn;

LimitedMap.js - it's basically refactored copy of Record.js

Implementation

import { OrderedMap, OrderedMapPrototype, emptyOrderedMap } from './OrderedMap';
import { DELETE } from './TrieUtils'

export class LimitedMap extends OrderedMap {

    //noinspection JSAnnotator - suppress `Missed superclass's constructor invocation` error in webstorm
    constructor(limit, name) {
        var hasInitialized;

        var LimitedMapType = function LimitedMap(values) {
            if (values instanceof LimitedMapType) {
                return values;
            }
            if (!(this instanceof LimitedMapType)) {
                return new LimitedMapType(values);
            }
            if (!hasInitialized) {
                hasInitialized = true;
                LimitedMapPrototype._name = name;
                LimitedMapPrototype._limit = limit;
            }
            this._map = OrderedMap(values).takeLast(limit);
        };

        var LimitedMapPrototype = LimitedMapType.prototype = Object.create(LimitedMapPrototype);
        LimitedMapPrototype.constructor = LimitedMapType;

        return LimitedMapType;
    }

    toString() {
        return this.__toString(limitedMapName(this) + ' {', '}');
    }

    // @pragma Access

    has(k) {
        return Boolean(this._map) && this._map.has(k);
    }

    get(k, notSetValue) {
        return this._map ? this._map.get(k, notSetValue) : notSetValue;
    }

    // @pragma Modification

    clear() {
        if (this.__ownerID) {
            this._map && this._map.clear();
            return this;
        }
        var LimitedMapType = this.constructor;
        return LimitedMapType._empty || (LimitedMapType._empty = makeLimitedMap(this, emptyOrderedMap()));
    }

    set(k, v) {
        var newMap = this._map;
        var limit = this._limit;

        if (newMap) {
            newMap = newMap.asMutable(); // I wanted to use `withMutations` here but `takeLast` doesn't work in it

            if (newMap.has(k)) { // we don't want to replace previous value, so remove it before setting new
                newMap.delete(k);
            }

            newMap.set(k, b); 

            if (newMap.size > limit) {  // this part maybe need to be optimized 
                newMap = newMap.takeLast(limit);
            }

            newMap = newMap.asImmutable();
        }

        if (this.__ownerID || newMap === this._map) {
            return this;
        }

        return makeLimitedMap(this, newMap);
    }

    remove(k) {
        var newMap = this._map && this._map.remove(k);
        if (this.__ownerID || newMap === this._map) {
            return this;
        }
        return makeLimitedMap(this, newMap);
    }

    wasAltered() {
        return this._map.wasAltered();
    }

    __iterator(type, reverse) {
        return this._map.__iterator(type, reverse);
    }

    __iterate(fn, reverse) {
        return this._map.__iterate(fn, reverse);
    }

    __ensureOwner(ownerID) {
        if (ownerID === this.__ownerID) {
            return this;
        }
        var newMap = this._map && this._map.__ensureOwner(ownerID);
        if (!ownerID) {
            this.__ownerID = ownerID;
            this._map = newMap;
            return this;
        }
        return makeLimitedMap(this, newMap, ownerID);
    }
}

var LimitedMapPrototype = LimitedMap.prototype;
LimitedMapPrototype[DELETE] = LimitedMapPrototype.remove;
LimitedMapPrototype.deleteIn =
    LimitedMapPrototype.removeIn = OrderedMapPrototype.removeIn;
LimitedMapPrototype.merge = OrderedMapPrototype.merge;
LimitedMapPrototype.mergeWith = OrderedMapPrototype.mergeWith;
LimitedMapPrototype.mergeIn = OrderedMapPrototype.mergeIn;
LimitedMapPrototype.mergeDeep = OrderedMapPrototype.mergeDeep;
LimitedMapPrototype.mergeDeepWith = OrderedMapPrototype.mergeDeepWith;
LimitedMapPrototype.mergeDeepIn = OrderedMapPrototype.mergeDeepIn;
LimitedMapPrototype.setIn = OrderedMapPrototype.setIn;
LimitedMapPrototype.update = OrderedMapPrototype.update;
LimitedMapPrototype.updateIn = OrderedMapPrototype.updateIn;
LimitedMapPrototype.withMutations = OrderedMapPrototype.withMutations;
LimitedMapPrototype.asMutable = OrderedMapPrototype.asMutable;
LimitedMapPrototype.asImmutable = OrderedMapPrototype.asImmutable;

function makeLimitedMap(likeLimitedMap, map, ownerID) {
    var limitedMap = Object.create(Object.getPrototypeOf(likeLimitedMap));
    limitedMap._map = map;
    limitedMap.__ownerID = ownerID;
    return limitedMap;
}

function limitedMapName(limitedMap) {
    return limitedMap._name || limitedMap.constructor.name || 'Record';
}

leebyron · 2016-04-16T16:24:42Z

This should behave correctly, but may not be an efficient implementation. LRUMaps which seek to be performant and persistent usually use some kind of structure that's easier to clean up like a btree or minheap

avocadowastaken · 2017-03-04T08:49:04Z

It has been a long time since then, i've tried max heap, btree, and Java TreeMap, and found it useless for current task - because of runtime normalization.

Everything that I need is limited size, and strict ordering. So I dropped the idea of new implementation and keep using OrderedMap + takeLast.

But it was a previous story.

Recently I start working on custom caching collections and implemented custom LinkedMap with es6 Map inside of it. And after some time I found that I need to store Immutable collections as keys and I remembered current issue.

Basically this LinkedMap works like OrderedMap with three differences:

It has limited size. 👍
It always adds value to the end, even if it's already in map. 👍
It's not immutable. 👎

So I guess it will be more efficient than using OrderedMap (with Map and List inside of it).

And finally -- Proposal.

Add new LinkedMap collection with:

Map interface.
Strict ordering.
setFirst and setLast methods.
set will behave as setFirst.
Custom Class Builder (like Record constructor) to allow:
- Limited Size
- Anything else in the future.

For example:

import { LinkedMap, LinkedMapBuilder } from 'immutable';

const lm = new LinkedMap().set(1, 0).set(2, 0).set(1, 0); // LinkedMap { 2: 0, 1: 0 }

const CustomLinkedMap = LinkedMapBuilder({ maxSize: 2 }, 'CustomLinkedMap');
const clm = CustomLinkedMap().set(1, 0).set(2, 0).set(1, 0).set(3, 0); // LinkedMap { 1: 0, 3: 0 }

avocadowastaken changed the title ~~Limit maximum size of Collection (e.g. LRUMap/LRUList)~~ Feature request: Limit maximum size of Collection (e.g. LRUMap/LRUList) Mar 7, 2016

leebyron closed this as completed Apr 16, 2016

avocadowastaken mentioned this issue Mar 8, 2017

Simplify unit test environment #1111

Closed

3 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Feature request: Limit maximum size of Collection (e.g. LRUMap/LRUList) #806

Feature request: Limit maximum size of Collection (e.g. LRUMap/LRUList) #806

avocadowastaken commented Mar 7, 2016

leebyron commented Apr 16, 2016

avocadowastaken commented Apr 16, 2016 •

edited

Loading

leebyron commented Apr 16, 2016

avocadowastaken commented Mar 4, 2017 •

edited

Loading

Feature request: Limit maximum size of Collection (e.g. LRUMap/LRUList) #806

Feature request: Limit maximum size of Collection (e.g. LRUMap/LRUList) #806

Comments

avocadowastaken commented Mar 7, 2016

leebyron commented Apr 16, 2016

avocadowastaken commented Apr 16, 2016 • edited Loading

leebyron commented Apr 16, 2016

avocadowastaken commented Mar 4, 2017 • edited Loading

avocadowastaken commented Apr 16, 2016 •

edited

Loading

avocadowastaken commented Mar 4, 2017 •

edited

Loading