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_int_stack.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_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