Class TextWithTerminatorExtensions

Extension methods for TextWithTerminator.

Inheritance

System.Object

TextWithTerminatorExtensions

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures

Assembly: MoreStructures.dll

Syntax

public static class TextWithTerminatorExtensions

Methods

BuildTerminatorsCDF(TextWithTerminator, ISet<Char>)

Builds the Cumulative Distribution Function (CDF) of the provided terminators in the provided fullText.

Declaration

public static IEnumerable<int> BuildTerminatorsCDF(TextWithTerminator fullText, ISet<char> terminators)

Parameters

Type	Name	Description
TextWithTerminator	fullText	The text, composed of a single or multiple concatenated TextWithTerminator.
ISet<System.Char>	terminators	The set of terminators of fullText.

Returns

Type	Description
IEnumerable<System.Int32>	A lazy-generated sequence of integers, representing the values of the CDF, indexed by char index in fullText.

Remarks

DEFINITION
- The Cumulative Distribution Function of a text T with terminators t is a function CDF such that CDF at index i is the number of chars in T up to index i included which are in t.
- In other terms, CDF[i] = sum(j = 0 to i, isTerminator(T[j])), where isTerminator(c) = 1 if c is in t, 0 otherwise.

ALGORITHM
- The definition is applied, iterating over the chars of fullText and yielding item by item.
- The algorithm is online.

COMPLEXITY
- Time Complexity is O(n * Ttc), where n is the length of fullText and Ttc is the time required to check whether a char of the text is a terminator or not.
- The "terminator checking" performance depends on the implementation of , terminators is an instance of.
- If terminators is an , is executed in constant time, and Time Complexity becomes O(n).
- Space Complexity is O(n) in all cases, since the only data structure instantiated by the algorithm is the output, which has as many items as the input text.

BuildTerminatorsIndexMap(TextWithTerminator, ISet<Char>)

Builds the Terminators Index Map of the provided terminators in the provided fullText.

Declaration

public static IEnumerable<int> BuildTerminatorsIndexMap(TextWithTerminator fullText, ISet<char> terminators)

Parameters

Type	Name	Description
TextWithTerminator	fullText	The text, composed of a single or multiple concatenated TextWithTerminator.
ISet<System.Char>	terminators	The set of terminators of fullText.

Returns

Type	Description
IEnumerable<System.Int32>	A lazy-generated sequence of integers, representing the values of the index map, indexed by char index in fullText.

Remarks

DEFINITION
- The terminators index map of a text T with terminators t is a function TIM such that TIM at index i is the index in T of the last encountered terminator of T up to index i included.
- In other terms, TIM[i] = max(j = 0 to i, isTerminator(T[j])), where isTerminator(c) = 1 if c is in t, 0 otherwise.

ALGORITHM
- The definition is applied, iterating over the chars of fullText and yielding the index of a new terminator each time one is encountered, for all indexes of the text from the one following the last emitted, to the current one, included.
- The algorithm keeps track of the last emitted index and assumes the full text terminates with a terminator (which is the case for every well-formed TextWithTerminator issued by GenerateFullText(TextWithTerminator[])).
- The algorithm is online. However, it requires consuming the input up to the next terminator, in order to emit values for indexes of chars in the text which refer to such terminator.
- For example, if the text is "ab1cde2fghilm3", where terminators are new[] {'1', '2', '3'}, emitting the first item of the output sequence requires consuming the input up to the terminator '1', emitting the second item of the output sequence requires consuming the input up to the terminator '2', etc.

COMPLEXITY
- Time Complexity is O(n * Ttc), where n is the length of fullText and Ttc is the time required to check whether a char of the text is a terminator or not.
- The "terminator checking" performance depends on the implementation of , terminators is an instance of.
- If terminators is an , is executed in constant time, and Time Complexity becomes O(n).
- Space Complexity is O(n) in all cases, since the only data structure instantiated by the algorithm is the output, which has as many items as the input text.

GenerateFullText(TextWithTerminator[])

Builds a single TextWithTerminator, concatenating the TextWithTerminator instances in texts. Returns as well the of all the terminators and their indexes.

Declaration

public static (TextWithTerminator fullText, ISet<char> terminators) GenerateFullText(this TextWithTerminator[] texts)

Parameters

Type	Name	Description
TextWithTerminator[]	texts	The text instances to join into a single text.

Returns

Type	Description
System.ValueTuple<TextWithTerminator, ISet<System.Char>>	A couple. The first item of the couple is a text with the Text of all items of texts concatenated, each followed by its own Terminator except the last, and the Terminator of the last item. The second item of the couple is a set of all the terminators included in the resulting text.

Remarks

COMPLEXITY
Requires iterating over the TextWithTerminator items of texts, but not on their content.
Therefore, Time Complexity is O(n), where n is the number of items of texts, and not O(t), where t is the length of the concatenated text.
Space Complexity is also O(n), since the of terminators contains n items and the generated full text receives a lazy evaluated of the System.Char in each TextWithTerminator of texts.

ToVirtuallyRotated(TextWithTerminator, Int32)

Builds a virtual rotation of the provided TextWithTerminator, by a number of chars defined by rotation, in constant time.

Declaration

public static VirtuallyRotatedTextWithTerminator ToVirtuallyRotated(this TextWithTerminator text, int rotation)

Parameters

Type	Name	Description
TextWithTerminator	text	The text which has to be rotated.
System.Int32	rotation	The number of chars to virtually rotate text.

Returns

Type	Description
VirtuallyRotatedTextWithTerminator	An object constructed in constant time and behaving like a rotation of the provided text.

Remarks

COMPLEXITY
- The rotation is "virtual" because no new string of length n is computed (which would make the constructor take linear time in the number of chars of text).
- Instead, a new object storing the rotation and keeping the reference to text is created in O(1) time and space.
- Such an object is able to appear as if the underlying string was recomputed, taking into account the rotation in all its exposed functionalities.