javalistload-balancingcircular-listround-robin

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


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       |
+–––––––––––+–––––––––––––––+

Solution

  • 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.