Skip to content

Add -Stable to Sort-Object and related tests #7862

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
adityapatwardhan merged 8 commits into from
Jan 16, 2019
Merged

Add -Stable to Sort-Object and related tests #7862

Show file tree
Hide file tree
Changes from 4 commits
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
73ba2f0
added -Stable sort and tests (#7846)
KirkMunro Sep 26, 2018
131aa16
updated for StyleCop; code review changes
KirkMunro Sep 26, 2018
9941e1e
updated nuget packages
KirkMunro Sep 26, 2018
2260eb0
Merge branch 'master' into sort-stable
KirkMunro Nov 1, 2018
7536ae8
code review changes
KirkMunro Nov 5, 2018
55da8b2
Merge branch 'sort-stable' of https://github.com/KirkMunro/PowerShell…
KirkMunro Nov 5, 2018
63d66bb
Fixed typo that Bruce pointed out
KirkMunro Nov 29, 2018
1c1b1fb
Merge branch 'master' into sort-stable
adityapatwardhan Jan 16, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
43 changes: 24 additions & 19 deletions src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -16,37 +16,42 @@ namespace Microsoft.PowerShell.Commands
public sealed class SortObjectCommand : OrderObjectBase
{
#region Command Line Switches

/// <summary>
/// Gets or sets a value indicating whether a stable sort is required.
Comment thread
KirkMunro marked this conversation as resolved.
/// </summary>
/// <value></value>
[Parameter(ParameterSetName = "Default")]
public SwitchParameter Stable { get; set; }

/// <summary>
/// This param specifies if sort order is ascending.
/// Gets or sets a value indicating whether the sort order is descending.
/// </summary>
[Parameter]
public SwitchParameter Descending
{
get { return DescendingOrder; }
set { DescendingOrder = value; }
}

/// <summary>
/// This param specifies if only unique objects are filtered.
/// Gets or sets a value indicating whether the sort filters out any duplicate objects.
/// </summary>
/// <value></value>
[Parameter]
public SwitchParameter Unique
{
get { return _unique; }
set { _unique = value; }
}
private bool _unique;
public SwitchParameter Unique { get; set; }

#endregion

/// <summary>
/// This param specifies you only want the top N items returned.
/// Gets or sets the number of items to return in a Top N sort.
/// </summary>
[Parameter(ParameterSetName = "Default")]
[Parameter(ParameterSetName = "Top", Mandatory = true)]
[ValidateRange(1, int.MaxValue)]
public int Top { get; set; } = 0;

/// <summary>
/// This param specifies you only want the bottom N items returned.
/// Gets or sets the number of items to return in a Bottom N sort.
/// </summary>
[Parameter(ParameterSetName = "Bottom", Mandatory = true)]
[ValidateRange(1, int.MaxValue)]
Expand Down Expand Up @@ -96,7 +101,7 @@ private int FullSort(List<OrderByPropertyEntry> dataToSort, OrderByPropertyCompa
// versions of PowerShell).
dataToSort.Sort(comparer);

if (_unique)
if (Unique)
{
// Move unique entries to the front of the list (this is significantly faster
// than removing them)
Expand All @@ -116,7 +121,8 @@ private int Heapify(List<OrderByPropertyEntry> dataToSort, OrderByPropertyCompar

// Identify how many items will be in the heap and the current number of items
int heapCount = 0;
int heapCapacity = Top > 0 ? Top : Bottom;
int heapCapacity = Stable ? int.MaxValue
: Top > 0 ? Top : Bottom;

// Identify the comparator (the value all comparisons will be made against based on whether we're
// doing a Top N or Bottom N sort)
Expand All @@ -132,7 +138,7 @@ private int Heapify(List<OrderByPropertyEntry> dataToSort, OrderByPropertyCompar
int comparator = Top > 0 ? -1 : 1;

// For unique sorts, use a sorted set to avoid adding unique items to the heap
SortedSet<OrderByPropertyEntry> uniqueSet = _unique ? new SortedSet<OrderByPropertyEntry>(orderByPropertyComparer) : null;
SortedSet<OrderByPropertyEntry> uniqueSet = Unique ? new SortedSet<OrderByPropertyEntry>(orderByPropertyComparer) : null;

// Tracking the index is necessary so that unsortable items can be output at the end, in the order
// in which they were received.
Expand All @@ -146,7 +152,7 @@ private int Heapify(List<OrderByPropertyEntry> dataToSort, OrderByPropertyCompar
}

// If we're doing a unique sort and the entry is not unique, discard the duplicate entry
if (_unique && !uniqueSet.Add(dataToSort[dataIndex]))
if (Unique && !uniqueSet.Add(dataToSort[dataIndex]))
{
discardedDuplicates++;
if (dataIndex != dataToSort.Count - discardedDuplicates)
Expand Down Expand Up @@ -239,13 +245,12 @@ protected override void EndProcessing()
// Track the number of items that will be output from the data once it is sorted
int sortedItemCount = dataToProcess.Count;

// If -Top & -Bottom were not used, or if -Top or -Bottom would return all objects, invoke
// an in-place full sort
if ((Top == 0 && Bottom == 0) || Top >= dataToProcess.Count || Bottom >= dataToProcess.Count)
Comment thread
KirkMunro marked this conversation as resolved.
// If -Stable, -Top & -Bottom were not used, invoke an in-place full sort
if (!Stable && Top == 0 && Bottom == 0)
{
sortedItemCount = FullSort(dataToProcess, comparer);
}
// Otherwise, use an indexed min-/max-heap to perform an in-place sort of all objects
// Otherwise, use an indexed min-/max-heap to perform an in-place, stable sort of all objects
Comment thread
KirkMunro marked this conversation as resolved.
Outdated
else
{
sortedItemCount = Heapify(dataToProcess, comparer);
Expand Down
74 changes: 74 additions & 0 deletions test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -225,6 +225,80 @@ Describe "Sort-Object DRT Unit Tests" -Tags "CI" {
}
}

Describe 'Sort-Object Stable Unit Tests' -Tags 'CI' {

Context 'Modulo stable sort' {

$unsortedData = 1..20
Comment thread
iSazonov marked this conversation as resolved.

It 'Return each value in an ordered set, sorted by the value modulo 3, with items having the same result appearing in the same order' {
$results = $unsortedData | Sort-Object {$_ % 3} -Stable

$results[0] | Should -Be 3
$results[1] | Should -Be 6
$results[2] | Should -Be 9
$results[3] | Should -Be 12
$results[4] | Should -Be 15
$results[5] | Should -Be 18
$results[6] | Should -Be 1
$results[7] | Should -Be 4
$results[8] | Should -Be 7
$results[9] | Should -Be 10
$results[10] | Should -Be 13
$results[11] | Should -Be 16
$results[12] | Should -Be 19
$results[13] | Should -Be 2
$results[14] | Should -Be 5
$results[15] | Should -Be 8
$results[16] | Should -Be 11
$results[17] | Should -Be 14
$results[18] | Should -Be 17
$results[19] | Should -Be 20
}

It 'Return each value in an ordered set, sorted by the value modulo 3 (descending), with items having the same result appearing in the same order' {
$results = $unsortedData | Sort-Object {$_ % 3} -Stable -Descending

$results[0] | Should -Be 2
$results[1] | Should -Be 5
$results[2] | Should -Be 8
$results[3] | Should -Be 11
$results[4] | Should -Be 14
$results[5] | Should -Be 17
$results[6] | Should -Be 20
$results[7] | Should -Be 1
$results[8] | Should -Be 4
$results[9] | Should -Be 7
$results[10] | Should -Be 10
$results[11] | Should -Be 13
$results[12] | Should -Be 16
$results[13] | Should -Be 19
$results[14] | Should -Be 3
$results[15] | Should -Be 6
$results[16] | Should -Be 9
$results[17] | Should -Be 12
$results[18] | Should -Be 15
$results[19] | Should -Be 18
}

It 'Return each value in an ordered set, sorted by the value modulo 3, discarding duplicates' {
$results = $unsortedData | Sort-Object {$_ % 3} -Stable -Unique

$results[0] | Should -Be 3
$results[1] | Should -Be 1
$results[2] | Should -Be 2
}

It 'Return each value in an ordered set, sorted by the value modulo 3 (descending), discarding duplicates' {
$results = $unsortedData | Sort-Object {$_ % 3} -Stable -Unique -Descending

$results[0] | Should -Be 2
$results[1] | Should -Be 1
$results[2] | Should -Be 3
}
}
}

Describe 'Sort-Object Top and Bottom Unit Tests' -Tags 'CI' {

# Helper function to compare two sort entries
Expand Down