#pragma once

#include <vector>
#include <algorithm>
#include <utility>
#include <type_traits>
#include <cassert>

#include <iostream>

namespace Gudhi_laplacian
{
  template <typename T>
  class Sparse_vector
  {
  public:
    Sparse_vector() : compressed(true), data()
    {
      static_assert(std::is_arithmetic<T>::value, "Only arithmetic types are supported.");
    }

    // Default destructor.
    // Default copy-constructor.
    // Default assignment operator.
    // Default moves.

    void compress()
    {
      if (compressed)
        return;
    
      std::vector<std::pair<unsigned int, T> > tmp(data); 
      data.clear();
      std::sort(tmp.begin(), tmp.end());
      for (auto it = tmp.cbegin(); it != tmp.cend(); ++it)
      {
        if (data.empty())
        {
          if (it->second != T())
          {
            data.push_back(*it);
          }
        }
        else if (it->first == data.back().first)
        {
          T x = data.back().second + it->second;
          if (x == T())
          {
            data.pop_back();
          }
          else
          {
            data.back().second = x;
          }
        }
        else if (it->second != T())
        {
          data.push_back(*it); 
        }
      }
      compressed = true;
    }

    inline void add(unsigned int i, T x)
    {
      data.push_back(std::make_pair(i, x));
      compressed = false;
    }

    static std::vector<Sparse_vector<T> > transpose(const std::vector<Sparse_vector<T> > & x, unsigned int n)
    {
      unsigned int m = x.size();

      std::vector<Sparse_vector<T> > ret(n);
      for (unsigned int i = 0; i < m; ++i)
      {
        const Sparse_vector<T> & a = x[i];
        for (auto it = a.cbegin(); it != a.cend(); ++it)
        {
          assert(it->first < n);
          ret[it->first].data.push_back(std::make_pair(i, it->second)); // Avoid add to keep compressed = true.
        }
      }
      return ret;
    }

    inline const T & operator[](typename std::vector<std::pair<unsigned int, T> >::size_type i)
    {
      std::cerr << "UNTESTED FUNCTION" << std::endl;
      assert(compressed);
      auto it = std::lower_bound(data.cbegin(), data.cend(), std::make_pair(i, T()),
                                 [](const std::pair<unsigned int, T> & x, const std::pair<unsigned int, T> & y)
                                 { return x.first < y.first; });
      if (it == data.cend() || it->first != i)
        return T();
      else
        return it->second;
    }

    inline typename std::vector<std::pair<unsigned int, T> >::size_type size() const { return data.size(); }
    inline typename std::vector<std::pair<unsigned int, T> >::size_type nnz() const { return data.size(); }
    
    using Const_iterator = typename std::vector<std::pair<unsigned int, T> >::const_iterator;
    inline Const_iterator cbegin() const { return data.cbegin(); }
    inline Const_iterator cend() const { return data.cend(); }
    inline Const_iterator begin() const { return data.cbegin(); }
    inline Const_iterator end() const { return data.cend(); }
    
  private:
    bool compressed;
    std::vector<std::pair<unsigned int, T> > data;
  };

}