SumTree

What is this?

SumTree is a high-performance, immutable data structure that combines the efficiency of Rope with powerful summary dimensions. It's designed for applications that need fast text editing, querying, and manipulation with computed summaries like line numbers, bracket counting, and custom metrics.

Why use this?

• Performance: Get the benefits of functional programming without the overhead of copying data on edits
• Rich Querying: Built-in support for line/column tracking, bracket matching, and custom summary dimensions
• Memory Efficient: Structural sharing means edits don't copy entire data structures
• Thread Safe: Immutable by design, safe for concurrent access
• Versatile: Works with any type T, not just text

Replace these types with better performance:

• string (for text editing scenarios)
• T[] (for immutable arrays with fast edits)
• List<T> (for functional-style list operations)
• ImmutableList<T> (with much better performance)
• StringBuilder (for complex text construction)

How does it work?

SumTree is a C# implementation that directly integrates Rope structure with summary dimensions. Based on the paper Ropes: an Alternative to Strings, but enhanced with:

• Summary Dimensions: Efficiently track computed properties (line numbers, bracket counts, custom metrics)
• Zero-Copy Operations: Structural sharing means edits create new views without copying data
• Cache-Friendly: Arrays of elements with subdivision only on edits for better CPU cache performance
• Automatic Balancing: Tree rebalances using Fibonacci heuristics for optimal performance

How do I use it?

dotnet add package BrunoMassa.SumTree

Basic Usage

usingSumTree;// Create a SumTree from text - no memory allocationSumTree<char>text="Hello, World!".ToSumTree();// Or create from any array/collectionSumTree<int>numbers=new[]{1,2,3,4,5}.ToSumTree();SumTree<string>words=new[]{"Hello","World"}.ToSumTree();// String-like operations for SumTree<char>Console.WriteLine(text.ToString());// "Hello, World!"Console.WriteLine(text.Length);// 13// Efficient concatenation (no copying)SumTree<char>combined=text+" How are you?".ToSumTree();Console.WriteLine(combined.ToString());// "Hello, World! How are you?"

Text Editing with Line Tracking

// Create text with line number trackingSumTree<char>document=@"Line 1Line 2Line 3".ToSumTreeWithLines();// Get line/column informationvar(line,column)=document.GetLineAndColumn(10);// line 2, column 4Console.WriteLine($"Position 10 is at line {line}, column {column}");// Find start of a specific linelonglineStart=document.FindLineStart(2);// Position 7Console.WriteLine($"Line 2 starts at position {lineStart}");// Get content of a specific linestringlineContent=document.GetLineContent(1);// "Line 1"Console.WriteLine($"Line 1 content: {lineContent}");// Insert text at specific line/columnSumTree<char>modified=document.InsertAtLineColumn(2,1,"Modified ");Console.WriteLine(modified.ToString());// Output:// Line 1// Modified Line 2// Line 3

Bracket Matching and Code Analysis

// Track both lines and bracket countsSumTree<char>code=@"function example() { if (condition) { return [1, 2, 3]; }}".ToSumTreeWithLinesAndBrackets();// Check if brackets are balancedboolbalanced=code.AreBracketsBalanced(code.Length);// trueConsole.WriteLine($"Brackets balanced: {balanced}");// Find specific bracket occurrenceslongfirstParen=code.FindNthOpenBracket('(',1);// Position of first '('longsecondBrace=code.FindNthOpenBracket('{',2);// Position of second '{'// Get bracket summaryvarbracketSummary=code.GetSummary<BracketCountSummary>();Console.WriteLine($"Open parens: {bracketSummary.OpenParentheses}");Console.WriteLine($"Open braces: {bracketSummary.OpenCurlyBraces}");Console.WriteLine($"Open brackets: {bracketSummary.OpenSquareBrackets}");

Powerful Search Operations

SumTree<char>text="The quick brown fox jumps over the lazy dog".ToSumTree();// Find patternslongpos1=text.IndexOf("quick".ToSumTree());// 4longpos2=text.IndexOf("the".ToSumTree(),10);// 31 (second occurrence)longpos3=text.LastIndexOf("o".ToSumTree());// 40 (last 'o')// Check containmentboolhasQuick=text.Contains("quick".ToSumTree());// trueboolhasSlow=text.Contains("slow".ToSumTree());// false// Case-insensitive search with custom comparervarcaseInsensitive=EqualityComparer<char>.Create((x,y)=>char.ToLower(x)==char.ToLower(y),
c =>char.ToLower(c).GetHashCode());longpos4=text.IndexOf("QUICK".ToSumTree(),caseInsensitive);// 4

Advanced Operations

// Efficient slicing (no copying)SumTree<char>text="Hello, World!".ToSumTree();SumTree<char>slice=text.Slice(7,5);// "World"// Remove ranges efficientlySumTree<char>modified=text.RemoveRange(5,2);// "Hello World!"// Replace elementsSumTree<char>replaced=text.Replace(' ','_');// "Hello,_World!"// Insert at any positionSumTree<char>inserted=text.Insert(5,'!');// "Hello!, World!"// Combine multiple SumTreesvarparts=new[]{"Hello".ToSumTree()," ".ToSumTree(),"World".ToSumTree()};SumTree<char>combined=parts.Combine();// "Hello World"

Custom Summary Dimensions

// Create a custom dimension that counts vowelspublicclassVowelCountDimension:SummaryDimensionBase<char,int>{publicoverrideintIdentity=>0;publicoverrideintSummarizeElement(charelement){return"aeiouAEIOU".Contains(element)?1:0;}publicoverrideintCombine(intleft,intright){returnleft+right;}}// Use the custom dimensionvarvowelDimension=newVowelCountDimension();SumTree<char>text="Hello World".ToSumTree(vowelDimension);intvowelCount=text.GetSummary<int>();// 3 vowels (e, o, o)Console.WriteLine($"Vowel count: {vowelCount}");

Working with Any Type

// SumTree works with any typeSumTree<int>numbers=new[]{1,2,3,4,5}.ToSumTree();SumTree<int>doubled=numbers.Select(x =>x*2);// { 2, 4, 6, 8, 10 }// Efficient sorted insertionSumTree<int>sorted=SumTree<int>.Empty;sorted=sorted.InsertSorted(5,Comparer<int>.Default);sorted=sorted.InsertSorted(2,Comparer<int>.Default);sorted=sorted.InsertSorted(8,Comparer<int>.Default);// Result: { 2, 5, 8 }// Filter operationsSumTree<int>evens=numbers.Where(x =>x%2==0);// { 2, 4 }

Constructors and Building

// Multiple ways to create SumTreesSumTree<char>empty=SumTree<char>.Empty;SumTree<char>single=newSumTree<char>('A');SumTree<char>fromArray=newSumTree<char>("Hello".ToCharArray());SumTree<char>fromMemory=newSumTree<char>("Hello".AsMemory());// Concatenation constructorSumTree<char>left="Hello".ToSumTree();SumTree<char>right=" World".ToSumTree();SumTree<char>combined=newSumTree<char>(left,right);// Balance trees when neededSumTree<char>balanced=unbalancedTree.Balanced();

Key Features

Performance Benefits

• O(log n) random access and edits
• O(log n) concatenation and splitting
• O(n) sequential iteration with excellent cache locality
• Zero-copy operations through structural sharing
• Automatic balancing maintains performance over time

Rich Summary System

• Line/Column Tracking: Built-in support for text editor scenarios
• Bracket Matching: Track parentheses, brackets, and braces automatically
• Custom Dimensions: Define your own summary computations
• Efficient Queries: Summary data maintained incrementally during edits

Developer Experience

• String-like API: SumTree<char> behaves like string but with better performance
• LINQ Integration: Full support for Select, Where, Aggregate, etc.
• Value Semantics: Structural equality and hash codes work as expected
• Thread Safe: Immutable design means safe concurrent access

Comparison with .NET Built-in Types

Operation	SumTree<T>	Rope<T>	String	StringBuilder	List<T>	ImmutableList<T>
Concat	O(log n)	O(log n)	O(n)	Amortized O(1)*	O(n)	O(log n)
Insert	O(log n)	O(log n)	O(n)	O(n)	O(n)	O(log n + k)†
Remove	O(log n)	O(log n)	O(n)	O(n)	O(n)	O(log n + k)†
IndexOf	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)
Random Access	O(log n)	O(log n)	O(1)	O(1)	O(1)	O(log n)
Memory Usage	Low*	Low*	High	Medium	High	High
Immutable	✓	✓	✓	✗	✗	✓
Summary Queries	✓	✗	✗	✗	✗	✗

• Low: Lower than flat arrays for edits (no full-copy), but has per-node pointer/struct overhead.
• StringBuilder concat is amortized O(1) for appends but still O(n) when converting to string. † k = size of the modified leaf chunk, which can make it slightly slower than pure log time.

Advanced Examples

Text Editor Implementation

publicclassSimpleTextEditor{privateSumTree<char>_document;publicSimpleTextEditor(stringinitialText=""){_document=initialText.ToSumTreeWithLines();}publicvoidInsertText(intline,intcolumn,stringtext){_document=_document.InsertAtLineColumn(line,column,text);}publicvoidDeleteLine(intlineNumber){longlineStart=_document.FindLineStart(lineNumber);longnextLineStart=lineNumber<GetLineCount()?_document.FindLineStart(lineNumber+1):_document.Length;_document=_document.RemoveRange(lineStart,nextLineStart-lineStart);}publicstringGetLine(intlineNumber){return_document.GetLineContent(lineNumber);}publicintGetLineCount(){varsummary=_document.GetSummary<LineNumberSummary>();returnsummary.Lines+1;// Lines are 0-based, add 1 for total count}public(intline,intcolumn)GetPosition(longindex){return_document.GetLineAndColumn(index);}publicoverridestringToString(){return_document.ToString();}}

Code Analysis Tool

publicclassCodeAnalyzer{publicstaticCodeMetricsAnalyze(stringsourceCode){varcode=sourceCode.ToSumTreeWithLinesAndBrackets();varlinesSummary=code.GetSummary<LineNumberSummary>();varbracketsSummary=code.GetSummary<BracketCountSummary>();returnnewCodeMetrics{LineCount=linesSummary.Lines+1,TotalCharacters=linesSummary.TotalCharacters,AverageLineLength=linesSummary.Lines>0?(double)linesSummary.TotalCharacters/(linesSummary.Lines+1):0,ParenthesesCount=bracketsSummary.OpenParentheses,BracketsCount=bracketsSummary.OpenSquareBrackets,BracesCount=bracketsSummary.OpenCurlyBraces,IsBalanced=bracketsSummary.IsBalanced,FunctionCount=CountFunctions(code),MaxNestingLevel=CalculateMaxNesting(code)};}privatestaticintCountFunctions(SumTree<char>code){// Count occurrences of "function" keywordintcount=0;longpos=0;varpattern="function".ToSumTree();while((pos=code.IndexOf(pattern,pos))!=-1){count++;pos+=pattern.Length;}returncount;}privatestaticintCalculateMaxNesting(SumTree<char>code){intmaxNesting=0;intcurrentNesting=0;foreach(charcincode){if(c=='{'){currentNesting++;maxNesting=Math.Max(maxNesting,currentNesting);}elseif(c=='}'){currentNesting--;}}returnmaxNesting;}}publicclassCodeMetrics{publicintLineCount{get;set;}publiclongTotalCharacters{get;set;}publicdoubleAverageLineLength{get;set;}publicintParenthesesCount{get;set;}publicintBracketsCount{get;set;}publicintBracesCount{get;set;}publicboolIsBalanced{get;set;}publicintFunctionCount{get;set;}publicintMaxNestingLevel{get;set;}}

Performance

SumTree is designed for high-performance scenarios where traditional string/list operations become bottlenecks:

• Text Editors: Handle large documents with efficient line-based operations
• Code Analysis: Parse and analyze source code with built-in bracket tracking
• Data Processing: Work with large immutable collections without copying overhead
• Collaborative Editing: Share data structures safely across threads/processes

License and Acknowledgements

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgements

• Original Rope paper by Boehm, Atkinson, and Plass
• Inspired by modern text editor data structures like those in VS Code and Xi Editor
• Built on the foundation of efficient immutable data structures
• C# Rope implementation by Andrew Chisholm

Author: Bruno Massa
Repository:https://github.com/brmassa/SumTree
Package:https://www.nuget.org/packages/com.BrunoMassa.SumTree