How to implement a round-robin circular list and count access requests of an element?

Wuaner picture Wuaner · Apr 4, 2014 · Viewed 15.3k times · Source

Scenario:

For a list that have 3 elements:

[A, B, C]

You can circular access it as many times as you want.

And there is an additional counting function records access count of each element.

For example, if accessing it 7 times, should return:

[A, B, C, A, B, C, A]

And have access count of each element as following:

+–––––––––––+–––––––––––––––+
|  Element  |  Access count |
+–––––––––––––––––––––––––––+
|     A     |       3       |
+–––––––––––––––––––––––––––+
|     B     |       2       |
+–––––––––––––––––––––––––––+
|     C     |       2       |
+–––––––––––+–––––––––––––––+

Add another additional function that allow caller to specify a elements list that should be filtered. Still use 7 times accessing as a example, filtering [C]:

[A, B, A, B, A, B, A]
+–––––––––––+–––––––––––––––+
|  Element  |  Access count |
+–––––––––––––––––––––––––––+
|     A     |       4       |
+–––––––––––––––––––––––––––+
|     B     |       3       |
+–––––––––––––––––––––––––––+
|     C     |       0       |
+–––––––––––+–––––––––––––––+

And the subsequent calling on getNextOne() should always fetch the one that access count is low. Simulate a load-balanced accessing count implementation. So, if second caller attempt to accessing it 10 times, should return:

[C, C, C, B, C, A, B, C, A, B, C, A]
+–––––––––––+–––––––––––––––+
|  Element  |  Access count |
+–––––––––––––––––––––––––––+
|     A     |       7       |
+–––––––––––––––––––––––––––+
|     B     |       6       |
+–––––––––––––––––––––––––––+
|     C     |       6       |
+–––––––––––+–––––––––––––––+

Answer

user180100 picture user180100 · Apr 4, 2014

Guava provides an Iterables.cycle(), coupled with a Multiset for counting and you're done:

package com.stackoverflow.so22869350;

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Multiset;

import java.util.Iterator;
import java.util.List;

public class Circular<T> {

    private final Multiset<T> counter;

    private final Iterator<T> elements;

    public Circular(final List<T> elements) {
        this.counter = HashMultiset.create();
        this.elements = Iterables.cycle(elements).iterator();
    }

    public T getOne() {
        final T element = this.elements.next();
        this.counter.add(element);
        return element;
    }

    public int getCount(final T element) {
        return this.counter.count(element);
    }

    public static void main(final String[] args) {
        final Circular<String> circular = new Circular<>(Lists.newArrayList("A", "B", "C"));
        for (int i = 0; i < 7; i++) {
            System.out.println(circular.getOne());
        }
        System.out.println("Count for A: " + circular.getCount("A"));
    }
} 

Output:

A
B
C
A
B
C
A
Count for A: 3

NB: Beware to have proper equals/hashCode for type T