// Dit programma biedt de gebruiker een menustructuur om met Fibonacci rijen
// te werken. Het dient om de oplossingen van onderdeel A van de tweede
// opgave Datastructuren, najaar 2005, enigszins uit te proberen.
//
// Het is echter geen ultieme correctheidstest. Zo laat dit programma niet
// toe dat een getal meerdere malen in de Fibonacci rij voorkomt, terwijl dat
// in principe wel mogelijk is.
//
// Bij het toevoegen van getallen heeft de gebruiker de gelegenheid om deze
// getallen random te laten generen. Zo kan hij/zij lekker snel een grote
// Fibonacci rij creeren.
// Tevens bevat het programma de mogelijkheid om de Fibonacci rij op het
// scherm af te beelden. Dit is een aparte optie in de menustructuur en wordt
// niet automatisch na iedere operatie op de Fibonacci rij uitgevoerd. De
// reden hiervoor is dat dit in het geval van een volle Fibonacci rij zoveel
// regels op het beeldscherm zou kosten, dat eventuele foutmeldingen van het
// scherm af zouden schieten.
// Overigens heeft het sowieso niet zo heel veel zin om deze afbeeldfunctie
// voor een volle Fibonacci rij aan te roepen, omdat de breedte van een
// venster (window) op een beeldscherm toch al gauw te klein is om alle
// getallen en spaties te bevatten die naast elkaar afgedrukt dienen te worden.

// Indien je meer toelichting nodig hebt over de opdracht of over de werking
// van dit programma, kom dan langs bij Robert Brijder, kamer 143.
// Ook als je fouten of inconsistenties (afgezien van de keuze voor Engels,
// respectievelijk Nederlands) in de code of het commentaar ontdekt, houdt
// Robert zich van harte aanbevolen.

// Heb je vragen over je eigen programma, wend je dan tot Sven van Haastregt:
// svhaastr@liacs.nl


#include <iostream>
#include <cstdlib>   // om random getallen te kunnen genereren
using namespace std;
#include "fiboqueue.h"
#define  MaxWaarde 999

int RandomRij [MaxWaarde+1],      // een rij randomgetallen
    RandomPositie [MaxWaarde+1],  // de positie van een getal in `RandomRij'
    RandomN;     // het aantal getallen dat nog in de randomrij staat
FiboNode *KnoopMetWaarde [MaxWaarde+1]; // een rij met pointers naar getallen
                                        // in de Fibonacci rij

//****************************************************************************

void InitRijen ()
 // initialiseer de rij van random getallen
 // en die van pointers naar knopen in de Fibonacci rij
{ QValueTp Waarde;

  RandomN = MaxWaarde;
  for (Waarde=1;Waarde<=RandomN;Waarde++)
  { RandomRij [Waarde] = Waarde;
    RandomPositie [Waarde] = Waarde;
  }

  for (Waarde=1;Waarde<=MaxWaarde;Waarde++)
    KnoopMetWaarde[Waarde] = NULL;

}  // InitRijen

//****************************************************************************

void GenereerRandomGetallen (FiboQueue *q, int N)
 // genereer `N' random getallen en voeg die toe aan de Fibonacci rij
{ int i,
      r, p;
  float fr;
  QValueTp Waarde,
           Hulp;

  for (i=1;i<=N;i++)
  {   // bepaal een random getal p tussen 1 en RandomN
    r = rand ();
    fr = ((float) r)/(((float) RAND_MAX)+1.0);
      // bij gewoon `RAND_MAX + 1' zou je over MAXINT heen kunnen lopen
      // en aldus een negatief getal krijgen
    fr *= RandomN;
    p = (int) fr+1;

      // we pakken nu het p-de random getal uit `RandomRij'
    Waarde = RandomRij [p];
    Hulp = RandomRij [RandomN];
    RandomRij [p] = Hulp;
    RandomPositie [Hulp] = p;
    RandomN --;
    KnoopMetWaarde [Waarde] = q -> Insert (Waarde);
  }  // for

}  // GenereerRandomGetallen

//****************************************************************************

void VoerGetallenIn (FiboQueue *q, int N)
 // voer met de hand `N' getallen in in de Fibonacci rij
{ int i,
      p;
  QValueTp Waarde,
           Hulp;

  for (i=1;i<=N;i++)
  { cout << "Geef een waarde voor de " << i << "-e in te voeren knoop,\n";
    cout << " minimaal 1, maximaal " << MaxWaarde << " : ";
    cin >> Waarde;
    if ((Waarde < 1) || (Waarde > MaxWaarde))
      cout << "Verkeerde waarde.\n";
    else
      if (KnoopMetWaarde [Waarde] != NULL)
      { cout << "Sorry, deze waarde stond al in de rij.\n";
        cout << "Ze is dus niet nog een keer ingevoegd.\n";
      }
      else
      {  // haal `Waarde' uit `RandomRij' en voeg haar toe aan de Fibonacci rij
        p = RandomPositie [Waarde];
        Hulp = RandomRij [RandomN];
        RandomRij [p] = Hulp;
        RandomPositie [Hulp] = p;
        RandomN --;
        KnoopMetWaarde [Waarde] = q -> Insert (Waarde);
      }
  }  // for

}  // VoerGetallenIn

//****************************************************************************

void VerwerkKeuze1 (FiboQueue *q)
 // geef de gebruiker de gelegenheid om een of meer waardes
 // in de Fibonacci rij in te voegen (Insert)
{ int  N;
  char Keuze = 'j';

  cout << "Hoeveel knopen wilt u invoeren, nog maximaal " << RandomN << " mogelijk : ";
  cin >> N;

  if ((N<0) || (N>RandomN))
    cout << "Verkeerd aantal.\n";
  else
    if (N>=1)
    { cout << "U kunt de waarde(s) zelf invoeren, of u kunt ze random laten genereren.\n";
      cout << "Wilt u ze zelf invoeren,  j/n : ";
      cin >> Keuze;
      if ((Keuze=='n') || (Keuze=='N'))
        GenereerRandomGetallen (q, N);
      else
        VoerGetallenIn (q, N);
    }

}  // VerwerkKeuze1

//****************************************************************************

void VerwerkKeuze2 (FiboQueue *q)
 // verwijder het minimum uit de Fibonacci rij en laat de gebruiker weten
 // welke waarde dit was (DeleteMin)
{ QValueTp Waarde;

  if (! q -> IsEmpty())
  { Waarde = q -> DeleteMin ();
    KnoopMetWaarde [Waarde] = NULL;
     // we mogen `Waarde' een volgende keer weer invoeren ->
     //  voeg haar toe aan `RandomRij'
    RandomN ++;
    RandomRij [RandomN] = Waarde;
    RandomPositie [Waarde] = RandomN;
    cout << "We hebben de (minimale) waarde " << Waarde <<
            " uit de Fibonacci rij gehaald.\n";
  }
  else
    cout << "De Fibonacci rij was al leeg.\n";

}  // VerwerkKeuze2

//****************************************************************************

void VerwerkKeuze3 (FiboQueue *q)
 // geef de gebruiker de gelegenheid om een waarde in de Fibonacci rij
 // te verlagen (Decrease)
{ QValueTp OudeWaarde,
           NieuweWaarde;
  int p;

  cout << "Geef de oude waarde van de knoop die u wilt verlagen : ";
  cin >> OudeWaarde;
  if ((OudeWaarde <= 1) || (OudeWaarde > MaxWaarde))
    cout << "Verkeerde waarde.\n";
  else
    if (KnoopMetWaarde[OudeWaarde] == NULL)
    { cout << "Deze waarde stond nog niet in de Fibonacci rij.\n";
      cout << "We kunnen haar dus zeker niet verlagen.\n";
    }
    else
    { cout << "Geef een nieuwe waarde voor deze knoop,\n";
      cout << " minimaal 1, maximaal " << OudeWaarde-1 << " : ";
      cin >> NieuweWaarde;
      if ((NieuweWaarde < 1) || (NieuweWaarde >= OudeWaarde))
        cout << "Verkeerde waarde.\n";
      else
        if (KnoopMetWaarde [NieuweWaarde] != NULL)
        { cout << "Sorry, deze waarde stond al in de rij.\n";
          cout << "We hebben de oude waarde dus niet verlaagd.\n";
        }
        else
        { q -> Decrease (KnoopMetWaarde[OudeWaarde], NieuweWaarde);
          KnoopMetWaarde [NieuweWaarde] = KnoopMetWaarde [OudeWaarde];
          KnoopMetWaarde [OudeWaarde] = NULL;
           // vervang `NieuweWaarde' in `RandomRij' door `OudeWaarde'
          p = RandomPositie [NieuweWaarde];
          RandomRij [p] = OudeWaarde;
          RandomPositie [OudeWaarde] = p;
        }
    }  // else: OudeWaarde OK

}  // VerwerkKeuze3

//****************************************************************************

void VerwerkKeuze4 (FiboQueue *q)
 // geef de gebruiker de gelegenheid om een waarde uit de Fibonacci rij
 // te verwijderen (Delete)
{

  cout << "Helaas ... deze methode hoeft niet ge-implementeerd te worden\n";

}  // VerwerkKeuze4

//****************************************************************************

int main () 
{ int       Keuze;
  FiboQueue *q;

  InitRijen ();
  q = new FiboQueue;

  do
  { cout << '\n';
    cout << "0. Stop\n1. Insert\n2. DeleteMin\n3. Decrease\n4. Delete\n5. Show\n";
    cout << "Maak een keuze : ";
    cin >> Keuze;
    cout << '\n';
    switch (Keuze)
    { case 1: VerwerkKeuze1 (q);
              break;
      case 2: VerwerkKeuze2 (q);
              break;
      case 3: VerwerkKeuze3 (q);
              break;
      case 4: VerwerkKeuze4 (q);
              break;
      case 5: q -> Show ();
              break;
      case 0: break;
      default: cout << "Verkeerde invoer. Probeer het nog eens.\n";
    }
  } while (Keuze != 0);

  delete q;           // deze instructie is expliciet nodig om
                      // de destructor aan het werk te zetten (getest)

  return 0;

}