package com.ankurdave.part;

class ArtNode48 extends ArtNode {
    public static int count;

    public ArtNode48() {
        super();
        count++;
    }

    public ArtNode48(final ArtNode48 other) {
        super(other);
        System.arraycopy(other.keys, 0, keys, 0, 256);
        for (int i = 0; i < other.num_children; i++) {
            children[i] = other.children[i];
            if (children[i] != null) {
                children[i].refcount++;
            }
        }
        count++;
    }

    public ArtNode48(final ArtNode16 other) {
        this();
        // ArtNode
        this.num_children = other.num_children;
        this.partial_len = other.partial_len;
        System.arraycopy(other.partial, 0, this.partial, 0,
                         Math.min(MAX_PREFIX_LEN, this.partial_len));

        // ArtNode48 from ArtNode16
        for (int i = 0; i < this.num_children; i++) {
            keys[to_uint(other.keys[i])] = (byte)(i + 1);
            children[i] = other.children[i];
            if (children[i] != null) {
                children[i].refcount++;
            }
        }
    }

    public ArtNode48(final ArtNode256 other) {
        this();
        assert(other.num_children <= 48);
        // ArtNode
        this.num_children = other.num_children;
        this.partial_len = other.partial_len;
        System.arraycopy(other.partial, 0, this.partial, 0,
                         Math.min(MAX_PREFIX_LEN, this.partial_len));

        // ArtNode48 from ArtNode256
        int pos = 0;
        for (int i = 0; i < 256; i++) {
            if (other.children[i] != null) {
                keys[i] = (byte)(pos + 1);
                children[pos] = other.children[i];
                children[pos].refcount++;
                pos++;
            }
        }
    }

    @Override public Node n_clone() {
        return new ArtNode48(this);
    }

    @Override public ChildPtr find_child(byte c) {
        int idx = to_uint(keys[to_uint(c)]);
        if (idx != 0) return new ArrayChildPtr(children, idx - 1);
        return null;
    }

    @Override public Leaf minimum() {
        int idx = 0;
        while (keys[idx] == 0) idx++;
        Node child = children[to_uint(keys[idx]) - 1];
        return Node.minimum(child);
     }

    @Override public void add_child(ChildPtr ref, byte c, Node child) {
        if (this.num_children < 48) {
            // Have to do a linear scan because deletion may create holes in
            // children array
            int pos = 0;
            while (children[pos] != null) pos++;

            this.children[pos] = child;
            child.refcount++;
            this.keys[to_uint(c)] = (byte)(pos + 1);
            this.num_children++;
        } else {
            // Copy the node48 into a new node256
            ArtNode256 result = new ArtNode256(this);
            // Update the parent pointer to the node256
            ref.change(result);
            // Insert the element into the node256 instead
            result.add_child(ref, c, child);
        }
    }

    @Override public void remove_child(ChildPtr ref, byte c) {
        // Delete the child, leaving a hole in children. We can't shift children
        // because that would require decrementing many elements of keys
        int pos = to_uint(keys[to_uint(c)]);
        keys[to_uint(c)] = 0;
        children[pos - 1].decrement_refcount();
        children[pos - 1] = null;
        num_children--;

        if (num_children == 12) {
            ArtNode16 result = new ArtNode16(this);
            ref.change(result);
        }
    }

    @Override public void iter(IterCallback cb) {
        for (int i = 0; i < 256; i++) {
            int idx = to_uint(keys[i]);
            if (idx != 0) {
                Node.iter(children[idx - 1], cb);
            }
        }
    }

    @Override public boolean exhausted(int c) {
        for (int i = c; i < 256; i++) {
            if (keys[i] != 0) {
                return false;
            }
        }
        return true;
    }

    @Override public int nextChildAtOrAfter(int c) {
        int pos = c;
        for (; pos < 256; pos++) {
            if (keys[pos] != 0) {
                break;
            }
        }
        return pos;
    }

    @Override public Node childAt(int c) {
        return children[to_uint(keys[c]) - 1];
    }

    @Override public int decrement_refcount() {
        if (--this.refcount <= 0) {
            int freed = 0;
            for (int i = 0; i < this.num_children; i++) {
                if (children[i] != null) {
                    freed += children[i].decrement_refcount();
                }
            }
            count--;
            // delete this;
            return freed + 728;
            // object size (8) + refcount (4) +
            // num_children int (4) + partial_len int (4) +
            // pointer to partial array (8) + partial array size (8+4+1*MAX_PREFIX_LEN)
            // pointer to key array (8) + key array size (8+4+1*256) +
            // pointer to children array (8) + children array size (8+4+8*48)
        }
        return 0;
    }

    byte[] keys = new byte[256];
    Node[] children = new Node[48];
}

@@ -287,46 +287,234 @@
     
-for (int i = 0; i %3C other.num_children
+// Copy the children. We have to look at all elements of %60children%60%0A        // rather than just the first num_children elements because %60children%60%0A        // may not be contiguous due to deletion%0A        for (int i = 0; i %3C 48
 ; i+
@@ -1193,51 +1193,8 @@
 i%5D;%0A
-            if (children%5Bi%5D != null) %7B%0A    
     
@@ -1221,38 +1221,24 @@
 refcount++;%0A
-            %7D%0A
         %7D%0A  

Fix a bug in node48