#include "SparseVector.hpp"

#include <list>
#include <cmath>
#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <stdexcept>

namespace pcsvm {

using namespace pcsvm;


SparseVector::SparseVector(const float *v, int n)
{
    for (int i=0; i<n; ++i)
        if (v[i])
            data_.push_back(item(i, v[i]));
}


SparseVector::SparseVector(const std::vector<float> &v)
{
    std::vector<float>::const_iterator it;
    item tmpItem;
    int index = 0;

    for (it=v.begin(); it != v.end(); ++it)
    {
            if (*it)
            {
                    tmpItem.index = index;
                    tmpItem.value= *it;
                    data_.push_back(tmpItem);
            }
            ++index;
    }
}

SparseVector::SparseVector(const SparseVector *o)
{
        SparseVector::const_iterator it;

        for (it = o->begin(); it != o->end(); ++it)
                data_.push_back(*it);
}

SparseVector& SparseVector::operator=(const SparseVector& other)
             {
                 //xx: nach einigen modifikationen ist das jetzt der standard-operator. so lassen ?
                     if (this != &other)
                     {
                             data_ = other.data_;
                     }
                     return *this;
             }



std::string SparseVector::to_str() const
             {
                 std::ostringstream s;
                 s << *this;
                 return s.str();
             }



SparseVector SparseVector::copy()  const
             {
                     return SparseVector(*this);
             }

 SparseVector& SparseVector::plusAlphaYpsilon(float alpha, const SparseVector &ypsilon)
             {
                    std::list<item>::iterator thisit, thisend;
                    std::list<item>::const_iterator yit, yend;

                    if (!alpha) return *this;

                    item *newnode;
                    
                    thisit = data_.begin();
                    thisend = data_.end();

                    if ((void*)&ypsilon == (void*)this)
                    {
                            float onePlusAlpha = 1.0f+alpha;
                            for (; thisit != thisend; ++thisit)
                                    thisit->value *= onePlusAlpha;
                            return *this;
                    }

                    yit = ypsilon.data_.begin();
                    yend = ypsilon.data_.end();
                    while (thisit != thisend && yit != yend)
                    {
                            if (thisit->index == yit->index)
                            {
                                    thisit->value += alpha* yit->value;
                                    ++thisit;
                                    ++yit;
                            }
                            else if (thisit->index < yit->index)
                            {
                                    ++thisit;
                            }
                            else
                            {
                                    newnode = new item();
                                    newnode->index = yit->index;
                                    newnode->value= alpha*yit->value;
                                    data_.insert(thisit, *newnode);
                                    ++yit;
                            }
                    }
                    while (yit != yend)
                    {
                            newnode = new item();
                            newnode->index = yit->index;
                            newnode->value= alpha*yit->value;
                            data_.push_back(*newnode);
                            ++yit;
                    }
                    // this[i] + alpha*y[i] might be zero, so prune:
                    prune(0);
                    return *this;
             }


SparseVector::SparseVector(const SparseVector &v): data_()
{
        SparseVector::const_iterator inpItStart, inpItEnd, it;

        inpItStart = v.begin();
        inpItEnd = v.end();
        item tempItem;
        for (it = inpItStart; it != inpItEnd; ++it)
        {
                tempItem.index = it->index;
                tempItem.value= it->value;
                data_.push_back(tempItem);
        }


}



void AnyIter::updateActual()
{
    if (!isValid()) return;

        if (_v2iter == _v2end) 
        {
                actualValue_.idx  = _v1iter->index;
                actualValue_.val1 = _v1iter->value;
                actualValue_.val2 = 0;
                return;
        } 
        if (_v1iter == _v1end)  
        {
                actualValue_.idx  = _v2iter->index;
                actualValue_.val2 = _v2iter->value;
                actualValue_.val1 = 0;
                return;
        } 
    // now: _v1iter and _v2iter are valid
        if (_v1iter->index < _v2iter->index) 
        {
                actualValue_.idx  = _v1iter->index;
                actualValue_.val1 = _v1iter->value;
                actualValue_.val2 = 0;
                return;
        } 

    // now: _v1iter is valid
    if (_v2iter->index < _v1iter->index)
        {
                actualValue_.idx  = _v2iter->index;
                actualValue_.val2 = _v2iter->value;
                actualValue_.val1 = 0;
                return;
        } 
        if (_v1iter->index == _v2iter->index)
        {
                actualValue_.idx  = _v2iter->index;
                actualValue_.val2 = _v2iter->value;
                actualValue_.val1 = _v1iter->value;
                return;
        }
}

bool AnyIter::isValid()
{
        return (_v1iter != _v1end || _v2iter != _v2end);
}

const IterValue* AnyIter::operator->() 
{
        return &actualValue_;
}

IterValue& AnyIter::operator*()
{
        return actualValue_;
}


AnyIter& AnyIter::operator++()
{

        if (_v1iter != _v1end && (_v2iter == _v2end || _v1iter->index < _v2iter->index))
                ++_v1iter;
        else if (_v2iter != _v2end && (_v1iter == _v1end || _v1iter->index > _v2iter->index))
                ++_v2iter;
        else if (_v1iter != _v1end && _v2iter != _v2end)
        {
                ++_v1iter;
                ++_v2iter;
        }
        if (isValid()) updateActual();

        return *this;
}

void BothIter::updateNext()
{
        // assert: none of the iters has reached the end
        // else isValid() should indicate the case !
        
        while (_v1iter != _v1end && _v2iter != _v2end && _v1iter->index != _v2iter->index)
        {
                if (_v1iter->index < _v2iter->index) ++_v1iter;
                if (_v2iter->index < _v1iter->index) ++_v2iter;
        }
                
        if (_v1iter != _v1end && _v2iter != _v2end)
        {
                // here: both iters show at entry with same index
                actualValue_.idx  = _v1iter->index;
                actualValue_.val1 = _v1iter->value;
                actualValue_.val2 = _v2iter->value;
        }

}

bool BothIter::isValid()
{
        return (_v1iter != _v1end && _v2iter != _v2end);
}

const IterValue* BothIter::operator->()
{
        return &actualValue_;
}

IterValue& BothIter::operator*()
{
        return actualValue_;
}

BothIter& BothIter::operator++()
{
        if (_v2iter->index == _v1iter->index) 
        {
                if (_v2iter != _v2end) ++_v2iter;
                else if (_v1iter != _v1end) ++_v1iter;
        }
        updateNext();
        return *this;
}



// FULLITER: iterates over pair of sparse vectors v1, v2 and delivers tuples (idx, val1, val2) for
//           0 <= idx <= max( v1.lastIndex(), v2.lastIndex())

void FullIter::initFirstPair()
{
        if (_v1iter == _v1end || _v2iter == _v2end)
        {
                _isValid = false;
                return;
        }

        if (_v1iter->index < _v2iter->index)
        {
                actualValue_.idx = _v1iter->index;
                actualValue_.val1= _v1iter->value;
                actualValue_.val2= 0;
                ++_v1iter;
                _isValid = true;
        }
        else if (_v1iter->index > _v2iter->index)
        {
                actualValue_.idx = _v2iter->index;
                actualValue_.val1= 0;
                actualValue_.val2= _v2iter->value;
                ++_v2iter;
        }
        else 
        {
                actualValue_.idx = _v2iter->index;
                actualValue_.val1= _v1iter->value;
                actualValue_.val2= _v2iter->value;
                ++_v1iter;
                ++_v2iter;
        }
        _actualIndex = actualValue_.idx;
        _isValid = true;
}

bool FullIter::isValid()
{
        return _isValid;
}

const IterValue* FullIter::operator->()
{
        return &actualValue_;
}

IterValue& FullIter::operator*()
{
        return actualValue_;
}

FullIter& FullIter::operator++()
{
        ++_actualIndex;

        if (_v1iter == _v1end && _v2iter == _v2end) 
        { 
                _isValid = false; 
                return *this; 
        }
        actualValue_.idx = _actualIndex;
        actualValue_.val1= 0;
        actualValue_.val2= 0;
        if (_v1iter != _v1end && _actualIndex == _v1iter->index)
        {
                actualValue_.val1 = _v1iter->value;
                ++_v1iter;
        }
        if (_v2iter != _v2end && _actualIndex == _v2iter->index)
        {
                actualValue_.val2 = _v2iter->value;
                ++_v2iter;
        }

        return *this;
}




float _dot(const SparseVector::const_iterator &v1begin, const SparseVector::const_iterator &v1end, 
           const SparseVector::const_iterator &v2begin, const SparseVector::const_iterator &v2end)
{

        float sum=0.0f;

        for (BothIter it(v1begin, v1end, v2begin, v2end); it.isValid(); ++it)
                sum += it->val1 * it->val2;

        return sum;

}

double _pDist(SparseVector::const_iterator v1begin, const SparseVector::const_iterator &v1end, 
              SparseVector::const_iterator v2begin,const  SparseVector::const_iterator &v2end, double p)
{

        AnyIter it(v1begin, v1end, v2begin, v2end);

        double sum = 0, tmp=0;
        for (; it.isValid(); ++it)
        {
                tmp = it->val1 - it->val2;
                sum += std::pow(std::abs(tmp),p);
        }

        return std::pow(sum, 1.0/p);

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Access methods: put() and get()
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//


void SparseVector::put(int idx, float value)
{

        // some remarks concerning speed:
        // filling a sparse vector is fastest when putting elements
        // with increasing index, nearly as fast is putting elements
        // with decreasing index. only random insertion becomes
        // slow for more or less dense vectors.
        //
        
        if (idx<0) throw std::range_error("put(): idx < 0 ! ");

        std::list<item>::iterator it;
        item node(idx, value);

        // internal: list is sorted by indices in growing order
        // beginngin from the head of the list.

        // empty list
        if (data_.empty())
        {
                if (value)  data_.push_back(node);
                return;
        }


        // index look at end of list ! [1]
        item lastItem = data_.back();
        if (lastItem.index < idx) 
        {
                if (value)  data_.push_back(node); 
                return;
        }

        // now search from beginning, keep ordering of list
            
        for (it = data_.begin(); it  != data_.end(); ++it)
        {
                if (idx < it->index) break;
                if (idx == it->index)
                { 
                        if (value) 
                           it->value = value; 
                        else // entry is zero !
                           data_.erase(it);
                        return;
                }
        }
        // checking for it != data_.end() not nedded, as
        // indices which belong after the list are handled
        // above. see [1]
        if (value)
           data_.insert(it, node);

}


float SparseVector::get(int idx) const
{
        if (idx<0) throw std::range_error("get(): idx < 0 ! ");

        const_iterator it;
        if (data_.empty())
                return 0.0f;
        for (it=begin(); it != end() && idx >= it->index ; ++it)
                if (idx == it->index)
                        return it->value;
        return 0.0f;
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//      overloaded operators
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

const SparseVector& SparseVector::operator*=(float skal)
{
        if (skal==0.0f)
                data_.clear();
        else
        {
                for (std::list<item>::iterator it = data_.begin(); it != data_.end(); ++it)
                        it->value *= skal;
        }
        return *this;
}



std::ostream& operator<<(std::ostream &o, const SparseVector &sv)
{
        SparseVector::const_iterator it;

        o << "<SparseVector ";

        if (sv.data_.size()<10)
        {
                for (it = sv.begin(); it != sv.end(); ++it)
                {
                        if (it != sv.begin()) o << ", ";
                         o << " " << it->index << ": " << it->value;
                }
        }
        else
        {
                int i;
                for (it = sv.begin(), i = 0; i < 4; ++it, ++i)
                {
                        if (it != sv.begin()) o << ", ";
                         o << " " << it->index << ": " << it->value; 
                }
                o << " ... ";

                SparseVector::const_iterator itx = sv.end();
                --itx; --itx; --itx; --itx; --itx; 
                for (i=0; i<5; i++, ++itx) 
                {
                        o << ", ";
                        o << " " << itx->index << ": " << itx->value; 
                }
        o << " (" << sv.data_.size() << " items)";
        }

        o << ">";
        return o;
}


std::vector<float> SparseVector::toVector(int startIndex, int endIndex)  const
{
        if (endIndex==-1) endIndex = lastIndex()+1;
        std::vector<float> result(endIndex-startIndex, 0.0f);

        std::list<SparseVector::item>::const_iterator it, itEnd;
        int tmpIdx;

        itEnd = end();
        for (it=begin(); it != itEnd && it->index <endIndex  ; ++it)
                if (it->index >= startIndex)
                {
                        tmpIdx = it->index-startIndex;
                        if (tmpIdx>=0) result[tmpIdx] = it->value;
                }
        return result;
}



SparseVector SparseVector::map(const SparseVector::FunctionType &f) const
{
        SparseVector retval;
        for (const_iterator it=begin(); it != end(); ++it)
                retval[it->index]=f(it->value);
        return retval;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//   update methods
///////////////////////////////////////////////////////////////////////////////////////////////////////////////





void SparseVector::prune(float epsilon) 
{
        std::list< item>::iterator it;

        for (it = begin(); it != end(); )
                if (fabs(double(it->value))<=epsilon)
                     it = data_.erase(it);
                else
                     ++it;
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//  FRIENDS
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

SparseVector axpy(float a, const SparseVector &x, const SparseVector &y)
{


        SparseVector retval = SparseVector();
        float value;

        std::list<SparseVector::item> &result = retval.data_;
        
        SparseVector::item tempobj;

        for (AnyIter it(x,y);  it.isValid(); ++it)
        {
                value = a*it->val1 + it->val2;
                if (value)
                {
                        tempobj.index = it->idx;
                        tempobj.value = value; 
                        result.push_back(tempobj);
                }
        }

        return retval;

}

float dot(const SparseVector &x, const SparseVector &y)
{

        SparseVector::const_iterator xit, xend;
        SparseVector::const_iterator yit, yend;
        xit= x.begin();
        yit= y.begin();
        xend = x.end();
        yend = y.end();
        return _dot(xit, xend, yit, yend);

}


double pDist(const SparseVector &x, const SparseVector &y, double p) 
{
        SparseVector::const_iterator xit, xend;
        SparseVector::const_iterator yit, yend;
        xit= x.begin();
        yit= y.begin();
        xend = x.end();
        yend = y.end();

        return _pDist(xit, xend, yit, yend, p);

}


double dist(const SparseVector &x, const SparseVector &y) 
{
        return pDist(x, y, 2.0);
}



SparseVector operator*(float skal, const SparseVector &sv)
{
        SparseVector tmp = sv;
        tmp *= skal;
        return tmp;
}



SparseVector operator*( const SparseVector &sv,float skal)
{
        return skal*sv;
}


float operator*( const SparseVector &a,const SparseVector &b)
{
    return dot(a,b);
}


double norm(const SparseVector &sv) 
{
        return sv.norm();
}

} // namespace