#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "progListeSC.h"
#include "fichierTP3.h"
using namespace std;



bool estTrieeLSC(ListeSC L){
  //   Res : Renvoie true si L est une ListeSC tri�e, false sinon

  if (estVideLSC(L) || estVideLSC(L->succ))
    return true;
  else
    return (L->info < (L->succ)->info) &&  estTrieeLSC(L->succ);
}

bool estListeIntervalle(ListeSC L){
  //   Res : renvoie true si L est une Liste intervalle, renvoie false sinon
  // A COMPLETER
  while ( L->succ != NULL) {
    if (L->succ->info - L->info != 1) return false;
    L=L->succ;
  }
  return true;
}

ListeSC consListeIntervalle1(int l, int p){
  //     Donn�e : l>0
  //     Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p
  //     Complexit� : Complexité dans le pire cas : O(N^2) ( boucle for + complexité de base de insererFinLC)
  assert(l>0);

  int i; ListeSC L;
  L=NULL;
  for(i=0;i<l;i++)
    insererFinLSC(L,p+i);
  return L;
}

ListeSC consListeIntervalle2(int l, int p){
  //     Donn�e : l>0
  //     Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p
  //     Complexit� : O(N)
  //     Version iterative
  p=p+l-1 ; //valeur du dernier element
  ListeSC L = NULL;
  while ( l>0) {
    L=creerLSC(p, L);
    p--;
    l--;
  }
  return L;
}

ListeSC consListeIntervalle3(int l, int p){
  //     Donn�e : l>0
  //     Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p
  //     Complexit� : O(N-1)
  //     Version r�cursive
    ListeSC L=NULL;
  if ( l == 0) return L;
  else {
    L = creerLSC(p,consListeIntervalle3(l-1,p+1));
    return L;
  }
}

void transfListeIntervalle(ListeSC L){
  //     Donn�e : L est une liste tri�e non vide
  //     Res : modifie L en y inserant des �l�ments de sorte qu'elle soit une Liste Intervalle
  //     Complexit� : ????
  while ( L->succ != NULL) {
    if (L->succ->info - L->info != 1) {
      insererApresLSC(L,L,L->info+1);
    }
    L=L->succ;
  }
  return;
}

ListeSC intersectionListesIntervalles(ListeSC l1, ListeSC l2){
  //     Donn�e : l1 et l2 2 listes intervalles
  //     Res : Renvoie l'intersection de l1 et l2; les �l�ments de la liste r�sultat sont recopi�s
  //     Complexit� : ordre O(N) une premiere partie au moins inferieure a la somme
  // de la longueur des listes, plus un appel lineaire a consListeIntervalle2
  assert(estListeIntervalle(l1));
  assert(estListeIntervalle(l2));
  while (l1 != NULL && l2 != NULL && l1->info != l2->info){
    if (l1->info<l2->info){
      l1= l1->succ;
    }
    else {
      l2=l2->succ;
    }
  }
  int p= l1->info;
  int l =0;
  while ( l1 != NULL && l2 != NULL && l1->info == l2->info){
    l1=l1->succ;
    l2=l2->succ;
    l++;
  }
  return consListeIntervalle2(l,p);
}

void plusLgSsLiInterv(ListeSC &L){
  //     Donn�e : L liste
  //     Res : L est modifiee, elle est la plus longue sous-liste intervalle de la liste en entr�e
  //     Complexit� : ????
  // ListeSC ret = L;
  // ListeSC ancien = NULL;
  // int lenght = 0;
  // while ( ret->succ != NULL){
  //   if (ret->succ->info - ret->info != 1){
  //     lenght=0;
  //     ret=ret->succ;
  //   }
  //   else {
  //     ancien
  //   }
  // }
}