Invercargill/src/lib/DataStructures/SortedSeries.vala

namespace Invercargill.DataStructures {

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

        private class SeriesNode<T> {
            public bool is_red;
            public Series<T> values;
            public SeriesNode<T>? left_child;
            public SeriesNode<T>? right_child;
            public SeriesNode<T>? parent;

            public SeriesNode(T item) {
                is_red = true;
                values = new Series<T>();
                values.add(item);
            }

            public T sample() {
                return values.first_or_default();
            }

            public void add_value(T value) {
                values.add(value);
            }

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

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

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

        public override Tracker<T> get_tracker () {
            if(root == null) {
                return empty<T>().get_tracker();
            }
            return new TreeTracker<T>(root);  
        }
        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
            print("Get lock and update count of items\n");
            rw_lock.writer_lock();
            n_items++;

            // Set root if it doesn't exist
            print("Set root if it doesn't exist\n");
            if(root == null) {
                root = new SeriesNode<T>(item);
                root.is_red = false;
                rw_lock.writer_unlock();
                return;
            }

            // Find leaf node
            print("Find leaf node\n");
            var node = root;
            int cmp;
            while(true) {
                cmp = comparitor(item, node.sample());
                print(@"CMP=$cmp; item=$((int)item); sample=$((int)node.sample());\n");
                if(cmp == 0) {
                    // No change to tree, simply add the value to this node
                    print("No change to tree, simply add the value to this node\n");
                    node.add_value (item);
                    rw_lock.writer_unlock();
                    return;
                }
                if(cmp > 0) {
                    if(node.right_child == null)
                        break;
                    node = node.right_child;
                }
                if(cmp < 0) {
                    if(node.left_child == null) 
                        break;
                    node = node.left_child;
                }
            }

            // Make new node, replacing the leaf
            print("Make new node, replacing the leaf\n");
            var new_node = new SeriesNode<T>(item);
            new_node.parent = node;
            if(node == null) {
                root = new_node;
                new_node.is_red = true;
            }
            else if(cmp > 0) {
                node.right_child = new_node;
            }
            else {
                node.left_child = new_node;
            }
            
            // Balance the tree
            print("Balance the tree\n");
            if(new_node.parent?.parent != null) {
                fix_insert (new_node);
            }
            rw_lock.writer_unlock();
        }

        private void fix_insert(SeriesNode<T> new_node) {
            var 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 != null && uncle.is_red) {
                        node.parent.is_red = false;
                        uncle.is_red = false;
                        uncle.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 != null && uncle.is_red) {
                        node.parent.is_red = false;
                        uncle.is_red = false;
                        uncle.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) {
            var y = x.right_child;
            x.right_child = y.left_child;
            if(y.left_child != null)
                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) {
            var y = x.left_child;
            x.left_child = y.right_child;
            if(y.right_child != null)
                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;
            Tracker<T> values;

            public TreeTracker(SeriesNode<T> root) {
                print("New tracker!\n");
                node = root;
                while(node.left_child != null) {
                    node = node.left_child;
                }
                values = node.values.get_tracker();
                find_next_node();
            }

            public override bool has_next () {
                return values.has_next() || next_node != null;
            }
            public override T get_next () {
                if(values.has_next()) {
                    return values.get_next();
                }
                node = next_node;
                values = node.values.get_tracker();
                var result = values.get_next();
                find_next_node();
                return result;
            }

            private void find_next_node() {
                next_node = null;
                if(node.right_child != null) {
                    next_node = node.right_child;
                    while(next_node.left_child != null) {
                        next_node = next_node.left_child;
                    }
                }
                else if(node.parent == null) {
                    next_node = null;
                }
                else if(node.parent.left_child == node) {
                    next_node = node.parent;
                }
                else if(node.parent.parent.right_child == node.parent) {
                    next_node = null;
                }
                else {
                    next_node = node.parent.parent;
                }
            }

        }

    }

}