Commons.Collections.SquareList 1.1.4

.NET 8.0 This package targets .NET 8.0. The package is compatible with this framework or higher. .NET Standard 2.1 This package targets .NET Standard 2.1. The package is compatible with this framework or higher. 
dotnet add package Commons.Collections.SquareList --version 1.1.4
                    


                    

                
NuGet\Install-Package Commons.Collections.SquareList -Version 1.1.4
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package. 
<PackageReference Include="Commons.Collections.SquareList" Version="1.1.4" />
For projects that support PackageReference, copy this XML node into the project file to reference the package. 
<PackageVersion Include="Commons.Collections.SquareList" Version="1.1.4" />
                    


                            Directory.Packages.props
                        

                    

                
<PackageReference Include="Commons.Collections.SquareList" />
                    


                            Project file
For projects that support Central Package Management (CPM), copy this XML node into the solution Directory.Packages.props file to version the package. 
paket add Commons.Collections.SquareList --version 1.1.4
                    


                    

                
#r "nuget: Commons.Collections.SquareList, 1.1.4"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package. 
#:package Commons.Collections.SquareList@1.1.4
#:package directive can be used in C# file-based apps starting in .NET 10 preview 4. Copy this into a .cs file before any lines of code to reference the package. 
#addin nuget:?package=Commons.Collections.SquareList&version=1.1.4
                    


                            Install as a Cake Addin
                        

                    

                
#tool nuget:?package=Commons.Collections.SquareList&version=1.1.4
                    


                            Install as a Cake Tool

Commons.Collections.SquareList

Managed Commons library containing the SquareList specialized collection.

Now requires .NET 8.0/C# 12 to build

Loosely based on an article published in the May 2013 issue of Dr Dobb's Journal, by Mark Sams.

His implementation in C used circular doubly-linked lists of doubly-linked lists, I've reimplemented using a List of Dynamic Slices backed by a single Big Array, It uses a lot less memory than linked lists, but inserts in crammed sets can have ripple effects with worst case O(n).

This implementation allows for multiple instances of the same value to be inserted, and then deleted one-at-a-time or wholesale.

Thinking about performance, search for counting/existence is done bidirectionally, but removal scans only in the forward direction, to have a stable behavior (remove the first found) when duplicates exist.

The SquareList is a structure that is particularly useful in applications that frequently require the current minimum and maximum values, as they both can be found in constant time, even accounting for deletions.

This implementation performs insert/delete/find operations within a worst-case running time of O(sqrt(n)) [In truth O(n) for inserts]. Values are always kept in ascending order, so traversing it in that order is natural and performant.

Commons.Collections.SquareList 1.1.4 is available at Nuget: Commons.Collections.SquareList.

Targets in the package

Release .NET Standard 1.0 .NET Standard 2.1 .NET 6.0 .NET 8.0 .NET 9.0 .NET 10.0
1.0.0 ✔
1.0.2 ✔
1.0.3 ✔ ✔
1.0.4 ✔ ✔ ✔
1.0.5 ✔ ✔ ✔
1.0.6 ✔ ✔ ✔
1.0.7 ✔ ✔ ✔ ✔
1.0.8 ✔ ✔ ✔ ✔
1.1.0 ✘ ✔ ✘ ✔ ✔
1.1.3 ✘ ✔ ✘ ✔ ✔ ✔
1.1.4 ✘ ✔ ✘ ✔ ✔ ✔

Performance

[!Version Information]

  • Runtime: .NET 10.0.7
  • SortedList: 10.0.0
  • SquareList: 1.1.4

Times (all in ms)

SortedList
Initial Size Creation Deletes Inserts Searchs Min Max
1000 1 1 0 0 17 20
1779 0 0 0 0 16 20
3163 0 0 0 0 16 20
5624 1 0 0 0 5 4
10000 0 1 1 0 3 3
17783 0 1 2 0 3 3
31623 1 2 3 0 3 3
56235 1 5 5 0 3 3
100000 2 9 10 0 3 3
177828 4 16 19 0 3 3
316228 8 29 33 0 3 3
562342 15 123 60 0 3 3
1000000 28 288 121 0 3 3
1778280 49 572 313 0 3 3
3162278 94 1116 760 0 3 3
5623414 170 1952 1548 0 3 3
10000000 327 3544 2920 0 3 3
17782795 593 6197 5274 0 2 3
31622777 1070 11219 9748 1 3 3
SquareList
Initial Size Creation Deletes Inserts Reinserts Searchs Min Max CutInHalf Shrink
1000 2 3 2 2 1 0 0 0 0
1779 0 7 4 1 1 0 0 0 0
3163 0 1 1 1 1 0 0 0 0
5624 3 1 1 1 1 0 0 0 0
10000 0 2 1 1 0 0 0 0 0
17783 0 1 1 2 0 0 0 0 2
31623 0 1 1 2 0 0 0 0 1
56235 0 1 2 3 0 0 0 0 1
100000 1 2 2 4 0 0 0 0 2
177828 1 2 3 7 0 0 0 0 4
316228 4 3 4 12 0 0 0 1 6
562342 4 2 2 27 0 0 0 0 2
1000000 8 1 6 47 0 0 0 0 3
1778280 13 3 3 84 0 0 0 1 6
3162278 23 5 4 156 0 0 0 2 10
5623414 41 6 5 278 1 0 0 2 18
10000000 74 7 7 665 1 0 0 5 33
17782795 124 11 9 888 1 0 0 12 51
31622777 232 14 12 1614 1 0 0 12 99

License: MIT

See LICENSE

Product Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 was computed.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 is compatible.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed.  net9.0 is compatible.  net9.0-android was computed.  net9.0-browser was computed.  net9.0-ios was computed.  net9.0-maccatalyst was computed.  net9.0-macos was computed.  net9.0-tvos was computed.  net9.0-windows was computed.  net10.0 is compatible.  net10.0-android was computed.  net10.0-browser was computed.  net10.0-ios was computed.  net10.0-maccatalyst was computed.  net10.0-macos was computed.  net10.0-tvos was computed.  net10.0-windows was computed. 
.NET Core netcoreapp3.0 was computed.  netcoreapp3.1 was computed. 
.NET Standard netstandard2.1 is compatible. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen60 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.

  • .NETStandard 2.1

    • No dependencies.

  • net10.0

    • No dependencies.

  • net8.0

    • No dependencies.

  • net9.0

    • No dependencies.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last Updated
1.1.4 0 5/9/2026
1.1.3 0 5/9/2026
1.1.1 219 11/14/2024
1.0.8 172 7/31/2024
1.0.6 598 8/10/2022
1.0.5 634 1/21/2022
1.0.4 476 11/15/2021
1.0.3 493 11/15/2021
1.0.2 572 11/10/2020
1.0.0 779 5/31/2019

- Packaging for netstandard2.1;net8.0;net9.0;net10.0

         - Added .NET 10.0 target framework
         - Updated NUnit to 4.6.0 and NUnit.Analyzers to 4.13.0
         - Add Directory.Build.props for common properties (specifically for packaging/versioning)
         - Add Directory.Build.targets for packaging tasks
         - Update README.md to reflect new version and packaging