libcds/src/static_sequence/static_sequence.h

   1 /* static_sequence.h
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * static_sequence 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 #ifndef _STATIC_SEQUENCE_H
  23 #define _STATIC_SEQUENCE_H
  24
  25
  26 #include <basics.h>
  27 #include <iostream>
  28 #include <vector>
  29
  30 #define WVTREE_HDR 2
  31 #define GMR_CHUNK_HDR 3
  32 #define GMR_HDR 4
  33 #define WVTREE_NOPTRS_HDR 5
  34 #define BS_HDR 6
  35
  36 using namespace std;
  37
  38 /** Base class for static sequences, contains many abstract functions, so this can't
  39  *  be instantiated.
  40  *
  41  *  @author Francisco Claude
  42  */
  43 class static_sequence {
  44
  45 public:
  46   static_sequence();
  47   virtual ~static_sequence();
  48
  49   /** Returns the number of occurrences of c until position i */
  50   virtual uint rank(uint c, uint i)=0;
  51   virtual uint rankLessThan(uint &i, uint j)
  52   {
  53       //assert(0); // Implemented only in static_sequence_wvtree
  54       return -1;
  55   }
  56
  57   /** Returns the position of the i-th c
  58    * @return (uint)-1 if i=0, len if i exceeds the number of cs */
  59   virtual uint select(uint c, uint i)=0;
  60         virtual uint select_next(uint c, uint i);
  61
  62   /** Returns the i-th element */
  63   virtual uint access(uint i)=0;
  64   virtual uint access(uint i, uint &rank)
  65   {
  66       //assert(0); // Implemented only in static_sequence_wvtree
  67       return -1;
  68   }
  69
  70   // Returns all elements from interval [i, j] such that
  71   // their value is in [min, max].
  72   virtual vector<int> access(uint i, uint j, uint min, uint max)
  73   {
  74       //assert(0); // Implemented only in static_sequence_wvtree
  75       return vector<int>();
  76   }
  77
  78   // Returns all elements from interval [i, j]
  79   virtual vector<int> accessAll(uint i, uint j)
  80   {
  81       //assert(0); // Implemented only in static_sequence_wvtree
  82       return vector<int>();
  83   }
  84
  85   // Counts the number of elements in interval [i,j] such that
  86   // their values are in [min,max]
  87   virtual uint count(uint i, uint j, uint min, uint max)
  88   {
  89       //assert(0); // Implemented only in static_sequence_wvtree
  90       return 0;
  91   }
  92
  93   /** Returns the length of the sequence */
  94   virtual uint length();
  95
  96   /** Returns how many cs are in the sequence */
  97   virtual uint count(uint c);
  98
  99   /** Returns the size of the structure in bytes */
 100   virtual uint size()=0;
 101
 102   /** Stores the bitmap given a file pointer, return 0 in case of success */
 103   virtual uint save(FILE * fp)=0;
 104
 105         virtual bool test(uint * seq, uint n);
 106
 107   /** Reads a bitmap determining the type */
 108   static static_sequence * load(FILE * fp);
 109
 110 protected:
 111   /** Length of the bitstring */
 112   uint len;
 113
 114 };
 115
 116 #include <static_sequence_wvtree.h>
 117 #include <static_sequence_gmr_chunk.h>
 118 #include <static_sequence_wvtree_noptrs.h>
 119 #include <static_sequence_gmr.h>
 120 #include <static_sequence_bs.h>
 121
 122 #endif  /* _STATIC_SEQUENCE_H */