Close

package closehashes;
public class Dict {
    private int CAPACITY = 10; // количество классов в словаре
    private char[][] 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<out.length; i++)
            out[i] = s.charAt(i);
        return out;
    }

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

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

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

    private int repeatHash(int hash, int i) { // метод считает повторный хэш для существующего хэша i -- номер повторного хэширования
        return (hash + i) % CAPACITY;
    } // todo функция хэширования

    private int find(char[] name){ // метод ищет имя в массиве и возвращает индекс, если его нет, возвращает -1
        // посчитать хэш
        int hash = computeHash(name);

        int i=0; // Номер повторения
        int startInd = repeatHash(hash, i++);
        // проверить на равенство имени если элемент пустой, вернуть -1
        if (a[startInd] == null) return -1;
        // Если нашли совпадение возвращаем индекс найденного имени
        if (arraysEqual(name, a[startInd])) return startInd;

        // создать переменную повторного хэша
        int nextInd=repeatHash(hash, i++);

        // Цикл повторных хэширований пока не вернулись в ту же позицию или не наткнулись на пустой
        while (a[nextInd] != null && nextInd != startInd) {
            if (arraysEqual(name, a[nextInd])) return nextInd; // если нашли, возвращаем позицию
            nextInd = repeatHash(hash, i++); // пересчитываем хэш
        }

        return -1; // если не нашли то элемента нет
    }



    public boolean MEMBER(String x) { // метод проверяет наличие имени в словаре
        char[] name = generateCharArray(x); // Сформировать массив символов
        //найти имя через find
        int ind = find(name);

        return (ind != -1); // Если вернулся не -1, то имя есть в словаре
    }

    public void INSERT(String x) { // метод вставляет имя в словарь, если его ещё там нет
        char[] name = generateCharArray(x); // Сформировать массив символов

        // посчитать хэш
        int hash = computeHash(name);

        int i=0; // Номер повторения
        int startInd = repeatHash(hash, i++);
        // проверить на равенство имени если элемент пустой, вернуть -1
        if (a[startInd] == null) {
            a[startInd] = name;
            return;
        }
        if (arraysEqual(name, a[startInd])) return ;

        // создать переменную повторного хэша
        int nextInd=repeatHash(hash, i++);
        int first_deleted = -1; // Переменная запоминающая индекс первого найденного удалённого
        if (a[startInd][0] == 0) first_deleted = startInd; // если в первом элементе удалённое имя, сразу запоминаем

        while (a[nextInd] != null && nextInd != startInd) { // Цикл повторных хэширований пока не вернулись в тот же хэш или не наткнулись на пустой
            if (arraysEqual(name, a[nextInd])) return; // если нашли выходим

            // если не был найден ещё удалённый и нашли такой запоминаем
            if (first_deleted == -1 && a[nextInd][0] == 0) first_deleted = nextInd;

            nextInd = repeatHash(hash, i++); // пересчитываем хэш
        }

        if (nextInd == startInd) throw new MyException("Словарь заполнен"); // если мы вернулись к тому же хешу, словарь заполнен

        a[(first_deleted == -1)? nextInd: first_deleted] = name; // вставляем имя в удалённый, если он был, иначе туда, куда пришли
    }

    public void DELETE(String x) { // почему бы при проходе для удаления не искать предыдущий а поменять контенты со следующим и удалить следующий
        char[] name = generateCharArray(x); // Сформировать массив символов
        //найти имя через find
        int ind = find(name);

        if (ind == -1) return; // если индекс -1 то такого элемента нет, ничего не делаем

        //записываем в начало символьного массива терминальный символ
        a[ind][0] = 0;
    }

    public void MAKENULL() { // Зануление голов связных списков
        for (int i = 0; i < CAPACITY; i++)
            a[i] = null;
    }

    public void PRINT(){
        for (int i=0; i<CAPACITY; i++){
            if (a[i] != null && a[i][0] != 0) {
                System.out.print(a[i]);
                System.out.print(" ");
            }
        }
        System.out.println();
    }
}