libcds/src/static_sequence/static_sequence_wvtree.cpp

   1 /* static_sequence_wvtree.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * static_sequence_wvtree definition
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #include <static_sequence_wvtree.h>
  23
  24 static_sequence_wvtree::static_sequence_wvtree(uint * symbols, uint n, wt_coder * c, static_bitsequence_builder * bmb, alphabet_mapper * am) {
  25   for(uint i=0;i<n;i++)
  26     symbols[i] = am->map(symbols[i]);
  27   this->am = am;
  28         am->use();
  29   this->c=c;
  30         c->use();
  31         root = new wt_node_internal(symbols, n, 0, c, bmb);
  32   for(uint i=0;i<n;i++)
  33     symbols[i] = am->unmap(symbols[i]);
  34 }
  35
  36 static_sequence_wvtree::static_sequence_wvtree(uchar * symbols, uint n, wt_coder * c, static_bitsequence_builder * bmb, alphabet_mapper * am) {
  37   for(uint i=0;i<n;i++)
  38     symbols[i] = (uchar)am->map((uint)symbols[i]);
  39   this->am = am;
  40         am->use();
  41   this->c=c;
  42         c->use();
  43         uint *done = new uint[n/W+1];
  44         for (uint i = 0; i < n/W+1; i++)
  45             done[i] = 0;
  46         root = new wt_node_internal(symbols, n, 0, c, bmb, 0, done);
  47         delete [] done;
  48         delete [] symbols;
  49         symbols = 0; // Already deleted!
  50 //  for(uint i=0;i<n;i++)
  51 //    symbols[i] = (uchar)am->unmap((uint)symbols[i]);
  52 }
  53
  54 static_sequence_wvtree::static_sequence_wvtree() {}
  55
  56 static_sequence_wvtree::~static_sequence_wvtree() {
  57         delete root;
  58         am->unuse();
  59   c->unuse();
  60 }
  61
  62 uint static_sequence_wvtree::rank(uint symbol, uint pos) {
  63         return root->rank(am->map(symbol), pos, 0, c);
  64 }
  65
  66 uint static_sequence_wvtree::rankLessThan(uint &symbol, uint pos) {
  67     uint s = am->map(symbol);
  68 //    std::cout << "lessthan..." << std::endl;
  69     uint r = root->rankLessThan(s, pos, 0, c);
  70     symbol = am->unmap(s);
  71     return r;
  72 }
  73
  74
  75 uint static_sequence_wvtree::count(uint s) {
  76   return root->rank(am->map(s), len-1, 0, c);
  77 }
  78
  79 uint static_sequence_wvtree::select(uint symbol, uint pos) {
  80         uint ret = root->select(am->map(symbol), pos, 0, c);
  81         if(ret==((uint)-1)) return (uint)-1;
  82         return ret-1;
  83 }
  84
  85 uint static_sequence_wvtree::access(uint pos) {
  86         return am->unmap(root->access(pos));
  87 }
  88
  89 vector<int> static_sequence_wvtree::access(uint i, uint j, uint min, uint max)
  90 {
  91     vector<int> resultSet;
  92     root->access(resultSet, i, j, am->map(min), am->map(max), c->depth()-1, 0);
  93     for (vector<int>::iterator it = resultSet.begin(); it != resultSet.end(); ++it)
  94         *it = am->unmap(*it);
  95     return resultSet;
  96 }
  97
  98 vector<int> static_sequence_wvtree::accessAll(uint i, uint j)
  99 {
 100     vector<int> resultSet;
 101     if (j > i)
 102         return resultSet;
 103
 104     resultSet.reserve(j-i+1);
 105     root->access(resultSet, i, j);
 106     for (vector<int>::iterator it = resultSet.begin(); it != resultSet.end(); ++it)
 107         *it = am->unmap(*it);
 108     return resultSet;
 109 }
 110
 111 uint static_sequence_wvtree::count(uint i, uint j, uint min, uint max)
 112 {
 113     return root->access(i, j, am->map(min), am->map(max), c->depth()-1, 0);
 114 }
 115
 116
 117 uint static_sequence_wvtree::size() {
 118         /*cout << "WT: " << root->size() << endl;
 119         cout << "Coder: " << c->size() << endl;
 120         cout << "AM: " << am->size() << endl;*/
 121         return sizeof(static_sequence_wvtree)+sizeof(uint)+root->size()+am->size()+c->size();
 122 }
 123
 124 uint static_sequence_wvtree::save(FILE * fp) {
 125   uint wr = WVTREE_HDR;
 126   wr = fwrite(&wr,sizeof(uint),1,fp);
 127   if(wr!=1) return 1;
 128   wr = fwrite(&n,sizeof(uint),1,fp);
 129   if(wr!=1) return 1;
 130   if(c->save(fp)) return 1;
 131   if(am->save(fp)) return 1;
 132   if(root->save(fp)) return 1;
 133   return 0;
 134 }
 135
 136 static_sequence_wvtree * static_sequence_wvtree::load(FILE *fp) {
 137   uint rd;
 138   if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL;
 139   if(rd!=WVTREE_HDR) return NULL;
 140   static_sequence_wvtree * ret = new static_sequence_wvtree();
 141   if(fread(&ret->n,sizeof(uint),1,fp)!=1) return NULL;
 142   ret->c = wt_coder::load(fp);
 143         ret->c->use();
 144   ret->am = alphabet_mapper::load(fp);
 145         ret->am->use();
 146   ret->root = wt_node::load(fp);
 147   return ret;
 148 }