## numbered-list.api
# Compiled by:
# src/lib/std/standard.lib# Compare to:
# src/lib/src/numbered-list.api# src/lib/src/tagged-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 a "sequence" to
# be some values (not necessarily all distinct)
# numbered 0..N together with "efficient"
# (O(log(N)) or so) implementations of the
# following operations:
#
# th
# FIND i value.
#
# 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 api is implemented in:
#
# src/lib/src/red-black-numbered-list.pkg#
api Numbered_List {
#
Numbered_List(X);
empty: Numbered_List(X); # The empty Numbered_List.
is_empty: Numbered_List(X) -> Bool; # Return TRUE if and only if the sequence is empty
from_list: List(X) -> Numbered_List(X); # Build a Numbered_List from the contents of a list.
singleton: X -> Numbered_List(X); # Return the specified singleton sequence
set: (Numbered_List(X), Int, X) -> Numbered_List(X);
set' : ((((Int, X)), Numbered_List(X)) ) -> Numbered_List(X);
($): (Numbered_List(X), (Int, X)) -> Numbered_List(X);
#
# Insert a keyval.
find # Look for an item, return NULL if the item doesn't exist
:
(Numbered_List(X), Int)
->
Null_Or(X);
# Note: The (_[]) enables 'vec[index]' notation;
get: (Numbered_List(X), Int) -> X; # Raises exception exceptions::INDEX_OUT_OF_BOUNDS; if index is invalid.
(_[]): (Numbered_List(X), Int) -> X; # Raises exception exceptions::INDEX_OUT_OF_BOUNDS; if index is invalid.
min_key: Numbered_List(X) -> Null_Or Int; # NULL if list is empty, otherwise THE 0.
max_key: Numbered_List(X) -> Null_Or Int; # NULL if list is empty, otherwise THE maxnumber.
contains_key # Return TRUE, iff the key is in the domain of the sequence
:
((Numbered_List(X), Int))
->
Bool;
remove # Remove i-th value from a Numbered_List, returning new sequence.
: # Raises lib_base::NOT_FOUND if not found.
( Numbered_List(X),
Int
)
->
Numbered_List(X);
first_val_else_null: Numbered_List(X) -> Null_Or(X);
last_val_else_null: Numbered_List(X) -> Null_Or(X);
#
# Return the first (last) item in the sequence (or NULL if it is empty)
first_keyval_else_null: Numbered_List(X) -> Null_Or( (Int, X) );
last_keyval_else_null: Numbered_List(X) -> Null_Or( (Int, X) );
#
# Return the first (last) keyval pair in the sequence (or NULL if it is empty)
shift: Numbered_List(X) -> Null_Or( Numbered_List(X) ); # Remove first item from sequence and return shortened sequence.
pop: Numbered_List(X) -> Null_Or( Numbered_List(X) ); # Remove last item from sequence and return shortened sequence.
push: (Numbered_List(X), X) -> Numbered_List(X); # Append new value to sequence.
unshift: (Numbered_List(X), X) -> Numbered_List(X); # Prepend new value to sequence.
vals_count: Numbered_List(X) -> Int;
#
# Return the number of items in the sequence
vals_list: Numbered_List(X) -> List(X);
keyvals_list: Numbered_List(X) -> List( (Int, X) );
#
# Return an ordered list of the items (and their keys) in the sequence.
keys_list: Numbered_List(X) -> List Int;
#
# Return an ordered list of the keys in the sequence.
compare_sequences # Given an ordering on the sequence's range,
: # return an ordering on the sequence.
((X, X) -> Order)
->
(Numbered_List(X), Numbered_List(X))
->
Order;
union_with: ((X, X) -> X) -> ((Numbered_List(X), Numbered_List(X))) -> Numbered_List(X);
keyed_union_with: ((Int, X, X) -> X) -> ((Numbered_List(X), Numbered_List(X))) -> 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) -> ((Numbered_List(X), Numbered_List(Y))) -> Numbered_List(Z);
keyed_intersect_with: ((Int, X, Y) -> Z) -> ((Numbered_List(X), Numbered_List(Y))) -> 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))
->
((Numbered_List(X), Numbered_List(Y)))
->
Numbered_List(Z);
keyed_merge_with
:
((Int, Null_Or(X), Null_Or(Y)) -> Null_Or(Z))
->
((Numbered_List(X), Numbered_List(Y)))
->
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) -> Numbered_List(X) -> Void;
keyed_apply: (((Int, X)) -> Void) -> Numbered_List(X) -> Void;
#
# Apply a function to the entries of the sequence in sequence order.
map: (X -> Y) -> Numbered_List(X) -> Numbered_List(Y);
keyed_map: ((Int, X) -> Y) -> Numbered_List(X) -> 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 -> Numbered_List(X) -> Y;
keyed_fold_forward: ((Int, X, Y) -> Y) -> Y -> Numbered_List(X) -> Y;
#
# Apply a folding function to the entries of the sequence
# in increasing sequence order.
fold_backward: ((X, Y) -> Y) -> Y -> Numbered_List(X) -> Y;
keyed_fold_backward: ((Int, X, Y) -> Y) -> Y -> Numbered_List(X) -> Y;
#
# Apply a folding function to the entries of the sequence
# in decreasing sequence order.
filter: (X -> Bool) -> Numbered_List(X) -> Numbered_List(X);
keyed_filter: ((Int, X) -> Bool) -> Numbered_List(X) -> 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)) -> Numbered_List(X) -> Numbered_List(Y);
keyed_map': ((Int, X) -> Null_Or(Y)) -> Numbered_List(X) -> Numbered_List(Y);
#
# Map a partial function over the elements of a sequence in increasing
# sequence order.
all_invariants_hold: Numbered_List(X) -> Bool;
debug_print: (Numbered_List(X), X -> Void) -> Int;
}; # 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.