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 { get; private set; }
            public SeriesNode<T> left_child { get; set; }
            public SeriesNode<T> right_child { get; set; }
            public SeriesNode<T> parent { get; set; }

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

            public SeriesNode.nil() {
                is_red = false;
                left_child = this;
                right_child = this;
                values = new Series<T>();
            }

            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 SeriesNode<T> nil;
        private RWLock rw_lock;
        private Series<SeriesNode<T>> node_refs;
        private CompareDelegate<T> comparitor;
        private int n_items;

        public SortedSeries(owned CompareDelegate<T>? comparitor = null) {
            nil = new SeriesNode<T>.nil();
            node_refs = new Series<SeriesNode<T>>();
            node_refs.add(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;
                }
            }

            var new_node = new SeriesNode<T> (item, nil);
            node_refs.add(new_node);
            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) {
            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.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) {
            var 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) {
            var 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;
            Tracker<T> values;

            public TreeTracker(SortedSeries<T> series) {
                print("New tracker!\n");
                this.series = series;
                node = series.root;
                while(node.left_child != series.nil) {
                    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 != series.nil) {
                //      next_node = node.right_child;
                //      while(next_node.left_child != series.nil) {
                //          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;
                //  }
                next_node = null;
                if (node == null) return;
                // standard inorder successor:
                if (node.right_child != series.nil) {
                    var n = node.right_child;
                    while (n.left_child != series.nil)
                        n = n.left_child;
                    next_node = n;
                    return;
                }
                var n = node;
                var p = n.parent;
                while (p != null && n == p.right_child) {
                    n = p;
                    p = p.parent;
                }
                next_node = p; // could be null (end)
            }

        }

    }

}