Class BalancedMergeSort

java.lang.Object
AEDs3.DataBase.BalancedMergeSort
public class BalancedMergeSort extends Object
Classe responsável por realizar a ordenação externa por intercalação balanceada. Este algoritmo divide os dados em segmentos menores e utiliza uma estrutura de heap (fila de prioridade) para realizar a intercalação eficiente de grandes quantidades de dados que não cabem na memória RAM de uma vez. A ordenação é realizada usando 2N arquivos temporários e o algoritmo de intercalação balanceada.

A classe utiliza a classe TrackDB para ler e gravar os registros de faixas de música, realizando a ordenação dos dados através de múltiplos arquivos temporários.

A ordenação ocorre em duas fases: 1. Distribuição inicial dos registros em 2N arquivos temporários. 2. Intercalação dos arquivos temporários, ordenando os dados e escrevendo-os de volta no banco de dados.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private static final record 
    BalancedMergeSort.FileTrack
    Classe auxiliar que agrupa uma Track com o índice do arquivo em que está, para uso com o PriorityQueue.
    private static class 
    BalancedMergeSort.WeightedTrack
    Classe auxiliar que agrupa uma Track com um peso, para uso com o PriorityQueue.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) TrackDB
    db
    Banco de dados de faixas de música (TrackDB) a ser ordenado.
    (package private) int
    fanout
    Número de caminhos (número de arquivos será o dobro).
    (package private) TrackDB[]
    files
    Arquivos temporários onde os dados são armazenados durante a ordenação.
    (package private) int
    maxHeapNodes
    Número máximo de registros a armazenar no heap durante a intercalação.
    (package private) boolean
    mergingFromFirstGroup
    Indica se estamos intercalando segmentos do grupo A (primeiro conjunto de N arquivos) para o grupo B (segundo grupo) ou vice-versa.
    (package private) boolean
    verbose
    Indica se deve exibir em `System.err` os passos da execução durante a ordenação.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BalancedMergeSort(TrackDB db)
    Construtor que inicializa a ordenação com os parâmetros padrão.
    BalancedMergeSort(TrackDB db, int fanout, int maxHeapNodes)
    Construtor que inicializa a ordenação com parâmetros personalizados.

  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    distribute()
    Distribui os registros do banco de dados em 2N arquivos temporários.
    TrackDB
    getDb()
    Retorna o banco de dados de faixas de música.
    int
    getFanout()
    Retorna o número de caminhos (fanout) utilizado na ordenação.
    TrackDB[]
    getFiles()
    Retorna os arquivos temporários utilizados durante a ordenação.
    int
    getMaxHeapNodes()
    Retorna o número máximo de registros a serem armazenados no heap durante a intercalação.
    boolean
    isMergingFromFirstGroup()
    Indica se a intercalação está ocorrendo do primeiro grupo de arquivos.
    boolean
    isVerbose()
    Indica se a execução deve exibir passos detalhados no console.
    private TrackDB
    merge()
    Intercala os registros de um grupo de N arquivos temporários no outro grupo.
    void
    setDb(TrackDB db)
    Define o banco de dados de faixas de música.
    void
    setFanout(int fanout)
    Define o número de caminhos (fanout) utilizado na ordenação.
    void
    setFiles(TrackDB[] files)
    Define os arquivos temporários utilizados durante a ordenação.
    void
    setMaxHeapNodes(int maxHeapNodes)
    Define o número máximo de registros a serem armazenados no heap durante a intercalação.
    void
    setMergingFromFirstGroup(boolean grupo)
    Define se a intercalação deve ocorrer do primeiro grupo de arquivos.
    void
    setVerbose(boolean verbose)
    Define se a execução deve exibir passos detalhados no console.
    void
    sort()
    Inicia o processo de ordenação do banco de dados utilizando o algoritmo de intercalação balanceada.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • db

      TrackDB db
      Banco de dados de faixas de música (TrackDB) a ser ordenado.

    • files

      TrackDB[] files
      Arquivos temporários onde os dados são armazenados durante a ordenação.

    • fanout

      int fanout
      Número de caminhos (número de arquivos será o dobro).

    • maxHeapNodes

      int maxHeapNodes
      Número máximo de registros a armazenar no heap durante a intercalação.

    • mergingFromFirstGroup

      boolean mergingFromFirstGroup
      Indica se estamos intercalando segmentos do grupo A (primeiro conjunto de N arquivos) para o grupo B (segundo grupo) ou vice-versa.

    • verbose

      boolean verbose
      Indica se deve exibir em `System.err` os passos da execução durante a ordenação.

  • Constructor Details

    • BalancedMergeSort

      public BalancedMergeSort(TrackDB db)
      Construtor que inicializa a ordenação com os parâmetros padrão.
      Parameters:
      db - O banco de dados a ser ordenado.

    • BalancedMergeSort

      public BalancedMergeSort(TrackDB db, int fanout, int maxHeapNodes)
      Construtor que inicializa a ordenação com parâmetros personalizados.
      Parameters:
      db - O banco de dados a ser ordenado.
      fanout - O número de caminhos N, onde o número de arquivos temporários será 2N.
      maxHeapNodes - O número máximo de registros a armazenar no heap.

  • Method Details

    • sort

      public void sort() throws IOException
      Inicia o processo de ordenação do banco de dados utilizando o algoritmo de intercalação balanceada. O processo é feito em duas fases: distribuição dos registros e intercalação dos segmentos.

      Após a ordenação, o banco de dados original é substituído pelos dados ordenados, e quaisquer índices serão reconstruídos.

      Throws:
      IOException - Se ocorrer algum erro de entrada/saída durante a execução.

    • distribute

      private void distribute() throws IOException
      Distribui os registros do banco de dados em 2N arquivos temporários. Utiliza um heap (PriorityQueue) para armazenar os elementos e realizar a distribuição de forma balanceada.
      Throws:
      IOException - Se ocorrer um erro de entrada/saída durante a distribuição.

    • merge

      private TrackDB merge() throws IOException
      Intercala os registros de um grupo de N arquivos temporários no outro grupo. Este método realiza a intercalação balanceada, utilizando um heap para encontrar o menor registro entre os arquivos e escrevê-lo no arquivo de destino.
      Returns:
      O banco de dados com os dados ordenados, ou null se a ordenação ainda não estiver completa.
      Throws:
      IOException - Se ocorrer um erro de entrada/saída durante a intercalação.

    • getDb

      public TrackDB getDb()
      Retorna o banco de dados de faixas de música.
      Returns:
      O banco de dados de faixas de música.

    • setDb

      public void setDb(TrackDB db)
      Define o banco de dados de faixas de música.
      Parameters:
      db - O banco de dados de faixas de música a ser definido.

    • getFiles

      public TrackDB[] getFiles()
      Retorna os arquivos temporários utilizados durante a ordenação.
      Returns:
      Um array de arquivos temporários.

    • setFiles

      public void setFiles(TrackDB[] files)
      Define os arquivos temporários utilizados durante a ordenação.
      Parameters:
      files - Um array de arquivos temporários a ser definido.

    • getFanout

      public int getFanout()
      Retorna o número de caminhos (fanout) utilizado na ordenação.
      Returns:
      O número de caminhos (fanout).

    • setFanout

      public void setFanout(int fanout)
      Define o número de caminhos (fanout) utilizado na ordenação.
      Parameters:
      fanout - O número de caminhos (fanout) a ser definido.

    • getMaxHeapNodes

      public int getMaxHeapNodes()
      Retorna o número máximo de registros a serem armazenados no heap durante a intercalação.
      Returns:
      O número máximo de registros no heap.

    • setMaxHeapNodes

      public void setMaxHeapNodes(int maxHeapNodes)
      Define o número máximo de registros a serem armazenados no heap durante a intercalação.
      Parameters:
      maxHeapNodes - O número máximo de registros no heap a ser definido.

    • isMergingFromFirstGroup

      public boolean isMergingFromFirstGroup()
      Indica se a intercalação está ocorrendo do primeiro grupo de arquivos.
      Returns:
      true se a intercalação está ocorrendo do primeiro grupo, caso contrário false.

    • setMergingFromFirstGroup

      public void setMergingFromFirstGroup(boolean grupo)
      Define se a intercalação deve ocorrer do primeiro grupo de arquivos.
      Parameters:
      grupo - true para intercalar do primeiro grupo, caso contrário false.

    • isVerbose

      public boolean isVerbose()
      Indica se a execução deve exibir passos detalhados no console.
      Returns:
      true se a execução deve ser detalhada, caso contrário false.

    • setVerbose

      public void setVerbose(boolean verbose)
      Define se a execução deve exibir passos detalhados no console.
      Parameters:
      verbose - true para exibir passos detalhados, caso contrário false.