/*
	* Copyright (C) 2002-2019 Sebastiano Vigna
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	*     http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
package it.unimi.dsi.fastutil.objects;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.NoSuchElementException;
A type-specific AVL tree set with a fast, small-footprint implementation.
 The iterators provided by this class are type-specific bidirectional iterators. Moreover, the iterator returned by iterator() can be safely cast to a type-specific list iterator. /**
 * A type-specific AVL tree set with a fast, small-footprint implementation.
 *
 * <p>
 * The iterators provided by this class are type-specific
 * {@link it.unimi.dsi.fastutil.BidirectionalIterator bidirectional iterators}.
 * Moreover, the iterator returned by {@code iterator()} can be safely cast to a
 * type-specific {@linkplain java.util.ListIterator list iterator}.
 */
public class ObjectAVLTreeSet<K> extends AbstractObjectSortedSet<K>
		implements
			java.io.Serializable,
			Cloneable,
			ObjectSortedSet<K> {
	
A reference to the root entry. /** A reference to the root entry. */
	protected transient Entry<K> tree;
	
Number of elements in this set. /** Number of elements in this set. */
	protected int count;
	
The entry of the first element of this set. /** The entry of the first element of this set. */
	protected transient Entry<K> firstEntry;
	
The entry of the last element of this set. /** The entry of the last element of this set. */
	protected transient Entry<K> lastEntry;
	
This set's comparator, as provided in the constructor. /** This set's comparator, as provided in the constructor. */
	protected Comparator<? super K> storedComparator;
	
This set's actual comparator; it may differ from ObjectAVLTreeSet<K>.storedComparator because it is always a type-specific comparator, so it could be derived from the former by wrapping. /**
	 * This set's actual comparator; it may differ from {@link #storedComparator}
	 * because it is always a type-specific comparator, so it could be derived from
	 * the former by wrapping.
	 */
	protected transient Comparator<? super K> actualComparator;
	private static final long serialVersionUID = -7046029254386353130L;
	{
		allocatePaths();
	}
	
Creates a new empty tree set.
/**
	 * Creates a new empty tree set.
	 */
	public ObjectAVLTreeSet() {
		tree = null;
		count = 0;
	}
	
Generates the comparator that will be actually used.
 When a given Comparator is specified and stored in ObjectAVLTreeSet<K>.storedComparator, we must check whether it is type-specific. If it is so, we can used directly, and we store it in ObjectAVLTreeSet<K>.actualComparator. Otherwise, we adapt it using a helper static method. /**
	 * Generates the comparator that will be actually used.
	 *
	 * <p>
	 * When a given {@link Comparator} is specified and stored in
	 * {@link #storedComparator}, we must check whether it is type-specific. If it
	 * is so, we can used directly, and we store it in {@link #actualComparator}.
	 * Otherwise, we adapt it using a helper static method.
	 */
	private void setActualComparator() {
		actualComparator = storedComparator;
	}
	
Creates a new empty tree set with the given comparator.
Params:
c –  a Comparator (even better, a type-specific comparator)./**
	 * Creates a new empty tree set with the given comparator.
	 *
	 * @param c
	 *            a {@link Comparator} (even better, a type-specific comparator).
	 */
	public ObjectAVLTreeSet(final Comparator<? super K> c) {
		this();
		storedComparator = c;
		setActualComparator();
	}
	
Creates a new tree set copying a given set.
Params:
c – 
           a collection to be copied into the new tree set./**
	 * Creates a new tree set copying a given set.
	 *
	 * @param c
	 *            a collection to be copied into the new tree set.
	 */
	public ObjectAVLTreeSet(final Collection<? extends K> c) {
		this();
		addAll(c);
	}
	
Creates a new tree set copying a given sorted set (and its Comparator). 
Params:
s –  a SortedSet to be copied into the new tree set./**
	 * Creates a new tree set copying a given sorted set (and its
	 * {@link Comparator}).
	 *
	 * @param s
	 *            a {@link SortedSet} to be copied into the new tree set.
	 */
	public ObjectAVLTreeSet(final SortedSet<K> s) {
		this(s.comparator());
		addAll(s);
	}
	
Creates a new tree set copying a given type-specific collection.
Params:
c – 
           a type-specific collection to be copied into the new tree set./**
	 * Creates a new tree set copying a given type-specific collection.
	 *
	 * @param c
	 *            a type-specific collection to be copied into the new tree set.
	 */
	public ObjectAVLTreeSet(final ObjectCollection<? extends K> c) {
		this();
		addAll(c);
	}
	
Creates a new tree set copying a given type-specific sorted set (and its Comparator). 
Params:
s – 
           a type-specific sorted set to be copied into the new tree set./**
	 * Creates a new tree set copying a given type-specific sorted set (and its
	 * {@link Comparator}).
	 *
	 * @param s
	 *            a type-specific sorted set to be copied into the new tree set.
	 */
	public ObjectAVLTreeSet(final ObjectSortedSet<K> s) {
		this(s.comparator());
		addAll(s);
	}
	
Creates a new tree set using elements provided by a type-specific iterator.
Params:
i – 
           a type-specific iterator whose elements will fill the set./**
	 * Creates a new tree set using elements provided by a type-specific iterator.
	 *
	 * @param i
	 *            a type-specific iterator whose elements will fill the set.
	 */
	public ObjectAVLTreeSet(final Iterator<? extends K> i) {
		while (i.hasNext())
			add(i.next());
	}
	
Creates a new tree set and fills it with the elements of a given array using a given Comparator. 
Params:
a – 
           an array whose elements will be used to fill the set.
offset – 
           the first element to use.
length – 
           the number of elements to use.
c –  a Comparator (even better, a type-specific comparator)./**
	 * Creates a new tree set and fills it with the elements of a given array using
	 * a given {@link Comparator}.
	 *
	 * @param a
	 *            an array whose elements will be used to fill the set.
	 * @param offset
	 *            the first element to use.
	 * @param length
	 *            the number of elements to use.
	 * @param c
	 *            a {@link Comparator} (even better, a type-specific comparator).
	 */
	public ObjectAVLTreeSet(final K[] a, final int offset, final int length, final Comparator<? super K> c) {
		this(c);
		ObjectArrays.ensureOffsetLength(a, offset, length);
		for (int i = 0; i < length; i++)
			add(a[offset + i]);
	}
	
Creates a new tree set and fills it with the elements of a given array.
Params:
a – 
           an array whose elements will be used to fill the set.
offset – 
           the first element to use.
length – 
           the number of elements to use./**
	 * Creates a new tree set and fills it with the elements of a given array.
	 *
	 * @param a
	 *            an array whose elements will be used to fill the set.
	 * @param offset
	 *            the first element to use.
	 * @param length
	 *            the number of elements to use.
	 */
	public ObjectAVLTreeSet(final K[] a, final int offset, final int length) {
		this(a, offset, length, null);
	}
	
Creates a new tree set copying the elements of an array.
Params:
a – 
           an array to be copied into the new tree set./**
	 * Creates a new tree set copying the elements of an array.
	 *
	 * @param a
	 *            an array to be copied into the new tree set.
	 */
	public ObjectAVLTreeSet(final K[] a) {
		this();
		int i = a.length;
		while (i-- != 0)
			add(a[i]);
	}
	
Creates a new tree set copying the elements of an array using a given Comparator. 
Params:
a – 
           an array to be copied into the new tree set.
c –  a Comparator (even better, a type-specific comparator)./**
	 * Creates a new tree set copying the elements of an array using a given
	 * {@link Comparator}.
	 *
	 * @param a
	 *            an array to be copied into the new tree set.
	 * @param c
	 *            a {@link Comparator} (even better, a type-specific comparator).
	 */
	public ObjectAVLTreeSet(final K[] a, final Comparator<? super K> c) {
		this(c);
		int i = a.length;
		while (i-- != 0)
			add(a[i]);
	}
	/*
	 * The following methods implements some basic building blocks used by all
	 * accessors. They are (and should be maintained) identical to those used in
	 * AVLTreeMap.drv.
	 *
	 * The add()/remove() code is derived from Ben Pfaff's GNU libavl
	 * (http://www.msu.edu/~pfaffben/avl/). If you want to understand what's going
	 * on, you should have a look at the literate code contained therein first.
	 */
	
Compares two keys in the right way.
 This method uses the ObjectAVLTreeSet<K>.actualComparator if it is non-null. Otherwise, it resorts to primitive type comparisons or to compareTo(). 
Params:
k1 – 
           the first key.
k2 – 
           the second key.
Returns:
a number smaller than, equal to or greater than 0, as usual (i.e.,
        when k1 < k2, k1 = k2 or k1 > k2, respectively)./**
	 * Compares two keys in the right way.
	 *
	 * <p>
	 * This method uses the {@link #actualComparator} if it is non-{@code null}.
	 * Otherwise, it resorts to primitive type comparisons or to
	 * {@link Comparable#compareTo(Object) compareTo()}.
	 *
	 * @param k1
	 *            the first key.
	 * @param k2
	 *            the second key.
	 * @return a number smaller than, equal to or greater than 0, as usual (i.e.,
	 *         when k1 &lt; k2, k1 = k2 or k1 &gt; k2, respectively).
	 */
	@SuppressWarnings("unchecked")
	final int compare(final K k1, final K k2) {
		return actualComparator == null ? (((Comparable<K>) (k1)).compareTo(k2)) : actualComparator.compare(k1, k2);
	}
	
Returns the entry corresponding to the given key, if it is in the tree; null, otherwise. 
Params:
k – 
           the key to search for.
Returns:
the corresponding entry, or null if no entry with the given key exists./**
	 * Returns the entry corresponding to the given key, if it is in the tree;
	 * {@code null}, otherwise.
	 *
	 * @param k
	 *            the key to search for.
	 * @return the corresponding entry, or {@code null} if no entry with the given
	 *         key exists.
	 */
	private Entry<K> findKey(final K k) {
		Entry<K> e = tree;
		int cmp;
		while (e != null && (cmp = compare(k, e.key)) != 0)
			e = cmp < 0 ? e.left() : e.right();
		return e;
	}
	
Locates a key.
Params:
k – 
           a key.
Returns:
the last entry on a search for the given key; this will be the given
        key, if it present; otherwise, it will be either the smallest greater
        key or the greatest smaller key./**
	 * Locates a key.
	 *
	 * @param k
	 *            a key.
	 * @return the last entry on a search for the given key; this will be the given
	 *         key, if it present; otherwise, it will be either the smallest greater
	 *         key or the greatest smaller key.
	 */
	final Entry<K> locateKey(final K k) {
		Entry<K> e = tree, last = tree;
		int cmp = 0;
		while (e != null && (cmp = compare(k, e.key)) != 0) {
			last = e;
			e = cmp < 0 ? e.left() : e.right();
		}
		return cmp == 0 ? e : last;
	}
	
This vector remembers the path followed during the current insertion. It
suffices for about 232 entries.
/**
	 * This vector remembers the path followed during the current insertion. It
	 * suffices for about 2<sup>32</sup> entries.
	 */
	private transient boolean dirPath[];
	private void allocatePaths() {
		dirPath = new boolean[48];
	}
	@Override
	public boolean add(final K k) {
		if (tree == null) { // The case of the empty tree is treated separately.
			count++;
			tree = lastEntry = firstEntry = new Entry<>(k);
		} else {
			Entry<K> p = tree, q = null, y = tree, z = null, e = null, w = null;
			int cmp, i = 0;
			while (true) {
				if ((cmp = compare(k, p.key)) == 0)
					return false;
				if (p.balance() != 0) {
					i = 0;
					z = q;
					y = p;
				}
				if (dirPath[i++] = cmp > 0) {
					if (p.succ()) {
						count++;
						e = new Entry<>(k);
						if (p.right == null)
							lastEntry = e;
						e.left = p;
						e.right = p.right;
						p.right(e);
						break;
					}
					q = p;
					p = p.right;
				} else {
					if (p.pred()) {
						count++;
						e = new Entry<>(k);
						if (p.left == null)
							firstEntry = e;
						e.right = p;
						e.left = p.left;
						p.left(e);
						break;
					}
					q = p;
					p = p.left;
				}
			}
			p = y;
			i = 0;
			while (p != e) {
				if (dirPath[i])
					p.incBalance();
				else
					p.decBalance();
				p = dirPath[i++] ? p.right : p.left;
			}
			if (y.balance() == -2) {
				Entry<K> x = y.left;
				if (x.balance() == -1) {
					w = x;
					if (x.succ()) {
						x.succ(false);
						y.pred(x);
					} else
						y.left = x.right;
					x.right = y;
					x.balance(0);
					y.balance(0);
				} else {
					assert x.balance() == 1;
					w = x.right;
					x.right = w.left;
					w.left = x;
					y.left = w.right;
					w.right = y;
					if (w.balance() == -1) {
						x.balance(0);
						y.balance(1);
					} else if (w.balance() == 0) {
						x.balance(0);
						y.balance(0);
					} else {
						x.balance(-1);
						y.balance(0);
					}
					w.balance(0);
					if (w.pred()) {
						x.succ(w);
						w.pred(false);
					}
					if (w.succ()) {
						y.pred(w);
						w.succ(false);
					}
				}
			} else if (y.balance() == +2) {
				Entry<K> x = y.right;
				if (x.balance() == 1) {
					w = x;
					if (x.pred()) {
						x.pred(false);
						y.succ(x);
					} else
						y.right = x.left;
					x.left = y;
					x.balance(0);
					y.balance(0);
				} else {
					assert x.balance() == -1;
					w = x.left;
					x.left = w.right;
					w.right = x;
					y.right = w.left;
					w.left = y;
					if (w.balance() == 1) {
						x.balance(0);
						y.balance(-1);
					} else if (w.balance() == 0) {
						x.balance(0);
						y.balance(0);
					} else {
						x.balance(1);
						y.balance(0);
					}
					w.balance(0);
					if (w.pred()) {
						y.succ(w);
						w.pred(false);
					}
					if (w.succ()) {
						x.pred(w);
						w.succ(false);
					}
				}
			} else
				return true;
			if (z == null)
				tree = w;
			else {
				if (z.left == y)
					z.left = w;
				else
					z.right = w;
			}
		}
		return true;
	}
	
Finds the parent of an entry.
Params:
e – 
           a node of the tree.
Returns:
the parent of the given node, or null for the root./**
	 * Finds the parent of an entry.
	 *
	 * @param e
	 *            a node of the tree.
	 * @return the parent of the given node, or {@code null} for the root.
	 */
	private Entry<K> parent(final Entry<K> e) {
		if (e == tree)
			return null;
		Entry<K> x, y, p;
		x = y = e;
		while (true) {
			if (y.succ()) {
				p = y.right;
				if (p == null || p.left != e) {
					while (!x.pred())
						x = x.left;
					p = x.left;
				}
				return p;
			} else if (x.pred()) {
				p = x.left;
				if (p == null || p.right != e) {
					while (!y.succ())
						y = y.right;
					p = y.right;
				}
				return p;
			}
			x = x.left;
			y = y.right;
		}
	}
	@SuppressWarnings("unchecked")
	@Override
	public boolean remove(final Object k) {
		if (tree == null)
			return false;
		int cmp;
		Entry<K> p = tree, q = null;
		boolean dir = false;
		final K kk = (K) k;
		while (true) {
			if ((cmp = compare(kk, p.key)) == 0)
				break;
			else if (dir = cmp > 0) {
				q = p;
				if ((p = p.right()) == null)
					return false;
			} else {
				q = p;
				if ((p = p.left()) == null)
					return false;
			}
		}
		if (p.left == null)
			firstEntry = p.next();
		if (p.right == null)
			lastEntry = p.prev();
		if (p.succ()) {
			if (p.pred()) {
				if (q != null) {
					if (dir)
						q.succ(p.right);
					else
						q.pred(p.left);
				} else
					tree = dir ? p.right : p.left;
			} else {
				p.prev().right = p.right;
				if (q != null) {
					if (dir)
						q.right = p.left;
					else
						q.left = p.left;
				} else
					tree = p.left;
			}
		} else {
			Entry<K> r = p.right;
			if (r.pred()) {
				r.left = p.left;
				r.pred(p.pred());
				if (!r.pred())
					r.prev().right = r;
				if (q != null) {
					if (dir)
						q.right = r;
					else
						q.left = r;
				} else
					tree = r;
				r.balance(p.balance());
				q = r;
				dir = true;
			} else {
				Entry<K> s;
				while (true) {
					s = r.left;
					if (s.pred())
						break;
					r = s;
				}
				if (s.succ())
					r.pred(s);
				else
					r.left = s.right;
				s.left = p.left;
				if (!p.pred()) {
					p.prev().right = s;
					s.pred(false);
				}
				s.right = p.right;
				s.succ(false);
				if (q != null) {
					if (dir)
						q.right = s;
					else
						q.left = s;
				} else
					tree = s;
				s.balance(p.balance());
				q = r;
				dir = false;
			}
		}
		Entry<K> y;
		while (q != null) {
			y = q;
			q = parent(y);
			if (!dir) {
				dir = q != null && q.left != y;
				y.incBalance();
				if (y.balance() == 1)
					break;
				else if (y.balance() == 2) {
					Entry<K> x = y.right;
					assert x != null;
					if (x.balance() == -1) {
						Entry<K> w;
						assert x.balance() == -1;
						w = x.left;
						x.left = w.right;
						w.right = x;
						y.right = w.left;
						w.left = y;
						if (w.balance() == 1) {
							x.balance(0);
							y.balance(-1);
						} else if (w.balance() == 0) {
							x.balance(0);
							y.balance(0);
						} else {
							assert w.balance() == -1;
							x.balance(1);
							y.balance(0);
						}
						w.balance(0);
						if (w.pred()) {
							y.succ(w);
							w.pred(false);
						}
						if (w.succ()) {
							x.pred(w);
							w.succ(false);
						}
						if (q != null) {
							if (dir)
								q.right = w;
							else
								q.left = w;
						} else
							tree = w;
					} else {
						if (q != null) {
							if (dir)
								q.right = x;
							else
								q.left = x;
						} else
							tree = x;
						if (x.balance() == 0) {
							y.right = x.left;
							x.left = y;
							x.balance(-1);
							y.balance(+1);
							break;
						}
						assert x.balance() == 1;
						if (x.pred()) {
							y.succ(true);
							x.pred(false);
						} else
							y.right = x.left;
						x.left = y;
						y.balance(0);
						x.balance(0);
					}
				}
			} else {
				dir = q != null && q.left != y;
				y.decBalance();
				if (y.balance() == -1)
					break;
				else if (y.balance() == -2) {
					Entry<K> x = y.left;
					assert x != null;
					if (x.balance() == 1) {
						Entry<K> w;
						assert x.balance() == 1;
						w = x.right;
						x.right = w.left;
						w.left = x;
						y.left = w.right;
						w.right = y;
						if (w.balance() == -1) {
							x.balance(0);
							y.balance(1);
						} else if (w.balance() == 0) {
							x.balance(0);
							y.balance(0);
						} else {
							assert w.balance() == 1;
							x.balance(-1);
							y.balance(0);
						}
						w.balance(0);
						if (w.pred()) {
							x.succ(w);
							w.pred(false);
						}
						if (w.succ()) {
							y.pred(w);
							w.succ(false);
						}
						if (q != null) {
							if (dir)
								q.right = w;
							else
								q.left = w;
						} else
							tree = w;
					} else {
						if (q != null) {
							if (dir)
								q.right = x;
							else
								q.left = x;
						} else
							tree = x;
						if (x.balance() == 0) {
							y.left = x.right;
							x.right = y;
							x.balance(+1);
							y.balance(-1);
							break;
						}
						assert x.balance() == -1;
						if (x.succ()) {
							y.pred(true);
							x.succ(false);
						} else
							y.left = x.right;
						x.right = y;
						y.balance(0);
						x.balance(0);
					}
				}
			}
		}
		count--;
		return true;
	}
	@SuppressWarnings("unchecked")
	@Override
	public boolean contains(final Object k) {
		return findKey((K) k) != null;
	}
	@SuppressWarnings("unchecked")
	public K get(final Object k) {
		final Entry<K> entry = findKey((K) k);
		return entry == null ? null : entry.key;
	}
	@Override
	public void clear() {
		count = 0;
		tree = null;
		firstEntry = lastEntry = null;
	}
	
This class represent an entry in a tree set.
 We use the only "metadata", i.e., info, to store information about balance, predecessor status and successor status. 

Note that since the class is recursive, it can be considered equivalently a
tree.
/**
	 * This class represent an entry in a tree set.
	 *
	 * <p>
	 * We use the only "metadata", i.e., {@link Entry#info}, to store information
	 * about balance, predecessor status and successor status.
	 *
	 * <p>
	 * Note that since the class is recursive, it can be considered equivalently a
	 * tree.
	 */
	private static final class Entry<K> implements Cloneable {
		
If the bit in this mask is true, Entry<K>.right points to a successor. /** If the bit in this mask is true, {@link #right} points to a successor. */
		private static final int SUCC_MASK = 1 << 31;
		
If the bit in this mask is true, Entry<K>.left points to a predecessor. /** If the bit in this mask is true, {@link #left} points to a predecessor. */
		private static final int PRED_MASK = 1 << 30;
		
The bits in this mask hold the node balance info. You can get it just by
casting to byte.
/**
		 * The bits in this mask hold the node balance info. You can get it just by
		 * casting to byte.
		 */
		private static final int BALANCE_MASK = 0xFF;
		
The key of this entry. /** The key of this entry. */
		K key;
		
The pointers to the left and right subtrees. /** The pointers to the left and right subtrees. */
		Entry<K> left, right;
		
This integers holds different information in different bits (see Entry<K>.SUCC_MASK, Entry<K>.PRED_MASK and Entry<K>.BALANCE_MASK). /**
		 * This integers holds different information in different bits (see
		 * {@link #SUCC_MASK}, {@link #PRED_MASK} and {@link #BALANCE_MASK}).
		 */
		int info;
		Entry() {
		}
		
Creates a new entry with the given key.
Params:
k – 
           a key./**
		 * Creates a new entry with the given key.
		 *
		 * @param k
		 *            a key.
		 */
		Entry(final K k) {
			this.key = k;
			info = SUCC_MASK | PRED_MASK;
		}
		
Returns the left subtree.
Returns:
the left subtree (null if the left subtree is empty)./**
		 * Returns the left subtree.
		 *
		 * @return the left subtree ({@code null} if the left subtree is empty).
		 */
		Entry<K> left() {
			return (info & PRED_MASK) != 0 ? null : left;
		}
		
Returns the right subtree.
Returns:
the right subtree (null if the right subtree is empty)./**
		 * Returns the right subtree.
		 *
		 * @return the right subtree ({@code null} if the right subtree is empty).
		 */
		Entry<K> right() {
			return (info & SUCC_MASK) != 0 ? null : right;
		}
		
Checks whether the left pointer is really a predecessor.
Returns:
true if the left pointer is a predecessor./**
		 * Checks whether the left pointer is really a predecessor.
		 * 
		 * @return true if the left pointer is a predecessor.
		 */
		boolean pred() {
			return (info & PRED_MASK) != 0;
		}
		
Checks whether the right pointer is really a successor.
Returns:
true if the right pointer is a successor./**
		 * Checks whether the right pointer is really a successor.
		 * 
		 * @return true if the right pointer is a successor.
		 */
		boolean succ() {
			return (info & SUCC_MASK) != 0;
		}
		
Sets whether the left pointer is really a predecessor.
Params:
pred – 
           if true then the left pointer will be considered a predecessor./**
		 * Sets whether the left pointer is really a predecessor.
		 * 
		 * @param pred
		 *            if true then the left pointer will be considered a predecessor.
		 */
		void pred(final boolean pred) {
			if (pred)
				info |= PRED_MASK;
			else
				info &= ~PRED_MASK;
		}
		
Sets whether the right pointer is really a successor.
Params:
succ – 
           if true then the right pointer will be considered a successor./**
		 * Sets whether the right pointer is really a successor.
		 * 
		 * @param succ
		 *            if true then the right pointer will be considered a successor.
		 */
		void succ(final boolean succ) {
			if (succ)
				info |= SUCC_MASK;
			else
				info &= ~SUCC_MASK;
		}
		
Sets the left pointer to a predecessor.
Params:
pred – 
           the predecessr./**
		 * Sets the left pointer to a predecessor.
		 * 
		 * @param pred
		 *            the predecessr.
		 */
		void pred(final Entry<K> pred) {
			info |= PRED_MASK;
			left = pred;
		}
		
Sets the right pointer to a successor.
Params:
succ – 
           the successor./**
		 * Sets the right pointer to a successor.
		 * 
		 * @param succ
		 *            the successor.
		 */
		void succ(final Entry<K> succ) {
			info |= SUCC_MASK;
			right = succ;
		}
		
Sets the left pointer to the given subtree.
Params:
left – 
           the new left subtree./**
		 * Sets the left pointer to the given subtree.
		 * 
		 * @param left
		 *            the new left subtree.
		 */
		void left(final Entry<K> left) {
			info &= ~PRED_MASK;
			this.left = left;
		}
		
Sets the right pointer to the given subtree.
Params:
right – 
           the new right subtree./**
		 * Sets the right pointer to the given subtree.
		 * 
		 * @param right
		 *            the new right subtree.
		 */
		void right(final Entry<K> right) {
			info &= ~SUCC_MASK;
			this.right = right;
		}
		
Returns the current level of the node.
Returns:
the current level of this node./**
		 * Returns the current level of the node.
		 * 
		 * @return the current level of this node.
		 */
		int balance() {
			return (byte) info;
		}
		
Sets the level of this node.
Params:
level – 
           the new level of this node./**
		 * Sets the level of this node.
		 * 
		 * @param level
		 *            the new level of this node.
		 */
		void balance(int level) {
			info &= ~BALANCE_MASK;
			info |= (level & BALANCE_MASK);
		}
		
Increments the level of this node. /** Increments the level of this node. */
		void incBalance() {
			info = info & ~BALANCE_MASK | ((byte) info + 1) & 0xFF;
		}
		
Decrements the level of this node. /** Decrements the level of this node. */
		protected void decBalance() {
			info = info & ~BALANCE_MASK | ((byte) info - 1) & 0xFF;
		}
		
Computes the next entry in the set order.
Returns:
the next entry (null) if this is the last entry)./**
		 * Computes the next entry in the set order.
		 *
		 * @return the next entry ({@code null}) if this is the last entry).
		 */
		Entry<K> next() {
			Entry<K> next = this.right;
			if ((info & SUCC_MASK) == 0)
				while ((next.info & PRED_MASK) == 0)
					next = next.left;
			return next;
		}
		
Computes the previous entry in the set order.
Returns:
the previous entry (null) if this is the first entry)./**
		 * Computes the previous entry in the set order.
		 *
		 * @return the previous entry ({@code null}) if this is the first entry).
		 */
		Entry<K> prev() {
			Entry<K> prev = this.left;
			if ((info & PRED_MASK) == 0)
				while ((prev.info & SUCC_MASK) == 0)
					prev = prev.right;
			return prev;
		}
		@Override
		@SuppressWarnings("unchecked")
		public Entry<K> clone() {
			Entry<K> c;
			try {
				c = (Entry<K>) super.clone();
			} catch (CloneNotSupportedException cantHappen) {
				throw new InternalError();
			}
			c.key = key;
			c.info = info;
			return c;
		}
		public boolean equals(final Object o) {
			if (!(o instanceof Entry))
				return false;
			Entry<?> e = (Entry<?>) o;
			return java.util.Objects.equals(key, e.key);
		}
		public int hashCode() {
			return ((key).hashCode());
		}
		public String toString() {
			return String.valueOf(key);
		}
		/*
		 * public void prettyPrint() { prettyPrint(0); }
		 * 
		 * public void prettyPrint(int level) { if (pred()) { for (int i = 0; i < level;
		 * i++) System.err.print("  "); System.err.println("pred: " + left); } else if
		 * (left != null) left.prettyPrint(level +1); for (int i = 0; i < level; i++)
		 * System.err.print("  "); System.err.println(key + " (" + level() + ")"); if
		 * (succ()) { for (int i = 0; i < level; i++) System.err.print("  ");
		 * System.err.println("succ: " + right); } else if (right != null)
		 * right.prettyPrint(level + 1); }
		 */
	}
	/*
	 * public void prettyPrint() { System.err.println("size: " + count); if (tree !=
	 * null) tree.prettyPrint(); }
	 */
	@Override
	public int size() {
		return count;
	}
	@Override
	public boolean isEmpty() {
		return count == 0;
	}
	@Override
	public K first() {
		if (tree == null)
			throw new NoSuchElementException();
		return firstEntry.key;
	}
	@Override
	public K last() {
		if (tree == null)
			throw new NoSuchElementException();
		return lastEntry.key;
	}
	
An iterator on the whole range.

This class can iterate in both directions on a threaded tree.
/**
	 * An iterator on the whole range.
	 *
	 * <p>
	 * This class can iterate in both directions on a threaded tree.
	 */
	private class SetIterator implements ObjectListIterator<K> {
		
The entry that will be returned by the next call to ListIterator.previous() (or null if no previous entry exists). /**
		 * The entry that will be returned by the next call to
		 * {@link java.util.ListIterator#previous()} (or {@code null} if no previous
		 * entry exists).
		 */
		Entry<K> prev;
		
The entry that will be returned by the next call to ListIterator.next() (or null if no next entry exists). /**
		 * The entry that will be returned by the next call to
		 * {@link java.util.ListIterator#next()} (or {@code null} if no next entry
		 * exists).
		 */
		Entry<K> next;
		
The last entry that was returned (or null if we did not iterate or used remove()). /**
		 * The last entry that was returned (or {@code null} if we did not iterate or
		 * used {@link #remove()}).
		 */
		Entry<K> curr;
		
The current index (in the sense of a ListIterator). Note that this value is not meaningful when this SetIterator has been created using the nonempty constructor. /**
		 * The current index (in the sense of a {@link java.util.ListIterator}). Note
		 * that this value is not meaningful when this {@link SetIterator} has been
		 * created using the nonempty constructor.
		 */
		int index = 0;
		SetIterator() {
			next = firstEntry;
		}
		SetIterator(final K k) {
			if ((next = locateKey(k)) != null) {
				if (compare(next.key, k) <= 0) {
					prev = next;
					next = next.next();
				} else
					prev = next.prev();
			}
		}
		@Override
		public boolean hasNext() {
			return next != null;
		}
		@Override
		public boolean hasPrevious() {
			return prev != null;
		}
		void updateNext() {
			next = next.next();
		}
		Entry<K> nextEntry() {
			if (!hasNext())
				throw new NoSuchElementException();
			curr = prev = next;
			index++;
			updateNext();
			return curr;
		}
		@Override
		public K next() {
			return nextEntry().key;
		}
		@Override
		public K previous() {
			return previousEntry().key;
		}
		void updatePrevious() {
			prev = prev.prev();
		}
		Entry<K> previousEntry() {
			if (!hasPrevious())
				throw new NoSuchElementException();
			curr = next = prev;
			index--;
			updatePrevious();
			return curr;
		}
		@Override
		public int nextIndex() {
			return index;
		}
		@Override
		public int previousIndex() {
			return index - 1;
		}
		@Override
		public void remove() {
			if (curr == null)
				throw new IllegalStateException();
			/*
			 * If the last operation was a next(), we are removing an entry that preceeds
			 * the current index, and thus we must decrement it.
			 */
			if (curr == prev)
				index--;
			next = prev = curr;
			updatePrevious();
			updateNext();
			ObjectAVLTreeSet.this.remove(curr.key);
			curr = null;
		}
	}
	@Override
	public ObjectBidirectionalIterator<K> iterator() {
		return new SetIterator();
	}
	@Override
	public ObjectBidirectionalIterator<K> iterator(final K from) {
		return new SetIterator(from);
	}
	@Override
	public Comparator<? super K> comparator() {
		return actualComparator;
	}
	@Override
	public ObjectSortedSet<K> headSet(final K to) {
		return new Subset((null), true, to, false);
	}
	@Override
	public ObjectSortedSet<K> tailSet(final K from) {
		return new Subset(from, false, (null), true);
	}
	@Override
	public ObjectSortedSet<K> subSet(final K from, final K to) {
		return new Subset(from, false, to, false);
	}
	
A subset with given range.
 This class represents a subset. One has to specify the left/right limits (which can be set to -∞ or ∞). Since the subset is a view on the set, at a given moment it could happen that the limits of the range are not any longer in the main set. Thus, things such as SortedSet.first() or Set.size() must be always computed on-the-fly. /**
	 * A subset with given range.
	 *
	 * <p>
	 * This class represents a subset. One has to specify the left/right limits
	 * (which can be set to -&infin; or &infin;). Since the subset is a view on the
	 * set, at a given moment it could happen that the limits of the range are not
	 * any longer in the main set. Thus, things such as
	 * {@link java.util.SortedSet#first()} or {@link java.util.SortedSet#size()}
	 * must be always computed on-the-fly.
	 */
	private final class Subset extends AbstractObjectSortedSet<K> implements java.io.Serializable, ObjectSortedSet<K> {
		private static final long serialVersionUID = -7046029254386353129L;
		
The start of the subset range, unless Subset.bottom is true. /** The start of the subset range, unless {@link #bottom} is true. */
		K from;
		
The end of the subset range, unless Subset.top is true. /** The end of the subset range, unless {@link #top} is true. */
		K to;
		
If true, the subset range starts from -∞. /** If true, the subset range starts from -&infin;. */
		boolean bottom;
		
If true, the subset range goes to ∞. /** If true, the subset range goes to &infin;. */
		boolean top;
		
Creates a new subset with given key range.
Params:
from – 
           the start of the subset range.
bottom – 
           if true, the first parameter is ignored and the range starts from
           -∞.
to – 
           the end of the subset range.
top – 
           if true, the third parameter is ignored and the range goes to
           ∞./**
		 * Creates a new subset with given key range.
		 *
		 * @param from
		 *            the start of the subset range.
		 * @param bottom
		 *            if true, the first parameter is ignored and the range starts from
		 *            -&infin;.
		 * @param to
		 *            the end of the subset range.
		 * @param top
		 *            if true, the third parameter is ignored and the range goes to
		 *            &infin;.
		 */
		public Subset(final K from, final boolean bottom, final K to, final boolean top) {
			if (!bottom && !top && ObjectAVLTreeSet.this.compare(from, to) > 0)
				throw new IllegalArgumentException(
						"Start element (" + from + ") is larger than end element (" + to + ")");
			this.from = from;
			this.bottom = bottom;
			this.to = to;
			this.top = top;
		}
		@Override
		public void clear() {
			final SubsetIterator i = new SubsetIterator();
			while (i.hasNext()) {
				i.next();
				i.remove();
			}
		}
		
Checks whether a key is in the subset range.
Params:
k – 
           a key.
Returns:
true if is the key is in the subset range./**
		 * Checks whether a key is in the subset range.
		 * 
		 * @param k
		 *            a key.
		 * @return true if is the key is in the subset range.
		 */
		final boolean in(final K k) {
			return (bottom || ObjectAVLTreeSet.this.compare(k, from) >= 0)
					&& (top || ObjectAVLTreeSet.this.compare(k, to) < 0);
		}
		@SuppressWarnings("unchecked")
		@Override
		public boolean contains(final Object k) {
			return in((K) k) && ObjectAVLTreeSet.this.contains(k);
		}
		@Override
		public boolean add(final K k) {
			if (!in(k))
				throw new IllegalArgumentException("Element (" + k + ") out of range ["
						+ (bottom ? "-" : String.valueOf(from)) + ", " + (top ? "-" : String.valueOf(to)) + ")");
			return ObjectAVLTreeSet.this.add(k);
		}
		@SuppressWarnings("unchecked")
		@Override
		public boolean remove(final Object k) {
			if (!in((K) k))
				return false;
			return ObjectAVLTreeSet.this.remove(k);
		}
		@Override
		public int size() {
			final SubsetIterator i = new SubsetIterator();
			int n = 0;
			while (i.hasNext()) {
				n++;
				i.next();
			}
			return n;
		}
		@Override
		public boolean isEmpty() {
			return !new SubsetIterator().hasNext();
		}
		@Override
		public Comparator<? super K> comparator() {
			return actualComparator;
		}
		@Override
		public ObjectBidirectionalIterator<K> iterator() {
			return new SubsetIterator();
		}
		@Override
		public ObjectBidirectionalIterator<K> iterator(final K from) {
			return new SubsetIterator(from);
		}
		@Override
		public ObjectSortedSet<K> headSet(final K to) {
			if (top)
				return new Subset(from, bottom, to, false);
			return compare(to, this.to) < 0 ? new Subset(from, bottom, to, false) : this;
		}
		@Override
		public ObjectSortedSet<K> tailSet(final K from) {
			if (bottom)
				return new Subset(from, false, to, top);
			return compare(from, this.from) > 0 ? new Subset(from, false, to, top) : this;
		}
		@Override
		public ObjectSortedSet<K> subSet(K from, K to) {
			if (top && bottom)
				return new Subset(from, false, to, false);
			if (!top)
				to = compare(to, this.to) < 0 ? to : this.to;
			if (!bottom)
				from = compare(from, this.from) > 0 ? from : this.from;
			if (!top && !bottom && from == this.from && to == this.to)
				return this;
			return new Subset(from, false, to, false);
		}
		
Locates the first entry.
Returns:
the first entry of this subset, or null if the subset is empty./**
		 * Locates the first entry.
		 *
		 * @return the first entry of this subset, or {@code null} if the subset is
		 *         empty.
		 */
		public ObjectAVLTreeSet.Entry<K> firstEntry() {
			if (tree == null)
				return null;
			// If this subset goes to -infinity, we return the main set first entry;
			// otherwise, we locate the start of the set.
			ObjectAVLTreeSet.Entry<K> e;
			if (bottom)
				e = firstEntry;
			else {
				e = locateKey(from);
				// If we find either the start or something greater we're OK.
				if (compare(e.key, from) < 0)
					e = e.next();
			}
			// Finally, if this subset doesn't go to infinity, we check that the resulting
			// key isn't greater than the end.
			if (e == null || !top && compare(e.key, to) >= 0)
				return null;
			return e;
		}
		
Locates the last entry.
Returns:
the last entry of this subset, or null if the subset is empty./**
		 * Locates the last entry.
		 *
		 * @return the last entry of this subset, or {@code null} if the subset is
		 *         empty.
		 */
		public ObjectAVLTreeSet.Entry<K> lastEntry() {
			if (tree == null)
				return null;
			// If this subset goes to infinity, we return the main set last entry;
			// otherwise, we locate the end of the set.
			ObjectAVLTreeSet.Entry<K> e;
			if (top)
				e = lastEntry;
			else {
				e = locateKey(to);
				// If we find something smaller than the end we're OK.
				if (compare(e.key, to) >= 0)
					e = e.prev();
			}
			// Finally, if this subset doesn't go to -infinity, we check that the resulting
			// key isn't smaller than the start.
			if (e == null || !bottom && compare(e.key, from) < 0)
				return null;
			return e;
		}
		@Override
		public K first() {
			ObjectAVLTreeSet.Entry<K> e = firstEntry();
			if (e == null)
				throw new NoSuchElementException();
			return e.key;
		}
		@Override
		public K last() {
			ObjectAVLTreeSet.Entry<K> e = lastEntry();
			if (e == null)
				throw new NoSuchElementException();
			return e.key;
		}
		
An iterator for subranges.
 This class inherits from SetIterator, but overrides the methods that update the pointer after a ListIterator.next() or ListIterator.previous(). If we would move out of the range of the subset we just overwrite the next or previous entry with null. /**
		 * An iterator for subranges.
		 *
		 * <p>
		 * This class inherits from {@link SetIterator}, but overrides the methods that
		 * update the pointer after a {@link java.util.ListIterator#next()} or
		 * {@link java.util.ListIterator#previous()}. If we would move out of the range
		 * of the subset we just overwrite the next or previous entry with {@code null}.
		 */
		private final class SubsetIterator extends SetIterator {
			SubsetIterator() {
				next = firstEntry();
			}
			SubsetIterator(final K k) {
				this();
				if (next != null) {
					if (!bottom && compare(k, next.key) < 0)
						prev = null;
					else if (!top && compare(k, (prev = lastEntry()).key) >= 0)
						next = null;
					else {
						next = locateKey(k);
						if (compare(next.key, k) <= 0) {
							prev = next;
							next = next.next();
						} else
							prev = next.prev();
					}
				}
			}
			@Override
			void updatePrevious() {
				prev = prev.prev();
				if (!bottom && prev != null && ObjectAVLTreeSet.this.compare(prev.key, from) < 0)
					prev = null;
			}
			@Override
			void updateNext() {
				next = next.next();
				if (!top && next != null && ObjectAVLTreeSet.this.compare(next.key, to) >= 0)
					next = null;
			}
		}
	}
	
Returns a deep copy of this tree set.

This method performs a deep copy of this tree set; the data stored in the
set, however, is not cloned. Note that this makes a difference only for
object keys.
Returns:
a deep copy of this tree set./**
	 * Returns a deep copy of this tree set.
	 *
	 * <p>
	 * This method performs a deep copy of this tree set; the data stored in the
	 * set, however, is not cloned. Note that this makes a difference only for
	 * object keys.
	 *
	 * @return a deep copy of this tree set.
	 */
	@Override
	@SuppressWarnings("unchecked")
	public Object clone() {
		ObjectAVLTreeSet<K> c;
		try {
			c = (ObjectAVLTreeSet<K>) super.clone();
		} catch (CloneNotSupportedException cantHappen) {
			throw new InternalError();
		}
		c.allocatePaths();
		if (count != 0) {
			// Also this apparently unfathomable code is derived from GNU libavl.
			Entry<K> e, p, q, rp = new Entry<>(), rq = new Entry<>();
			p = rp;
			rp.left(tree);
			q = rq;
			rq.pred(null);
			while (true) {
				if (!p.pred()) {
					e = p.left.clone();
					e.pred(q.left);
					e.succ(q);
					q.left(e);
					p = p.left;
					q = q.left;
				} else {
					while (p.succ()) {
						p = p.right;
						if (p == null) {
							q.right = null;
							c.tree = rq.left;
							c.firstEntry = c.tree;
							while (c.firstEntry.left != null)
								c.firstEntry = c.firstEntry.left;
							c.lastEntry = c.tree;
							while (c.lastEntry.right != null)
								c.lastEntry = c.lastEntry.right;
							return c;
						}
						q = q.right;
					}
					p = p.right;
					q = q.right;
				}
				if (!p.succ()) {
					e = p.right.clone();
					e.succ(q.right);
					e.pred(q);
					q.right(e);
				}
			}
		}
		return c;
	}
	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		int n = count;
		SetIterator i = new SetIterator();
		s.defaultWriteObject();
		while (n-- != 0)
			s.writeObject(i.next());
	}
	
Reads the given number of entries from the input stream, returning the
corresponding tree.
Params:
s – 
           the input stream.
n – 
           the (positive) number of entries to read.
pred – 
           the entry containing the key that preceeds the first key in the
           tree.
succ – 
           the entry containing the key that follows the last key in the
           tree./**
	 * Reads the given number of entries from the input stream, returning the
	 * corresponding tree.
	 *
	 * @param s
	 *            the input stream.
	 * @param n
	 *            the (positive) number of entries to read.
	 * @param pred
	 *            the entry containing the key that preceeds the first key in the
	 *            tree.
	 * @param succ
	 *            the entry containing the key that follows the last key in the
	 *            tree.
	 */
	@SuppressWarnings("unchecked")
	private Entry<K> readTree(final java.io.ObjectInputStream s, final int n, final Entry<K> pred, final Entry<K> succ)
			throws java.io.IOException, ClassNotFoundException {
		if (n == 1) {
			final Entry<K> top = new Entry<>((K) s.readObject());
			top.pred(pred);
			top.succ(succ);
			return top;
		}
		if (n == 2) {
			/*
			 * We handle separately this case so that recursion will always* be on nonempty
			 * subtrees.
			 */
			final Entry<K> top = new Entry<>((K) s.readObject());
			top.right(new Entry<>((K) s.readObject()));
			top.right.pred(top);
			top.balance(1);
			top.pred(pred);
			top.right.succ(succ);
			return top;
		}
		// The right subtree is the largest one.
		final int rightN = n / 2, leftN = n - rightN - 1;
		final Entry<K> top = new Entry<>();
		top.left(readTree(s, leftN, pred, top));
		top.key = (K) s.readObject();
		top.right(readTree(s, rightN, top, succ));
		if (n == (n & -n))
			top.balance(1); // Quick test for determining whether n is a power of 2.
		return top;
	}
	private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();
		/*
		 * The storedComparator is now correctly set, but we must restore on-the-fly the
		 * actualComparator.
		 */
		setActualComparator();
		allocatePaths();
		if (count != 0) {
			tree = readTree(s, count, null, null);
			Entry<K> e;
			e = tree;
			while (e.left() != null)
				e = e.left();
			firstEntry = e;
			e = tree;
			while (e.right() != null)
				e = e.right();
			lastEntry = e;
		}
	}
}