////////////////////////////////////////////////////////////////////////////////
   // MillScript-Util: an Open Spice interpreter and batch website creation tool
   // Copyright (C) 2005 Open World Ltd, Kevin Rogers
   //
   // This file is part of MillScript-Util.
   //
   // MillScript-Util is free software; you can redistribute it and/or modify it under
   // the terms of the GNU General Public License as published by the Free
   // Software Foundation; either version 2 of the License, or (at your option)
  // any later version.
  //
  // MillScript-Util is distributed in the hope that it will be useful, but WITHOUT
  // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  // more details.
  //
  // You should have received a copy of the GNU General Public License along with
  // MillScript-Util; if not, write to the Free Software Foundation, Inc., 59 Temple
  // Place, Suite 330, Boston, MA  02111-1307  USA
  ////////////////////////////////////////////////////////////////////////////////
  package org.millscript.commons.util.map;
  
  import java.io.IOException;
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
  import java.io.Serializable;
  
  import org.millscript.commons.alert.alerts.Fault;
  import org.millscript.commons.util.IList;
  import org.millscript.commons.util.IMap;
  import org.millscript.commons.util.ListIterator;
  import org.millscript.commons.util.MapIterator;
  import org.millscript.commons.util.Maplet;
  import org.millscript.commons.util.alerts.ListIndexOutOfBoundsAlert;
  import org.millscript.commons.util.alerts.NoSuchKeyInMapAlert;
  import org.millscript.commons.util.iterator.AbstractListIterator;
  import org.millscript.commons.util.iterator.AbstractMapIterator;
  import org.millscript.commons.util.iterator.ArrayListIterator;
  import org.millscript.commons.util.list.AbstractIList;
  import org.millscript.commons.util.list.IArrayList;
  
  /**
   * 
   */
  public class EBinaryTreeMap< K extends Comparable< K >, V > extends AbstractEMap< K, V > implements Cloneable, Serializable {
  
      /**
       * This is the ID from the release 0.1.0 for future compatibility.
       */
      private static final long serialVersionUID = 5434674165103600680L;
  
      public static class Node< K extends Comparable< K >, V > implements Maplet< K, V > {
  
          /**
           * The height of the tree at this point, i.e. the largest numer of
           * child nodes to a leaf. A short allows for a maximum height of 32767
           * nodes(without trying to use the negatives) allowing around 500
           * million entries in the map. 
           */
          private short height;
  
          /**
           * The size of the tree at this point, i.e. the number of nodes
           * including this one and its children.
           */
          int size;
  
          /**
           * The maplet key stored at this node.
           */
          final K key;
  
          /**
           * The left child node.
           */
          Node< K, V > left;
  
          /**
           * The parent node.
           */
          Node< K, V > parent;
  
          /**
           * The right child node.
           */
          Node< K, V > right;
  
          /**
           * The maplet value stored at this node.
           */
          V value;
  
          public Node( final Node< K, V > p, final K k, final V v ) {
              // This new node has no children, so it's height is zero
              this.height = 0;
              this.key = k;
              this.parent = p;
              // This new node has no children, so it's size is one
              this.size = 1;
             this.value = v;
         }
 
         public Node( final Node< K, V > p, final K[] keys, final V[] values, final int first, final int last ) {
             this.parent = p;
             // The index of the central element within the slice is half the
             // length of the array, rounding up. To avoid calling methods we
             // use an integer math version, where we take the length of the
             // array, subtract one, halve, then add one to get the central
             // index. e.g. the variable keys is an array type, so the central
             // index is
             // ( ( keys.length - 1 ) / 2 ) + 1;
             // which gives us the one based index to the central element within
             // the slice, so we skip adding the final one.
             // To get the index into the whole array we must add to the first
             // index and adjust for the one/zero based indexing.
             final int zeroBasedCentralIndex = ( last + first - 1 ) / 2;
             this.key = (K) keys[ zeroBasedCentralIndex ];
             this.value = (V) values[ zeroBasedCentralIndex ];
             // NOTE - Technically we should subtract one from the one-based
             // central index, but as the earlier calculation gives us the zero
             // based index we can use that directly as the index of the last
             // element in the slice of the array for the left branch
             // Are there any elements left on the left?
             if ( zeroBasedCentralIndex >= first ) {
                 // Yes there are...
                 this.left = new Node< K, V >( this, keys, values, first, zeroBasedCentralIndex );
             }
             // NOTE - We add two here as we use a zero based central index, but
             // a one based first/last index
             final int lastRight = zeroBasedCentralIndex + 2;
             // Are there any elements left on the right?
             if ( lastRight <= last ) {
                 // Yes there are...
                 this.right = new Node< K, V >( this, keys, values, lastRight, last );
             }
             // We have to update the size on the way out...
             this.updateSize();
         }
 
         public Node< K, V > deepCopy() {
             final Node< K, V > copy = new Node< K, V >( this.parent, this.key, this.value );
             if ( this.left != null ) {
                 copy.left = this.left.deepCopy();
             }
             if ( this.right != null ) {
                 copy.right = this.right.deepCopy();
             }
             copy.updateSize();
             return copy;
         }
 
         public Node< K, V > getLeftmost() {
             Node< K, V > leftmost = this;
             while ( leftmost.left != null ) {
                 leftmost = leftmost.left;
             }
             return leftmost;
         }
 
         public Node< K, V > getNextInSequence() {
             // Must advance to the next node if available.
             if ( this.right == null ) {
                 if ( this.parent == null ) {
                     // We're at the top of the tree and there's nothing on
                     // the right, so we're done.
                     return null;
                 } else {
                     // Ok, there's nothing to the right so we have to go up
                     // the tree to our parent
                     Node< K, V > nextNode = this.parent;
                     // Check if the current node is the rightmost node of
                     // the branch
                     if ( this == this.parent.right ) {
                         // It is, so go up the tree until we find an
                         // element that is the left child of its parent and
                         // choose that parent.
                         while ( nextNode.parent != null && nextNode == nextNode.parent.right ) {
                             nextNode = nextNode.parent;
                         }
                         nextNode = nextNode.parent;
                     }
                     return nextNode;
                 }
             } else {
                 Node< K, V > nextNode = this.right;
                 while ( nextNode.left != null ) {
                     nextNode = nextNode.left;
                 }
                 return nextNode;
             }
         }
 
         public K getKey() {
             return this.key;
         }
 
         public V getValue() {
             return this.value;
         }
 
         public void insertPushLeft( final EBinaryTreeMap< K, V > map, final K k, final V v ) {
             // 1) Initialise the new node
             final Node< K, V > replacementNode = new Node< K, V >( this.parent, k, v );
             replacementNode.left = this;
             replacementNode.right = this.right;
             // 2) Put the replacement node in place
             if ( this.parent == null ) {
                 map.root = replacementNode;
             } else if ( this == this.parent.left ) {
                 this.parent.left = replacementNode;
             } else {
                 this.parent.right = replacementNode;
             }
             this.parent = replacementNode;
             this.right.parent = replacementNode;
             this.right = null;
             // 3) Update the sizes for this node, the old parent
             // and the new nodes
             this.updateSize();
             // Set the new nodes size
             replacementNode.updateSize();
         }
 
         public void insertPushRight( final EBinaryTreeMap< K, V > map, final K k, final V v ) {
             // 1) Initialise the new node
             final Node< K, V > replacementNode = new Node< K, V >( this.parent, k, v );
             replacementNode.left = this.left;
             replacementNode.right = this;
             // 2) Put the replacement node in place
             if ( this.parent == null ) {
                 map.root = replacementNode;
             } else if ( this == this.parent.left ) {
                 this.parent.left = replacementNode;
             } else {
                 this.parent.right = replacementNode;
             }
             this.parent = replacementNode;
             this.left.parent = replacementNode;
             this.left = null;
             // 3) Update the sizes for this node, the old parent
             // and the new nodes
             this.updateSize();
             // Set the new nodes size
             replacementNode.updateSize();
         }
 
         protected Node< K, V > remove( final EBinaryTreeMap< K, V > map ) {
             if ( this.left == null ) {
                 if ( this.parent == null ) {
                     // Delete this node by moving its right to be the root
                     map.root = this.right;
                 } else if ( this == this.parent.left ) {
                     this.parent.left = this.right;
                 } else {
                     this.parent.right = this.right;
                 }
                 if ( this.right == null ) {
                     return this.parent;
                 } else {
                     this.right.parent = this.parent;
                     return this.right;
                 }
             } else if ( this.right == null ) {
                 // Delete this node by moving its left to be the
                 // root
                 if ( this.parent == null ) {
                     // Delete this node by moving its right to be the root
                     map.root = this.left;
                 } else if ( this == this.parent.left ) {
                     this.parent.left = this.left;
                 } else {
                     this.parent.right = this.left;
                 }
                 if ( this.left == null ) {
                     return this.parent;
                 } else {
                     this.left.parent = this.parent;
                     return this.left;
                 }
             } else if ( Math.random() < 0.5d ) {
                 // Ok there is a left and right, so we've randomly
                 // chosen to move the right
                 // NOTE - At this point the left and right are not null
                 Node< K, V > replacement = this.right;
                 while ( replacement.left != null ) {
                     replacement = replacement.left;
                 }
                 if ( this.parent == null ) {
                     // Delete this node by moving its right to be the root
                     map.root = replacement;
                 } else if ( this == this.parent.left ) {
                     this.parent.left = replacement;
                 } else {
                     this.parent.right = replacement;
                 }
                 if ( replacement == this.right ) {
                     // Ok we will replace this node with our right(which has no
                     // left children)
                     replacement.left = this.left;
                     this.left.parent = replacement;
                     replacement.parent = this.parent;
                 } else {
                     // We will replace this node with the leftmost child of the
                     // right node
                     replacement.left = this.left;
                     this.left.parent = replacement;
                     // The replacement is the left child of its parent
                     replacement.parent.left = replacement.right;
                     if ( replacement.right != null ) {
                         replacement.right.parent = replacement.parent;
                     }
                     Node< K, V > fixsizeFromHere = replacement.parent;
                     replacement.parent = this.parent;
                     replacement.right = this.right;
                     this.right.parent = replacement;
                     for ( ; fixsizeFromHere != null; fixsizeFromHere = fixsizeFromHere.parent ) {
                         fixsizeFromHere.updateSize();
                     }
                 }
                 return replacement;
             } else {
                 // Ok there is a left and right, so we've randomly
                 // chosen to move the left
                 // NOTE - At this point the left and right are not null
                 Node< K, V > replacement = this.left;
                 while ( replacement.right != null ) {
                     replacement = replacement.right;
                 }
                 if ( this.parent == null ) {
                     // Delete this node by moving its right to be the root
                     map.root = replacement;
                 } else if ( this == this.parent.left ) {
                     this.parent.left = replacement;
                 } else {
                     this.parent.right = replacement;
                 }
                 if ( replacement == this.left ) {
                     // Ok we will replace this node with our left(which has no
                     // right children)
                     replacement.right = this.right;
                     this.right.parent = replacement;
                     replacement.parent = this.parent;
                 } else {
                     // We will replace this node with the leftmost child of the
                     // right node
                     replacement.right = this.right;
                     this.right.parent = replacement;
                     // The replacement is the right child of its parent
                     replacement.parent.right = replacement.left;
                     if ( replacement.left != null ) {
                         replacement.left.parent = replacement.parent;
                     }
                     Node< K, V > fixsizeFromHere = replacement.parent;
                     replacement.parent = this.parent;
                     replacement.left = this.left;
                     this.left.parent = replacement;
                     for ( ; fixsizeFromHere != null; fixsizeFromHere = fixsizeFromHere.parent ) {
                         fixsizeFromHere.updateSize();
                     }
                 }
                 return replacement;
             }
         }
 
         public void rotateLeft( final EBinaryTreeMap< K, V > map ) {
             // 1) Set the parent of the right element to our parent
             this.right.parent = this.parent;
             // 2) Update our parent(if there is one) to point to its new child,
             // our right element
             if ( this.parent == null ) {
                 map.root = this.right;
             } else {
                 if ( this == this.parent.left ) {
                     this.parent.left = this.right;
                 } else {
                     this.parent.right = this.right;
                 }
             }
             // 3) Update our parent node so it points to it's new parent
             this.parent = this.right;
             // 4) Store a reference to the node being moved
             final Node< K, V > onTheMove = this.right.left;
             // 5) Move this node to the left child of the (old) right node
             this.right.left = this;
             // 6) Move the left child of the old right node to the right child
             // of this one.
             this.right = onTheMove;
             if ( onTheMove != null ) {
                 onTheMove.parent = this;
             }
             // 7) Update the sizes for this node and the old parent
             this.updateSize();
             this.parent.updateSize();
         }
 
         public void rotateRight( final EBinaryTreeMap< K, V > map ) {
             // 1) Set the parent of the left element to our parent
             this.left.parent = this.parent;
             // 2) Update our parent(if there is one) to point to its new child,
             // our left element
             if ( this.parent == null ) {
                 map.root = this.left;
             } else {
                 if ( this == this.parent.left ) {
                     this.parent.left = this.left;
                 } else {
                     this.parent.right = this.left;
                 }
             }
             // 3) Update our parent node so it points to it's new parent
             this.parent = this.left;
             // 4) Store a reference to the node being moved
             final Node< K, V > onTheMove = this.left.right;
             // 5) Move this node to the right child of the (old) left node
             this.left.right = this;
             // 6) Move the right child of the old left node to the left child
             // of this one.
             this.left = onTheMove;
             if ( onTheMove != null ) {
                 onTheMove.parent = this;
             }
             // 7) Update the sizes for this node and the old parent
             this.updateSize();
             this.parent.updateSize();
         }
 
         protected void updateSize() {
             if ( this.left == null ) {
                 if ( this.right == null ) {
                     this.size = 1;
                 } else {
                     this.size = 1 + this.right.size;
                 }
             } else {
                 if ( this.right == null ) {
                     this.size = 1 + this.left.size;
                 } else {
                     this.size = 1 + this.left.size + this.right.size;
                 }
             }
         }
 
     }
 
     public static class NodeIterator< K extends Comparable< K >, V > extends AbstractMapIterator< K, V > {
 
         /**
          * The current node in the iteration.
          */
         private Node< K, V > currentNode;
 
         /**
          * The next node in the iteration, if this is null 
          */
         private Node< K, V > nextNode;
 
         /**
          * Constructs a new binary tree map iterator to iterate over the specified
          * node tree.
          *
          * @param rootNode  the root node in the tree to iterate over 
          * @param share if <code>true</code> the specified node tree will be
          * shared otherwise the array will be copied.
          */
         public NodeIterator( final Node< K, V > rootNode, final boolean share ) {
             if ( rootNode != null ) {
                 if ( share ) {
                     this.nextNode = rootNode.getLeftmost();
                 } else {
                     this.nextNode = rootNode.deepCopy().getLeftmost();
                 }
             }
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
          */
         @Override
         protected void advance() {
             // Ensure the next node is properly populated
             this.checkNext();
             // Move to the next node
             this.currentNode = this.nextNode;
             this.nextNode = null;
         }
 
         /**
          * Checks that the next maplet field is populated with the next maplet
          * if one is available.
          */
         private void checkNext() {
             if ( this.nextNode == null && this.currentNode != null ) {
                 this.nextNode = this.currentNode.getNextInSequence();
             }
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#getKey()
          */
         @Override
         protected K getKey() {
             return this.currentNode.key;
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#getMaplet()
          */
         @Override
         protected Maplet< K, V > getMaplet() {
             return this.currentNode;
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
          */
         @Override
         protected V getValue() {
             return this.currentNode.value;
         }
 
         /**
          * @see org.millscript.commons.util.MapIterator#hasNext()
          */
         public boolean hasNext() {
             this.checkNext();
             return this.nextNode != null;
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
          */
         @Override
         protected boolean outOfBounds() {
             return this.currentNode == null;
         }
 
     }
 
     public static class NodeKeyIterator< K extends Comparable< K > > extends NodeXIterator< K > {
 
         /**
          * Constructs a new binary tree map iterator to iterate over the specified
          * node tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param num   the number of elements in this iteration
          */
         protected NodeKeyIterator( final Node< ?, ? > node, final int num ) {
             super( node, num );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXIterator#getAppropriateNodePart(org.millscript.commons.util.map.EBinaryTreeMap.Node)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         K getAppropriateNodePart( final Node< ?, ? > node ) {
             return (K) node.getKey();
         }
         
     }
     
     public static class NodeKeyList< K extends Comparable< K > > extends NodeXList< K > {
 
         /**
          * Constructs a new immutable list of the keys in the specified node
          * tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param start the index(one based, inclusive) to start iterating from
          * @param end   the index(one based, inclusive) to stop iterating at
          */
         protected NodeKeyList( final Node< ?, ? > node, final int start, final int end ) {
             super( node, start, end );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#getAppropriateNodePart(org.millscript.commons.util.map.EBinaryTreeMap.Node)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         K getAppropriateNodePart( final Node< ?, ? > node ) {
             return (K) node.getKey();
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#sharedIterator()
          */
         @Override
         public ListIterator< K > sharedIterator() {
             return new NodeKeyIterator< K >(
                 this.firstNode,
                 this.size
             );
         }
         
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#sharedSlice(int, int)
          */
         @Override IList< K > sharedSlice( final int first, final int last ) {
             return new NodeKeyList< K >(
                 this.firstNode,
                 this.firstIndex + first - 1,
                 this.firstIndex + last - 1
             );
         }
         
     }
 
     public static class NodeMapletIterator< K extends Comparable< K >, V > extends NodeXIterator< Maplet< K, V > > {
 
         /**
          * Constructs a new binary tree map iterator to iterate over the specified
          * node tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param num   the number of elements in this iteration
          */
         protected NodeMapletIterator( final Node< ?, ? > node, final int num ) {
             super( node, num );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXIterator#getAppropriateNodePart(org.millscript.commons.util.map.EBinaryTreeMap.Node)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         Maplet< K, V > getAppropriateNodePart( final Node< ?, ? > node ) {
             return (Maplet< K, V >) node;
         }
         
     }
     
     public static class NodeMapletList< K extends Comparable< K >, V > extends NodeXList< Maplet< K, V > > {
 
         /**
          * Constructs a new immutable list of the maplets in the specified node
          * tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param start the index(one based, inclusive) to start iterating from
          * @param end   the index(one based, inclusive) to stop iterating at
          */
         protected NodeMapletList( final Node< ?, ? > node, final int start, final int end ) {
             super( node, start, end );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#getAppropriateNodePart(org.millscript.commons.util.map.EBinaryTreeMap.Node)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         Maplet< K, V > getAppropriateNodePart( final Node< ?, ? > node ) {
             return (Maplet<K, V>) node;
         }
         
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#sharedIterator()
          */
         @Override
         public ListIterator< Maplet< K, V > > sharedIterator() {
             return new NodeMapletIterator< K, V >(
                 this.firstNode,
                 this.size
             );
         }
         
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#sharedSlice(int, int)
          */
         @Override
         IList< Maplet< K, V > > sharedSlice( final int first, final int last ) {
             return new NodeMapletList< K, V >(
                 this.firstNode,
                 this.firstIndex + first - 1,
                 this.firstIndex + last - 1
             );
         }
         
     }
 
     public static class NodeValueIterator< V > extends NodeXIterator< V > {
 
         /**
          * Constructs a new binary tree map iterator to iterate over the specified
          * node tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param num   the number of elements in this iteration
          */
         protected NodeValueIterator( final Node< ?, ? > node, final int num ) {
             super( node, num );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXIterator#getAppropriateNodePart(org.millscript.commons.util.map.EBinaryTreeMap.Node)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         V getAppropriateNodePart( final Node< ?, ? > node ) {
             return (V) node.getValue();
         }
         
     }
     
     public static class NodeValueList< V > extends NodeXList< V > {
 
         /**
          * Constructs a new immutable list of the values in the specified node
          * tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param start the index(one based, inclusive) to start iterating from
          * @param end   the index(one based, inclusive) to stop iterating at
          */
         protected NodeValueList( final Node< ?, ? > node, final int start, final int end ) {
             super( node, start, end );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#getAppropriateNodePart(org.millscript.commons.util.map.EBinaryTreeMap.Node)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         V getAppropriateNodePart( final Node< ?, ? > node ) {
             return (V) node.getValue();
         }
         
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#sharedIterator()
          */
         @Override
         public ListIterator< V > sharedIterator() {
             return new NodeValueIterator< V >(
                 this.firstNode,
                 this.size
             );
         }
 
         /**
          * @see org.millscript.commons.util.map.EBinaryTreeMap.NodeXList#sharedSlice(int, int)
          */
         @Override
         IList< V > sharedSlice( final int first, final int last ) {
             return new NodeValueList< V >(
                 this.firstNode,
                 this.firstIndex + first - 1,
                 this.firstIndex + last - 1
             );
         }
         
     }
 
     public abstract static class NodeXIterator< E > extends AbstractListIterator< E > {
 
         /**
          * The current node in the iteration.
          */
         private Node< ?, ? > currentNode;
 
         /**
          * The next node in the iteration, if this is null 
          */
         private Node< ?, ? > nextNode;
 
         /**
          * The list size.
          */
         private final int size;
 
         /**
          * Constructs a new binary tree map iterator to iterate over the specified
          * node tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param num   the number of elements in this iteration
          */
         protected NodeXIterator( final Node< ?, ? > node, final int num ) {
             if ( num <= 0 ) {
                 this.nextNode = null;
                 this.size = 0;
             } else {
                 this.nextNode = node;
                 this.size = num;
             }
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
          */
         @Override
         protected void advance() {
             // Increment the position
             super.advance();
             this.currentNode = this.nextNode;
             // Check if we've reached the last element in the iteration and
             // ensure the next node is properly populated
             if ( super.position == this.size ) {
                 this.nextNode = null;
             } else if ( this.nextNode != null ) {
                 this.nextNode = this.currentNode.getNextInSequence();
             }
         }
 
         /**
          * Returns the appropriate part of the specified node for this list.
          *
          * @param node  the node to get the appropriate part from
          * @return  the appropriate part of the specified node
          */
         abstract E getAppropriateNodePart( Node< ?, ? > node );
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
          */
         @Override
         protected E getValue() {
             return this.getAppropriateNodePart( this.currentNode );
         }
 
         /**
          * @see org.millscript.commons.util.MapIterator#hasNext()
          */
         public boolean hasNext() {
             return this.nextNode != null;
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
          */
         @Override
         protected boolean outOfBounds() {
             return this.currentNode == null;
         }
 
     }
 
     public abstract static class NodeXList< E > extends AbstractIList< E > {
 
         /**
          * The index of the first element.
          */
         final int firstIndex;
 
         /**
          * The first node in the list.
          */
         final Node< ?, ? > firstNode;
 
         /**
          * The list size.
          */
         final int size;
 
         /**
          * Constructs a new immutable list backed by the specified node tree.
          *
          * @param node  any node in the leftmost branch of the backing store
          * tree
          * @param start the index(one based, inclusive) to start iterating from
          * @param end   the index(one based, inclusive) to stop iterating at
          */
         protected NodeXList( final Node< ?, ? > node, final int start, final int end ) {
             this.firstIndex = start;
             if ( start > end ) {
                 this.firstNode = null;
                 this.size = 0;
             } else if ( end - start + 1 > node.size ) {
                 throw new ListIndexOutOfBoundsAlert(
                     "Requested list exceeds bounds of specified node tree"
                 ).culprit(
                     "first element index",
                     start
                 ).culprit(
                     "last element index",
                     end
                 ).decorate( node ).mishap();
             } else {
                 Node< ?, ? > current = node.getLeftmost();
                 int outerListCount = 1;
                 // Find the first link in the shared chain
                 for ( ; outerListCount < start; outerListCount++ ) {
                     current = current.getNextInSequence();
                 }
                 this.firstNode = current;
                 this.size = end - start + 1;
             }
         }
 
         /**
          * @see org.millscript.commons.util.list.AbstractIList#doGet(int)
          */
         @Override
         protected E doGet( final int pos ) {
             int currentPos = 1;
             for ( Node< ?, ? > current = this.firstNode; current != null; current = current.getNextInSequence() ) {
                 if ( pos == currentPos++ ) {
                     return this.getAppropriateNodePart( current );
                 }
             }
             throw new Fault(
                 "Specified position is neither out of bounds or within the list!"
             ).culprit( "index", pos ).decorate( this ).mishap();
         }
 
         /**
          * @see org.millscript.commons.util.list.AbstractIList#doSlice(int, int, boolean)
          */
         @Override
         @SuppressWarnings( "unchecked" )
         protected IList< E > doSlice( final int first, final int last, final boolean share ) {
             if ( share ) {
                 return this.sharedSlice( first, last );
             } else {
                 // Return a copy of the relevant slice of the list
                 final E[] objects = (E[]) new Object[ first - last + 1 ];
                 Node< ?, ? > current = this.firstNode;
                 int outerListCount = 1;
                 // Find the first link in the shared chain
                 for ( ; outerListCount <= first; outerListCount++ ) {
                     current = current.getNextInSequence();
                 }
                 // Now copy each required link into the array
                 int newArrayPos = 0;
                 for ( ; current != null && outerListCount <= last; current = current.getNextInSequence(), outerListCount++ ) {
                     objects[ newArrayPos++ ] = this.getAppropriateNodePart( current );
                 }
                 return new IArrayList< E >( objects, true );
             }
         }
 
         /**
          * Returns the appropriate part of the specified node for this list.
          *
          * @param node  the node to get the appropriate part from
          * @return  the appropriate part of the specified node
          */
         abstract E getAppropriateNodePart( Node< ?, ? > node );
 
         /**
          * @see org.millscript.commons.util.IList#indexOf(java.lang.Object)
          */
         public int indexOf( final E value ) {
             int currentPos = 1;
             for ( Node< ?, ? > current = this.firstNode; current != null; current = current.getNextInSequence() ) {
                 if ( value == null ? this.getAppropriateNodePart( current ) == null : value.equals( this.getAppropriateNodePart( current ) ) ) {
                     return currentPos;
                 }
             }
             return 0;
         }
 
         /**
          * @see org.millscript.commons.util.IMap#iterator(boolean)
          */
         @SuppressWarnings( "unchecked" )
         public ListIterator< E > iterator( final boolean share ) {
             if ( share ) {
                 return this.sharedIterator();
             } else {
                 final E[] objects = (E[]) new Object[ this.size() ];
                 Node< ?, ? > current = this.firstNode;
                 for ( int i = 0; current != null; i++, current = current.getNextInSequence() ) {
                     objects[ i ] = this.getAppropriateNodePart( current );
                 }
                 return new ArrayListIterator< E >( objects, true );
             }
         }
 
         /**
          * Returns a list iterator which shares backing store with this list.
          *
          * @return  a list iterator which shares this lists backing store
          */
         abstract ListIterator< E > sharedIterator();
 
         /**
          * Returns a slice of this list which shares backing store with this
          * list.
          *
          * @param first the index(one based) of the first element in the slice
          * @param last  the index(one based) of the last element in the slice
          * @return  a slice of this list which shares this lists backing store
          */
         abstract IList< E > sharedSlice( int first, int last );
 
         /**
          * @see org.millscript.commons.util.IMap#size()
          */
         public int size() {
             return this.size;
         }
         
     }
 
     // FIXME - The should ideally be private
     /**
      * The root node in the tree.
      */
     transient Node< K, V > root;
 
     /**
      * Constructs a new, emtpy extensible scapegoat tree map.
      */
     public EBinaryTreeMap() {
     }
 
     /**
      * Constructs a new extensible scapegoat tree map which contains all the
      * mappings from the specified map.
      *
      * @param map   the <code>Map</code> to copy mappings from
      */
     public EBinaryTreeMap( final IMap< K, V > map ) {
         if ( map.size() != 0 ) {
             final MapIterator< K, V > it = map.iterator( true );
             while ( it.hasNext() ) {
                 this.insert( it.nextKey(), it.currentValue() );
             }
         }
     }
 
     /**
      * @see java.lang.Object#clone()
      */
     @Override
     @SuppressWarnings( "unchecked" )
     public Object clone() throws CloneNotSupportedException {
         final EBinaryTreeMap< K, V > map = (EBinaryTreeMap< K, V >) super.clone();
         map.root = this.root.deepCopy();
         return map;
     }
 
     protected int compare( final K a, final K b ) {
         // NOTE - This null handling should ensure that null is pushed as
         // far to one side as possible, but doesn't cause an exception
         if ( a == null ) {
             if ( b == null ) {
                 return 0;
             } else {
                 return Integer.MAX_VALUE;
             }
         } else {
             if ( b == null ) {
                 return Integer.MIN_VALUE;
             }
         }
         final Class ca = a.getClass();
         final Class cb = b.getClass();
         if ( ca == cb ) {
             // Ok, a and b are the same type and comparable so use that to
             // handle the comparison
             return a.compareTo( b );
         } else {
             // a and b are different types, so use the class names to order
             // them. This will result in objects of the same class being
             // grouped together, while ordering within a type is handled by
             // either the Comparable interface(if implemented) or the types
             // hashCode implementation
             return ca.getName().compareTo( cb.getName() );
         }
     }
 
     /**
      * @see org.millscript.commons.util.IMap#contains(java.lang.Object, java.lang.Object)
      */
     public boolean contains( final K key, final V value ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches
                     return value == null ? current.value == null
                                          : value.equals( current.value );
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     current = current.left;
                 } else {
                     // We need to search down the right branch
                     current = current.right;
                 }
             }
         }
         return false;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#containsKey(java.lang.Object)
      */
     public boolean containsKey( final K key ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches
                     return true;
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     current = current.left;
                 } else {
                     // We need to search down the right branch
                     current = current.right;
                 }
             }
         }
         return false;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#containsValue(java.lang.Object)
      */
     public boolean containsValue( final V value ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root.getLeftmost();
             while ( current != null ) {
                 if ( value == null ? current.value == null : value.equals( current.value ) ) {
                     return true;
                 } else {
                     current = current.getNextInSequence();
                 }
             }
         }
         return false;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#get(java.lang.Object)
      */
     public V get( final K key ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches
                     return current.value;
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     current = current.left;
                 } else {
                     // We need to search down the right branch
                     current = current.right;
                 }
             }
         }
         return this.getDefault().get( this, key );
     }
 
     /**
      * @see org.millscript.commons.util.EMap#insert(java.lang.Object, java.lang.Object)
      */
     public void insert( final K key, final V value ) {
         if ( this.root == null ) {
             this.root = new Node< K, V >( null, key, value );
         } else {
             Node< K, V > current = this.root;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches, the insert is handled as a fancy update
                     // NOTE - We don't need to do any post-processing on the tree
                     // as it hasn't changed.
                     current.value = value;
                     break;
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     if ( current.left == null ) {
                         // Add the new node, handling any required tree adjustments
                         // resulting from adding the new node
                         if ( current.parent == null ) {
                             // In general no tree adjustments should be required
                             // when inserting an element at the root, so just add
                             // the new node
                             current.left = new Node< K, V >( current, key, value );
                         } else if ( current == current.parent.left && current.parent.right == null ) {
                             // This node is the left child of its parent and it has
                             // no uncle, add the new node and rotate the tree right
                             // about our parent
                             current.left = new Node< K, V >( current, key, value );
                             current.parent.rotateRight( this );
                         } else if ( current == current.parent.right && current.parent.left == null ) {
                             // The node is the right child of its parent and it has
                             // no uncle. Reorganise the tree putting the new node
                             // in place of our parent
                             current.parent.insertPushLeft( this, key, value );
                         } else {
                             // Just add the new node
                             current.left = new Node< K, V >( current, key, value );
                         }
                         break;
                     } else {
                         current = current.left;
                     }
                 } else {
                     // We need to search down the right branch
                     if ( current.right == null ) {
                         // Add the new node, handling any required tree adjustments
                         // resulting from adding the new node
                         if ( current.parent == null ) {
                             // In general no tree adjustments should be required
                             // when inserting an element at the root, so just add
                             // the new node
                             current.right = new Node< K, V >( current, key, value );
                         } else if ( current == current.parent.right && current.parent.left == null ) {
                             // This node is the right child of its parent and it has
                             // no uncle, add the new node and rotate the tree left
                             // about our parent
                             current.right = new Node< K, V >( current, key, value );
                             current.parent.rotateLeft( this );
                         } else if ( current == current.parent.left && current.parent.right == null ) {
                             // The node is the left child of its parent and it has
                             // no uncle. Reorganise the tree putting the new node
                             // in place of our parent
                             current.parent.insertPushRight( this, key, value );
                         } else {
                             // Just add the new node
                             current.right = new Node< K, V >( current, key, value );
                         }
                         break;
                     } else {
                         current = current.right;
                     }
                 }
             }
             // Update the node size from the current up to the root
             while ( current != null ) {
                 current.updateSize();
                 current = current.parent;
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.IMap#iterator(boolean)
      */
     public MapIterator< K, V > iterator( final boolean share ) {
         return new NodeIterator< K, V >( this.root, share );
     }
 
     /**
      * Reads this object from the specified {@link ObjectInputStream}.
      *
      * @param stream    the {@link ObjectInputStream} to read the objects data
      * from
      * @serialData      Reads the default object, followed by the integer
      * number of mappings and then an alternating sequence of key-value pairs
      * @throws ClassNotFoundException   if a required class cannot be found
      * @throws IOException      if something goes wrong during the
      * deserialization process
      */
     @SuppressWarnings( "unchecked" )
     private void readObject( final ObjectInputStream stream ) throws ClassNotFoundException, IOException {
         // Write the default stuff
         stream.defaultReadObject();
         // Retrieve the number of mappings in the array.
         final int size = stream.readInt();
         // Allocate arrays to temporarily store the mappings in
         final K[] keys = (K[]) new Comparable[ size ];
         final V[] values = (V[]) new Comparable[ size ];
         for ( int i = 0; i < size; i++ ) {
             keys[ i ] = (K) stream.readObject();
             values[ i ] = (V) stream.readObject();
         }
         this.root = new Node< K, V >( null, keys, values, 1, size );
     }
 
     /**
      * @see org.millscript.commons.util.EMap#remove(java.lang.Object, java.lang.Object)
      */
     public void remove( final K key, final V value ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root;
             Node< K, V > parent = null;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches, check the value to see if it matches the
                     // supplied one.
                     if ( value == null ? current.value == null : value.equals( current.value ) ) {
                         // Ok, the node matches completely, delete!
                         current = current.remove( this );
                         break;
                     }
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     parent = current;
                     current = current.left;
                 } else {
                     // We need to search down the right branch
                     parent = current;
                     current = current.right;
                 }
             }
             // Update the node size from the current up to the root
             while ( parent != null ) {
                 parent.updateSize();
                 parent = parent.parent;
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.EMap#removeAll()
      */
     public void removeAll() {
         this.root = null;
     }
 
     /**
      * @see org.millscript.commons.util.EMap#removeKey(java.lang.Object)
      */
     public void removeKey( final K key ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches
                     current = current.remove( this );
                     break;
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     current = current.left;
                 } else {
                     // We need to search down the right branch
                     current = current.right;
                 }
             }
             // Update the node size from the current up to the root
             while ( current != null ) {
                 current.updateSize();
                 current = current.parent;
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.EMap#removeValue(java.lang.Object)
      */
     public void removeValue( final V value ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root.getLeftmost();
             while ( current != null ) {
                 if ( value == null ? current.value == null : value.equals( current.value ) ) {
                     current = current.remove( this );
                     for ( Node fixsize = current; fixsize != null; fixsize = fixsize.parent ) {
                         fixsize.updateSize();
                     }
                 } else {
                     current = current.getNextInSequence();
                 }
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.map.AbstractIMap#sharedKeyList()
      */
     @Override
     protected IList< K > sharedKeyList() {
         return new NodeKeyList< K >( this.root, 1, this.size() );
     }
 
     /**
      * @see org.millscript.commons.util.map.AbstractIMap#sharedMapletList()
      */
     @Override
     protected IList< Maplet< K, V > > sharedMapletList() {
         return new NodeMapletList< K, V >( this.root, 1, this.size() );
     }
 
     /**
      * @see org.millscript.commons.util.map.AbstractIMap#sharedValueList()
      */
     @Override
     protected IList< V > sharedValueList() {
         return new NodeValueList< V >( this.root, 1, this.size() );
     }
 
     /**
      * @see org.millscript.commons.util.IMap#size()
      */
     public int size() {
         return this.root == null ? 0 : this.root.size;
     }
 
     /**
      * @see org.millscript.commons.util.UMap#update(java.lang.Object, java.lang.Object)
      */
     public void update( final K key, final V value ) {
         if ( this.root != null ) {
             Node< K, V > current = this.root;
             while ( current != null ) {
                 final int comp = this.compare( key, current.key );
                 if ( comp == 0 ) {
                     // This node matches
                     current.value = value;
                     return;
                 } else if ( comp < 0 ) {
                     // We need to search down the left branch
                     current = current.left;
                 } else {
                     // We need to search down the right branch
                     current = current.right;
                 }
             }
         }
         throw new NoSuchKeyInMapAlert(
             "Only pre-existing keys can have their values updated"
         ).culpritKey( key ).decorate( this ).mishap();
     }
 
     /**
      * Writes this object to the specified {@link ObjectOutputStream}.
      *
      * @param stream    the {@link ObjectOutputStream} to write this object to
      * @serialData      Writes the default object and then an alternating
      * sequence of key-value pairs
      * @throws IOException      if something goes wrong during the
      * serialization process
      */
     private void writeObject( final ObjectOutputStream stream ) throws IOException {
         // Write the default stuff
         stream.defaultWriteObject();
         // Save the number of mappings in the array.