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
  61   /** Returns the i-th element */
  62   virtual uint access(uint i)=0;
  63   virtual uint access(uint i, uint &rank)
  64   {
  65       //assert(0); // Implemented only in static_sequence_wvtree
  66       return -1;
  67   }
  68
  69   // Returns all elements from interval [i, j] such that
  70   // their value is in [min, max].
  71   virtual vector<int> access(uint i, uint j, uint min, uint max)
  72   {
  73       //assert(0); // Implemented only in static_sequence_wvtree
  74       return vector<int>();
  75   }
  76
  77   // Returns all elements from interval [i, j]
  78   virtual vector<int> accessAll(uint i, uint j)
  79   {
  80       //assert(0); // Implemented only in static_sequence_wvtree
  81       return vector<int>();
  82   }
  83
  84   // Counts the number of elements in interval [i,j] such that
  85   // their values are in [min,max]
  86   virtual uint count(uint i, uint j, uint min, uint max)
  87   {
  88       //assert(0); // Implemented only in static_sequence_wvtree
  89       return 0;
  90   }
  91
  92   /** Returns the length of the sequence */
  93   virtual uint length();
  94
  95   /** Returns how many cs are in the sequence */
  96   virtual uint count(uint c);
  97
  98   /** Returns the size of the structure in bytes */
  99   virtual uint size()=0;
 100
 101   /** Stores the bitmap given a file pointer, return 0 in case of success */
 102   virtual uint save(FILE * fp)=0;
 103
 104         virtual bool test(uint * seq, uint n);
 105
 106   /** Reads a bitmap determining the type */
 107   static static_sequence * load(FILE * fp);
 108
 109 protected:
 110   /** Length of the bitstring */
 111   uint len;
 112
 113 };
 114
 115 #include <static_sequence_wvtree.h>
 116 #include <static_sequence_gmr_chunk.h>
 117 #include <static_sequence_wvtree_noptrs.h>
 118 #include <static_sequence_gmr.h>
 119 #include <static_sequence_bs.h>
 120
 121 #endif  /* _STATIC_SEQUENCE_H */