package grenier

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Basic ordering operations
1. Memory management

package grenier

grenier.balmap
- Balmap
  - Map
    
    Make
    
    O
  - Set
    
    Make
    
    O
grenier.baltree
- Bt1
- Bt2
- Mbt
  - MEASURE
  - Make
    
    M
grenier.binpacking
- Maxrects
grenier.dbseq
- Dbseq
grenier.doubledouble
- Doubledouble
  - Infix
grenier.fastdom
- Fastdom
grenier.hll
- Hll
- Hll_consts
grenier.jmphash
- Jmphash
grenier.orderme
grenier.physh
- Physh
  - Map
  - Set
grenier.state_elimination
- State_elimination
  - Convert
    
    NFA
    
    Finals
    
    Initials
    
    States
    
    Transitions
    
    Regex
  - NFA
    
    Finals
    
    Initials
    
    States
    
    Transitions
  - Regex
grenier.strong
- Strong
  - Finite
    
    Array
    
    Of_array
    
    A
    
    T
    
    Elt
    
    Set
    
    Gensym
  - Natural
    
    Nth
    
    N
    
    T
  - Order
grenier.trope
- Trope
grenier.valmari
- Partition
- Valmari
  - DFA
  - INPUT
  - Minimize
    
    In
    
    Label

Legend:
Library
Module
Module type
Parameter
Class
Class type

Basic ordering operations

type t

An element of an ordering.

val root : unit -> t

Create a new ordering with a single element. O(1)

val after : t -> t

after t inserts a new element to the ordering, greater than t but less than all existing elements greater than t.

O(1) amortized.

val before : t -> t

before t inserts a new element to the ordering, less than t but greater than all existing elements less than t.

O(1) amortized.

val inside : t -> t

val outside : t -> t

val same_order : t -> t -> bool

Check if two elements belong to the same order. O(1)

type rel =

| Before
| Inside
| Equal
| Outside
| After

Compare two elements. O(1)

val compare : t -> t -> rel

val cardinal : t -> int

How many elements are ordered. O(1)

Memory management

val forget : t -> unit

When you know you are not going to use an element any longer, forget it to release memory. It makes operations slightly faster to not have to wait for the GC to release elements.

val is_valid : t -> bool

After calling forget, an element should not be used. You can check if it is the case with is_valid.

Algorithm due to: Two Simplified Algorithms for Maintaining Order in a List Bender et al., 2002

val unsafe_check : t -> string -> unit