// Функция определения того, является ли переданное число
// результатом возведения числа 2 в какую-либо степень
// (далее - степенью 2)
import isPowerOfTwo from '../../algorithms/math/is-power-of-two'

export default class SegmentTree {
  constructor(arr, fn, fb) {
    this.arr = arr
    // Основная операция
    this.fn = fn
    // Резервная операция
    this.fb = fb
    // Инициализируем представление дерева в виде массива
    this.tree = this.initTree(arr)
    // Строим дерево
    this.buildTree()
  }

  // Инициализирует представление дерева в виде массива
  initTree(arr) {
    let treeLength
    const arrLength = arr.length

    if (isPowerOfTwo(arrLength)) {
      // Если длина массива является степенью 2
      treeLength = arrLength * 2 - 1
    } else {
      // Если длина массива не является степенью 2,
      // нужно найти следующее число, которое является таковым,
      // и использовать его для вычисления длины дерева.
      // Это обусловлено тем, что пустые потомки идеального
      // бинарного дерева должны быть заполнены `null`
      const currentPower = Math.floor(Math.log2(arrLength))
      const nextPower = currentPower + 1
      const nextPowerOfTwoN = 2 ** nextPower

      treeLength = nextPowerOfTwoN * 2 - 1
    }

    return new Array(treeLength).fill(null)
  }

  // Строит дерево
  buildTree() {
    const leftIndex = 0
    const rightIndex = this.arr.length - 1
    const position = 0
    // Обращаемся к рекурсии
    this.buildTreeRecursively(leftIndex, rightIndex, position)
  }

  // Строит дерево рекурсивно
  buildTreeRecursively(leftIndex, rightIndex, position) {
    // Если левый и правый индексы совпадают, значит,
    // мы закончили деление пополам и добрались до листового узла.
    // Значение листа нужно копировать из массива в дерево
    if (leftIndex === rightIndex) {
      this.tree[position] = this.arr[leftIndex]
      return
    }

    // Делим массив на две равные части и обрабатываем каждую рекурсивно
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
    // Обрабатываем левую половину
    this.buildTreeRecursively(
      leftIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    )
    // Обрабатываем правую половину
    this.buildTreeRecursively(
      middleIndex + 1,
      rightIndex,
      this.getRightChildIndex(position),
    )

    // После заполнения всех листьев,
    // мы можем построить дерево снизу вверх
    // с помощью переданной функции
    this.tree[position] = this.fn(
      this.tree[this.getLeftChildIndex(position)],
      this.tree[this.getRightChildIndex(position)],
    )
  }

  // Выполняет запрос диапазона
  rangeQuery(queryLeftIndex, queryRightIndex) {
    const leftIndex = 0
    const rightIndex = this.arr.length - 1
    const position = 0
    // Обращаемся к рекурсии
    return this.rangeQueryRecursively(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      rightIndex,
      position,
    )
  }

  // Выполняет запрос диапазона рекурсивно
  rangeQueryRecursively(
    queryLeftIndex,
    queryRightIndex,
    leftIndex,
    rightIndex,
    position,
  ) {
    if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
      // Полное перекрытие
      return this.tree[position]
    }

    if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
      // Перекрытие отсутствует
      return this.fb
    }

    // Частичное перекрытие
    const middleIndex = Math.floor((leftIndex + rightIndex) / 2)
    const leftFnResult = this.rangeQueryRecursively(
      queryLeftIndex,
      queryRightIndex,
      leftIndex,
      middleIndex,
      this.getLeftChildIndex(position),
    )
    const rightFnResult = this.rangeQueryRecursively(
      queryLeftIndex,
      queryRightIndex,
      middleIndex + 1,
      rightIndex,
      this.getRightChildIndex(position),
    )

    // Обрабатываем узлы с помощью переданной функции
    // и возвращаем результат
    return this.fn(leftFnResult, rightFnResult)
  }

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

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

// data-structures/tree/__tests__/segment-tree.test.js
import SegmentTree from '../segment-tree'

describe('SegmentTree', () => {
  it('должен построить дерево для массива #0 с длиной, являющейся степенью 2', () => {
    const array = [-1, 2]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([-1, -1, 2])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен построить дерево для массива #1 с длиной, являющейся степень 2', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([-1, -1, 0, -1, 2, 4, 0])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен построить дерево для массива #0 с длиной, НЕ являющейся степень 2', () => {
    const array = [0, 1, 2]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([0, 0, 2, 0, 1, null, null])
    expect(segmentTree.tree.length).toBe(2 * 4 - 1)
  })

  it('должен построить дерево для массива #1 с длиной, НЕ являющейся степень 2', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.tree).toEqual([
      -1,
      -1,
      0,
      -1,
      4,
      0,
      1,
      -1,
      3,
      null,
      null,
      0,
      2,
      null,
      null,
    ])
    expect(segmentTree.tree.length).toBe(2 * 8 - 1)
  })

  it('должен построить максимальное дерево (предок является максимальным потомком)', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, Math.max, -Infinity)

    expect(segmentTree.tree).toEqual([4, 2, 4, -1, 2, 4, 0])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен построить суммарное дерево (редок является суммой потомков)', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, (a, b) => a + b, 0)

    expect(segmentTree.tree).toEqual([5, 1, 4, -1, 2, 4, 0])
    expect(segmentTree.tree.length).toBe(2 * array.length - 1)
  })

  it('должен выполнить минимальный запрос диапазона на массиве с длиной, являющейся степенью 2', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.rangeQuery(0, 5)).toBe(-1)
    expect(segmentTree.rangeQuery(0, 2)).toBe(-1)
    expect(segmentTree.rangeQuery(1, 3)).toBe(0)
    expect(segmentTree.rangeQuery(2, 4)).toBe(0)
    expect(segmentTree.rangeQuery(4, 5)).toBe(1)
    expect(segmentTree.rangeQuery(2, 2)).toBe(4)
  })

  it('должен выполнить минимальный запрос диапазона на массиве с длиной, НЕ являющейся степенью 2', () => {
    const array = [-1, 2, 4, 0]
    const segmentTree = new SegmentTree(array, Math.min, Infinity)

    expect(segmentTree.rangeQuery(0, 4)).toBe(-1)
    expect(segmentTree.rangeQuery(0, 1)).toBe(-1)
    expect(segmentTree.rangeQuery(1, 3)).toBe(0)
    expect(segmentTree.rangeQuery(1, 2)).toBe(2)
    expect(segmentTree.rangeQuery(2, 3)).toBe(0)
    expect(segmentTree.rangeQuery(2, 2)).toBe(4)
  })

  it('должен выполнить максимальный запрос диапазона', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, Math.max, -Infinity)

    expect(segmentTree.rangeQuery(0, 5)).toBe(4)
    expect(segmentTree.rangeQuery(0, 1)).toBe(3)
    expect(segmentTree.rangeQuery(1, 3)).toBe(4)
    expect(segmentTree.rangeQuery(2, 4)).toBe(4)
    expect(segmentTree.rangeQuery(4, 5)).toBe(2)
    expect(segmentTree.rangeQuery(3, 3)).toBe(0)
  })

  it('должен выполнить суммарный запрос диапазона', () => {
    const array = [-1, 3, 4, 0, 2, 1]
    const segmentTree = new SegmentTree(array, (a, b) => a + b, 0)

    expect(segmentTree.rangeQuery(0, 5)).toBe(9)
    expect(segmentTree.rangeQuery(0, 1)).toBe(2)
    expect(segmentTree.rangeQuery(1, 3)).toBe(7)
    expect(segmentTree.rangeQuery(2, 4)).toBe(6)
    expect(segmentTree.rangeQuery(4, 5)).toBe(3)
    expect(segmentTree.rangeQuery(3, 3)).toBe(0)
  })
})

export default class FenwickTree {
  // Конструктор создает дерево Фенвика размера `size`,
  // однако, размер дерева `n+1`, потому что индексация начинается с `1`
  constructor(size) {
    this.size = size
    // Заполняем массив нулями
    this.tree = new Array(size + 1).fill(0)
  }

  // Прибавляет значение к существующему на указанной позиции
  increase(position, value) {
    if (position < 1 || position > this.size) {
      throw new Error('Позиция находится за пределами разрешенного диапазона')
    }

    // magic! :D
    for (let i = position; i <= this.size; i += i & -i) {
      this.tree[i] += value
    }

    return this
  }

  // Возвращает сумму от индекса 1 до указанной позиции
  query(position) {
    if (position < 1 || position > this.size) {
      throw new Error('Позиция находится за пределами разрешенного диапазона')
    }

    let sum = 0

    // magic! :D
    for (let i = position; i > 0; i -= i & -i) {
      sum += this.tree[i]
    }

    return sum
  }

  // Возвращает сумму от `leftIndex` до `rightIndex`
  queryRange(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) {
      throw new Error('Левый индекс не может превышать правый')
    }

    if (leftIndex === 1) {
      return this.query(rightIndex)
    }

    return this.query(rightIndex) - this.query(leftIndex - 1)
  }
}

// data-structures/tree/__tests__/fenwick-tree.test.js
import FenwickTree from '../fenwick-tree'

describe('FenwickTree', () => {
  it('должен создать деревья правильного размера', () => {
    const tree1 = new FenwickTree(5)
    expect(tree1.tree.length).toBe(5 + 1)

    for (let i = 0; i < 5; i += 1) {
      expect(tree1.tree[i]).toBe(0)
    }

    const tree2 = new FenwickTree(50)
    expect(tree2.tree.length).toBe(50 + 1)
  })

  it('должен создать правильное дерево', () => {
    const inputArray = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3]

    const tree = new FenwickTree(inputArray.length)
    expect(tree.tree.length).toBe(inputArray.length + 1)

    inputArray.forEach((value, index) => {
      tree.increase(index + 1, value)
    })

    expect(tree.tree).toEqual([0, 3, 5, -1, 10, 5, 9, -3, 19, 7, 9, 3])

    expect(tree.query(1)).toBe(3)
    expect(tree.query(2)).toBe(5)
    expect(tree.query(3)).toBe(4)
    expect(tree.query(4)).toBe(10)
    expect(tree.query(5)).toBe(15)
    expect(tree.query(6)).toBe(19)
    expect(tree.query(7)).toBe(16)
    expect(tree.query(8)).toBe(19)
    expect(tree.query(9)).toBe(26)
    expect(tree.query(10)).toBe(28)
    expect(tree.query(11)).toBe(31)

    expect(tree.queryRange(1, 1)).toBe(3)
    expect(tree.queryRange(1, 2)).toBe(5)
    expect(tree.queryRange(2, 4)).toBe(7)
    expect(tree.queryRange(6, 9)).toBe(11)

    tree.increase(3, 1)

    expect(tree.query(1)).toBe(3)
    expect(tree.query(2)).toBe(5)
    expect(tree.query(3)).toBe(5)
    expect(tree.query(4)).toBe(11)
    expect(tree.query(5)).toBe(16)
    expect(tree.query(6)).toBe(20)
    expect(tree.query(7)).toBe(17)
    expect(tree.query(8)).toBe(20)
    expect(tree.query(9)).toBe(27)
    expect(tree.query(10)).toBe(29)
    expect(tree.query(11)).toBe(32)

    expect(tree.queryRange(1, 1)).toBe(3)
    expect(tree.queryRange(1, 2)).toBe(5)
    expect(tree.queryRange(2, 4)).toBe(8)
    expect(tree.queryRange(6, 9)).toBe(11)
  })

  it('должен правильно выполнить запросы', () => {
    const tree = new FenwickTree(5)

    tree.increase(1, 4)
    tree.increase(3, 7)

    expect(tree.query(1)).toBe(4)
    expect(tree.query(3)).toBe(11)
    expect(tree.query(5)).toBe(11)
    expect(tree.queryRange(2, 3)).toBe(7)

    tree.increase(2, 5)
    expect(tree.query(5)).toBe(16)

    tree.increase(1, 3)
    expect(tree.queryRange(1, 1)).toBe(7)
    expect(tree.query(5)).toBe(19)
    expect(tree.queryRange(1, 5)).toBe(19)
  })

  it('должен выбросить исключения', () => {
    const tree = new FenwickTree(5)

    const increaseAtInvalidLowIndex = () => {
      tree.increase(0, 1)
    }

    const increaseAtInvalidHighIndex = () => {
      tree.increase(10, 1)
    }

    const queryInvalidLowIndex = () => {
      tree.query(0)
    }

    const queryInvalidHighIndex = () => {
      tree.query(10)
    }

    const rangeQueryInvalidIndex = () => {
      tree.queryRange(3, 2)
    }

    expect(increaseAtInvalidLowIndex).toThrowError()
    expect(increaseAtInvalidHighIndex).toThrowError()
    expect(queryInvalidLowIndex).toThrowError()
    expect(queryInvalidHighIndex).toThrowError()
    expect(rangeQueryInvalidIndex).toThrowError()
  })
})

// Связный список
import LinkedList from '../linked-list'

// Функция сравнения ребер
const edgeComparator = (a, b) => {
  if (a.getKey() === b.getKey()) {
    return 0
  }

  return a.getKey() < b.getKey() ? -1 : 1
}

// Функция преобразования соседних узлов
const convertNeighbors = (node) => {
  return node.value.from === this ? node.value.to : node.value.from
}

export default class Node {
  constructor(value) {
    if (!value) {
      throw new Error('Узел графа должен иметь значение!')
    }

    // Значение узла
    this.value = value
    // Связный список ребер
    this.edges = new LinkedList(edgeComparator)
  }

  // Добавляет ребро в список
  addEdge(edge) {
    this.edges.append(edge)

    return this
  }

  // Удаляет ребро из списка
  removeEdge(edge) {
    this.edges.remove(edge)

    return this
  }

  // Удаляет все ребра
  removeAllEdges() {
    this.getEdges().forEach((edge) => {
      this.removeEdge(edge)
    })

    return this
  }

  // Возвращает список соседей
  getNeighbors() {
    const edges = this.edges.toArray()

    return edges.map(convertNeighbors)
  }

  // Возвращает список ребер в виде массива значений
  getEdges() {
    return this.edges.toArray().map((node) => node.value)
  }

  // Возвращает длину (глубину) узла
  getDegree() {
    return this.edges.toArray().length
  }

  // Возвращает значение узла
  getKey() {
    return this.value
  }

  // Определяет наличие ребра
  hasEdge(edge) {
    const _edge = this.edges.find({ cb: (node) => node === edge })

    return Boolean(_edge)
  }

  // Определяет наличие соседа
  hasNeighbor(node) {
    const _node = this.edges.find({
      cb: (n) => n.to === node || n.from === node,
    })

    return Boolean(_node)
  }

  // Выполняет поиск ребра по узлу
  findEdge(node) {
    const _node = this.edges.find({
      cb: (n) => n.to === node || n.from === node,
    })

    return _node ? _node.value : null
  }

  // Возвращает строковое представление узла.
  // Принимает кастомную функцию стрингификации
  toString(cb) {
    return cb ? cb(this.value) : `${this.value}`
  }
}

// data-structures/graph/__tests__/node.test.js
import Node from '../node'
import Edge from '../edge'

describe('Node', () => {
  it('должен выбросить исключение при создании узла без значения', () => {
    let node = null

    function createEmptyVertex() {
      node = new Node()
    }

    expect(node).toBeNull()
    expect(createEmptyVertex).toThrow()
  })

  it('должен создать узел графа', () => {
    const node = new Node('A')

    expect(node).toBeDefined()
    expect(node.value).toBe('A')
    expect(node.toString()).toBe('A')
    expect(node.getKey()).toBe('A')
    expect(node.edges.toString()).toBe('')
    expect(node.getEdges()).toEqual([])
  })

  it('должен добавить ребра в узел и определить их наличие', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.hasEdge(edgeAB)).toBe(true)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)
    expect(nodeA.getEdges().length).toBe(1)
    expect(nodeA.getEdges()[0].toString()).toBe('A_B')
  })

  it('должен удалить определенные ребра из узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    nodeA.addEdge(edgeAB).addEdge(edgeAC)

    expect(nodeA.hasEdge(edgeAB)).toBe(true)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)

    expect(nodeA.hasEdge(edgeAC)).toBe(true)
    expect(nodeC.hasEdge(edgeAC)).toBe(false)

    expect(nodeA.getEdges().length).toBe(2)

    expect(nodeA.getEdges()[0].toString()).toBe('A_B')
    expect(nodeA.getEdges()[1].toString()).toBe('A_C')

    nodeA.removeEdge(edgeAB)
    expect(nodeA.hasEdge(edgeAB)).toBe(false)
    expect(nodeA.hasEdge(edgeAC)).toBe(true)
    expect(nodeA.getEdges()[0].toString()).toBe('A_C')

    nodeA.removeEdge(edgeAC)
    expect(nodeA.hasEdge(edgeAB)).toBe(false)
    expect(nodeA.hasEdge(edgeAC)).toBe(false)
    expect(nodeA.getEdges().length).toBe(0)
  })

  it('должна удалить все ребра из узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    nodeA.addEdge(edgeAB).addEdge(edgeAC)

    expect(nodeA.hasEdge(edgeAB)).toBe(true)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)

    expect(nodeA.hasEdge(edgeAC)).toBe(true)
    expect(nodeC.hasEdge(edgeAC)).toBe(false)

    expect(nodeA.getEdges().length).toBe(2)

    nodeA.removeAllEdges()

    expect(nodeA.hasEdge(edgeAB)).toBe(false)
    expect(nodeB.hasEdge(edgeAB)).toBe(false)

    expect(nodeA.hasEdge(edgeAC)).toBe(false)
    expect(nodeC.hasEdge(edgeAC)).toBe(false)

    expect(nodeA.getEdges().length).toBe(0)
  })

  it('должен вернуть соседей узла в случае, если текущий узел является начальным', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    nodeA.addEdge(edgeAB).addEdge(edgeAC)

    expect(nodeB.getNeighbors()).toEqual([])

    const neighbors = nodeA.getNeighbors()

    expect(neighbors.length).toBe(2)
    expect(neighbors[0]).toEqual(nodeB)
    expect(neighbors[1]).toEqual(nodeC)
  })

  it('должен вернуть соседей узла в случае, если текущий узел является конечным', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeBA = new Edge(nodeB, nodeA)
    const edgeCA = new Edge(nodeC, nodeA)
    nodeA.addEdge(edgeBA).addEdge(edgeCA)

    expect(nodeB.getNeighbors()).toEqual([])

    const neighbors = nodeA.getNeighbors()

    expect(neighbors.length).toBe(2)
    expect(neighbors[0]).toEqual(nodeB)
    expect(neighbors[1]).toEqual(nodeC)
  })

  it('должен определить наличие соседнего узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.hasNeighbor(nodeB)).toBe(true)
    expect(nodeA.hasNeighbor(nodeC)).toBe(false)
  })

  it('должен найти ребро по узлу', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.findEdge(nodeB)).toEqual(edgeAB)
    expect(nodeA.findEdge(nodeC)).toBeNull()
  })

  it('должен вычислить глубину узла', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')

    expect(nodeA.getDegree()).toBe(0)

    const edgeAB = new Edge(nodeA, nodeB)
    nodeA.addEdge(edgeAB)

    expect(nodeA.getDegree()).toBe(1)

    const edgeBA = new Edge(nodeB, nodeA)
    nodeA.addEdge(edgeBA)

    expect(nodeA.getDegree()).toBe(2)

    nodeA.addEdge(edgeAB)
    expect(nodeA.getDegree()).toBe(3)

    expect(nodeA.getEdges().length).toEqual(3)
  })
})

// data-structures/graph/__tests__/edge.test.js
import Edge from '../edge'
import Node from '../node'

describe('Edge', () => {
  it('должена создать ребро графа с дефолтным весом', () => {
    const from = new Node('A')
    const to = new Node('B')
    const edge = new Edge(from, to)

    expect(edge.getKey()).toBe('A_B')
    expect(edge.toString()).toBe('A_B')
    expect(edge.from).toEqual(from)
    expect(edge.to).toEqual(to)
    expect(edge.weight).toEqual(0)
  })

  it('должена создать граф с указанным весом', () => {
    const from = new Node('A')
    const to = new Node('B')
    const edge = new Edge(from, to, 10)

    expect(edge.from).toEqual(from)
    expect(edge.to).toEqual(to)
    expect(edge.weight).toEqual(10)
  })

  it('должен инвертировать ребро', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const edge = new Edge(nodeA, nodeB, 10)

    expect(edge.from).toEqual(nodeA)
    expect(edge.to).toEqual(nodeB)
    expect(edge.weight).toEqual(10)

    edge.reverse()

    expect(edge.from).toEqual(nodeB)
    expect(edge.to).toEqual(nodeA)
    expect(edge.weight).toEqual(10)
  })
})

export default class Graph {
  constructor(isDirected = false) {
    // Индикатор направленности графа
    // (по умолчанию граф является ненаправленным)
    this.isDirected = isDirected
    // Узлы
    this.nodes = {}
    // Ребра
    this.edges = {}
  }

  // Добавляет узел в граф
  addNode(newNode) {
    this.nodes[newNode.getKey()] = newNode

    return this
  }

  // Возвращает узел по ключу
  getNodeByKey(key) {
    return this.nodes[key]
  }

  // Возвращает соседние узлы
  getNeighbors(node) {
    return node.getNeighbors()
  }

  // Возвращает значения всех узлов
  getAllNodes() {
    return Object.values(this.nodes)
  }

  // Возвращает значения всех ребер
  getAllEdges() {
    return Object.values(this.edges)
  }

  // Добавляет ребро в граф
  addEdge(newEdge) {
    // Пытаемся найти начальную и конечную вершины
    let from = this.getNodeByKey(newEdge.from.getKey())
    let to = this.getNodeByKey(newEdge.to.getKey())

    // Добавляем начальную вершину
    if (!from) {
      this.addNode(newEdge.from)
      from = this.getNodeByKey(newEdge.from.getKey())
    }

    // Добавляем конечную вершину
    if (!to) {
      this.addNode(newEdge.to)
      to = this.getNodeByKey(newEdge.to.getKey())
    }

    // Если ребро уже добавлено
    if (this.edges[newEdge.getKey()]) {
      throw new Error('Ребро уже добавлено!')
    } else {
      // Добавляем ребро
      this.edges[newEdge.getKey()] = newEdge
    }

    // Добавляем ребро в вершины
    if (this.isDirected) {
      from.addEdge(newEdge)
    } else {
      from.addEdge(newEdge)
      to.addEdge(newEdge)
    }

    return this
  }

  // Удаляет ребро из графа
  removeEdge(edge) {
    if (this.edges[edge.getKey()]) {
      // Удаляем ребро
      delete this.edges[edge.getKey()]
    } else {
      throw new Error('Ребро не найдено!')
    }

    // Пытаемся найти начальную и конечную вершины
    let from = this.getNodeByKey(edge.from.getKey())
    let to = this.getNodeByKey(edge.to.getKey())

    // Удаляем ребро из вершин
    from && from.removeEdge(edge)
    to && to.removeEdge(edge)
  }

  // Находит ребро в графе
  findEdge(from, to) {
    // Находим узел по начальному ключу
    const node = this.getNodeByKey(from.getKey())

    if (!node) return null

    // Пытаемся найти конечное ребро
    return node.findEdge(to)
  }

  // Возвращает вес графа
  getWeight() {
    // Суммируем веса всех ребер
    return this.getAllEdges().reduce((acc, edge) => acc + edge.weight, 0)
  }

  // Инвертирует граф
  reverse() {
    // Для каждого ребра
    this.getAllEdges().forEach((edge) => {
      // Удаляем ребро из графа
      this.removeEdge(edge)

      // Инвертируем ребро
      edge.reverse()

      // Снова добавляем ребро в граф
      this.addEdge(edge)
    })

    return this
  }

  // Возвращает индексы узлов в виде объекта
  getNodesIndices() {
    const indices = {}

    this.getAllNodes().forEach((node, index) => {
      indices[node.getKey()] = index
    })

    return indices
  }

  // Возвращает матрицу смежности
  getAdjacencyMatrix() {
    // Узлы
    const nodes = this.getAllNodes()
    // Индексы узлов
    const indices = this.getNodesIndices()
    // Инициализируем матрицу смежности (заполняем ее `null`)
    const matrix = new Array(nodes.length)
      .fill()
      .map(() => new Array(nodes.length).fill(null))

    // Формируем матрицу.
    // Перебираем узлы
    nodes.forEach((node, index) => {
      // Перебираем соседей узла
      node.getNeighbors().forEach((neighbor) => {
        // Индекс соседа
        const neighborIndex = indices[neighbor.getKey()]
        // [индекс узла][индекс соседа] = вес ребра
        matrix[index][neighborIndex] = this.findEdge(node, neighbor).weight
      })
    })

    return matrix
  }

  // Возвращает строковое представление графа
  toString() {
    return Object.keys(this.nodes).toString()
  }
}

// data-structures/graph/__tests__/graph.test.js
import Graph from '..'
import Node from '../node'
import Edge from '../edge'

describe('Graph', () => {
  it('должен добавить узлы в граф', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')

    graph.addNode(nodeA).addNode(nodeB)

    expect(graph.toString()).toBe('A,B')
    expect(graph.getNodeByKey(nodeA.getKey())).toEqual(nodeA)
    expect(graph.getNodeByKey(nodeB.getKey())).toEqual(nodeB)
  })

  it('должен добавить ребра в ненаправленный граф', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')

    const edgeAB = new Edge(nodeA, nodeB)

    graph.addEdge(edgeAB)

    expect(graph.getAllNodes().length).toBe(2)
    expect(graph.getAllNodes()[0]).toEqual(nodeA)
    expect(graph.getAllNodes()[1]).toEqual(nodeB)

    const graphNodeA = graph.getNodeByKey(nodeA.getKey())
    const graphNodeB = graph.getNodeByKey(nodeB.getKey())

    expect(graph.toString()).toBe('A,B')
    expect(graphNodeA).toBeDefined()
    expect(graphNodeB).toBeDefined()

    expect(graph.getNodeByKey('not existing')).toBeUndefined()

    expect(graphNodeA.getNeighbors().length).toBe(1)
    expect(graphNodeA.getNeighbors()[0]).toEqual(nodeB)
    expect(graphNodeA.getNeighbors()[0]).toEqual(graphNodeB)

    expect(graphNodeB.getNeighbors().length).toBe(1)
    expect(graphNodeB.getNeighbors()[0]).toEqual(nodeA)
    expect(graphNodeB.getNeighbors()[0]).toEqual(graphNodeA)
  })

  it('должен добавить ребра в направленный граф', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')

    const edgeAB = new Edge(nodeA, nodeB)

    graph.addEdge(edgeAB)

    const graphNodeA = graph.getNodeByKey(nodeA.getKey())
    const graphNodeB = graph.getNodeByKey(nodeB.getKey())

    expect(graph.toString()).toBe('A,B')
    expect(graphNodeA).toBeDefined()
    expect(graphNodeB).toBeDefined()

    expect(graphNodeA.getNeighbors().length).toBe(1)
    expect(graphNodeA.getNeighbors()[0]).toEqual(nodeB)
    expect(graphNodeA.getNeighbors()[0]).toEqual(graphNodeB)

    expect(graphNodeB.getNeighbors().length).toBe(0)
  })

  it('должен найти ребра по узлам в ненаправленном графе', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB, 10)

    graph.addEdge(edgeAB)

    const graphEdgeAB = graph.findEdge(nodeA, nodeB)
    const graphEdgeBA = graph.findEdge(nodeB, nodeA)
    const graphEdgeAC = graph.findEdge(nodeA, nodeC)
    const graphEdgeCA = graph.findEdge(nodeC, nodeA)

    expect(graphEdgeAC).toBeNull()
    expect(graphEdgeCA).toBeNull()
    expect(graphEdgeAB).toEqual(edgeAB)
    expect(graphEdgeBA).toEqual(edgeAB)
    expect(graphEdgeAB.weight).toBe(10)
  })

  it('должен найти ребра по узлам в направленном графе', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB, 10)

    graph.addEdge(edgeAB)

    const graphEdgeAB = graph.findEdge(nodeA, nodeB)
    const graphEdgeBA = graph.findEdge(nodeB, nodeA)
    const graphEdgeAC = graph.findEdge(nodeA, nodeC)
    const graphEdgeCA = graph.findEdge(nodeC, nodeA)

    expect(graphEdgeAC).toBeNull()
    expect(graphEdgeCA).toBeNull()
    expect(graphEdgeBA).toBeNull()
    expect(graphEdgeAB).toEqual(edgeAB)
    expect(graphEdgeAB.weight).toBe(10)
  })

  it('должен вернуть соседей узла', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)

    graph.addEdge(edgeAB).addEdge(edgeAC)

    const neighbors = graph.getNeighbors(nodeA)

    expect(neighbors.length).toBe(2)
    expect(neighbors[0]).toEqual(nodeB)
    expect(neighbors[1]).toEqual(nodeC)
  })

  it('должен выбросить исключение при повторном добавлении ребра', () => {
    function addSameEdgeTwice() {
      const graph = new Graph(true)

      const nodeA = new Node('A')
      const nodeB = new Node('B')

      const edgeAB = new Edge(nodeA, nodeB)

      graph.addEdge(edgeAB).addEdge(edgeAB)
    }

    expect(addSameEdgeTwice).toThrow()
  })

  it('должен вернуть список всех добавленных узлов', () => {
    const graph = new Graph(true)

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)

    graph.addEdge(edgeAB).addEdge(edgeBC)

    const edges = graph.getAllEdges()

    expect(edges.length).toBe(2)
    expect(edges[0]).toEqual(edgeAB)
    expect(edges[1]).toEqual(edgeBC)
  })

  it('должен вычислить общий вес дефолтного графа', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)
    const edgeAD = new Edge(nodeA, nodeD)

    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeAD)

    expect(graph.getWeight()).toBe(0)
  })

  it('должен вычислить общий вес взвешенного графа', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB, 1)
    const edgeBC = new Edge(nodeB, nodeC, 2)
    const edgeCD = new Edge(nodeC, nodeD, 3)
    const edgeAD = new Edge(nodeA, nodeD, 4)

    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeAD)

    expect(graph.getWeight()).toBe(10)
  })

  it('должен удалить ребра из графа', () => {
    const graph = new Graph()

    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeAC = new Edge(nodeA, nodeC)

    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeAC)

    expect(graph.getAllEdges().length).toBe(3)

    graph.removeEdge(edgeAB)

    expect(graph.getAllEdges().length).toBe(2)
    expect(graph.getAllEdges()[0].getKey()).toBe(edgeBC.getKey())
    expect(graph.getAllEdges()[1].getKey()).toBe(edgeAC.getKey())
  })

  it('должен выбросить исключение при удалении несуществующего узла', () => {
    function deleteNotExistingEdge() {
      const graph = new Graph()

      const nodeA = new Node('A')
      const nodeB = new Node('B')
      const nodeC = new Node('C')

      const edgeAB = new Edge(nodeA, nodeB)
      const edgeBC = new Edge(nodeB, nodeC)

      graph.addEdge(edgeAB)
      graph.removeEdge(edgeBC)
    }

    expect(deleteNotExistingEdge).toThrowError()
  })

  it('должен инвертировать граф', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeAC = new Edge(nodeA, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)

    const graph = new Graph(true)
    graph.addEdge(edgeAB).addEdge(edgeAC).addEdge(edgeCD)

    expect(graph.toString()).toBe('A,B,C,D')
    expect(graph.getAllEdges().length).toBe(3)
    expect(graph.getNeighbors(nodeA).length).toBe(2)
    expect(graph.getNeighbors(nodeA)[0].getKey()).toBe(nodeB.getKey())
    expect(graph.getNeighbors(nodeA)[1].getKey()).toBe(nodeC.getKey())
    expect(graph.getNeighbors(nodeB).length).toBe(0)
    expect(graph.getNeighbors(nodeC).length).toBe(1)
    expect(graph.getNeighbors(nodeC)[0].getKey()).toBe(nodeD.getKey())
    expect(graph.getNeighbors(nodeD).length).toBe(0)

    graph.reverse()

    expect(graph.toString()).toBe('A,B,C,D')
    expect(graph.getAllEdges().length).toBe(3)
    expect(graph.getNeighbors(nodeA).length).toBe(0)
    expect(graph.getNeighbors(nodeB).length).toBe(1)
    expect(graph.getNeighbors(nodeB)[0].getKey()).toBe(nodeA.getKey())
    expect(graph.getNeighbors(nodeC).length).toBe(1)
    expect(graph.getNeighbors(nodeC)[0].getKey()).toBe(nodeA.getKey())
    expect(graph.getNeighbors(nodeD).length).toBe(1)
    expect(graph.getNeighbors(nodeD)[0].getKey()).toBe(nodeC.getKey())
  })

  it('должен вернуть индексы узлов', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)
    const edgeBD = new Edge(nodeB, nodeD)

    const graph = new Graph()
    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeBD)

    const verticesIndices = graph.getNodesIndices()
    expect(verticesIndices).toEqual({
      A: 0,
      B: 1,
      C: 2,
      D: 3,
    })
  })

  it('должен вернуть матрицу смежности для ненаправленного графа', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB)
    const edgeBC = new Edge(nodeB, nodeC)
    const edgeCD = new Edge(nodeC, nodeD)
    const edgeBD = new Edge(nodeB, nodeD)

    const graph = new Graph()
    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeBD)

    const adjacencyMatrix = graph.getAdjacencyMatrix()
    expect(adjacencyMatrix).toEqual([
      [null, 0, null, null],
      [0, null, 0, 0],
      [null, 0, null, 0],
      [null, 0, 0, null],
    ])
  })

  it('должен вернуть матрицу смежности для направленного графа', () => {
    const nodeA = new Node('A')
    const nodeB = new Node('B')
    const nodeC = new Node('C')
    const nodeD = new Node('D')

    const edgeAB = new Edge(nodeA, nodeB, 2)
    const edgeBC = new Edge(nodeB, nodeC, 1)
    const edgeCD = new Edge(nodeC, nodeD, 5)
    const edgeBD = new Edge(nodeB, nodeD, 7)

    const graph = new Graph(true)
    graph.addEdge(edgeAB).addEdge(edgeBC).addEdge(edgeCD).addEdge(edgeBD)

    const adjacencyMatrix = graph.getAdjacencyMatrix()
    expect(adjacencyMatrix).toEqual([
      [null, 2, null, null],
      [null, null, 1, 7],
      [null, null, null, 5],
      [null, null, null, null],
    ])
  })
})