package com.cube.index;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
* Cubic Index Tree - Multi-level index using cubic progression.
*
* Index levels:
* Level 1: 1³×6 = 6
* Level 2: 2³×6 = 48
* Level 3: 3³×6 = 162
* Level 4: 4³×6 = 384
* Level 5: 5³×6 = 750
* ...
*
* Each level has 6 sides for distributing data.
* Keys are routed to appropriate level based on hash value.
*/
public class CubicIndexTree {
private static final Logger logger = LoggerFactory.getLogger(CubicIndexTree.class);
private final ConcurrentSkipListMap<Integer, CubicIndexNode> levels;
private final ReadWriteLock treeLock;
private final int maxLevels;
private final boolean autoExpand;
/**
* Create a cubic index tree
*
* @param initialLevels Number of initial levels to create
* @param maxLevels Maximum levels allowed
* @param autoExpand Whether to automatically create new levels
*/
public CubicIndexTree(int initialLevels, int maxLevels, boolean autoExpand) {
this.levels = new ConcurrentSkipListMap<>();
this.treeLock = new ReentrantReadWriteLock();
this.maxLevels = maxLevels;
this.autoExpand = autoExpand;
// Create initial levels
for (int i = 1; i <= initialLevels; i++) {
levels.put(i, new CubicIndexNode(i));
}
logger.info("Cubic index tree created with {} levels (max: {}, auto-expand: {})",
initialLevels, maxLevels, autoExpand);
}
/**
* Create a cubic index tree with defaults
*/
public CubicIndexTree() {
this(5, 20, true); // 5 initial levels, up to 20, auto-expand
}
/**
* Calculate which level a key should go to based on its hash
*/
public int calculateLevel(String key) {
// Use hash to determine level
long hash = Math.abs((long) key.hashCode());
// Map hash to a level (1 to current max)
int currentMaxLevel = levels.isEmpty() ? 1 : levels.lastKey();
// Simple distribution: use modulo to spread across levels
// For better distribution, we could use more sophisticated hashing
int level = (int) (hash % currentMaxLevel) + 1;
// Ensure level exists
if (!levels.containsKey(level) && autoExpand && level <= maxLevels) {
expandToLevel(level);
}
return Math.min(level, currentMaxLevel);
}
/**
* Calculate optimal level based on data size
*/
public int calculateOptimalLevel(int estimatedSize) {
// Choose level based on capacity
// Each level can hold approximately indexValue entries
for (int level = 1; level <= maxLevels; level++) {
long capacity = CubicIndexNode.calculateCubicIndex(level);
if (capacity >= estimatedSize) {
return level;
}
}
return maxLevels;
}
/**
* Expand tree to include the specified level
*/
private void expandToLevel(int targetLevel) {
treeLock.writeLock().lock();
try {
int currentMax = levels.isEmpty() ? 0 : levels.lastKey();
for (int level = currentMax + 1; level <= targetLevel && level <= maxLevels; level++) {
if (!levels.containsKey(level)) {
levels.put(level, new CubicIndexNode(level));
logger.debug("Expanded cubic tree to level {}", level);
}
}
} finally {
treeLock.writeLock().unlock();
}
}
/**
* Put a key-value pair into the index
*/
public void put(String key, byte[] value) {
int level = calculateLevel(key);
CubicIndexNode node = levels.get(level);
if (node == null) {
throw new IllegalStateException("Level " + level + " does not exist");
}
node.put(key, value);
}
/**
* Get a value from the index
*/
public byte[] get(String key) {
// Try to find in the calculated level first
int level = calculateLevel(key);
CubicIndexNode node = levels.get(level);
if (node != null) {
byte[] value = node.get(key);
if (value != null) {
return value;
}
}
// If not found, search all levels (key might have been moved)
for (CubicIndexNode n : levels.values()) {
byte[] value = n.get(key);
if (value != null) {
return value;
}
}
return null;
}
/**
* Check if key exists in the index
*/
public boolean containsKey(String key) {
return get(key) != null;
}
/**
* Remove a key from the index
*/
public boolean remove(String key) {
// Search all levels
for (CubicIndexNode node : levels.values()) {
if (node.remove(key)) {
return true;
}
}
return false;
}
/**
* Get all keys in the index
*/
public Set<String> getAllKeys() {
Set<String> allKeys = new HashSet<>();
for (CubicIndexNode node : levels.values()) {
allKeys.addAll(node.getAllKeys());
}
return allKeys;
}
/**
* Search for keys matching a prefix
*/
public List<String> searchPrefix(String prefix) {
List<String> results = new ArrayList<>();
for (CubicIndexNode node : levels.values()) {
for (String key : node.getAllKeys()) {
if (key.startsWith(prefix)) {
results.add(key);
}
}
}
Collections.sort(results);
return results;
}
/**
* Range search between two keys
*/
public List<String> searchRange(String startKey, String endKey) {
List<String> results = new ArrayList<>();
for (CubicIndexNode node : levels.values()) {
for (String key : node.getAllKeys()) {
if (key.compareTo(startKey) >= 0 && key.compareTo(endKey) <= 0) {
results.add(key);
}
}
}
Collections.sort(results);
return results;
}
/**
* Get a specific level node
*/
public CubicIndexNode getLevel(int level) {
return levels.get(level);
}
/**
* Get number of levels
*/
public int getLevelCount() {
return levels.size();
}
/**
* Get total number of keys across all levels
*/
public int getTotalSize() {
int total = 0;
for (CubicIndexNode node : levels.values()) {
total += node.getTotalSize();
}
return total;
}
/**
* Rebalance the tree by redistributing keys
*/
public void rebalance() {
treeLock.writeLock().lock();
try {
logger.info("Rebalancing cubic index tree...");
// Collect all key-value pairs
Map<String, byte[]> allData = new HashMap<>();
for (CubicIndexNode node : levels.values()) {
for (String key : node.getAllKeys()) {
allData.put(key, node.get(key));
}
}
// Clear all nodes
for (CubicIndexNode node : levels.values()) {
for (String key : node.getAllKeys()) {
node.remove(key);
}
}
// Redistribute
for (Map.Entry<String, byte[]> entry : allData.entrySet()) {
put(entry.getKey(), entry.getValue());
}
logger.info("Rebalanced {} keys across {} levels", allData.size(), levels.size());
} finally {
treeLock.writeLock().unlock();
}
}
/**
* Get comprehensive statistics
*/
public Map<String, Object> getStats() {
Map<String, Object> stats = new LinkedHashMap<>();
stats.put("totalLevels", levels.size());
stats.put("maxLevels", maxLevels);
stats.put("autoExpand", autoExpand);
stats.put("totalKeys", getTotalSize());
// Per-level statistics
Map<String, Object> levelStats = new LinkedHashMap<>();
for (Map.Entry<Integer, CubicIndexNode> entry : levels.entrySet()) {
int level = entry.getKey();
CubicIndexNode node = entry.getValue();
Map<String, Object> nodeStats = new LinkedHashMap<>();
nodeStats.put("indexValue", node.getIndexValue());
nodeStats.put("keys", node.getTotalSize());
nodeStats.put("capacity", node.getIndexValue());
nodeStats.put("utilization",
String.format("%.2f%%", (node.getTotalSize() * 100.0) / node.getIndexValue()));
levelStats.put("Level-" + level, nodeStats);
}
stats.put("levels", levelStats);
// Distribution across sides
Map<String, Integer> sideDistribution = new LinkedHashMap<>();
for (CubicIndexNode.Side side : CubicIndexNode.Side.values()) {
int count = 0;
for (CubicIndexNode node : levels.values()) {
count += node.getSide(side).size();
}
sideDistribution.put(side.name(), count);
}
stats.put("sideDistribution", sideDistribution);
return stats;
}
/**
* Print tree structure
*/
public void printStructure() {
System.out.println("Cubic Index Tree Structure:");
System.out.println("===========================");
for (Map.Entry<Integer, CubicIndexNode> entry : levels.entrySet()) {
int level = entry.getKey();
CubicIndexNode node = entry.getValue();
System.out.printf("Level %d: Index=%d (%d³×6) - %d keys%n",
level, node.getIndexValue(), level, node.getTotalSize());
for (CubicIndexNode.Side side : CubicIndexNode.Side.values()) {
int count = node.getSide(side).size();
if (count > 0) {
System.out.printf(" %s: %d keys%n", side.name(), count);
}
}
}
System.out.println("===========================");
System.out.printf("Total: %d keys across %d levels%n", getTotalSize(), levels.size());
}
/**
* Clear all data
*/
public void clear() {
treeLock.writeLock().lock();
try {
for (CubicIndexNode node : levels.values()) {
for (String key : node.getAllKeys()) {
node.remove(key);
}
}
logger.info("Cleared all data from cubic index tree");
} finally {
treeLock.writeLock().unlock();
}
}
}
