BitMagic-C++
bmsparsevec.h
Go to the documentation of this file.
1#ifndef BMSPARSEVEC_H__INCLUDED__
2#define BMSPARSEVEC_H__INCLUDED__
3/*
4Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5
6Licensed under the Apache License, Version 2.0 (the "License");
7you may not use this file except in compliance with the License.
8You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12Unless required by applicable law or agreed to in writing, software
13distributed under the License is distributed on an "AS IS" BASIS,
14WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15See the License for the specific language governing permissions and
16limitations under the License.
17
18For more information please visit: http://bitmagic.io
19*/
20
21/*! \file bmsparsevec.h
22 \brief Sparse constainer sparse_vector<> for integer types using
23 bit-transposition transform
24*/
25
26#include <memory.h>
27
28#ifndef BM_NO_STL
29#include <stdexcept>
30#endif
31
32#ifndef BM__H__INCLUDED__
33// BitMagic utility headers do not include main "bm.h" declaration
34// #include "bm.h" or "bm64.h" explicitly
35# error missing include (bm.h or bm64.h)
36#endif
37
38
39#include "bmtrans.h"
40#include "bmalgo_impl.h"
41#include "bmbuffer.h"
42#include "bmbmatrix.h"
43#include "bmdef.h"
44
45namespace bm
46{
47
48/** \defgroup svector Sparse and compressed vectors
49 Sparse vector for integer types using bit transposition transform
50
51 @ingroup bmagic
52 */
53
54
55/** \defgroup sv sparse_vector<>
56 Sparse vector for integer types using bit transposition transform
57
58 @ingroup bmagic
59 */
60
61
62/*!
63 \brief sparse vector with runtime compression using bit transposition method
64
65 Sparse vector implements variable bit-depth storage model.
66 Initial data is bit-transposed into bit-planes so each element
67 may use less memory than the original native data type prescribes.
68 For example, 32-bit integer may only use 20 bits.
69
70 Another level of compression is provided by bit-vector (BV template parameter)
71 used for storing bit planes. bvector<> implements varians of on the fly block
72 compression, so if a significant area of a sparse vector uses less bits - it
73 will save memory.
74
75 Overall it provides variable bit-depth compression, sparse compression in
76 bit-plains.
77
78 @ingroup sv
79*/
80template<class Val, class BV>
81class sparse_vector : public base_sparse_vector<Val, BV, 1>
82{
83public:
84 typedef Val value_type;
85 typedef BV bvector_type;
91 typedef typename BV::allocator_type allocator_type;
94 typedef typename allocator_type::allocator_pool_type allocator_pool_type;
97
98
99 /*! Statistical information about memory allocation details. */
100 struct statistics : public bv_statistics
101 {};
102
103 /*! Traits and features used in algorithms to correctly run
104 on a particular type of sparse vector
105 */
106 struct is_remap_support { enum trait { value = false }; };
107 struct is_rsc_support { enum trait { value = false }; };
108
109 /**
110 Reference class to access elements via common [] operator
111 @ingroup sv
112 */
114 {
115 public:
117 : sv_(sv), idx_(idx)
118 {}
119 operator value_type() const BMNOEXCEPT { return sv_.get(idx_); }
121 {
122 sv_.set(idx_, (value_type)ref);
123 return *this;
124 }
126 {
127 sv_.set(idx_, val);
128 return *this;
129 }
130 bool operator==(const reference& ref) const BMNOEXCEPT
131 { return bool(*this) == bool(ref); }
132 bool is_null() const BMNOEXCEPT { return sv_.is_null(idx_); }
133 private:
135 size_type idx_;
136 };
137
138
139 /**
140 Const iterator to traverse the sparse vector.
141
142 Implementation uses buffer for decoding so, competing changes
143 to the original vector may not match the iterator returned values.
144
145 This iterator keeps an operational buffer for 8K elements,
146 so memory footprint is not negligable (about 64K for unsigned int)
147
148 @ingroup sv
149 */
151 {
152 public:
153 friend class sparse_vector;
154
155#ifndef BM_NO_STL
156 typedef std::input_iterator_tag iterator_category;
157#endif
165 typedef bm::byte_buffer<allocator_type> buffer_type;
166
167 typedef unsigned difference_type;
168 typedef unsigned* pointer;
170
171 public:
176
177 bool operator==(const const_iterator& it) const BMNOEXCEPT
178 { return (pos_ == it.pos_) && (sv_ == it.sv_); }
180 { return ! operator==(it); }
182 { return pos_ < it.pos_; }
184 { return pos_ <= it.pos_; }
186 { return pos_ > it.pos_; }
188 { return pos_ >= it.pos_; }
189
190 /// \brief Get current position (value)
191 value_type operator*() const { return this->value(); }
192
193
194 /// \brief Advance to the next available value
195 const_iterator& operator++() BMNOEXCEPT { this->advance(); return *this; }
196
197 /// \brief Advance to the next available value
199 { const_iterator tmp(*this);this->advance(); return tmp; }
200
201
202 /// \brief Get current position (value)
204
205 /// \brief Get NULL status
206 bool is_null() const BMNOEXCEPT;
207
208 /// Returns true if iterator is at a valid position
209 bool valid() const BMNOEXCEPT { return pos_ != bm::id_max; }
210
211 /// Invalidate current iterator
213
214 /// Current position (index) in the vector
215 size_type pos() const BMNOEXCEPT{ return pos_; }
216
217 /// re-position to a specified position
219
220 /// advance iterator forward by one
221 /// @return true if it is still valid
223
225 private:
226 enum buf_size_e
227 {
228 n_buf_size = 1024 * 8
229 };
230
231 private:
232 const sparse_vector_type* sv_; ///!< ptr to parent
233 size_type pos_; ///!< Position
234 mutable buffer_type buffer_; ///!< value buffer
235 mutable value_type* buf_ptr_; ///!< position in the buffer
236 };
237
238 /**
239 Back insert iterator implements buffered insert, faster than generic
240 access assignment.
241
242 Limitations for buffered inserter:
243 1. Do not use more than one inserter per vector at a time
244 2. Use method flush() at the end to send the rest of accumulated buffer
245 flush is happening automatically on destruction, but if flush produces an
246 exception (for whatever reason) it will be an exception in destructor.
247 As such, explicit flush() is safer way to finilize the sparse vector load.
248
249 @ingroup sv
250 */
252 {
253 public:
254#ifndef BM_NO_STL
255 typedef std::output_iterator_tag iterator_category;
256#endif
264 typedef bm::byte_buffer<allocator_type> buffer_type;
265
266 typedef void difference_type;
267 typedef void pointer;
268 typedef void reference;
269
270 public:
274
276 {
277 BM_ASSERT(bi.empty());
278 this->flush(); sv_ = bi.sv_; bv_null_ = bi. bv_null_;
279 return *this;
280 }
281
283
284 /** push value to the vector */
285 back_insert_iterator& operator=(value_type v) { this->add(v); return *this; }
286 /** noop */
287 back_insert_iterator& operator*() { return *this; }
288 /** noop */
289 back_insert_iterator& operator++() { return *this; }
290 /** noop */
291 back_insert_iterator& operator++( int ) { return *this; }
292
293 /** add value to the container*/
295
296 /** add NULL (no-value) to the container */
297 void add_null();
298
299 /** add a series of consequitve NULLs (no-value) to the container */
300 void add_null(size_type count);
301
302 /** return true if insertion buffer is empty */
303 bool empty() const;
304
305 /** flush the accumulated buffer */
306 void flush();
307
308 // ---------------------------------------------------------------
309 // open internals
310 // (TODO: create proper friend declarations)
311 //
312 /**
313 Get access to not-null vector
314 @internal
315 */
316 bvector_type* get_null_bvect() const BMNOEXCEPT { return bv_null_; }
317
318 /** add value to the buffer without changing the NULL vector
319 @param v - value to push back
320 @return index of added value in the internal buffer
321 @internal
322 */
324
325 /**
326 Reconfшпгку back inserter not to touch the NULL vector
327 */
328 void disable_set_null() BMNOEXCEPT { set_not_null_ = false; }
329 // ---------------------------------------------------------------
330
331 protected:
333 private:
334 enum buf_size_e
335 {
336 n_buf_size = 1024 * 8
337 };
338
339 private:
340 bm::sparse_vector<Val, BV>* sv_; ///!< pointer on the parent vector
341 bvector_type* bv_null_; ///!< not NULL vector pointer
342 buffer_type buffer_; ///!< value buffer
343 value_type* buf_ptr_; ///!< position in the buffer
344 block_idx_type prev_nb_; ///!< previous block added
345 bool set_not_null_;
346 };
347
350
351public:
352 // ------------------------------------------------------------
353 /*! @name Construction and assignment */
354 ///@{
355
356 /*!
357 \brief Sparse vector constructor
358
359 \param null_able - defines if vector supports NULL values flag
360 by default it is OFF, use bm::use_null to enable it
361 \param ap - allocation strategy for underlying bit-vectors
362 Default allocation policy uses BM_BIT setting (fastest access)
363 \param bv_max_size - maximum possible size of underlying bit-vectors
364 Please note, this is NOT size of svector itself, it is dynamic upper limit
365 which should be used very carefully if we surely know the ultimate size
366 \param alloc - allocator for bit-vectors
367
368 \sa bvector<>
369 \sa bm::bvector<>::allocation_policy
370 \sa bm::startegy
371 */
374 size_type bv_max_size = bm::id_max,
375 const allocator_type& alloc = allocator_type());
376
377 /*! copy-ctor */
379
380 /*! copy assignmment operator */
382 {
383 if (this != &sv)
385 return *this;
386 }
387
388#ifndef BM_NO_CXX11
389 /*! move-ctor */
391
392
393 /*! move assignmment operator */
395 {
396 if (this != &sv)
397 {
398 clear();
399 swap(sv);
400 }
401 return *this;
402 }
403#endif
404
406 ///@}
407
408
409 // ------------------------------------------------------------
410 /*! @name Element access */
411 ///@{
412
413 /** \brief Operator to get write access to an element */
415 { return reference(*this, idx); }
416
417 /*!
418 \brief get specified element without bounds checking
419 \param idx - element index
420 \return value of the element
421 */
423 { return this->get(idx); }
424
425 /*!
426 \brief access specified element with bounds checking
427 \param idx - element index
428 \return value of the element
429 */
431 /*!
432 \brief get specified element without bounds checking
433 \param idx - element index
434 \return value of the element
435 */
437
438 /*!
439 \brief set specified element with bounds checking and automatic resize
440 \param idx - element index
441 \param v - element value
442 */
444
445 /*!
446 \brief increment specified element by one
447 \param idx - element index
448 */
449 void inc(size_type idx);
450
451 /*!
452 \brief push value back into vector
453 \param v - element value
454 */
456
457 /*!
458 \brief push back specified amount of NULL values
459 \param count - number of NULLs to push back
460 */
462
463 /*!
464 \brief insert specified element into container
465 \param idx - element index
466 \param v - element value
467 */
469
470 /*!
471 \brief erase specified element from container
472 \param idx - element index
473 */
474 void erase(size_type idx);
475
476 /*!
477 \brief clear specified element with bounds checking and automatic resize
478 \param idx - element index
479 \param set_null - if true the value receives NULL (unassigned) value
480 */
481 void clear(size_type idx, bool set_null = false);
482
483 ///@}
484
485 // ------------------------------------------------------------
486 /*! @name Iterator access */
487 //@{
488
489 /** Provide const iterator access to container content */
490 const_iterator begin() const BMNOEXCEPT;
491
492 /** Provide const iterator access to the end */
494 { return const_iterator(this, bm::id_max); }
495
496 /** Get const_itertor re-positioned to specific element
497 @param idx - position in the sparse vector
498 */
501
502 /** Provide back insert iterator
503 Back insert iterator implements buffered insertion,
504 which is faster, than random access or push_back
505 */
508 ///@}
509
510
511 // ------------------------------------------------------------
512 /*! @name Various traits */
513 //@{
514
515 /** \brief set specified element to unassigned value (NULL)
516 \param idx - element index
517 */
519
520 /** \brief trait if sparse vector is "compressed" (false)
521 */
522 static
523 bool is_compressed() BMNOEXCEPT { return false; }
524
525 ///@}
526
527
528 // ------------------------------------------------------------
529 /*! @name Loading of sparse vector from C-style array */
530 //@{
531
532 /*!
533 \brief Import list of elements from a C-style array
534 \param arr - source array
535 \param arr_size - source size
536 \param offset - target index in the sparse vector
537 \param set_not_null - import should register in not null vector
538 */
539 void import(const value_type* arr,
540 size_type arr_size,
541 size_type offset = 0,
542 bool set_not_null = true);
543
544 /*!
545 \brief Import list of elements from a C-style array (pushed back)
546 \param arr - source array
547 \param arr_size - source array size
548 \param set_not_null - import should register in not null vector
549 */
550 void import_back(const value_type* arr,
551 size_type arr_size,
552 bool set_not_null = true);
553 ///@}
554
555 // ------------------------------------------------------------
556 /*! @name Export content to C-style array */
557 ///@{
558
559 /*!
560 \brief Bulk export list of elements to a C-style array
561
562 For efficiency, this is left as a low level function,
563 it does not do any bounds checking on the target array, it will
564 override memory and crash if you are not careful with allocation
565 and request size.
566
567 \param arr - dest array
568 \param idx_from - index in the sparse vector to export from
569 \param dec_size - decoding size (array allocation should match)
570 \param zero_mem - set to false if target array is pre-initialized
571 with 0s to avoid performance penalty
572
573 \return number of actually exported elements (can be less than requested)
574
575 \sa gather
576 */
578 size_type idx_from,
579 size_type dec_size,
580 bool zero_mem = true) const;
581
582
583 /*!
584 \brief Gather elements to a C-style array
585
586 Gather collects values from different locations, for best
587 performance feed it with sorted list of indexes.
588
589 Faster than one-by-one random access.
590
591 For efficiency, this is left as a low level function,
592 it does not do any bounds checking on the target array, it will
593 override memory and crash if you are not careful with allocation
594 and request size.
595
596 \param arr - dest array
597 \param idx - index list to gather elements
598 \param size - decoding index list size (array allocation should match)
599 \param sorted_idx - sort order directive for the idx array
600 (BM_UNSORTED, BM_SORTED, BM_UNKNOWN)
601 Sort order affects both performance and correctness(!), use BM_UNKNOWN
602 if not sure.
603
604 \return number of actually exported elements (can be less than requested)
605
606 \sa decode
607 */
609 const size_type* idx,
611 bm::sort_order sorted_idx) const;
612 ///@}
613
614 /*! \brief content exchange
615 */
617
618 // ------------------------------------------------------------
619 /*! @name Clear */
620 ///@{
621
622 /*! \brief resize to zero, free memory */
624
625 /*!
626 \brief clear range (assign bit 0 for all plains)
627 \param left - interval start
628 \param right - interval end (closed interval)
629 \param set_null - set cleared values to unassigned (NULL)
630 */
632 size_type right,
633 bool set_null = false);
634
635 ///@}
636
637 // ------------------------------------------------------------
638 /*! @name Size, etc */
639 ///@{
640
641 /*! \brief return size of the vector
642 \return size of sparse vector
643 */
644 size_type size() const BMNOEXCEPT { return this->size_; }
645
646 /*! \brief return true if vector is empty
647 \return true if empty
648 */
649 bool empty() const BMNOEXCEPT { return (size() == 0); }
650
651 /*! \brief resize vector
652 \param sz - new size
653 */
655 ///@}
656
657 // ------------------------------------------------------------
658 /*! @name Comparison */
659 ///@{
660
661 /*!
662 \brief check if another sparse vector has the same content and size
663
664 \param sv - sparse vector for comparison
665 \param null_able - flag to consider NULL vector in comparison (default)
666 or compare only value content plains
667
668 \return true, if it is the same
669 */
671 bm::null_support null_able = bm::use_null) const BMNOEXCEPT;
672
673 ///@}
674
675 // ------------------------------------------------------------
676 /*! @name Element comparison */
677 ///@{
678
679 /**
680 \brief Compare vector element with argument
681
682 \param idx - vactor element index
683 \param val - argument to compare with
684
685 \return 0 - equal, < 0 - vect[i] < str, >0 otherwise
686 */
687 int compare(size_type idx, const value_type val) const BMNOEXCEPT;
688
689 ///@}
690
691 // ------------------------------------------------------------
692 /*! @name Memory optimization */
693 ///@{
694
695 /*!
696 \brief run memory optimization for all vector plains
697 \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
698 \param opt_mode - requested compression depth
699 \param stat - memory allocation statistics after optimization
700 */
701 void optimize(bm::word_t* temp_block = 0,
703 typename sparse_vector<Val, BV>::statistics* stat = 0);
704
705 /*!
706 \brief Optimize sizes of GAP blocks
707
708 This method runs an analysis to find optimal GAP levels for all bit plains
709 of the vector.
710 */
712
713 /*!
714 @brief Calculates memory statistics.
715
716 Function fills statistics structure containing information about how
717 this vector uses memory and estimation of max. amount of memory
718 bvector needs to serialize itself.
719
720 @param st - pointer on statistics structure to be filled in.
721
722 @sa statistics
723 */
726 ///@}
727
728 // ------------------------------------------------------------
729 /*! @name Merge, split, partition data */
730 ///@{
731
732 /*!
733 \brief join all with another sparse vector using OR operation
734 \param sv - argument vector to join with
735 \return slf reference
736 @sa merge
737 */
739
740 /*!
741 \brief merge with another sparse vector using OR operation
742 Merge is different from join(), because it borrows data from the source
743 vector, so it gets modified.
744
745 \param sv - [in, out]argument vector to join with (vector mutates)
746
747 \return slf reference
748 @sa join
749 */
751
752
753 /**
754 @brief copy range of values from another sparse vector
755
756 Copy [left..right] values from the source vector,
757 clear everything outside the range.
758
759 \param sv - source vector
760 \param left - index from in losed diapason of [left..right]
761 \param right - index to in losed diapason of [left..right]
762 \param splice_null - "use_null" copy range for NULL vector or
763 do not copy it
764 */
766 size_type left, size_type right,
767 bm::null_support splice_null = bm::use_null);
768
769 /**
770 @brief Apply value filter, defined by mask vector
771
772 All bit-plains are ANDed against the filter mask.
773 */
774 void filter(const bvector_type& bv_mask);
775
776 ///@}
777
778
779 // ------------------------------------------------------------
780 /*! @name Access to internals */
781 ///@{
782
783
784 /*! \brief syncronize internal structures */
785 void sync(bool /*force*/) {}
786
787
788 /*!
789 \brief Bulk export list of elements to a C-style array
790
791 Use of all extract() methods is restricted.
792 Please consider decode() for the same purpose.
793
794 \param arr - dest array
795 \param size - dest size
796 \param offset - target index in the sparse vector to export from
797 \param zero_mem - set to false if target array is pre-initialized
798 with 0s to avoid performance penalty
799 \return number of exported elements
800
801 \sa decode
802
803 @internal
804 */
807 size_type offset = 0,
808 bool zero_mem = true) const BMNOEXCEPT2;
809
810 /** \brief extract small window without use of masking vector
811 \sa decode
812 @internal
813 */
816 size_type offset,
817 bool zero_mem = true) const;
818
819 /** \brief extract medium window without use of masking vector
820 \sa decode
821 @internal
822 */
825 size_type offset,
826 bool zero_mem = true) const;
827
828 /** \brief address translation for this type of container
829 \internal
830 */
831 static
833
834 /**
835 \brief throw range error
836 \internal
837 */
838 static
839 void throw_range_error(const char* err_msg);
840
841 /**
842 \brief throw bad alloc
843 \internal
844 */
845 static
847
848
849 /**
850 \brief find position of compressed element by its rank
851 */
852 static
854
855 /**
856 \brief size of sparse vector (may be different for RSC)
857 */
859
860 /**
861 \brief Always 1 (non-matrix type)
862 */
864
865 ///@}
866
867 /// Set allocator pool for local (non-threaded)
868 /// memory cyclic(lots of alloc-free ops) opertations
869 ///
871
872protected:
874 {
876 };
877
878
879 /*! \brief set value without checking boundaries */
881
882 /*! \brief set value without checking boundaries or support of NULL */
884
885 /*! \brief push value back into vector without NULL semantics */
887
888 /*! \brief insert value without checking boundaries */
890 /*! \brief insert value without checking boundaries or support of NULL */
892
895
896 bool is_remap() const BMNOEXCEPT { return false; }
897 size_t remap_size() const BMNOEXCEPT { return 0; }
898 const unsigned char* get_remap_buffer() const BMNOEXCEPT { return 0; }
899 unsigned char* init_remap_buffer() BMNOEXCEPT { return 0; }
901
903 size_type* idx_from, size_type* idx_to) const BMNOEXCEPT
904 {
905 *idx_from = from; *idx_to = to; return true;
906 }
907
908protected:
909 template<class V, class SV> friend class rsc_sparse_vector;
910 template<class SVect> friend class sparse_vector_scanner;
911 template<class SVect> friend class sparse_vector_serializer;
912 template<class SVect> friend class sparse_vector_deserializer;
913
914};
915
916
917//---------------------------------------------------------------------
918//---------------------------------------------------------------------
919
920
921template<class Val, class BV>
923 bm::null_support null_able,
925 size_type bv_max_size,
926 const allocator_type& alloc)
927: parent_type(null_able, ap, bv_max_size, alloc)
928{}
929
930//---------------------------------------------------------------------
931
932template<class Val, class BV>
936
937//---------------------------------------------------------------------
938#ifndef BM_NO_CXX11
939
940template<class Val, class BV>
945
946#endif
947
948
949//---------------------------------------------------------------------
950
951template<class Val, class BV>
954
955//---------------------------------------------------------------------
956
957template<class Val, class BV>
959{
960 parent_type::swap(sv);
961}
962
963//---------------------------------------------------------------------
964
965template<class Val, class BV>
967{
968#ifndef BM_NO_STL
969 throw std::range_error(err_msg);
970#else
971 BM_ASSERT_THROW(false, BM_ERR_RANGE);
972#endif
973}
974
975//---------------------------------------------------------------------
976
977template<class Val, class BV>
979{
980 BV::throw_bad_alloc();
981}
982
983//---------------------------------------------------------------------
984
985template<class Val, class BV>
987{
988 clear(idx, true);
989}
990
991//---------------------------------------------------------------------
992
993template<class Val, class BV>
995 size_type arr_size,
996 size_type offset,
997 bool set_not_null)
998{
999 unsigned char b_list[sizeof(Val)*8];
1000 unsigned row_len[sizeof(Val)*8] = {0, };
1001
1002 const unsigned transpose_window = 256;
1003 bm::tmatrix<size_type, sizeof(Val)*8, transpose_window> tm; // matrix accumulator
1004
1005 if (arr_size == 0)
1006 throw_range_error("sparse_vector range error (import size 0)");
1007
1008 if (offset < this->size_) // in case it touches existing elements
1009 {
1010 // clear all plains in the range to provide corrrect import of 0 values
1011 this->clear_range(offset, offset + arr_size - 1);
1012 }
1013
1014 // transposition algorithm uses bitscan to find index bits and store it
1015 // in temporary matrix (list for each bit plain), matrix here works
1016 // when array gets to big - the list gets loaded into bit-vector using
1017 // bulk load algorithm, which is faster than single bit access
1018 //
1019
1020 size_type i;
1021 for (i = 0; i < arr_size; ++i)
1022 {
1023 unsigned bcnt = bm::bitscan(arr[i], b_list);
1024 const size_type bit_idx = i + offset;
1025
1026 for (unsigned j = 0; j < bcnt; ++j)
1027 {
1028 unsigned p = b_list[j];
1029 unsigned rl = row_len[p];
1030 tm.row(p)[rl] = bit_idx;
1031 row_len[p] = ++rl;
1032
1033 if (rl == transpose_window)
1034 {
1035 bvector_type* bv = this->get_plain(p);
1036 const size_type* r = tm.row(p);
1037 bv->set(r, rl, BM_SORTED);
1038 row_len[p] = 0;
1039 tm.row(p)[0] = 0;
1040 }
1041 } // for j
1042 } // for i
1043
1044 // process incomplete transposition lines
1045 //
1046 for (unsigned k = 0; k < tm.rows(); ++k)
1047 {
1048 unsigned rl = row_len[k];
1049 if (rl)
1050 {
1051 bvector_type* bv = this->get_plain(k);
1052 const size_type* r = tm.row(k);
1053 bv->set(r, rl, BM_SORTED);
1054 }
1055 } // for k
1056
1057
1058 if (i + offset > this->size_)
1059 this->size_ = i + offset;
1060
1061 if (set_not_null)
1062 {
1063 bvector_type* bv_null = this->get_null_bvect();
1064 if (bv_null) // configured to support NULL assignments
1065 bv_null->set_range(offset, offset + arr_size - 1);
1066 }
1067}
1068
1069//---------------------------------------------------------------------
1070
1071template<class Val, class BV>
1073 size_type arr_size,
1074 bool set_not_null)
1075{
1076 this->import(arr, arr_size, this->size(), set_not_null);
1077}
1078
1079//---------------------------------------------------------------------
1080
1081template<class Val, class BV>
1084 size_type idx_from,
1085 size_type dec_size,
1086 bool zero_mem) const
1087{
1088 return extract(arr, dec_size, idx_from, zero_mem);
1089}
1090
1091//---------------------------------------------------------------------
1092
1093template<class Val, class BV>
1096 const size_type* idx,
1097 size_type size,
1098 bm::sort_order sorted_idx) const
1099{
1100 BM_ASSERT(arr);
1101 BM_ASSERT(idx);
1102 BM_ASSERT(size);
1103
1104 if (size == 1) // corner case: get 1 value
1105 {
1106 arr[0] = this->get(idx[0]);
1107 return size;
1108 }
1109 ::memset(arr, 0, sizeof(value_type)*size);
1110
1111 for (size_type i = 0; i < size;)
1112 {
1113 bool sorted_block = true;
1114
1115 // look ahead for the depth of the same block
1116 // (speculate more than one index lookup per block)
1117 //
1118 block_idx_type nb = (idx[i] >> bm::set_block_shift);
1119 size_type r = i;
1120
1121 switch (sorted_idx)
1122 {
1123 case BM_UNKNOWN:
1124 {
1125 size_type idx_prev = idx[r];
1126 for (; (r < size) && (nb == (idx[r] >> bm::set_block_shift)); ++r)
1127 {
1128 sorted_block = !(idx[r] < idx_prev); // sorted check
1129 idx_prev = idx[r];
1130 }
1131 }
1132 break;
1133 case BM_UNSORTED:
1134 sorted_block = false;
1135 for (; r < size; ++r)
1136 {
1137 block_idx_type nb_next = (idx[r] >> bm::set_block_shift);
1138 if (nb != nb_next)
1139 break;
1140 } // for r
1141 break;
1142 // no break(!) intentional fall through
1143 case BM_SORTED:
1144 #ifdef BM64ADDR
1145 r = bm::idx_arr_block_lookup_u64(idx, size, nb, r);
1146 #else
1147 r = bm::idx_arr_block_lookup_u32(idx, size, nb, r);
1148 #endif
1149 break;
1150 case BM_SORTED_UNIFORM:
1151 r = size;
1152 break;
1153 default:
1154 BM_ASSERT(0);
1155 } // switch
1156
1157 // single element hit, use plain random access
1158 if (r == i+1)
1159 {
1160 arr[i] = this->get(idx[i]);
1161 ++i;
1162 continue;
1163 }
1164
1165 // process block co-located elements at ones for best (CPU cache opt)
1166 //
1167 unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1168 unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1169
1170 unsigned eff_plains = this->effective_plains(); // TODO: get real effective plains for [i,j]
1171 for (unsigned j = 0; j < eff_plains; ++j)
1172 {
1173 const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1174 if (!blk)
1175 continue;
1176 value_type vm;
1177 const value_type mask1 = 1;
1178
1179 if (blk == FULL_BLOCK_FAKE_ADDR)
1180 {
1181 vm = (mask1 << j);
1182 for (size_type k = i; k < r; ++k)
1183 arr[k] |= vm;
1184 continue;
1185 }
1186 if (BM_IS_GAP(blk))
1187 {
1188 const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1189 unsigned is_set;
1190
1191 if (sorted_block) // b-search hybrid with scan lookup
1192 {
1193 for (size_type k = i; k < r; )
1194 {
1195 unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1196
1197 unsigned gidx = bm::gap_bfind(gap_blk, nbit, &is_set);
1198 unsigned gap_value = gap_blk[gidx];
1199 if (is_set)
1200 {
1201 arr[k] |= vm = (mask1 << j);
1202 for (++k; k < r; ++k) // speculative look-up
1203 {
1204 if (unsigned(idx[k] & bm::set_block_mask) <= gap_value)
1205 arr[k] |= vm;
1206 else
1207 break;
1208 }
1209 }
1210 else // 0 GAP - skip. not set
1211 {
1212 for (++k;
1213 (k < r) &&
1214 (unsigned(idx[k] & bm::set_block_mask) <= gap_value);
1215 ++k) {}
1216 }
1217 } // for k
1218 }
1219 else // unsorted block gather request: b-search lookup
1220 {
1221 for (size_type k = i; k < r; ++k)
1222 {
1223 unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1224 is_set = bm::gap_test_unr(gap_blk, nbit);
1225 arr[k] |= (value_type(bool(is_set)) << j);
1226 } // for k
1227 }
1228 continue;
1229 }
1230 bm::bit_block_gather_scatter(arr, blk, idx, r, i, j);
1231 } // for (each plain)
1232
1233 i = r;
1234
1235 } // for i
1236
1237 return size;
1238}
1239
1240//---------------------------------------------------------------------
1241
1242template<class Val, class BV>
1245 size_type size,
1246 size_type offset,
1247 bool zero_mem) const
1248{
1249 if (size == 0)
1250 return 0;
1251 if (zero_mem)
1252 ::memset(arr, 0, sizeof(value_type)*size);
1253
1254 size_type start = offset;
1255 size_type end = start + size;
1256 if (end > this->size_)
1257 {
1258 end = this->size_;
1259 }
1260
1261 // calculate logical block coordinates and masks
1262 //
1263 block_idx_type nb = (start >> bm::set_block_shift);
1264 unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1265 unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1266 unsigned nbit = unsigned(start & bm::set_block_mask);
1267 unsigned nword = unsigned(nbit >> bm::set_word_shift);
1268 unsigned mask0 = 1u << (nbit & bm::set_word_mask);
1269 const bm::word_t* blk = 0;
1270 unsigned is_set;
1271
1272 for (unsigned j = 0; j < sizeof(Val)*8; ++j)
1273 {
1274 blk = this->bmatr_.get_block(j, i0, j0);
1275 bool is_gap = BM_IS_GAP(blk);
1276
1277 for (size_type k = start; k < end; ++k)
1278 {
1280 if (nb1 != nb) // block switch boundaries
1281 {
1282 nb = nb1;
1283 i0 = unsigned(nb >> bm::set_array_shift);
1284 j0 = unsigned(nb & bm::set_array_mask);
1285 blk = this->bmatr_.get_block(j, i0, j0);
1286 is_gap = BM_IS_GAP(blk);
1287 }
1288 if (!blk)
1289 continue;
1290 nbit = unsigned(k & bm::set_block_mask);
1291 if (is_gap)
1292 {
1293 is_set = bm::gap_test_unr(BMGAP_PTR(blk), nbit);
1294 }
1295 else
1296 {
1297 if (blk == FULL_BLOCK_FAKE_ADDR)
1298 {
1299 is_set = 1;
1300 }
1301 else
1302 {
1303 BM_ASSERT(!IS_FULL_BLOCK(blk));
1304 nword = unsigned(nbit >> bm::set_word_shift);
1305 mask0 = 1u << (nbit & bm::set_word_mask);
1306 is_set = (blk[nword] & mask0);
1307 }
1308 }
1309 size_type idx = k - offset;
1310 value_type vm = (bool) is_set;
1311 vm <<= j;
1312 arr[idx] |= vm;
1313
1314 } // for k
1315
1316 } // for j
1317 return 0;
1318}
1319
1320//---------------------------------------------------------------------
1321
1322template<class Val, class BV>
1325 size_type size,
1326 size_type offset,
1327 bool zero_mem) const
1328{
1329 if (size == 0)
1330 return 0;
1331
1332 if (zero_mem)
1333 ::memset(arr, 0, sizeof(value_type)*size);
1334
1335 size_type start = offset;
1336 size_type end = start + size;
1337 if (end > this->size_)
1338 {
1339 end = this->size_;
1340 }
1341
1342 for (size_type i = 0; i < parent_type::value_bits(); ++i)
1343 {
1344 const bvector_type* bv = this->bmatr_.get_row(i);
1345 if (!bv)
1346 continue;
1347
1348 value_type mask = 1;
1349 mask <<= i;
1350 typename BV::enumerator en(bv, offset);
1351 for (;en.valid(); ++en)
1352 {
1353 size_type idx = *en - offset;
1354 if (idx >= size)
1355 break;
1356 arr[idx] |= mask;
1357 } // for
1358
1359 } // for i
1360
1361 return 0;
1362}
1363
1364
1365//---------------------------------------------------------------------
1366
1367template<class Val, class BV>
1370 size_type size,
1371 size_type offset,
1372 bool zero_mem) const BMNOEXCEPT2
1373{
1374 /// Decoder functor
1375 /// @internal
1376 ///
1377 struct sv_decode_visitor_func
1378 {
1379 sv_decode_visitor_func(value_type* BMRESTRICT varr,
1380 value_type mask,
1382 : arr_(varr), mask_(mask), sv_off_(off)
1383 {}
1384
1385 void add_bits(size_type bv_offset,
1386 const unsigned char* bits, unsigned bits_size) BMNOEXCEPT
1387 {
1388 // can be negative (-1) when bv base offset = 0 and sv = 1,2..
1389 size_type base = bv_offset - sv_off_;
1390 value_type m = mask_;
1391 for (unsigned i = 0; i < bits_size; ++i)
1392 arr_[bits[i] + base] |= m;
1393 }
1394 void add_range(size_type bv_offset, size_type sz) BMNOEXCEPT
1395 {
1396 auto base = bv_offset - sv_off_;
1397 value_type m = mask_;
1398 for (size_type i = 0; i < sz; ++i)
1399 arr_[i + base] |= m;
1400 }
1401
1402 value_type* BMRESTRICT arr_; ///< target array for reverse transpose
1403 value_type mask_; ///< bit-plane mask
1404 size_type sv_off_; ///< SV read offset
1405 };
1406
1407 if (!size)
1408 return 0;
1409
1410 if (zero_mem)
1411 ::memset(arr, 0, sizeof(value_type)*size);
1412
1413 size_type end = offset + size;
1414 if (end > this->size_)
1415 end = this->size_;
1416
1417 sv_decode_visitor_func func(arr, 0, offset);
1418
1419 for (size_type i = 0; i < parent_type::value_bits(); ++i)
1420 {
1421 const bvector_type* bv = this->bmatr_.get_row(i);
1422 if (!bv)
1423 continue;
1424 func.mask_ = (value_type(1) << i); // set target plane OR mask
1425 bm::for_each_bit_range_no_check(*bv, offset, end-1, func);
1426 } // for i
1427 return end - offset;
1428}
1429
1430//---------------------------------------------------------------------
1431
1432template<class Val, class BV>
1435{
1436 if (idx >= this->size_)
1437 throw_range_error("sparse vector range error");
1438 return this->get(idx);
1439}
1440
1441//---------------------------------------------------------------------
1442
1443template<class Val, class BV>
1447{
1448 BM_ASSERT(i < bm::id_max);
1449 BM_ASSERT(i < size());
1450
1451 value_type v = 0;
1452 unsigned eff_plains = this->effective_plains();
1453 for (unsigned j = 0; j < eff_plains; j+=4)
1454 {
1455 bool b = this->bmatr_.test_4rows(j);
1456 if (b)
1457 {
1458 value_type vm = (value_type)this->bmatr_.get_half_octet(i, j);
1459 v |= vm << j;
1460 }
1461 } // for j
1462 return v;
1463}
1464
1465
1466//---------------------------------------------------------------------
1467
1468template<class Val, class BV>
1470{
1471 if (idx >= size())
1472 {
1473 this->size_ = idx+1;
1474 }
1475 set_value(idx, v);
1476}
1477
1478//---------------------------------------------------------------------
1479
1480template<class Val, class BV>
1482{
1483 if (idx >= size())
1484 this->size_ = idx+1;
1485
1486 set_value(idx, (value_type)0);
1487 if (set_null)
1488 {
1489 bvector_type* bv_null = this->get_null_bvect();
1490 if (bv_null)
1491 bv_null->set(idx, false);
1492 }
1493}
1494
1495//---------------------------------------------------------------------
1496
1497template<class Val, class BV>
1499{
1500 set_value(this->size_, v);
1501 ++(this->size_);
1502}
1503
1504//---------------------------------------------------------------------
1505
1506template<class Val, class BV>
1508{
1509 BM_ASSERT(count);
1510 BM_ASSERT(bm::id_max - count > this->size_);
1511 BM_ASSERT(this->is_nullable());
1512
1513 this->size_ += count;
1514}
1515
1516
1517//---------------------------------------------------------------------
1518
1519template<class Val, class BV>
1521{
1522 if (idx >= size())
1523 {
1524 this->size_ = idx+1;
1525 set_value(idx, v);
1526 return;
1527 }
1528 insert_value(idx, v);
1529}
1530
1531//---------------------------------------------------------------------
1532
1533template<class Val, class BV>
1535{
1536 insert_value_no_null(idx, v);
1537 this->insert_null(idx, true);
1538}
1539
1540//---------------------------------------------------------------------
1541
1542template<class Val, class BV>
1544{
1545 unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1546 value_type mask = 1u;
1547 unsigned i = 0;
1548 for (; i <= bsr; ++i)
1549 {
1550 if (v & mask)
1551 {
1552 bvector_type* bv = this->get_plain(i);
1553 bv->insert(idx, true);
1554 }
1555 else
1556 {
1557 bvector_type_ptr bv = this->bmatr_.get_row(i);
1558 if (bv)
1559 bv->insert(idx, false);
1560 }
1561 mask <<= 1;
1562 } // for i
1563 // insert 0 into all other existing plains
1564 unsigned eff_plains = this->effective_plains();
1565 for (; i < eff_plains; ++i)
1566 {
1567 bvector_type* bv = this->bmatr_.get_row(i);
1568 if (bv)
1569 bv->insert(idx, false);
1570 } // for i
1571
1572 this->size_++;
1573}
1574
1575//---------------------------------------------------------------------
1576
1577template<class Val, class BV>
1579{
1580 BM_ASSERT(idx < this->size_);
1581 if (idx >= this->size_)
1582 return;
1583 this->erase_column(idx);
1584 this->size_--;
1585}
1586
1587
1588//---------------------------------------------------------------------
1589
1590template<class Val, class BV>
1592{
1593 set_value_no_null(this->size_, v);
1594 ++(this->size_);
1595}
1596
1597//---------------------------------------------------------------------
1598
1599template<class Val, class BV>
1601{
1602 set_value_no_null(idx, v);
1603 bvector_type* bv_null = this->get_null_bvect();
1604 if (bv_null)
1605 bv_null->set_bit_no_check(idx);
1606}
1607
1608//---------------------------------------------------------------------
1609
1610template<class Val, class BV>
1612{
1613 // calculate logical block coordinates and masks
1614 //
1615 block_idx_type nb = (idx >> bm::set_block_shift);
1616 unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1617 unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1618
1619 // clear the plains where needed
1620 unsigned eff_plains = this->effective_plains();
1621 unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1622
1623 for (unsigned i = bsr; i < eff_plains; ++i)
1624 {
1625 const bm::word_t* blk = this->bmatr_.get_block(i, i0, j0);
1626 if (blk)
1627 {
1628 bvector_type* bv = this->bmatr_.get_row(i);
1629 if (bv)
1630 bv->clear_bit_no_check(idx);
1631 }
1632 } // for i
1633
1634 if (v)
1635 {
1636 value_type mask = 1u;
1637 for (unsigned j = 0; j <= bsr; ++j)
1638 {
1639 if (v & mask)
1640 {
1641 bvector_type* bv = this->get_plain(j);
1642 bv->set_bit_no_check(idx);
1643 }
1644 else
1645 {
1646 const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1647 if (blk)
1648 {
1649 bvector_type* bv = this->bmatr_.get_row(j);
1650 bv->clear_bit_no_check(idx);
1651 }
1652 }
1653 mask <<= 1;
1654 } // for j
1655 }
1656}
1657
1658//---------------------------------------------------------------------
1659
1660template<class Val, class BV>
1662{
1663 if (idx >= this->size_)
1664 this->size_ = idx+1;
1665
1666 for (unsigned i = 0; i < parent_type::sv_value_plains; ++i)
1667 {
1668 bvector_type* bv = this->get_plain(i);
1669 bool carry_over = bv->inc(idx);
1670 if (!carry_over)
1671 break;
1672 }
1673 bvector_type* bv_null = this->get_null_bvect();
1674 if (bv_null)
1675 bv_null->set_bit_no_check(idx);
1676}
1677
1678//---------------------------------------------------------------------
1679
1680template<class Val, class BV>
1682{
1683 parent_type::clear();
1684}
1685
1686//---------------------------------------------------------------------
1687
1688template<class Val, class BV>
1690{
1691 BM_ASSERT(rank);
1692 pos = rank - 1;
1693 return true;
1694}
1695
1696//---------------------------------------------------------------------
1697
1698template<class Val, class BV>
1702 typename sparse_vector<Val, BV>::size_type right,
1703 bool set_null)
1704{
1705 parent_type::clear_range(left, right, set_null);
1706 return *this;
1707}
1708
1709//---------------------------------------------------------------------
1710
1711template<class Val, class BV>
1714{
1715 BM_ASSERT(st);
1716 typename bvector_type::statistics stbv;
1717 parent_type::calc_stat(&stbv);
1718 if (st)
1719 {
1720 st->reset();
1721 st->add(stbv);
1722 }
1723}
1724
1725//---------------------------------------------------------------------
1726
1727template<class Val, class BV>
1729 bm::word_t* temp_block,
1730 typename bvector_type::optmode opt_mode,
1732{
1733 typename bvector_type::statistics stbv;
1734 stbv.reset();
1735 parent_type::optimize(temp_block, opt_mode, st ? &stbv : 0);
1736
1737 if (st)
1738 {
1739 st->reset();
1740 st->add(stbv);
1741 }
1742}
1743
1744//---------------------------------------------------------------------
1745
1746template<class Val, class BV>
1748{
1749 unsigned stored_plains = this->stored_plains();
1750 for (unsigned j = 0; j < stored_plains; ++j)
1751 {
1752 bvector_type* bv = this->bmatr_.get_row(j);
1753 if (bv)
1754 {
1755 bv->optimize_gap_size();
1756 }
1757 }
1758}
1759
1760//---------------------------------------------------------------------
1761
1762template<class Val, class BV>
1765{
1766 size_type arg_size = sv.size();
1767 if (this->size_ < arg_size)
1768 {
1769 resize(arg_size);
1770 }
1771 bvector_type* bv_null = this->get_null_bvect();
1772 unsigned plains;
1773 if (bv_null)
1774 plains = this->stored_plains();
1775 else
1776 plains = this->plains();
1777
1778 for (unsigned j = 0; j < plains; ++j)
1779 {
1780 const bvector_type* arg_bv = sv.bmatr_.row(j);
1781 if (arg_bv)
1782 {
1783 bvector_type* bv = this->bmatr_.get_row(j);
1784 if (!bv)
1785 bv = this->get_plain(j);
1786 *bv |= *arg_bv;
1787 }
1788 } // for j
1789
1790 // our vector is NULL-able but argument is not (assumed all values are real)
1791 if (bv_null && !sv.is_nullable())
1792 {
1793 bv_null->set_range(0, arg_size-1);
1794 }
1795
1796 return *this;
1797}
1798
1799//---------------------------------------------------------------------
1800
1801template<class Val, class BV>
1804{
1805 size_type arg_size = sv.size();
1806 if (this->size_ < arg_size)
1807 {
1808 resize(arg_size);
1809 }
1810 bvector_type* bv_null = this->get_null_bvect();
1811 unsigned plains;
1812 if (bv_null)
1813 plains = this->stored_plains();
1814 else
1815 plains = this->plains();
1816
1817 for (unsigned j = 0; j < plains; ++j)
1818 {
1819 bvector_type* arg_bv = sv.bmatr_.get_row(j);//sv.plains_[j];
1820 if (arg_bv)
1821 {
1822 bvector_type* bv = this->bmatr_.get_row(j);//this->plains_[j];
1823 if (!bv)
1824 bv = this->get_plain(j);
1825 bv->merge(*arg_bv);
1826 }
1827 } // for j
1828
1829 // our vector is NULL-able but argument is not (assumed all values are real)
1830 if (bv_null && !sv.is_nullable())
1831 {
1832 bv_null->set_range(0, arg_size-1);
1833 }
1834
1835 return *this;
1836}
1837
1838//---------------------------------------------------------------------
1839
1840template<class Val, class BV>
1843 typename sparse_vector<Val, BV>::size_type right,
1844 bm::null_support splice_null)
1845{
1846 if (left > right)
1847 bm::xor_swap(left, right);
1848 //this->clear();
1849 this->copy_range_plains(sv, left, right, splice_null);
1850 this->resize(sv.size());
1851}
1852//---------------------------------------------------------------------
1853
1854template<class Val, class BV>
1856 const typename sparse_vector<Val, BV>::bvector_type& bv_mask)
1857{
1858 bvector_type* bv_null = this->get_null_bvect();
1859 unsigned plains;
1860 if (bv_null)
1861 {
1862 plains = this->stored_plains();
1863 bv_null->bit_and(bv_mask);
1864 }
1865 else
1866 plains = this->plains();
1867
1868 for (unsigned j = 0; j < plains; ++j)
1869 {
1870 bvector_type* bv = this->bmatr_.get_row(j);
1871 if (bv)
1872 bv->bit_and(bv_mask);
1873 }
1874}
1875
1876//---------------------------------------------------------------------
1877
1878template<class Val, class BV>
1880 const value_type val) const BMNOEXCEPT
1881{
1882 // TODO: consider bit-by-bit comparison to minimize CPU hit miss in plans get()
1883 value_type sv_value = get(idx);
1884 return (sv_value > val) - (sv_value < val);
1885}
1886
1887//---------------------------------------------------------------------
1888
1889template<class Val, class BV>
1891 bm::null_support null_able) const BMNOEXCEPT
1892{
1893 return parent_type::equal(sv, null_able);
1894}
1895
1896//---------------------------------------------------------------------
1897
1898template<class Val, class BV>
1901{
1902 typedef typename sparse_vector<Val, BV>::const_iterator it_type;
1903 return it_type(this);
1904}
1905
1906//---------------------------------------------------------------------
1907
1908template<class Val, class BV>
1911{
1912 this->bmatr_.set_allocator_pool(pool_ptr);
1913}
1914
1915
1916//---------------------------------------------------------------------
1917//
1918//---------------------------------------------------------------------
1919
1920
1921template<class Val, class BV>
1925
1926//---------------------------------------------------------------------
1927
1928template<class Val, class BV>
1931: sv_(it.sv_), pos_(it.pos_), buf_ptr_(0)
1932{}
1933
1934//---------------------------------------------------------------------
1935
1936template<class Val, class BV>
1939 ) BMNOEXCEPT
1940: sv_(sv), buf_ptr_(0)
1941{
1942 BM_ASSERT(sv_);
1943 pos_ = sv_->empty() ? bm::id_max : 0u;
1944}
1945
1946//---------------------------------------------------------------------
1947
1948template<class Val, class BV>
1952: sv_(sv), buf_ptr_(0)
1953{
1954 BM_ASSERT(sv_);
1955 this->go_to(pos);
1956}
1957
1958//---------------------------------------------------------------------
1959
1960template<class Val, class BV>
1962{
1963 pos_ = (!sv_ || pos >= sv_->size()) ? bm::id_max : pos;
1964 buf_ptr_ = 0;
1965}
1966
1967//---------------------------------------------------------------------
1968
1969template<class Val, class BV>
1971{
1972 if (pos_ == bm::id_max) // nothing to do, we are at the end
1973 return false;
1974 ++pos_;
1975 if (pos_ >= sv_->size())
1976 {
1977 this->invalidate();
1978 return false;
1979 }
1980 if (buf_ptr_)
1981 {
1982 ++buf_ptr_;
1983 if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
1984 buf_ptr_ = 0;
1985 }
1986 return true;
1987}
1988
1989//---------------------------------------------------------------------
1990
1991template<class Val, class BV>
1994{
1995 BM_ASSERT(this->valid());
1996 value_type v;
1997
1998 if (!buf_ptr_)
1999 {
2000 buffer_.reserve(n_buf_size * sizeof(value_type));
2001 buf_ptr_ = (value_type*)(buffer_.data());
2002 sv_->extract(buf_ptr_, n_buf_size, pos_, true);
2003 }
2004 v = *buf_ptr_;
2005 return v;
2006}
2007
2008//---------------------------------------------------------------------
2009
2010template<class Val, class BV>
2012{
2013 value_type v = value();
2014 if (buf_ptr_)
2015 {
2016 v = *buf_ptr_;
2017 value_type* buf_end = ((value_type*)buffer_.data()) + n_buf_size;
2018 while(!v)
2019 {
2020 ++pos_;
2021 if (++buf_ptr_ < buf_end)
2022 v = *buf_ptr_;
2023 else
2024 break;
2025 }
2026 if (pos_ >= sv_->size())
2027 {
2028 pos_ = bm::id_max;
2029 return;
2030 }
2031 if (buf_ptr_ >= buf_end)
2032 buf_ptr_ = 0;
2033 }
2034}
2035
2036//---------------------------------------------------------------------
2037
2038template<class Val, class BV>
2040{
2041 return sv_->is_null(pos_);
2042}
2043
2044
2045//---------------------------------------------------------------------
2046//
2047//---------------------------------------------------------------------
2048
2049
2050template<class Val, class BV>
2052: sv_(0), bv_null_(0), buf_ptr_(0), prev_nb_(0), set_not_null_(true)
2053{}
2054
2055//---------------------------------------------------------------------
2056
2057template<class Val, class BV>
2060: sv_(sv), buf_ptr_(0), set_not_null_(true)
2061{
2062 if (sv)
2063 {
2064 prev_nb_ = sv_->size() >> bm::set_block_shift;
2065 bv_null_ = sv_->get_null_bvect();
2066 }
2067 else
2068 {
2069 bv_null_ = 0; prev_nb_ = 0;
2070 }
2071}
2072
2073//---------------------------------------------------------------------
2074
2075template<class Val, class BV>
2077 const typename sparse_vector<Val, BV>::back_insert_iterator& bi)
2078: sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(0), prev_nb_(bi.prev_nb_),
2079 set_not_null_(bi.set_not_null_)
2080{
2081 BM_ASSERT(bi.empty());
2082}
2083
2084//---------------------------------------------------------------------
2085
2086template<class Val, class BV>
2091
2092//---------------------------------------------------------------------
2093
2094template<class Val, class BV>
2097{
2098 size_type buf_idx = this->add_value_no_null(v);
2099 if (bv_null_)
2100 {
2101 typename sparse_vector<Val, BV>::size_type sz = sv_->size();
2102 bv_null_->set_bit_no_check(sz + buf_idx);
2103 }
2104}
2105
2106//---------------------------------------------------------------------
2107
2108template<class Val, class BV>
2112{
2113 BM_ASSERT(sv_);
2114 if (!buf_ptr_) // not allocated (yet)
2115 {
2116 buffer_.reserve(n_buf_size * sizeof(value_type));
2117 buf_ptr_ = (value_type*)(buffer_.data());
2118 *buf_ptr_ = v;
2119 ++buf_ptr_;
2120 return 0;
2121 }
2122 if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
2123 {
2124 this->flush();
2125 buf_ptr_ = (value_type*)(buffer_.data());
2126 }
2127
2128 *buf_ptr_ = v;
2129 size_type buf_idx = size_type(buf_ptr_ - ((value_type*)buffer_.data()));
2130 ++buf_ptr_;
2131 return buf_idx;
2132}
2133
2134//---------------------------------------------------------------------
2135
2136template<class Val, class BV>
2138{
2139 BM_ASSERT(bv_null_);
2140 this->add_value_no_null(value_type(0));
2141}
2142
2143//---------------------------------------------------------------------
2144
2145template<class Val, class BV>
2148{
2149 if (count < 32)
2150 {
2151 for (size_type i = 0; i < count; ++i)
2152 this->add_value_no_null(value_type(0));
2153 }
2154 else
2155 {
2156 this->flush();
2157 sv_->push_back_null(count);
2158 }
2159}
2160
2161//---------------------------------------------------------------------
2162
2163template<class Val, class BV>
2165{
2166 return (!buf_ptr_ || !sv_);
2167}
2168
2169//---------------------------------------------------------------------
2170
2171template<class Val, class BV>
2173{
2174 if (this->empty())
2175 return;
2176 value_type* d = (value_type*)buffer_.data();
2177 sv_->import_back(d, size_type(buf_ptr_ - d), false); //!set_not_null_);
2178 buf_ptr_ = 0;
2179 block_idx_type nb = sv_->size() >> bm::set_block_shift;
2180 if (nb != prev_nb_)
2181 {
2182 // optimize all previous blocks in all planes
2183 sv_->optimize_block(prev_nb_);
2184 prev_nb_ = nb;
2185 }
2186}
2187
2188//---------------------------------------------------------------------
2189
2190
2191} // namespace bm
2192
2193#include "bmundef.h"
2194
2195
2196#endif
Algorithms for bvector<>
basic bit-matrix class and utilities
Definitions(internal)
#define IS_FULL_BLOCK(addr)
Definition bmdef.h:153
#define BMRESTRICT
Definition bmdef.h:193
#define BMNOEXCEPT
Definition bmdef.h:79
#define BMGAP_PTR(ptr)
Definition bmdef.h:179
#define BM_IS_GAP(ptr)
Definition bmdef.h:181
#define BM_ASSERT
Definition bmdef.h:130
#define BM_ASSERT_THROW(x, xerrcode)
Definition bmdef.h:401
#define FULL_BLOCK_FAKE_ADDR
Definition bmdef.h:149
#define BMNOEXCEPT2
Definition bmdef.h:82
Utilities for bit transposition (internal) (experimental!)
pre-processor un-defines to avoid global space pollution (internal)
Base class for bit-transposed sparse vector construction.
Definition bmbmatrix.h:254
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
Definition bmbmatrix.h:1175
bmatrix_type bmatr_
bit-transposed matrix
Definition bmbmatrix.h:495
void resize(size_type new_size)
Definition bmbmatrix.h:1267
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
Definition bmbmatrix.h:322
Basic dense bit-matrix class.
Definition bmbmatrix.h:54
const bvector_type * row(size_type i) const BMNOEXCEPT
Definition bmbmatrix.h:560
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT
Definition bmbmatrix.h:570
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:600
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:108
optmode
Optimization mode Every next level means additional checks (better compression vs time)
Definition bm.h:130
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:134
allocator_type::allocator_pool_type allocator_pool_type
Definition bm.h:111
bm::id_t size_type
Definition bm.h:117
blocks_manager_type::block_idx_type block_idx_type
Definition bm.h:113
Alloc allocator_type
Definition bm.h:110
Rank-Select compressed sparse vector.
Back insert iterator implements buffered insert, faster than generic access assignment.
back_insert_iterator & operator=(value_type v)
push value to the vector
void add_null(size_type count)
add a series of consequitve NULLs (no-value) to the container
bm::byte_buffer< allocator_type > buffer_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
bvector_type::block_idx_type block_idx_type
size_type add_value_no_null(value_type v)
add value to the buffer without changing the NULL vector
void add_null()
add NULL (no-value) to the container
back_insert_iterator & operator++()
noop
sparse_vector_type::size_type size_type
bvector_type * get_null_bvect() const BMNOEXCEPT
Get access to not-null vector.
back_insert_iterator & operator++(int)
noop
back_insert_iterator(const back_insert_iterator &bi)
void add(value_type v)
add value to the container
void flush()
flush the accumulated buffer
void disable_set_null() BMNOEXCEPT
Reconfшпгку back inserter not to touch the NULL vector.
bool empty() const
return true if insertion buffer is empty
sparse_vector_type * sparse_vector_type_ptr
back_insert_iterator(sparse_vector_type *sv)
bvector_type::allocator_type allocator_type
back_insert_iterator & operator*()
noop
sparse_vector< Val, BV > sparse_vector_type
back_insert_iterator & operator=(const back_insert_iterator &bi)
std::output_iterator_tag iterator_category
sparse_vector_type::value_type value_type
sparse_vector_type::bvector_type bvector_type
Const iterator to traverse the sparse vector.
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
void go_to(size_type pos) BMNOEXCEPT
re-position to a specified position
std::input_iterator_tag iterator_category
bool operator==(const const_iterator &it) const BMNOEXCEPT
bool operator>(const const_iterator &it) const BMNOEXCEPT
bvector_type::allocator_type allocator_type
sparse_vector< Val, BV > sparse_vector_type
bool is_null() const BMNOEXCEPT
Get NULL status.
bool advance() BMNOEXCEPT
advance iterator forward by one
value_type operator*() const
Get current position (value)
sparse_vector_type::bvector_type bvector_type
bool operator!=(const const_iterator &it) const BMNOEXCEPT
bool operator<(const const_iterator &it) const BMNOEXCEPT
bool operator<=(const const_iterator &it) const BMNOEXCEPT
bool valid() const BMNOEXCEPT
Returns true if iterator is at a valid position.
bm::byte_buffer< allocator_type > buffer_type
void invalidate() BMNOEXCEPT
Invalidate current iterator.
value_type value() const
Get current position (value)
sparse_vector_type::size_type size_type
size_type pos() const BMNOEXCEPT
Current position (index) in the vector.
sparse_vector_type * sparse_vector_type_ptr
sparse_vector_type::value_type value_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
const_iterator & operator++(int)
Advance to the next available value.
bool operator>=(const const_iterator &it) const BMNOEXCEPT
Reference class to access elements via common [] operator.
bool operator==(const reference &ref) const BMNOEXCEPT
bool is_null() const BMNOEXCEPT
reference & operator=(const reference &ref)
reference & operator=(value_type val)
reference(sparse_vector< Val, BV > &sv, size_type idx) BMNOEXCEPT
sparse vector de-serializer
algorithms for sparse_vector scan/search
sparse vector with runtime compression using bit transposition method
Definition bmsparsevec.h:82
void inc(size_type idx)
increment specified element by one
bool is_remap() const BMNOEXCEPT
bvector_type::size_type size_type
Definition bmsparsevec.h:87
static bool is_compressed() BMNOEXCEPT
trait if sparse vector is "compressed" (false)
value_type at(size_type idx) const
access specified element with bounds checking
void set_null(size_type idx)
set specified element to unassigned value (NULL)
void copy_range(const sparse_vector< Val, BV > &sv, size_type left, size_type right, bm::null_support splice_null=bm::use_null)
copy range of values from another sparse vector
void erase(size_type idx)
erase specified element from container
void set_value(size_type idx, value_type v)
set value without checking boundaries
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
allocator_type::allocator_pool_type allocator_pool_type
Definition bmsparsevec.h:94
void insert_value_no_null(size_type idx, value_type v)
insert value without checking boundaries or support of NULL
bool equal(const sparse_vector< Val, BV > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
check if another sparse vector has the same content and size
void sync(bool)
syncronize internal structures
const value_type & const_reference
Definition bmsparsevec.h:90
void push_back(value_type v)
push value back into vector
size_type size_internal() const BMNOEXCEPT
void push_back_no_null(value_type v)
push value back into vector without NULL semantics
void insert_value(size_type idx, value_type v)
insert value without checking boundaries
bvector_type * bvector_type_ptr
Definition bmsparsevec.h:86
void resize_internal(size_type sz)
unsigned char * init_remap_buffer() BMNOEXCEPT
void set_remap() BMNOEXCEPT
size_type size() const BMNOEXCEPT
return size of the vector
void optimize_gap_size()
Optimize sizes of GAP blocks.
sparse_vector(const sparse_vector< Val, BV > &sv)
sparse_vector(sparse_vector< Val, BV > &&sv) BMNOEXCEPT
bvector_type::enumerator bvector_enumerator_type
Definition bmsparsevec.h:93
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
void resize(size_type sz)
resize vector
size_t remap_size() const BMNOEXCEPT
void set_value_no_null(size_type idx, value_type v)
set value without checking boundaries or support of NULL
static void throw_range_error(const char *err_msg)
throw range error
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
bool resolve_range(size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
friend back_insert_iterator
bvector_type::block_idx_type block_idx_type
Definition bmsparsevec.h:88
size_type gather(value_type *arr, const size_type *idx, size_type size, bm::sort_order sorted_idx) const
Gather elements to a C-style array.
void push_back_null(size_type count)
push back specified amount of NULL values
sparse_vector< Val, BV > & merge(sparse_vector< Val, BV > &sv)
merge with another sparse vector using OR operation Merge is different from join(),...
const unsigned char * get_remap_buffer() const BMNOEXCEPT
int compare(size_type idx, const value_type val) const BMNOEXCEPT
Compare vector element with argument.
size_type extract_plains(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract medium window without use of masking vector
bool empty() const BMNOEXCEPT
return true if vector is empty
~sparse_vector() BMNOEXCEPT
static bool find_rank(size_type rank, size_type &pos) BMNOEXCEPT
find position of compressed element by its rank
sparse_vector< Val, BV > & operator=(const sparse_vector< Val, BV > &sv)
void swap(sparse_vector< Val, BV > &sv) BMNOEXCEPT
content exchange
sparse_vector< Val, BV > & join(const sparse_vector< Val, BV > &sv)
join all with another sparse vector using OR operation
static size_type translate_address(size_type i) BMNOEXCEPT
address translation for this type of container
void insert(size_type idx, value_type v)
insert specified element into container
void import_back(const value_type *arr, size_type arr_size, bool set_not_null=true)
Import list of elements from a C-style array (pushed back)
base_sparse_vector< Val, BV, 1 > parent_type
Definition bmsparsevec.h:96
size_type extract_range(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract small window without use of masking vector
void calc_stat(struct sparse_vector< Val, BV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
static void throw_bad_alloc()
throw bad alloc
BV::allocator_type allocator_type
Definition bmsparsevec.h:91
sparse_vector(bm::null_support null_able=bm::no_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Sparse vector constructor.
sparse_vector< Val, BV > & clear_range(size_type left, size_type right, bool set_null=false)
clear range (assign bit 0 for all plains)
size_type effective_size() const BMNOEXCEPT
size of sparse vector (may be different for RSC)
void clear() BMNOEXCEPT
resize to zero, free memory
size_type decode(value_type *arr, size_type idx_from, size_type dec_size, bool zero_mem=true) const
Bulk export list of elements to a C-style array.
bm::basic_bmatrix< BV > bmatrix_type
Definition bmsparsevec.h:95
size_type extract(value_type *arr, size_type size, size_type offset=0, bool zero_mem=true) const BMNOEXCEPT2
Bulk export list of elements to a C-style array.
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
bvector_type::allocation_policy allocation_policy_type
Definition bmsparsevec.h:92
void import(const value_type *arr, size_type arr_size, size_type offset=0, bool set_not_null=true)
Import list of elements from a C-style array.
void filter(const bvector_type &bv_mask)
Apply value filter, defined by mask vector.
const bvector_type * bvector_type_const_ptr
Definition bmsparsevec.h:89
void clear(size_type idx, bool set_null=false)
clear specified element with bounds checking and automatic resize
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations.
value_type operator[](size_type idx) const BMNOEXCEPT
get specified element without bounds checking
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector plains
void bit_block_gather_scatter(unsigned *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx) BMNOEXCEPT
bit index to word gather-scatter algorithm (SIMD)
Definition bmfunc.h:8471
unsigned bit_scan_reverse(T value) BMNOEXCEPT
Definition bmutil.h:415
sort_order
Sort order declaration.
Definition bmconst.h:189
null_support
NULL-able value support.
Definition bmconst.h:214
@ BM_UNSORTED
input set is NOT sorted
Definition bmconst.h:190
@ BM_SORTED
input set is sorted (ascending order)
Definition bmconst.h:191
@ BM_UNKNOWN
sort order unknown
Definition bmconst.h:193
@ BM_SORTED_UNIFORM
sorted and in one block (internal!)
Definition bmconst.h:192
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:215
@ no_null
do not support NULL values
Definition bmconst.h:216
unsigned gap_test_unr(const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition bmfunc.h:1298
Definition bm.h:77
const unsigned set_array_mask
Definition bmconst.h:96
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition bmfunc.h:909
const unsigned id_max
Definition bmconst.h:108
unsigned int word_t
Definition bmconst.h:38
const unsigned set_block_mask
Definition bmconst.h:56
unsigned short bitscan(V w, B *bits) BMNOEXCEPT
Definition bmfunc.h:554
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Definition bmfunc.h:1220
const unsigned set_word_shift
Definition bmconst.h:71
bm::id64_t idx_arr_block_lookup_u64(const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start) BMNOEXCEPT
block boundaries look ahead U32
Definition bmfunc.h:8546
unsigned idx_arr_block_lookup_u32(const unsigned *idx, unsigned size, unsigned nb, unsigned start) BMNOEXCEPT
block boundaries look ahead U32
Definition bmfunc.h:8572
const unsigned set_array_shift
Definition bmconst.h:95
unsigned short gap_word_t
Definition bmconst.h:77
const unsigned set_block_shift
Definition bmconst.h:55
const unsigned set_word_mask
Definition bmconst.h:72
void for_each_bit_range_no_check(const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
Implementation of for_each_bit_range without boilerplave checks.
Structure with statistical information about memory allocation footprint, serialization projection,...
Definition bmfunc.h:55
void reset() BMNOEXCEPT
Reset statisctics.
Definition bmfunc.h:96
void add(const bv_statistics &st) BMNOEXCEPT
Sum data from another sttructure.
Definition bmfunc.h:105
memory allocation policy
Definition bm.h:820
Statistical information about bitset's memory allocation details.
Definition bm.h:122
Mini-matrix for bit transposition purposes.
Definition bmtrans.h:41