1

Тема: Map. Capped Map. Допоможіть зрозуміти чому падають тести

Добрий вечір. Прошу вашої допомоги з цим завданням. Використовую IntelliJ IDEA.

Int String Capped Map
The purpose of this exercise is to train you in implementing Collections.

Estimated workload of this exercise is 180 min.

Description
Please, proceed to IntStringCappedMap and implement its methods.

IntStringCappedMap is a Map with Integer keys and String values.
"Capped" means that this map has a capacity property.
Total length of all String values in a map must not exceed its capacity.
If a new added value would lead to such overflowing, the map must evict its current entries until adding new value would not exceed its capacity.
Eviction must follow the order of adding values to the map - the oldest value must be evicted first.
Note that if length of the new String value is more than capacity, map must throw an IllegalArgumentException and evict no entry.

You need to implement following methods:

entrySet - the method is partially implemented.
It returns an AbstractSet and you must only provide implementations for its iterator next and hasNext methods.
get - return a value by its key.
put - set a value by a given key.
If it leads to exceeding capacity, be sure to evict as many of the oldest elements as needed.
remove - removes a value by key.
size - returns number of map entries.
Example
IntStringCappedMap map = new IntStringCappedMap(25);
map.put(5, "Five");
map.put(6, "Six");
map.put(7, "Seven");
map.put(8, "Eight");
map.put(12, "Twelve");
map.put(9, "Nine");
map.put(1, "One");

System.out.println(new TreeMap<>(map));
//{1=One, 7=Seven, 8=Eight, 9=Nine, 12=Twelve}

Ось моя реалізація. Наведений в завданні приклад виконується.

import java.util.*;

class IntStringCappedMap extends AbstractMap<Integer, String> {

    private final long capacity;
    private final Map<Integer, String> map;
    public IntStringCappedMap(final long capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>((int)capacity);
    }

    public long getCapacity() {
        return capacity;
    }


    @Override
    public Set<Entry<Integer, String>> entrySet() {
        return new AbstractSet<>() {
            @Override
            public Iterator<Entry<Integer, String>> iterator() {
                return new Iterator<>() {
                    Set<Entry<Integer, String>> entry = map.entrySet();
                    Iterator iterator = entry.iterator();
                    @Override
                    public boolean hasNext() {
                        return iterator.hasNext();
                    }

                    @Override
                    public Entry<Integer, String> next() {
                        return (Entry<Integer, String>) iterator.next();
                    }
                };
            }

            @Override
            public int size() {
                return IntStringCappedMap.this.size();
            }
        };
    }

    @Override
    public String get(final Object key) {
        return map.get(key);
    }

    @Override
    public String put(final Integer key, final String value) {
        if (value.length() > capacity) throw new IllegalArgumentException();
        while (totalSizeOfValues() + value.length() > capacity) {
            // так я видаляю найстаріший елемент, тобто пару яка потрапила перша
            for (Map.Entry<Integer, String> entry : map.entrySet()) {
                map.remove(entry.getKey());
                break;
            }
        }
        return map.put(key, value);
    }

    @Override
    public String remove(final Object key) {
        return map.remove(key);
    }

    @Override
    public int size() {
        return map.size();
    }

    private long totalSizeOfValues() {
        long total_size = 0;
        for (Map.Entry<Integer, String> entry: map.entrySet()) {
            total_size += entry.getValue().length();
        }
        return total_size;
    }
}

Але тест не проходить. Ось частина повідомлення.
Expected :map(20):[3:3333333, 4:99999, 6:00, 7:2, 8:7, 9:0]
Actual   :map(20):[3:3333333, 4:99999, 6:00, 7:2, 9:0]

Ось тест

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.StandardOpenOption;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import static com.company.autotasks.collections.IntStringCappedMapTest.toStringSet;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.params.provider.Arguments.arguments;

class IntStringCappedMapRandomTest {

    static Stream<Arguments> testCases() {
        return Stream.of(
                42,
                654692,
                7714,
                845632,
                15966,
                12358,
                852139,
                8569,
                112584,
                3263
        ).map(i -> arguments(i, expectedList(i)));
    }

    @ParameterizedTest(name = "[{index}] {0}")
    @MethodSource("testCases")
    void testInitialState(int seed, List<String> expected) {
        Random random = new Random(seed);
        IntStringCappedMap map = new IntStringCappedMap(10 + random.nextInt(20));

        Iterator<String> expectedIt = expected.iterator();

        int iterations = 10 + random.nextInt(10);
        for (int i = 0; i < iterations; i++) {
            if (random.nextInt(4) != 0) {
                map.put(random.nextInt(10),
                        Integer.toString(random.nextInt(10))
                                .repeat(random.nextInt(8))
                );
            } else {
                map.remove(random.nextInt(5));
            }
            assertEquals(expectedIt.next(), toString(map));
        }
    }

    private String toString(final IntStringCappedMap map) {
        return "map(" + map.getCapacity() + "):" + toStringSet(map).toString();
    }

    private void writeFile(final int seed, final String actual) {
        try {
            Files.writeString(
                    Path.of("src", "test", "resources", seed + ".txt"),
                    actual + "\n", StandardOpenOption.APPEND, StandardOpenOption.CREATE);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static List<String> expectedList(int seed) {
        try {
            return Files.readAllLines(Path.of("src", "test", "resources", seed + ".txt"));
        } catch (IOException e) {
            return List.of();
        }
    }

}

Будь ласка, виділіть свій час, щоб допомогти мені.
І відразу ж хочу подякувати за те, що прочитали до цього рядка.

2 Востаннє редагувалося koala (21.12.2021 22:07:50)

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

Я в сучасній Джаві ніц не розумію, але ніби ви не обробляєте ситуацію, коли додається значення з уже наявним ключем. За умовою "the oldest value must be evicted first"; тобто має бути так:

IntStringCappedMap map = new IntStringCappedMap(10);
map.put(1, "AAA");
map.put(2, "BBB");
map.put(3, "CCC");
map.put(2, "DDD"); //нічого не викидається, бо BBB замінюється на DDD
map.put(4, "EEEEEE"); //викидаються ключі 1 і 3, бо (нове) значення для ключа 2 - наймолодше

Ну і я взагалі не певен, в якій послідовності entrySet().iterator() видає елементи, прогляньте документацію.

Окремо дякую за якісне питання із завданням, кодом і описом проблеми, тут такі цінуються.

Подякували: zxzpogoncuk1

3

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

А ті файли з сідс згенерувались для тесту. Хотілось би їх побачити.

Подякували: zxzpogoncuk1

4

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

koala написав:

Я в сучасній Джаві ніц не розумію, але ніби ви не обробляєте ситуацію, коли додається значення з вже наявним ключем. За умовою "the oldest value must be evicted first"; тобто має бути так:

IntStringCappedMap map = new IntStringCappedMap(10);
map.put(1, "AAA");
map.put(2, "BBB");
map.put(3, "CCC");
map.put(2, "DDD"); //нічого не викидається, бо BBB замінюється на DDD
map.put(4, "EEEEEE"); //викидаються ключі 1 і 3, бо (нове) значення для ключа 2 - наймолодше

Ну і я взагалі не певен, в якій послідовності entrySet().iterator() видає елементи, прогляньте документацію.

Окремо дякую за якісне питання із завданням, кодом і описом проблеми, тут такі цінуються.

Там виглядає що то пов'язаний список, тобто найстарший, то певно той, що в кінці списку. Або на початку в залежності від імплементації. Не думаю що дата додавання є в структурі того класу.

Подякували: zxzpogoncuk1

5

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

private final Map<Integer, String> map

Оце напевно та частина коду яку їм не можна модифікувати. Тобто часу там нема.

Подякували: zxzpogoncuk1

6

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

while (totalSizeOfValues() + value.length() > capacity) {
 // так я видаляю найстаріший елемент, тобто пару яка потрапила перша 
for (Map.Entry<Integer, String> entry : map.entrySet()) { 
map.remove(entry.getKey()); break; }
 }

Я оцей кусок не розумію, нащо там for?

Подякували: zxzpogoncuk1

7

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

Хоча дійсно, якщо приходить значення з тим самим ключом, то його напевно треба витирати на старому місці і тягнути на початок списку.

Подякували: zxzpogoncuk1

8

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

koala написав:

Ну і я взагалі не певен, в якій послідовності entrySet().iterator() видає елементи, прогляньте документацію.

Видає в тому ж порядку. Якщо ви про це казали

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "AAA");
        map.put(2, "BBB");
        map.put(3, "CCC");
        map.put(4, "DDD");
        map.put(5, "EEE");
        map.put(6, "FFF");
        Iterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}
Програма видає
1=AAA
2=BBB
3=CCC
4=DDD
5=EEE
6=FFF

Та й ніби метод entrySet() працює правильно

IntStringCappedMap map = new IntStringCappedMap(100);
        map.put(1, "AAA");
        map.put(2, "BBB");
        map.put(3, "CCC");
        map.put(4, "DDD");
        map.put(5, "EEE");
        map.put(6, "FFF");
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry);
        }
Видає
1=AAA
2=BBB
3=CCC
4=DDD
5=EEE
6=FFF

koala написав:

ви не обробляєте ситуацію, коли додається значення з уже наявним ключем.

Ви маєте рацію. Після того як виправив метод put проходить 9 з 10 тестів(а було 6 з 10).

public String put(final Integer key, final String value) {
        if (value.length() > capacity) throw new IllegalArgumentException();
        // перевірка на той самий ключ
        if (map.containsKey(key)) {
            map.remove(key);
            return map.put(key, value);
        }
        while (totalSizeOfValues() + value.length() > capacity) {
            // так я видаляю найстаріший елемент, тобто пару яка потрапила перша
            for (Map.Entry<Integer, String> entry : map.entrySet()) {
                map.remove(entry.getKey());
                break;
            }
        }
        return map.put(key, value);
    }





Vo_Vik написав:

А ті файли з сідс згенерувались для тесту. Хотілось би їх побачити.

Вибачте, але я не знаю що таке сідс. Ось те що я отримав, напевно воно тут є https://github.com/npogoncuk/capped-map


Vo_Vik написав:

Там виглядає що то пов'язаний список, тобто найстарший, то певно той, що в кінці списку. Або на початку в залежності від імплементації.

Здається, що елемент, який додали першим(є найстарішим), є на початку.

public class Main {
    public static void main(String[] args) {
        IntStringCappedMap map = new IntStringCappedMap(100);
        map.put(1, "AAA");
        map.put(2, "BBB");
        map.put(3, "CCC");
        map.put(4, "DDD");
        map.put(5, "EEE");
        map.put(6, "FFF");
        System.out.println(map);
    }
}
Виводить
{1=AAA, 2=BBB, 3=CCC, 4=DDD, 5=EEE, 6=FFF}
Vo_Vik написав:
private final Map<Integer, String> map

Оце напевно та частина коду яку їм не можна модифікувати. Тобто часу там нема.

Ні, це я написав. Спочатку клас вигладав так.

import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

class IntStringCappedMap extends AbstractMap<Integer, String> {

    private final long capacity;

    public IntStringCappedMap(final long capacity) {
        this.capacity = capacity;
    }

    public long getCapacity() {
        return capacity;
    }

    @Override
    public Set<Entry<Integer, String>> entrySet() {
        return new AbstractSet<>() {
            @Override
            public Iterator<Entry<Integer, String>> iterator() {
                return new Iterator<>() {
                    @Override
                    public boolean hasNext() {
                        //implement this method
                        throw new UnsupportedOperationException();
                    }

                    @Override
                    public Entry<Integer, String> next() {
                        //implement this method
                        throw new UnsupportedOperationException();
                    }
                };
            }

            @Override
            public int size() {
                return IntStringCappedMap.this.size();
            }
        };
    }

    @Override
    public String get(final Object key) {
        //implement this method
        throw new UnsupportedOperationException();
    }

    @Override
    public String put(final Integer key, final String value) {
        //implement this method
        throw new UnsupportedOperationException();
    }

    @Override
    public String remove(final Object key) {
        //implement this method
        throw new UnsupportedOperationException();
    }

    @Override
    public int size() {
        //implement this method
        throw new UnsupportedOperationException();
    }

}
Vo_Vik написав:
while (totalSizeOfValues() + value.length() > capacity) {
 // так я видаляю найстаріший елемент, тобто пару яка потрапила перша 
for (Map.Entry<Integer, String> entry : map.entrySet()) { 
map.remove(entry.getKey()); break; }
 }

Я оцей кусок не розумію, нащо там for?

Мені потрібно видалити найстаріший елемент, а як я розумію він перший. Ключ першого елемента я не знаю, тому використовую entrySet(), бо він, як я зрозумів, дає в тому ж порядку в якому записано. Тобто завдяки ньому я отримаю першу пару, візьму пеший ключ і тоді видалю першу пару з map.

На жаль, ще один тест не проходить.
org.opentest4j.AssertionFailedError:
Expected :map(28):[1:999, 3:88, 5:888888, 6:333, 7:111, 8:22, 9:666666]
Actual   :map(28):[0:555555, 1:999, 3:88, 5:888888, 6:333, 7:111, 8:22, 9:666666]


Дякую всім за поряди.

9

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

public static <K, V> Entry<K, V> getFirst(Map<K, V> map) { if (map.isEmpty()) return null; return map.entrySet().iterator().next(); }
Подякували: zxzpogoncuk1

10

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

Спасибі. Так і справді набагато краще

public String put(final Integer key, final String value) {
        if (value.length() > capacity) throw new IllegalArgumentException();
        // перевірка на той самий ключ
        if (map.containsKey(key)) {
            map.remove(key);
            return map.put(key, value);
        }
        while (totalSizeOfValues() + value.length() > capacity) {
            map.remove(getFirst(map).getKey());
        }
        return map.put(key, value);
    }

11

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

І ще коли перезаписуєте той самий ключ, то теж би здалось довжину перевіряти, бо значення може бути довше ніж було.

Подякували: zxzpogoncuk1

12

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

Ваша правда. Тепер і другий тест проходить.

public String put(final Integer key, final String value) {
        if (value.length() > capacity) throw new IllegalArgumentException();
        // перевірка на той самий ключ
        if (map.containsKey(key)) map.remove(key);
        while (totalSizeOfValues() + value.length() > capacity) {
            map.remove(getFirst(map).getKey());
        }
        return map.put(key, value);
    }

Залишилося три методи, які не проходять.

void testPutSubstituting() {
        var map = new IntStringCappedMap(100);
        assertNull(map.put(12, "12"));
        assertNull(map.put(1234, "1234"));
        assertNull(map.put(123, "123"));
        assertNull(map.put(1, "1"));
        //видасть помилку
        assertEquals("1234", map.put(1234, "4321"));
        assertEquals("1", map.put(1, "one"));


        assertAll(
                () -> assertEquals(Set.of("1:one", "12:12", "123:123", "1234:4321"), toStringSet(map)),
                () -> assertEquals(4, map.size())
        );
    }

Expected :1234
Actual   :null

void testPutSubstitutingWithEviction() {
        var map = new IntStringCappedMap(10);
        for (int i = 0; i < 8; i++) {
            assertNull(map.put(8 - i, Integer.toString(8 - i)));
        }
        // тут видасть помилку
        assertEquals("5", map.put(5, "55555"));
        assertAll(
                () -> assertEquals(
                        Set.of("1:1", "2:2", "3:3", "4:4", "5:55555", "6:6"),
                        toStringSet(map)),
                () -> assertEquals(6, map.size())
        );
    }

Expected :5
Actual   :null

void testPutSubstitutingNoEvictionIsNeeded() {
        {
            var map = new IntStringCappedMap(5);
            assertNull(map.put(12, "12"));
            assertNull(map.put(123, "123"));
            // видасть помилку
            assertEquals("123", map.put(123, "321"));

            assertAll(
                    () -> assertEquals(Set.of("12:12", "123:321"), toStringSet(map)),
                    () -> assertEquals(2, map.size())
            );
        }

        {
            var map = new IntStringCappedMap(10);
            for (int i = 0; i < 7; i++) {
                assertNull(map.put(i + 1, Integer.toString(i + 1)));
            }
            assertEquals("4", map.put(4, "4444"));
            assertAll(
                    () -> assertEquals(
                            Set.of("1:1", "2:2", "3:3", "4:4444", "5:5", "6:6", "7:7"),
                            toStringSet(map)),
                    () -> assertEquals(7, map.size())
            );
        }
    }

Expected :123
Actual   :null


Але я не розумію звідки null

13

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

Ну очевидно, що срінгові ключі, треба в інтеджер переводити.

Подякували: zxzpogoncuk1

14

Re: Map. Capped Map. Допоможіть зрозуміти чому падають тести

метод  put
Returns:
the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key, if the implementation supports null values.)
Тому замінив код на

public String put(final Integer key, final String value) {
        if (value.length() > capacity) throw new IllegalArgumentException();
        // перевірка на той самий ключ
        String previousValue = null;
        if (map.containsKey(key)) {
            previousValue = map.remove(key);
        }
        while (totalSizeOfValues() + value.length() > capacity) {
            map.remove(getFirst(map).getKey());
        }

        String str = map.put(key, value);
        if (previousValue != null) return previousValue;
        return str;
    }

Всі тести пройшло.
Щиро дякую за паради. Ви дуже мені допомогли, бо зараз пора іспитів і часу не вистачає.