Invercargill/src/lib/DataStructures/SortedSeries.vala

namespace Invercargill.DataStructures {

    public class SortedSeries<T> : Enumerable<T>, Lot<T>, ReadOnlyCollection<T>, Collection<T> {

        [Compact]
        private class SeriesNode<T> {
            public bool is_red;
            public SeriesNodeItem<T>* first_value;
            public SeriesNodeItem<T>* last_value;
            public SeriesNode<T>* left_child;
            public SeriesNode<T>* right_child;
            public SeriesNode<T>* parent;

            public SeriesNode(owned T value, SeriesNode<T>* nil) {
                is_red = true;
                left_child = nil;
                right_child = nil;
                first_value = new SeriesNodeItem<T>((owned)value);
                last_value = first_value;
            }

            public SeriesNode.nil() {
                is_red = false;
                left_child = this;
                right_child = this;
            }

            public unowned T sample() {
                return first_value->item;
            }

            public void add_value(owned T value) {
                SeriesNodeItem<T>* new_value = new SeriesNodeItem<T>((owned)value);
                last_value->next = new_value;
                last_value = new_value;
            }

            //  public void remove_all_values_where (PredicateDelegate<T> predicate) {
            //      values = values.where(v => !predicate(v)).to_buffer();
            //  }
        }

        [Compact]
        private class SeriesNodeItem<T> { 
            public T item;
            public SeriesNodeItem<T>* next;

            public SeriesNodeItem(owned T item) {
                this.item = (owned)item;
            }
        }

        private SeriesNode<T>* root;
        private SeriesNode<T>* nil;
        private RWLock rw_lock;
        private CompareDelegate<T> comparitor;
        private int n_items;

        public override uint length { get { return n_items; }}

        public SortedSeries(owned CompareDelegate<T>? comparitor = null) {
            nil = new SeriesNode<T>.nil();
            root = nil;
            rw_lock = RWLock();
            n_items = 0;
            this.comparitor = (owned)comparitor ?? Operators.comparison<T>();
        }

        public override Tracker<T> get_tracker () {
            if(root == nil) {
                return empty<T>().get_tracker();
            }
            return new TreeTracker<T>(this);  
        }
        public override uint? peek_count () {
            return n_items;
        }
        public override EnumerableInfo get_info () {
            return new EnumerableInfo.infer_ultimate (this, EnumerableCategory.IN_MEMORY);
        }


        public void add (T item) {
            // Get lock and update count of items
            //  rw_lock.writer_lock();
            n_items++;

            SeriesNode<T>* parent = null;
            SeriesNode<T>* current = root;
            int cmp = 0;

            while(current != nil) {
                parent = current;
                cmp = comparitor(item, current->sample());
                if(cmp == 0) {
                    // Add to node, has no effect on tree
                    current->add_value(item);
                    //  rw_lock.writer_unlock();
                    return;
                }
                if(cmp < 0) {
                    current = current->left_child;
                }
                else {
                    current = current->right_child;
                }
            }

            SeriesNode<T>* new_node = new SeriesNode<T> (item, nil);
            new_node->parent = parent;
            if(parent == null) {
                root = new_node;
            }
            else {
                if(cmp == 0) {
                    assert_not_reached ();
                }
                else if(cmp < 0) {
                    parent->left_child = new_node;
                }
                else {
                    parent->right_child = new_node;
                }
            }

            if(new_node->parent == null) {
                new_node->is_red = false;
            }
            else if(new_node->parent->parent != null) {
                fix_insert(new_node);
            }

            //  rw_lock.writer_unlock();
        }

        private void fix_insert(SeriesNode<T>* new_node) {
            SeriesNode<T>* node = new_node;
            while(node != root && node->parent->is_red) {
                if(node->parent == node->parent->parent->left_child) {
                    var uncle = node->parent->parent->right_child;
                    if(uncle->is_red) {
                        node->parent->is_red = false;
                        uncle->is_red = false;
                        node->parent->parent->is_red = true;
                        node = node->parent->parent;
                        continue;
                    }
                    if(node == node->parent->right_child) {
                        node = node->parent;
                        rotate_left(node);
                    }
                    node->parent->is_red = false;
                    node->parent->parent->is_red = true;
                    rotate_right (node->parent->parent);
                }
                else {
                    var uncle = node->parent->parent->left_child;
                    if(uncle->is_red) {
                        node->parent->is_red = false;
                        uncle->is_red = false;
                        node->parent->parent->is_red = true;
                        node = node->parent->parent;
                        continue;
                    }
                    if(node == node->parent->left_child) {
                        node = node->parent;
                        rotate_right(node);
                    }
                    node->parent->is_red = false;
                    node->parent->parent->is_red = true;
                    rotate_left(node->parent->parent);
                }
            }
            root->is_red = false;
        }

        ~SortedSeries() {
            clear();
            delete nil;
        }

        // --- removal methods and helpers ---

        public void remove_first_where (PredicateDelegate<T> predicate) {
            if (root == nil) return;

            // iterative inorder using Vector as stack
            Vector<SeriesNode<T>*> stack = new Vector<SeriesNode<T>*>();
            SeriesNode<T>* node = root;

            while (node != null || stack.length != 0) {
                while (node != null && node != nil) {
                    stack.add (node);
                    node = node->left_child;
                }
                if (stack.length == 0) break;
                node = stack[stack.length - 1];
                stack.remove_at (stack.length - 1);

                // scan values linked list
                SeriesNodeItem<T>* prev = null;
                SeriesNodeItem<T>* vi = node->first_value;
                while (vi != null) {
                    SeriesNodeItem<T>* next = vi->next;
                    if (predicate (vi->item)) {
                        // remove vi from list and delete it
                        if (prev == null) {
                            node->first_value = next;
                            if (node->first_value == null)
                                node->last_value = null;
                        } else {
                            prev->next = next;
                            if (prev->next == null)
                                node->last_value = prev;
                        }
                        // Delete won't unref the value so explicitly set to null before deleting
                        vi->item = null;
                        delete vi;
                        n_items--;
                        // if node has no remaining values, remove node from tree (and delete it)
                        if (node->first_value == null) {
                            rb_delete_node (node);
                        }
                        return;
                    }
                    prev = vi;
                    vi = next;
                }

                node = node->right_child;
            }
        }

        public void remove_all_where (PredicateDelegate<T> predicate) {
            if (root == nil) return;

            // collect nodes via inorder traversal first (so tree mutations won't confuse traversal)
            Vector<SeriesNode<T>*> nodes = new Vector<SeriesNode<T>*>();
            Vector<SeriesNode<T>*> stack = new Vector<SeriesNode<T>*>();
            SeriesNode<T>* node = root;
            while (node != null || stack.length != 0) {
                while (node != null && node != nil) {
                    stack.add (node);
                    node = node->left_child;
                }
                if (stack.length == 0) break;
                node = stack[stack.length - 1];
                stack.remove_at (stack.length - 1);
                nodes.add (node);
                node = node->right_child;
            }

            // process each collected node (some nodes may already have been removed; skip those)
            for (uint i = 0; i < nodes.length; i++) {
                var n = nodes[i];
                // skip if node is the sentinel or already orphaned (not in tree)
                if (n == nil) continue;
                // quick check: if n is not reachable from any parent and isn't root, it may have been removed
                if (n->parent == null && n != root) continue;

                SeriesNodeItem<T>* prev = null;
                SeriesNodeItem<T>* vi = n->first_value;
                while (vi != null) {
                    SeriesNodeItem<T>* next = vi->next;
                    if (predicate (vi->item)) {
                        // remove vi and delete it
                        if (prev == null) {
                            n->first_value = next;
                            if (n->first_value == null)
                                n->last_value = null;
                        } else {
                            prev->next = next;
                            if (prev->next == null)
                                n->last_value = prev;
                        }
                        // Delete won't unref the value so explicitly set to null before deleting
                        vi->item = null;
                        delete vi;
                        n_items--;
                        // continue scanning with same prev (since prev didn't change)
                        vi = next;
                        continue;
                    }
                    prev = vi;
                    vi = next;
                }
                // if node now empty, delete node from tree
                if (n->first_value == null) {
                    rb_delete_node (n);
                }
            }
        }

        public void clear () {
            if (root == nil) {
                n_items = 0;
                return;
            }

            // postorder traversal to delete all nodes and their items (retain nil sentinel)
            Vector<SeriesNode<T>*> stack = new Vector<SeriesNode<T>*>();
            SeriesNode<T>* node = root;
            SeriesNode<T>* last = null;

            while ((node != null && node != nil) || stack.length != 0) {
                if (node != null && node != nil) {
                    stack.add (node);
                    node = node->left_child;
                } else {
                    var peek = stack[stack.length - 1];
                    if (peek->right_child != nil && last != peek->right_child) {
                        node = peek->right_child;
                    } else {
                        // delete all items in peek
                        SeriesNodeItem<T>* vi = peek->first_value;
                        while (vi != null) {
                            SeriesNodeItem<T>* next = vi->next;
                            // Delete won't unref the value so explicitly set to null before deleting
                            vi->item = null;
                            delete vi;
                            vi = next;
                        }
                        // sever links and delete node (but don't delete sentinel nil)
                        peek->first_value = null;
                        peek->last_value = null;
                        peek->left_child = nil;
                        peek->right_child = nil;
                        peek->parent = null;
                        last = peek;
                        stack.remove_at (stack.length - 1);
                        delete peek;
                    }
                }
            }

            // reset structure
            root = nil;
            n_items = 0;
        }

        // --- RB helper functions (use nil sentinel; delete removed node at the end) ---

        private void transplant (SeriesNode<T>* u, SeriesNode<T>* v) {
            if (u->parent == null) {
                root = v;
            } else if (u == u->parent->left_child) {
                u->parent->left_child = v;
            } else {
                u->parent->right_child = v;
            }
            // set v->parent even if v == nil (that's OK)
            if (v != null)
                v->parent = u->parent;
        }

        private SeriesNode<T>* tree_minimum (SeriesNode<T>* x) {
            while (x->left_child != nil) {
                x = x->left_child;
            }
            return x;
        }

        // delete a node z from the tree (assumes z->first_value == null). deletes the node object at the end.
        // uses standard RB-delete algorithm; x and relatives may be nil sentinel.
        private void rb_delete_node (SeriesNode<T>* z) {
            if (z == nil) return;
            // remember original z to delete at end
            SeriesNode<T>* z_original = z;

            SeriesNode<T>* y = z;
            bool y_original_red = y->is_red;
            SeriesNode<T>* x = nil; // x will be the node that moves into y's original position (or nil)

            if (z->left_child == nil) {
                x = z->right_child;
                transplant (z, z->right_child);
            } else if (z->right_child == nil) {
                x = z->left_child;
                transplant (z, z->left_child);
            } else {
                y = tree_minimum (z->right_child);
                y_original_red = y->is_red;
                x = y->right_child;
                if (y->parent == z) {
                    // x->parent should be y (x may be nil)
                    if (x != null)
                        x->parent = y;
                } else {
                    transplant (y, y->right_child);
                    y->right_child = z->right_child;
                    if (y->right_child != null)
                        y->right_child->parent = y;
                }
                transplant (z, y);
                y->left_child = z->left_child;
                if (y->left_child != null)
                    y->left_child->parent = y;
                y->is_red = z->is_red;
            }

            // If the removed/moved node was black, fixup
            if (!y_original_red) {
                rb_delete_fixup (x);
            }

            // ensure root is black
            if (root != nil)
                root->is_red = false;

            // finally delete the original node (but never delete nil)
            if (z_original != nil)
                delete z_original;
        }

        // fixup when x replaced a black node. x may be nil sentinel.
        private void rb_delete_fixup (SeriesNode<T>* x) {
            while (x != root && !x->is_red) {
                if (x == x->parent->left_child) {
                    var w = x->parent->right_child;
                    if (w->is_red) {
                        w->is_red = false;
                        x->parent->is_red = true;
                        rotate_left (x->parent);
                        w = x->parent->right_child;
                    }
                    if ((!w->left_child->is_red) && (!w->right_child->is_red)) {
                        w->is_red = true;
                        x = x->parent;
                    } else {
                        if (!w->right_child->is_red) {
                            if (w->left_child != nil)
                                w->left_child->is_red = false;
                            w->is_red = true;
                            rotate_right (w);
                            w = x->parent->right_child;
                        }
                        w->is_red = x->parent->is_red;
                        x->parent->is_red = false;
                        if (w->right_child != nil)
                            w->right_child->is_red = false;
                        rotate_left (x->parent);
                        x = root;
                    }
                } else {
                    var w = x->parent->left_child;
                    if (w->is_red) {
                        w->is_red = false;
                        x->parent->is_red = true;
                        rotate_right (x->parent);
                        w = x->parent->left_child;
                    }
                    if ((!w->right_child->is_red) && (!w->left_child->is_red)) {
                        w->is_red = true;
                        x = x->parent;
                    } else {
                        if (!w->left_child->is_red) {
                            if (w->right_child != nil)
                                w->right_child->is_red = false;
                            w->is_red = true;
                            rotate_left (w);
                            w = x->parent->left_child;
                        }
                        w->is_red = x->parent->is_red;
                        x->parent->is_red = false;
                        if (w->left_child != nil)
                            w->left_child->is_red = false;
                        rotate_right (x->parent);
                        x = root;
                    }
                }
            }
            x->is_red = false;
        }

        private void rotate_left(SeriesNode<T>* x) {
            SeriesNode<T>* y = x->right_child;
            x->right_child = y->left_child;
            if(y->left_child != nil)
                y->left_child->parent = x;
            y->parent = x->parent;
            if(x->parent == null)
                root = y;
            else if(x->parent->left_child == x)
                x->parent->left_child = y;
            else
                x->parent->right_child = y;
            y->left_child = x;
            x->parent = y;
        }

        private void rotate_right(SeriesNode<T>* x) {
            SeriesNode<T>* y = x->left_child;
            x->left_child = y->right_child;
            if(y->right_child != nil)
                y->right_child->parent = x;
            y->parent = x->parent;
            if(x->parent == null)
                root = y;
            else if(x->parent->right_child == x)
                x->parent->right_child = y;
            else
                x->parent->left_child = y;
            y->right_child = x;
            x->parent = y;
        }
        
        private class TreeTracker<T> : Tracker<T> {

            SeriesNode<T>* node;
            SeriesNode<T>* next_node;
            SortedSeries<T> series;
            SeriesNodeItem<T>* values;

            public TreeTracker(SortedSeries<T> series) {
                this.series = series;
                node = series.root;
                while(node->left_child != series.nil) {
                    node = node->left_child;
                }
                values = node->first_value;
                find_next_node();
            }

            public override bool has_next () {
                return values != null || next_node != null;
            }
            public override T get_next () {
                if(values != null) {
                    var item = values->item;
                    values = values->next;
                    return item;
                }
                node = next_node;
                var item = node->first_value->item;
                values = node->first_value->next;
                find_next_node();
                return item;
            }

            private void find_next_node() {
                next_node = null;
                if (node == null) return;
                // standard inorder successor:
                if (node->right_child != series.nil) {
                    SeriesNode<T>* n = node->right_child;
                    while (n->left_child != series.nil)
                        n = n->left_child;
                    next_node = n;
                    return;
                }
                SeriesNode<T>* n = node;
                SeriesNode<T>* p = n->parent;
                while (p != null && n == p->right_child) {
                    n = p;
                    p = p->parent;
                }
                next_node = p; // could be null (end)
            }

        }

    }

}