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_INT_STACK 00022 #define INCLUDED_SDSL_SORTED_INT_STACK 00023 00024 #include "int_vector.hpp" 00025 #include "bitmagic.hpp" 00026 #include <vector> 00027 00029 namespace sdsl 00030 { 00031 00033 00036 class sorted_int_stack 00037 { 00038 public: 00039 typedef int_vector<64>::size_type size_type; 00040 private: 00041 size_type m_n; // maximal value which can be stored on the stack 00042 size_type m_cnt; // counter for elements on the stack 00043 size_type m_top; // top element of the stack 00044 int_vector<64> m_stack; // memory for the stack 00045 std::vector<size_type> m_overflow; // memory for the elements which are greater than n 00046 00047 inline size_type block_nr(size_type x) { 00048 return x/63; 00049 }; // maybe we can speed this up with bit hacks 00050 inline size_type block_pos(size_type x) { 00051 return x%63; 00052 }; // maybe we can speed this up with bit hacks 00053 public: 00054 sorted_int_stack(size_type n); 00055 sorted_int_stack(const sorted_int_stack& sis); 00056 ~sorted_int_stack() {}; 00057 00060 bool empty() const { 00061 return 0==m_cnt; 00062 }; 00063 00067 const size_type top() const; 00068 00071 void pop(); 00072 00077 void push(size_type x); 00078 00081 size_type size()const { 00082 return m_cnt; 00083 }; 00084 00085 size_type serialize(std::ostream& out)const; 00086 void load(std::istream& in); 00087 00089 00091 sorted_int_stack& operator=(const sorted_int_stack& sis); 00092 00094 00099 bool operator==(const sorted_int_stack& sis)const; 00101 00106 bool operator!=(const sorted_int_stack& sis)const; 00107 00108 }; 00109 00110 inline sorted_int_stack::sorted_int_stack(size_type n):m_n(n), m_cnt(0), m_top(0) 00111 { 00112 m_stack = int_vector<64>(block_nr(n)+2, 0); 00113 m_stack[0] = 1; 00114 } 00115 inline sorted_int_stack::sorted_int_stack(const sorted_int_stack& sis):m_n(sis.m_n), m_cnt(sis.m_cnt), m_top(sis.m_top) 00116 { 00117 m_stack = sis.m_stack; 00118 m_overflow = sis.m_overflow; 00119 } 00120 00121 inline sorted_int_stack& sorted_int_stack::operator=(const sorted_int_stack& sis) 00122 { 00123 if (this != &sis) { 00124 m_n = sis.m_n; 00125 m_cnt = sis.m_cnt; 00126 m_top = sis.m_top; 00127 m_stack = sis.m_stack; 00128 m_overflow = sis.m_overflow; 00129 } 00130 return *this; 00131 } 00132 00133 inline bool sorted_int_stack::operator==(const sorted_int_stack& sis)const 00134 { 00135 return m_n == sis.m_n and m_cnt == sis.m_cnt and m_top == sis.m_top and m_stack == sis.m_stack and m_overflow == sis.m_overflow; 00136 } 00137 00138 inline bool sorted_int_stack::operator!=(const sorted_int_stack& sis)const 00139 { 00140 return !(*this==sis); 00141 } 00142 00143 inline const sorted_int_stack::size_type sorted_int_stack::top()const 00144 { 00145 return m_top-63; 00146 } 00147 00148 inline void sorted_int_stack::push(size_type x) 00149 { 00150 x += 63; 00151 assert(empty() || m_top < x); 00152 ++m_cnt; //< increment counter 00153 if (x > m_n+63) { 00154 if (m_overflow.empty()) { 00155 m_overflow.push_back(m_top); 00156 } 00157 m_overflow.push_back(x); 00158 m_top = x; 00159 } else { 00160 size_type bn = block_nr(x); 00161 m_stack[bn] ^= (1ULL << block_pos(x)); 00162 if (m_stack[bn-1] == 0) { 00163 m_stack[bn-1] = 0x8000000000000000ULL | m_top; 00164 } 00165 m_top = x; 00166 } 00167 } 00168 00169 inline void sorted_int_stack::pop() 00170 { 00171 if (!empty()) { 00172 --m_cnt; //< decrement counter 00173 if (m_top > m_n+63) { 00174 m_overflow.pop_back(); 00175 m_top = m_overflow.back(); 00176 if (m_overflow.size()==1) 00177 m_overflow.pop_back(); 00178 } else { 00179 size_type bn = block_nr(m_top); 00180 uint64_t w = m_stack[ bn ]; 00181 assert((w>>63) == 0); // highest bit is not set, as the block contains no pointer 00182 w ^= (1ULL << block_pos(m_top)); 00183 m_stack[ bn ] = w; 00184 if (w>0) { 00185 m_top = bn*63 + bit_magic::l1BP(w); 00186 } else { // w==0 and cnt>0 00187 assert(bn > 0); 00188 w = m_stack[ bn-1 ]; 00189 if ((w>>63) == 0) { // highest bit is not set => the block contains no pointer 00190 assert(w>0); 00191 m_top = (bn-1)*63 + bit_magic::l1BP(w); 00192 } else { // block contains pointers 00193 m_stack[bn-1] = 0; 00194 m_top = w&0x7FFFFFFFFFFFFFFFULL; 00195 } 00196 } 00197 } 00198 } 00199 } 00200 00201 inline sorted_int_stack::size_type sorted_int_stack::serialize(std::ostream& out)const 00202 { 00203 size_type written_bytes = 0; 00204 written_bytes += util::write_member(m_n); 00205 written_bytes += util::write_member(m_top); 00206 written_bytes += util::write_member(m_cnt); 00207 written_bytes += m_stack.serialize(out); 00208 int_vector<sizeof(written_bytes)*8> v(m_overflow.size()); 00209 for (size_type i=0; i<v.size(); ++i) v[i] = m_overflow[i]; 00210 written_bytes += v.serialize(out); 00211 return written_bytes; 00212 } 00213 00214 inline void sorted_int_stack::load(std::istream& in) 00215 { 00216 util::read_member(m_n, in); 00217 util::read_member(m_top, in); 00218 util::read_member(m_cnt, in); 00219 m_stack.load(in); 00220 size_type t; 00221 int_vector<sizeof(t)*8> v(m_overflow.size()); 00222 v.load(in); 00223 for (size_type i=0; i<v.size(); ++i) m_overflow[i] = v[i]; 00224 } 00225 00226 }// end namespace sdsl 00227 00228 #endif // end file