# Ćwiczenia 3, grupa śr. 16-18, 9 listopada 2022

###### tags: `PRW22` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | X | | | | | | | |
Marcin Dąbrowski | | | | | | | | |
Jakub Gałecki | | | | | | | | |
Kamila Goszcz | X | X | | X | | | X | |
Wiktor Hamberger | X | X | X | X | | | | |
Jan Jankowicz | X | X | X | X | X | X | | |
Mikołaj Jaszcza | X | X | X | X | | | | |
Zuzanna Kania | X | X | X |==X==| | | X | |
Wiktoria Kuna | | | | | | | | |
Patryk Mazur | X | | | | | | | |
Hubert Obrzut | X | X | X | X |==X==| X | X | |
Magdalena Rzepka | X | | | | | | X | |
Joanna Stachowicz | | | | | | | | |
Rafał Starypan |X | X | ==X== | X | | | X | |
Maria Szlasa | X | X | X | X | | | X | |
Daniel Wiczołek | | | | | | | | |
Adam Jarząbek | X |==X==| X |X | | | | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Kamila Goszcz
:::

class MergeSort implements Runnable {
    protected int help_arr[];
    protected int arr[];
    protected int l, r;
    final int SMALL = 20;

    MergeSort(int arr[], int help[], int l, int r) {
        this.arr = arr;
        this.help_arr = help;
        this.l = l;
        this.r = r;
    }

    private void merge(int left, int middle, int right) {
        int left_index = left;
        int right_index = middle + 1;

        for (int i = left; i <= right; i++) {
            this.help_arr[i] = arr[i];
        }
        int index = left;
        while (left_index < middle + 1 && right_index < right + 1) {
            if (help_arr[left_index] <= help_arr[right_index]) {
                arr[index] = help_arr[left_index];
                left_index += 1;
            } else {
                arr[index] = help_arr[right_index];
                right_index += 1;
            }
            index += 1;
        }
        while (left_index < middle + 1) {
            arr[index] = help_arr[left_index];
            index += 1;
            left_index += 1;
        }
        while (right_index < right + 1) {
            arr[index] = help_arr[right_index];
            index += 1;
            right_index += 1;
        }
    }

    public void sort(int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            sort(left, middle);
            sort(middle + 1, right);
            merge(left, middle, right);
        }
    }

    @Override
    public void run() {
        if (this.l < this.r) {
            int m = (this.l + this.r) / 2;
            MergeSort left = new MergeSort(arr, help_arr, this.l, m);
            MergeSort right = new MergeSort(arr, help_arr, m + 1, this.r);
            Thread t1 = new Thread(left);
            Thread t2 = new Thread(right);
            t1.start();
            t2.start();
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            this.merge(this.l, m, this.r);
        }
    }
}

## Zadanie 2
:::success
Autor: Adam Jarząbek
:::

class MergeSort implements Runnable {

	public static final int MIN_SIZE_TO_DO_MULTITHREADING = 4;
	protected int array[];
	protected int arrayCopy[];
	protected int startIndex, endIndex;

	MergeSort(int array[], int arrayCopy[], int startIndex, int endIndex) {

		this.array = array;
		this.startIndex = startIndex;
		this.endIndex = endIndex;
		this.arrayCopy = arrayCopy;
	}

	private void merge(int leftIndex, int middleIndex, int rightIndex) {

		int leftArrayPivot = leftIndex;
		int rightArrayPivot = middleIndex + 1;
		int resultArrayPivot = leftIndex;

		while (leftArrayPivot <= middleIndex && rightArrayPivot <= rightIndex) {
			if (arrayCopy[leftArrayPivot] <= arrayCopy[rightArrayPivot]) {
				array[resultArrayPivot] = arrayCopy[leftArrayPivot];
				leftArrayPivot += 1;
			}
			else {
				array[resultArrayPivot] = arrayCopy[rightArrayPivot];
				rightArrayPivot += 1;
			}
			resultArrayPivot += 1;
		}
		while (leftArrayPivot <= middleIndex) {
			array[resultArrayPivot] = arrayCopy[leftArrayPivot];
			resultArrayPivot += 1;
			leftArrayPivot += 1;
		}
		while (rightArrayPivot <= rightIndex) {
			array[resultArrayPivot] = arrayCopy[rightArrayPivot];
			resultArrayPivot += 1;
			rightArrayPivot += 1;
		}
		updateArrayCopy(startIndex, endIndex);
	}

	public void updateArrayCopy(int startIndex, int endIndex) {

		for (int i = startIndex; i <= endIndex; i++) {
			arrayCopy[i] = array[i];
		}
	}

	public void sort(int startIndex, int endIndex) {

		if (startIndex < endIndex) {
			int middleIndex = (startIndex + endIndex) / 2;

			sort(startIndex, middleIndex);
			sort(middleIndex + 1, endIndex);

			merge(startIndex, middleIndex, endIndex);
		}
	}

	@Override
	public void run() {

		System.out.println("Starting thread...");

		if (this.startIndex < this.endIndex) {

			if (endIndex - startIndex < MIN_SIZE_TO_DO_MULTITHREADING) {
				sort(startIndex, endIndex);
			}

			else {
				int middleIndex = (startIndex + endIndex) / 2;

				MergeSort leftMerge = new MergeSort(array, arrayCopy, startIndex, middleIndex);
				MergeSort rightMerge = new MergeSort(array, arrayCopy, middleIndex + 1, endIndex);

				Thread leftHalfThread = new Thread(leftMerge);

				leftHalfThread.start();

				rightMerge.sort(middleIndex + 1, endIndex);

				try {
					leftHalfThread.join();
				}
				catch (InterruptedException e) {
					e.printStackTrace();
				}

				merge(startIndex, middleIndex, endIndex);
			}
		}
	}
}

public class RookieMergeSort {

	public static void main(String[] args) {

		int arr[] = { 8, 5, 6, 7, 4, 3, 1, 2};

		MergeSort mergeSort = new MergeSort(arr, new int[8], 0, 7);

		mergeSort.updateArrayCopy(0, 7);

		Thread thread = new Thread(mergeSort);

		thread.start();
		try {
			thread.join();
		}
		catch (InterruptedException e) {
			e.printStackTrace();
		}

		for (int element : arr)
			System.out.printf("%d ", element);
	}
}

## Zadanie 3
:::success
Autor: Rafał Starypan


package zad3;

class ThreadCounter {
    private int currentThreadCount;
    private int maxThreadCount;

    public ThreadCounter(int maxThreadCount) {
        this.currentThreadCount = 0;
        this.maxThreadCount = maxThreadCount;
    }

    public synchronized int getCurrentThreadCount() {
        return currentThreadCount;
    }

    public synchronized int incrementAndGetCurrentThreadCount() {
        if (currentThreadCount < maxThreadCount) {
            int temp  = currentThreadCount;
            currentThreadCount = temp + 1;
            return temp;
        }
        return currentThreadCount;
    }
}

package zad3;

class MergeSort implements Runnable {
    protected int arr[];
    protected int l, r;

    protected ThreadCounter counter;

    private int sharedArr[];

    MergeSort(int arr[], int l, int r, ThreadCounter counter) {
        this.arr = arr;
        this.l = l;
        this.r = r;

        this.sharedArr = new int [arr.length];

        this.counter = counter;
    }

    private void merge(int l, int m, int r) {
        for (int i = l; i <= r; i++) {
            sharedArr[i] = arr[i];
        }

        int i = l;
        int j = m + 1;
        int sortedPos = l;

        while (i <= m && j <= r) {
            if (sharedArr[i] <= sharedArr[j]) {
                arr[sortedPos] = sharedArr[i];
                i++;
            } else {
                arr[sortedPos] = sharedArr[j];
                j++;
            }
            sortedPos++;
        }

        while (i <= m) {
            arr[sortedPos] = sharedArr[i];
            sortedPos++;
            i++;
        }

        while (j <= r) {
            arr[sortedPos] = sharedArr[j];
            sortedPos++;
            j++;
        }
    }

    private void sort(int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(l, m);
            sort(m + 1, r);
            merge(l, m, r);
        }
    }

    private void sortWithThreading() {
        int m = (l + r) / 2;

        MergeSort L = new MergeSort(arr, l, m, counter);
        MergeSort R = new MergeSort(arr, m + 1, r, counter);

        Thread t1 = new Thread(L);
        Thread t2 = new Thread(R);
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        this.merge(l, m, r);
    }

    @Override
    public void run() {
        System.out.println(Thread.currentThread().getName());

        if (l < r) {
            int m = (l + r) / 2;
            MergeSort left = new MergeSort(arr, l, m, counter);
            MergeSort right = new MergeSort(arr, m + 1, r, counter);

            Thread t1 = null;
            Thread t2 = null;

            try {
                if (counter.incrementAndGetCurrentThreadCount() < RookieMergeSort.MAX_THREAD_COUNT - 1) {
                    t1 = new Thread(left);
                    t1.start();
                } else {
                    sort(l, m);
                }

                if (counter.incrementAndGetCurrentThreadCount() < RookieMergeSort.MAX_THREAD_COUNT - 1) {
                    t2 = new Thread(right);
                    t2.start();
                } else {
                    sort(m + 1, r);
                }

                if (t1 != null) {
                    t1.join();
                }
                if (t2 != null) {
                    t2.join();
                }

            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            this.merge(l, m, r);
        }
    }
}

package zad3;

public class RookieMergeSort {
    public static final int MAX_THREAD_COUNT = 4;

    public static void main(String[] args) {
        int arr[] = {5, 10, 6, 7, 8, 9, 11, 4, 3, 2};

        ThreadCounter counter = new ThreadCounter(MAX_THREAD_COUNT);
        MergeSort w = new MergeSort(arr, 0, arr.length - 1, counter);

        Thread t = new Thread(w);

        t.start();
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        for (int i = 0; i < arr.length; i++)
            System.out.printf("%d ", arr[i]);

        System.out.println(counter.getCurrentThreadCount());

    }
}

:::

## Zadanie 4
:::success
Autor Zuzanna Kania


class LongestSubseq implements Runnable {
    protected int arr[];
    protected int left, right, longestLeftIdx, longestRightIdx, leftEndIdx, rightBeginIdx;

    LongestSubseq(int arr[], int left, int right) {
        this.arr = arr;
        this.left = left;
        this.right = right;
        this.longestLeftIdx = right;
        this.longestRightIdx = left;
        this.leftEndIdx = left;
        this.rightBeginIdx = right;
    }

    private void merge(int left, int mid, int right, LongestSubseq leftPart, LongestSubseq rightPart) {
        // jeśli koniec lewej połowy == początek prawej połowy
        if (this.arr[mid] == this.arr[mid + 1]) {
            this.longestLeftIdx = leftPart.rightBeginIdx;
            this.longestRightIdx = rightPart.leftEndIdx;
        }
        // jeśli w lewej połowie mamy dłuższy ciąg
        if (leftPart.longestRightIdx - leftPart.longestLeftIdx + 1 > this.longestRightIdx
                - this.longestLeftIdx + 1) {
            this.longestLeftIdx = leftPart.longestLeftIdx;
            this.longestRightIdx = leftPart.longestRightIdx;
        }
        // jeśli w prawej połowie mamy dłuższy ciąg
        if (rightPart.longestRightIdx - rightPart.longestLeftIdx + 1 > this.longestRightIdx
                - this.longestLeftIdx + 1) {
            this.longestLeftIdx = rightPart.longestLeftIdx;
            this.longestRightIdx = rightPart.longestRightIdx;
        }
        // aktualizuj koniec lewej części
        if (leftPart.leftEndIdx == mid && this.arr[mid] == this.arr[rightPart.leftEndIdx]) {
            this.leftEndIdx = rightPart.leftEndIdx;
        } else {
            this.leftEndIdx = leftPart.leftEndIdx;
        }
        // aktualizuj początek prawej części
        if (rightPart.rightBeginIdx == mid + 1 && this.arr[mid + 1] == this.arr[leftPart.rightBeginIdx]) {
            this.rightBeginIdx = leftPart.rightBeginIdx;
        } else {
            this.rightBeginIdx = rightPart.rightBeginIdx;
        }
    }

    public int[] getResult() {
        int resArr[] = new int[this.longestRightIdx - this.longestLeftIdx + 1];
        int j = 0;
        for (int i = this.longestLeftIdx; i <= this.longestRightIdx; i++) {
            resArr[j] = this.arr[i];
            j++;
        }
        return resArr;
    }

    @Override
    public void run() {
        if (this.left < this.right) {
            int m = (this.left + this.right) / 2;
            LongestSubseq leftSub = new LongestSubseq(arr, this.left, m);
            LongestSubseq rightSub = new LongestSubseq(arr, m + 1, this.right);
            Thread t1 = new Thread(leftSub);
            Thread t2 = new Thread(rightSub);
            t1.start();
            t2.start();
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            this.merge(this.left, m, this.right, leftSub, rightSub);
        }
    }
}

public class zadanie4 {
    public static void main(String[] args) {
        int arr[] = { 1, 2, 1, 2, 1, 2, 1, 2, 3, 3, 3 };
        LongestSubseq w = new LongestSubseq(arr, 0, arr.length - 1);

        Thread t = new Thread(w);

        t.start();
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        int res[] = w.getResult();

        for (int i = 0; i < res.length; i++)
            System.out.printf("%d ", res[i]);

    }
}

:::

## Zadanie 5
:::success
Autor: Hubert Obrzut
:::

class TaskPool
{
   ConcurrentLinkedQueue<Task> queue;
   int tasksLeft;

   TaskPool()
   {
      this.tasksLeft = 0;
      queue = new ConcurrentLinkedQueue<Task>();
   }

   synchronized void updateTasksLeft(int delta)
   {
      tasksLeft += delta;
   }
}

abstract class Task
{
   abstract boolean isReady();
   abstract void execute();

   void merge(int[] arr, int[] buf, int l, int m, int r)
   {
      for (int i = l; i <= r; ++i)
         buf[i] = arr[i];

      int i = l, j = m+1, k = l;
      while (i <= m && j <= r)
         arr[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
      while (i <= m) arr[k++] = buf[i++];
      while (j <= r) arr[k++] = buf[j++];
   }
}

class SortTask extends Task
{
   int l, r;
   int[] arr, buf;
   MergeTask parent;
   TaskPool pool;
   static final int SEQUENTIAL_THRESHOLD = 50;

   SortTask(int l, int r, int[] arr, int[] buf, TaskPool pool, MergeTask parent)
   {
      this.l = l;
      this.r = r;
      this.arr = arr;
      this.buf = buf;
      this.pool = pool;
      this.parent = parent;
   }

   void execute()
   {
      if (r-l+1 <= SEQUENTIAL_THRESHOLD)
      {
         sort_sequential(l, r);
         if (parent != null)
            parent.childCompleted();
      }
      else
      {
         int m = (l+r) / 2;
         MergeTask mergeTask = new MergeTask(l, m, r, arr, buf, pool, parent);
         pool.queue.offer(new SortTask(l, m, arr, buf, pool, mergeTask));
         pool.queue.offer(new SortTask(m+1, r, arr, buf, pool, mergeTask));
         pool.queue.offer(mergeTask);
         pool.updateTasksLeft(3);
      }
      pool.updateTasksLeft(-1);
   }

   void sort_sequential(int l, int r)
   {
      if (l < r)
      {
         int m = (l+r) / 2;
         sort_sequential(l, m);
         sort_sequential(m+1, r);
         merge(arr, buf, l, m, r);
      }
   }
   
    boolean isReady() { return true; }
}

class MergeTask extends Task
{
   int l, m, r;
   int childCompleted;
   int[] arr, buf;
   TaskPool pool;
   MergeTask parent;

   MergeTask(int l, int m, int r, int arr[], int buf[], TaskPool pool, MergeTask parent)
   {
      this.l = l;
      this.m = m;
      this.r = r;
      this.childCompleted = 0;
      this.arr = arr;
      this.buf = buf;
      this.pool = pool;
      this.parent = parent;
   }

   void execute()
   {
      merge(arr, buf, l, m, r);
      if (parent != null)
         parent.childCompleted();
      pool.updateTasksLeft(-1);
   }
   
   boolean isReady() { return childCompleted == 2; }
   synchronized void childCompleted() { ++childCompleted; }
}

class MergeSort implements Runnable
{
   int[] arr, buf;
   TaskPool pool;

   MergeSort(int[] arr, int[] buf, TaskPool pool)
   {
      this.arr = arr;
      this.buf = buf;
      this.pool = pool;
   }

   @Override
   public void run()
   {
      while (pool.tasksLeft > 0)
      {
         Task task = pool.queue.poll();
         if (task != null)
         {
            if (task.isReady())
               task.execute();
            else
               pool.queue.offer(task);
         }
      }
   }
}

public class PoolOfThreads
{
   static final int NUM_THREADS = 4;

   public static void main(String[] args)
   {
      int n = 10000;
      int[] arr = new int[n];
      int[] buf = new int[n];
      Random random = new Random();
      for (int i = 0; i < n; ++i)
         arr[i] = random.nextInt(n);

      TaskPool pool = new TaskPool();
      Task initialTask = new SortTask(0, n-1, arr, buf, pool, null);
      pool.queue.offer(initialTask);
      pool.tasksLeft = 1;

      Thread[] threads = new Thread[NUM_THREADS];
      for (int i = 0; i < NUM_THREADS; ++i)
      {
         MergeSort w = new MergeSort(arr, buf, pool);
         threads[i] = new Thread(w);
         threads[i].start();
      }

      try {
         for (int i = 0; i < NUM_THREADS; ++i)
            threads[i].join();
      } catch (InterruptedException e) {
         e.printStackTrace();
      }

      for (int i = 0; i < n-1; ++i)
         assert arr[i] <= arr[i+1];

      // for (int i = 0; i < n; ++i)
         // System.out.printf("%d ", arr[i]);
   }
}

## Zadanie 6
:::success
Autor: Jan Jankowicz
:::


Zakończenie wątku polega na skonsumowaniu przez niego eventu o specjalnym typie - TERMINATE. Jeśli wątek pobierze takie zadanie z kolejki, to przed zakończeniem swojego działania wrzuci na kolejkę taki sam event, aby poinformować następny czekający wątek o zakończeniu sortowania. Pierwsze wrzucenie zadania kończącego na kolejkę dzieje się w momencie skończenia zadania scalania całości tablicy.

Empiryczne porównanie średnich czasów działania merge sorta zaimplementowanego z użyciem LinkedBlockingQueue i z użyciem ConcurrentLinkedQueue wskazuje na większą wydajność (przynajmniej w tym zastosowaniu) tej pierwszej kolejki. Z doświadczeń wynika, że użycie LinkedBlockingQueue zwiększa szybkość działania programu około dwukrotnie.

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.LinkedBlockingQueue;

public class RookieMergeSortBlockingQueue {

    public static void main(String[] args) {
        sortAndPrintOut(RookieMergeSortUtils.generateArray());

        long timeSum = 0;
        for (int i = 0; i < 100; i++) {
            timeSum += sortAndPrintOut(RookieMergeSortUtils.generateRandomArray(2500));
        }

        System.out.println("Average time: " + timeSum/100);
    }

    private static long sortAndPrintOut(int[] arrayToSort) {
        long startTime = System.currentTimeMillis();

        int size = arrayToSort.length;

        BlockingQueue<MergeSortTask> taskQueue = new LinkedBlockingQueue<>();
        Set<ArrayRange> sortedArrayRanges = ConcurrentHashMap.newKeySet();

        taskQueue.offer(new MergeSortTask(MergeSortTask.MergeSortTaskType.SORT, new ArrayRange(0, size - 1)));

        List<Thread> workers = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            workers.add(new Thread(new MergeSortBlockingQueueWorker(arrayToSort, taskQueue, sortedArrayRanges)));
        }

        workers.forEach(Thread::start);

        try {
            for (Thread worker : workers) {
                worker.join();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        for (int i = 0; i < size; i++)
            System.out.printf("%d ", arrayToSort[i]);
        System.out.print("\n");

        long endTime = System.currentTimeMillis();
        System.out.printf("Sort time: %d\n", endTime - startTime);

        return endTime - startTime;
    }

}

class MergeSortBlockingQueueWorker implements Runnable {
    protected int sortedArray[];
    protected final BlockingQueue<MergeSortTask> taskQueue;
    protected final Set<ArrayRange> sortedArrayRanges;

    protected MergeSortBlockingQueueWorker(int sortedArray[], BlockingQueue<MergeSortTask> taskQueue, Set<ArrayRange> sortedArrayRanges) {
        this.sortedArray = sortedArray;
        this.taskQueue = taskQueue;
        this.sortedArrayRanges = sortedArrayRanges;
    }

    private void merge(int leftSortingBound, int splitIndex, int rightSortingBound) {
        int[] leftArray = getSubarray(leftSortingBound, splitIndex);
        int[] rightArray = getSubarray(splitIndex + 1, rightSortingBound);

        mergeSortedArrays(leftArray, rightArray, leftSortingBound);
    }

    private int[] getSubarray(int leftSortingBound, int rightSortingBound) {
        int size = rightSortingBound - leftSortingBound + 1;
        int[] subarray = new int[size];
        copyArray(sortedArray, leftSortingBound, subarray, 0, size);
        return subarray;
    }

    private static void copyArray(int sourceArray[], int sourceArrayFirstElementIndex, int targetArray[], int targetArrayFirstElementIndex, int size) {
        for (int i = 0; i < size; i++) {
            targetArray[targetArrayFirstElementIndex + i] = sourceArray[sourceArrayFirstElementIndex + i];
        }
    }

    private void mergeSortedArrays(int[] leftArray, int[] rightArray, int leftSortingBound) {
        int leftArraySize = leftArray.length;
        int rightArraySize = rightArray.length;

        int leftArrayCurrentMergingIndex = 0, rightArrayCurrentMergingIndex = 0;
        int resultArrayCurrentMergingIndex = leftSortingBound;
        while (leftArrayCurrentMergingIndex < leftArraySize && rightArrayCurrentMergingIndex < rightArraySize) {
            if (leftArray[leftArrayCurrentMergingIndex] <= rightArray[rightArrayCurrentMergingIndex]) {
                sortedArray[resultArrayCurrentMergingIndex] = leftArray[leftArrayCurrentMergingIndex];
                leftArrayCurrentMergingIndex += 1;
            } else {
                sortedArray[resultArrayCurrentMergingIndex] = rightArray[rightArrayCurrentMergingIndex];
                rightArrayCurrentMergingIndex += 1;
            }
            resultArrayCurrentMergingIndex += 1;
        }
        while (leftArrayCurrentMergingIndex < leftArraySize) {
            sortedArray[resultArrayCurrentMergingIndex] = leftArray[leftArrayCurrentMergingIndex];
            resultArrayCurrentMergingIndex += 1;
            leftArrayCurrentMergingIndex += 1;
        }
        while (rightArrayCurrentMergingIndex < rightArraySize) {
            sortedArray[resultArrayCurrentMergingIndex] = rightArray[rightArrayCurrentMergingIndex];
            resultArrayCurrentMergingIndex += 1;
            rightArrayCurrentMergingIndex += 1;
        }
    }

    @Override
    public void run() {
        MergeSortTask task;
        while (true) {
            try {
                task = taskQueue.take();
                if (MergeSortTask.MergeSortTaskType.TERMINATE.equals(task.type)) {
                    taskQueue.offer(MergeSortTask.termination());
                    break;
                } else {
                    handleTask(task);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private void handleTask(MergeSortTask task) {
        switch (task.type) {
            case SORT:
                if (task.arrayRange.leftBound < task.arrayRange.rightBound) {
                    taskQueue.offer(new MergeSortTask(MergeSortTask.MergeSortTaskType.SORT, task.arrayRange.getLeftHalf()));
                    taskQueue.offer(new MergeSortTask(MergeSortTask.MergeSortTaskType.SORT, task.arrayRange.getRightHalf()));
                    taskQueue.offer(new MergeSortTask(MergeSortTask.MergeSortTaskType.MERGE, task.arrayRange));
                } else {
                    sortedArrayRanges.add(task.arrayRange);
                }
                break;
            case MERGE:
                if (sortedArrayRanges.contains(task.arrayRange.getLeftHalf()) && sortedArrayRanges.contains(task.arrayRange.getRightHalf())) {
                    merge(task.arrayRange.leftBound, ArrayRange.getMedianIndex(task.arrayRange), task.arrayRange.rightBound);
                    sortedArrayRanges.add(task.arrayRange);
                    if (task.arrayRange.leftBound == 0 && task.arrayRange.rightBound == sortedArray.length - 1) {
                        taskQueue.offer(MergeSortTask.termination());
                    }
                } else {
                    taskQueue.offer(task);
                }
                break;
            case TERMINATE:
                taskQueue.offer(MergeSortTask.termination());
                break;
        }
    }

}

class MergeSortTask {

    final MergeSortTaskType type;
    final ArrayRange arrayRange;

    MergeSortTask(MergeSortTaskType type, ArrayRange arrayRange) {
        this.type = type;
        this.arrayRange = arrayRange;
    }

    public static MergeSortTask termination() {
        return new  MergeSortTask(MergeSortTaskType.TERMINATE, null);
    }

    enum MergeSortTaskType {
        SORT, MERGE, TERMINATE
    }

    @Override
    public String toString() {
        if (MergeSortTaskType.TERMINATE.equals(type)) {
            return "Task - TERMINATE";
        } else {
            return String.format("Task - %s array in range %s", type, this.arrayRange);
        }

    }

}

class ArrayRange {
    final int leftBound;
    final int rightBound;

    ArrayRange(int leftBound, int rightBound) {
        this.leftBound = leftBound;
        this.rightBound = rightBound;
    }

    public ArrayRange getLeftHalf() {
        int medianIndex = getMedianIndex(this);
        return new ArrayRange(leftBound, medianIndex);
    }

    public ArrayRange getRightHalf() {
        int medianIndex = getMedianIndex(this);
        return new ArrayRange(medianIndex + 1, rightBound);
    }

    public static int getMedianIndex(ArrayRange arrayRange) {
        return (arrayRange.leftBound + arrayRange.rightBound) / 2;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        ArrayRange that = (ArrayRange) o;
        return leftBound == that.leftBound &&
                rightBound == that.rightBound;
    }

    @Override
    public int hashCode() {
        return Objects.hash(leftBound, rightBound);
    }

    @Override
    public String toString() {
        return String.format("[%d, %d]", this.leftBound, this.rightBound);
    }

}

## Zadanie 7
:::success
Autor: Maria Szlasa
:::

### Niezakleszczenie
Zakleszczenie może zajść, jeśli wszystkie wątki zostaną zatrzymane w którejś pętli.

W pętki do-while w for spradzamy, czy jakiś wątek o numerze mniejszym ma podniesioną flagę. Jeśli ma to my opuszczamy swoją flagę i czekamy. Wtedy zawsze do dalszej części algorytmu przejdzie wątek o najniższym numerze, który chce wywołać lock.

W pętli for sprawdzamy, czy jakieś wątki o większym numerze, które przeszły przez do-while chcą wejść do CS. Jeśli tak to czekamy aż one wykonają sekcje.
Dlaczego tak jest?
Jeśli nie ma żadnego wątku w do-while, to wyjdzie z tej pętli. Jeśli w do-while są jakieś wątki o większym numerze to opuszczą one swoją flagę czekając na mniejsze.

## Zadanie 8
:::success
Autor: Magdalena Rzepka
:::

Załóżmy, że mamy wątki A, B i C oraz dwie lokacje L~A~ i L~B~.
Każdy wątek przed wejściem do sekcji krytycznej musi zapisać dane przynajmniej w jednej współdzielonej lokacji.
- gdyby wątek mógł wejść bez zapisania czegokolwiek, to inny wątek nie mógłby sprawdzić, że ktoś już jest w sekcji krytycznej i sam mógłby tam wejść - stan lokacji wskazywałby, że nikogo tam nie ma -> stan niespójności

Będziemy rozważać sytuację, w której wątek B 3 razy będzie chciał wejść do sekcji krytyczej.
Lokalizacje L~A~ i L~B~ są początkowo puste (wskazują, że nikogo nie ma i nikt nie chce wejść do sekcji krytycznej).
Skoro przed wejściem do sekcji krytycznej wątek B musi zapisać dane przynajmniej w jednej lokalizacji, to musi przynajmniej dwa razy zapisać w pewnej lokalizacji jako pierwszej (nazwijmy ją L~B~).

**Uruchamiamy wątek B i zatrzymujemy go w momencie, w którym chce zapisać dane do L~B~ jako pierwszej lokacji po raz pierwszy.**
- lokalizacje L~A~ i L~B~ są puste, bo wątek B wychodząc z sekcji krytycznej robi jakiegoś rodzaju unlock() i czyści lokalizacje, których używa, a te nie używane nie są przez nic nadpisywane.

Wątek A musi zapisać dane w lokalizacji L~A~ (może również zapisać w L~B~).
- gdyby wątek A zapisał dane tylko w lokalizacji L~B~ i wszedł do sekcji krytycznej to wątek B po uruchomieniu nadpisałby dane w L~B~ i również wszedł do sekcji krytycznej, bo obecność A zostałaby zapomniana.

**Uruchamiamy wątek A i zatrzymujemy go, przed zapisaniem danych w lokalizacji L~A~.**
- lokaliacja L~A~ jest pusta, ale lokalizacja L~B~ może zawierać jakieś dane.

**Uruchamiamy wątek B, który zapisuje dane do L~B~ (może też do L~A~).
Wątek B wychodząc z sekcji krytycznej robi unlock() i czyści L~B~ (jeżeli nadpisał też L~A~ to czyści L~A~).**
- lokacje L~A~ i L~B~ są puste.

**Zatrzymujemy wątek B, kiedy chce zapisać do L~B~ jako pierwszej lokacji po raz drugi.**
- lokacje L~A~ i L~B~ są puste, bo gdyby wątek B wchodził do sekcji krytycznej to by sprzątał za sobą a nic innego co nadpisuje nie byłoby uruchomione.

**Uruchamiamy wątek C.
Wątek C zapisuje dane w przynajmniej jednej lokacji, wchodzi do sekcji krytycznej i zostaje zatrzymany.**

**Uruchamiamy wątek A i B.
Wątek A nadpisuje lokacje L~A~ a wątek B lokacje L~B~.**

W tym momencie nie został nam ślad do wątku C i żaden z wątków nie wie, że C znajduje się w sekcji krytycznej.
Któryś z wątków w końcu będzie mógł wejść do sekcji krytycznej (bo rozważamy algorytm nie zakleszczający się) i w sekcji krytycznej będą 2 wątki.