Implement robust k-means with k-means++ initialization

Implement from scratch in Python (no scikit‑learn) a function kmeans(X, k, max_iter=300, tol=1e-4, random_state=0) that returns (centroids, labels). Requirements: a) Use k‑means++ initialization; b) Use vectorized NumPy operations for distance computation; c) Stop early when the maximum centroid shift is < tol; d) Handle empty clusters by re‑seeding to the point with the largest current assignment distance; e) Support an optional sample_weights array that reweights both assignment and centroid updates; f) Ensure deterministic behavior with random_state; g) Analyze time and space complexity in terms of n samples, d dimensions, and k clusters; h) Explain how you would test correctness (e.g., on simple 2D blobs) and diagnose convergence issues (e.g., inertia not decreasing). Provide the function signature, docstring, and well‑commented code.