How to convert array pointer manipulation ( &(*t)->next[x] ) from C to C#

Question

I am trying to convert some old 'C' code to C#, but having a problem with the syntax t = &(*t)->next[u]; and (*t)->end = 1;

The relevant part of original code is as follows

typedef struct Trie Trie;

struct Trie {
    int end;
    Trie *next[26];
};

void trie_insert(Trie **t, const char *p)
{
    while (*p) {
        unsigned u = trie_index(*p++);
        if (u < 26) {
            if (*t == NULL) {
                *t = calloc(1, sizeof(**t));
            }

            t = &(*t)->next[u];  // how to convert this??
        }
    }
    if (*t == NULL) {
        *t = calloc(1, sizeof(**t));
    }
    (*t)->end = 1;
}

Trie *trie_from(const char **data)
{
    Trie *t = NULL;

    while (*data) {
        trie_insert(&t, *data++);
    }

    return t;
}

and my converted code (so far) looks like this

class Trie
{
    int end { get; set; }
    public Trie[] next;

    public Trie()
    {
        next = new Trie[26];
    }
    public Trie(string[] data)
    {
        Trie[] t = null;
        foreach (string cc in data)
        {
            insert(t, cc);
        }
    }
    void insert(Trie[] t, String p)
    {
       foreach (char c in p) { 
            UInt32 u = index(c);
            if (u < 26)
            {
                if (t[0] == null)
                {
                    t[0] = new Trie();
                }

                t = &(*t)->next[u]; // how to convert this line??
            }
        }
        if (t[0] == null)
        {
            t[0] = new Trie();
        }
        (*t)->end = 1; // and this line??
    }

any help with these lines (and anything else I have done wrongly!) would be most welcome.

There's also a Trie comparison function in the C Code:

int trie_cmp(const void* pa, const void* pb)
{
    const void* const* a = pa;
    const void* const* b = pb;

    return (*a > *b) - (*a < *b);
}

which I have converted as follows:

public int CompareTo(Object obj)
        {
            Trie that = (Trie)obj;

            for (int n=0; n< 26; n++)
            {
                Trie t1 = this.next[n];
                Trie t2 = that.next[n];
                if (t1 == null && t2 == null)
                    continue;
                if (t1 == null)
                    return -1;
                if (t2 == null)
                    return +1;
                if (t1.end || t2.end) {
                    int foo = 1;        // debug point
                }
                return (t1.CompareTo(t2));
            }
            return 0;
        }

but debugging shows that every Trie referred to is NULL (the code never gets beyond if (t1 == null && t2 == null) continue;)

If it helps to know, the data used for the Trie structure is a large array of 5-letter words (always 5 letters).

I did try a free version of a commercial C++ to C# converter, which wasn't helpful.

Answer 1

I understand from the question that the algorithm is not necessarily to be implemented line by line in C#, but rather mutatis mutandis.

Since the instance var end indicates that the end of a word has been reached, it would therefore be in C# rather of type bool and not int.

Assuming that there are methods in the class Trie that encapsulate access to internals, this variable could also be made private and the name adjusted to _end appropriately.

private bool _end;

The main concern of this question is to define a tree node structure. The program has an array of nodes where each element can be either null or point to the next node. The goal is to establish a tree-like structure for strings composed of an alphabet, such as a-z. This requires an array of 26 nodes, with each position corresponding to a character in the alphabet. This approach enables identification of common prefixes, which can be useful for features like autocompletion.

An graphical example for the array of words new[]{"intranet","interstate","indecisive","intense"} would look like this:

Each end of a word is marked with a * in the graph.

A good explanation of tries can be found here.

In C code the node is a struct that is dynamically allocated. The pointers to the struct are then placed at the location based on the character in the array. In C#, the equivalent would be to create a node object using the new keyword and assigning it to the corresponding location in the array. Note: the array is initialized to null references.

Accordingly the Trie next array could be declared like this:

private readonly Trie?[] _next = new Trie?[26];

The method Insert could be implemented recursively something like this:

private void Insert(String p)
{
    if (string.IsNullOrEmpty(p))
    {
        _end = true;
        return;
    }

    var u = Index(p[0]);
    if (u < 26)
    {
        var t = _next[u] ??= new Trie();
        t.Insert(p[1..]);
    }
}

If you prefer a non-recursive variant, how about something like:

private void Insert(String p)
{
    var t = this;
    foreach (var c in p)
    {
        var u = Index(c);
        if (u < 26)
        {
            t = t._next[Index(c)] ??= new Trie();
        }
    }

    t._end = true;
}

For the sake of completeness, here the constructors:

private Trie()
{
}

public Trie(string[] data)
{
    foreach (var cc in data)
    {
        Insert(cc);
    }
}

You could call it something like this:

Trie trie = new Trie(new[]
{
    "intranet",
    "interstate",
    "indecisive",
    "intense"
});
//call some method on trie...