github.com/google/btree v1.0.0: New, BTree, Item

Clean-room public code sample — generation instructions

Write a brand-new, minimal, self-contained code sample in this clean-room directory.
Do not copy, paraphrase, or reference any existing project source. Work only from this spec.

A csx.json manifest scaffold already exists. Do not recreate it from memory. Preserve its case.goal, packages and symbols; fill its empty case.contract with exact assertions and correct its environment, commands and verifierAdapter for the files you generate.

Goal: verify pkg:golang/github.com/google/btree@v1.0.0
Kind: HOW

Use EXACTLY these public packages and versions:
  - pkg:golang/github.com/google/btree@v1.0.0
Required runtime conditions:
  - ecosystem: golang
  - language: go
  - packageManager: go@1.26.6
  - runtime: go@1.26.6

Rules:
  - One focused purpose; the smallest project that proves the goal.
  - Include a contract test (test/contract.*) that runs OFFLINE and exits 0 exactly when the goal behavior works.
  - Pin every dependency with a lockfile so resolution is reproducible.
  - No secrets, credentials, or tokens. No real URLs (only example.com or localhost). No absolute paths.
  - No personal names, emails, company names, or project identifiers of any kind.
  - No binaries and no generated output (node_modules, dist, target, venv, .git, .env).
  - Keep it under 200 files and 256KB packed.

{"case":{"caseId":"case:sha256:e98a1bb18e559939aabdf927be19ecf893552d8c3944252236016100eb181776","contract":["btree.New creates an empty BTree of the specified degree","BTree.ReplaceOrInsert inserts items and updates tree length","BTree.Get and BTree.Has retrieve inserted items by key","BTree.Ascend visits items in sorted ascending order","BTree.Delete removes an item and decrements tree length"],"goal":"verify pkg:golang/github.com/google/btree@v1.0.0","kind":"HOW","packages":["pkg:golang/github.com/google/btree@v1.0.0"],"schemaVersion":1,"symbols":["github.com/google/btree.New","github.com/google/btree.BTree","github.com/google/btree.Item","github.com/google/btree.Int"]},"contractCommand":["go","run","./test"],"environment":{"arch":"x64","distro":"ubuntu","ecosystem":"golang","language":"go","libc":"glibc","libcVersion":"2.39","os":"linux","osVersionBucket":"24","packageManager":"go","packageManagerVersion":"1.26.6","runtime":"go","runtimeVersion":"1.26.6","schemaVersion":1},"license":"MIT-0","packages":["pkg:golang/github.com/google/btree@v1.0.0"],"schemaVersion":1,"subject":"pkg:golang/github.com/google/btree@v1.0.0","symbols":["github.com/google/btree.New","github.com/google/btree.BTree","github.com/google/btree.Item","github.com/google/btree.Int"],"verifierAdapter":"golang@1"}

module sample

go 1.22

require github.com/google/btree v1.0.0

github.com/google/btree v1.0.0 h1:0udJVsspx3VBr5FwtLhQQtuAsVc79tTq0ocGIPAU6qo=
github.com/google/btree v1.0.0/go.mod h1:lNA+9X1NB3Zf8V7Ke586lFgjr2dZNuvo3lPJSGZ5JPQ=

package sample

import (
	"github.com/google/btree"
)

// NewIntTree initializes a BTree of the given degree.
func NewIntTree(degree int) *btree.BTree {
	return btree.New(degree)
}

// InsertItem inserts or replaces an item in the BTree.
func InsertItem(tr *btree.BTree, item btree.Item) btree.Item {
	return tr.ReplaceOrInsert(item)
}

// ContainsItem checks if the item exists in the BTree.
func ContainsItem(tr *btree.BTree, item btree.Item) bool {
	return tr.Has(item)
}

// FindItem looks up an item in the BTree and returns it if found.
func FindItem(tr *btree.BTree, item btree.Item) btree.Item {
	return tr.Get(item)
}

// RemoveItem deletes an item from the BTree and returns the deleted item.
func RemoveItem(tr *btree.BTree, item btree.Item) btree.Item {
	return tr.Delete(item)
}

// CollectAscending iterates through all items in ascending order.
func CollectAscending(tr *btree.BTree) []btree.Item {
	var result []btree.Item
	tr.Ascend(func(i btree.Item) bool {
		result = append(result, i)
		return true
	})
	return result
}

{
  "schemaVersion": 1,
  "goal": "verify pkg:golang/github.com/google/btree@v1.0.0",
  "kind": "HOW",
  "packages": [
    "pkg:golang/github.com/google/btree@v1.0.0"
  ],
  "runtimeConditions": {
    "ecosystem": "golang",
    "language": "go",
    "packageManager": "go@1.26.6",
    "runtime": "go@1.26.6"
  }
}

package main

import (
	"fmt"
	"os"
	"reflect"

	"github.com/google/btree"
	"sample"
)

func main() {
	// Assertion 1: btree.New creates an empty BTree of the specified degree
	tr := sample.NewIntTree(2)
	if tr == nil {
		fmt.Fprintf(os.Stderr, "assertion 1 failed: btree.New returned nil\n")
		os.Exit(1)
	}
	if tr.Len() != 0 {
		fmt.Fprintf(os.Stderr, "assertion 1 failed: expected Len() == 0, got %d\n", tr.Len())
		os.Exit(1)
	}

	// Assertion 2: BTree.ReplaceOrInsert inserts items and updates tree length
	prev := sample.InsertItem(tr, btree.Int(10))
	if prev != nil {
		fmt.Fprintf(os.Stderr, "assertion 2 failed: expected nil prev item on new insert, got %v\n", prev)
		os.Exit(1)
	}
	sample.InsertItem(tr, btree.Int(5))
	sample.InsertItem(tr, btree.Int(20))
	sample.InsertItem(tr, btree.Int(15))

	if tr.Len() != 4 {
		fmt.Fprintf(os.Stderr, "assertion 2 failed: expected Len() == 4, got %d\n", tr.Len())
		os.Exit(1)
	}

	oldItem := sample.InsertItem(tr, btree.Int(10))
	if oldItem != btree.Int(10) {
		fmt.Fprintf(os.Stderr, "assertion 2 failed: expected replaced item 10, got %v\n", oldItem)
		os.Exit(1)
	}
	if tr.Len() != 4 {
		fmt.Fprintf(os.Stderr, "assertion 2 failed: expected Len() to remain 4 after replace, got %d\n", tr.Len())
		os.Exit(1)
	}

	// Assertion 3: BTree.Get and BTree.Has retrieve inserted items by key
	if !sample.ContainsItem(tr, btree.Int(15)) {
		fmt.Fprintf(os.Stderr, "assertion 3 failed: expected ContainsItem(15) == true\n")
		os.Exit(1)
	}
	if sample.ContainsItem(tr, btree.Int(99)) {
		fmt.Fprintf(os.Stderr, "assertion 3 failed: expected ContainsItem(99) == false\n")
		os.Exit(1)
	}
	found := sample.FindItem(tr, btree.Int(20))
	if found != btree.Int(20) {
		fmt.Fprintf(os.Stderr, "assertion 3 failed: expected FindItem(20) == 20, got %v\n", found)
		os.Exit(1)
	}
	notFound := sample.FindItem(tr, btree.Int(99))
	if notFound != nil {
		fmt.Fprintf(os.Stderr, "assertion 3 failed: expected FindItem(99) == nil, got %v\n", notFound)
		os.Exit(1)
	}

	// Assertion 4: BTree.Ascend visits items in sorted ascending order
	items := sample.CollectAscending(tr)
	expected := []btree.Item{btree.Int(5), btree.Int(10), btree.Int(15), btree.Int(20)}
	if !reflect.DeepEqual(items, expected) {
		fmt.Fprintf(os.Stderr, "assertion 4 failed: expected %v, got %v\n", expected, items)
		os.Exit(1)
	}
	if tr.Min() != btree.Int(5) {
		fmt.Fprintf(os.Stderr, "assertion 4 failed: expected Min() == 5, got %v\n", tr.Min())
		os.Exit(1)
	}
	if tr.Max() != btree.Int(20) {
		fmt.Fprintf(os.Stderr, "assertion 4 failed: expected Max() == 20, got %v\n", tr.Max())
		os.Exit(1)
	}

	// Assertion 5: BTree.Delete removes an item and decrements tree length
	deleted := sample.RemoveItem(tr, btree.Int(10))
	if deleted != btree.Int(10) {
		fmt.Fprintf(os.Stderr, "assertion 5 failed: expected Delete(10) == 10, got %v\n", deleted)
		os.Exit(1)
	}
	if tr.Len() != 3 {
		fmt.Fprintf(os.Stderr, "assertion 5 failed: expected Len() == 3 after delete, got %d\n", tr.Len())
		os.Exit(1)
	}
	if sample.ContainsItem(tr, btree.Int(10)) {
		fmt.Fprintf(os.Stderr, "assertion 5 failed: ContainsItem(10) should be false after delete\n")
		os.Exit(1)
	}
	delMissing := sample.RemoveItem(tr, btree.Int(100))
	if delMissing != nil {
		fmt.Fprintf(os.Stderr, "assertion 5 failed: Delete(100) on missing key expected nil, got %v\n", delMissing)
		os.Exit(1)
	}

	fmt.Println("All btree contract assertions passed successfully.")
}