package hjelpeklasser;
import java.util.*;
public class Tabell
{
private Tabell() {}
public static void fratilKontroll(int tablengde, int fra, int til)
{
if (fra < 0)
throw new ArrayIndexOutOfBoundsException
("fra(" + fra + ") er negativ!");
if (til > tablengde)
throw new ArrayIndexOutOfBoundsException
("til(" + til + ") > tablengde(" + tablengde + ")");
if (fra > til)
throw new IllegalArgumentException
("fra(" + fra + ") > til(" + til + ") - illegalt intervall!");
}
public static void bytt(int[] a, int i, int j)
{
int temp = a[i]; a[i] = a[j]; a[j] = temp;
}
public static void skriv(int... a)
{
for (int k : a) System.out.print(k + " ");
}
public static void skrivln(int... a)
{
skriv(a);
System.out.println();
}
public static void skriv(Object... a)
{
for (Object o : a) System.out.print(o + " ");
}
public static void skrivln(Object... a)
{
skriv(a);
System.out.println();
}
private static int parter0(int[] a, int v, int h, int skilleverdi)
{
while (true)
{
while (v <= h && a[v] < skilleverdi) v++;
while (v <= h && a[h] >= skilleverdi) h--;
if (v < h) Tabell.bytt(a,v++,h--);
else return v;
}
}
public static int parter(int[] a, int fra, int til, int skilleverdi)
{
fratilKontroll(a.length, fra, til);
return parter0(a, fra, til - 1, skilleverdi);
}
public static int parter(int[] a, int skilleverdi)
{
return parter0(a, 0, a.length - 1, skilleverdi);
}
private static int sParter0(int[] a, int v, int h, int indeks)
{
bytt(a, indeks, h);
int pos = parter0(a, v, h - 1, a[h]);
bytt(a, pos, h);
return pos;
}
public static int sParter(int[] a, int fra, int til, int indeks)
{
fratilKontroll(a.length, fra, til);
if (fra == til) throw new
IllegalArgumentException("Intervallet a[" + fra + ":" + til + "> er tomt!");
if (indeks < fra || indeks >= til) throw new
IllegalArgumentException("indeks(" + indeks + ") er utenfor intervallet!");
return sParter0(a, fra, til - 1, indeks);
}
public static int sParter(int[] a, int indeks)
{
if (indeks < 0 || indeks >= a.length) throw new
IllegalArgumentException("indeks(" + indeks + ") er utenfor tabellen!");
return sParter0(a, 0, a.length - 1, indeks);
}
private static void kvikksortering0(int[] a, int v, int h)
{
if (v >= h) return;
int k = sParter0(a, v, h, (v + h)/2);
kvikksortering0(a, v, k - 1);
kvikksortering0(a, k + 1, h);
}
public static void kvikksortering(int[] a, int fra, int til)
{
fratilKontroll(a.length, fra, til);
kvikksortering0(a, fra, til - 1);
}
public static void kvikksortering(int[] a)
{
kvikksortering0(a, 0, a.length - 1);
}
public static int[] randPerm(int n)
{
Random r = new Random();
int[] a = new int[n];
for (int i = 0; i < n; )
{
int k = r.nextInt(n) + 1;
boolean nyVerdi = true;
for (int j = 0; j < i && nyVerdi; j++)
{
if (a[j] == k) nyVerdi = false;
}
if (nyVerdi) a[i++] = k;
}
return a;
}
public static int maks(double[] a)
{
int m = 0;
double maksverdi = a[0];
for (int i = 1; i < a.length; i++) if (a[i] > maksverdi)
{
maksverdi = a[i];
m = i;
}
return m;
}
public static int maks(int[] a)
{
int m = 0;
int maksverdi = a[0];
for (int i = 1; i < a.length; i++) if (a[i] > maksverdi)
{
maksverdi = a[i];
m = i;
}
return m;
}
public static int[] naturligeTall(int n)
{
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i + 1;
return a;
}
public static boolean nestePermutasjon(int[] a)
{
int n = a.length, i = n - 2;
while (i >= 0 && a[i] > a[i+1]) i--;
if (i < 0) return false;
int j = n - 1;
for (int x = a[i]; a[j] < x; j--);
bytt(a,i,j);
for (j = n; ++i < --j; ) bytt(a,i,j);
return true;
}
private static class PermIterator implements Iterator<int[]>
{
private int[] a;
private boolean flere = true;
private PermIterator(int n)
{
a = naturligeTall(n);
}
private PermIterator(int[] p)
{
a = p.clone();
}
public int[] next()
{
int[] b = a.clone();
flere = nestePermutasjon(a);
return b;
}
public boolean hasNext() { return flere; }
public void remove() { throw new UnsupportedOperationException(); }
}
public static Iterator<int[]> permiterator(int n)
{
return new PermIterator(n);
}
public static Iterator<int[]> permiterator(int[] a)
{
return new PermIterator(a);
}
public static <T extends Comparable<? super T>> int maks(T[] a)
{
int m = 0;
T maksverdi = a[0];
for (int i = 1; i < a.length; i++) if (a[i].compareTo(maksverdi) > 0)
{
maksverdi = a[i];
m = i;
}
return m;
}
public static void bytt(Object[] a, int i, int j)
{
Object temp = a[i]; a[i] = a[j]; a[j] = temp;
}
public static Integer[] randPermInteger(int n)
{
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++) a[i] = i+1;
Random r = new Random();
for (int k = n-1; k > 0; k--)
{
int i = r.nextInt(k+1);
bytt(a,k,i);
}
return a;
}
public static <T extends Comparable<T>> void innsettingssortering(T[] a)
{
for (int i = 1; i < a.length; i++)
{
T temp = a[i];
int j = i-1;
for (; j >= 0 && temp.compareTo(a[j]) < 0; j--) a[j+1] = a[j];
a[j+1] = temp;
}
}
public static <T> int maks(T[] a, Comparator<? super T> c)
{
int m = 0;
T maksverdi = a[0];
for (int i = 1; i < a.length; i++) if (c.compare(a[i],maksverdi) > 0)
{
maksverdi = a[i];
m = i;
}
return m;
}
public static int binærsøk(int[] a, int fra, int til, int verdi)
{
Tabell.fratilKontroll(a.length,fra,til);
int v = fra, h = til - 1;
while (v < h)
{
int m = (v + h)/2;
if (verdi > a[m]) v = m + 1;
else h = m;
}
if (h < v || verdi < a[v]) return -(v + 1);
else if (verdi == a[v]) return v;
else return -(v + 2);
}
public static int binærsøk(int[] a, int verdi)
{
return binærsøk(a,0,a.length,verdi);
}
public static <T>
void innsettingssortering(T[] a, Comparator<? super T> c)
{
for (int i = 1; i < a.length; i++)
{
T temp = a[i];
int j = i-1;
for (; j >= 0 && c.compare(temp,a[j]) < 0; j--) a[j+1] = a[j];
a[j+1] = temp;
}
}
private static <T>
void flett(T[] a, T[] b, int fra, int m, int til, Comparator<? super T> c)
{
int n = m - fra;
System.arraycopy(a,fra,b,0,n);
int i = 0, j = m, k = fra;
while (i < n && j < til)
a[k++] = c.compare(b[i],a[j]) < 0 ? b[i++] : a[j++];
while (i < n) a[k++] = b[i++];
}
private static <T>
void flettesortering(T[] a, T[] b, int fra, int til, Comparator<? super T> c)
{
if (til - fra <= 1) return;
int m = (fra + til)/2;
flettesortering(a,b,fra,m,c);
flettesortering(a,b,m,til,c);
flett(a,b,fra,m,til,c);
}
public static <T> void flettesortering(T[] a, Comparator<? super T> c)
{
T[] b = (T[]) new Object[a.length/2];
flettesortering(a,b,0,a.length,c);
}
private static void flett(int[] a, int[] b, int fra, int m, int til)
{
int n = m - fra;
System.arraycopy(a,fra,b,0,n);
int i = 0, j = m, k = fra;
while (i < n && j < til)
a[k++] = b[i] < a[j] ? b[i++] : a[j++];
while (i < n) a[k++] = b[i++];
}
private static void flettesortering(int[] a, int[] b, int fra, int til)
{
if (til - fra <= 1) return;
int m = (fra + til)/2;
flettesortering(a,b,fra,m);
flettesortering(a,b,m,til);
flett(a,b,fra,m,til);
}
public static void flettesortering(int[] a)
{
int[] b = new int[a.length/2];
flettesortering(a,b,0,a.length);
}
public static <T>
int parter(T[] a, int v, int h, T skilleverdi, Comparator<? super T> c)
{
while (v <= h && c.compare(a[v],skilleverdi) < 0) v++;
while (v <= h && c.compare(skilleverdi,a[h]) <= 0) h--;
while (true)
{
if (v < h) Tabell.bytt(a,v++,h--); else return v;
while (c.compare(a[v],skilleverdi) < 0) v++;
while (c.compare(skilleverdi,a[h]) <= 0) h--;
}
}
public static <T> int parter(T[] a, T skilleverdi, Comparator<? super T> c)
{
return parter(a,0,a.length-1,skilleverdi,c);
}
public static <T>
int sParter(T[] a, int v, int h, int k, Comparator<? super T> c)
{
if (v < 0 || h >= a.length || k < v || k > h) throw new
IllegalArgumentException("Ulovlig parameterverdi");
bytt(a,k,h);
int p = parter(a,v,h-1,a[h],c);
bytt(a,p,h);
return p;
}
public static <T>
int sParter(T[] a, int k, Comparator<? super T> c)
{
return sParter(a,0,a.length-1,k,c);
}
private static <T>
void kvikksortering(T[] a, int v, int h, Comparator<? super T> c)
{
if (v >= h) return;
int p = sParter(a,v,h,(v + h)/2,c);
kvikksortering(a,v,p-1,c);
kvikksortering(a,p+1,h,c);
}
public static <T>
void kvikksortering(T[] a, Comparator<? super T> c)
{
kvikksortering(a,0,a.length-1,c);
}
public static boolean erSortertStigende(int[] a)
{
for (int i = 1; i < a.length; i++)
if (a[i-1] > a[i]) return false;
return true;
}
public static void innsettingssortering(int[] a, int fra, int til)
{
fratilKontroll(a.length,fra,til);
for (int i = fra + 1; i < til; i++)
{
int temp = a[i];
int j = i-1; for (; j >= fra && temp < a[j]; j--) a[j+1] = a[j];
a[j+1] = temp;
}
}
public static void innsettingssortering(int[] a)
{
innsettingssortering(a,0,a.length);
}
public static int antallForskjellige(int[] a)
{
if (a.length <= 1) return a.length;
int antall = 1;
for (int i = 1; i < a.length; i++) if (a[i-1] < a[i]) antall++;
return antall;
}
public static int union(int[] a, int m, int[] b, int n, int[] c)
{
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if (a[i] < b[j]) c[k++] = a[i++];
else if (a[i] == b[j])
{
c[k++] = a[i++];
j++;
}
else c[k++] = b[j++];
}
while (i < m) c[k++] = a[i++];
while (j < n) c[k++] = b[j++];
return k;
}
public static int union(int[] a, int[] b, int[] c)
{
return union(a,a.length,b,b.length,c);
}
public static int snitt(int[] a, int m, int[] b, int n, int[] c)
{
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if (a[i] < b[j]) i++;
else if (a[i] == b[j])
{
c[k++] = a[i++];
j++;
}
else j++;
}
return k;
}
public static int snitt(int[] a, int[] b, int[] c)
{
return snitt(a,a.length,b,b.length,c);
}
public static int differans(int[] a, int m, int[] b, int n, int[] c)
{
if (m < 0 || m > a.length)
throw new IllegalArgumentException("a[0:m> er ulovlig!");
if (n < 0 || n > b.length)
throw new IllegalArgumentException("b[0:n> er ulovlig!");
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if (a[i] < b[j]) c[k++] = a[i++];
else if (a[i] == b[j]) { i++; j++;}
else j++;
}
while (i < m) c[k++] = a[i++];
return k;
}
public static int differans(int[] a, int[] b, int[] c)
{
return differans(a,a.length,b,b.length,c);
}
public static boolean erLik(int[] a, int m, int[] b, int n)
{
if (m < 0 || m > a.length)
throw new IllegalArgumentException("a[0:m> er ulovlig!");
if (n < 0 || n > b.length)
throw new IllegalArgumentException("b[0:n> er ulovlig!");
if (m != n) return false;
if (a == b) return true;
for (int i = 0; i < m; i++)
if (a[i] != b[i]) return false;
return true;
}
public static boolean erLik(int[] a, int[] b)
{
return erLik(a,a.length,b,b.length);
}
public static boolean inklusjon(int[] a, int m, int[] b, int n)
{
if (m < 0 || m > a.length)
throw new IllegalArgumentException("a[0:m> er ulovlig!");
if (n < 0 || n > b.length)
throw new IllegalArgumentException("b[0:n> er ulovlig!");
int i = 0, j = 0;
while (i < m && j < n)
{
if (a[i] < b[j]) i++;
else if (a[i] == b[j]) {i++; j++;}
else return false;
}
return j == n;
}
public static boolean inklusjon(int[] a, int[] b)
{
return inklusjon(a,a.length,b,b.length);
}
public static int xunion(int[] a, int m, int[] b, int n, int[] c)
{
if (m < 0 || m > a.length)
throw new IllegalArgumentException("a[0:m> er ulovlig!");
if (n < 0 || n > b.length)
throw new IllegalArgumentException("b[0:n> er ulovlig!");
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if (a[i] < b[j]) c[k++] = a[i++];
else if (a[i] == b[j]) { i++; j++;}
else c[k++] = b[j++];
}
while (i < m) c[k++] = a[i++];
while (j < n) c[k++] = b[j++];
return k;
}
public static int xunion(int[] a, int[] b, int[] c)
{
return xunion(a,a.length,b,b.length,c);
}
public static int maks(int[] a, int fra, int til)
{
if (fra < 0 || til > a.length || fra >= til)
{
throw new IllegalArgumentException("Illegalt intervall!");
}
int m = fra;
int maksverdi = a[fra];
for (int i = fra + 1; i < til; i++)
{
if (a[i] > maksverdi)
{
m = i;
maksverdi = a[m];
}
}
return m;
}
public static void utvalgssortering(int[] a)
{
for (int k = a.length; k > 1; k--)
{
bytt(a,maks(a,0,k),k-1);
}
}
public static <T> int maks(T[] a, int fra, int til, Comparator<? super T> c)
{
if (fra < 0 || til > a.length || fra >= til)
{
throw new IllegalArgumentException("Illegalt intervall!");
}
int m = fra;
T maksverdi = a[fra];
for (int i = fra + 1; i < til; i++)
{
if (c.compare(a[i], maksverdi) > 0)
{
m = i;
maksverdi = a[m];
}
}
return m;
}
public static <T> void utvalgssortering(T[] a, Comparator<? super T> c)
{
for (int k = a.length; k > 1; k--)
{
bytt(a,maks(a,0,k,c),k-1);
}
}
public static void snu(int[] a, int fra, int til)
{
fratilKontroll(til, fra, til);
int v = fra, h = til - 1;
while (v < h) bytt(a,v++,h--);
}
public static void snu(int[] a)
{
snu(a,0,a.length-1);
}
}