Repository: celestiaorg/nmt
Pull request #105 (2023-02-17 14:23:44)

feat: implement nmt methods Min/MaxNamespace
Closes https://github.com/celestiaorg/nmt/issues/104



rootulp: Sorry this PR was still in draft b/c I was waiting for CI checks to pass before marking as ready for review. 
codecov[bot]: # [Codecov](https://codecov.io/gh/celestiaorg/nmt/pull/105?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) Report
> Merging [#105](https://codecov.io/gh/celestiaorg/nmt/pull/105?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (7e6d26f) into [master](https://codecov.io/gh/celestiaorg/nmt/commit/fa98a59cbf582b3a0880ba0222a49e3bf5032f6d?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (fa98a59) will **increase** coverage by `0.01%`.
> The diff coverage is `100.00%`.

> :exclamation: Current head 7e6d26f differs from pull request most recent head 893ff03. Consider uploading reports for the commit 893ff03 to get more accurate results

```diff
@@            Coverage Diff             @@
##           master     #105      +/-   ##
==========================================
+ Coverage   96.21%   96.23%   +0.01%     
==========================================
  Files           6        6              
  Lines         423      425       +2     
==========================================
+ Hits          407      409       +2     
  Misses         10       10              
  Partials        6        6              
```


| [Impacted Files](https://codecov.io/gh/celestiaorg/nmt/pull/105?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) | Coverage Δ | |
|---|---|---|
| [nmt.go](https://codecov.io/gh/celestiaorg/nmt/pull/105?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-bm10Lmdv) | `98.82% <100.00%> (+0.01%)` | :arrow_up: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg)


Patch:
diff --git a/nmt.go b/nmt.go
index 2a4f8c1..830aeb0 100644
--- a/nmt.go
+++ b/nmt.go
@@ -414,6 +414,16 @@ func (n *NamespacedMerkleTree) Root() []byte {
 	return n.rawRoot
 }
 
+// MinNamespace returns the minimum namespace ID in this Namespaced Merkle Tree.
+func (n *NamespacedMerkleTree) MinNamespace() namespace.ID {
+	return MinNamespace(n.Root(), n.NamespaceSize())
+}
+
+// MaxNamespace returns the maximum namespace ID in this Namespaced Merkle Tree.
+func (n *NamespacedMerkleTree) MaxNamespace() namespace.ID {
+	return MaxNamespace(n.Root(), n.NamespaceSize())
+}
+
 // computeRoot calculates the namespace Merkle root for a tree/sub-tree that
 // encompasses the leaves within the range of [start, end).
 func (n *NamespacedMerkleTree) computeRoot(start, end int) []byte {


Test patch:
diff --git a/nmt_test.go b/nmt_test.go
index eeabe4b..3b6ff2b 100644
--- a/nmt_test.go
+++ b/nmt_test.go
@@ -14,6 +14,7 @@ import (
 	"testing"
 
 	"github.com/celestiaorg/nmt/namespace"
+	"github.com/stretchr/testify/assert"
 )
 
 type namespaceDataPair struct {
@@ -773,3 +774,73 @@ func generateRandNamespacedRawData(total int, nidSize int, leafSize int) [][]byt
 func sortByteArrays(src [][]byte) {
 	sort.Slice(src, func(i, j int) bool { return bytes.Compare(src[i], src[j]) < 0 })
 }
+
+func TestMinMaxNamespace(t *testing.T) {
+	type testCase struct {
+		name    string
+		tree    *NamespacedMerkleTree
+		wantMin namespace.ID
+		wantMax namespace.ID
+	}
+	testCases := []testCase{
+		{
+			name:    "example tree with four leaves",
+			tree:    exampleTreeWithFourLeaves(),
+			wantMin: namespace.ID{0},
+			wantMax: namespace.ID{3},
+		},
+		{
+			name:    "example tree with eight leaves",
+			tree:    exampleTreeWithEightLeaves(),
+			wantMin: namespace.ID{1, 1},
+			wantMax: namespace.ID{8, 8},
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			assert.Equal(t, tc.wantMin, tc.tree.MinNamespace())
+			assert.Equal(t, tc.wantMax, tc.tree.MaxNamespace())
+		})
+	}
+}
+
+func exampleTreeWithFourLeaves() *NamespacedMerkleTree {
+	nidSize := 1
+	data := [][]byte{
+		append(namespace.ID{0}, []byte("leaf_0")...),
+		append(namespace.ID{0}, []byte("leaf_1")...),
+		append(namespace.ID{1}, []byte("leaf_2")...),
+		append(namespace.ID{3}, []byte("leaf_3")...),
+	}
+
+	tree := New(sha256.New(), NamespaceIDSize(nidSize))
+	for _, d := range data {
+		if err := tree.Push(d); err != nil {
+			panic(fmt.Sprintf("unexpected error: %v", err))
+		}
+	}
+	return tree
+}
+
+func exampleTreeWithEightLeaves() *NamespacedMerkleTree {
+	nidSize := 2
+	data := [][]byte{
+		append(namespace.ID{1, 1}, []byte("leaf_0")...),
+		append(namespace.ID{2, 2}, []byte("leaf_1")...),
+		append(namespace.ID{3, 3}, []byte("leaf_2")...),
+		append(namespace.ID{4, 4}, []byte("leaf_3")...),
+		append(namespace.ID{5, 5}, []byte("leaf_4")...),
+		append(namespace.ID{6, 6}, []byte("leaf_5")...),
+		append(namespace.ID{7, 7}, []byte("leaf_6")...),
+		append(namespace.ID{8, 8}, []byte("leaf_7")...),
+	}
+
+	tree := New(sha256.New(), NamespaceIDSize(nidSize))
+	for _, d := range data {
+		if err := tree.Push(d); err != nil {
+			panic(fmt.Sprintf("unexpected error: %v", err))
+		}
+	}
+	return tree
+}