## tagged-numbered-list.api
# Compiled by:
# src/lib/std/standard.lib# Compare to:
# src/lib/src/numbered-list.api# src/lib/src/numbered-list.api# src/lib/src/map.api# src/lib/src/set.api# Abstract api for applicative-style
# (side-effect free) sequences.
#
# By a "sequence" we here mean essentially a
# numbered list. Our motivation is to support
# such things as representing a text document in
# memory as a sequence of lines supporting easy
# insertion and deletion of lines for editing.
#
# Somewhat more formally, we take an "impure sequence" to
# be some values numbered 0..N together with "efficient"
# (O(log(N)) or so) implementations of the following
# operations:
#
# th
# FIND i value.
#
# INDEX_OF: Find current index of a
# previously inserted value -- that is,
# 'i' such that find(i) yields that value.
# (Support for this operation is the
# main advantage of Tagged_Numbered_List over Sequence.)
#
# th
# INSERT a value at i slot, renumbering so that
# previous items (i..N) become items (i+1 .. N+1)
#
# th
# REMOVE i value, renumbering so that
# previous items (i+1 .. N) become items (i .. N-1).
#
# This is essentially what in the literature is called
# "the order maintenance problem" or "an order datastructure":
#
# Two Algorithms for Maintaining Order in a List
# Dietz & Slater 1988: http://www.cs.cmu.edu/~sleator/papers/maintaining-order.html
#
# Two Simplified Algorithms for Maintaining Order in a List
# Bender, Cole &al 2002: http://citeseer.ist.psu.edu/bender02two.html
#
# The above go to great lengths to shave off a factor of O(log(N)):
# We don't worry about that here.
# This api is implemented in:
# src/lib/src/red-black-tagged-numbered-list.pkg#
api Tagged_Numbered_List {
Tagged_Numbered_List(X);
Tag(X);
is_empty: Tagged_Numbered_List(X) -> Bool; # Return TRUE if and only if the sequence is empty
# from_list: List(X) -> Tagged_Numbered_List(X); # Build a Order from the contents of a list.
empty: Tagged_Numbered_List(X);
# tag_value: Tag(X) -> X;
set: (Tagged_Numbered_List(X), Int, X) -> (Tagged_Numbered_List(X), Tag(X));
set' : ((((Int, X)), Tagged_Numbered_List(X)) ) -> (Tagged_Numbered_List(X), Tag(X));
($): (Tagged_Numbered_List(X), (Int, X)) -> Tagged_Numbered_List(X);
#
# Insert a keyval.
# find_tag: Tag(X) -> Int; # Return number of nodes preceding tagged node in sequence.
# nth_tag # Find n-th tag, return (THE tag) if it exists else NULL.
# :
# (Tagged_Numbered_List(X), Int)
# ->
# Null_Or( Tag(X) );
find # Find n-th val, return (THE val) if it exists else NULL.
:
(Tagged_Numbered_List(X), Int)
->
Null_Or(X);
# Note: The (_[]) enables 'vec[index]' notation;
sub: (Tagged_Numbered_List(X), Int) -> X;
(_[]): (Tagged_Numbered_List(X), Int) -> X;
# min_key: Tagged_Numbered_List(X) -> Null_Or Int; # Always THE 0.
# max_key: Tagged_Numbered_List(X) -> Null_Or Int; #
#
# contains_key # Return TRUE, iff the key is in the domain of the sequence
# :
# ((Tagged_Numbered_List(X), Int))
# ->
# Bool;
#
# remove # Remove i-th value from a tagged sequence.
# : # Raises lib_base::NOT_FOUND if not found.
# (
# Tagged_Numbered_List(X),
# Int
# )
# ->
# Tagged_Numbered_List(X);
#
# first_val_else_null: Tagged_Numbered_List(X) -> Null_Or(X);
# last_val_else_null: Tagged_Numbered_List(X) -> Null_Or(X);
# #
# # Return the first (last) item in the sequence (or NULL if it is empty)
#
# first_keyval_else_null: Tagged_Numbered_List(X) -> Null_Or( (Int, X) );
# last_keyval_else_null: Tagged_Numbered_List(X) -> Null_Or( (Int, X) );
# #
# # Return the first (last) keyval pair in the sequence (or NULL if it is empty)
#
# shift: Tagged_Numbered_List(X) -> Null_Or( (Tagged_Numbered_List(X), X) ); # Remove and return first item in sequence.
# pop: Tagged_Numbered_List(X) -> Null_Or( (Tagged_Numbered_List(X), X) ); # Remove and return last value in sequence.
# push: (Tagged_Numbered_List(X), X) -> Tagged_Numbered_List(X); # Append new value to sequence.
# unshift: (Tagged_Numbered_List(X), X) -> Tagged_Numbered_List(X); # Prepend new value to sequence.
vals_count: Tagged_Numbered_List(X) -> Int;
#
# Return the number of items in the sequence
# vals_list: Tagged_Numbered_List(X) -> List(X);
#
# keyvals_list: Tagged_Numbered_List(X) -> List( (Int, X) );
# #
# # Return an ordered list of the items (and their keys) in the sequence.
#
# keys_list: Tagged_Numbered_List(X) -> List Int;
# #
# # Return an ordered list of the keys in the sequence.
#
# compare_sequences # Given an ordering on the sequence's elements,
# : # return an ordering on the sequence.
# ((X, X) -> Order)
# ->
# (Tagged_Numbered_List(X), Tagged_Numbered_List(X))
# ->
# Order;
#
# union_with: ((X, X) -> X) -> ((Tagged_Numbered_List(X), Tagged_Numbered_List(X))) -> Tagged_Numbered_List(X);
# keyed_union_with: ((Int, X, X) -> X) -> ((Tagged_Numbered_List(X), Tagged_Numbered_List(X))) -> Tagged_Numbered_List(X);
# #
# # Return a sequence whose domain is the union of the domains of the two input
# # sequences, using the supplied function to define the sequence on elements that
# # are in both domains.
#
# intersect_with: ((X, Y) -> Z) -> ((Tagged_Numbered_List(X), Tagged_Numbered_List(Y))) -> Tagged_Numbered_List(Z);
# keyed_intersect_with: ((Int, X, Y) -> Z) -> ((Tagged_Numbered_List(X), Tagged_Numbered_List(Y))) -> Tagged_Numbered_List(Z);
# #
# # Return a sequence whose domain is the intersection of the domains of the
# # two input sequences, using the supplied function to define the range.
#
#
#
# merge_with
# :
# ((Null_Or(X), Null_Or(Y)) -> Null_Or(Z))
# ->
# ((Tagged_Numbered_List(X), Tagged_Numbered_List(Y)))
# ->
# Tagged_Numbered_List(Z);
#
# keyed_merge_with
# :
# ((Int, Null_Or(X), Null_Or(Y)) -> Null_Or(Z))
# ->
# ((Tagged_Numbered_List(X), Tagged_Numbered_List(Y)))
# ->
# Tagged_Numbered_List(Z);
# #
# # Merge two sequences using the given function to control the merge.
# # For each key k in the union of the two sequences domains, the function
# # is applied to the image of the key under the sequence. If the function
# # returns THE y, then (k, y) is added to the resulting sequence.
#
# apply: (X -> Void) -> Tagged_Numbered_List(X) -> Void;
# keyed_apply: (((Int, X)) -> Void) -> Tagged_Numbered_List(X) -> Void;
# #
# # Apply a function to the entries of the sequence in sequence order.
#
# map: (X -> Y) -> Tagged_Numbered_List(X) -> Tagged_Numbered_List(Y);
# keyed_map: ((Int, X) -> Y) -> Tagged_Numbered_List(X) -> Tagged_Numbered_List(Y);
# #
# # Create a new sequence by applying a sequence function to the
# # name/value pairs in the sequence.
#
# fold_forward: ((X, Y) -> Y) -> Y -> Tagged_Numbered_List(X) -> Y;
# keyed_fold_forward: ((Int, X, Y) -> Y) -> Y -> Tagged_Numbered_List(X) -> Y;
# #
# # Apply a folding function to the entries of the sequence
# # in increasing sequence order.
#
# fold_backward: ((X, Y) -> Y) -> Y -> Tagged_Numbered_List(X) -> Y;
# keyed_fold_backward: ((Int, X, Y) -> Y) -> Y -> Tagged_Numbered_List(X) -> Y;
# #
# # Apply a folding function to the entries of the sequence
# # in decreasing sequence order.
#
# filter: (X -> Bool) -> Tagged_Numbered_List(X) -> Tagged_Numbered_List(X);
# keyed_filter: ((Int, X) -> Bool) -> Tagged_Numbered_List(X) -> Tagged_Numbered_List(X);
# #
# # Filter out those elements of the sequence that do not satisfy the
# # predicate. The filtering is done in increasing sequence order.
#
# map': (X -> Null_Or(Y)) -> Tagged_Numbered_List(X) -> Tagged_Numbered_List(Y);
# keyed_map': ((Int, X) -> Null_Or(Y)) -> Tagged_Numbered_List(X) -> Tagged_Numbered_List(Y);
# #
# # Map a partial function over the elements of a sequence in increasing
# # sequence order.
all_invariants_hold: Tagged_Numbered_List(X) -> Bool;
debug_print: (Tagged_Numbered_List(X), X -> Void) -> Int;
}; # Tagged_Numbered_List
## COPYRIGHT (c) 1996 by AT&T Research. See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.