libcds/src/static_permutation/perm.h

   1 /* perm.h
   2  * Copyright (C) 2005, Diego Arroyuelo, all rights reserved.
   3  *
   4  * Permutation
   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 PERMINCLUDED
  23 #define PERMINCLUDED
  24
  25 #include <basics.h>
  26 #include <static_bitsequence.h>
  27 #include <static_bitsequence_builder.h>
  28
  29 typedef struct sperm
  30 {
  31   uint *elems;                   // elements of the permutation
  32   uint nelems;                   // # of elements
  33   static_bitsequence * bmap;                   // bitmap allowing rank() queries in O(1) time
  34   uint *bwdptrs;                 // array of backward pointers
  35   uint nbits;                    // log(nelems)
  36   uint nbwdptrs;                 // # of backward pointers
  37   uint t;
  38 } *perm;
  39
  40 typedef struct
  41 {
  42   uint key;
  43   uint pointer;
  44 } auxbwd;
  45
  46 /** Creates a permutation
  47  *
  48  *  @author Diego Arroyuelo
  49  */
  50 perm createPerm(uint *elems, uint nelems, uint t, static_bitsequence_builder * bmb);
  51
  52 /** Gets the i-th element of the permutation
  53  *
  54  *  @author Diego Arroyuelo
  55  */
  56 uint getelemPerm(perm P, uint i);
  57
  58 /** Destroys a permutation
  59  *
  60  *  @author Diego Arroyuelo
  61  */
  62 void destroyPerm(perm P);
  63
  64 /** Get pi(i)^{-1}
  65  *
  66  *  @author Diego Arroyuelo
  67  */
  68 uint inversePerm(perm P, uint i);
  69
  70 /** Saves a permutation
  71  *
  72  *  @author Diego Arroyuelo
  73  */
  74 uint savePerm(perm P, FILE *f);
  75
  76 /** Loads a permutation
  77  *
  78  *  @author Diego Arroyuelo
  79  */
  80 perm loadPerm(FILE *f);
  81
  82 /** Returns the size of the data structure
  83  *
  84  *  @author Diego Arroyuelo
  85  */
  86 uint sizeofPerm(perm P);
  87
  88 #endif