/*
 *  Boyer-Moore Search
 *
 *  01.06.1998, implemented by Michael Neumann
 */

# include <algorithm>

int BoyerMooreSearch(char* text, char* muster, int tlen, int mlen)
{
  int i, j, skip[256];

  for(i=0; i<256; ++i)  skip[i]=mlen;
  for(i=0; i<mlen; ++i) skip[muster[i]]=mlen-1-i;

  for(i=j=mlen-1; j>=0; --i, --j)
    while(text[i] != muster[j]) {
      i += max(mlen-j,skip[text[i]]);
      if(i >= tlen) return -1;
      j = mlen-1;
    }
  return i;
}

/*
 *  BubbleSort
 *
 *  20.11.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __BUBBLESORT_HEADER__
# define __BUBBLESORT_HEADER__

# include <algorithm>

template <class itemType, class indexType=int>
void BubbleSort(itemType a[], indexType l, indexType r)
{
  static indexType i, j;

  for(i=r; i>l; --i)
    for(j=l; j<i; ++j)
      if(a[j] > a[j+1]) std::swap(a[j], a[j+1]);
}

# endif

/*
 *  BucketSort (Distrubution Counting)
 *
 *  21.11.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __BUCKETSORT_HEADER__
# define __BUCKETSORT_HEADER__

# include <algorithm>


// itemType must have an typecast to "int", which identifies the sortkey
template <class itemType, class indexType=int>
class BucketSort {
  public:

    // the array b[] had to be the same size like a[]
    void Sort(itemType a[], itemType b[], indexType l, indexType r) {
      a = &a[l]; b = &b[l];
      for(int i=0; i<sizeof(int); ++i) {
        sort_byte(i,a,b,r-l+1);
        std::swap(a,b);
      }
    }

  protected:

    sort_byte(int bytenr, itemType a[], itemType b[], indexType count) {
      static indexType i;
      typedef unsigned char* UCP;

      for(i=0; i<256; ++i) occurences[i] = 0;   // better: memset
      for(i=0; i<count; ++i) ++occurences[((UCP)&a[i])[bytenr]];
      for(i=1; i<256; ++i) occurences[i] += occurences[i-1];
      for(i=count-1; i>=0; --i)
        b[--occurences[((UCP)&a[i])[bytenr]]] = a[i];
    }

    int occurences[256];
};

# endif

/*
    Größter Gemeinsamer Teiler

    Es sind nur Werte größer als Null zulässig.
*/

int ggt( int a, int b )
{
  int temp;
  if( a < b ) { temp=a; a=b; b=temp; }
  while( (temp = a%b) != 0 )
  {
    a = b;
    b = temp;
  };
  return b;
}

/*
 *  Hash1.Cpp
 *
 *  03.06.1998, implemented by Michael Neumann
 */

int hash1(int M, char* t)
{
  unsigned h=0;
  for(;*t;++t) h = ((h << 8)+ *t) % M;
  return h;
}

/*
 *  hashpjw, algorithm by P.J.Weinberg
 *
 *  03.06.1998, implemented by Michael Neumann
 */

int hashpjw(int M, char* t)
{
  unsigned h=0, g;
  for(;*t;++t) {
    h = (h << 4)+ *t;
    if(g=h&0xf0000000) {
      h ^= g>>24;
      h ^= g;
    }
  }
  return h%M;
}

#include <stdio.h>

int main(int argc, char *argv[])
{
   printf("Hello World\n");
   return 0;
}

#include <iostream.h>

int main(int argc, char *argv[])
{
   cout << "Hello World" << endl;
   return 0;
}

#include <iostream>
using namespace std;

int main()
{
   cout << "Hello World" << endl;
   return 0;
}

/*
 *  InsertionSort
 *
 *  20.11.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __INSERTIONSORT_HEADER__
# define __INSERTIONSORT_HEADER__

# include <algorithm>

template <class itemType, class indexType=int>
void InsertionSort(itemType a[], indexType l, indexType r)
{
  static indexType i, j;
  static itemType v;

  for(i=l+1; i<=r; ++i) {
    for(j=i-1, v=a[i]; j>=l && a[j]>v; a[j+1]=a[j], --j);
    a[j+1] = v;
  }
}

# endif

/*
 *  MergeSort
 *
 *  21.11.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __MERGESORT_HEADER__
# define __MERGESORT_HEADER__

# include <algorithm>

// Array b[] must have same size like a[]; result is in a[]!
template <class itemType, class indexType=int>
void MergeSort(itemType a[], itemType b[], indexType l, indexType r)
{
  indexType i, j, k, m;

  if(r > l) {
    m = (r+l)/2;
    MergeSort(a,b,l,m);
    MergeSort(a,b,m+1,r);
    for(i=m+1; i>l; --i) b[i-1] = a[i-1];
    for(j=m; j<r; ++j) b[r+m-j] = a[j+1];
    for(k=l; k<=r; ++k) a[k] = (b[i] < b[j]) ?  b[i++] : b[j--];
  }
}

# endif

/*
 *  QuickSort, algorithm by C.A.R. Hoare (1960)
 *
 *  01.06.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __QUICKSORT_HEADER__
# define __QUICKSORT_HEADER__

# include <algorithm>

template <class itemType, class indexType=int>
void QuickSort(itemType a[], indexType l, indexType r)
{
  static itemType m;
  static indexType j;
  indexType i;

  if(r > l) {
    m = a[r]; i = l-1; j = r;
    for(;;) {
      while(a[++i] < m);
      while(a[--j] > m);
      if(i >= j) break;
      std::swap(a[i], a[j]);
    }
    std::swap(a[i],a[r]);
    QuickSort(a,l,i-1);
    QuickSort(a,i+1,r);
  }
}

# endif

/*
 *  SelectionSort
 *
 *  20.11.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __SELECTIONSORT_HEADER__
# define __SELECTIONSORT_HEADER__

# include <algorithm>

template <class itemType, class indexType=int>
void SelectionSort(itemType a[], indexType l, indexType r)
{
  static indexType i, j, min;

  for(i=l; i<r; ++i) {
    for(min=i, j=i+1; j<=r; ++j) if(a[j] < a[min]) min = j;
    std::swap(a[min], a[i]);
  }
}

# endif

/*
 *  ShellSort
 *
 *  20.11.1998, implemented by Michael Neumann (mneumann@ntecs.de)
 */

# ifndef __SHELLSORT_HEADER__
# define __SHELLSORT_HEADER__

# include <algorithm>

template <class itemType, class indexType=int>
void ShellSort(itemType a[], indexType l, indexType r)
{
  static indexType i, j, h;
  static itemType v;

  for(h=1; h<=(r-l)/9; h=3*h+1);
  for(; h>0; h/=3) {
    for(i=l+h; i<=r; ++i) {
      for(j=i-h, v=a[i]; j>=l && a[j]>v; a[j+h]=a[j], j-=h);
      a[j+h] = v;
    }
  }
}

# endif

#include <stdio.h>

void main()
{
   printf("Hello World\n");
}

#include <iostream.h>

void main()
{
   cout << "Hello World" << endl;
}