// Импортируем конструктор связного списка
// (мы будем использовать метод цепочек для разрешения коллизий)
import LinkedList from './linked-list'

// Дефолтный размер таблицы
// (в реальности размер будет намного больше)
const defaultSize = 32

// Хэш-таблица
export default class HashTable {
  constructor(size = defaultSize) {
    // Создаем таблицу указанного размера и
    // заполняем ее пустыми связными списками
    this.buckets = new Array(size).fill(null).map(() => new LinkedList())
    // Хранилище ключей
    this.keys = {}
  }

  // Преобразует ключ в хэшированное значение
  // (хэш-функция)
  hash(key) {
    // Для простоты в качестве хэша используется сумма кодов символов ключа
    // https://developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt
    const hash = [...key].reduce((acc, char) => acc + char.charCodeAt(0), 0)
    // Хэшированное значение не должно превышать размера таблицы
    return hash % this.buckets.length
  }

  // Устанавливает значение по ключу
  set(key, value) {
    // Хэшируем ключ
    // (получаем индекс массива)
    const index = this.hash(key)
    // Сохраняем хэш по ключу
    this.keys[key] = index
    // Извлекаем нужный список
    const bucket = this.buckets[index]
    // Извлекаем узел
    // (значением узла является объект)
    const node = bucket.find({ cb: (value) => value.key === key })
    // Если узел не найден
    if (!node) {
      // Добавляем новый узел
      bucket.append({ key, value })
    } else {
      // Иначе, обновляем значение узла
      node.value.value = value
    }
  }

  // Удаляет значение по ключу
  remove(key) {
    // Хэшируем ключ
    const index = this.hash(key)
    // Удаляем хэш по ключу
    delete this.keys[key]
    // Извлекаем нужный список
    const bucket = this.buckets[index]
    // Извлекаем узел
    const node = bucket.find({ cb: (value) => value.key === key })
    // Возвращаем удаленный узел или `null`,
    // если узел отсутствует
    return node ? bucket.remove(node.value) : null
  }

  // Возвращает значение по ключу
  get(key) {
    // Хэшируем ключ
    const index = this.hash(key)
    // Извлекаем нужный список
    const bucket = this.buckets[index]
    // Извлекаем узел
    const node = bucket.find({ cb: (value) => value.key === key })
    // Возвращаем значение узла или `null`,
    // если узел отсутствует
    return node ? node.value.value : null
  }

  // Определяет наличие ключа
  has(key) {
    // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/hasOwn
    return Object.hasOwn(this.keys, key)
  }

  // Возвращает все ключи
  getKeys() {
    return Object.keys(this.keys)
  }

  // Возвращает все значения
  getValues() {
    // Перебираем списки и возвращаем значения всех узлов
    return this.buckets.reduce((acc, bucket) => {
      return acc.concat(
        // Метод `toArray` преобразует связный список в массив
        bucket.toArray().map((node) => node.value.value),
      )
    }, [])
  }
}

// data-structures/__tests__/hash-table.test.js
import HashTable from '../hash-table'

describe('HashTable', () => {
  it('должен создать хэш-таблицы указанного размера', () => {
    const defaultHashTable = new HashTable()
    expect(defaultHashTable.buckets.length).toBe(32)

    const biggerHashTable = new HashTable(64)
    expect(biggerHashTable.buckets.length).toBe(64)
  })

  it('должен генерировать правильный хэш для ключей', () => {
    const hashTable = new HashTable()

    expect(hashTable.hash('a')).toBe(1)
    expect(hashTable.hash('b')).toBe(2)
    expect(hashTable.hash('abc')).toBe(6)
  })

  it('должен устанавливать, читать и удалять значения с коллизиями', () => {
    const hashTable = new HashTable(3)

    expect(hashTable.hash('a')).toBe(1)
    expect(hashTable.hash('b')).toBe(2)
    expect(hashTable.hash('c')).toBe(0)
    expect(hashTable.hash('d')).toBe(1)

    hashTable.set('a', 'sky-old')
    hashTable.set('a', 'sky')
    hashTable.set('b', 'sea')
    hashTable.set('c', 'earth')
    hashTable.set('d', 'ocean')

    expect(hashTable.has('x')).toBe(false)
    expect(hashTable.has('b')).toBe(true)
    expect(hashTable.has('c')).toBe(true)

    const stringifier = (value) => `${value.key}:${value.value}`

    expect(hashTable.buckets[0].toString(stringifier)).toBe('c:earth')
    expect(hashTable.buckets[1].toString(stringifier)).toBe('a:sky,d:ocean')
    expect(hashTable.buckets[2].toString(stringifier)).toBe('b:sea')

    expect(hashTable.get('a')).toBe('sky')
    expect(hashTable.get('d')).toBe('ocean')
    expect(hashTable.get('x')).toBeNull()

    hashTable.remove('a')

    expect(hashTable.remove('not-existing')).toBeNull()

    expect(hashTable.get('a')).toBeNull()
    expect(hashTable.get('d')).toBe('ocean')

    hashTable.set('d', 'ocean-new')
    expect(hashTable.get('d')).toBe('ocean-new')
  })

  it('должен добавить в таблицу объекты', () => {
    const hashTable = new HashTable()

    hashTable.set('objectKey', { prop1: 'a', prop2: 'b' })

    const object = hashTable.get('objectKey')
    expect(object).toBeDefined()
    expect(object.prop1).toBe('a')
    expect(object.prop2).toBe('b')
  })

  it('должен отслеживать актуальные ключи', () => {
    const hashTable = new HashTable(3)

    hashTable.set('a', 'sky-old')
    hashTable.set('a', 'sky')
    hashTable.set('b', 'sea')
    hashTable.set('c', 'earth')
    hashTable.set('d', 'ocean')

    expect(hashTable.getKeys()).toEqual(['a', 'b', 'c', 'd'])
    expect(hashTable.has('a')).toBe(true)
    expect(hashTable.has('x')).toBe(false)

    hashTable.remove('a')

    expect(hashTable.has('a')).toBe(false)
    expect(hashTable.has('b')).toBe(true)
    expect(hashTable.has('x')).toBe(false)
  })

  it('должен вернуть все значения', () => {
    const hashTable = new HashTable(3)

    hashTable.set('a', 'alpha')
    hashTable.set('b', 'beta')
    hashTable.set('c', 'gamma')

    expect(hashTable.getValues()).toEqual(['gamma', 'alpha', 'beta'])
  })

  it('должен вернуть все значения пустой таблицы', () => {
    const hashTable = new HashTable()
    expect(hashTable.getValues()).toEqual([])
  })

  it('должен вернуть все значения при наличии коллизий', () => {
    const hashTable = new HashTable(3)

    // Ключи `ab` и `ba` в текущей реализации будут иметь одинаковый хэш.
    // Нужно убедиться в сериализации нескольких значений одного списка
    hashTable.set('ab', 'one')
    hashTable.set('ba', 'two')

    hashTable.set('ac', 'three')

    expect(hashTable.getValues()).toEqual(['one', 'two', 'three'])
  })
})

// Импортируем конструктор функции сравнения узлов
import Comparator from '../../utils/comparator'

// Родительский класс для min- и max-куч
export default class Heap {
  constructor(fn) {
    // Кучи должны создаваться с помощью соответствующих подклассов
    if (new.target === Heap) {
      throw new TypeError('Кучу нельзя создавать напрямую!')
    }
    // Представление кучи в виде массива
    this.heapContainer = []
    // Функция сравнения элементов
    this.compare = new Comparator(fn)
  }

  // Возвращает индекс левого потомка
  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1
  }

  // Возвращает индекс правого потомка
  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2
  }

  // Возвращает индекс предка
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2)
  }

  // Проверяет наличие предка
  hasParent(childIndex) {
    return this.getParentIndex(childIndex) >= 0
  }

  // Проверяет наличие левого потомка
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length
  }

  // Проверяет наличие правого потомка
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length
  }

  // Возвращает левого потомка
  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)]
  }

  // Возвращает правого потомка
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)]
  }

  // Возвращает предка
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)]
  }

  // Определяет пустоту кучи
  isEmpty() {
    return this.heapContainer.length === 0
  }

  // Возвращает строковое представление кучи
  toString() {
    return this.heapContainer.toString()
  }

  // Возвращает ссылку на корневой элемент кучи
  // (наименьший для min-кучи, наибольший для max-кучи;
  // элемент не удаляется)
  peek() {
    if (this.isEmpty()) {
      return null
    }

    return this.heapContainer[0]
  }

  // Удаляет и возвращает корневой элемент кучи
  poll() {
    if (this.isEmpty()) {
      return null
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop()
    }

    const item = this.heapContainer[0]
    // Перемещаем последний элемент в начало
    this.heapContainer[0] = this.heapContainer.pop()
    // Просеиваем кучу вниз
    this.heapifyDown()
    // Возвращаем удаленный элемент
    return item
  }

  // Добавляет элемент в кучу
  add(item) {
    // Добавляем новый элемент в конец кучи
    this.heapContainer.push(item)
    // Просеиваем кучу вверх
    this.heapifyUp()

    return this
  }

  // Удаляет элемент из кучи.
  // Принимает элемент и кастомную функцию сравнения элементов
  remove(item, comparator = this.compare) {
    // Определяем количество удаляемых элементов
    const numberOfItemsToRemove = this.find(item, comparator).length

    for (let i = 0; i < numberOfItemsToRemove; i += 1) {
      // Определять индекс удаляемого элемента необходимо на каждой итерации,
      // поскольку куча каждый раз модифицируется
      const index = this.find(item, comparator).pop()

      // Последний элемент просто удаляется
      if (index === this.heapContainer.length - 1) {
        this.heapContainer.pop()
      } else {
        // Иначе, перемещаем последний элемент на освободившееся место
        this.heapContainer[index] = this.heapContainer.pop()
        // Получаем родительский элемент
        const parentItem = this.parent(index)

        // Если предок отсутствует или неправильно расположен,
        // просеиваем кучу вниз
        if (
          this.hasLeftChild(index) &&
          (!parentItem ||
            this.pairIsInCorrectOrder(parentItem, this.heapContainer[index]))
        ) {
          this.heapifyDown(index)
        } else {
          // Иначе, просеиваем кучу вверх
          this.heapifyUp(index)
        }
      }
    }

    return this
  }

  // Находит индексы всех элементов, равных `item`.
  // Принимает искомый элемент и кастомную функцию сравнения элементов
  find(item, comparator = this.compare) {
    const indices = []

    for (let i = 0; i < this.heapContainer.length; i += 1) {
      if (comparator.equal(this.heapContainer[i], item)) {
        indices.push(i)
      }
    }

    return indices
  }

  // Меняет элементы местами
  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexOne]
    this.heapContainer[indexOne] = this.heapContainer[indexTwo]
    this.heapContainer[indexTwo] = tmp
  }

  // Просеивает кучу вверх.
  // Принимает кастомный индекс начальной позиции
  heapifyUp(customStartIndex) {
    // Берем последний элемент (последний в массиве или нижний левый в дереве)
    // и поднимаем его наверх до тех пор, пока он не будет
    // правильно расположен по отношению к предку
    let currentIndex = customStartIndex || this.heapContainer.length - 1

    while (
      this.hasParent(currentIndex) &&
      !this.pairIsInCorrectOrder(
        this.parent(currentIndex),
        this.heapContainer[currentIndex],
      )
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex))
      currentIndex = this.getParentIndex(currentIndex)
    }
  }

  // Просеивает кучу вниз.
  // Принимает кастомный индекс начальной позиции (по умолчанию 0)
  heapifyDown(customStartIndex = 0) {
    // Сравниваем предка с его потомками и
    // меняем местами предка с соответствующим потомком
    // (наименьшим для min-кучи и наибольшим для max-кучи).
    // Затем делаем тоже самое для следующего потомка
    let currentIndex = customStartIndex
    let nextIndex = null

    // Пока есть левый потомок
    while (this.hasLeftChild(currentIndex)) {
      // Если есть правый потомок и
      // потомки расположены в правильном порядке
      if (
        this.hasRightChild(currentIndex) &&
        this.pairIsInCorrectOrder(
          this.rightChild(currentIndex),
          this.leftChild(currentIndex),
        )
      ) {
        // Следующим индексом является индекс правого потомка
        nextIndex = this.getRightChildIndex(currentIndex)
      } else {
        // Иначе, следующим индексом является индекс левого потомка
        nextIndex = this.getLeftChildIndex(currentIndex)
      }

      // Прерываем цикл, если элементы расположены в правильном порядке
      if (
        this.pairIsInCorrectOrder(
          this.heapContainer[currentIndex],
          this.heapContainer[nextIndex],
        )
      ) {
        break
      }

      // Меняем элементы местами
      this.swap(currentIndex, nextIndex)
      // Обновляем текущий индекс
      currentIndex = nextIndex
    }
  }

  // Проверяет, что пара элементов в куче расположена в правильном порядке.
  // Для min-кучи первый элемент всегда должен быть меньше или равен второму.
  // Для max-кучи первый элемент всегда должен быть больше или равен второму.
  // Этот метод должен быть реализован соответствующими подклассами
  // (min-кучей и max-кучей)
  pairIsInCorrectOrder(firstElement, secondElement) {
    throw new Error('Метод сравнения не реализован!')
  }
}

// data-structures/heap/__tests__/min-heap.test.js
import MinHeap from '../min-heap'
import Comparator from '../../../utils/comparator'

describe('MinHeap', () => {
  it('должен создать пустую min-кучу', () => {
    const minHeap = new MinHeap()

    expect(minHeap).toBeDefined()
    expect(minHeap.peek()).toBeNull()
    expect(minHeap.isEmpty()).toBe(true)
  })

  it('должен добавить элементы в кучу и просеять ее вверх', () => {
    const minHeap = new MinHeap()

    minHeap.add(5)
    expect(minHeap.isEmpty()).toBe(false)
    expect(minHeap.peek()).toBe(5)
    expect(minHeap.toString()).toBe('5')

    minHeap.add(3)
    expect(minHeap.peek()).toBe(3)
    expect(minHeap.toString()).toBe('3,5')

    minHeap.add(10)
    expect(minHeap.peek()).toBe(3)
    expect(minHeap.toString()).toBe('3,5,10')

    minHeap.add(1)
    expect(minHeap.peek()).toBe(1)
    expect(minHeap.toString()).toBe('1,3,10,5')

    minHeap.add(1)
    expect(minHeap.peek()).toBe(1)
    expect(minHeap.toString()).toBe('1,1,10,5,3')

    expect(minHeap.poll()).toBe(1)
    expect(minHeap.toString()).toBe('1,3,10,5')

    expect(minHeap.poll()).toBe(1)
    expect(minHeap.toString()).toBe('3,5,10')

    expect(minHeap.poll()).toBe(3)
    expect(minHeap.toString()).toBe('5,10')
  })

  it('должен извлечь элементы из кучи и просеять ее вниз', () => {
    const minHeap = new MinHeap()

    minHeap.add(5)
    minHeap.add(3)
    minHeap.add(10)
    minHeap.add(11)
    minHeap.add(1)

    expect(minHeap.toString()).toBe('1,3,10,11,5')

    expect(minHeap.poll()).toBe(1)
    expect(minHeap.toString()).toBe('3,5,10,11')

    expect(minHeap.poll()).toBe(3)
    expect(minHeap.toString()).toBe('5,11,10')

    expect(minHeap.poll()).toBe(5)
    expect(minHeap.toString()).toBe('10,11')

    expect(minHeap.poll()).toBe(10)
    expect(minHeap.toString()).toBe('11')

    expect(minHeap.poll()).toBe(11)
    expect(minHeap.toString()).toBe('')

    expect(minHeap.poll()).toBeNull()
    expect(minHeap.toString()).toBe('')
  })

  it('должен просеять кучу вниз по правильной ветке', () => {
    const minHeap = new MinHeap()

    minHeap.add(3)
    minHeap.add(12)
    minHeap.add(10)

    expect(minHeap.toString()).toBe('3,12,10')

    minHeap.add(11)
    expect(minHeap.toString()).toBe('3,11,10,12')

    expect(minHeap.poll()).toBe(3)
    expect(minHeap.toString()).toBe('10,11,12')
  })

  it('должен находить индексы элементов', () => {
    const minHeap = new MinHeap()

    minHeap.add(3)
    minHeap.add(12)
    minHeap.add(10)
    minHeap.add(11)
    minHeap.add(11)

    expect(minHeap.toString()).toBe('3,11,10,12,11')

    expect(minHeap.find(5)).toEqual([])
    expect(minHeap.find(3)).toEqual([0])
    expect(minHeap.find(11)).toEqual([1, 4])
  })

  it('должен удалять элементы из кучи с ее просеиванием вниз', () => {
    const minHeap = new MinHeap()

    minHeap.add(3)
    minHeap.add(12)
    minHeap.add(10)
    minHeap.add(11)
    minHeap.add(11)

    expect(minHeap.toString()).toBe('3,11,10,12,11')

    expect(minHeap.remove(3).toString()).toEqual('10,11,11,12')
    expect(minHeap.remove(3).peek()).toEqual(10)
    expect(minHeap.remove(11).toString()).toEqual('10,12')
    expect(minHeap.remove(3).peek()).toEqual(10)
  })

  it('должен удалять элементы из кучи с ее просеиванием вверх', () => {
    const minHeap = new MinHeap()

    minHeap.add(3)
    minHeap.add(10)
    minHeap.add(5)
    minHeap.add(6)
    minHeap.add(7)
    minHeap.add(4)
    minHeap.add(6)
    minHeap.add(8)
    minHeap.add(2)
    minHeap.add(1)

    expect(minHeap.toString()).toBe('1,2,4,6,3,5,6,10,8,7')
    expect(minHeap.remove(8).toString()).toEqual('1,2,4,6,3,5,6,10,7')
    expect(minHeap.remove(7).toString()).toEqual('1,2,4,6,3,5,6,10')
    expect(minHeap.remove(1).toString()).toEqual('2,3,4,6,10,5,6')
    expect(minHeap.remove(2).toString()).toEqual('3,6,4,6,10,5')
    expect(minHeap.remove(6).toString()).toEqual('3,5,4,10')
    expect(minHeap.remove(10).toString()).toEqual('3,5,4')
    expect(minHeap.remove(5).toString()).toEqual('3,4')
    expect(minHeap.remove(3).toString()).toEqual('4')
    expect(minHeap.remove(4).toString()).toEqual('')
  })

  it('должен удалить элементы из кучи, найденные с помощью кастомной функции сравнения', () => {
    const minHeap = new MinHeap()
    minHeap.add('dddd')
    minHeap.add('ccc')
    minHeap.add('bb')
    minHeap.add('a')

    expect(minHeap.toString()).toBe('a,bb,ccc,dddd')

    const comparator = new Comparator((a, b) => {
      if (a.length === b.length) {
        return 0
      }

      return a.length < b.length ? -1 : 1
    })

    minHeap.remove('hey', comparator)
    expect(minHeap.toString()).toBe('a,bb,dddd')
  })

  it('должен удалить элементы из кучи с правильной реструктуризацией дерева', () => {
    const minHeap = new MinHeap()

    minHeap.add(1)
    minHeap.add(2)
    minHeap.add(3)
    minHeap.add(4)
    minHeap.add(5)
    minHeap.add(6)
    minHeap.add(7)
    minHeap.add(8)
    minHeap.add(9)

    expect(minHeap.toString()).toBe('1,2,3,4,5,6,7,8,9')

    minHeap.remove(2)
    expect(minHeap.toString()).toBe('1,4,3,8,5,6,7,9')

    minHeap.remove(4)
    expect(minHeap.toString()).toBe('1,5,3,8,9,6,7')
  })
})

// data-structures/heap/__tests__/max-heap.test.js
import MaxHeap from '../max-heap'
import Comparator from '../../../utils/comparator'

describe('MaxHeap', () => {
  it('должен создать пустую max-кучу', () => {
    const maxHeap = new MaxHeap()

    expect(maxHeap).toBeDefined()
    expect(maxHeap.peek()).toBeNull()
    expect(maxHeap.isEmpty()).toBe(true)
  })

  it('должен добавить элементы в кучу и просеять ее вверх', () => {
    const maxHeap = new MaxHeap()

    maxHeap.add(5)
    expect(maxHeap.isEmpty()).toBe(false)
    expect(maxHeap.peek()).toBe(5)
    expect(maxHeap.toString()).toBe('5')

    maxHeap.add(3)
    expect(maxHeap.peek()).toBe(5)
    expect(maxHeap.toString()).toBe('5,3')

    maxHeap.add(10)
    expect(maxHeap.peek()).toBe(10)
    expect(maxHeap.toString()).toBe('10,3,5')

    maxHeap.add(1)
    expect(maxHeap.peek()).toBe(10)
    expect(maxHeap.toString()).toBe('10,3,5,1')

    maxHeap.add(1)
    expect(maxHeap.peek()).toBe(10)
    expect(maxHeap.toString()).toBe('10,3,5,1,1')

    expect(maxHeap.poll()).toBe(10)
    expect(maxHeap.toString()).toBe('5,3,1,1')

    expect(maxHeap.poll()).toBe(5)
    expect(maxHeap.toString()).toBe('3,1,1')

    expect(maxHeap.poll()).toBe(3)
    expect(maxHeap.toString()).toBe('1,1')
  })

  it('должен извлечь элементы из кучи и просеять ее вниз', () => {
    const maxHeap = new MaxHeap()

    maxHeap.add(5)
    maxHeap.add(3)
    maxHeap.add(10)
    maxHeap.add(11)
    maxHeap.add(1)

    expect(maxHeap.toString()).toBe('11,10,5,3,1')

    expect(maxHeap.poll()).toBe(11)
    expect(maxHeap.toString()).toBe('10,3,5,1')

    expect(maxHeap.poll()).toBe(10)
    expect(maxHeap.toString()).toBe('5,3,1')

    expect(maxHeap.poll()).toBe(5)
    expect(maxHeap.toString()).toBe('3,1')

    expect(maxHeap.poll()).toBe(3)
    expect(maxHeap.toString()).toBe('1')

    expect(maxHeap.poll()).toBe(1)
    expect(maxHeap.toString()).toBe('')

    expect(maxHeap.poll()).toBeNull()
    expect(maxHeap.toString()).toBe('')
  })

  it('должен просеять кучу вниз по правильной ветке', () => {
    const maxHeap = new MaxHeap()

    maxHeap.add(3)
    maxHeap.add(12)
    maxHeap.add(10)

    expect(maxHeap.toString()).toBe('12,3,10')

    maxHeap.add(11)
    expect(maxHeap.toString()).toBe('12,11,10,3')

    expect(maxHeap.poll()).toBe(12)
    expect(maxHeap.toString()).toBe('11,3,10')
  })

  it('должен находить индексы элементов', () => {
    const maxHeap = new MaxHeap()

    maxHeap.add(3)
    maxHeap.add(12)
    maxHeap.add(10)
    maxHeap.add(11)
    maxHeap.add(11)

    expect(maxHeap.toString()).toBe('12,11,10,3,11')

    expect(maxHeap.find(5)).toEqual([])
    expect(maxHeap.find(12)).toEqual([0])
    expect(maxHeap.find(11)).toEqual([1, 4])
  })

  it('должен удалять элементы из кучи с ее просеиванием вниз', () => {
    const maxHeap = new MaxHeap()

    maxHeap.add(3)
    maxHeap.add(12)
    maxHeap.add(10)
    maxHeap.add(11)
    maxHeap.add(11)

    expect(maxHeap.toString()).toBe('12,11,10,3,11')

    expect(maxHeap.remove(12).toString()).toEqual('11,11,10,3')
    expect(maxHeap.remove(12).peek()).toEqual(11)
    expect(maxHeap.remove(11).toString()).toEqual('10,3')
    expect(maxHeap.remove(10).peek()).toEqual(3)
  })

  it('должен удалять элементы из кучи с ее просеиванием вверх', () => {
    const maxHeap = new MaxHeap()

    maxHeap.add(3)
    maxHeap.add(10)
    maxHeap.add(5)
    maxHeap.add(6)
    maxHeap.add(7)
    maxHeap.add(4)
    maxHeap.add(6)
    maxHeap.add(8)
    maxHeap.add(2)
    maxHeap.add(1)

    expect(maxHeap.toString()).toBe('10,8,6,7,6,4,5,3,2,1')
    expect(maxHeap.remove(4).toString()).toEqual('10,8,6,7,6,1,5,3,2')
    expect(maxHeap.remove(3).toString()).toEqual('10,8,6,7,6,1,5,2')
    expect(maxHeap.remove(5).toString()).toEqual('10,8,6,7,6,1,2')
    expect(maxHeap.remove(10).toString()).toEqual('8,7,6,2,6,1')
    expect(maxHeap.remove(6).toString()).toEqual('8,7,1,2')
    expect(maxHeap.remove(2).toString()).toEqual('8,7,1')
    expect(maxHeap.remove(1).toString()).toEqual('8,7')
    expect(maxHeap.remove(7).toString()).toEqual('8')
    expect(maxHeap.remove(8).toString()).toEqual('')
  })

  it('должен удалить элементы из кучи, найденные с помощью кастомной функции сравнения', () => {
    const maxHeap = new MaxHeap()
    maxHeap.add('a')
    maxHeap.add('bb')
    maxHeap.add('ccc')
    maxHeap.add('dddd')

    expect(maxHeap.toString()).toBe('dddd,ccc,bb,a')

    const comparator = new Comparator((a, b) => {
      if (a.length === b.length) {
        return 0
      }

      return a.length < b.length ? -1 : 1
    })

    maxHeap.remove('hey', comparator)
    expect(maxHeap.toString()).toBe('dddd,a,bb')
  })
})

// Импортируем конструктор функции сравнения узлов
import Comparator from '../utils/comparator'
// Импортируем конструктор min-кучи
import MinHeap from './heap/min-heap'

// Очередь с приоритетом.
// Реализация на основе min-кучи
export default class PriorityQueue extends MinHeap {
  constructor() {
    // Инициализируем min-кучу
    super()
    // Карта приоритетов
    this.priorities = new Map()
    // Функция сравнения элементов
    this.compare = new Comparator(this.comparePriorities.bind(this))
  }

  // Добавляет элемент в очередь.
  // Принимает элемент и приоритет.
  // Чем больше приоритет (меньше значение `priority`),
  // тем "выше" элемент находится в очереди
  add(item, priority = 0) {
    // Обновляем приоритеты
    this.priorities.set(item, priority)
    // Добавляем элемент в кучу
    super.add(item)

    return this
  }

  // Удаляет элемент из очереди.
  // Принимает элемент и кастомную функцию сравнения элементов
  remove(item, compare) {
    // Удаляем элемент из кучи
    super.remove(item, compare)
    // Обновляем приоритеты
    this.priorities.delete(item)

    return this
  }

  // Обновляет приоритет.
  // Принимает элемент и новый приоритет
  changePriority(item, priority) {
    // Удаляем элемент из очереди
    this.remove(item, new Comparator(this.compareValues))
    // Добавляем элемент с новым приоритетом
    this.add(item, priority)

    return this
  }

  // Ищет элемент по значению.
  // Возвращает массив индексов
  findByValue(item) {
    return this.find(item, new Comparator(this.compareValues))
  }

  // Определяет наличие элемента
  hasValue(item) {
    return this.findByValue(item).length > 0
  }

  // Сравнивает приоритеты
  comparePriorities(a, b) {
    // Вызываем функцию сравнения значений,
    // передавая ей приоритеты
    return this.compareValues(this.priorities.get(a), this.priorities.get(b))
  }

  // Сравнивает значения
  compareValues(a, b) {
    if (a === b) {
      return 0
    }
    return a < b ? -1 : 1
  }
}

import PriorityQueue from '../priority-queue'

describe('PriorityQueue', () => {
  it('должен создать дефолтную очередь с приоритетом', () => {
    const priorityQueue = new PriorityQueue()

    expect(priorityQueue).toBeDefined()
  })

  it('должен добавить элементы с приоритетом в очередь', () => {
    const priorityQueue = new PriorityQueue()

    priorityQueue.add(10, 1)
    expect(priorityQueue.peek()).toBe(10)

    priorityQueue.add(5, 2)
    expect(priorityQueue.peek()).toBe(10)

    priorityQueue.add(100, 0)
    expect(priorityQueue.peek()).toBe(100)
  })

  it('должен добавить в очередь объекты', () => {
    const priorityQueue = new PriorityQueue()

    const user1 = { name: 'Mike' }
    const user2 = { name: 'Bill' }
    const user3 = { name: 'Jane' }

    priorityQueue.add(user1, 1)
    expect(priorityQueue.peek()).toBe(user1)

    priorityQueue.add(user2, 2)
    expect(priorityQueue.peek()).toBe(user1)

    priorityQueue.add(user3, 0)
    expect(priorityQueue.peek()).toBe(user3)
  })

  it('должен извлечь элементы из очереди согласно приоритету', () => {
    const priorityQueue = new PriorityQueue()

    priorityQueue.add(10, 1)
    priorityQueue.add(5, 2)
    priorityQueue.add(100, 0)
    priorityQueue.add(200, 0)

    expect(priorityQueue.poll()).toBe(100)
    expect(priorityQueue.poll()).toBe(200)
    expect(priorityQueue.poll()).toBe(10)
    expect(priorityQueue.poll()).toBe(5)
  })

  it('должен обновить приоритеты головных узлов', () => {
    const priorityQueue = new PriorityQueue()

    priorityQueue.add(10, 1)
    priorityQueue.add(5, 2)
    priorityQueue.add(100, 0)
    priorityQueue.add(200, 0)

    expect(priorityQueue.peek()).toBe(100)

    priorityQueue.changePriority(100, 10)
    priorityQueue.changePriority(10, 20)

    expect(priorityQueue.poll()).toBe(200)
    expect(priorityQueue.poll()).toBe(5)
    expect(priorityQueue.poll()).toBe(100)
    expect(priorityQueue.poll()).toBe(10)
  })

  it('должен обновить приоритеты внутренних узлов', () => {
    const priorityQueue = new PriorityQueue()

    priorityQueue.add(10, 1)
    priorityQueue.add(5, 2)
    priorityQueue.add(100, 0)
    priorityQueue.add(200, 0)

    expect(priorityQueue.peek()).toBe(100)

    priorityQueue.changePriority(200, 10)
    priorityQueue.changePriority(10, 20)

    expect(priorityQueue.poll()).toBe(100)
    expect(priorityQueue.poll()).toBe(5)
    expect(priorityQueue.poll()).toBe(200)
    expect(priorityQueue.poll()).toBe(10)
  })

  it('должен обновить приоритеты и добавить элемент', () => {
    const priorityQueue = new PriorityQueue()

    priorityQueue.add(10, 1)
    priorityQueue.add(5, 2)
    priorityQueue.add(100, 0)
    priorityQueue.add(200, 0)

    priorityQueue.changePriority(200, 10)
    priorityQueue.changePriority(10, 20)

    priorityQueue.add(15, 15)

    expect(priorityQueue.poll()).toBe(100)
    expect(priorityQueue.poll()).toBe(5)
    expect(priorityQueue.poll()).toBe(200)
    expect(priorityQueue.poll()).toBe(15)
    expect(priorityQueue.poll()).toBe(10)
  })

  it('должен определить наличие значений элементов', () => {
    const priorityQueue = new PriorityQueue()

    priorityQueue.add(10, 1)
    priorityQueue.add(5, 2)
    priorityQueue.add(100, 0)
    priorityQueue.add(200, 0)
    priorityQueue.add(15, 15)

    expect(priorityQueue.hasValue(70)).toBe(false)
    expect(priorityQueue.hasValue(15)).toBe(true)
  })
})

// Импортируем конструктор хэш-таблицы
import HashTable from '../hash-table'

// Последний (завершающий) символ
export const HEAD_CHARACTER = '*'

// Узел префиксного дерева
export default class Node {
  constructor(char, isCompleteWord = false) {
    // Символ
    this.char = char
    // Индикатор завершающего символа
    this.isCompleteWord = isCompleteWord
    // Хэш-таблица потомков
    this.children = new HashTable()
  }

  // Добавляет потомка в дерево
  addChild(char, isCompleteWord = false) {
    // Добавляем узел при отсутствии
    if (!this.hasChild(char)) {
      this.children.set(char, new Node(char, isCompleteWord))
    }

    // Извлекаем узел
    const node = this.getChild(char)

    // Обновляем флаг `isCompleteWord` при необходимости,
    // например, при добавлении слова "car" после слова "carpet",
    // букву "r" нужно пометить как завершающую
    node.isCompleteWord = node.isCompleteWord || isCompleteWord

    // Возвращаем узел
    return node
  }

  // Удаляет потомка
  removeChild(char) {
    // Извлекаем узел
    const node = this.getChild(char)

    // Удаляем узел, только если:
    // - у него нет потомков
    // - node.isCompleteWord === false
    if (node && !node.isCompleteWord && !node.hasChildren()) {
      this.children.remove(char)
    }

    return this
  }

  // Возвращает потомка
  getChild(char) {
    return this.children.get(char)
  }

  // Определяет наличие потомка
  hasChild(char) {
    return this.children.has(char)
  }

  // Определяет наличие потомков
  hasChildren() {
    return this.children.getKeys().length > 0
  }

  // Автодополнение (предложение следующих символов)
  suggestChildren() {
    return [...this.children.getKeys()]
  }

  // Преобразует потомков в строку
  // с указанием признака завершающего символа
  toString() {
    let childrenAsString = this.suggestChildren().toString()
    childrenAsString = childrenAsString ? `:${childrenAsString}` : ''
    const isCompleteString = this.isCompleteWord ? HEAD_CHARACTER : ''

    return `${this.char}${isCompleteString}${childrenAsString}`
  }
}

import TrieNode, { HEAD_CHARACTER } from './node'

// Префиксное дерево
export default class Trie {
  constructor() {
    // Головной (корневой) узел
    this.head = new TrieNode(HEAD_CHARACTER)
  }

  // Добавляет слово (ключ) в дерево
  addWord(word) {
    // Преобразуем строку (слово) в массив символов
    // (вопрос на засыпку: почему лучше не использовать `split()`?
    // Подсказка: попробуйте преобразовать "Hello, ?!")
    const chars = [...word]

    // Текущий узел (начинаем с головного)
    let node = this.head

    // Перебираем символы и добавляем каждый в дерево
    for (let i = 0; i < chars.length; i++) {
      // Индикатор последнего (завершающего) символа
      const isComplete = i === chars.length - 1
      // Добавляем потомка
      node = node.addChild(chars[i], isComplete)
    }

    return this
  }

  // Удаляет слово (ключ) из дерева
  removeWord(word) {
    // Удаляет слово рекурсивно ("сначала в глубину")
    const depthFirstRemove = (node, i = 0) => {
      // Если удаляемый символ находится за пределами слова,
      // ничего не делаем
      if (i >= word.length) return

      // Символ
      const char = word[i]
      // Следующий узел
      const nextNode = node.getChild(char)

      // Если следующий узел отсутствует,
      // ничего не делаем
      if (!nextNode) return

      // Погружаемся глубже
      depthFirstRemove(nextNode, i + 1)

      // Поскольку мы удаляем слово,
      // необходимо обновить флаг `isCompleteWord`
      // его последнего символа
      if (i === word.length - 1) {
        nextNode.isCompleteWord = false
      }

      // Узел удаляется, только если:
      // - у него нет потомков
      // - nextNode.isCompleteWord === false
      node.removeChild(char)
    }

    // Начинаем с головного узла
    depthFirstRemove(this.head)

    return this
  }

  // Автодополнение (предложение следующих символов)
  suggestNextCharacters(word) {
    // Получаем последний символ
    const lastChar = this.getLastCharNode(word)

    // Если последний символ отсутствует
    if (!lastChar) {
      return null
    }

    // Возвращаем массив следующих символов
    return lastChar.suggestChildren()
  }

  // Определяет наличие слова в дереве
  doesWordExist(word) {
    // Получаем последний символ
    const lastChar = this.getLastCharNode(word)

    return Boolean(lastChar) && lastChar.isCompleteWord
  }

  // Возвращает последний символ
  getLastCharNode(word) {
    // Разбиваем слово на символы
    const chars = [...word]
    // Текущий узел (начинаем с головного)
    let node = this.head

    // Перебираем символы
    for (let i = 0; i < chars.length; i++) {
      // Если символ отсутствует
      if (!node.hasChild(chars[i])) {
        return null
      }

      // Извлекаем потомка
      node = node.getChild(chars[i])
    }

    // Возвращаем последний узел
    return node
  }
}

// data-structures/trie/__tests__/node.test.js
import TrieNode from '../node'

describe('TrieNode', () => {
  it('должен создать узел префиксного дерева', () => {
    const trieNode = new TrieNode('c', true)

    expect(trieNode.char).toBe('c')
    expect(trieNode.isCompleteWord).toBe(true)
    expect(trieNode.toString()).toBe('c*')
  })

  it('должен добавить потомков', () => {
    const trieNode = new TrieNode('c')

    trieNode.addChild('a', true)
    trieNode.addChild('o')

    expect(trieNode.toString()).toBe('c:a,o')
  })

  it('должен извлечь потомков', () => {
    const trieNode = new TrieNode('c')

    trieNode.addChild('a')
    trieNode.addChild('o')

    expect(trieNode.getChild('a').toString()).toBe('a')
    expect(trieNode.getChild('a').char).toBe('a')
    expect(trieNode.getChild('o').toString()).toBe('o')
    expect(trieNode.getChild('b')).toBeNull()
  })

  it('должен определить наличие потомков', () => {
    const trieNode = new TrieNode('c')

    expect(trieNode.hasChildren()).toBe(false)

    trieNode.addChild('a')

    expect(trieNode.hasChildren()).toBe(true)
  })

  it('должен определить наличие конкретного потомка', () => {
    const trieNode = new TrieNode('c')

    trieNode.addChild('a')
    trieNode.addChild('o')

    expect(trieNode.hasChild('a')).toBe(true)
    expect(trieNode.hasChild('o')).toBe(true)
    expect(trieNode.hasChild('b')).toBe(false)
  })

  it('должен получить следующие символы', () => {
    const trieNode = new TrieNode('c')

    trieNode.addChild('a')
    trieNode.addChild('o')

    expect(trieNode.suggestChildren()).toEqual(['a', 'o'])
  })

  it('должен удалить потомка, если у него НЕТ потомков', () => {
    const trieNode = new TrieNode('c')
    trieNode.addChild('a')
    expect(trieNode.hasChild('a')).toBe(true)

    trieNode.removeChild('a')
    expect(trieNode.hasChild('a')).toBe(false)
  })

  it('НЕ должен удалять потомков, у которых есть потомки', () => {
    const trieNode = new TrieNode('c')
    trieNode.addChild('a')
    const childNode = trieNode.getChild('a')
    childNode.addChild('r')

    trieNode.removeChild('a')
    expect(trieNode.hasChild('a')).toEqual(true)
  })

  it('НЕ должен удалять потомков, которые являются завершающими символами', () => {
    const trieNode = new TrieNode('c')
    const IS_COMPLETE_WORD = true
    trieNode.addChild('a', IS_COMPLETE_WORD)

    trieNode.removeChild('a')
    expect(trieNode.hasChild('a')).toEqual(true)
  })
})

// data-structures/trie/__tests__/trie.test.js
import Trie from '..'

describe('Trie', () => {
  it('должен создать префиксное дерево', () => {
    const trie = new Trie()

    expect(trie).toBeDefined()
    expect(trie.head.toString()).toBe('*')
  })

  it('должен добавить слова в дерево', () => {
    const trie = new Trie()

    trie.addWord('cat')

    expect(trie.head.toString()).toBe('*:c')
    expect(trie.head.getChild('c').toString()).toBe('c:a')

    trie.addWord('car')
    expect(trie.head.toString()).toBe('*:c')
    expect(trie.head.getChild('c').toString()).toBe('c:a')
    expect(trie.head.getChild('c').getChild('a').toString()).toBe('a:t,r')
    expect(trie.head.getChild('c').getChild('a').getChild('t').toString()).toBe(
      't*',
    )
  })

  it('должен удалить слова из дерева', () => {
    const trie = new Trie()

    trie.addWord('carpet')
    trie.addWord('car')
    trie.addWord('cat')
    trie.addWord('cart')
    expect(trie.doesWordExist('carpet')).toBe(true)
    expect(trie.doesWordExist('car')).toBe(true)
    expect(trie.doesWordExist('cart')).toBe(true)
    expect(trie.doesWordExist('cat')).toBe(true)

    // Пытаемся удалить несуществующее слово
    trie.removeWord('carpool')
    expect(trie.doesWordExist('carpet')).toBe(true)
    expect(trie.doesWordExist('car')).toBe(true)
    expect(trie.doesWordExist('cart')).toBe(true)
    expect(trie.doesWordExist('cat')).toBe(true)

    trie.removeWord('carpet')
    expect(trie.doesWordExist('carpet')).toEqual(false)
    expect(trie.doesWordExist('car')).toEqual(true)
    expect(trie.doesWordExist('cart')).toBe(true)
    expect(trie.doesWordExist('cat')).toBe(true)

    trie.removeWord('cat')
    expect(trie.doesWordExist('car')).toEqual(true)
    expect(trie.doesWordExist('cart')).toBe(true)
    expect(trie.doesWordExist('cat')).toBe(false)

    trie.removeWord('car')
    expect(trie.doesWordExist('car')).toEqual(false)
    expect(trie.doesWordExist('cart')).toBe(true)

    trie.removeWord('cart')
    expect(trie.doesWordExist('car')).toEqual(false)
    expect(trie.doesWordExist('cart')).toBe(false)
  })

  it('должен получить следующие символы', () => {
    const trie = new Trie()

    trie.addWord('cat')
    trie.addWord('cats')
    trie.addWord('car')
    trie.addWord('caption')

    expect(trie.suggestNextCharacters('ca')).toEqual(['t', 'r', 'p'])
    expect(trie.suggestNextCharacters('cat')).toEqual(['s'])
    expect(trie.suggestNextCharacters('cab')).toBeNull()
  })

  it('должен определить наличие слов', () => {
    const trie = new Trie()

    trie.addWord('cat')
    trie.addWord('cats')
    trie.addWord('carpet')
    trie.addWord('car')
    trie.addWord('caption')

    expect(trie.doesWordExist('cat')).toBe(true)
    expect(trie.doesWordExist('cats')).toBe(true)
    expect(trie.doesWordExist('carpet')).toBe(true)
    expect(trie.doesWordExist('car')).toBe(true)
    expect(trie.doesWordExist('cap')).toBe(false)
    expect(trie.doesWordExist('call')).toBe(false)
  })
})