Module Collections.TreequenceSource

A Treequence is an implementation `Dlist` which keeps its elements in a tree. Every operation that adds elements to Treequence is O(1). Operations that retrieve or remove elements from it will restructure the tree to expose either the front or back of the list for fast access. This allows for efficient accesses on both ends but there is a cost to be paid when switching between accessing from the front/back or the back.

include Dlist_itf.S
Sourcetype 'a t

A 'a t is a Dlist containing elements of type 'a. A Dlist, short for double-ended list, is a purely functional ordered list of elements that can be accessed both from the front and the back.

Sourceval name : string

A name for the datatype, there are different implementations of this interface, you can check this name to identify which implementation you are using.

Sourceval empty : 'a t

An empty Dlist, contains no elements.

Sourceval is_empty : 'a t -> bool

is_empty t is true iff there are no elements in t.

Sourceval map : ('a -> 'b) -> 'a t -> 'b t

map f t applies a function to each element of t, creating a new Dlist with the results.

Sourceval singleton : 'a -> 'a t

Creates a Dlist containing a single element.

Sourceval size : 'a t -> int

size t returns the number of elements in t. This operation is O(1).

Sourceval push : 'a -> 'a t -> 'a t

push el t Adds an element to the front of t.

Sourceval pop : 'a t -> ('a * 'a t) option

pop el t Removes an element from the front of t.

Sourceval push_end : 'a -> 'a t -> 'a t

push_end el t Adds an element to the end of t.

Sourceval pop_end : 'a t -> ('a * 'a t) option

pop_end el t Removes an element from the end of t.

Sourceval append : 'a t -> 'a t -> 'a t

append s1 s2 Creates Dlist that contains all elements of s1 followed by all elements of s2.

Sourceval of_list : 'a list -> 'a t

of_list elements Creates a Dlist from the elements of the list. The front of the list will become the front ot the Dlist. The first element you pop from the Dlist will be the first element in the list.

Sourceval to_string : ('a -> string) -> 'a t -> string

Converts Dlist into a string revealing its internal structure. Useful for debugging and testing.

Sourceval get : int -> 'a t -> 'a

get i s finds element at index i from the front. For example get 0 s is equivalent pop s

Sourceval to_list : 'a t -> 'a list

to_list s converts a Dlist into a list by popping all elements from the front.