A trick that can help AI's to write POV-Ray code, "force" them to write simple
python code, only using arrays. Classes and numpy & co are not allowed. AI's are
well trained on Python and bare bones python isn't far of POV-Ray.

I didn't test any of the code. It's just for illustatration.

Me: "can you generate python code for a red black tree, without the use of
external libraries (like numpy). Only use arrays and no classes"

it to three attempts before it (Copilot) dropped classes.

%<------%<------%<------
# Implementation of Red-Black Tree in Python using arrays and no classes

# NIL node is represented by 0
NIL = 0

# Tree structure as arrays
tree = [None]  # Store keys
color = [NIL]  # Color array: 0 for BLACK, 1 for RED
left = [NIL]
right = [NIL]
parent = [NIL]

# Root of the tree
root = NIL

def insert(key):
    global root

    new_node = len(tree)
    tree.append(key)
    color.append(1)  # New node is RED
    left.append(NIL)
    right.append(NIL)
    parent.append(NIL)

    parent_node = NIL
    current = root

    while current != NIL:
        parent_node = current
        if key < tree[current]:
            current = left[current]
        else:
            current = right[current]

    parent[new_node] = parent_node

    if parent_node == NIL:
        root = new_node
    elif key < tree[parent_node]:
        left[parent_node] = new_node
    else:
        right[parent_node] = new_node

    insert_fixup(new_node)

def insert_fixup(node):
    global root

    while node != root and color[parent[node]] == 1:
        if parent[node] == left[parent[parent[node]]]:
            uncle = right[parent[parent[node]]]
            if color[uncle] == 1:
                color[parent[node]] = 0
                color[uncle] = 0
                color[parent[parent[node]]] = 1
                node = parent[parent[node]]
            else:
                if node == right[parent[node]]:
                    node = parent[node]
                    left_rotate(node)
                color[parent[node]] = 0
                color[parent[parent[node]]] = 1
                right_rotate(parent[parent[node]])
        else:
            uncle = left[parent[parent[node]]]
            if color[uncle] == 1:
                color[parent[node]] = 0
                color[uncle] = 0
                color[parent[parent[node]]] = 1
                node = parent[parent[node]]
            else:
                if node == left[parent[node]]:
                    node = parent[node]
                    right_rotate(node)
                color[parent[node]] = 0
                color[parent[parent[node]]] = 1
                left_rotate(parent[parent[node]])
    color[root] = 0

def left_rotate(x):
    global root

    y = right[x]
    right[x] = left[y]
    if left[y] != NIL:
        parent[left[y]] = x
    parent[y] = parent[x]
    if parent[x] == NIL:
        root = y
    elif x == left[parent[x]]:
        left[parent[x]] = y
    else:
        right[parent[x]] = y
    left[y] = x
    parent[x] = y

def right_rotate(y):
    global root

    x = left[y]
    left[y] = right[x]
    if right[x] != NIL:
        parent[right[x]] = y
    parent[x] = parent[y]
    if parent[y] == NIL:
        root = x
    elif y == right[parent[y]]:
        right[parent[y]] = x
    else:
        left[parent[y]] = x
    right[x] = y
    parent[y] = x

# Example usage
insert(10)
insert(20)
insert(30)
insert(15)
insert(25)

# For debugging: print the tree structure
def print_tree():
    for i in range(1, len(tree)):
        print(f"Node {i}: key={tree[i]}, color={'RED' if color[i] == 1 else
'BLACK'}, left={left[i]}, right={right[i]}, parent={parent[i]}")

print_tree()

%<------%<------%<------


Me: "can you convert the code to POV-Ray?"


%<------%<------%<------
#declare NIL = 0; // NIL node is represented by 0

#declare tree = array[1] { NIL }; // Tree structure as an array
#declare color = array[1] { NIL }; // Color array: 0 for BLACK, 1 for RED
#declare left = array[1] { NIL };
#declare right = array[1] { NIL };
#declare parent = array[1] { NIL };
#declare root = NIL; // Root of the tree

#macro Insert(key)
    #declare new_node = dimension_size(tree, 1);
    #declare tree = concat(tree, array[1] { key });
    #declare color = concat(color, array[1] { 1 }); // New node is RED
    #declare left = concat(left, array[1] { NIL });
    #declare right = concat(right, array[1] { NIL });
    #declare parent = concat(parent, array[1] { NIL });

    #declare parent_node = NIL;
    #declare current = root;

    #while (current != NIL)
        #declare parent_node = current;
        #if (key < tree[current])
            #declare current = left[current];
        #else
            #declare current = right[current];
        #end
    #end

    #declare parent[new_node] = parent_node;

    #if (parent_node == NIL)
        #declare root = new_node;
    #elif (key < tree[parent_node])
        #declare left[parent_node] = new_node;
    #else
        #declare right[parent_node] = new_node;
    #end

    InsertFixup(new_node);
#end

#macro InsertFixup(node)
    #while (node != root & color[parent[node]] == 1)
        #if (parent[node] == left[parent[parent[node]]])
            #declare uncle = right[parent[parent[node]]];
            #if (color[uncle] == 1)
                #declare color[parent[node]] = 0;
                #declare color[uncle] = 0;
                #declare color[parent[parent[node]]] = 1;
                #declare node = parent[parent[node]];
            #else
                #if (node == right[parent[node]])
                    #declare node = parent[node];
                    LeftRotate(node);
                #end
                #declare color[parent[node]] = 0;
                #declare color[parent[parent[node]]] = 1;
                RightRotate(parent[parent[node]]);
            #end
        #else
            #declare uncle = left[parent[parent[node]]];
            #if (color[uncle] == 1)
                #declare color[parent[node]] = 0;
                #declare color[uncle] = 0;
                #declare color[parent[parent[node]]] = 1;
                #declare node = parent[parent[node]];
            #else
                #if (node == left[parent[node]])
                    #declare node = parent[node];
                    RightRotate(node);
                #end
                #declare color[parent[node]] = 0;
                #declare color[parent[parent[node]]] = 1;
                LeftRotate(parent[parent[node]]);
            #end
        #end
    #end
    #declare color[root] = 0;
#end

#macro LeftRotate(x)
    #declare y = right[x];
    #declare right[x] = left[y];
    #if (left[y] != NIL)
        #declare parent[left[y]] = x;
    #end
    #declare parent[y] = parent[x];
    #if (parent[x] == NIL)
        #declare root = y;
    #elif (x == left[parent[x]])
        #declare left[parent[x]] = y;
    #else
        #declare right[parent[x]] = y;
    #end
    #declare left[y] = x;
    #declare parent[x] = y;
#end

#macro RightRotate(y)
    #declare x = left[y];
    #declare left[y] = right[x];
    #if (right[x] != NIL)
        #declare parent[right[x]] = y;
    #end
    #declare parent[x] = parent[y];
    #if (parent[y] == NIL)
        #declare root = x;
    #elif (y == right[parent[y]])
        #declare right[parent[y]] = x;
    #else
        #declare left[parent[y]] = x;
    #end
    #declare right[x] = y;
    #declare parent[y] = x;
#end

// Example usage
Insert(10);
Insert(20);
Insert(30);
Insert(15);
Insert(25);
%<------%<------%<------


ingo

Post a reply to this message

the same thing with Mistral:

python:
# Constants for colors
RED = 0
BLACK = 1

# Node structure: [value, color, left_index, right_index, parent_index]
tree = []

def create_node(value, color, left, right, parent):
    return [value, color, left, right, parent]

def left_rotate(index):
    right_child_index = tree[index][3]
    tree[index][3] = tree[right_child_index][2]

    if tree[right_child_index][2] != None:
        tree[tree[right_child_index][2]][4] = index

    tree[right_child_index][4] = tree[index][4]

    if tree[index][4] == None:
        root_index = right_child_index
    elif index == tree[tree[index][4]][2]:
        tree[tree[index][4]][2] = right_child_index
    else:
        tree[tree[index][4]][3] = right_child_index

    tree[right_child_index][2] = index
    tree[index][4] = right_child_index

def right_rotate(index):
    left_child_index = tree[index][2]
    tree[index][2] = tree[left_child_index][3]

    if tree[left_child_index][3] != None:
        tree[tree[left_child_index][3]][4] = index

    tree[left_child_index][4] = tree[index][4]

    if tree[index][4] == None:
        root_index = left_child_index
    elif index == tree[tree[index][4]][3]:
        tree[tree[index][4]][3] = left_child_index
    else:
        tree[tree[index][4]][2] = left_child_index

    tree[left_child_index][3] = index
    tree[index][4] = left_child_index

def insert_fixup(index):
    while tree[tree[index][4]][1] == RED:
        if tree[index][4] == tree[tree[tree[index][4]][4]][2]:
            y = tree[tree[tree[index][4]][4]][3]
            if y != None and tree[y][1] == RED:
                tree[tree[index][4]][1] = BLACK
                tree[y][1] = BLACK
                tree[tree[tree[index][4]][4]][1] = RED
                index = tree[tree[index][4]][4]
            elif index == tree[tree[index][4]][3]:
                index = tree[index][4]
                left_rotate(index)
            tree[tree[index][4]][1] = BLACK
            tree[tree[tree[index][4]][4]][1] = RED
            right_rotate(tree[tree[index][4]][4])
        else:
            y = tree[tree[tree[index][4]][4]][2]
            if y != None and tree[y][1] == RED:
                tree[tree[index][4]][1] = BLACK
                tree[y][1] = BLACK
                tree[tree[tree[index][4]][4]][1] = RED
                index = tree[tree[index][4]][4]
            elif index == tree[tree[index][4]][2]:
                index = tree[index][4]
                right_rotate(index)
            tree[tree[index][4]][1] = BLACK
            tree[tree[tree[index][4]][4]][1] = RED
            left_rotate(tree[tree[index][4]][4])
    tree[root_index][1] = BLACK

def insert(value):
    global root_index
    new_node = create_node(value, RED, None, None, None)
    tree.append(new_node)
    new_index = len(tree) - 1

    if root_index is None:
        root_index = new_index
    else:
        current_index = root_index
        while True:
            if value < tree[current_index][0]:
                if tree[current_index][2] is None:
                    tree[current_index][2] = new_index
                    tree[new_index][4] = current_index
                    break
                else:
                    current_index = tree[current_index][2]
            else:
                if tree[current_index][3] is None:
                    tree[current_index][3] = new_index
                    tree[new_index][4] = current_index
                    break
                else:
                    current_index = tree[current_index][3]

    insert_fixup(new_index)

def inorder_traversal(index):
    if index is not None:
        inorder_traversal(tree[index][2])
        print(f'Value: {tree[index][0]}, Color: {"RED" if tree[index][1] == RED
else "BLACK"}')
        inorder_traversal(tree[index][3])

# Example usage
root_index = None
insert(10)
insert(20)
insert(30)
insert(15)
insert(25)

print("Inorder Traversal of the Red-Black Tree:")
inorder_traversal(root_index)



POV-Ray:

#version 3.7;
global_settings {
  assumed_gamma 1.0
}

#include "colors.inc"

// Constants for colors
#declare RED = rgb <1, 0, 0>;
#declare BLACK = rgb <0, 0, 0>;

// Node structure: [value, color, left_index, right_index, parent_index]
#declare Tree = array[50]; // Array to store tree nodes
#declare NodeSize = 0.5;
#declare NodeSpacing = 2.0;
#declare RootIndex = 0;

// Macro to create a node
#macro CreateNode(index, value, color, left, right, parent)
  #declare Tree[index] = array[6];
  #declare Tree[index][0] = value;
  #declare Tree[index][1] = color;
  #declare Tree[index][2] = left;
  #declare Tree[index][3] = right;
  #declare Tree[index][4] = parent;
  #declare Tree[index][5] = 0; // Flag to check if the node is used
  #declare Tree[index][5] = 1;
#end

// Macro to draw a node
#macro DrawNode(index)
  #if (Tree[index][5] = 1)
    sphere {
      <Tree[index][0] * NodeSpacing, -index * NodeSpacing, 0>, NodeSize
      texture {
        pigment { Tree[index][1] }
        finish { ambient 0.1 diffuse 0.6 }
      }
    }
  #end
#end

// Macro to draw an edge
#macro DrawEdge(parent_index, child_index)
  #if (Tree[child_index][5] = 1)
    cylinder {
      <Tree[parent_index][0] * NodeSpacing, -parent_index * NodeSpacing, 0>,
      <Tree[child_index][0] * NodeSpacing, -child_index * NodeSpacing, 0>,
      NodeSize / 4
      texture {
        pigment { BLACK }
        finish { ambient 0.1 diffuse 0.6 }
      }
    }
  #end
#end

// Macro to insert a value into the tree
#macro Insert(value)
  #declare new_index = 0;
  #while (Tree[new_index][5] = 1 & new_index < 50)
    #declare new_index = new_index + 1;
  #end
  #if (new_index < 50)
    #declare current_index = RootIndex;
    #while (Tree[current_index][5] = 1)
      #if (value < Tree[current_index][0])
        #if (Tree[current_index][2] = -1)
          #declare Tree[current_index][2] = new_index;
          #break
        #else
          #declare current_index = Tree[current_index][2];
        #end
      #else
        #if (Tree[current_index][3] = -1)
          #declare Tree[current_index][3] = new_index;
          #break
        #else
          #declare current_index = Tree[current_index][3];
        #end
      #end
    #end
    CreateNode(new_index, value, RED, -1, -1, current_index)
    #if (RootIndex = 0)
      #declare RootIndex = new_index;
    #end
  #end
#end

camera {
  location <0, -15, 10>
  look_at <0, 0, 0>
}

light_source {
  <2, -4, 5>
  color rgb <1, 1, 1>
}

// Insert values into the tree
Insert(10)
Insert(20)
Insert(30)
Insert(15)
Insert(25)

// Draw the tree
#declare index = 0;
#while (index < 50)
  DrawNode(index)
  #if (Tree[index][2] != -1)
    DrawEdge(index, Tree[index][2])
  #end
  #if (Tree[index][3] != -1)
    DrawEdge(index, Tree[index][3])
  #end
  #declare index = index + 1;
#end

Post a reply to this message

Same thing with Claude:

Python: first try

%<------%<------%<------
# Red-Black Tree implementation using arrays
# Colors: RED = True, BLACK = False

# Each node is represented as a tuple in the array:
# (key, color, parent_index, left_child_index, right_child_index)
# NIL nodes are represented by -1 index

def create_tree():
    # Initialize empty tree with just a NIL root
    tree = []
    # Add NIL node (key=None, color=BLACK, parent=-1, left=-1, right=-1)
    tree.append((None, False, -1, -1, -1))
    return tree

def is_nil(tree, index):
    return index == -1 or index == 0

def get_root_index(tree):
    # Root is at index 1 if it exists, otherwise -1
    return 1 if len(tree) > 1 else -1

def left_rotate(tree, x_index):
    # Get node x and its right child y
    x_key, x_color, x_parent, x_left, x_right = tree[x_index]
    y_index = x_right

    if is_nil(tree, y_index):
        return  # Can't rotate if right child is NIL

    y_key, y_color, y_parent, y_left, y_right = tree[y_index]

    # Turn y's left subtree into x's right subtree
    tree[x_index] = (x_key, x_color, x_parent, x_left, y_left)

    if not is_nil(tree, y_left):
        # Update parent of y's left child
        y_left_key, y_left_color, _, y_left_left, y_left_right = tree[y_left]
        tree[y_left] = (y_left_key, y_left_color, x_index, y_left_left,
y_left_right)

    # Link y's parent to x's parent
    tree[y_index] = (y_key, y_color, x_parent, x_index, y_right)

    # Link x's parent to y
    if is_nil(tree, x_parent):
        # x was the root
        pass
    else:
        parent_key, parent_color, parent_parent, parent_left, parent_right =
tree[x_parent]
        if x_index == parent_left:
            tree[x_parent] = (parent_key, parent_color, parent_parent, y_index,
parent_right)
        else:
            tree[x_parent] = (parent_key, parent_color, parent_parent,
parent_left, y_index)

    # Put x on y's left
    tree[x_index] = (x_key, x_color, y_index, x_left, y_left)

def right_rotate(tree, y_index):
    # Get node y and its left child x
    y_key, y_color, y_parent, y_left, y_right = tree[y_index]
    x_index = y_left

    if is_nil(tree, x_index):
        return  # Can't rotate if left child is NIL

    x_key, x_color, x_parent, x_left, x_right = tree[x_index]

    # Turn x's right subtree into y's left subtree
    tree[y_index] = (y_key, y_color, y_parent, x_right, y_right)

    if not is_nil(tree, x_right):
        # Update parent of x's right child
        x_right_key, x_right_color, _, x_right_left, x_right_right =
tree[x_right]
        tree[x_right] = (x_right_key, x_right_color, y_index, x_right_left,
x_right_right)

    # Link x's parent to y's parent
    tree[x_index] = (x_key, x_color, y_parent, x_left, y_index)

    # Link y's parent to x
    if is_nil(tree, y_parent):
        # y was the root
        pass
    else:
        parent_key, parent_color, parent_parent, parent_left, parent_right =
tree[y_parent]
        if y_index == parent_left:
            tree[x_parent] = (parent_key, parent_color, parent_parent, x_index,
parent_right)
        else:
            tree[x_parent] = (parent_key, parent_color, parent_parent,
parent_left, x_index)

    # Put y on x's right
    tree[y_index] = (y_key, y_color, x_index, x_right, y_right)

def rb_insert_fixup(tree, z_index):
    while True:
        # Get z's parent
        _, _, z_parent, _, _ = tree[z_index]

        if is_nil(tree, z_parent):
            # z is the root
            break

        # Get z's parent's info
        _, parent_color, parent_parent, _, _ = tree[z_parent]

        if not parent_color:  # Parent is BLACK
            break

        # If we're here, parent is RED
        # Get grandparent info
        _, _, grandparent_parent, grandparent_left, grandparent_right =
tree[parent_parent]

        # Check if parent is left or right child of grandparent
        if z_parent == grandparent_left:
            y_index = grandparent_right  # y is z's uncle

            if not is_nil(tree, y_index) and tree[y_index][1]:  # Uncle is RED
                # Case 1: z's uncle y is red
                # Make parent and uncle BLACK
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                y_key, _, y_parent, y_left, y_right = tree[y_index]
                tree[y_index] = (y_key, False, y_parent, y_left, y_right)

                # Make grandparent RED
                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                # Move z to grandparent and continue
                z_index = parent_parent
            else:
                # Uncle is BLACK or NIL
                if z_index == parent_right:
                    # Case 2: z is a right child
                    z_index = z_parent
                    left_rotate(tree, z_index)
                    _, _, z_parent, _, _ = tree[z_index]

                # Case 3: z is a left child
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                right_rotate(tree, parent_parent)
                break
        else:
            # Mirror image of above
            y_index = grandparent_left  # y is z's uncle

            if not is_nil(tree, y_index) and tree[y_index][1]:  # Uncle is RED
                # Case 1: z's uncle y is red
                # Make parent and uncle BLACK
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                y_key, _, y_parent, y_left, y_right = tree[y_index]
                tree[y_index] = (y_key, False, y_parent, y_left, y_right)

                # Make grandparent RED
                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                # Move z to grandparent and continue
                z_index = parent_parent
            else:
                # Uncle is BLACK or NIL
                if z_index == parent_left:
                    # Case 2: z is a left child
                    z_index = z_parent
                    right_rotate(tree, z_index)
                    _, _, z_parent, _, _ = tree[z_index]

                # Case 3: z is a right child
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                left_rotate(tree, parent_parent)
                break

    # Make root black
    root_index = get_root_index(tree)
    if not is_nil(tree, root_index):
        root_key, _, root_parent, root_left, root_right = tree[root_index]
        tree[root_index] = (root_key, False, root_parent, root_left, root_right)

def rb_insert(tree, key):
    # Create a new node
    new_node_index = len(tree)
    # Initially colored RED, with NIL children
    tree.append((key, True, -1, 0, 0))

    # Find the correct position for the new node
    y_index = 0  # NIL
    x_index = get_root_index(tree)

    while not is_nil(tree, x_index):
        y_index = x_index
        x_key, _, _, x_left, x_right = tree[x_index]

        if key < x_key:
            x_index = x_left
        else:
            x_index = x_right

    # Set parent of the new node
    tree[new_node_index] = (key, True, y_index, 0, 0)

    # Insert the new node as a child of y
    if is_nil(tree, y_index):
        # Tree was empty, new node is the root
        pass
    else:
        y_key, y_color, y_parent, y_left, y_right = tree[y_index]

        if key < y_key:
            tree[y_index] = (y_key, y_color, y_parent, new_node_index, y_right)
        else:
            tree[y_index] = (y_key, y_color, y_parent, y_left, new_node_index)

    # Fix the red-black properties
    rb_insert_fixup(tree, new_node_index)

def rb_search(tree, key):
    x_index = get_root_index(tree)

    while not is_nil(tree, x_index):
        x_key, _, _, x_left, x_right = tree[x_index]

        if key == x_key:
            return x_index
        elif key < x_key:
            x_index = x_left
        else:
            x_index = x_right

    return -1  # Key not found

def inorder_traverse(tree, node_index, result):
    if is_nil(tree, node_index):
        return

    node_key, node_color, _, node_left, node_right = tree[node_index]

    inorder_traverse(tree, node_left, result)
    result.append((node_key, "RED" if node_color else "BLACK"))
    inorder_traverse(tree, node_right, result)

def print_tree(tree):
    result = []
    root_index = get_root_index(tree)
    inorder_traverse(tree, root_index, result)
    return result

# Example usage
def example():
    tree = create_tree()

    # Insert some values
    for key in [10, 20, 30, 15, 25, 5, 35]:
        rb_insert(tree, key)

    # Search for a key
    found_index = rb_search(tree, 15)
    if found_index != -1:
        print(f"Found key 15 at index {found_index}")
    else:
        print("Key 15 not found")

    # Print the tree in order
    print("Inorder traversal (with colors):")
    result = print_tree(tree)
    for key, color in result:
        print(f"{key} ({color})")

if __name__ == "__main__":
    example()
%<------%<------%<------


POV-Ray: first try


%<------%<------%<------
// Red-Black Tree implementation in POV-Ray using macros
// Colors: RED = 1, BLACK = 0

// Global arrays to store the tree
// Each node contains: key, color, parent_index, left_child_index,
right_child_index
#declare TreeSize = 100; // Maximum size of the tree
#declare TreeKeys = array[TreeSize];
#declare TreeColors = array[TreeSize];
#declare TreeParents = array[TreeSize];
#declare TreeLefts = array[TreeSize];
#declare TreeRights = array[TreeSize];
#declare TreeCount = 1; // Start at 1 because 0 is reserved for NIL

// Initialize the tree with a NIL node at index 0
#macro InitTree()
    #declare TreeKeys[0] = -1;    // NIL key (arbitrary value)
    #declare TreeColors[0] = 0;   // NIL is BLACK
    #declare TreeParents[0] = -1; // NIL parent
    #declare TreeLefts[0] = -1;   // NIL left
    #declare TreeRights[0] = -1;  // NIL right
    #declare TreeCount = 1;       // Reset count to 1
#end

// Check if node is NIL
#macro IsNil(index)
    #local result = (index = 0 | index = -1);
    result
#end

// Get the root index
#macro GetRootIndex()
    #local result = 1;
    #if(TreeCount <= 1)
        #local result = -1;
    #end
    result
#end

// Left Rotate operation
#macro LeftRotate(x_index)
    #local x_key = TreeKeys[x_index];
    #local x_color = TreeColors[x_index];
    #local x_parent = TreeParents[x_index];
    #local x_left = TreeLefts[x_index];
    #local x_right = TreeRights[x_index];
    #local y_index = x_right;

    #if(!IsNil(y_index))
        #local y_key = TreeKeys[y_index];
        #local y_color = TreeColors[y_index];
        #local y_left = TreeLefts[y_index];
        #local y_right = TreeRights[y_index];

        // Turn y's left subtree into x's right subtree
        #declare TreeRights[x_index] = y_left;

        #if(!IsNil(y_left))
            #declare TreeParents[y_left] = x_index;
        #end

        // Link y's parent to x's parent
        #declare TreeParents[y_index] = x_parent;

        // Link x's parent to y
        #if(IsNil(x_parent))
            // x was the root, do nothing
        #else
            #if(x_index = TreeLefts[x_parent])
                #declare TreeLefts[x_parent] = y_index;
            #else
                #declare TreeRights[x_parent] = y_index;
            #end
        #end

        // Put x on y's left
        #declare TreeLefts[y_index] = x_index;
        #declare TreeParents[x_index] = y_index;
    #end
#end

// Right Rotate operation
#macro RightRotate(y_index)
    #local y_key = TreeKeys[y_index];
    #local y_color = TreeColors[y_index];
    #local y_parent = TreeParents[y_index];
    #local y_left = TreeLefts[y_index];
    #local y_right = TreeRights[y_index];
    #local x_index = y_left;

    #if(!IsNil(x_index))
        #local x_key = TreeKeys[x_index];
        #local x_color = TreeColors[x_index];
        #local x_left = TreeLefts[x_index];
        #local x_right = TreeRights[x_index];

        // Turn x's right subtree into y's left subtree
        #declare TreeLefts[y_index] = x_right;

        #if(!IsNil(x_right))
            #declare TreeParents[x_right] = y_index;
        #end

        // Link x's parent to y's parent
        #declare TreeParents[x_index] = y_parent;

        // Link y's parent to x
        #if(IsNil(y_parent))
            // y was the root, do nothing
        #else
            #if(y_index = TreeLefts[y_parent])
                #declare TreeLefts[y_parent] = x_index;
            #else
                #declare TreeRights[y_parent] = x_index;
            #end
        #end

        // Put y on x's right
        #declare TreeRights[x_index] = y_index;
        #declare TreeParents[y_index] = x_index;
    #end
#end

// Fix red-black properties after insertion
#macro RBInsertFixup(z_index)
    #local continue_loop = true;

    #while(continue_loop)
        #local z_parent = TreeParents[z_index];

        #if(IsNil(z_parent))
            // z is the root
            #local continue_loop = false;
        #else
            #local parent_color = TreeColors[z_parent];

            #if(parent_color = 0) // Parent is BLACK
                #local continue_loop = false;
            #else
                // Parent is RED
                #local parent_parent = TreeParents[z_parent];

                #if(z_parent = TreeLefts[parent_parent]) // Parent is left child
                    #local y_index = TreeRights[parent_parent]; // Uncle

                    #if(!IsNil(y_index) & TreeColors[y_index] = 1) // Uncle is
RED
                        // Case 1: Uncle is red
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[y_index] = 0;  // Uncle -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        #local z_index = parent_parent;
                    #else
                        // Uncle is BLACK or NIL
                        #if(z_index = TreeRights[z_parent]) // z is right child
                            // Case 2: z is right child
                            #local z_index = z_parent;
                            LeftRotate(z_index)
                            #local z_parent = TreeParents[z_index];
                        #end

                        // Case 3: z is left child
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        RightRotate(parent_parent)
                        #local continue_loop = false;
                    #end
                #else // Parent is right child
                    #local y_index = TreeLefts[parent_parent]; // Uncle

                    #if(!IsNil(y_index) & TreeColors[y_index] = 1) // Uncle is
RED
                        // Case 1: Uncle is red
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[y_index] = 0;  // Uncle -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        #local z_index = parent_parent;
                    #else
                        // Uncle is BLACK or NIL
                        #if(z_index = TreeLefts[z_parent]) // z is left child
                            // Case 2: z is left child
                            #local z_index = z_parent;
                            RightRotate(z_index)
                            #local z_parent = TreeParents[z_index];
                        #end

                        // Case 3: z is right child
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        LeftRotate(parent_parent)
                        #local continue_loop = false;
                    #end
                #end
            #end
        #end
    #end

    // Make root black
    #local root_index = GetRootIndex();
    #if(!IsNil(root_index))
        #declare TreeColors[root_index] = 0;
    #end
#end

// Insert a new key into the tree
#macro RBInsert(key)
    // Create a new node
    #local new_node_index = TreeCount;
    #declare TreeCount = TreeCount + 1;

    // Initialize node as RED with NIL children
    #declare TreeKeys[new_node_index] = key;
    #declare TreeColors[new_node_index] = 1; // RED
    #declare TreeParents[new_node_index] = -1;
    #declare TreeLefts[new_node_index] = 0; // NIL
    #declare TreeRights[new_node_index] = 0; // NIL

    // Find the correct position for the new node
    #local y_index = 0; // NIL
    #local x_index = GetRootIndex();

    #while(!IsNil(x_index))
        #local y_index = x_index;
        #local x_key = TreeKeys[x_index];

        #if(key < x_key)
            #local x_index = TreeLefts[x_index];
        #else
            #local x_index = TreeRights[x_index];
        #end
    #end

    // Set parent of the new node
    #declare TreeParents[new_node_index] = y_index;

    // Insert the new node as a child of y
    #if(IsNil(y_index))
        // Tree was empty, new node is the root
        // Do nothing, already set up correctly
    #else
        #if(key < TreeKeys[y_index])
            #declare TreeLefts[y_index] = new_node_index;
        #else
            #declare TreeRights[y_index] = new_node_index;
        #end
    #end

    // Fix the red-black properties
    RBInsertFixup(new_node_index)
#end

// Search for a key in the tree
#macro RBSearch(key)
    #local found_index = -1;
    #local x_index = GetRootIndex();

    #while(!IsNil(x_index) & found_index = -1)
        #local x_key = TreeKeys[x_index];

        #if(key = x_key)
            #local found_index = x_index;
        #elseif(key < x_key)
            #local x_index = TreeLefts[x_index];
        #else
            #local x_index = TreeRights[x_index];
        #end
    #end

    found_index
#end

// Visualization macros

// Draw a single node
#macro DrawNode(index, x, y, z, level)
    #local node_radius = 0.2;
    #local color_value = rgb <1,0,0>;  // RED
    #if(TreeColors[index] = 0)
        #local color_value = rgb <0,0,0>;  // BLACK
    #end

    sphere {
        <x, y, z>, node_radius
        pigment { color color_value }
        finish {
            ambient 0.2
            diffuse 0.8
            specular 0.5
        }
    }

    // Add text for the key value
    #local key_str = str(TreeKeys[index], 0, 0);
    text {
        ttf "arial.ttf", key_str, 0.1, <0, 0, 0>
        pigment { color rgb <1, 1, 1> }  // White text
        scale 0.15
        translate <x-0.1, y-0.05, z+node_radius+0.01>
    }

    // Draw left child
    #local left_index = TreeLefts[index];
    #if(!IsNil(left_index))
        #local x_offset = 2.0 / pow(2, level);
        #local new_x = x - x_offset;
        #local new_y = y - 1;
        #local new_z = z;

        cylinder {
            <x, y, z>, <new_x, new_y, new_z>, 0.03
            pigment { color rgb <0.5, 0.5, 0.5> }
        }

        DrawNode(left_index, new_x, new_y, new_z, level + 1)
    #end

    // Draw right child
    #local right_index = TreeRights[index];
    #if(!IsNil(right_index))
        #local x_offset = 2.0 / pow(2, level);
        #local new_x = x + x_offset;
        #local new_y = y - 1;
        #local new_z = z;

        cylinder {
            <x, y, z>, <new_x, new_y, new_z>, 0.03
            pigment { color rgb <0.5, 0.5, 0.5> }
        }

        DrawNode(right_index, new_x, new_y, new_z, level + 1)
    #end
#end

// Visualize the entire tree
#macro VisualizeTree()
    #local root_index = GetRootIndex();

    #if(!IsNil(root_index))
        DrawNode(root_index, 0, 0, 0, 1)
    #end
#end

// Print information about a node (for debugging)
#macro PrintNode(index)
    #debug concat(
        "Node ", str(index, 0, 0), ": ",
        "Key=", str(TreeKeys[index], 0, 0), ", ",
        "Color=", str(TreeColors[index], 0, 0), ", ",
        "Parent=", str(TreeParents[index], 0, 0), ", ",
        "Left=", str(TreeLefts[index], 0, 0), ", ",
        "Right=", str(TreeRights[index], 0, 0), "\n"
    )
#end

// Example usage in a POV-Ray scene
#macro ExampleTree()
    InitTree()

    // Insert some values
    RBInsert(10)
    RBInsert(20)
    RBInsert(30)
    RBInsert(15)
    RBInsert(25)
    RBInsert(5)
    RBInsert(35)

    // Search for a key
    #local found_index = RBSearch(15);
    #if(found_index != -1)
        #debug concat("Found key 15 at index ", str(found_index, 0, 0), "\n")
    #else
        #debug "Key 15 not found\n"
    #end

    // Print all nodes
    #debug "Tree contents:\n"
    #for(i, 1, TreeCount-1)
        PrintNode(i)
    #end

    VisualizeTree()
#end

// Scene setup
camera {
    location <0, 0, -10>
    look_at <0, 0, 0>
    angle 30
}

light_source {
    <5, 5, -10>
    color rgb <1, 1, 1>
}

light_source {
    <-5, 5, -10>
    color rgb <0.5, 0.5, 0.5>
}

background { color rgb <1, 1, 1> }

// Run the example
ExampleTree()

%<------%<------%<------

Post a reply to this message

"ingo" <nomail@nomail> wrote:
> Same thing with Claude:
>
 Just saw that Claude 3.7 is available again and gave it a go with the Claude
3.5 and some touch ups by me. It works, I think after a few tests. Deleting
nodes is not implemented. Also it may need some restructuring by putting things
in arrays that act as record/struct/object:

---%<------%<------%<---
// Red-Black Tree implementation in POV-Ray using macros
// Colors: RED = 1, BLACK = 0

// Global arrays to store the tree
// Each node contains: key, color, parent_index, left_child_index,
right_child_index
#declare TreeSize = 100; // Maximum size of the tree
#declare TreeKeys = array[TreeSize];
#declare TreeColors = array[TreeSize];
#declare TreeParents = array[TreeSize];
#declare TreeLefts = array[TreeSize];
#declare TreeRights = array[TreeSize];
#declare TreeCount = 1; // Start at 1 because 0 is reserved for NIL
#declare RootIndex = 0; // Track the root index explicitly

// Initialize the tree with a NIL node at index 0
#macro InitTree()
    #declare TreeKeys[0] = -1;    // NIL key (arbitrary value)
    #declare TreeColors[0] = 0;   // NIL is BLACK
    #declare TreeParents[0] = 0;  // NIL parent is itself
    #declare TreeLefts[0] = 0;    // NIL left is itself
    #declare TreeRights[0] = 0;   // NIL right is itself
    #declare TreeCount = 1;       // Reset count to 1
    #declare RootIndex = 0;       // Empty tree
    #debug "Tree initialized\n"
#end

// Check if node is NIL
#macro IsNil(index)
    #local result = (index = 0);
    result
#end

// Get the root index
#macro GetRootIndex()
    #debug concat("GetRootIndex: ", str(RootIndex, 0, 0), "\n")
    RootIndex
#end

// Left Rotate operation
#macro LeftRotate(x_index)
    #debug concat("LeftRotate: ", str(x_index, 0, 0), "\n")
    #local y_index = TreeRights[x_index];

    #if(!IsNil(y_index))
        // Turn Y's left subtree into X's right subtree
        #declare TreeRights[x_index] = TreeLefts[y_index];

        #if(!IsNil(TreeLefts[y_index]))
            #declare TreeParents[TreeLefts[y_index]] = x_index;
        #end

        // Link Y's parent to X's parent
        #declare TreeParents[y_index] = TreeParents[x_index];

        // Link X's parent to Y
        #if(IsNil(TreeParents[x_index]))
            // X was the root, make Y the new root
            #declare RootIndex = y_index;
        #else
            #if(x_index = TreeLefts[TreeParents[x_index]])
                #declare TreeLefts[TreeParents[x_index]] = y_index;
            #else
                #declare TreeRights[TreeParents[x_index]] = y_index;
            #end
        #end

        // Put X on Y's left
        #declare TreeLefts[y_index] = x_index;
        #declare TreeParents[x_index] = y_index;
    #end
#end


// Right Rotate operation
#macro RightRotate(y_index)
    #debug concat("RightRotate: ", str(y_index, 0, 0), "\n")
    #local x_index = TreeLefts[y_index];

    #if(!IsNil(x_index))
        // Turn X's right subtree into Y's left subtree
        #declare TreeLefts[y_index] = TreeRights[x_index];

        #if(!IsNil(TreeRights[x_index]))
            #declare TreeParents[TreeRights[x_index]] = y_index;
        #end

        // Link X's parent to Y's parent
        #declare TreeParents[x_index] = TreeParents[y_index];

        // Link Y's parent to X
        #if(IsNil(TreeParents[y_index]))
            // Y was the root, make X the new root
            #declare RootIndex = x_index;
        #else
            #if(y_index = TreeLefts[TreeParents[y_index]])
                #declare TreeLefts[TreeParents[y_index]] = x_index;
            #else
                #declare TreeRights[TreeParents[y_index]] = x_index;
            #end
        #end

        // Put Y on X's right
        #declare TreeRights[x_index] = y_index;
        #declare TreeParents[y_index] = x_index;
    #end
#end


// Fix red-black properties after insertion
#macro RBInsertFixup(z_index)
    #debug concat("RBInsertFixup: ", str(z_index, 0, 0), "\n")

    // Continue fixing while Z's parent is RED
    #while(!IsNil(TreeParents[z_index]) & TreeColors[TreeParents[z_index]] = 1)
        #if(TreeParents[z_index] = TreeLefts[TreeParents[TreeParents[z_index]]])
            // Parent is left child of grandparent
            #local y_index = TreeRights[TreeParents[TreeParents[z_index]]]; //
Uncle

            #if(TreeColors[y_index] = 1) // Uncle is RED
                // Case 1: Recolor
                #declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
                #declare TreeColors[y_index] = 0; // Uncle to BLACK
                #declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
                #local z_index = TreeParents[TreeParents[z_index]]; // Move up
to grandparent
            #else
                // Uncle is BLACK
                #if(z_index = TreeRights[TreeParents[z_index]]) // Z is right
child
                    // Case 2: Z is right child - Convert to Case 3
                    #local z_index = TreeParents[z_index];
                    LeftRotate(z_index)
                #end

                // Case 3: Z is left child
                #declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
                #declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
                RightRotate(TreeParents[TreeParents[z_index]])
            #end
        #else
            // Parent is right child of grandparent
            #local y_index = TreeLefts[TreeParents[TreeParents[z_index]]]; //
Uncle

            #if(TreeColors[y_index] = 1) // Uncle is RED
                // Case 1: Recolor
                #declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
                #declare TreeColors[y_index] = 0; // Uncle to BLACK
                #declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
                #local z_index = TreeParents[TreeParents[z_index]]; // Move up
to grandparent
            #else
                // Uncle is BLACK
                #if(z_index = TreeLefts[TreeParents[z_index]]) // Z is left
child
                    // Case 2: Z is left child - Convert to Case 3
                    #local z_index = TreeParents[z_index];
                    RightRotate(z_index)
                #end

                // Case 3: Z is right child
                #declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
                #declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
                LeftRotate(TreeParents[TreeParents[z_index]])
            #end
        #end
    #end

    // Make sure root is BLACK
    #declare TreeColors[RootIndex] = 0;
#end


// Insert a new key into the tree
#macro RBInsert(key)
    #debug concat("RBInsert: ", str(key, 0, 0), "\n")

    // Create a new node
    #local z_index = TreeCount;
    #declare TreeCount = TreeCount + 1;

    // Initialize node with RED color
    #declare TreeKeys[z_index] = key;
    #declare TreeColors[z_index] = 1; // RED
    #declare TreeLefts[z_index] = 0;  // NIL
    #declare TreeRights[z_index] = 0; // NIL

    // Find insertion position
    #local y_index = 0; // NIL
    #local x_index = RootIndex;

    #while(!IsNil(x_index))
        #local y_index = x_index;

        #if(key < TreeKeys[x_index])
            #local x_index = TreeLefts[x_index];
        #else
            #local x_index = TreeRights[x_index];
        #end
    #end

    // Insert the node
    #declare TreeParents[z_index] = y_index;

    #if(IsNil(y_index))
        // Tree was empty
        #declare RootIndex = z_index;
    #else
        #if(key < TreeKeys[y_index])
            #declare TreeLefts[y_index] = z_index;
        #else
            #declare TreeRights[y_index] = z_index;
        #end
    #end

    // Fix the red-black properties
    RBInsertFixup(z_index)

    #debug concat("Insert complete for key: ", str(key, 0, 0), "\n")
#end

// Search for a key in the tree
#macro RBSearch(key)
    #debug concat("RBSearch: ", str(key, 0, 0), "\n")
    #local found_index = -1;
    #local x_index = RootIndex;

    #while(!IsNil(x_index) & found_index = -1)
        #if(key = TreeKeys[x_index])
            #local found_index = x_index;
        #elseif(key < TreeKeys[x_index])
            #local x_index = TreeLefts[x_index];
        #else
            #local x_index = TreeRights[x_index];
        #end
    #end

    #debug concat("Search result for key ", str(key, 0, 0), ": ",
str(found_index, 0, 0), "\n")
    found_index
#end

// Print the tree structure for debugging
#macro PrintTree()
    #debug "Tree structure:\n"
    #debug concat("Root index: ", str(RootIndex, 0, 0), "\n")
    #debug concat("Tree count: ", str(TreeCount, 0, 0), "\n")

    #local i = 0;
    #while(i < TreeCount)
        #debug concat("Node ", str(i, 0, 0), ": ")
        #debug concat("Key=", str(TreeKeys[i], 0, 0), ", ")
        #debug concat("Color=", str(TreeColors[i], 0, 0), ", ")
        #debug concat("Parent=", str(TreeParents[i], 0, 0), ", ")
        #debug concat("Left=", str(TreeLefts[i], 0, 0), ", ")
        #debug concat("Right=", str(TreeRights[i], 0, 0), "\n")
        #local i = i + 1;
    #end
#end


InitTree()

// Insert some values
#debug "1a\n"
RBInsert(10)
#debug "1b\n"
RBInsert(20)
#debug "1c\n"
RBInsert(30)
#debug "1d\n"
RBInsert(15)
#debug "1e\n"
RBInsert(25)
#debug "1f\n"
RBInsert(5)
#debug "1g\n"
RBInsert(35)

PrintTree()
---%<------%<------%<---


ingo

Post a reply to this message

hi,

"ingo" <nomail@nomail> wrote:
> "ingo" <nomail@nomail> wrote:
> > Same thing with Claude:
> >
>  ... Deleting nodes is not implemented. ...

</grin>


regards, jr.

Post a reply to this message