michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2011, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street, 
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the 
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: #pragma once
michael@0: #include <iterator>
michael@0: #include <utility>
michael@0: 
michael@0: #include "inc/Main.h"
michael@0: 
michael@0: namespace graphite2 {
michael@0: 
michael@0: 
michael@0: // A read-only packed fast sparse array of uint16 with uint16 keys.
michael@0: // Like most container classes this has capacity and size properties and these
michael@0: // refer to the number of stored entries and the number of addressable entries
michael@0: // as normal. However due the sparse nature the capacity is always <= than the
michael@0: // size.
michael@0: class sparse
michael@0: {
michael@0: public:
michael@0:     typedef uint16  key_type;
michael@0:     typedef uint16  mapped_type;
michael@0:     typedef std::pair<const key_type, mapped_type> value_type;
michael@0: 
michael@0: private:
michael@0:     typedef unsigned long   mask_t;
michael@0: 
michael@0:     static const unsigned char  SIZEOF_CHUNK = (sizeof(mask_t) - sizeof(key_type))*8;
michael@0: 
michael@0:     struct chunk
michael@0:     {
michael@0:         mask_t          mask:SIZEOF_CHUNK;
michael@0:         key_type        offset;
michael@0:     };
michael@0: 
michael@0:     static chunk  empty_chunk;
michael@0:     sparse(const sparse &);
michael@0:     sparse & operator = (const sparse &);
michael@0: 
michael@0: public:
michael@0:     template<typename I>
michael@0:     sparse(I first, const I last);
michael@0:     sparse() throw();
michael@0:     ~sparse() throw();
michael@0: 
michael@0:     operator bool () const throw();
michael@0:     mapped_type     operator [] (const key_type k) const throw();
michael@0: 
michael@0:     size_t capacity() const throw();
michael@0:     size_t size()     const throw();
michael@0: 
michael@0:     size_t _sizeof() const throw();
michael@0:     
michael@0:     CLASS_NEW_DELETE;
michael@0: 
michael@0: private:
michael@0:     union {
michael@0:         chunk         * map;
michael@0:         mapped_type   * values;
michael@0:     }           m_array;
michael@0:     key_type    m_nchunks;
michael@0: };
michael@0: 
michael@0: 
michael@0: inline
michael@0: sparse::sparse() throw() : m_nchunks(0)
michael@0: {
michael@0:     m_array.map = &empty_chunk;
michael@0: }
michael@0: 
michael@0: 
michael@0: template <typename I>
michael@0: sparse::sparse(I attr, const I last)
michael@0: : m_nchunks(0)
michael@0: {
michael@0:     m_array.map = 0;
michael@0: 
michael@0:     // Find the maximum extent of the key space.
michael@0:     size_t n_values=0;
michael@0:     long lastkey = -1;
michael@0:     for (I i = attr; i != last; ++i, ++n_values)
michael@0:     {
michael@0:         const typename std::iterator_traits<I>::value_type v = *i;
michael@0:         if (v.second == 0)      { --n_values; continue; }
michael@0:         if (v.first <= lastkey) { m_nchunks = 0; return; }
michael@0: 
michael@0:         lastkey = v.first;
michael@0:         const key_type k = v.first / SIZEOF_CHUNK;
michael@0:         if (k >= m_nchunks) m_nchunks = k+1;
michael@0:     }
michael@0:     if (m_nchunks == 0)
michael@0:     {
michael@0:         m_array.map=&empty_chunk;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     m_array.values = grzeroalloc<mapped_type>((m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)
michael@0:                                                  / sizeof(mapped_type)
michael@0:                                                  + n_values);
michael@0: 
michael@0:     if (m_array.values == 0)
michael@0:     {
michael@0:         free(m_array.values); m_array.map=0;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     chunk * ci = m_array.map;
michael@0:     ci->offset = (m_nchunks*sizeof(chunk) + sizeof(mapped_type)-1)/sizeof(mapped_type);
michael@0:     mapped_type * vi = m_array.values + ci->offset;
michael@0:     for (; attr != last; ++attr, ++vi)
michael@0:     {
michael@0:         const typename std::iterator_traits<I>::value_type v = *attr;
michael@0:         if (v.second == 0)  { --vi; continue; }
michael@0: 
michael@0:         chunk * const ci_ = m_array.map + v.first/SIZEOF_CHUNK;
michael@0: 
michael@0:         if (ci != ci_)
michael@0:         {
michael@0:             ci = ci_;
michael@0:             ci->offset = vi - m_array.values;
michael@0:         }
michael@0: 
michael@0:         ci->mask |= 1UL << (SIZEOF_CHUNK - 1 - (v.first % SIZEOF_CHUNK));
michael@0:         *vi = v.second;
michael@0:     }
michael@0: }
michael@0: 
michael@0: 
michael@0: inline
michael@0: sparse::operator bool () const throw()
michael@0: {
michael@0:     return m_array.map != 0;
michael@0: }
michael@0: 
michael@0: inline
michael@0: size_t sparse::size() const throw()
michael@0: {
michael@0:     return m_nchunks*SIZEOF_CHUNK;
michael@0: }
michael@0: 
michael@0: inline
michael@0: size_t sparse::_sizeof() const throw()
michael@0: {
michael@0:     return sizeof(sparse) + capacity()*sizeof(mapped_type) + m_nchunks*sizeof(chunk);
michael@0: }
michael@0: 
michael@0: } // namespace graphite2