#include <iostream>
#include <list>
#include "listIOpar.hh"
using namespace std; 

// El uso de typedef no es necesario para que la solución sea correcta-
typedef list<pair<int,int> > Vec_espars;


int prod_escalar(const Vec_espars& t1, const Vec_espars& t2) 
/* Pre: t1 i t2 son les representacions dispersas de dos vectors v1 i
   v2 de la mateixa longitud */
/* Post: el resultat és el producte escalar de v1 i v2 */
{
  int pe = 0; 
  list<pair<int,int> >::const_iterator it1, it2; 
  it1 = t1.begin(); 
  it2 = t2.begin();
/* Inv: si it1 != t1.end(), it2 != t2.end(), pos1 = it1->first, pos2 =
   it2->first i pos = maxim(pos1,pos2), llavors pe és el producte
   escalar de les posicions de v1[0...pos-1] i v2[0...pos-1];
   altrament, pe és el producte escalar de v1 i v2 */
  while (it1 != t1.end() and it2 != t2.end()) {
     if (it1->first < it2->first) ++it1;
     else if (it2->first < it1->first) ++it2;
     else {
        pe += (it1->second)*(it2->second); 
        ++it1;
        ++it2; 
     }
  }
  return pe;
}

/* Terminación: en cada iteración it1, it2 o ambos se aproximan a
   t1.end() o t2.end()*/




// Apartado 2.2

// Inmersión por resultados
void ir_prod_esc(const Vi& v1, const Vi& v2, int j, int& p) {
/* Pre:  v1.size() = v2.size(), 0 <= j <= v1.size() */
/* Post: p es el producto escalar de v1[0...j-1] y v2[0...j-1] */
  if (j == 0) p = 0;
  else {
     ir_prod_esc(v1,v2,j-1,p);
     /* HI: p es el producto escalar de v1[0...j-2] y v2[0...j-2] 
	para 1 <= j <= v.size() */
     p += v1[j-1]*v2[j-1];
  }
}

/* Terminación: en cada iteración j decrece. */


void prod_escalar(const Vi& v1, const Vi& v2, int& pe) 
/* Pre:  v1.size() = v2.size()  */
/* Post: pe és el producte escalar de v1 i v2 */
{  
  int n = v1.size();
  ir_prod_esc(v1,v2,n,pe);
}



// Inmersión por datos
void id_vec_prod_esc(const Vi& v1, const Vi& v2, int j, int& pe) {
/* Pre: v1.size() = v2.size() = v.size(), 0 <= j <= v.size() 
   pe es el producto escalar de v1[0...j-1] y v2[0...j-1] */
/* Post: pe es el producto escalar de v1 i v2 */
  if (j < v1.size()) {
     pe += v1[j]*v2[j];
     id_vec_prod_esc(v1,v2,j+1,pe);
    /* HI: el resultado es el producto escalar de v1 y v2 */
  }
}

/* Terminación: en cada iteración la distancia entre v1.size() y j
   decrece. */


void vec_prod_escalar(const Vi& v1, const Vi& v2, int& pe) 
/* Pre:  v1.size() = v2.size() */
/* Post: pe és el producte escalar de v1 i v2 */
{  
  pe = 0;
  id_vec_prod_esc(v1,v2,0,pe);
}