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 int? 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) {
                    print("Does this actually happen?\n");
                    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;
        }
        public void remove_first_where (PredicateDelegate<T> predicate) {
            assert_not_reached ();
        }
        public void remove_all_where (PredicateDelegate<T> predicate) {
            assert_not_reached ();
        }
        public void clear () {
            assert_not_reached ();
        }


        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)
            }

        }

    }

}