SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
sdsl/include/sdsl/sorted_stack_support.hpp
Go to the documentation of this file.
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