Class NaiveDoubleLengthPcsSorter

An implementation of IDoubleLengthPcsSorter sorting of partial cyclic shifts (PCS) of length 2 * L of a string by generating them and sorting with the LINQ-provided QuickSort. Ignores the provided order and equivalence classes of the PCS of length L.

Inheritance
System.Object
NaiveDoubleLengthPcsSorter
Implements
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.SuffixArrays.CyclicShifts
Assembly: MoreStructures.dll
Syntax
public class NaiveDoubleLengthPcsSorter : IDoubleLengthPcsSorter
Remarks

ADVANTAGES AND DISADVANTAGES
- Unlike other implementations, such as CountingSortDoubleLengthPcsSorter, this sorter needs to know whether the input being provided includes a terminator (i.e. its last char is "special" as it uniquely identify the end of the string) or not.
- This information is required since this sorter performs sorting by actually comparing PCS.
- Other implementations don't require such information, since they never compare PCS against each other: they use externally provided data structures, from which they infer the order.

ALGORITHM
- For each index i of the input string, a cyclic shift starting at i and of length 2 * L is generated.
- Cyclic shifts are sorted in ascending lexicographic order, using .
- Indexes i, corresponding to the sorted cyclic shifts, are returned as a list.

COMPLEXITY
- There are always n cyclic shifts, where n is the length of the input string.
- Each cyclic shift has length 2 * L: building it takes O(L) time and space.
- Sorting the cyclic shifts via QuickSort takes O(n * log(n)) comparisons, between strings of length L.
- Generating the output takes O(n * L) space.
- Therefore, Time Complexity is O(n * log(n) * L) and Space Complexity is O(n * L) space.
- If L is not constant, but rather O(n), Time Complexity is O(n^2 * log(n)) and Space Complexity is O(n^2).

Constructors

| Improve this Doc View Source

NaiveDoubleLengthPcsSorter(String, Int32, Boolean)

Declaration
public NaiveDoubleLengthPcsSorter(string input, int pcsLength, bool inputWithTerminator)
Parameters
Type Name Description
System.String input

System.Int32 pcsLength

System.Boolean inputWithTerminator

Whether input is terminated by a terminator char. If so, the last char of input will be treated as a terminator char when comparing PCS of the input. Otherwise, for System.String will be used.

Properties

| Improve this Doc View Source

Input

The input string, whose PCS have to be sorted.

Declaration
public string Input { get; }
Property Value
Type Description
System.String
| Improve this Doc View Source

PcsLength

The length L of the PCS. Remark: sorting is done of PCS of length 2 * L, not L.

Declaration
public int PcsLength { get; }
Property Value
Type Description
System.Int32

Methods

| Improve this Doc View Source

Sort()

Declaration
public IList<int> Sort()
Returns
Type Description
IList<System.Int32>
Remarks

Implements

Extension Methods