Import libcds.

[SXSI/libcds.git] / src / static_permutation / perm.h

diff --git a/src/static_permutation/perm.h b/src/static_permutation/perm.h
new file mode 100755 (executable)
index 0000000..20d0bf6
--- /dev/null
+++ b/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