// Template für Paare und Arrays
//
// Aufruf: paar worte ...
//
// Klaus Kusche, 2014

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

template <typename T1, typename T2>
class Paar
{
  public:
    Paar() {}  // ohne Standard-Konstruktor könnte man kein Paar-Array anlegen!
    Paar(T1 e, T2 z) : eins(e), zwei(z) {}
    T1 getEins() { return eins; }
    T2 getZwei() { return zwei; }
    bool operator==(const Paar &r) const { return eins == r.eins; }
    bool operator<(const Paar &r) const { return eins < r.eins; }
  private:
    T1 eins;
    T2 zwei;
};

template <typename T>
class Array
{
  public:
    Array(int m) : max(m), anz(0), array(new T[max]) {}
    ~Array() { delete [] array; }

    // Copy-Konstruktor und Zuweisung verbieten
    Array(const Array &orig) = delete;
    Array &operator=(const Array &orig) = delete;

    bool dazu(const T &wert) {
      if (anz == max) return false;
      array[anz++] = wert;
      return true;
    }

    T* kleinstes();
    T* naechstes(const T &wert);
    
  private:
    int max;
    int anz;
    T *array;
};

template <typename T>
T* Array<T>::kleinstes()
{
  if (anz == 0) return nullptr;
  
  T *ergeb = &(array[0]);

  for (int i = 1; i < anz; ++i) {
    if (array[i] < *ergeb) {
      ergeb = &(array[i]);
    }
  }

  return ergeb;
}

template <typename T>
T* Array<T>::naechstes(const T &wert)
{
  // Zu Beginn wissen wir noch nicht, ob es überhaupt ein Ergebnis gibt:
  // Es gibt kein Ergebnis, wenn das Array leer ist,
  // oder wenn alle Elemente des Arrays kleinergleich "wert" sind.
  // Das erste Element des Arrays ist *nicht* automatisch erster Kandidat
  // für das Ergebnis (denn es könnte ja kleinergleich "wert" sein)
  T *ergeb = nullptr;

  for (int i = 0; i < anz; ++i) {
    // array[i] ist der neue Wert für das Ergebnis, wenn es
    // - größer ist als der Wert "wert", dessen Nachfolger wir suchen
    // - und entweder bisher noch gar kein solcher Wert gefunden wurde
    //   oder array[i] kleiner als der bisher gefundene Wert ist
    if ((wert < array[i]) && ((ergeb == nullptr) || (array[i] < *ergeb))) {
      ergeb = &(array[i]);
    }
  }

  return ergeb;  
}

typedef Paar<string, int> paar_t;

int main(int argc, const char *argv[])
{
  Array<paar_t> a(argc - 1);

  for (int i = 1; i < argc; ++i) {
    a.dazu(paar_t(argv[i], i));
  }

  for (paar_t *p = a.kleinstes(); p != nullptr; p=a.naechstes(*p)) {
    cout << p->getEins() << ": " << p->getZwei() << endl;
  }

  exit(EXIT_SUCCESS);
}