SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
00001 /* sdsl - succinct data structures library 00002 Copyright (C) 2009 Simon Gog 00003 00004 This program is free software: you can redistribute it and/or modify 00005 it under the terms of the GNU General Public License as published by 00006 the Free Software Foundation, either version 3 of the License, or 00007 (at your option) any later version. 00008 00009 This program is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 GNU General Public License for more details. 00013 00014 You should have received a copy of the GNU General Public License 00015 along with this program. If not, see http://www.gnu.org/licenses/ . 00016 */ 00021 #ifndef INCLUDED_SDSL_SORTED_STACK_SUPPORT 00022 #define INCLUDED_SDSL_SORTED_STACK_SUPPORT 00023 00024 #include "int_vector.hpp" 00025 #include "bitmagic.hpp" 00026 #include <vector> 00027 00029 namespace sdsl 00030 { 00031 00033 00036 class sorted_stack_support 00037 { 00038 public: 00039 typedef int_vector<64>::size_type size_type; 00040 private: 00041 size_type m_n; // Size of the supported vector. 00042 size_type m_cnt; // Counter for the indices on the stack. 00043 size_type m_top; // Topmost index of the stack. 00044 int_vector<64> m_stack; // Memory for the stack. 00045 00046 inline size_type block_nr(size_type x) { 00047 return x/63; 00048 }; // TODO: maybe we can speed this up with bit hacks 00049 inline size_type block_pos(size_type x) { 00050 return x%63; 00051 }; // TODO: maybe we can speed this up with bit hacks 00052 public: 00054 00056 sorted_stack_support(size_type n); 00057 00058 sorted_stack_support(const sorted_stack_support& sis); 00059 ~sorted_stack_support() {}; 00060 00063 bool empty() const { 00064 return 0==m_cnt; 00065 }; 00066 00070 const size_type top() const; 00071 00074 void pop(); 00075 00080 void push(size_type x); 00081 00084 size_type size()const { 00085 return m_cnt; 00086 }; 00087 00088 size_type serialize(std::ostream& out)const; 00089 void load(std::istream& in); 00090 00092 00094 sorted_stack_support& operator=(const sorted_stack_support& sis); 00095 00097 00102 bool operator==(const sorted_stack_support& sis)const; 00104 00109 bool operator!=(const sorted_stack_support& sis)const; 00110 00111 }; 00112 00113 inline sorted_stack_support::sorted_stack_support(size_type n):m_n(n), m_cnt(0), m_top(0), m_stack() 00114 { 00115 m_stack = int_vector<64>(block_nr(m_n+1)+1, 0); 00116 m_stack[0] = 1; 00117 } 00118 00119 inline sorted_stack_support::sorted_stack_support(const sorted_stack_support& sis):m_n(sis.m_n), m_cnt(sis.m_cnt), m_top(sis.m_top), m_stack() 00120 { 00121 m_stack = sis.m_stack; 00122 } 00123 00124 inline sorted_stack_support& sorted_stack_support::operator=(const sorted_stack_support& sis) 00125 { 00126 if (this != &sis) { 00127 m_n = sis.m_n; 00128 m_cnt = sis.m_cnt; 00129 m_top = sis.m_top; 00130 m_stack = sis.m_stack; 00131 } 00132 return *this; 00133 } 00134 00135 inline bool sorted_stack_support::operator==(const sorted_stack_support& sis)const 00136 { 00137 return m_n == sis.m_n and m_cnt == sis.m_cnt and m_top == sis.m_top and m_stack == sis.m_stack; 00138 } 00139 00140 inline bool sorted_stack_support::operator!=(const sorted_stack_support& sis)const 00141 { 00142 return !(*this==sis); 00143 } 00144 00145 inline const sorted_stack_support::size_type sorted_stack_support::top()const 00146 { 00147 return m_top-1; 00148 } 00149 00150 inline void sorted_stack_support::push(size_type x) 00151 { 00152 x += 1; 00153 ++m_cnt; //< increment counter 00154 size_type bn = block_nr(x); 00155 m_stack[bn] ^= (1ULL << block_pos(x)); 00156 if (bn > 0 and m_stack[bn-1] == 0) { 00157 m_stack[bn-1] = 0x8000000000000000ULL | m_top; 00158 } 00159 m_top = x; 00160 } 00161 00162 inline void sorted_stack_support::pop() 00163 { 00164 if (!empty()) { 00165 --m_cnt; //< decrement counter 00166 size_type bn = block_nr(m_top); 00167 uint64_t w = m_stack[ bn ]; 00168 assert((w>>63) == 0); // highest bit is not set, as the block contains no pointer 00169 w ^= (1ULL << block_pos(m_top)); 00170 m_stack[ bn ] = w; 00171 if (w>0) { 00172 m_top = bn*63 + bit_magic::l1BP(w); 00173 } else { // w==0 and cnt>0 00174 assert(bn > 0); 00175 w = m_stack[ bn-1 ]; 00176 if ((w>>63) == 0) { // highest bit is not set => the block contains no pointer 00177 assert(w>0); 00178 m_top = (bn-1)*63 + bit_magic::l1BP(w); 00179 } else { // block contains pointers 00180 m_stack[bn-1] = 0; 00181 m_top = w&0x7FFFFFFFFFFFFFFFULL; 00182 } 00183 } 00184 } 00185 } 00186 00187 inline sorted_stack_support::size_type sorted_stack_support::serialize(std::ostream& out)const 00188 { 00189 size_type written_bytes = 0; 00190 written_bytes += util::write_member(m_n, out); 00191 written_bytes += util::write_member(m_top, out); 00192 written_bytes += util::write_member(m_cnt, out); 00193 written_bytes += m_stack.serialize(out); 00194 return written_bytes; 00195 } 00196 00197 inline void sorted_stack_support::load(std::istream& in) 00198 { 00199 util::read_member(m_n, in); 00200 util::read_member(m_top, in); 00201 util::read_member(m_cnt, in); 00202 m_stack.load(in); 00203 } 00204 00205 }// end namespace sdsl 00206 00207 #endif // end file