Probable “user error” with input parameters, C++; pointer inputs, “binary” conversion

I am trying to write a couple of template functions that convert back and forth between a value of any data type (within reason) bytewise into a character string.
The idea is to (eventually) store the values in a .bin file, and also to be able to recover the values from said .bin file.
However, I need to get the conversion functions correct, first.
Originally, I wrote a toy function that did both that looked line this:

template<typename T>
void buildabin(T x)
{
    char* X;
    T x_;
    X = (char*)&x;
    memcpy(&x_, X, sizeof(T));
    cout<<x_<<endl;
}

This seemed to work fine.
However, when I tried to separate out the two capabilities, using:

template<typename T>
void buildabin(char*& X, T x)
{
    X = (char*)&x;
}

And:

template<typename T>
void buildaT(char* X, T& x)
{
    memcpy(&x, X, sizeof(T));
}

It seems as if it is doing the conversion to the binary string correctly, however, upon input to “buildaT”, it barfs – after placing some couts for X in various places, for some strange reason, it is not getting even the address of X correctly.
And of course, “little” x just returns garbage.

I have tried every scheme I can to get this to work. It seems it’s a “user error” on my part with respect to input in the “buildaT” function, but I am stuck as to where the error lies.

Here is main, if that helps:

int main()
{
    //char* G = new char(sizeof(double)); //(tried this also)

    char* G = NULL;

    double g;

    cin>>g;

    buildabin<double>(G, g);

    double g_;

    buildaT<double>(G, g_);

    cout<<g_<<endl;


    return(0);
}

java – How can I optimize this Binary Search Tree?

I’ve added some methods to a basic BST implementation for integers – if anyone can point out some ways that this could be written in a more efficient or clean manner, please let me know.

public class BST {
    
    /*
     *  1) Node inner class
     */
    
    private class Node {
        
        int data;
        Node leftChild, rightChild;
        
        public Node(int num, Node left, Node right) {
            this.data = num;
            this.leftChild = left;
            this.rightChild = right;
        }

    }
    
    
    // 2) Variables
    
    private Node root = null;   // every binary search tree object will be assigned a root node = null
    private int nodeCount = 0;
    
    // 3) Methods: size
    public int size() {
        return nodeCount;
    }
    
    // 4) Methods: isEmpty
    public boolean isEmpty() {
        return (root == null);   // if the root of the BST is null (we haven't added any nodes) then the BST is empty
    }
    
    // 5) Methods: contains (recursive), SEARCH
    public boolean treeContains(int info) {
        return treeContains(root, info);
    }
    
    public boolean treeContains(Node node, int info) {
        
        if (node == null) return false;   // corner case: if tree is null, but also BASE CASE
        
        // SEARCHING, but looking for a number so we can use O log(n) time
        if (info > node.data) { // go to the right
            return treeContains(node.rightChild, info);
            }
        else if (info < node.data) {
            return treeContains(node.leftChild, info);
        }
        else {  // either node has bigger or smaller data or this case: it is equal
            return true;
        }
    }
    
    // 6) Methods: add
    public boolean add(int newData) {
        if (treeContains(newData)) return false;
        
        else {
            root = add(root, newData);  // NOTE: this works but why can't it just be add(root,newdata) without the "root = " ?
            nodeCount++;
            return true;    
        }
    }
    
    public Node add(Node node, int newData) {
        
        if (node == null) {
            node = new Node(newData, null, null);               // NOTE: how does this add a node? it doesn't place it anywhere? it just exists somewhere? i mean i understand that by then we're pointing to a space that is null but still
        }
        
        else if (newData > node.data) {
            node.rightChild = add(node.rightChild, newData);
            }
        else {                                                  // else if newData is less or equal to node data
            node.leftChild = add(node.leftChild, newData);
            }
        return node;
    }
    
    // 7) Methods: remove
    // look up node to be removed, set it to null, recursive
    
    public boolean remove(int newData) {
        if (!treeContains(newData)) return false;  // will null BST's fall under this ???
        
        else {
            root = remove(root,newData);        // NOTE: why do we need to have root = remove(root, newData) ??? instead of just remove..
            nodeCount--;
            return true;
        }
    }
    
    public Node remove(Node node, int newData) {
        
        if (node.data == newData) {         // if we find the node we want to delete 
            
            // 3 SCENARIOS - the node can be a leaf, can have 1 or 2 children
            
            // leaf node
            if (node.leftChild==null && node.rightChild== null) {
                node = null;
            }
            
            // node has left child only
            else if (node.leftChild !=null && node.rightChild == null) {
                node.data = node.leftChild.data;   // left child is now node
                node.leftChild = null;
            }
            
            // node has right child only
            else if (node.leftChild==null && node.rightChild!=null) {
                Node temp = node.rightChild;        // trying another way of switching nodes & deleting
                node.rightChild = null;
                node.data = temp.data; 
            }
            
            // node has both children
            else {
                Node temp = findMin(node.rightChild);       
                node.data = temp.data;                          // switch data
                node.rightChild = remove(node.rightChild, temp.data);   // remove the findMin node, originally node.RC = remove...
            }
        }
        
        else if (newData < node.data) {
            node.leftChild = remove (node.leftChild, newData);
        }
        
        else {   // if newData > node.data
            node.rightChild = remove(node.rightChild, newData);
        }
        
        return node;
    }
    
      // Helper method to find the leftmost node (which has the smallest value)
      private Node findMin(Node node) {
        while (node.leftChild != null) 
            node = node.leftChild;
        return node;
      }

    
    
    // 8) Methods: In order tree traversal
      public void traverseInOrder(Node node) {
          if (node == null) return;
          
          traverseInOrder(node.leftChild);
          System.out.print(node.data + " ");
          traverseInOrder(node.rightChild);
      }
    

    // 9) Methods: Pre order tree traversal
      public void traversePreOrder(Node node) {
          if (node == null) return;
          
          System.out.print(node.data + " ");
          traversePreOrder(node.leftChild);
          traversePreOrder(node.rightChild);
      }
    
    
    // 10) Methods: Post order tree traversal
      public void traversePostOrder(Node node) {
          if (node == null) return;
          
          traversePostOrder(node.leftChild);
          traversePostOrder(node.rightChild);
          System.out.print(node.data + " ");
      }
    

    // RUN METHODS
      
    public static void main(String() args) {
        
        BST tree1 = new BST();
        
        tree1.add(10);
        tree1.add(7);
        tree1.add(5);
        tree1.add(8);
        tree1.add(20);
        tree1.add(15);
        tree1.add(25);
        
        tree1.traverseInOrder(tree1.root);
        
        System.out.println( "nSize of tree is: " + tree1.size() );
        System.out.println( "Root of tree is: " + tree1.root.data );
        System.out.println( "Min num of tree is: " + tree1.findMin(tree1.root).data );
        System.out.println( "Does the tree contain the #5 ? " + tree1.treeContains(5) );
        
        tree1.remove(8);
        tree1.remove(20);
        
        tree1.traverseInOrder(tree1.root);
        System.out.println( "nSize of tree is: " + tree1.size() );
    }
    

}

Thank you!!

godot – Traversing an acyclic binary tree to construct paths from a given starting node, but the paths come out wrong

The tree is an acyclic binary tree. It’s composed of node objects that have a list of connections to link objects (at most 3), and link objects that have a list of connections to node objects (always 2). I am trying to construct a list of possible paths to other nodes that can be reached given a fuel budget and a fuel cost on each link. What it is supposed to do is go through each non-backtracking connection of a node, and spawn a new route and thread to investigate that, leaving the current one to end at that node and thus create a list of routes to every node in the reachable area. When executed, the list of end destinations are valid but many of the paths that are constructed to get to them are wrong, going down other branches in the tree that are extraneous or entirely outside of the reachable area bounded by the fuel budget as well as jumping between nodes that aren’t directly connected. There seems to be some pattern in the errors, when going down from the root of some branches of the tree the path goes down every offshoot in order first instead of going in a straight line, and when going up the tree the path tends to go further out and make triangle shapes, often landing somewhere other than the listed destination. I have already checked the link and node connections themselves to see if they are assigned properly, and they are. What am I getting wrong?

Route class definition

var origin:Node
var destination:Node
var totaldV:float
var totalt:float
var dVBudget:float
var tBudget:float
var tdVRatio:float
var links:Array
var nodes:Array

func duplicate_values(originator:Route):
    origin = originator.origin
    destination = originator.destination
    totaldV = originator.totaldV
    totalt = originator.totalt
    dVBudget = originator.dVBudget
    tBudget = originator.tBudget
    tdVRatio = originator.tdVRatio
    nodes = originator.nodes
    links = originator.links


func _init(originator_route):
    if originator_route != null:
        duplicate_values(originator_route)

Tree traversal algorithm

var routes:Array
onready var root = get_node("..")

func traverse(current_node:Node, previous_route:Route):
    if previous_route == null:                             # Starts off the recursion by providing an initial node
        previous_route = Route.new(null)
        previous_route.origin = current_node
        previous_route.nodes.append(previous_route.origin)
        previous_route.dVBudget = 2000
        previous_route.totaldV = 0
    for link in current_node.connections:
        if (previous_route.totaldV + link.dV < previous_route.dVBudget && 
        !IsBacktracking(previous_route, LinkDestination(link, current_node))):   # If there is enough fuel and the link isn't backtracking, go through it.
            var working_route:Route = Route.new(previous_route)    # Copy the previous route to make the new route
            routes.append(working_route)
            working_route.destination = LinkDestination(link, current_node)
            working_route.totaldV += link.dV
            working_route.totalt += link.t
            working_route.links.append(link)
            working_route.nodes.append(working_route.destination)
            traverse(working_route.destination, working_route)
    DisplayRoutes()
    root.get_parent().pathSelectionFlag = true   # UI control boolean


func IsBacktracking(route:Route, destinationNode:Node) -> bool:
    for nodeI in route.nodes:
        if (destinationNode == nodeI):
            return true
    return false


func LinkDestination(link:Node, originNode:Node) -> Node:    # Finds the node on the other side of a link
    for nodeI in link.connections:
        if (nodeI != originNode):
            return nodeI
    return originNode

algorithms – Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here.
As highlighted by the lack of a 7*2^64/8 term it is not necessarily full, but it is always complete. The nodes are stored in numerical order (in-order) in a list of which I know the size, and I have the index (call it the in-order index) of a node in that sorted list.

I’m trying to get the index (call it level-order index) of that same node if the array was stored according to the breadth-first traversal order (level-order) of the tree instead. In the example, the tree root would have level-order index 0 and in-order index 3.

What I’ve found already is that the level-order index consists of two parts:

  • A base part which is the amount of nodes contained in the full tree above the level in which the node resides.
  • An offset part which is the amount of nodes to the left of this node in the level in which it is contained.

Summed together, they produce the level-order index.

I’ve been able to solve this for the full tree case, as then the level at which a node is contained is the number of times its in-order index + 1 is divisible by 2. However, for the general case in which the tree is not necessarily full, how would that base part be calculated from the in-order index?

Of course, it is possible by iterating the tree programmatically, but since the exact layout and contents of the entire tree are known simply from the amount of nodes that it contains, I was wondering whether a mathematical relation between these two indices holds. Does anyone have an idea?

What is an algorithm to do this binary image segmantation task?

What I need to do is go from a binary image like this:

to a segmented structure like this:

because I have a program that operates on those separated line contours after.
As you see, those contours are not perfect, they might be slightly bent but where they meet it’s always pretty much orthogonal, there are no 45 degree lines. The lines are between 3 and 20 pixels wide. The whole image is sometimes slightly rotated (less that 10 degrees) but if you find a solution that only works without rotation I could look into de-rotating stuff before. The inserted gap may be of any width (preferably 1px or 2px) as long as it entirely separates one line from another.

I thought one could do something like on page 15 of this paper (the description of what they do is on page 13). Essentially this would come down to finding one marker per line segment and then watershed, but I have no idea how to find that marker.

Just to be clear:

On any point of line intersection, this

is good, as well as this:

If easier to achieve,

this:

is acceptable too, although not preferred.

What’s not ok is this:

This is not only true for three-line t-sections but also two-line corner connections (= it doesn’t matter which of the two lines meeting gets shortened).

Sorry for the huge pictures, didn’t know how to prevent them from turning out this big.

I am working with python and cv2 so it would be a plus if you use that. On the other hand, even a link to a re-implementable algorithm or an idea how to find markers would be fine. Also, I’m looking for a fast and easy algorithm that works on binary (0 or 255) images, not any crazy machine-learning stuff (if avoidable). I have really time but lack the right idea. Thanks in advance.

automata – How to describe the Language which accepts all binary strings divisible by 4 (in binary, divisible by 100)?

I’m trying to write an inductive proof to show that my DFA accepts all binary strings which are divisible by 4 (divisible by $100_2$). Part of this proof is describing the language which machine $M$ accepts.

So far I’ve written the language as:

${0, 1}^*{00}$

Because any binary string when interpreted as a binary number is divisible by 4 iff its last two digits are $00$.

However I’d like to exclude the empty string from this.

Should I write it as $({0, 1}^* – {varepsilon}){00}$? To get rid of the empty string from the set of all binary strings.

plotting – How to plot clusters with binary matrix and coordinates?

I have to lists, x and y that contain the coordinates of $N$ nodes. The nodes are divided into non overlapping clusters. The clustering information is provided in a binary matrix $M$ of size $Ctimes N$, where $C$ is the number of clusters. If $M_{c,n}=1$, then node $n$ belongs to cluster $c$.

How can I show the clusters graphically?

recursion – How to perform AND on binary “recursive repeating sequences”?

Suppose, we have a two binary sequences, encoded as “recursive repeating sequences” (I don’t know exactly how to name them). Each sequence can contain other sequences and has number related to how many times this sequence is repeated, or can contain a bit either 0 or 1. Following image describes it visually:

enter image description here

On this image repetition is denoted by lower index number nearby ending bracket. The bits need to be expanded are denoted by regular size font.

Each sequence can produce binary sequence (sequence of bits), when we expand it.

The questions are:

  1. Can we create a algorithm, that performs AND on two recursive repeating sequences, without expanding both of them? (The algorithm should produce third recursive repeating sequence, such when we expand it, it is AND on both expanded input sequences).
  2. If the answer for first question is true, how such algorithm will look (for example in pseudo code) ?

Note: In practice, the numbers responsible for repetition may be very large, so expansion of whole sequence is not practical in terms of computation – but if algorithm will need to do it partially, it may be accepted.

c++ – C++20 : N-dim matrix version 2, broadcasting binary operators

I’ve improved my previous N-dim Matrix class (C++20 : N-dimensional minimal Matrix class), adding some key feature from NumPy: Matrix broadcasting!

Broadcasting is a key required feature for taking inputs with possibly different shape in matrix binary operators.
https://github.com/onnx/onnx/blob/master/docs/Broadcasting.md

Only binary addition has been implemented, other binary operators (sub, mul, div, …) are just similar boilerplates.

Since my code is getting bloated, I’ll post here the GitHub link of notable changes from the previous version:

https://github.com/frozenca/Ndim-Matrix/blob/main/ObjectBase.h

https://github.com/frozenca/Ndim-Matrix/blob/main/MatrixBase.h#L309

https://github.com/frozenca/Ndim-Matrix/blob/main/Matrix.h#L267

https://github.com/frozenca/Ndim-Matrix/blob/main/MatrixUtils.h#L56

https://github.com/frozenca/Ndim-Matrix/blob/main/MatrixUtils.h#L199

Simple broadcasting test:

#include "Matrix.h"
#include <iostream>
#include <iterator>
#include <numeric>

int main() {

    auto m6 = frozenca::ones<double, 3>({2, 3, 3});
    // {{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}, {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}}
    std::cout << m6 << 'n';

    auto m7 = frozenca::zeros<int, 2>({1, 3});
    std::iota(std::begin(m7), std::end(m7), 1);
    // {{1, 2, 3}}
    std::cout << m7 << 'n';

    auto m8 = m6 + m7; // type: Matrix<double, 3> with size (2, 3, 3)
    // {{{2, 3, 4}, {2, 3, 4}, {2, 3, 4}}, {{2, 3, 4}, {2, 3, 4}, {2, 3, 4}}}
    std::cout << m8 << 'n';
}

Feel free to comment anything!

Yet to come: Linear algebra stuffs (.dot(), .matmul(), SVD, inverse/pseudoinverse, etc)

cpu – How do you “time” the measure of binary streams?

This is just something I’ve been wondering just out of curiosity. I apologize if this doesn’t fall under the category of this forum, and if so feel free to divert me 🙂

Whenever a computer does anything, it always handles a sequence of bits. My question is: how does it actually measure what bit goes in what place? I’m curious of the electric current that gets sent into the transistors, and how these are actually placed correctly in the binary stream. I understand the concept of the transistors and how a threshold voltage determines whether or not a bit is 0 or 1, but how are these bits actually placed in sequence?

Say if we have a binary sequence of 00010010001. How does whatever component handling this stream know how “long” it has to wait with no current before it places a 0-bit, and then moves on? According to my understanding, for the first three 0-bits, there will be no current going into the transistors. But does it have to “wait” for a set amount of time before it determines that a single bit is 0? I’m generally just confused as to how a computer knows the difference between a single 0-bit, and (for example) 10 different 0-bits. When does a computer know to set another bit?. Appreciate any feedback! 🙂