key.tex

\documentclass[11pt]{article} 
\usepackage[latin1]{inputenc} 
\usepackage[T1]{fontenc} 
\usepackage{textcomp}
\usepackage{fullpage} 
\usepackage{url} 
\usepackage{ocamldoc}
\begin{document}
\tableofcontents
\section{Module {\tt{Key}} : Implementation of a triply-linked list, an extension of a doubly linked
    list.}
\label{module:Key}\index{Key@\verb`Key`}
 A node in a triply linked list serves one of three purposes:


    \begin{itemize}
\item {\tt{DictEnd}} - the end of the list
\item {\tt{Bridge}} - a linked list node. A {\tt{Bridge}} node represents a key in
    common between one or several lists, and the lists are maintained as
    a map from dictionary id to link.
\end{itemize}



    For now, the types of {\tt{dict\_id\_t}} and {\tt{val\_t}} have been hardcoded into
    the system, but later they could be modularized using a functor.



\ocamldocvspace{0.5cm}



\label{type:Key.dict-underscoreid-underscoret}\begin{ocamldoccode}
type dict_id_t = string 
\end{ocamldoccode}
\index{dict-underscoreid-underscoret@\verb`dict_id_t`}
\begin{ocamldocdescription}
The type of the identifier for the dictionary.


\end{ocamldocdescription}




\label{type:Key.val-underscoret}\begin{ocamldoccode}
type val_t = string 
\end{ocamldoccode}
\index{val-underscoret@\verb`val_t`}
\begin{ocamldocdescription}
The type of the value of nodes in the list.


\end{ocamldocdescription}




\begin{ocamldoccode}
{\tt{module }}{\tt{StringMap}}{\tt{ : }}\end{ocamldoccode}
\label{module:Key.StringMap}\index{StringMap@\verb`StringMap`}

{\tt{Map.Make}}{\tt{(}}\begin{ocamldocsigend}


\label{type:Key.StringMap.t}\begin{ocamldoccode}
type t = Key.dict_id_t 
\end{ocamldoccode}
\index{t@\verb`t`}


\label{val:Key.StringMap.compare}\begin{ocamldoccode}
val compare : {\textquotesingle}a -> {\textquotesingle}a -> int
\end{ocamldoccode}
\index{compare@\verb`compare`}
\end{ocamldocsigend}
{\tt{)}}

\begin{ocamldocdescription}
Internal module to maintain owner set.


\end{ocamldocdescription}




\begin{ocamldoccode}
{\tt{module }}{\tt{StringSet}}{\tt{ : }}\end{ocamldoccode}
\label{module:Key.StringSet}\index{StringSet@\verb`StringSet`}

{\tt{Set.Make}}{\tt{(}}\begin{ocamldocsigend}


\label{type:Key.StringSet.t}\begin{ocamldoccode}
type t = Key.dict_id_t 
\end{ocamldoccode}
\index{t@\verb`t`}


\label{val:Key.StringSet.compare}\begin{ocamldoccode}
val compare : {\textquotesingle}a -> {\textquotesingle}a -> int
\end{ocamldoccode}
\index{compare@\verb`compare`}
\end{ocamldocsigend}
{\tt{)}}

\begin{ocamldocdescription}
Internal module to maintain link map.


\end{ocamldocdescription}




\label{type:Key.t}\begin{ocamldoccode}
type t =
  | DictEnd
\end{ocamldoccode}
\begin{ocamldoccomment}
Indicates the end of the list.
\end{ocamldoccomment}
\begin{ocamldoccode}
  | Bridge of bridge_t
\end{ocamldoccode}
\begin{ocamldoccomment}
Indicates a bridge node between
              one or several lists.
\end{ocamldoccomment}
\index{t@\verb`t`}
\begin{ocamldocdescription}
The basic key type.


\end{ocamldocdescription}




\label{type:Key.link-underscoret}\begin{ocamldoccode}
type link_t = {\char123}
  mutable next : t ;
\end{ocamldoccode}
\begin{ocamldoccomment}
The next key in the list
\end{ocamldoccomment}
\begin{ocamldoccode}
  mutable prev : t ;
\end{ocamldoccode}
\begin{ocamldoccomment}
The previous key in the list
\end{ocamldoccomment}
\begin{ocamldoccode}
{\char125}
\end{ocamldoccode}
\index{link-underscoret@\verb`link_t`}
\begin{ocamldocdescription}
{\tt{link\_t}} represents a link to keys before and after the current item.
    It is used in the {\tt{Bridge}} node inside a map.


\end{ocamldocdescription}




\label{type:Key.bridge-underscoret}\begin{ocamldoccode}
type bridge_t = {\char123}
  bvalue : val_t ;
\end{ocamldoccode}
\begin{ocamldoccomment}
The value of the {\tt{Bridge}} node.
\end{ocamldoccomment}
\begin{ocamldoccode}
  owners : StringSet.t ;
\end{ocamldoccode}
\begin{ocamldoccomment}
The set of owners of the value
                     in this node.
\end{ocamldoccomment}
\begin{ocamldoccode}
  mutable links : link_t StringMap.t ;
\end{ocamldoccode}
\begin{ocamldoccomment}
The set of
                dictionaries which this node is linked to.
\end{ocamldoccomment}
\begin{ocamldoccode}
{\char125}
\end{ocamldoccode}
\index{bridge-underscoret@\verb`bridge_t`}
\begin{ocamldocdescription}
{\tt{bridge\_t}} is the type of a {\tt{Bridge}} node. A {\tt{Bridge}} node uses a
    {\tt{StringMap}} to keep track of which dictionaries this node is included
    in.


\end{ocamldocdescription}




\label{val:Key.empty-underscorelink}\begin{ocamldoccode}
val empty_link : unit -> link_t
\end{ocamldoccode}
\index{empty-underscorelink@\verb`empty_link`}
\begin{ocamldocdescription}
Creates an empty link.


\end{ocamldocdescription}




\label{val:Key.create}\begin{ocamldoccode}
val create : val_t -> StringMap.key -> t
\end{ocamldoccode}
\index{create@\verb`create`}
\begin{ocamldocdescription}
Creates a simple key containing {\tt{value}} for dictionary {\tt{did}}.


\end{ocamldocdescription}




\label{val:Key.belongs-underscoreto}\begin{ocamldoccode}
val belongs_to : StringSet.elt -> t -> bool
\end{ocamldoccode}
\index{belongs-underscoreto@\verb`belongs_to`}
\begin{ocamldocdescription}
Tests whether the input node belongs to {\tt{dict}}.


\end{ocamldocdescription}




\label{val:Key.add-underscorelink}\begin{ocamldoccode}
val add_link : t -> StringMap.key -> unit
\end{ocamldoccode}
\index{add-underscorelink@\verb`add_link`}
\begin{ocamldocdescription}
Adds a link to {\tt{did}} in node {\tt{key}}.


\end{ocamldocdescription}




\label{exception:Key.No-underscorelink}\begin{ocamldoccode}
exception No_link
\end{ocamldoccode}
\index{No-underscorelink@\verb`No_link`}
\begin{ocamldocdescription}
An exception that is thrown when trying to get the link of a
    {\tt{DictEnd}} node.


\end{ocamldocdescription}




\label{val:Key.get-underscorelink}\begin{ocamldoccode}
val get_link : StringMap.key -> t -> link_t
\end{ocamldoccode}
\index{get-underscorelink@\verb`get_link`}
\begin{ocamldocdescription}
Returns the link for the node for dictionary {\tt{dict}}, raising {\tt{No\_link}}
    if the node is a {\tt{DictEnd}}. If the node doesn't contain a link for
    {\tt{dict}}, then a link is added to the node and the new link is returned.


\end{ocamldocdescription}




\label{val:Key.insert-underscoreafter}\begin{ocamldoccode}
val insert_after : t -> t -> StringMap.key -> t
\end{ocamldoccode}
\index{insert-underscoreafter@\verb`insert_after`}
\begin{ocamldocdescription}
Inserts {\tt{ins}} immediately after {\tt{key}} in dictionary {\tt{dict}}, 
    returning the new {\tt{ins}} node.


\end{ocamldocdescription}




\label{val:Key.insert-underscorebefore}\begin{ocamldoccode}
val insert_before : t -> t -> StringMap.key -> t
\end{ocamldoccode}
\index{insert-underscorebefore@\verb`insert_before`}
\begin{ocamldocdescription}
Inserts {\tt{ins}} immediately before {\tt{key}} in dictionary {\tt{dict}}, 
    returning the new {\tt{ins}} node.


\end{ocamldocdescription}




\label{val:Key.to-underscorelist}\begin{ocamldoccode}
val to_list : t -> StringMap.key -> val_t list
\end{ocamldoccode}
\index{to-underscorelist@\verb`to_list`}
\begin{ocamldocdescription}
Converts a triply-linked list into a regular list starting with node
    {\tt{key}} and using the {\tt{dict}} link in any {\tt{Bridge}} nodes.


\end{ocamldocdescription}




\label{val:Key.prev-underscorekey}\begin{ocamldoccode}
val prev_key : t -> StringMap.key -> t
\end{ocamldoccode}
\index{prev-underscorekey@\verb`prev_key`}
\begin{ocamldocdescription}
Returns the key before {\tt{key}} in {\tt{did}}.


\end{ocamldocdescription}




\label{val:Key.next-underscorekey}\begin{ocamldoccode}
val next_key : t -> StringMap.key -> t
\end{ocamldoccode}
\index{next-underscorekey@\verb`next_key`}
\begin{ocamldocdescription}
Returns the key after {\tt{key}} in {\tt{did}}.


\end{ocamldocdescription}




\label{val:Key.is-underscorebridge}\begin{ocamldoccode}
val is_bridge : t -> bool
\end{ocamldoccode}
\index{is-underscorebridge@\verb`is_bridge`}
\begin{ocamldocdescription}
Returns true if the node is a {\tt{Bridge}}.


\end{ocamldocdescription}




\label{val:Key.value}\begin{ocamldoccode}
val value : t -> val_t
\end{ocamldoccode}
\index{value@\verb`value`}
\begin{ocamldocdescription}
Returns the value of a node, failing on DictEnd.


\end{ocamldocdescription}


\end{document}