X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_permutation%2Fperm.h;fp=libcds%2Fsrc%2Fstatic_permutation%2Fperm.h;h=20d0bf6175b5e76e6c052197efdbf10e265e9397;hb=60f0f1a447b2b89ca99589c68333d72bcdeb263d;hp=0000000000000000000000000000000000000000;hpb=52cb7bbcda67f4676335cdd4eb96d4d87ad1445d;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_permutation/perm.h b/libcds/src/static_permutation/perm.h
new file mode 100755
index 0000000..20d0bf6
--- /dev/null
+++ b/libcds/src/static_permutation/perm.h
@@ -0,0 +1,88 @@
+/* perm.h
+ * Copyright (C) 2005, Diego Arroyuelo, all rights reserved.
+ *
+ * Permutation
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
+
+#ifndef PERMINCLUDED
+#define PERMINCLUDED
+
+#include <basics.h>
+#include <static_bitsequence.h>
+#include <static_bitsequence_builder.h>
+
+typedef struct sperm
+{
+  uint *elems;                   // elements of the permutation
+  uint nelems;                   // # of elements
+  static_bitsequence * bmap;                   // bitmap allowing rank() queries in O(1) time
+  uint *bwdptrs;                 // array of backward pointers
+  uint nbits;                    // log(nelems)
+  uint nbwdptrs;                 // # of backward pointers
+  uint t;
+} *perm;
+
+typedef struct
+{
+  uint key;
+  uint pointer;
+} auxbwd;
+
+/** Creates a permutation
+ *  
+ *  @author Diego Arroyuelo
+ */
+perm createPerm(uint *elems, uint nelems, uint t, static_bitsequence_builder * bmb);
+
+/** Gets the i-th element of the permutation
+ *  
+ *  @author Diego Arroyuelo
+ */
+uint getelemPerm(perm P, uint i);
+
+/** Destroys a permutation
+ *  
+ *  @author Diego Arroyuelo
+ */
+void destroyPerm(perm P);
+
+/** Get pi(i)^{-1}
+ *  
+ *  @author Diego Arroyuelo
+ */
+uint inversePerm(perm P, uint i);
+
+/** Saves a permutation
+ *  
+ *  @author Diego Arroyuelo
+ */
+uint savePerm(perm P, FILE *f);
+
+/** Loads a permutation
+ *  
+ *  @author Diego Arroyuelo
+ */
+perm loadPerm(FILE *f);
+
+/** Returns the size of the data structure
+ *  
+ *  @author Diego Arroyuelo
+ */
+uint sizeofPerm(perm P);
+
+#endif