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

Question

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

score 29 · Accepted Answer · edited Aug 01 '21 at 17:01

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.

score 8 · Answer 2 · edited Aug 01 '21 at 16:23

The above answer is correct, just adding one more simpler way of round robin algorithm with list.

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

public class MyRoundRobin<T> implements Iterable<T> {
    private List<T> coll;
    private int index = 0;

    public MyRoundRobin(List<T> coll) {
        this.coll = coll;
    }

    public Iterator<T> iterator() {
        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return true;
            }
            @Override
            public T next() {
                if (index >= coll.size()) {
                    index = 0;
                }
                T res = coll.get(index++);
                return res;
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

score 2 · Answer 3 · 2021-04-10T20:11:19.667

You can implement a circular access list based on a single TreeMap.

TreeMap
Key	`Integer` number of access requests
Value	`List<T>` list of objects to which access was requested

Class `CircularList<T>`

Methods	This code works in Java 7 without additional libraries
getOne()	return `T` the first element with the least number of access requests
getOne(List<T> filter)	return `T` the first element with the least number of access requests that is not contained in the filter
getOne(T filterIn)	return `T` the filtered element
getCount(T element)	return `int` the number of access requests of the search element, or `-1` if there is no such element
status()	return `String` the current status of the map

Try it online!

public class CircularList<T> {
    private final TreeMap<Integer, List<T>> elements = new TreeMap<>();

    /**
     * @param list required.
     */
    public CircularList(List<T> list) {
        if (list == null || list.size() == 0) return;
        this.elements.put(0, new ArrayList<>(list));
    }

    /**
     * @return the first element with the least number of access requests.
     */
    public synchronized T getOne() {
        // pull out the entry with the least number of access requests
        Map.Entry<Integer, List<T>> entry = this.elements.pollFirstEntry();
        Integer key = entry.getKey();
        List<T> value = entry.getValue();
        // pull out the first element from the list
        T element = value.remove(0);
        // if there is something left in the list, then put it back
        if (value.size() > 0) this.elements.put(key, value);
        // take the next list with greater number of access requests
        List<T> newValue = this.elements.get(key + 1);
        // create it if it doesn't exist
        if (newValue == null) newValue = new ArrayList<>();
        // add the current element to this list
        newValue.add(element);
        // update the map
        this.elements.put(key + 1, newValue);
        // return the first element with the least number of access requests
        return element;
    }

    /**
     * @param filter elements list that should be filtered.
     * @return the first element with the least number of
     * access requests that is not contained in the filter.
     */
    public synchronized T getOne(List<T> filter) {
        // incorrect filter is not applied
        if (filter == null || filter.size() == 0) return getOne();
        Integer key = -1;
        List<T> value;
        T element = null;
        // iterate over the entries of the map
        for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
            key = entry.getKey();
            value = entry.getValue();
            element = null;
            // iterate over the elements of the list
            for (T el : value) {
                // the first element not contained in the filter
                if (!filter.contains(el)) {
                    element = el;
                    // remove this element from the list
                    value.remove(el);
                    // if there is nothing left in the list, remove the entry
                    if (value.size() == 0) this.elements.remove(key);
                    break;
                }
            }
            // if the element is found
            if (element != null) break;
        }
        // if no element is found, no filter is applied
        if (element == null) return getOne();
        // take the next list with greater number of access requests
        List<T> newValue = this.elements.get(key + 1);
        // create it if it doesn't exist
        if (newValue == null) newValue = new ArrayList<>();
        // add the current element to this list
        newValue.add(element);
        // update the map
        this.elements.put(key + 1, newValue);
        // return the first element with the least number of access requests
        return element;
    }

    /**
     * @param filterIn element that should be filtered.
     * @return the filtered element.
     */
    public synchronized T getOne(T filterIn) {
        // incorrect filter is not applied
        if (filterIn == null) return getOne();
        // iterate over the entries of the map
        for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
            Integer key = entry.getKey();
            List<T> value = entry.getValue();
            // iterate over the elements of the list
            for (T element : value) {
                // if element is found
                if (filterIn.equals(element)) {
                    // remove this element from the list
                    value.remove(element);
                    // if there is nothing left in the list, remove the entry
                    if (value.size() == 0) this.elements.remove(key);
                    // take the next list with greater number of access requests
                    List<T> newValue = this.elements.get(key + 1);
                    // create it if it doesn't exist
                    if (newValue == null) newValue = new ArrayList<>();
                    // add the current element to this list
                    newValue.add(element);
                    // update the map
                    this.elements.put(key + 1, newValue);
                    // return filtered element
                    return element;
                }
            }
        }
        // if no element is found, no filter is applied
        return getOne();
    }

    /**
     * Search for the element in the lists of the map.
     *
     * @param element search element.
     * @return the number of access requests of the
     * search element, or -1 if there is no such element.
     */
    public int getCount(T element) {
        for (Map.Entry<Integer, List<T>> entry : this.elements.entrySet()) {
            if (entry.getValue().contains(element)) {
                return entry.getKey();
            }
        }
        return -1;
    }

    /**
     * @return the current status of the map.
     */
    public String status() {
        return elements.toString();
    }

    @Override
    public String toString() {
        return elements.toString();
    }
}

// Test
public static void main(String[] args) {
    CircularList<String> list =
            new CircularList<>(Arrays.asList("A", "B", "C", "D"));
    System.out.println(list); // {0=[A, B, C, D]}
    for (int i = 0; i < 10; i++) {
        System.out.print(list.getOne(Arrays.asList("A")) + " ");
        // B C D B C D B C D B
    }
    System.out.println();
    System.out.println(list.status()); // {0=[A], 3=[C, D], 4=[B]}
    for (int i = 0; i < 3; i++) {
        System.out.print(list.getOne("D") + " ");
        // D D D
    }
    System.out.println();
    System.out.println(list.status()); // {0=[A], 3=[C], 4=[B], 6=[D]}
    for (int i = 0; i < 14; i++) {
        System.out.print(list.getOne() + " ");
        // A A A C A B C A B C A D B C
    }
    System.out.println();
    System.out.println(list.status()); // {6=[A], 7=[D, B, C]}
    System.out.println(list.getCount("A")); // 6
    System.out.println(list.getCount("E")); // -1
}

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

3 Answers3

Class CircularList<T>

Class `CircularList<T>`