-
dem0091 authored48996b51
MatrixSearch.cs 17.08 KiB
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace AlgorithmLibrary
{
internal class MatrixSearch
{
static private int index1 = -1; //pozice radku
static private int index2 = -1; //pozice sloupce
static private int counter = 0; //uruje pozici v poli indexy
static private int[] indexy = new int[4_000_000]; //pole pro ulozeni indexu v pripade vice vyskytu
//binarni vyhledavni - pomocna funkce algoritmu binaryMatice
private static int indexPrvku(int[] A, int l, int r, int k, float div)
{
if (l > r)
return -1;
int interval = r - l;
int rozdel = (int)(interval * (1 - div));
int divIndex = l + rozdel;
if (A[divIndex] == k)
{
return divIndex;
}
else if (A[divIndex] < k)
{
return indexPrvku(A, divIndex + 1, r, k, div);
}
else
{
return indexPrvku(A, l, divIndex - 1, k, div);
}
}
static private bool neniVetsiNezK(int[] A, int x, int k)
{
// neni vetsi nez k, takze je moznym resenim
//je tam dalsi vyskyt k?
return A[x] <= k;
}
//binarni vyhledavni - pomocna funkce algoritmu binaryMatice
//v pripade kdy se prvek k vyskytuje cetne, vraci funkce nejvyssi index jednoho z vyskytujicich prvku k v poli
static private int nejvetsiPrvekNeVetsiNezK(int[] A, int x, int y, int k)
{
int l = x, r = y;
int nejlepsi = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (neniVetsiNezK(A, mid, k))
{
nejlepsi = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return nejlepsi;
}
static public Tuple<int, int> Saddleback(int[][] A, int k)
{
index1 = -1; index2 = -1;
saddleback(A, k);
return new Tuple<int, int>(index1, index2);
}
/**
* Saddleback vyhledavani v matici prvniho vyskytu NEREKURZIVNI
* @param A pole k serazeni
* @param k hledany prvek
* @return algoritmus ulozi pozici vyskytu do promene index1 a index2
*/
static private void saddleback(int[][] A, int k)
{
int i = 0;
int j = A[0].Length - 1;
while (i < A.Length && j >= 0)
{
if (A[i][j] == k)
{
index1 = i;
index2 = j;
return;
}
else if (A[i][j] > k) j--;
else i++;
}
return;
}
static public Tuple<int, int> IndexPrvku2D(int[][] A, int k, float div1, float div2)
{
index1 = -1;
index2 = -1;
indexPrvku2D(A, 0, A.Length - 1, 0, A[0].Length - 1, k, div1, div2);
return new Tuple<int, int>(index1, index2);
}
/**
* Vyhledavaní prvku v matici pomoci rozdel a panuj
* @param A 2D pole, ve kterem se hleda prvek
* @param x prvni index radku na ktery se smi sahnout
* @param y posledni index radku, na ktery se smi sahnout
* @param u prvni index sloupce na ktery se smi sahnout
* @param v posledni index sloupce, na ktery se smi sahnout
* @param k hledany prvek
* @param div1 hodnota urcujici pomer rozdeleni b1 v ramci radku
* @param div2 hodnota urcujici pomer rozdeleni b2 v ramci sloupcu
* @return pozice vyskytu se ulozi do globalni promene index1 a index2
*/
static private void indexPrvku2D(int[][] A, int x, int y, int u, int v, int k, float div1, float div2)
{
if (u >= v && x >= y)
{
if (x == y && u == v && A[x][u] == k)
{
index1 = x; index2 = u;
}
else { return; }
}
int e1 = (int)(x + (y - x) * div1);
int e2 = (int)(u + (v - u) * div2);
bool row = (x == y);
bool column = (u == v);
//podminka 1
if (k < A[e1][e2])
{
indexPrvku2D(A, x, e1, u, e2, k, div1, div2); if (!row) indexPrvku2D(A, e1 + 1, y, u, e2, k, div1, div2);
if (!column) indexPrvku2D(A, x, e1, e2 + 1, v, k, div1, div2);
return;
}
//podminka 2
if (k > A[e1][e2])
{
indexPrvku2D(A, e1 + 1, y, e2 + 1, v, k, div1, div2);
if (!row) indexPrvku2D(A, e1 + 1, y, u, e2, k, div1, div2);
if (!column) indexPrvku2D(A, x, e1, e2 + 1, v, k, div1, div2);
return;
}
//podminka 3
if (k == A[e1][e2])
{
index1 = e1;
index2 = e2;
return;
}
return;
}
static public Tuple<int, int>[] IndexyPrvku2D(int[][] A, int k, float div)
{
indexy = new int[4_000_000];
counter = 0;
indexyPrvku2D(A, 0, A.Length - 1, 0, A[0].Length - 1, k, div);
Tuple<int, int>[] result = new Tuple<int, int>[counter / 2];
for (int i = 0; i < counter; i += 2)
{
result[i / 2] = new Tuple<int, int>(indexy[i], indexy[i + 1]);
}
return result;
}
/**
* Vyhledavani vice vyskytu prvku v matici pomoci rozdel a panuj
* @param A 2D pole, ve kterem se hleda prvek
* @param x prvni index radku na ktery se smi sahnout
* @param y posledni index radku, na ktery se smi sahnout
* @param u prvni index sloupce na ktery se smi sahnout
* @param v posledni index sloupce, na ktery se smi sahnout
* @param k hledany prvek
* @param div hodnota urcujici pomer rozdeleni b v ramci radku i sloupcu
* @return pozice vyskytu se ulozi do globalni promene indexy
*/
static private void indexyPrvku2D(int[][] A, int x, int y, int u, int v, int k, float div)
{
if (u >= v && x >= y)
{
if (x == y && u == v && A[x][u] == k)
{
indexy[counter++] = x;
indexy[counter++] = u;
return;
}
else { return; }
}
int e1 = (int)(x + (y - x) * div);
int e2 = (int)(u + (v - u) * div);
bool row = (x == y);
bool column = (u == v);
//podminka 1
if (k < A[e1][e2])
{ indexyPrvku2D(A, x, e1, u, e2, k, div);
if (!column) indexyPrvku2D(A, e1 + 1, y, u, e2, k, div);
if (!row) indexyPrvku2D(A, x, e1, e2 + 1, v, k, div);
return;
}
//podminka 2
if (k > A[e1][e2])
{
indexyPrvku2D(A, e1 + 1, y, e2 + 1, v, k, div);
if (!row) indexyPrvku2D(A, e1 + 1, y, u, e2, k, div);
if (!column) indexyPrvku2D(A, x, e1, e2 + 1, v, k, div);
return;
}
//podminka 3
if (k == A[e1][e2])
{
indexy[counter++] = e1;
indexy[counter++] = e2;
A[e1][e2] = -1;
indexyPrvku2D(A, x, e1, u, e2, k, div);
if (!row) //pokud to neni radek
{
indexyPrvku2D(A, e1 + 1, y, u, e2, k, div);
}
if (!column) //pokud to neni sloupec
{
indexyPrvku2D(A, x, e1, e2 + 1, v, k, div);
}
if (!row || !column) //pokud to neni radek nebo sloupec
{
indexyPrvku2D(A, e1 + 1, y, e2 + 1, v, k, div);
}
return;
}
return;
}
static public Tuple<int, int> BinaryMatice(int[][] A, int k, float div)
{
index1 = -1;
index2 = -1;
binaryMatice(A, 0, A.Length - 1, 0, A[0].Length - 1, k, div);
return new Tuple<int, int>(index1, index2);
}
/**
* Vyhledavani prvniho vyskytu prvku v matici pomoci binarniho vyhledavani
* @param A 2D pole, ve kterem se hleda prvek
* @param x prvni index radku na ktery se smi sahnout
* @param y posledni index radku, na ktery se smi sahnout
* @param u prvni index sloupce na ktery se smi sahnout
* @param v posledni index sloupce, na ktery se smi sahnout
* @param k hledany prvek
* @param div hodnota urcujici pomer rozdeleni b radku a binarniho vyhledvani
* @return pozice vyskytu se ulozi do globalni promene indexy
*/
static private void binaryMatice(int[][] A, int x, int y, int u, int v, int k, float div)
{
if (v < u) return;
if (index1 != -1 && index2 != -1) return;
if (x == -1 || y == -1) return;
if (y < x) return;
if (u >= v && x >= y)
{
if (x == y && u == v && A[x][u] == k) {
index1 = x; index2 = u;
return;
}
else { return; }
}
if (x == y)
{
index1 = x;
index2 = indexPrvku(A[x], u, v, k, div);
return;
}
int e1 = (int)(x + (y - x) * div); //urceni radku pomoci parametru div
int e2 = nejvetsiPrvekNeVetsiNezK(A[e1], u, v, k); //binarni vyhledavani na radku
if (e2 == -1)
{
e2 = u - 1;
binaryMatice(A, x, e1 - 1, e2 + 1, v, k, div);
return;
}
if (k == A[e1][e2])
{
index1 = e1;
index2 = e2;
return;
}
binaryMatice(A, e1 + 1, y, u, e2, k, div);
binaryMatice(A, x, e1 - 1, e2 + 1, v, k, div);
return;
}
static private bool neniVetsiNezK2(int[] A, int x, int k)
{
// je mensi nez k, takze je moznym resenim
return A[x] < k;
}
//pomocna funkce algoritmu BinaryMaticeVsechny
//vrati pozici nejvetsiho prvku na radku, ktery je mensi nez k
static private int nejvetsiPrvekMensiNezK(int[] A, int x, int y, int k)
{
int l = x, r = y;
int nejlepsi = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (neniVetsiNezK2(A, mid, k))
{
nejlepsi = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
if (nejlepsi == -1)
{
nejlepsi = l - 1; // -1 je tu proto, ze se po vyjiti z funkce na nekterych mistech hlavniho algoritmu pricte 1
}
return nejlepsi;
}
static private bool neniVetsiNezK_sloupec(int[][] A, int sloupec, int x, int k, bool prvni)
{
// neni vetsi nez k, takze je moznym resenim
if (prvni) return A[x][sloupec] < k;
return A[x][sloupec] <= k;
}
//upravene binarni vyhledavani ve sloupci matice
//pomocna funkce algoritmu BinaryMaticeVsechny
//funkce najde prvni nebo posledni vyskyt podle nastaveni parametru prvni
static private int prvniPosledniSloupec(int[][] A, int sloupec, int x, int y, int k, bool prvni)
{
int l = x, r = y;
int nejlepsi = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (neniVetsiNezK_sloupec(A, sloupec, mid, k, prvni))
{
nejlepsi = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
if (prvni) return l;
return nejlepsi;
}
//binarni vyhledavani ve sloupci matice
//pomocna funkce algoritmu BinaryMaticeVsechny
private static int indexPrvkuSloupec(int[][] A, int column, int x, int y, int k, float div)
{
if (x > y)
return -1;
int interval = y - x;
int rozdel = (int)(interval * (1 - div));
int divIndex = x + rozdel;
if (A[divIndex][column] == k)
{
return divIndex;
}
else if (A[divIndex][column] < k)
{
return indexPrvkuSloupec(A, column, divIndex + 1, y, k, div);
}
else
{
return indexPrvkuSloupec(A, column, x, divIndex - 1, k, div);
}
}
//pomocna funkce algoritmu BinaryMaticeVsechny
//uklada vsechny pozice vyskytu ve vymezene sekci
static private void ulozPozicevyksytu(int[][] A, int x, int y, int L, int R, int row, int k, float div)
{
for (int i = L; i <= R; i++)
{
int zacatek = prvniPosledniSloupec(A, i, x, row, k, true);
int konec = prvniPosledniSloupec(A, i, row, y, k, false);
for (int j = zacatek; j <= konec; j++)
{
indexy[counter++] = j;
indexy[counter++] = i;
}
}
}
static public Tuple<int, int>[] BinaryMaticeVsechny(int[][] A, int k, float div)
{
indexy = new int[4_000_000];
counter = 0;
binaryMaticeVsechny(A, 0, A.Length - 1, 0, A[0].Length - 1, k, div);
Tuple<int, int>[] result = new Tuple<int, int>[counter/2];
for (int i = 0; i < counter; i += 2)
{
result[i / 2] = new Tuple<int, int>(indexy[i], indexy[i + 1]);
}
return result;
}
/**
* Vyhledavani vsech vyskytu prvku v matici pomoci binarniho vyhledavani
* @param A 2D pole, ve kterem se hleda prvek
* @param x prvni index radku na ktery se smi sahnout
* @param y posledni index radku, na ktery se smi sahnout
* @param u prvni index sloupce na ktery se smi sahnout
* @param v posledni index sloupce, na ktery se smi sahnout
* @param k hledany prvek
* @param div hodnota urcujici pomer rozdeleni b radku a binarniho vyhledvani
* @return pozice vyskytu se ulozi do globalni promene indexy
*/
static private void binaryMaticeVsechny(int[][] A, int x, int y, int u, int v, int k, float div)
{
int index_L = -1;
int index_R = -1;
if (v < u) return;
if (x == -1 || y == -1) return;
if (y < x) return;
if (u >= v && x >= y)
{
if (x == y && u == v && A[x][u] == k)
{
indexy[counter++] = x; indexy[counter++] = u; //zapsani pozice vyskytu prvku k
}
else { return; }
}
if (x == y)
{
index_R = nejvetsiPrvekNeVetsiNezK(A[x], u, v, k); //najdi nejpravejsi vyskyt prku a uloz index
if (index_R != -1)
{
if (A[x][index_R] == k)
{
index_L = nejvetsiPrvekMensiNezK(A[x], u, v, k) + 1; //pokud se prvek nasel, hledame levou hranici intervalu, na kterem lezi hledane prvky
for (int i = index_L; i <= index_R; i++)
{
indexy[counter++] = x; indexy[counter++] = i; //zapsani pozice vyskytu prvku k
}
}
}
return;
}
int e1 = (int)(x + (y - x) * div);
int e2 = nejvetsiPrvekNeVetsiNezK(A[e1], u, v, k); //to znamena ze nasel posledni vyksyt prvku - pokud je na konci je treba skontrolavat prvek a pokud je hodnta -1 prvek tam neni
int e2_hranice = e2;
if (e2 == -1)
{
e2 = u - 1;
binaryMaticeVsechny(A, x, e1 - 1, e2 + 1, v, k, div);
return;
} if (A[e1][e2] == k)
{
index_R = e2;
index_L = nejvetsiPrvekMensiNezK(A[e1], u, v, k) + 1;
ulozPozicevyksytu(A, x, y, index_L, index_R, e1, k, div); //zapsani pozice vyskytu prvku k
e2 = index_L - 1;
}
binaryMaticeVsechny(A, e1 + 1, y, u, e2, k, div);
e2 = e2_hranice;
binaryMaticeVsechny(A, x, e1 - 1, e2 + 1, v, k, div);
return;
}
}
}