open

package openhashes;
public class Dict {
    private int CLASS_COUNT = 5; // количество классов в словаре
    private Item a[]; // массив классов, хранит головы связных списков

    private static boolean arraysEqual(char[] a, char[] b){ // Метод проверки массивов на равенство
        if (a == b) return true;

        for (int i=0; i<a.length; i++){
            if (a[i] != b[i]) return false;
            if (a[i] == 0) break;
        }
        return true;
    }

    private static char[] generateCharArray(String s){
        char[] out = new char[10];
        for (int i=0; i<s.length(); i++)
            out[i] = s.charAt(i);
        return out;
    }

    private class Item { // Объект связного списка
        char[] name;
        Item next;

        private static void writeName(char[] from, char[] to){ // Метод берёт массив символов from и записывает в to
            // цикл по массиву и перезаписывание символов из from в to
            for (int i=0; i<10 && from[i] != 0; i++)
                to[i] = from[i];
        }

        public Item(char[] x){
            name = new char[10];
            writeName(x, name);
        }

        private void deleteNext(){ // метод удаляет следующий за текущим элемент
            // указатели на следующий равен указателю следующего элемента
            next = next.next;
        }

    }


    public Dict(){ // Конструктор по умолчанию, выделяет память на массив классов
        a = new Item[CLASS_COUNT];
    }

    public Dict(int n){ // Принимает количество возможных элементов множества (область определения)
        CLASS_COUNT = n/10;
        a = new Item[CLASS_COUNT];
    }

    private Item findPrevforMember(char[] name, Item head) { //!на непустом списке! метод ищет предыдущий элемент перед искомым именем в списке, на вход получает голову списка
        // если элемента нет в списке вернётся хвост (prev.next == null)

        // два указателя fir = head sec = head.next
        Item fir = head, sec = head.next;

        // пока второй не равен искомому или null
        while (sec != null && !arraysEqual(sec.name, name)) {
            fir = sec;
            sec = sec.next;
        }

        return fir;// вернуть первый
    }

    private int computeHash(char[] a){ // метод считает хэш для имени
        int out = 0;
        for (int i=0; a[i]!=0 && i<10; i++)
            out = (out + a[i]) % CLASS_COUNT;
        return out;
    }

    public boolean MEMBER(String x){ // метод проверяет наличие имени в словаре
        char[] name = generateCharArray(x); // Сформировать массив символов
        // определить номер класса вычислив хэш
        int hash = computeHash(name);

        // если список пустой вернуть ложь
        if (a[hash] == null) return false;

        // найти предыдущий элемент в списке нужного класса
        Item prev = findPrevforMember(name, a[hash]);

        return (prev.next != null); // если следующий есть то true
    }

    public void INSERT(String x){ // метод вставляет имя в словарь, если его ещё там нет
        char[] name = generateCharArray(x); // Сформировать массив символов
        // определить номер класса вычислив хэш
        int hash = computeHash(name);

        // если список пустой вставить в голову
        if (a[hash] == null) {
            a[hash] = new Item(name);
            return;
        }

        // проверить наличие в классе (вызвать findPrevforMember на списке нужного класса) если есть, ничего не делаем
        Item prev = findPrevforMember(name, a[hash]);

        if (prev.next != null) return; // если следующий есть то элемент уже в списке

        // если элемента нет, добавить его в голову
        Item temp = a[hash]; // указатель чтобы не потерять голову
        a[hash] = new Item(name);
        a[hash].next = temp;
    }

    public void DELETE(String x){
        char[] name = generateCharArray(x); // Сформировать массив символов

        // определить номер класса вычислив хэш
        int hash = computeHash(name);

        // если список пустой ничего не делать
        if (a[hash] == null) return;

        // Если в списке имя находится в голове, удаляем его
        if (arraysEqual(a[hash].name, name)) {
            a[hash] = a[hash].next;
            return;
        }

        // найти предыдущий элемент перед искомым
        Item prev = findPrevforMember(name, a[hash]);

        if (prev.next != null) prev.deleteNext(); // если следующий есть то удаляем
    }

    public void MAKENULL(){
        for (int i=0; i<CLASS_COUNT; i++)
            a[i] = null;
    }

    public void PRINT(){
        for (int i=0; i<CLASS_COUNT; i++){
            if (a[i] != null) {
                System.out.print(a[i].name);
                System.out.print(" ");
                Item el = a[i].next;
                while (el != null) {
                    System.out.print(el.name);
                    System.out.print(" ");
                    el = el.next;
                }
            }
        }
        System.out.println();
    }
}