Example git persistent data structure

To continue on the post of Persistent data structure and git, I've created this repo: https://github.com/mhewedy-playground/how-get-works

Looking into the objects database, here's the database objects exposed:

$ git log
commit d5ef93b09fe8d80fa903894a1bac93d3a67d55d3 (HEAD -> master)
Author: Muhammad Hewedy <mhewedy@gmail.com>
Date:   Mon Mar 25 00:09:37 2019 +0300

commit 16dc45d02209a4bfcb26b066f18bf290507cf87f
Author: Muhammad Hewedy <mhewedy@gmail.com>
Date:   Mon Mar 25 00:05:20 2019 +0300
---------------------------------------------------------------------
# first commit tree
$ git cat-file -p 16dc
tree 029ec860ecb064cf689695c176a5baafc910916a
author Muhammad Hewedy <mhewedy@gmail.com> 1553461520 +0300
committer Muhammad Hewedy <mhewedy@gmail.com> 1553461520 +0300

$ git cat-file -p 029e
040000 tree e9199b34206372b3d2b1e2c06b3ccfeaef6d8804 a

$ git cat-file -p e919
040000 tree b1d74266c8b55b9cd7796c056888b6edcc1d1a98 b

$ git cat-file -p b1d7
040000 tree 68aba62e560c0ebc3396e8ae9335232cd93a3f60 c

$ git cat-file -p 68ab
100644 blob 3b18e512dba79e4c8300dd08aeb37f8e728b8dad hello.txt
---------------------------------------------------------------------
# second (HEAD/master) commit tree
$ git cat-file -p d5ef
tree 9d0986abb4d98c7b1a26e6a4efe2156981ebd583
parent 16dc45d02209a4bfcb26b066f18bf290507cf87f
author Muhammad Hewedy <mhewedy@gmail.com> 1553461777 +0300
committer Muhammad Hewedy <mhewedy@gmail.com> 1553461777 +0300

$ git cat-file -p 9d09
040000 tree 48bc9a2ae3efb7aef6095e4db249a5775b71d155 a

$ git cat-file -p 48bc
040000 tree 5899cb357c13a7e7fa8aacc9b73ad741877d5390 b

$ git cat-file -p 5899
040000 tree 68aba62e560c0ebc3396e8ae9335232cd93a3f60 c
100644 blob 345e6aef713208c8d50cdea23b85e6ad831f0449 test.txt

$ git cat-file -p 68ab
100644 blob 3b18e512dba79e4c8300dd08aeb37f8e728b8dad hello.txt


Which is represented by the following diagram

Persistent data structure and git

From Wikipedia:

a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not update the structure in-place, but instead always yield a new updated structure.

Git own objects database is a persistence data structure.

Consider git repo with the following log:

commit 5a19382be2d700129a0c0ca81340a8858075501b (HEAD -> master)
Author: Muhammad Hewedy <mhewedy@gmail.com>
Date:   Tue Mar 19 23:35:34 2019 +0300

    Modifing menu

commit 64dba215678c5a888c178990da7186f8ada939b0
Author: Muhammad Hewedy <mhewedy@gmail.com>
Date:   Tue Mar 19 23:11:35 2019 +0300

    First Commit

When catting the latest commit, and the one previous to it, they will share the same unchanged element.

lets check the latest commit:

$ git cat-file -p 5a19382be2d700129a0c0ca81340a8858075501b
tree 80c92c5fa5a179dec9d7f6f0b81b45dd7d32742d
parent 64dba215678c5a888c178990da7186f8ada939b0
author Muhammad Hewedy <mhewedy@gmail.com> 1553027734 +0300
committer Muhammad Hewedy <mhewedy@gmail.com> 1553027734 +0300

Modifing menu

$ git cat-file -p 80c92c5fa5a179dec9d7f6f0b81b45dd7d32742d
100644 blob 3e34d35b8b00e443866d4e9fcbb152a308497147 menu.txt
040000 tree 9cbe2293128382f7d60125add044260f8630012a recipes

Now let's check its parent commit (the first commit):

$ git cat-file -p 64dba215678c5a888c178990da7186f8ada939b0
tree 8ae44ec1b6ef7e4b66eb7be36fba1046081d7128
author Muhammad Hewedy <mhewedy@gmail.com> 1553026295 +0300
committer Muhammad Hewedy <mhewedy@gmail.com> 1553026295 +0300

First Commit

$ git cat-file -p 8ae44ec1b6ef7e4b66eb7be36fba1046081d7128
100644 blob 23991897e13e47ed0adb91a0082c31c82fe0cbe5 menu.txt
040000 tree 9cbe2293128382f7d60125add044260f8630012a recipes

The recipes tree has not been changed, and since both commits share it, however, the menu.txt file has been changed, so each commit links to its own version.

In the end, the head of the persistent data structure always refers to the latest version of it. with the ability to track every single change.

Simple N Ad-hoc Tree Datastructure

Salam,

I needed to have some tree data structure ..

This tree have more than 2 childern with no particular order among them.

So I decided to write this simple implementation myself.

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;

public class XSGBTree<T>
{
    private Node root;
    
    public XSGBTree(T rootInfo)
    {
        root = new Node(rootInfo);
    }
    
    public Node getRoot()
    {
        return root;
    }
    
    public Node insert(T info, Node parent)
    {
        Node node = new Node(info);
        parent.getChildNodes().add(node);
        return node;
    }
    
    public void traverse(PrintStream out)
    {
        traverse(root, out);
    }
    
    public void traverse(Node node, PrintStream out)
    {
        out.println("Node: " + node.information);
        List<Node> childNodes = node.getChildNodes();
        System.out.println("Childern: "  + childNodes.size());

        for (int i=0; i< childNodes.size() ; i++)
        {
            out.println("child #:" + i + "\t" + childNodes.get(i).information);
            traverse(childNodes.get(i), out);    
        }
    }

    class Node
    {
        T information;
        Node parent;
        List<Node> childNodes = new ArrayList<XSGBTree<T>.Node>();

        public Node(T information)
        {
            this.information = information;
        }
        
        public List<Node> getChildNodes()
        {
            return childNodes;
        }
        
        boolean isRoot()
        {
            return this.parent == null;
        }

        boolean isLeaf()
        {
            return childNodes.size() == 0;
        }

        boolean isNode()
        {
            return !isLeaf();
        }
    }
}

Test class:

import xmlschemaparsing.XSGBTree.Node;


//http://en.wikipedia.org/wiki/File:Binary_search_tree.svg

public class XSGBTreeTest
{
    public static void main(String[] args)
    {
        XSGBTree<String> xsgbTree = new XSGBTree<String>("8");
        Node rootNode = xsgbTree.getRoot();
        Node node3 = xsgbTree.insert("3", rootNode);
        Node node8 = xsgbTree.insert("10", rootNode);
        
        Node node1 = xsgbTree.insert("1", node3);
        Node node6 = xsgbTree.insert("6", node3);
        Node node7 = xsgbTree.insert("7", node3);
        
        xsgbTree.traverse(System.out);
    }
}

Stack infix in C

Based on the post of "Stack implementation in C", here's Stack infix implementation in C:

// the idea of this example from "Data Structures and Algorithms using C#"
// main_stack_infix.c

#include <stdio.h>
#include <ctype.h>
#include "stack.h"

#define CHAR_TO_INT(x) ((x)-48)

void calc(struct stack*, struct stack*);

int main(void)
{
    struct stack s1, s2;
    char *equation = "1 + 2 - 9 ";
    int count=0;

    init(&s1);
    init(&s2);

    while (*equation != '\0')
    {
        if (count == 2)
        {
            calc(&s1, &s2);
            count=1;
        }

        if (isdigit(*equation) != 0)
        {
            push(&s1, CHAR_TO_INT(*equation));
            count++;
        }else if (ispunct(*equation) != 0)
        {
            push(&s2, *equation);
        }
        equation++;     
    }
    printf("%i\n", peek(&s1));
    return 0;
}

void calc(struct stack *s1, struct stack *s2)
{
    int x = pop(s1);
    int y = pop(s1);
    int op = pop(s2);
    int ret = 0;
    
    switch (op)
    {
    case '+':
        ret = y+x;
        break;
    case '-':
        ret = y-x;
        break;
    case '*':
        ret = y*x;
        break;
    case '/':
        ret = y/x;
        break;
    }
    
    push(s1, ret);
}

Stack implementation in C

Hi folks,

I've written a stack implementation in C from sometime ago, and I'd like to share with you.

#ifndef STACK_H
#define STACK_H

#define STACK_SIZE 100

struct stack
{
    int data[STACK_SIZE];
    int top;
};

void    init(struct stack*);
void    push(struct stack*, int);
int     pop(struct stack*);
int     peek(struct stack*);
int     is_empty(struct stack*);
int     is_full(struct stack*);
void    print(struct stack*);
int     count(struct stack*);

#endif

#include <stdio.h>
#include <errno.h>
#include "stack.h"

void init(struct stack *s)
{
    s->top = -1;
}

void push(struct stack *s, int value)
{
    if (!is_full(s))
        s->data[++(s->top)] = value;
    else
        fprintf(stderr, "StackOverFlow\n");
}

int pop(struct stack *s)
{
    int ret = peek(s);
    if (errno == 0)
        s->top--;
    errno=0;        // non-throw the exception
    return ret;
}

int peek(struct stack *s)
{
    if (!is_empty(s))
        return s->data[s->top];
    else
    {
        fprintf(stderr, "StackUnderFlow\n");
        errno = 200;        // throw an exception to the calling method (in C way)
        return -1;
    }
}

int is_empty(struct stack *s)
{
    return (s->top == -1);
}

int is_full(struct stack *s)
{
    return (s->top == STACK_SIZE-1);
}

void print(struct stack *s)
{
    int i;
    for (i=0; i<= s->top ; i++)
    {
        printf("%i\n", s->data[i]);
    }
}

int count(struct stack *s)
{
    return s->top + 1;
}