import { BPlusTree } from 'b-pl-tree'

const { BPlusTree } = require('b-pl-tree')

import { BPlusTree } from 'b-pl-tree' // Uses TypeScript source directly

import {
  BPlusTree,           // Main B+ tree class
  Node,                // Node class for tree structure
  TransactionContext,  // Transaction management

  // Type definitions
  PortableBPlusTree,   // Serializable tree format
  ValueType,           // Supported key types (number | string | boolean)
  PortableNode,        // Serializable node format
  ITransactionContext, // Transaction interface
  SavepointInfo,       // Savepoint information interface
  SavepointSnapshot,   // Savepoint snapshot interface
  Comparator,          // Comparator function type
  Transaction,         // Transaction function type
  Cursor               // Query cursor type
} from 'b-pl-tree'

import {
  serializeTree,       // Convert tree to portable format
  deserializeTree,     // Load data into existing tree
  createTreeFrom       // Create new tree from data
} from 'b-pl-tree'

import {
  query,               // Main query function

  // Query operators
  map,                 // Transform data
  filter,              // Filter data
  reduce,              // Aggregate data
  forEach,             // Execute side effects

  // Source functions
  sourceEach,          // Iterate all items
  sourceEq,            // Find exact matches
  sourceGt,            // Find greater than
  sourceLt,            // Find less than
  sourceRange,         // Find within range

  // Action functions
  remove,              // Remove operations

  // Evaluation utilities
  executeQuery         // Execute query pipeline
} from 'b-pl-tree'

import {
  print_node,                    // Debug tree structure
  compare_keys_primitive,        // Compare primitive keys
  compare_keys_array,           // Compare array keys
  compare_keys_object           // Compare object keys
} from 'b-pl-tree'

// Import everything you need
import {
  BPlusTree,
  TransactionContext,
  serializeTree,
  deserializeTree,
  query,
  filter,
  map,
  type ValueType,
  type Comparator,
  type SavepointInfo
} from 'b-pl-tree'

// Ready to use!
const tree = new BPlusTree<User, number>(3, false)
const txCtx = new TransactionContext(tree)

// Example with savepoints
async function exampleWithSavepoints() {
  // Create savepoint
  const savepointId = await txCtx.createSavepoint('checkpoint')

  // Make changes
  tree.insert_in_transaction(1, { id: 1, name: 'Alice' }, txCtx)

  // Get savepoint info
  const info: SavepointInfo | undefined = txCtx.getSavepointInfo(savepointId)
  console.log('Savepoint info:', info)

  // Rollback if needed
  await txCtx.rollbackToSavepoint(savepointId)

  // Commit transaction
  await txCtx.commit()
}

import { BPlusTree } from 'b-pl-tree'

// Create a B+ tree with minimum degree 3, allowing duplicates
const tree = new BPlusTree<string, number>(3, false)

// Basic operations
tree.insert(10, 'ten')
tree.insert(20, 'twenty')
tree.insert(15, 'fifteen')

console.log(tree.find(15)) // 'fifteen'
console.log(tree.size) // 3

// Remove operations
tree.remove(10)
console.log(tree.size) // 2

new BPlusTree<T, K>(minDegree: number, unique: boolean = true, comparator?: (a: K, b: K) => number)

// Insert a key-value pair
tree.insert(key: K, value: T): boolean

// Examples
tree.insert(42, { name: 'Alice', age: 30 })
tree.insert('key1', 'value1')

// Find single value by key
tree.find(key: K): T | null

// Find all values for a key (useful for non-unique trees)
tree.find_all(key: K): T[]

// Examples
const user = tree.find(42)
const allUsers = tree.find_all('admin') // For duplicate keys

// Remove first occurrence of key
tree.remove(key: K): boolean

// Remove all occurrences of key
tree.remove_all(key: K): number

// Examples
tree.remove(42) // Remove first occurrence
tree.remove_all('temp') // Remove all occurrences

// Get tree size (total number of key-value pairs)
tree.size: number

// Count occurrences of a specific key
tree.count(key: K): number

// Check if tree contains key
tree.contains(key: K): boolean

// Get all keys in sorted order
tree.keys(): K[]

// Get all values
tree.values(): T[]

// Get all key-value pairs
tree.entries(): [K, T][]

import { TransactionContext } from 'b-pl-tree'

// Create a transaction context
const txCtx = new TransactionContext(tree)

// Perform transactional operations
tree.insert_in_transaction(10, 'ten', txCtx)
tree.insert_in_transaction(20, 'twenty', txCtx)

// Find within transaction (sees uncommitted changes)
const value = tree.get_all_in_transaction(10, txCtx) // ['ten']

// Commit the transaction
await txCtx.commit()

// Or abort the transaction
// await txCtx.abort()

tree.insert_in_transaction(key: K, value: T, txCtx: TransactionContext<T, K>): boolean

// Remove single occurrence
tree.remove_in_transaction(key: K, txCtx: TransactionContext<T, K>, all?: false): boolean

// Remove all occurrences
tree.remove_in_transaction(key: K, txCtx: TransactionContext<T, K>, all: true): boolean

tree.get_all_in_transaction(key: K, txCtx: TransactionContext<T, K>): T[]

// Commit transaction (apply all changes)
await txCtx.commit(): Promise<void>

// Abort transaction (discard all changes)
await txCtx.abort(): Promise<void>

// Check if transaction is active
txCtx.isActive(): boolean

// Phase 1: Prepare
const canCommit = await txCtx.prepareCommit()

if (canCommit) {
  // Phase 2: Finalize commit
  await txCtx.finalizeCommit()
} else {
  // Abort if prepare failed
  await txCtx.abort()
}

// Prepare phase - validate and lock resources
txCtx.prepareCommit(): Promise<boolean>

// Finalize phase - apply changes atomically
txCtx.finalizeCommit(): Promise<void>

// Abort after prepare
txCtx.abort(): Promise<void>

import { TransactionContext } from 'b-pl-tree'

// Create a transaction context
const txCtx = new TransactionContext(tree)

// Make some changes
tree.insert_in_transaction(10, 'ten', txCtx)
tree.insert_in_transaction(20, 'twenty', txCtx)

// Create a savepoint
const savepointId = await txCtx.createSavepoint('checkpoint-1')

// Make more changes
tree.insert_in_transaction(30, 'thirty', txCtx)
tree.remove_in_transaction(10, txCtx)

// Rollback to savepoint (reverts changes made after savepoint creation)
await txCtx.rollbackToSavepoint(savepointId)

// Now: 10='ten', 20='twenty' exist, but 30 and removal of 10 are reverted
console.log(tree.find_in_transaction(10, txCtx)) // ['ten'] - restored
console.log(tree.find_in_transaction(20, txCtx)) // ['twenty'] - remains
console.log(tree.find_in_transaction(30, txCtx)) // undefined - reverted

// Commit the transaction
await txCtx.commit()

// Create a named savepoint
const savepointId = await txCtx.createSavepoint(name: string): Promise<string>

// Returns unique savepoint ID for later reference
console.log(savepointId) // "sp-tx-1234567890-abc123-1-1234567890"

// Rollback to a specific savepoint
await txCtx.rollbackToSavepoint(savepointId: string): Promise<void>

// Reverts all changes made after the savepoint was created
// Automatically removes any newer savepoints

// Release a savepoint to free memory
await txCtx.releaseSavepoint(savepointId: string): Promise<void>

// Savepoint data is cleaned up, but transaction state remains unchanged

// Get list of all savepoints (sorted by name)
const savepoints = txCtx.listSavepoints(): string[]
console.log(savepoints)
// ["checkpoint-1 (sp-tx-...) - 2024-01-15T10:30:00.000Z"]

// Get detailed information about a savepoint
const info = txCtx.getSavepointInfo(savepointId: string): SavepointInfo | undefined
console.log(info)
// {
//   savepointId: "sp-tx-1234567890-abc123-1-1234567890",
//   name: "checkpoint-1",
//   timestamp: 1705315800000,
//   workingNodesCount: 2,
//   deletedNodesCount: 0
// }

const txCtx = new TransactionContext(tree)

// Initial state
tree.insert_in_transaction(1, 'one', txCtx)

// First savepoint
const sp1 = await txCtx.createSavepoint('level-1')
tree.insert_in_transaction(2, 'two', txCtx)

// Second savepoint (nested)
const sp2 = await txCtx.createSavepoint('level-2')
tree.insert_in_transaction(3, 'three', txCtx)

// Third savepoint (nested deeper)
const sp3 = await txCtx.createSavepoint('level-3')
tree.insert_in_transaction(4, 'four', txCtx)

// Rollback to level-2 (removes level-3 savepoint automatically)
await txCtx.rollbackToSavepoint(sp2)

// State: 1='one', 2='two', 3='three' (4 is reverted)
// Available savepoints: level-1, level-2 (level-3 is removed)

console.log(txCtx.listSavepoints().length) // 2

async function complexOperation(txCtx: TransactionContext<string, number>) {
  // Create savepoint before risky operation
  const safepointId = await txCtx.createSavepoint('before-risky-operation')

  try {
    // Perform risky operations
    tree.insert_in_transaction(100, 'hundred', txCtx)
    tree.remove_in_transaction(50, txCtx) // Might fail

    // Validate results
    if (tree.find_in_transaction(100, txCtx) === undefined) {
      throw new Error('Validation failed')
    }

    // Success - release savepoint
    await txCtx.releaseSavepoint(safepointId)
    return true

  } catch (error) {
    // Error - rollback to savepoint
    console.log('Operation failed, rolling back:', error.message)
    await txCtx.rollbackToSavepoint(safepointId)
    return false
  }
}

// Usage
const txCtx = new TransactionContext(tree)
const success = await complexOperation(txCtx)

if (success) {
  await txCtx.commit()
} else {
  await txCtx.abort()
}

async function batchProcessWithCheckpoints(
  items: Array<[number, string]>,
  checkpointInterval: number = 100
) {
  const txCtx = new TransactionContext(tree)
  let lastCheckpoint: string | undefined

  try {
    for (let i = 0; i < items.length; i++) {
      const [key, value] = items[i]

      // Create checkpoint every N items
      if (i % checkpointInterval === 0) {
        if (lastCheckpoint) {
          await txCtx.releaseSavepoint(lastCheckpoint)
        }
        lastCheckpoint = await txCtx.createSavepoint(`checkpoint-${i}`)
      }

      // Process item
      tree.insert_in_transaction(key, value, txCtx)

      // Validate item (example)
      if (key < 0) {
        throw new Error(`Invalid key: ${key}`)
      }
    }

    // Success - commit all changes
    await txCtx.commit()
    return { success: true, processed: items.length }

  } catch (error) {
    // Error - rollback to last checkpoint
    if (lastCheckpoint) {
      console.log('Rolling back to last checkpoint')
      await txCtx.rollbackToSavepoint(lastCheckpoint)

      // Could continue processing from checkpoint or abort
      await txCtx.abort()
    } else {
      await txCtx.abort()
    }

    return { success: false, error: error.message }
  }
}

// Usage
const result = await batchProcessWithCheckpoints([
  [1, 'one'],
  [2, 'two'],
  [3, 'three']
])

async function multiStageTransaction() {
  const txCtx = new TransactionContext(tree)

  try {
    // Stage 1: Data preparation
    const stage1 = await txCtx.createSavepoint('stage-1-complete')
    tree.insert_in_transaction(10, 'prepared-data', txCtx)

    // Stage 2: Data transformation
    const stage2 = await txCtx.createSavepoint('stage-2-complete')
    tree.insert_in_transaction(20, 'transformed-data', txCtx)

    // Stage 3: Data validation (might fail)
    const stage3 = await txCtx.createSavepoint('stage-3-complete')
    tree.insert_in_transaction(30, 'validated-data', txCtx)

    // Simulate validation failure
    const isValid = Math.random() > 0.5
    if (!isValid) {
      // Rollback to stage 2 and try alternative approach
      await txCtx.rollbackToSavepoint(stage2)
      tree.insert_in_transaction(31, 'alternative-data', txCtx)
    }

    // Final commit
    await txCtx.commit()
    console.log('Multi-stage transaction completed successfully')

  } catch (error) {
    console.log('Transaction failed:', error.message)
    await txCtx.abort()
  }
}

// ✅ Good: Release savepoints when no longer needed
const sp1 = await txCtx.createSavepoint('temp-checkpoint')
// ... do work ...
await txCtx.releaseSavepoint(sp1) // Free memory

// ✅ Good: Savepoints are automatically cleaned up on commit/abort
await txCtx.commit() // All savepoints are released

// ❌ Avoid: Creating too many savepoints without cleanup
for (let i = 0; i < 1000; i++) {
  await txCtx.createSavepoint(`sp-${i}`) // Memory leak!
}

// ✅ Good: Descriptive names
await txCtx.createSavepoint('before-user-validation')
await txCtx.createSavepoint('after-data-import')
await txCtx.createSavepoint('pre-calculation-phase')

// ❌ Avoid: Generic names
await txCtx.createSavepoint('sp1')
await txCtx.createSavepoint('temp')

// ✅ Good: Handle savepoint errors
try {
  await txCtx.rollbackToSavepoint('non-existent')
} catch (error) {
  console.log('Savepoint not found:', error.message)
  // Handle gracefully
}

// ✅ Good: Check savepoint existence
const info = txCtx.getSavepointInfo(savepointId)
if (info) {
  await txCtx.rollbackToSavepoint(savepointId)
} else {
  console.log('Savepoint no longer exists')
}

import { SavepointInfo, SavepointSnapshot } from 'b-pl-tree'

// Savepoint information
interface SavepointInfo {
  savepointId: string      // Unique identifier
  name: string             // User-provided name
  timestamp: number        // Creation timestamp
  workingNodesCount: number // Number of modified nodes
  deletedNodesCount: number // Number of deleted nodes
}

// Internal snapshot structure (for advanced use)
interface SavepointSnapshot<T, K> {
  savepointId: string
  name: string
  timestamp: number
  workingRootId: number | undefined
  workingNodesSnapshot: Map<number, Node<T, K>>
  deletedNodesSnapshot: Set<number>
}

interface User {
  id: number
  name: string
  email: string
  age: number
}

const userTree = new BPlusTree<User, number>(3, true)

// Insert users
userTree.insert(1, { id: 1, name: 'Alice', email: '[email protected]', age: 30 })
userTree.insert(2, { id: 2, name: 'Bob', email: '[email protected]', age: 25 })

// Find user
const alice = userTree.find(1)
console.log(alice?.name) // 'Alice'

// Create tree allowing duplicate keys (e.g., age index)
const ageIndex = new BPlusTree<User, number>(3, false)

// Multiple users can have the same age
ageIndex.insert(25, { id: 1, name: 'Alice', email: '[email protected]', age: 25 })
ageIndex.insert(25, { id: 2, name: 'Bob', email: '[email protected]', age: 25 })
ageIndex.insert(30, { id: 3, name: 'Charlie', email: '[email protected]', age: 30 })

// Find all users aged 25
const users25 = ageIndex.find_all(25) // Returns both Alice and Bob
console.log(users25.length) // 2

// Transaction 1
const tx1 = new TransactionContext(tree)
tree.insert_in_transaction(100, 'tx1-value', tx1)

// Transaction 2 (concurrent)
const tx2 = new TransactionContext(tree)
tree.insert_in_transaction(200, 'tx2-value', tx2)

// tx1 cannot see tx2's changes and vice versa
console.log(tree.get_all_in_transaction(200, tx1)) // []
console.log(tree.get_all_in_transaction(100, tx2)) // []

// Commit tx1
await tx1.commit()

// Now main tree has tx1's changes, but tx2 still isolated
console.log(tree.find(100)) // 'tx1-value'
console.log(tree.get_all_in_transaction(100, tx2)) // [] (snapshot isolation)

// Commit tx2
await tx2.commit()
console.log(tree.find(200)) // 'tx2-value'

async function batchInsert(items: Array<[K, T]>) {
  const txCtx = new TransactionContext(tree)

  try {
    // Insert all items in transaction
    for (const [key, value] of items) {
      tree.insert_in_transaction(key, value, txCtx)
    }

    // Commit all changes atomically
    await txCtx.commit()
    return true
  } catch (error) {
    // Abort on any error
    await txCtx.abort()
    return false
  }
}

// Usage
const success = await batchInsert([
  [1, 'one'],
  [2, 'two'],
  [3, 'three']
])

import { serializeTree, deserializeTree, createTreeFrom } from 'b-pl-tree'

// Create and populate a tree
const tree = new BPlusTree<User, number>(3, false)
tree.insert(1, { id: 1, name: 'Alice', age: 30 })
tree.insert(2, { id: 2, name: 'Bob', age: 25 })
tree.insert(3, { id: 3, name: 'Charlie', age: 35 })

// Serialize tree to portable format
const serialized = serializeTree(tree)
console.log(serialized)
// {
//   t: 3,
//   unique: false,
//   root: 1,
//   next_node_id: 2,
//   nodes: [
//     { id: 1, leaf: true, keys: [1, 2, 3], pointers: [...], ... }
//   ]
// }

// Create a new empty tree
const newTree = new BPlusTree<User, number>()

// Deserialize data into the existing tree
deserializeTree(newTree, serialized)

// Tree now contains all the original data
console.log(newTree.size) // 3
console.log(newTree.find(1)) // { id: 1, name: 'Alice', age: 30 }

// Create tree directly from serialized data
const restoredTree = createTreeFrom<User, number>(serialized)

// Tree is ready to use
console.log(restoredTree.size) // 3
console.log(restoredTree.t) // 3 (from serialized data)
console.log(restoredTree.unique) // false (from serialized data)

// Override some options while preserving data
const customTree = createTreeFrom<User, number>(serialized, {
  t: 5,           // Will be overridden by serialized t=3
  unique: true,   // Will be overridden by serialized unique=false
  comparator: customComparator // Custom comparator will be used
})

// Serialized data takes precedence for t and unique
console.log(customTree.t) // 3 (from serialized data)
console.log(customTree.unique) // false (from serialized data)

// Simple object format
const simpleData = {
  'user1': { name: 'Alice', age: 30 },
  'user2': { name: 'Bob', age: 25 },
  'user3': { name: 'Charlie', age: 35 }
}

// Create tree from simple object
const tree = createTreeFrom<User, string>(simpleData)
console.log(tree.size) // 3

// Or deserialize into existing tree
const existingTree = new BPlusTree<User, string>()
deserializeTree(existingTree, simpleData)

import { writeFile, readFile } from 'fs/promises'

// Save tree to file
async function saveTreeToFile<T, K>(tree: BPlusTree<T, K>, filename: string): Promise<void> {
  const serialized = serializeTree(tree)
  const json = JSON.stringify(serialized, null, 2)
  await writeFile(filename, json, 'utf8')
}

// Load tree from file
async function loadTreeFromFile<T, K>(filename: string): Promise<BPlusTree<T, K>> {
  const json = await readFile(filename, 'utf8')
  const serialized = JSON.parse(json)
  return createTreeFrom<T, K>(serialized)
}

// Usage
await saveTreeToFile(userTree, 'users.json')
const loadedTree = await loadTreeFromFile<User, number>('users.json')

// Example with a database
class TreeRepository {
  async saveTree<T, K>(name: string, tree: BPlusTree<T, K>): Promise<void> {
    const serialized = serializeTree(tree)
    await db.query(
      'INSERT INTO trees (name, data) VALUES (?, ?) ON DUPLICATE KEY UPDATE data = ?',
      [name, JSON.stringify(serialized), JSON.stringify(serialized)]
    )
  }

  async loadTree<T, K>(name: string): Promise<BPlusTree<T, K> | null> {
    const result = await db.query('SELECT data FROM trees WHERE name = ?', [name])
    if (result.length === 0) return null

    const serialized = JSON.parse(result[0].data)
    return createTreeFrom<T, K>(serialized)
  }

  async restoreTreeInto<T, K>(name: string, tree: BPlusTree<T, K>): Promise<boolean> {
    const result = await db.query('SELECT data FROM trees WHERE name = ?', [name])
    if (result.length === 0) return false

    const serialized = JSON.parse(result[0].data)
    deserializeTree(tree, serialized)
    return true
  }
}

// Usage
const repo = new TreeRepository()

// Save
await repo.saveTree('user_index', userTree)

// Load
const loadedTree = await repo.loadTree<User, number>('user_index')

// Restore into existing tree
const existingTree = new BPlusTree<User, number>()
const restored = await repo.restoreTreeInto('user_index', existingTree)

try {
  // Serialization is generally safe
  const serialized = serializeTree(tree)

  // Deserialization handles malformed data gracefully
  const newTree = createTreeFrom(serialized)
} catch (error) {
  console.error('Serialization error:', error)
  // Handle error appropriately
}

// Graceful handling of invalid data
const malformedData = { invalid: 'data' }
deserializeTree(tree, malformedData) // Won't throw, tree remains unchanged

// Определяем тип составного ключа
interface CompositeKey {
  department: string
  level: number
  joinDate?: Date
}

// Создаем компаратор для составного ключа
const compositeComparator = (a: CompositeKey, b: CompositeKey): number => {
  // Обработка null/undefined значений
  if (!a || !b) {
    if (a === b) return 0
    return !a ? -1 : 1
  }

  // Сравнение по department (первый приоритет)
  if (a.department !== b.department) {
    return a.department.localeCompare(b.department)
  }

  // Сравнение по level (второй приоритет)
  if (a.level !== b.level) {
    return a.level - b.level
  }

  // Сравнение по joinDate (третий приоритет, опционально)
  if (a.joinDate && b.joinDate) {
    return a.joinDate.getTime() - b.joinDate.getTime()
  }
  if (a.joinDate && !b.joinDate) return 1
  if (!a.joinDate && b.joinDate) return -1

  return 0
}

// Создаем дерево с составным ключом
const employeeIndex = new BPlusTree<Employee, CompositeKey>(
  3,
  false, // Разрешаем дубликаты
  compositeComparator
)

interface Employee {
  id: number
  name: string
  department: string
  level: number
  joinDate: Date
  salary: number
}

// Вставка данных с составными ключами
const employees: Employee[] = [
  {
    id: 1,
    name: 'Alice Johnson',
    department: 'Engineering',
    level: 3,
    joinDate: new Date('2020-01-15'),
    salary: 95000
  },
  {
    id: 2,
    name: 'Bob Smith',
    department: 'Engineering',
    level: 2,
    joinDate: new Date('2021-03-10'),
    salary: 75000
  },
  {
    id: 3,
    name: 'Charlie Brown',
    department: 'Marketing',
    level: 3,
    joinDate: new Date('2019-08-22'),
    salary: 85000
  }
]

// Индексирование по составному ключу
employees.forEach(emp => {
  const compositeKey: CompositeKey = {
    department: emp.department,
    level: emp.level,
    joinDate: emp.joinDate
  }
  employeeIndex.insert(compositeKey, emp)
})

// Поиск по точному составному ключу
const engineeringLevel3 = employeeIndex.find_all({
  department: 'Engineering',
  level: 3
})

// Поиск с частичным ключом (используя query API)
import { sourceEach, filter, executeQuery } from 'b-pl-tree'

const engineeringEmployees = executeQuery(
  sourceEach<Employee, CompositeKey>(true),
  filter(([key, _]) => key.department === 'Engineering')
)(employeeIndex)

// Использование массивов для составных ключей
import { compare_keys_array } from 'b-pl-tree'

// Составной ключ: [год, месяц, день, час]
type DateTimeKey = [number, number, number, number]

const timeSeriesIndex = new BPlusTree<SensorReading, DateTimeKey>(
  3,
  false,
  compare_keys_array // Встроенный компаратор для массивов
)

interface SensorReading {
  sensorId: string
  value: number
  timestamp: Date
}

// Вставка данных временных рядов
const readings: SensorReading[] = [
  {
    sensorId: 'temp-01',
    value: 23.5,
    timestamp: new Date('2024-01-15T10:30:00')
  },
  {
    sensorId: 'temp-02',
    value: 24.1,
    timestamp: new Date('2024-01-15T10:31:00')
  }
]

readings.forEach(reading => {
  const date = reading.timestamp
  const key: DateTimeKey = [
    date.getFullYear(),
    date.getMonth() + 1,
    date.getDate(),
    date.getHours()
  ]
  timeSeriesIndex.insert(key, reading)
})

// Поиск данных за конкретный час
const hourlyData = timeSeriesIndex.find_all([2024, 1, 15, 10])

// Создание системы многоуровневых индексов
class EmployeeDatabase {
  // Первичный индекс по ID
  private primaryIndex = new BPlusTree<Employee, number>(3, true)

  // Вторичный индекс по отделу и уровню
  private departmentLevelIndex = new BPlusTree<Employee, CompositeKey>(
    3,
    false,
    compositeComparator
  )

  // Индекс по зарплате (для диапазонных запросов)
  private salaryIndex = new BPlusTree<Employee, number>(3, false)

  addEmployee(employee: Employee): void {
    // Вставка в первичный индекс
    this.primaryIndex.insert(employee.id, employee)

    // Вставка во вторичные индексы
    this.departmentLevelIndex.insert({
      department: employee.department,
      level: employee.level,
      joinDate: employee.joinDate
    }, employee)

    this.salaryIndex.insert(employee.salary, employee)
  }

  // Поиск по ID (быстрый поиск)
  findById(id: number): Employee | null {
    return this.primaryIndex.find(id)
  }

  // Поиск по отделу и уровню
  findByDepartmentAndLevel(department: string, level: number): Employee[] {
    return this.departmentLevelIndex.find_all({
      department,
      level
    })
  }

  // Поиск в диапазоне зарплат
  findBySalaryRange(minSalary: number, maxSalary: number): Employee[] {
    const results: Employee[] = []

    // Используем query API для диапазонного поиска
    const generator = executeQuery(
      sourceRange<Employee, number>(minSalary, maxSalary, true, true),
      filter(([salary, _]) => salary >= minSalary && salary <= maxSalary)
    )(this.salaryIndex)

    for (const cursor of generator) {
      results.push(cursor.value)
    }

    return results
  }
}

// Транзакционные операции с несколькими индексами
async function addEmployeeTransactionally(
  database: EmployeeDatabase,
  employee: Employee
): Promise<boolean> {
  const primaryTx = database.primaryIndex.begin_transaction()
  const departmentTx = database.departmentLevelIndex.begin_transaction()
  const salaryTx = database.salaryIndex.begin_transaction()

  try {
    // Вставка во все индексы в рамках транзакций
    database.primaryIndex.insert_in_transaction(employee.id, employee, primaryTx)

    database.departmentLevelIndex.insert_in_transaction({
      department: employee.department,
      level: employee.level,
      joinDate: employee.joinDate
    }, employee, departmentTx)

    database.salaryIndex.insert_in_transaction(employee.salary, employee, salaryTx)

    // Подготовка к коммиту (2PC)
    const canCommit = await Promise.all([
      primaryTx.prepareCommit(),
      departmentTx.prepareCommit(),
      salaryTx.prepareCommit()
    ])

    if (canCommit.every(result => result)) {
      // Финализация коммита
      await Promise.all([
        primaryTx.finalizeCommit(),
        departmentTx.finalizeCommit(),
        salaryTx.finalizeCommit()
      ])
      return true
    } else {
      throw new Error('Prepare phase failed')
    }
  } catch (error) {
    // Откат всех транзакций
    await Promise.all([
      primaryTx.abort(),
      departmentTx.abort(),
      salaryTx.abort()
    ])
    return false
  }
}

import { compare_keys_primitive } from 'b-pl-tree'

// Автоматически используется по умолчанию для number, string, boolean
const simpleTree = new BPlusTree<User, number>(3, true)
// Эквивалентно:
const explicitTree = new BPlusTree<User, number>(3, true, compare_keys_primitive)

// Поддерживает сравнение:
// - Чисел: 1 < 2 < 3
// - Строк: 'a' < 'b' < 'c' (лексикографическое сравнение)
// - Булевых значений: false < true
// - Смешанных типов с приоритетом: boolean < number < string

import { compare_keys_array } from 'b-pl-tree'

// Сравнивает массивы поэлементно
const arrayTree = new BPlusTree<Data, number[]>(3, false, compare_keys_array)

// Примеры сравнения:
// [1, 2] < [1, 3]     (второй элемент больше)
// [1, 2] < [1, 2, 3]  (первый массив короче)
// [2] > [1, 9, 9]     (первый элемент больше)

// Практическое применение - временные ряды
type TimeKey = [year: number, month: number, day: number, hour: number]
const timeSeriesTree = new BPlusTree<SensorData, TimeKey>(3, false, compare_keys_array)

// Автоматическая сортировка по времени:
timeSeriesTree.insert([2024, 1, 15, 10], data1)  // 2024-01-15 10:00
timeSeriesTree.insert([2024, 1, 15, 9], data2)   // 2024-01-15 09:00
timeSeriesTree.insert([2024, 1, 16, 8], data3)   // 2024-01-16 08:00

import { compare_keys_object } from 'b-pl-tree'

// Сравнивает объекты по всем свойствам в алфавитном порядке ключей
interface ProductKey {
  category: string
  brand: string
  price: number
}

const productTree = new BPlusTree<Product, ProductKey>(
  3,
  false,
  compare_keys_object
)

// Порядок сравнения: brand -> category -> price (алфавитный порядок ключей)
// Примеры:
// { brand: 'Apple', category: 'Electronics', price: 999 }
// < { brand: 'Apple', category: 'Electronics', price: 1099 }
// < { brand: 'Samsung', category: 'Electronics', price: 899 }

// ВАЖНО: Все объекты должны иметь одинаковую структуру ключей

// Пример: сортировка по отделу (по возрастанию), затем по зарплате (по убыванию)
interface EmployeeSortKey {
  department: string  // ASC
  salary: number      // DESC
  joinDate: Date      // ASC
}

const mixedSortComparator = (a: EmployeeSortKey, b: EmployeeSortKey): number => {
  // 1. Отдел по возрастанию (A-Z)
  if (a.department !== b.department) {
    return a.department.localeCompare(b.department) // ASC
  }

  // 2. Зарплата по убыванию (высокая -> низкая)
  if (a.salary !== b.salary) {
    return b.salary - a.salary // DESC (обратный порядок)
  }

  // 3. Дата приема по возрастанию (старые -> новые)
  return a.joinDate.getTime() - b.joinDate.getTime() // ASC
}

// Результат сортировки:
// Engineering, $100000, 2020-01-01
// Engineering, $95000,  2021-01-01
// Engineering, $90000,  2019-01-01
// Marketing,   $85000,  2020-06-01
// Marketing,   $80000,  2021-03-01

// Пример: система рейтингов с приоритетами
interface RatingKey {
  priority: number    // DESC (высокий приоритет первым)
  score: number       // DESC (высокий балл первым)
  timestamp: Date     // ASC (старые записи первыми при равенстве)
}

const priorityComparator = (a: RatingKey, b: RatingKey): number => {
  // 1. Приоритет по убыванию (1 = высший, 5 = низший)
  if (a.priority !== b.priority) {
    return a.priority - b.priority // ASC для приоритета (1, 2, 3, 4, 5)
  }

  // 2. Балл по убыванию (100 -> 0)
  if (a.score !== b.score) {
    return b.score - a.score // DESC
  }

  // 3. Время по возрастанию (FIFO при равенстве)
  return a.timestamp.getTime() - b.timestamp.getTime() // ASC
}

// Пример: сортировка локаций
interface LocationKey {
  country: string     // ASC (алфавитный порядок)
  population: number  // DESC (большие города первыми)
  name: string        // ASC (алфавитный порядок городов)
}

const geoComparator = (a: LocationKey, b: LocationKey): number => {
  // 1. Страна по алфавиту
  if (a.country !== b.country) {
    return a.country.localeCompare(b.country)
  }

  // 2. Население по убыванию (мегаполисы первыми)
  if (a.population !== b.population) {
    return b.population - a.population
  }

  // 3. Название города по алфавиту
  return a.name.localeCompare(b.name)
}

// Результат:
// Russia, Moscow, 12000000
// Russia, SPb, 5000000
// Russia, Kazan, 1200000
// USA, NYC, 8000000
// USA, LA, 4000000

// Пример: сортировка версий ПО
interface VersionKey {
  major: number       // DESC (новые версии первыми)
  minor: number       // DESC
  patch: number       // DESC
  isStable: boolean   // DESC (стабильные версии первыми)
}

const versionComparator = (a: VersionKey, b: VersionKey): number => {
  // 1. Стабильность (true > false)
  if (a.isStable !== b.isStable) {
    return b.isStable ? 1 : -1 // Стабильные первыми
  }

  // 2. Major версия по убыванию
  if (a.major !== b.major) {
    return b.major - a.major
  }

  // 3. Minor версия по убыванию
  if (a.minor !== b.minor) {
    return b.minor - a.minor
  }

  // 4. Patch версия по убыванию
  return b.patch - a.patch
}

// Результат:
// 2.1.0 (stable)
// 2.0.5 (stable)
// 2.0.0 (stable)
// 2.2.0 (beta)
// 2.1.1 (beta)

// Компаратор с приоритетами полей
interface EmployeeKey {
  department: string
  level: number
  joinDate: Date
}

const employeeComparator = (a: EmployeeKey, b: EmployeeKey): number => {
  // Приоритет 1: Отдел
  if (a.department !== b.department) {
    return a.department.localeCompare(b.department)
  }

  // Приоритет 2: Уровень (по убыванию)
  if (a.level !== b.level) {
    return b.level - a.level // Обратный порядок
  }

  // Приоритет 3: Дата приема на работу
  return a.joinDate.getTime() - b.joinDate.getTime()
}

// Компаратор с обработкой null/undefined
const nullSafeComparator = (a: string | null, b: string | null): number => {
  if (a === null && b === null) return 0
  if (a === null) return -1  // null считается меньше
  if (b === null) return 1
  return a.localeCompare(b)
}

// Компаратор для сложных вложенных структур
interface LocationKey {
  country: string
  city: string
  coordinates: { lat: number; lng: number }
}

const locationComparator = (a: LocationKey, b: LocationKey): number => {
  // Сначала по стране
  if (a.country !== b.country) {
    return a.country.localeCompare(b.country)
  }

  // Затем по городу
  if (a.city !== b.city) {
    return a.city.localeCompare(b.city)
  }

  // Наконец по координатам (сначала широта, потом долгота)
  if (a.coordinates.lat !== b.coordinates.lat) {
    return a.coordinates.lat - b.coordinates.lat
  }

  return a.coordinates.lng - b.coordinates.lng
}

// Оптимизированный компаратор для частых сравнений
const optimizedComparator = (a: ComplexKey, b: ComplexKey): number => {
  // Быстрое сравнение наиболее различающихся полей в первую очередь

  // 1. Числовые поля сравниваются быстрее строковых
  if (a.numericField !== b.numericField) {
    return a.numericField - b.numericField
  }

  // 2. Короткие строки сравниваются быстрее длинных
  if (a.shortString !== b.shortString) {
    return a.shortString.localeCompare(b.shortString)
  }

  // 3. Дорогие операции в последнюю очередь
  return a.expensiveField.localeCompare(b.expensiveField)
}

// Кэширование результатов для очень дорогих компараторов
const memoizedComparator = (() => {
  const cache = new Map<string, number>()

  return (a: ComplexKey, b: ComplexKey): number => {
    const cacheKey = `${JSON.stringify(a)}_${JSON.stringify(b)}`

    if (cache.has(cacheKey)) {
      return cache.get(cacheKey)!
    }

    const result = expensiveComparisonLogic(a, b)
    cache.set(cacheKey, result)
    return result
  }
})()

// Индекс для таблицы заказов: (customer_id, order_date, order_id)
interface OrderKey {
  customerId: number
  orderDate: Date
  orderId: number
}

const orderComparator = (a: OrderKey, b: OrderKey): number => {
  if (a.customerId !== b.customerId) return a.customerId - b.customerId
  if (a.orderDate.getTime() !== b.orderDate.getTime()) {
    return a.orderDate.getTime() - b.orderDate.getTime()
  }
  return a.orderId - b.orderId
}

// Эффективные запросы:
// - Все заказы клиента
// - Заказы клиента за период
// - Конкретный заказ

// Индекс для геолокации: (страна, регион, город, почтовый_код)
type GeoKey = [country: string, region: string, city: string, postalCode: string]

const geoIndex = new BPlusTree<Location, GeoKey>(3, false, compare_keys_array)

// Быстрый поиск по иерархии:
// - Все локации в стране
// - Все города в регионе
// - Точный адрес

// Метрики по времени: (метрика, год, месяц, день, час)
type MetricKey = [metric: string, year: number, month: number, day: number, hour: number]

const metricsIndex = new BPlusTree<MetricData, MetricKey>(3, false, compare_keys_array)

// Агрегация данных:
// - Все метрики за день
// - Конкретная метрика за период
// - Почасовая детализация

// Каталог товаров: (категория, подкатегория, бренд, модель)
interface ProductCatalogKey {
  category: string
  subcategory: string
  brand: string
  model: string
}

// Навигация по каталогу:
// - Все товары категории
// - Товары бренда в подкатегории
// - Конкретная модель

// Версии документов: (проект, документ, версия_мажор, версия_минор)
type VersionKey = [project: string, document: string, major: number, minor: number]

const versionIndex = new BPlusTree<DocumentVersion, VersionKey>(3, false, compare_keys_array)

// Управление версиями:
// - Все версии документа
// - Последняя версия проекта
// - Конкретная версия

// ❌ Неэффективный порядок (редко используемое поле первым)
interface BadKey {
  timestamp: Date    // Уникальное значение
  category: string   // Часто используется в запросах
  userId: number     // Часто используется в запросах
}

// ✅ Эффективный порядок (часто используемые поля первыми)
interface GoodKey {
  category: string   // Часто используется в запросах
  userId: number     // Часто используется в запросах
  timestamp: Date    // Уникальное значение для сортировки
}

// Располагайте поля по убыванию селективности
interface OptimalKey {
  highSelectivity: string    // Много уникальных значений
  mediumSelectivity: number  // Средняя селективность
  lowSelectivity: boolean    // Мало уникальных значений
}

// ❌ Слишком большие ключи
interface HeavyKey {
  longDescription: string  // Может быть очень длинным
  metadata: object        // Сложная структура
}

// ✅ Компактные ключи
interface LightKey {
  id: number             // Компактный идентификатор
  type: string           // Короткая строка
  priority: number       // Числовое значение
}

import { query, map, filter, reduce } from 'b-pl-tree'

// Complex query example
const result = await query(
  tree.includes([1, 3, 5]), // Get specific keys
  filter(([key, value]) => value.age > 20), // Filter by condition
  map(([key, value]) => ({ ...value, key })), // Transform data
  reduce((acc, item) => {
    acc.set(item.name, item)
    return acc
  }, new Map()) // Reduce to final result
)(tree)

// Strongly typed tree
const stringTree = new BPlusTree<string, number>(3)
stringTree.insert(1, "hello") // ✅ Valid
stringTree.insert("1", "hello") // ❌ Type error

// Custom key types
const dateTree = new BPlusTree<Event, string>(3, true, (a, b) => a.localeCompare(b))

// Custom string comparator (case-insensitive)
const tree = new BPlusTree<string, string>(3, true, (a, b) =>
  a.toLowerCase().localeCompare(b.toLowerCase())
)

// Date comparator
const dateTree = new BPlusTree<Event, Date>(3, true, (a, b) =>
  a.getTime() - b.getTime()
)

try {
  const txCtx = new TransactionContext(tree)

  // Transactional operations
  tree.insert_in_transaction(key, value, txCtx)

  // Commit with error handling
  await txCtx.commit()
} catch (error) {
  console.error('Transaction failed:', error)
  // Transaction is automatically aborted on error
}

// Tree statistics
console.log(`Tree size: ${tree.size}`)
console.log(`Tree height: ${tree.height}`)
console.log(`Node count: ${tree.nodeCount}`)

// Debug tree structure
tree.printTree() // Prints tree structure to console

// Validate tree integrity
const isValid = tree.validate()
console.log(`Tree is valid: ${isValid}`)