1c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// This file is part of Eigen, a lightweight C++ template library
2c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// for linear algebra.
3c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath//
4c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath//
6c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// This Source Code Form is subject to the terms of the Mozilla
7c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// Public License v. 2.0. If a copy of the MPL was not distributed
8c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
10c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#ifndef EIGEN_COMPRESSED_STORAGE_H
11c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#define EIGEN_COMPRESSED_STORAGE_H
12c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
13c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathnamespace Eigen {
14c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
15c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathnamespace internal {
16c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
17c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath/** \internal
18c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  * Stores a sparse set of values as a list of values and a list of indices.
19c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  *
20c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  */
21c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathtemplate<typename _Scalar,typename _Index>
22c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamathclass CompressedStorage
23c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath{
24c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  public:
25c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
26c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    typedef _Scalar Scalar;
27c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    typedef _Index Index;
28c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
29c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  protected:
30c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
31c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    typedef typename NumTraits<Scalar>::Real RealScalar;
32c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
33c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  public:
34c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
35c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    CompressedStorage()
36c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0)
37c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {}
38c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
39c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    CompressedStorage(size_t size)
40c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0)
41c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
42c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      resize(size);
43c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
44c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
45c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    CompressedStorage(const CompressedStorage& other)
46c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      : m_values(0), m_indices(0), m_size(0), m_allocatedSize(0)
47c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
48c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      *this = other;
49c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
50c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
51c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    CompressedStorage& operator=(const CompressedStorage& other)
52c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
53c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      resize(other.size());
547faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez      internal::smart_copy(other.m_values,  other.m_values  + m_size, m_values);
557faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez      internal::smart_copy(other.m_indices, other.m_indices + m_size, m_indices);
56c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return *this;
57c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
58c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
59c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    void swap(CompressedStorage& other)
60c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
61c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      std::swap(m_values, other.m_values);
62c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      std::swap(m_indices, other.m_indices);
63c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      std::swap(m_size, other.m_size);
64c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      std::swap(m_allocatedSize, other.m_allocatedSize);
65c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
66c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
67c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    ~CompressedStorage()
68c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
69c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      delete[] m_values;
70c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      delete[] m_indices;
71c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
72c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
73c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    void reserve(size_t size)
74c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
75c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      size_t newAllocatedSize = m_size + size;
76c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      if (newAllocatedSize > m_allocatedSize)
77c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        reallocate(newAllocatedSize);
78c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
79c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
80c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    void squeeze()
81c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
82c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      if (m_allocatedSize>m_size)
83c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        reallocate(m_size);
84c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
85c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
867faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez    void resize(size_t size, double reserveSizeFactor = 0)
87c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
88c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      if (m_allocatedSize<size)
897faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez        reallocate(size + size_t(reserveSizeFactor*double(size)));
90c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      m_size = size;
91c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
92c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
93c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    void append(const Scalar& v, Index i)
94c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
95c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      Index id = static_cast<Index>(m_size);
96c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      resize(m_size+1, 1);
97c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      m_values[id] = v;
98c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      m_indices[id] = i;
99c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
100c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
101c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline size_t size() const { return m_size; }
102c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline size_t allocatedSize() const { return m_allocatedSize; }
103c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline void clear() { m_size = 0; }
104c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
105c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline Scalar& value(size_t i) { return m_values[i]; }
106c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline const Scalar& value(size_t i) const { return m_values[i]; }
107c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
108c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline Index& index(size_t i) { return m_indices[i]; }
109c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline const Index& index(size_t i) const { return m_indices[i]; }
110c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
111c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    static CompressedStorage Map(Index* indices, Scalar* values, size_t size)
112c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
113c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      CompressedStorage res;
114c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      res.m_indices = indices;
115c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      res.m_values = values;
116c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      res.m_allocatedSize = res.m_size = size;
117c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return res;
118c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
119c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
120c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    /** \returns the largest \c k such that for all \c j in [0,k) index[\c j]\<\a key */
121c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline Index searchLowerIndex(Index key) const
122c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
123c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return searchLowerIndex(0, m_size, key);
124c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
125c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
126c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    /** \returns the largest \c k in [start,end) such that for all \c j in [start,k) index[\c j]\<\a key */
127c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline Index searchLowerIndex(size_t start, size_t end, Index key) const
128c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
129c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      while(end>start)
130c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      {
131c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        size_t mid = (end+start)>>1;
132c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        if (m_indices[mid]<key)
133c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          start = mid+1;
134c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        else
135c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          end = mid;
136c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      }
137c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return static_cast<Index>(start);
138c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
139c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
140c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    /** \returns the stored value at index \a key
141c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      * If the value does not exist, then the value \a defaultValue is returned without any insertion. */
1427faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez    inline Scalar at(Index key, const Scalar& defaultValue = Scalar(0)) const
143c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
144c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      if (m_size==0)
145c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        return defaultValue;
146c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      else if (key==m_indices[m_size-1])
147c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        return m_values[m_size-1];
148c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      // ^^  optimization: let's first check if it is the last coefficient
149c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      // (very common in high level algorithms)
150c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      const size_t id = searchLowerIndex(0,m_size-1,key);
151c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return ((id<m_size) && (m_indices[id]==key)) ? m_values[id] : defaultValue;
152c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
153c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
154c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    /** Like at(), but the search is performed in the range [start,end) */
1557faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez    inline Scalar atInRange(size_t start, size_t end, Index key, const Scalar& defaultValue = Scalar(0)) const
156c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
157c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      if (start>=end)
158c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        return Scalar(0);
159c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      else if (end>start && key==m_indices[end-1])
160c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        return m_values[end-1];
161c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      // ^^  optimization: let's first check if it is the last coefficient
162c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      // (very common in high level algorithms)
163c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      const size_t id = searchLowerIndex(start,end-1,key);
164c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return ((id<end) && (m_indices[id]==key)) ? m_values[id] : defaultValue;
165c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
166c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
167c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    /** \returns a reference to the value at index \a key
168c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      * If the value does not exist, then the value \a defaultValue is inserted
169c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      * such that the keys are sorted. */
1707faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez    inline Scalar& atWithInsertion(Index key, const Scalar& defaultValue = Scalar(0))
171c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
172c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      size_t id = searchLowerIndex(0,m_size,key);
173c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      if (id>=m_size || m_indices[id]!=key)
174c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      {
175c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        resize(m_size+1,1);
176c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        for (size_t j=m_size-1; j>id; --j)
177c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        {
178c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          m_indices[j] = m_indices[j-1];
179c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          m_values[j] = m_values[j-1];
180c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        }
181c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        m_indices[id] = key;
182c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        m_values[id] = defaultValue;
183c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      }
184c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      return m_values[id];
185c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
186c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
1877faaa9f3f0df9d23790277834d426c3d992ac3baCarlos Hernandez    void prune(const Scalar& reference, const RealScalar& epsilon = NumTraits<RealScalar>::dummy_precision())
188c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
189c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      size_t k = 0;
190c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      size_t n = size();
191c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      for (size_t i=0; i<n; ++i)
192c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      {
193c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        if (!internal::isMuchSmallerThan(value(i), reference, epsilon))
194c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        {
195c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          value(k) = value(i);
196c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          index(k) = index(i);
197c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath          ++k;
198c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath        }
199c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      }
200c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      resize(k,0);
201c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
202c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
203c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  protected:
204c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
205c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    inline void reallocate(size_t size)
206c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    {
207c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      Scalar* newValues  = new Scalar[size];
208c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      Index* newIndices = new Index[size];
209c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      size_t copySize = (std::min)(size, m_size);
210c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      // copy
211c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      internal::smart_copy(m_values, m_values+copySize, newValues);
212c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      internal::smart_copy(m_indices, m_indices+copySize, newIndices);
213c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      // delete old stuff
214c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      delete[] m_values;
215c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      delete[] m_indices;
216c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      m_values = newValues;
217c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      m_indices = newIndices;
218c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath      m_allocatedSize = size;
219c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    }
220c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
221c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath  protected:
222c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    Scalar* m_values;
223c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    Index* m_indices;
224c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    size_t m_size;
225c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath    size_t m_allocatedSize;
226c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
227c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath};
228c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
229c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} // end namespace internal
230c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
231c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath} // end namespace Eigen
232c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath
233c981c48f5bc9aefeffc0bcb0cc3934c2fae179ddNarayan Kamath#endif // EIGEN_COMPRESSED_STORAGE_H
234