C++博客-feng

位图索引排序

Wang Feng — Sat, 05 Dec 2009 04:56:00 GMT

昨晚网上搜了一下，没有找到C++实现的代码，于是自己写了一个；
无心在这里copy/paste位图排序的具体解释，如果有知道得不详细的，请访问Wikipedia。

  1 #ifndef _BITMAP_HPP_INCLUDED
  2 #define _BITMAP_HPP_INCLUDED
  3
  4 #include <cstring> //for memset
  5
  6
  7 namespace feng
  8 {
  9
10 template<typename Type>
11 class Bitmap_Sort
12 {
13         typedef Type template_type;
14     private:
15         struct _Bitmap_Impl;
16         _Bitmap_Impl* bi_;
17     public:
18         Bitmap_Sort( const template_type& lower = 1, const template_type& upper = 100 )
19         {
20         bi_ = lower < upper ?
21             new _Bitmap_Impl(lower,upper) :
22             new _Bitmap_Impl(upper,lower);
23
24         }
25         ~Bitmap_Sort()
26         {
27         delete bi_;
28         }
29
30         void process( const template_type& v ) const
31         {
32             (*bi_).register_number( v );
33         }
34
35         template<typename Input_Itor>
36         void process( Input_Itor begin, Input_Itor end ) const
37         {
38         while ( begin != end )
39             (*bi_).register_number( *begin++ );
40         //including  is not of necessity
41         //for_each( begin, end, &((*bi_).register_number) );
42         }
43
44         template<typename Output_Itor>
45         Output_Itor produce( Output_Itor begin ) const
46         {
47         for ( Type i = (*bi_).lower_; i <= (*bi_).upper_; ++i )
48             if ( (*bi_).query_number(i) )
49             *begin++ = i;
50         return begin;
51         }
52 };
53
54
55 template<typename Type>
56 struct Bitmap_Sort<Type> :: _Bitmap_Impl
57 {
58         typedef unsigned long word_type;
59     typedef Type template_type;
60
61     _Bitmap_Impl( const template_type& lower=1, const template_type& upper=100 )
62         : lower_(lower),upper_(upper)
63     {
64             const template_type length = upper - lower + 1;
65         const word_type size = (length >> bit_shift()) + 1;
66
67         buffer_ =  new word_type[size];
68
69         memset(buffer_,size,0);
70     }
71     ~_Bitmap_Impl()
72     {
73         delete [] buffer_;
74     }
75
76     bool register_number( const template_type& v ) const
77     {
78         bool ans = false;
79         if ( v <= upper_ && v >= lower_ )
80         {
81             const template_type shift = v - lower_;
82             const word_type arr_position = shift >> bit_shift();
83             const word_type relative_position = shift & ( (1 << bit_shift()) - 1 );
84             const word_type patch = 1 << ( relative_position + 1 );
85             buffer_[arr_position] |= patch;
86             ans = true;
87         }
88         return ans;
89     }
90     bool query_number( const template_type& v ) const
91     {
92         bool ans = false;
93         //not necessory, commented
94         //if ( v <= upper_ && v >= lower_ )
95         //{
96         const template_type shift = v - lower_;
97         const word_type arr_position = shift >> bit_shift();
98         const word_type relative_position = shift & ( (1 << bit_shift()) - 1 );
99         const word_type patch = 1 << ( relative_position + 1 );
100         if( buffer_[arr_position] & patch )
101             ans = true;
102         //}
103         return ans;
104     }
105
106     const word_type bit_shift() const
107     {
108         return 8 == sizeof(unsiged long) ? 6 : 5;
110     }
111
112     template_type lower_;
113     template_type upper_;
114     mutable word_type* buffer_;
115 };
116
117
118 }//namespace feng
119
120 #endif //_BITMAP_HPP_INCLUDED
121
122
123

一个测试用例：

#include <bitmap.hpp>

#include <iostream>
#include <iterator>

using namespace std;

int main()
{
    feng::Bitmap_Sort<unsigned long> bs(1, 10000000);
    //feng::Bitmap_Sort bs(10000000, 1);

    bs.process((istream_iterator<unsigned long>(cin)), (istream_iterator<unsigned long>()));

    bs.produce(ostream_iterator<unsigned long>(cout, "\n"));

    return 0;
}

Wang Feng 2009-12-05 12:56 发表评论

Communix操作系统简史

Wang Feng — Sun, 11 Jan 2009 07:33:00 GMT

摘要: 影射而已，当笑话看看就行：）阅读全文

Wang Feng 2009-01-11 15:33 发表评论

非均匀取样数据的功率谱估计方法

Wang Feng — Fri, 02 Jan 2009 13:20:00 GMT

摘要: 非均匀采样的数据的功率谱估计方法以及其C++实现阅读全文

Wang Feng 2009-01-02 21:20 发表评论

kde4 svn 编译笔记

Wang Feng — Thu, 18 Dec 2008 09:53:00 GMT

摘要: 中午的时候翻到2007年12月24号的kde编译笔记，不知不觉一年过去了，忽有所感，于是重新编译一次kde4，记之阅读全文

Wang Feng 2008-12-18 17:53 发表评论

对一类因偷换概念而引发的悖论的思考

Wang Feng — Mon, 24 Nov 2008 12:15:00 GMT

摘要: 探讨了一类因为偷换概念而产生的悖论。阅读全文

Wang Feng 2008-11-24 20:15 发表评论

nth_element ---- 比较优美的代码

Wang Feng — Thu, 06 Nov 2008 08:47:00 GMT

摘要: 一段觉得比较漂亮的代码 nth_element 阅读全文

Wang Feng 2008-11-06 16:47 发表评论

将遗传算法的库放到sf去了

Wang Feng — Tue, 28 Oct 2008 02:20:00 GMT

请在这里(http://sourceforge.net/projects/gaplusplus/)下载源代码。cppblog不支持tar.bz2格式的文档上传。

方才在csdn灌水时，发现有人给出这个blog上文章的链接，实在汗颜。
这边的blog荒废了好久，一直没有动手写下去；
前不久把代码重构了一下，放到sf去了；

如有建议或者疑问，欢迎来信(wanng.fenng[at]gmail.com)讨论。

Wang Feng 2008-10-28 10:20 发表评论

遗传算法系列（4）变异算法

Wang Feng — Sun, 22 Jun 2008 08:20:00 GMT

摘要: 遗传算法中，基因变异算法阅读全文

Wang Feng 2008-06-22 16:20 发表评论

遗传算法系列（3）交叉算法

Wang Feng — Wed, 18 Jun 2008 07:56:00 GMT

摘要: 遗传算法中交叉算法的简单介绍。可以理解为人类社会的婚姻过程。阅读全文

Wang Feng 2008-06-18 15:56 发表评论

遗传算法系列（2）遗传算法中的数据结构和与之相关的一些数值算法

Wang Feng — Mon, 16 Jun 2008 08:53:00 GMT

摘要: 遗传算法的数据结构定义，以及相关的几个基本算法，c++实现代码。阅读全文

Wang Feng 2008-06-16 16:53 发表评论