/* Example which creates a dictionary using the "trie" datastructure */
class trieClass  {
    var conts;

    const STRIDE = 4; // The conts are an array of [n*STRIDE] quads

    // These are the offsets of the subcomponents of each triple.
    const CHAR = 0, CHILD = 1, NEXT = 2, VAL = 3;

    const INITSIZE = 128; // Pick a reasonable size

    // Allocate the initial conts array with an optional first argument size
    public proc create() {
        var size = INITSIZE;
        if (oadl::nargs()) size = oadl::arg(0);
        conts = new Array(size, STRIDE);
        conts[0,CHAR] = "TRIE"; // Just for debugging
        conts[0,NEXT] = 1; // Allocate first slot to track # used
    }

    // Allocate a node. Extents conts if needed.
    proc alloc() {
        var used = conts[0,NEXT];
        var len = conts.length();
        var res = used;

        // Extend the array if needed
        if (used >= len) {
            conts = conts.reshape(len*2, STRIDE);
        }

        // Increment and store the used count
        used++;
        conts[0,NEXT] = used;

        // Initialize and return the next available slot
        conts[res,[CHAR,VAL,CHILD,NEXT]] = nil;
        return res;
    }

    proc insert(key, val) {
        var used = conts[0,NEXT];
        var keyLen = key.length();
        var curr = (used == 1) ? nil : 1;
        var ch = keyLen ? key[0] : nil;

        while (keyLen) {
            // Find the current char in the linked list at this level
            var prev = nil;
            while ((curr != nil) && (conts[curr,CHAR] != ch)) {
                prev = curr;
                curr = conts[curr,NEXT];
            }

            if (curr == nil) {
                // Not found. Create a new entry.
                curr = alloc();
                conts[curr,CHAR] = ch;
                if (prev != nil) conts[prev,NEXT] = curr;
            }

            // We now have a node with ch in it
            if (keyLen == 1) {
                // We are done! Insert the value at this position
                conts[curr,VAL] = val;
                return;
            }

            // Get the suffix of the key and continue
            key = key[1:];
            ch = key[0];
            keyLen--;

            // Descend one level
            var level = conts[curr,CHILD];
            if (!level) {
                // Need to create a new level so we can descend
                level = alloc();
                conts[curr,CHILD] = level;
                conts[level,CHAR] = ch;
            }

            // Start iterating at this lower level
            curr = level;
        }
    }

    proc lookup(key) {
        var used = conts[0,NEXT];
        var keyLen = key.length();
        var curr = (used == 1) ? nil : 1;
        var ch = keyLen ? key[0] : nil;

        while (keyLen) {
            // Find the current char in the linked list at this level
            while ((curr != nil) && (conts[curr,CHAR] != ch)) {
                curr = conts[curr,NEXT];
            }

            if (curr == nil) return nil; // Not found. Not in trie.

            // We now have a node with ch in it
            if (keyLen == 1) {
                // End of string. See if there is a value.
                var val = conts[curr,VAL];
                if (val != nil) return val;

                // Check to see if there is a unique suffix
                curr = conts[curr,CHILD];
                while (curr) {
                    if (conts[curr,NEXT]) return nil; // Not unique
                    var child = conts[curr,CHILD];
                    val = conts[curr,VAL];

                    if (val != nil) {
                        // Found a value at this level. If there are no
                        // children, then this was a unique suffix.
                        return (child == nil) ? val : nil;
                    }

                    // Descend one level
                    curr = child;
                }

                // This should not happen...
                return nil;
            }

            // Get the suffix of the key and continue
            key = key[1:];
            ch = key[0];
            keyLen--;

            // Descend one level
            curr = conts[curr,CHILD];
            if (!curr) return nil; // Badness. Not found.
        }
    }

    // Overload array index assignment as "insert", just like a Dict
    operator [=] (key, val) {
        insert(key, val);
    }

    // Overload array index fetch as "lookup", just like a dict
    operator [] (key) {
        return lookup(key);
    }

    public proc print() {
        var used = conts[0,NEXT];
        // SL - left adjust; / - advance to next line after format
        ::print("SL,4V6,V,/",
                        // The header row
                        {"#", "CH","CHLD","NEXT","VAL"},
                        // The number column
                        [used,1].iterate(),
                        // The chars
                        WideChar(conts[0:used-1,0]),
                        // The contents
                        conts[0:used-1,1:]);
    }
}

proc main()
{
    var trie = new trieClass();
    trie["fred"] = 1;
    trie["foo"] = 2;
    trie["bar"] = 3;
    "fred = ", trie["fred"], '\n';
    "foo  = ", trie["foo" ], '\n';
    "bar  = ", trie["bar" ], '\n';
    "fr   = ", trie["fr"  ], '\n';
    trie.print();
}