it.unipi.di.rs
Class Rank

java.lang.Object
  extended by it.unipi.di.rs.Rank
All Implemented Interfaces:
IRankSelect

public class Rank
extends Object
implements IRankSelect

An index implementing the rank function over binary files. The index uses a two-level-bucketing system to store information about partial counts. It performs the rank operation in constant time and the select through a binary search.

Author:
Claudio Corsi, Paolo Ferragina, Alessandro Barilari

Field Summary
 
Fields inherited from interface it.unipi.di.rs.IRankSelect
DISK, MEMORY
 
Constructor Summary
Rank(String source)
          Creates an object and initializes basic data structures; it will be necessary to use a specific method to create data structures or load them.
Rank(String source, Directory tdb)
          Creates an object from a source contained in a Directory and initializes basic data structures; it will be necessary to use a specific method to create data structures or load them.
 
Method Summary
 long count1(long start, long end)
          Returns the number of 1s in the selected range of the source
 void createIndex(int mode)
          Creates the index in memory or on disk.
 void createIndex(int mode, float iPerc)
          Creates the index in memory or on disk using the specified amount of space
 void createIndex(int mode, int lbLen, int sbLen)
          Creates index data structures using specified lengths
 boolean get(long index)
          Returns the value at the specified position
static String getIndexFileName(String baseName)
          Generates the names of the file that will contain the index in case of store() operations
 long ISize()
          Returns the size in bits of the index
 void load()
          Loads the data structures from the default file(s)
 void load(Directory directory)
          This methods acts as IRankSelect.load(), but load data structures from a Directory
 int numLBRank()
          Returns the number of Large buckets
 int numSBRank()
          Returns the number of Small buckets
 long rank0(long pos)
          Returns the rank0 at the pos-th bit (starting from 0)
 long rank1(long pos)
          Returns the rank1 at the pos-th bit (starting from 0)
 long Scard()
          Returns the number of 1s in the source
 long select1(long rank)
          Returns the position of the rank-th 1 (starting from 0)
 int sizeLBRank()
          Returns the size of the Large buckets
 int sizeSBRank()
          Returns the size of the Small buckets
 long Ssize()
          Returns the size in bits of the source file.
 void store()
          Stores data structures in the default file(s).
 void store(Directory directory)
          This methods acts as IRankSelect.store(), but store data structures inside a Directory
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Rank

public Rank(String source)
     throws IOException
Creates an object and initializes basic data structures; it will be necessary to use a specific method to create data structures or load them.

Parameters:
source - the name of the source file
Throws:
IOException

Rank

public Rank(String source,
            Directory tdb)
     throws IOException
Creates an object from a source contained in a Directory and initializes basic data structures; it will be necessary to use a specific method to create data structures or load them.

Parameters:
source - the name of the source file inside the Directory
tdb - the Directory that contains the source
Throws:
IOException
Method Detail

getIndexFileName

public static String getIndexFileName(String baseName)
Generates the names of the file that will contain the index in case of store() operations

Parameters:
baseName - is the name from which generate the new names; tipically the name of the source of the index
Returns:
the name of the file that will contain main index data structures

sizeLBRank

public int sizeLBRank()
               throws IOException
Returns the size of the Large buckets

Returns:
the size in bits of the Large Buckets of the rank index
Throws:
IOException

sizeSBRank

public int sizeSBRank()
               throws IOException
Returns the size of the Small buckets

Returns:
the size in bits of the Small Buckets of the rank index
Throws:
IOException

numLBRank

public int numLBRank()
              throws IOException
Returns the number of Large buckets

Returns:
the number of Large Buckets in the index
Throws:
IOException

numSBRank

public int numSBRank()
              throws IOException
Returns the number of Small buckets

Returns:
the number of Small Buckets in the index
Throws:
IOException

Scard

public long Scard()
           throws IOException
Description copied from interface: IRankSelect
Returns the number of 1s in the source

Specified by:
Scard in interface IRankSelect
Throws:
IOException

Ssize

public long Ssize()
Description copied from interface: IRankSelect
Returns the size in bits of the source file.

Specified by:
Ssize in interface IRankSelect

ISize

public long ISize()
           throws IOException
Description copied from interface: IRankSelect
Returns the size in bits of the index

Specified by:
ISize in interface IRankSelect
Throws:
IOException

createIndex

public void createIndex(int mode)
                 throws IOException
Description copied from interface: IRankSelect
Creates the index in memory or on disk.

Specified by:
createIndex in interface IRankSelect
Parameters:
mode - the mode of creation (IRankSelect.MEMORY or IRankSelect.DISK)
Throws:
IOException

createIndex

public void createIndex(int mode,
                        float iPerc)
                 throws IOException
Description copied from interface: IRankSelect
Creates the index in memory or on disk using the specified amount of space

Specified by:
createIndex in interface IRankSelect
Parameters:
mode - the mode of creation (IRankSelect.MEMORY or IRankSelect.DISK)
iPerc - is the space occupancy in terms of % of the source dimension that the index must achieve
Throws:
IOException

createIndex

public void createIndex(int mode,
                        int lbLen,
                        int sbLen)
                 throws IOException
Creates index data structures using specified lengths

Parameters:
mode - the mode of creation
lbLen - dimension of first-level buckets
sbLen - dimension of second-level buckets
Throws:
YQLException
IOException

rank0

public long rank0(long pos)
           throws IOException
Description copied from interface: IRankSelect
Returns the rank0 at the pos-th bit (starting from 0)

Specified by:
rank0 in interface IRankSelect
Parameters:
pos - is the position to analyze
Throws:
IOException

rank1

public long rank1(long pos)
           throws IOException
Description copied from interface: IRankSelect
Returns the rank1 at the pos-th bit (starting from 0)

Specified by:
rank1 in interface IRankSelect
Parameters:
pos - is the position to analyze
Throws:
IOException

select1

public long select1(long rank)
             throws IOException
Description copied from interface: IRankSelect
Returns the position of the rank-th 1 (starting from 0)

Specified by:
select1 in interface IRankSelect
Parameters:
rank - is the rank to find
Throws:
IOException

load

public void load()
          throws IOException
Description copied from interface: IRankSelect
Loads the data structures from the default file(s)

Specified by:
load in interface IRankSelect
Throws:
IOException

load

public void load(Directory directory)
          throws IOException
Description copied from interface: IRankSelect
This methods acts as IRankSelect.load(), but load data structures from a Directory

Specified by:
load in interface IRankSelect
Parameters:
directory - the source Directory; must be opened in READ_MODE
Throws:
IOException

store

public void store()
           throws IOException
Description copied from interface: IRankSelect
Stores data structures in the default file(s). Previous data contained in the output file will be deleted.

Specified by:
store in interface IRankSelect
Throws:
IOException

store

public void store(Directory directory)
           throws IOException
Description copied from interface: IRankSelect
This methods acts as IRankSelect.store(), but store data structures inside a Directory

Specified by:
store in interface IRankSelect
Parameters:
directory - the destination Directory; must be opened in WRITE_MODE
Throws:
IOException

count1

public long count1(long start,
                   long end)
            throws IOException
Description copied from interface: IRankSelect
Returns the number of 1s in the selected range of the source

Specified by:
count1 in interface IRankSelect
Returns:
the number of 1s in the range [start, end]
Throws:
IOException

get

public boolean get(long index)
            throws IOException
Description copied from interface: IRankSelect
Returns the value at the specified position

Specified by:
get in interface IRankSelect
Returns:
the boolean value of the i-th bit of the source (starting from 0)
Throws:
IOException