#include "Item.hpp"

namespace local {

template <class I>
class ItemIterWrapper
{
    protected:
        I it_;                 // zu wrappender iterator
        Item item_;

    public:
        ItemIterWrapper(I it) : it_(it) , item_()
        {
            if (it->index==0)
                item_ = *it;
        }

        bool operator==(const I &other) const
        {
            return it_ == other;
        }
        bool operator==(const ItemIterWrapper<I> &other) const
        {
            return it_ == other.it_;
        }

        bool operator!=(const I &other) const
        {

            return it_ != other;
        }
        bool operator!=(const ItemIterWrapper<I> &other) const
        {
            return it_ != other.it_;
        }

        ItemIterWrapper operator++() 
        {
            item_.index++;
            if (item_.index > it_ -> index)
                ++it_;
            if (item_.index == it_ -> index)
                item_.value = it_ -> value;
            else
                item_.value = 0;

            return *this;
        }
};

typedef std::list<Item>::iterator Iterator;

class ValueIterator: public ItemIterWrapper<Iterator >
{
    public:
        ValueIterator(const Iterator &it): ItemIterWrapper<Iterator >(it) {};
        float& operator*() { return item_.value; }
        float* operator->(){ return &(item_.value); }

};

typedef std::list<Item>::const_iterator ConstIterator;
class ConstValueIterator: public ItemIterWrapper<ConstIterator >
{
    public:
        ConstValueIterator(const ConstIterator &it): ItemIterWrapper<ConstIterator >(it) {};
        float operator*() { return item_.value; }
        const float* operator->(){ return &(item_.value); }
};


} // namepspace local

class SparsePolicy
{
    private:

        std::list<Item> data_;

    public:

         static const bool do_comp_test = false;
         int entries() { return data_.size(); }
         void clear() { data_.clear(); }

         SparsePolicy(int n=0): data_() {};  // parameter n nur für interface-konvention der policies !

         class Proxy
         {
            public:
                    Proxy(int idx, SparsePolicy &sv): _idx(idx), _sv(sv) {}
                    operator float() { return _sv.get(_idx) ;}
                    float operator=(float val)
                                   { _sv.put(_idx, val); return val;}
            private:
                    int _idx;
                    SparsePolicy &_sv;
         };

         float get(int idx) const;
         void put(int idx, float value);





         inline Proxy operator[](int idx)       { return Proxy(idx, *this); }
                float operator[](int idx) const { return get(idx); }

                // fuer sparse vektoren sind alle indices gueltig:
         inline Proxy at(int idx)       { return Proxy(idx, *this); }
                float at(int idx) const { return get(idx); }

         int len() const { return data_.back().index+1; }

         typedef ::local::ConstValueIterator const_value_iterator;
         typedef ::local::ValueIterator      value_iterator;

         typedef std::list<Item>::iterator  item_iterator;
         typedef std::list<Item>::const_iterator  const_item_iterator;
         item_iterator begin() { return data_.begin(); }
         item_iterator end()   { return data_.end(); }
         const_item_iterator begin() const { return data_.begin(); }
         const_item_iterator end()   const { return data_.end(); }
};
        
float SparsePolicy::get(int idx) const
{
        //if (idx<0) throw std::range_error("get(): idx < 0 ! ");

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

void SparsePolicy::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);

}