/* Свой список

Посмотреть, как реализован LinkedList.
Элементы следуют так: 1->2->3->4  и так 4->3->2->1
По образу и подобию создать Solution.
Элементы должны следовать так:
1->3->7->15
    ->8...
 ->4->9
    ->10
2->5->11
    ->12
 ->6->13
    ->14
Удалили 2 и 9
1->3->7->15
    ->8
 ->4->10
Добавили 16,17,18,19,20 (всегда добавляются на самый последний уровень к тем элементам, которые есть)
1->3->7->15
       ->16
    ->8->17
       ->18
 ->4->10->19
        ->20
Удалили 18 и 20
1->3->7->15
       ->16
    ->8->17
 ->4->10->19
Добавили 21 и 22 (всегда добавляются на самый последний уровень к тем элементам, которые есть.
Последний уровень состоит из 15, 16, 17, 19. 19 последний добавленный элемент, 10 - его родитель.
На данный момент 10 не содержит оба дочерних элемента, поэтому 21 добавился к 10. 22 добавляется в следующий уровень.)
1->3->7->15->22
       ->16
    ->8->17
 ->4->10->19
        ->21

Во внутренней реализации элементы должны добавляться по 2 на каждый уровень
Метод getParent должен возвращать элемент, который на него ссылается.
Например, 3 ссылается на 7 и на 8, т.е.  getParent("8")=="3", а getParent("13")=="6"
Строки могут быть любыми.
При удалении элемента должна удаляться вся ветка. Например, list.remove("5") должен удалить "5", "11", "12"
Итерироваться элементы должны в порядке добавления
Доступ по индексу запрещен, воспользуйтесь при необходимости UnsupportedOperationException
Должно быть наследование AbstractList<String>, List<String>, Cloneable, Serializable
Метод main в тестировании не участвует
*/

Написал код, вроде выполнил все условия, тестирую main'ом разными вариантами удалений и добавлений. На выходе ожидаемый правильный результат. Но тестирование не проходит. Подскажите, в чем может быть дело.

public class Solution extends AbstractList<String> implements List<String>, Cloneable, Serializable {

    public static LinkedList<Node> nodesOfTree = new LinkedList<Node>();
    public static ArrayList<String> valuesOfNodes = new ArrayList<String>();
    public static Node root = new Node();

    public static void main(String[] args) {
        List<String> list = new Solution();
        for (int i = 1; i < 16; i++) {
            list.add(String.valueOf(i));
        }
        System.out.println("До удаления:");
        System.out.println("Expected 3, actual is " + ((Solution) list).getParent("8"));
        System.out.println("Expected 7, actual is " + ((Solution) list).getParent("15"));
        list.remove("5");
        System.out.println(System.lineSeparator() + "После операции удадения:");
        System.out.println("Expected null, actual is " + ((Solution) list).getParent("1"));

        System.out.println(System.lineSeparator() + "Количество узлов: " + nodesOfTree.size());
        System.out.println("Левый потомок корня: " + root.leftChild.value);
        System.out.println("Правый потомок корня: " + root.rightChild.value);

        for (Node node : nodesOfTree) {
            System.out.println("значение: " + node.value + ", родитель: " + node.parent.value + ", левый потомок: " + node.leftChild.value + ", правый потомок: " + node.rightChild.value);
        }
        System.out.println( System.lineSeparator() + "СПИСОК ЗНАЧЕНИЙ УЗЛОВ ПОСЛЕ УДАЛЕНИЙ");
        for (String string : valuesOfNodes) System.out.print(string + ", ");
    }

    @Override
    public boolean add(String s) {
        if (nodesOfTree.isEmpty()) {
            Node node = new Node(s);
            root.leftChild = node;
            node.parent = root;
            node.leftChild = new Node();
            node.rightChild = new Node();
        }
        else {
            Node lastNode = nodesOfTree.getLast();
            Node lastParent = lastNode.parent;
            if (!lastNode.isRightChild(lastParent)) {
                Node node = new Node(s);
                lastParent.rightChild = node;
                node.parent = lastParent;
                node.leftChild = new Node();
                node.rightChild = new Node();
            }
            else {
                int indexOfNewParent = nodesOfTree.indexOf(lastParent) + 1;
                ListIterator<Node> iterator = nodesOfTree.listIterator(indexOfNewParent);
                Node newParent = iterator.next();
                Node node = new Node(s);
                newParent.leftChild = node;
                node.parent = newParent;
                node.leftChild = new Node();
                node.rightChild = new Node();

            }
        }
        return true;
    }

    public boolean remove(Object o) {
        int index = valuesOfNodes.indexOf(o);
        ListIterator<Node> nodeIterator = nodesOfTree.listIterator(index);
        Node node = nodeIterator.next();

        if (node.parent.leftChild == node) {
            node.parent.leftChild = node.parent.rightChild;
            node.parent.rightChild = new Node();
        }
        else {
            node.parent.rightChild = new Node();
        }

        ArrayList<Node> nodesForRemove = new ArrayList<Node>();
        ArrayList<String> valuesForRemove = new ArrayList<String>();

        nodesForRemove.add(node);
        valuesForRemove.add(node.value);

        for (int i = 0; i < nodesForRemove.size(); i++) {
            for (Node nodeOfTree : nodesOfTree) {
                ListIterator<Node> iteratorNode = nodesForRemove.listIterator(i);
                node = iteratorNode.next();
                if (nodeOfTree.isChild(node)) {
                    nodesForRemove.add(nodeOfTree);
                    valuesForRemove.add(nodeOfTree.value);
                }
            }
        }
        nodesOfTree.removeAll(nodesForRemove);
        valuesOfNodes.removeAll(valuesForRemove);
        return true;
    }

    public String getParent(String value) {
        try {
            //have to be implemented
            String parent;
            int index = valuesOfNodes.indexOf(value);
            ListIterator<Node> iterator = nodesOfTree.listIterator(index);
            Node node = iterator.next();
            parent = node.parent.value;
            return parent;
        } catch (IndexOutOfBoundsException e) {
            return null;
        }
    }

    @Override
    public String get(int index) {
        throw new UnsupportedOperationException();
    }

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

    public static class Node implements Serializable, Cloneable {
        public String value;
        public Node leftChild;
        public Node rightChild;
        public Node parent;
        public Node() {}
        public Node(String value) {
            this.value = value;
            nodesOfTree.add(this);
            valuesOfNodes.add(this.value);
        }
        public boolean isChild(Node node) {
            return this.parent == node;
        }
        public boolean isRightChild(Node node) {
            return this == node.rightChild;
        }

    }
}

задан 31 Авг '16, 17:08

Core's gravatar image

Core
756
одобрено: 18%

изменено 31 Авг '16, 17:11

...---...

(01 Сен '16, 16:26) Core

Победил!!! В общем оставил я свой "читерский" вариант, не стал создавать итератор. Косяк был в методе clear(). Первый косяк, который вы тоже обнаружили, это статические поля. Исправил. Второй косяк оказался тем же, который был при методе removeALL: clear() вызывал метод iterator(), а метод iterator() у меня, как я писал ранее возвращал итератор valuesOfNodes, т.о поле-список nodesOfTree не чистилось. Я просто решил после каждого метода в мэйне вывести еще размер и обнаружил, что да чистка сасого листа (внешнего) произошла, но при этом количество узлов осталось тем же (метод size у меня вызывает этот же метод у поля NodesOfTree). Вобщем, что изменилось относительно самого первого моего варианта:

//1)убрал статики с полей;
//2)переопределил три метода возвращающие итераторы:

@Override
public Iterator<String> iterator() {
    return valuesOfNodes.iterator();
}

@Override
public ListIterator<String> listIterator() {
    return valuesOfNodes.listIterator();
}

@Override
public ListIterator<String> listIterator(int index) {
    return valuesOfNodes.listIterator(index);
}

//3) переопределил removeAll(), чтобы удаление происходило не только из valuesOfNodes, но и из nodesOfTree:

@Override
public boolean removeAll(Collection<?> c) {
    ArrayList<Object> listForRemoveAll = new ArrayList<Object>(c);
    for (int i = 0; i < listForRemoveAll.size(); i++) {
        remove(listForRemoveAll.get(i));
    }
    return true;
}

//4) Ну и переопределил clear():

@Override
public void clear() {
    super.clear();
    nodesOfTree.clear();
}

Итератор свой не делал, решил обойтись итераторами полей. MameMamuk, спасибо за комменатии и советы. И за main))). Не могли бы вы поделиться своим кодом по этой задаче. Интересно посмотреть, как у вас реавлизовано.

ссылка

опубликован 04 Сен '16, 14:48

Core's gravatar image

Core
756
одобрено: 18%

Задача довольно объемная, боюсь, что вникать в код никто не будет. Поэтому общие советы:

  1. Переопределите итератор.
  2. Напишите тесты всех методов, которые реализует ваш класс.

Может быть что-нибудь я забыл из методов, но у меня был вот такой main:

    List<String> list = new Solution();

    for (int i = 1; i < 16; i++) {
        list.add(String.valueOf(i));
    }
    print((Solution) list);

    list.remove("2");
    print((Solution) list);

    list.remove("15");
    print((Solution) list);

    list.add("15");
    print((Solution) list);

    list.remove("9");
    print((Solution) list);

    for (int i = 16; i <= 20; i++) {
        list.add(String.valueOf(i));
    }
    print((Solution) list);

    list.remove("18");
    list.remove("20");
    print((Solution) list);

    list.add("21");
    list.add("22");
    print((Solution) list);

    System.out.println("16 Expected 7, actual is " + ((Solution) list).getParent("16"));
    System.out.println("10 Expected 4, actual is " + ((Solution) list).getParent("10"));
    System.out.println("17 Expected 8, actual is " + ((Solution) list).getParent("17"));
    System.out.println("19 Expected 10, actual is " + ((Solution) list).getParent("19"));
    System.out.println("21 Expected 10, actual is " + ((Solution) list).getParent("21"));
    System.out.println("22 Expected 15, actual is " + ((Solution) list).getParent("22"));
    System.out.println("1 Expected null, actual is " + ((Solution) list).getParent("1"));

    ByteArrayOutputStream bytes = new ByteArrayOutputStream();
    ObjectOutputStream out = new ObjectOutputStream(bytes);
    out.writeObject(list);
    out.flush();
    out.close();
    ObjectInputStream in = new ObjectInputStream(new ByteArrayInputStream(bytes.toByteArray()));
    List<String> loadedList = (List<String>) in.readObject();
    in.close();
    bytes.close();
    print((Solution) loadedList);

    List<String> clonedList = (List<String>) ((Solution) list).clone();
    print((Solution) clonedList);

    System.out.println("list equals clonedList = " + list.equals(clonedList));
    System.out.println("list equals loadedList = " + list.equals(loadedList));

    loadedList.clear();
    print((Solution) loadedList);

    System.out.println("list contains value 17 = " + list.contains("7"));
    System.out.println("list contains value 22 = " + list.contains("22"));

    System.out.print("list.toArray: ");
    for (Object s : list.toArray())
        System.out.print(s + " ");
    System.out.println();

    List<String> otherList = new ArrayList<>();
    otherList.add("21");
    otherList.add("22");
    System.out.println("list containsAll otherList = " + list.containsAll(otherList));

    list.removeAll(otherList);
    print((Solution) list);

    list.addAll(otherList);
    print((Solution) list);

Взял ваш код и прогнал его со своим main для тестов. Получил такой вывод:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 
15
1, 3, 4, 7, 8, 9, 10, 15, 
8
1, 3, 4, 7, 8, 9, 10, 
7
1, 3, 4, 7, 8, 9, 10, 15, 
8
1, 3, 4, 7, 8, 10, 15, 
7
1, 3, 4, 7, 8, 10, 15, 16, 17, 18, 19, 20, 
12
1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 
10
1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22, 
12
16 Expected 7, actual is 7
10 Expected 4, actual is 4
17 Expected 8, actual is 8
19 Expected 10, actual is 10
21 Expected 10, actual is 10
22 Expected 15, actual is 15
1 Expected null, actual is null
1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22, 
12
1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22, 
12
Exception in thread "main" java.lang.UnsupportedOperationException
    at com.javarush.Solution.get(Solution.java:239)
    at com.javarush.Solution.get(Solution.java:54)
    at java.util.AbstractList$Itr.next(AbstractList.java:358)
    at java.util.AbstractList.equals(AbstractList.java:521)
    at com.javarush.Solution.main(Solution.java:125)

Пока не дошло до методов, которые неявно внутри себя используют итератор - все было ок. Поэтому, мне кажется, вы на верном пути и осталось совсем немного.

ссылка

опубликован 01 Сен '16, 17:09

MameMamuk's gravatar image

MameMamuk
1986
одобрено: 47%

Хм, интересненько. Сейчас попрорбую ваш main. Спасибо

(02 Сен '16, 07:41) Core

Да, вы правы. System.out.println(list), equals() и clear() вызывают методы iterator(), listIterator() и перегруженный listIterator(int index) соответсвенно. А эти товарищи реализованы в АбстактЛисте и возвращают объект итератора АбстактЛиста у котрого метод next() вызывает "ЗЛОЙ" get(int i). Переопредкелил iterator(), listIterator() и перегруженный listIterator(int index), чтобы они соответственно вызывали эти же методы, но у моего поля valuesOfNodes, которе хранит в себе ссылку на обычный ArrayList, get() котрого не вызывает Exceprtion и всё заработало. Но тест не про-хо-дит. Беда-беда. В чем еще может быть причина?

Вот то, что я добавил.

    @Override
public Iterator<String> iterator() {
    return valuesOfNodes.iterator();
}

@Override
public ListIterator<String> listIterator() {
    return valuesOfNodes.listIterator();
}

@Override
public ListIterator<String> listIterator(int index) {
    return valuesOfNodes.listIterator(index);
}

Вот main. Он немного поправлен. Незначительно.

    public static void main(String[] args) throws IOException, ClassNotFoundException, CloneNotSupportedException {
    List<String> list = new Solution();
    for (int i = 1; i < 16; i++) {
        list.add(String.valueOf(i));
    }
    System.out.println((Solution) list);
    list.remove("2");
    System.out.println((Solution) list);
    list.remove("15");
    System.out.println((Solution) list);
    list.add("15");
    System.out.println((Solution) list);
    list.remove("9");
    System.out.println((Solution) list);
    for (int i = 16; i <= 20; i++) {
        list.add(String.valueOf(i));
    }
    System.out.println((Solution) list);
    list.remove("18");
    list.remove("20");
    System.out.println((Solution) list);
    list.add("21");
    list.add("22");
    System.out.println((Solution) list);
    System.out.println("16 Expected 7, actual is " + ((Solution) list).getParent("16"));
    System.out.println("10 Expected 4, actual is " + ((Solution) list).getParent("10"));
    System.out.println("17 Expected 8, actual is " + ((Solution) list).getParent("17"));
    System.out.println("19 Expected 10, actual is " + ((Solution) list).getParent("19"));
    System.out.println("21 Expected 10, actual is " + ((Solution) list).getParent("21"));
    System.out.println("22 Expected 15, actual is " + ((Solution) list).getParent("22"));
    System.out.println("1 Expected null, actual is " + ((Solution) list).getParent("1"));
    ByteArrayOutputStream bytes = new ByteArrayOutputStream();
    ObjectOutputStream out = new ObjectOutputStream(bytes);
    out.writeObject(list);
    out.flush();
    out.close();
    ObjectInputStream in = new ObjectInputStream(new ByteArrayInputStream(bytes.toByteArray()));
    List<String> loadedList = (List<String>) in.readObject();
    in.close();
    bytes.close();
    System.out.println("list: " + (Solution)list);
    System.out.println("loadedList: " + (Solution) loadedList);
    List<String> clonedList = (List<String>) ((Solution) list).clone();
    System.out.println("clonedList: " + (Solution) clonedList);
    System.out.println("list equals clonedList = " + list.equals(clonedList));
    System.out.println("list equals loadedList = " + list.equals(loadedList));
    loadedList.clear();
    System.out.println("list: " + (Solution) list);
    System.out.println("loadedList: " + (Solution) loadedList);
    System.out.println("clonedList: " + (Solution) clonedList);
    System.out.println("list contains value 17 = " + list.contains("17"));
    System.out.println("list contains value 22 = " + list.contains("22"));
    System.out.print("list.toArray: ");
    for (Object s : list.toArray())
        System.out.print(s + " ");
    System.out.println();
    List<String> otherList = new ArrayList<>();
    otherList.add("21");
    otherList.add("22");
    System.out.println("otherList: " + otherList);
    System.out.println("list containsAll otherList = " + list.containsAll(otherList));
    list.removeAll(otherList);
    System.out.println((Solution) list);
    list.addAll(otherList);
    System.out.println((Solution) list);

}

Вот выход:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1, 3, 4, 7, 8, 9, 10, 15]
[1, 3, 4, 7, 8, 9, 10]
[1, 3, 4, 7, 8, 9, 10, 15]
[1, 3, 4, 7, 8, 10, 15]
[1, 3, 4, 7, 8, 10, 15, 16, 17, 18, 19, 20]
[1, 3, 4, 7, 8, 10, 15, 16, 17, 19]
[1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]
16 Expected 7, actual is 7
10 Expected 4, actual is 4
17 Expected 8, actual is 8
19 Expected 10, actual is 10
21 Expected 10, actual is 10
22 Expected 15, actual is 15
1 Expected null, actual is null
list: [1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]
loadedList: [1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]
clonedList: [1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]
list equals clonedList = true
list equals loadedList = true
list: [1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]
loadedList: []
clonedList: [1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]
list contains value 17 = true
list contains value 22 = true
list.toArray: 1 3 4 7 8 10 15 16 17 19 21 22 
otherList: [21, 22]
list containsAll otherList = true
[1, 3, 4, 7, 8, 10, 15, 16, 17, 19]
[1, 3, 4, 7, 8, 10, 15, 16, 17, 19, 21, 22]

Ну что валидатору еще от меня надо? Выручайте. 6ую ночь плохо сплю)))

ссылка

опубликован 02 Сен '16, 14:36

Core's gravatar image

Core
756
одобрено: 18%

изменено 02 Сен '16, 14:44

На самом деле не так много методов.

Очевидные:

@Override
public int size() {...}
@Override
public boolean add(String s) {...}
@Override
public boolean remove(Object o) {...}

Итератор

@Override
public Iterator<String> iterator() {return new Itr();}

При этом у меня была своя собственная реализация итератора (скопипащенная с LinkedList)

private class Itr implements Iterator<String> {...}

Ещё переопределил equals и clear, так как в AbstractList реализуются через ListIterator:

@Override
public boolean equals(Object o)
@Override
public void clear()

Ну и мне было лень проверять все методы AbstractList, перечисленные ниже, поэтому тупо их переопределил с явным выкидыванием UnsupportedOperationException:

@Override
public String get(int index) {throw new UnsupportedOperationException();}
@Override
public String set(int index, String element) {throw new UnsupportedOperationException();}
@Override
public void add(int index, String element) {throw new UnsupportedOperationException();}
@Override
public String remove(int index) {throw new UnsupportedOperationException();}
@Override
public List<String> subList(int fromIndex, int toIndex) {throw new UnsupportedOperationException();}
@Override
protected void removeRange(int fromIndex, int toIndex) {throw new UnsupportedOperationException();}
@Override
public int indexOf(Object o) {throw new UnsupportedOperationException();}
@Override
public int lastIndexOf(Object o) {throw new UnsupportedOperationException();}
@Override
public ListIterator<String> listIterator() {throw new UnsupportedOperationException();}
@Override
public ListIterator<String> listIterator(int index) {throw new UnsupportedOperationException();}
@Override
public boolean addAll(int index, Collection<? extends String> c) {throw new UnsupportedOperationException();}
(04 Сен '16, 06:49) MameMamuk

Да, прошу прощения, не указал, что убрал статики с полей Solution. То, что removeAll некорректно отрабатывает тоже вчера заметил и переопределили его, так, чтобы элементы удалялись из NodesOfTree. Тем не менее, тестирование не проходит. В вашем решении вы вообще в принципе какие методы реализовали?

(04 Сен '16, 05:49) Core

Поправка - в вашем случае так просто Iterator не переопределить, видимо. Потому что у вас в Node нет previous и next - только родитель и листья... У меня в Node были в том числе и previous/next - как раз для реализации своего итератора.

(04 Сен '16, 02:48) MameMamuk

Полагаю, что вы еще какие-то изменения вносили, чтобы получить вывод, приведенный выше? :) Потому что у меня ваш код, приведенный в начале после вызова loadedList.clear() очищает и исходный list из-за того, что у вас nodesOfTree и valuesOfNodes статические.

Мне кажется, что проблема опять-таки в итераторе. Вы немного "считерили", вернув итератор valuesOfNodes. Добавьте для тестирования вывод размера списка до и после removeAll(otherList):

System.out.println("list size before remove = " + list.size());
list.removeAll(otherList);
System.out.println("list size after remove = " + list.size());

У меня получился вот такой вывод:

...
list containsAll otherList = true
list size before remove = 12
list size after remove = 12
[1, 3, 4, 7, 8, 10, 15, 16, 17, 19]
...

А всё потому, что при вызове iterator.remove вызывается remove из класса ArrayList и удаляет элемент только из valuesOfNodes, при этом nodesOfTree никак не изменяется. Мне кажется, стоит "честно" написать свой итератор. Я просто скопипастил ListIterator из LinkedList, убрав методы, которые не нужны в Iterator. А методы listIterator я вообще не трогал - оставил как есть, чтобы возвращали UnsupportedOperationException, потому что они оперируют индексами и вроде как по условию задачи это вполне нормально.

(04 Сен '16, 02:43) MameMamuk
Ваш ответ
включить просмотр

Следить за вопросом

По Email:

После авторизации вы сможете подписаться на любые обновления здесь

Основы Markdown

  • *italic* or _italic_
  • **bold** or __bold__
  • ссылка:[текст](http://url.com/ "заголовок")
  • изображение?![alt текст](/path/img.jpg "заголовок")
  • нумерованный список: 1. Foo 2. Bar
  • Для того чтобы добавить разрыв строки просто добавьте два пробела.
  • основные HTML тэги, также поддерживаются

Тэги:

×64
×27
×1
×1
×1

Задан: 31 Авг '16, 17:08

Просмотров: 538 раз

Отредактирован: 04 Сен '16, 14:48