Update: libcds WT, empty texts in bitv.

[SXSI/TextCollection.git] / RLWaveletTree.h

diff --git a/RLWaveletTree.h b/RLWaveletTree.h
new file mode 100644 (file)
index 0000000..f3ed9ed
--- /dev/null
+++ b/RLWaveletTree.h
@@ -0,0 +1,64 @@
+/***************************************************************************
+ *   Copyright (C) 2007 by Veli Mäkinen                                    *
+ *                                                                         *
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ *   This program is distributed in the hope that it will be useful,       *
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
+ *   GNU General Public License for more details.                          *
+ *                                                                         *
+ *   You should have received a copy of the GNU General Public License     *
+ *   along with this program; if not, write to the                         *
+ *   Free Software Foundation, Inc.,                                       *
+ *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.         *
+ ***************************************************************************/
+
+/*
+ * Wavelet tree by Veli Mäkinen,
+ */
+
+#ifndef _RLWAVELETTREE_H_
+#define _RLWAVELETTREE_H_
+#include "GapEncode.h"
+#include "Tools.h"
+#include "BitRank.h"
+
+class RLWaveletTree {
+private:
+       ulong n;
+       ulong maxlevel;
+       ulong *leaves; // stores the leaf positions of characters 0..2^maxlevel-1
+        GapEncode *bitrank;
+        BitRank *charMap;
+        void remapAlphabet(uchar*, ulong);
+
+        ulong prevRunLen; // Used by charAtPosRun()
+        ulong prevPos;
+        ulong prevChar;
+        ulong prevRank;
+public:            
+    RLWaveletTree(uchar *, ulong);
+    RLWaveletTree(FILE *);
+    ~RLWaveletTree();
+
+    void Save(FILE *) const;
+   ulong rank(ulong c, ulong i);
+    
+   ulong select(ulong c, ulong j);
+        
+   bool IsCharAtPos(ulong c, ulong i);
+
+   ulong charAtPos(ulong i);
+   ulong charAtPos(ulong i, ulong *rank);
+   ulong charAtPosRun(ulong i, ulong *rank);
+   double spaceInBits() {
+       return 0; // Not implemented
+   }
+};
+
+#endif