M COPYING +1 -1
@@ 1,5 1,5 @@
- Copyright 2015-2018 Chris Cannam.
+ Copyright 2015-2021 Chris Cannam.
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
M README => README.md +74 -61
@@ 22,6 22,7 @@ entry type, which is some sort of sequen
storing them in a tree structure according to their common prefixes,
branching where they diverge.
+```
g - a - t - o - r*
/
a* - l - l* - i
@@ 29,6 30,7 @@ branching where they diverge.
. a - n - c - e* - s*
\
z - e - b - r - a*
+```
(The asterisk shows nodes marked as entries in the trie rather than
just potential branches, so this trie contains the six string entries
@@ 53,86 55,89 @@ one passed in, but internally sharing an
The main signatures are:
- * TRIE (trie.sig) - signature of a trie set container with arbitrary
- entry type
+ * `TRIE` (`trie.sig`) - signature of a trie set container with
+ arbitrary entry type
- * TRIE_MAP (trie-map.sig) - signature of a polymorphic-value trie map
- container with arbitrary key type
-
- * PATTERN_MATCH_TRIE (pattern-match-trie.sig) - signature extending
- TRIE with the capability of matching sequences with wildcards in
- them. Unlike TRIE, this exposes the types of the individual
- elements in each entry (e.g. char, for a trie with string entries)
+ * `TRIE_MAP` (`trie-map.sig`) - signature of a polymorphic-value trie
+ map container with arbitrary key type
- * PATTERN_MATCH_TRIE_MAP (pattern-match-trie-map.sig) - signature
- extending TRIE_MAP with the capability of matching sequences with
- wildcards in them, like PATTERN_MATCH_TRIE
+ * `PATTERN_MATCH_TRIE` (`pattern-match-trie.sig`) - signature
+ extending `TRIE` with the capability of matching sequences with
+ wildcards in them. Unlike `TRIE`, this exposes the types of the
+ individual elements in each entry (e.g. `char`, for a trie with
+ string entries)
-There is a single core trie map implementation provided: TrieMapFn, in
-trie-map-fn.sml. This is a functor parameterised by the node map type
-for the trie (which determines how sub-node relationships are stored)
-and the external key and entry types (which determine the API for the
-trie). All of the external concrete trie-map and trie structures are
-implemented using TrieMapFn internally.
+ * `PATTERN_MATCH_TRIE_MAP` (`pattern-match-trie-map.sig`) - signature
+ extending `TRIE_MAP` with the capability of matching sequences with
+ wildcards in them, like `PATTERN_MATCH_TRIE`
+
+There is a single core trie map implementation provided: `TrieMapFn`,
+in `trie-map-fn.sml`. This is a functor parameterised by the node map
+type for the trie (which determines how sub-node relationships are
+stored) and the external key and entry types (which determine the API
+for the trie). All of the external concrete trie-map and trie
+structures are implemented using `TrieMapFn` internally.
These functors then adapt trie-maps into set-type trie structures:
- * TrieFn (trie-fn.sml) - a functor that turns a TRIE_MAP into a TRIE
+ * `TrieFn` (`trie-fn.sml`) - a functor that turns a `TRIE_MAP` into a
+ `TRIE`
- * PatternMatchTrieFn (pattern-match-trie-fn.sml) - a functor that
- turns a PATTERN_MATCH_TRIE_MAP into a PATTERN_MATCH_TRIE
+ * `PatternMatchTrieFn` (`pattern-match-trie-fn.sml`) - a functor that
+ turns a `PATTERN_MATCH_TRIE_MAP` into a `PATTERN_MATCH_TRIE`
The following external interfaces are then provided in list-tries.sml:
- * ListMTrieMapFn - a functor that takes a comparable element type and
- implements a PATTERN_MATCH_TRIE_MAP in which the entry type is a
- list of that element. The implementation uses a red-black tree map
- (from the SML/NJ library) at every trie node. This is better suited
- to wide, shallow trie structures than narrow, deep ones, but can be
- surprisingly efficient in both time and space. Insertion and
+ * `ListMTrieMapFn` - a functor that takes a comparable element type
+ and implements a `PATTERN_MATCH_TRIE_MAP` in which the entry type
+ is a list of that element. The implementation uses a red-black tree
+ map (from the SML/NJ library) at every trie node. This is better
+ suited to wide, shallow trie structures than narrow, deep ones, but
+ can be surprisingly efficient in both time and space. Insertion and
enumeration are relatively cheap and lookup is relatively more
expensive.
- * ListATrieMapFn - a functor that takes an element type that can be
+ * `ListATrieMapFn` - a functor that takes an element type that can be
mapped compactly onto a small integer range, and implements a
- PATTERN_MATCH_TRIE_MAP in which the entry type is a list of that
+ `PATTERN_MATCH_TRIE_MAP` in which the entry type is a list of that
element. The implementation uses an array (or rather a vector) at
each node, extending the vector to span the range of inserted
- values. This may be better suited than ListMTrieMapFn to narrow,
+ values. This may be better suited than `ListMTrieMapFn` to narrow,
deep structures with small numbers of possible values at each
node. Lookups are relatively cheap and insertion is relatively more
expensive.
- * ListBTrieMapFn - a functor that takes an element type that can be
+ * `ListBTrieMapFn` - a functor that takes an element type that can be
mapped compactly onto a small integer range, and implements a
- PATTERN_MATCH_TRIE_MAP in which the entry type is a list of that
+ `PATTERN_MATCH_TRIE_MAP` in which the entry type is a list of that
element. The implementation uses a bitmap-compressed semi-sparse
array at each node. This is only suited to entries whose elements
map sparsely into a small range.
- * ListMTrieFn, ListATrieFn, ListBTrieFn (list-tries.sml) - shorthands
- that turn an element type directly into a trie set (the set
- equivalents of *TrieMapFn)
+ * `ListMTrieFn`, `ListATrieFn`, `ListBTrieFn` (`list-tries.sml`) -
+ shorthands that turn an element type directly into a trie set (the
+ set equivalents of `*TrieMapFn`)
For each of these tries with list entry types, an equivalent trie with
-a vector entry type is also provided, in vector-tries.sml:
+a vector entry type is also provided, in `vector-tries.sml`:
- * VectorMTrieMapFn, VectorATrieMapFn, VectorBTrieMapFn - vector
- equivalents of ListMTrieMapFn, ListATrieMapFn, ListBTrieMapFn
+ * `VectorMTrieMapFn`, `VectorATrieMapFn`, `VectorBTrieMapFn` - vector
+ equivalents of `ListMTrieMapFn`, `ListATrieMapFn`, `ListBTrieMapFn`
- * VectorMTrieFn, VectorATrieFn, VectorBTrieFn - vector equivalents
- of ListMTrieFn, ListATrieFn, ListBTrieFn
+ * `VectorMTrieFn`, `VectorATrieFn`, `VectorBTrieFn` - vector
+ equivalents of `ListMTrieFn`, `ListATrieFn`, `ListBTrieFn`
Finally there are specialisations for tries with string entries, found
-in string-tries.sml:
+in `string-tries.sml`:
- * StringMTrieMap, StringATrieMap, StringBTrieMap - trie-maps with
- string key type
+ * `StringMTrieMap`, `StringATrieMap`, `StringBTrieMap` - trie-maps
+ with string key type
- * StringMTrie, StringATrie, StringBTrie - trie sets with string key
- type
+ * `StringMTrie`, `StringATrie`, `StringBTrie` - trie sets with string
+ key type
- * StringTrieMap, StringTrie - aliases for StringMTrieMap, StringMTrie
+ * `StringTrieMap`, `StringTrie` - aliases for `StringMTrieMap`,
+ `StringMTrie`
2. PERSISTENT HASH MAP
@@ 159,14 164,14 @@ The main signature is:
And this is implemented by
- * PersistentHashMapFn (persistent-hash-map-fn.sml) - a functor that
- takes a hash key type and hash function and implements a
- PERSISTENT_HASH_MAP with that key type
+ * `PersistentHashMapFn` (`persistent-hash-map-fn.sml`) - a functor
+ that takes a hash key type and hash function and implements a
+ `PERSISTENT_HASH_MAP` with that key type
There is a specialisation for string keys:
- * StringHashMap (string-hash-map.sml) - a PERSISTENT_HASH_MAP with
- string keys
+ * `StringHashMap` (`string-hash-map.sml`) - a `PERSISTENT_HASH_MAP`
+ with string keys
3. PERSISTENT ARRAY AND QUEUE
@@ 177,9 182,9 @@ double-ended queue containers. These are
Basis vector with the addition of update, append, and pop-from-end
operations which return new (partly shared) containers. The queue
supports all of the same operations plus prepend and pop-from-start,
-but its plain iteration (foldl) is not as fast as the array. For both
-containers, all of the update, append, prepend, and pop operations
-take time independent of the container size.
+but its plain iteration (`foldl`) is not as fast as the array. For
+both containers, all of the update, append, prepend, and pop
+operations take time independent of the container size.
Note that these containers are competitive only if both immutability
and general updating are desired. A vector is faster to tabulate and
@@ 189,25 194,31 @@ if updating within the queue is not need
The implementations use an array-mapped-trie somewhat like that
popularised by the Clojure language. Both containers are limited in
-size to 2^32 elements or the maximum size of Int.int, whichever is
+size to 2^32 elements or the maximum size of `Int.int`, whichever is
smaller. The former is an implementation limit, the latter an artifact
of the choice of API. For the queue, the limit is of current queue
length, not of the total number of append/pop cycles.
The main signatures are:
- * PERSISTENT_ARRAY (persistent-array.sig) - signature of a
+ * `PERSISTENT_ARRAY` (`persistent-array.sig`) - signature of a
polymorphic-value persistent array container
- * PERSISTENT_QUEUE (persistent-queue.sig) - signature of a
+ * `PERSISTENT_ARRAY_SLICE` (`persistent-array-slice.sig`) - signature
+ of a slice into a `PERSISTENT_ARRAY`
+
+ * `PERSISTENT_QUEUE` (`persistent-queue.sig`) - signature of a
polymorphic-value persistent queue container
And these are implemented by
- * PersistentArray (persistent-array.sml) - a polymorphic-value
+ * `PersistentArray` (`persistent-array.sml`) - a polymorphic-value
persistent array container
- * PersistentQueue (persistent-queue.sml) - a polymorphic-value
+ * `PersistentArraySlice` (`persistent-array-slice.sml`) - slice into
+ a `PersistentArray`
+
+ * `PersistentQueue` (`persistent-queue.sml`) - a polymorphic-value
persistent queue container
@@ 216,14 227,16 @@ TO BUILD & TEST
Basic unit tests are provided. With the MLton compiler, run
+```
$ mlton test.mlb && ./test
+```
-To use in other projects, include trie.mlb from your MLB file.
+To use in other projects, include `trie.mlb` from your MLB file.
AUTHOR
------
-Copyright 2015-2020 Chris Cannam.
+Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details.
M atrie-node-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature ATRIE_ELEMENT = sig
M btrie-node-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature BTRIE_ELEMENT = sig
M list-trie-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
functor ListTrieMapFn (M : TRIE_NODE_MAP)
M mtrie-node-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature MTRIE_ELEMENT = sig
M pattern-match-trie-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
functor PatternMatchTrieFn (M : PATTERN_MATCH_TRIE_MAP)
M pattern-match-trie-map.sig +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2016 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature PATTERN_MATCH_TRIE_MAP = sig
M pattern-match-trie.sig +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2016 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature PATTERN_MATCH_TRIE = sig
M persistent-hash-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
functor PersistentHashMapFn (Key : HASH_KEY)
M persistent-hash-map.sig +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature HASH_KEY = sig
M string-tries.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature STRING_TRIE_MAP = sig
M test-support.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2016 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
structure TestSupport = struct
M test.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature TRIE_TEST_FN_ARG = sig
M tests.sig +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2016 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature TESTS = sig
M trie-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
functor TrieFn (M : TRIE_MAP)
M trie-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
(** Signature for the map used within a trie node to store branching
M trie-map.sig +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature TRIE_MAP = sig
M trie.sig +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature TRIE = sig
M vector-trie-map-fn.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
signature VECTOR_TRIE_MAP_FN_ARG = sig
M word32-trie-map.sml +1 -1
@@ 1,5 1,5 @@
-(* Copyright 2015-2018 Chris Cannam.
+(* Copyright 2015-2021 Chris Cannam.
MIT/X11 licence. See the file COPYING for details. *)
structure Word32NodeMap