private void addIntermediateNode ( Node < V > original , int numOverlappingCharacters , String key , int indexOfStartOfOverlap , V value ) { // get the current prefix for the node char [ ] originalPrefix = original . prefix ; // create the new prefix for the original node, which will be all the // non-overlapping characters. Note that the first distinguish // character will be used as the map, so the prefix is shorter. char distinguishing = originalPrefix [ numOverlappingCharacters ] ; char [ ] remainingPrefix = Arrays . copyOfRange ( originalPrefix , numOverlappingCharacters + 1 , originalPrefix . length ) ; char [ ] overlappingPrefix = Arrays . copyOfRange ( originalPrefix , 0 , numOverlappingCharacters ) ; // Create a new Node, which will be a copy of the original node with // the remaining prefix. This new Node will become a child once the // new key-value mapping is put in place Node < V > child = new Node < V > ( remainingPrefix , original . value ) ; // copy over the children as well child . children = original . children ; // original . prefix = overlappingPrefix ; original . children = new CharMap < Node < V > > ( ) ; original . addChild ( distinguishing , child ) ; // Determine whether the remaining portion of the key was a substring of // the original prefix, or whether the two keys diverge but shared a // common, overlapping prefix int remainingKeyChars = key . length ( ) - indexOfStartOfOverlap ; // if the key was a substring, rework the original node to have the new // value and shorter prefix consisting of the overlapping characters if ( numOverlappingCharacters == remainingKeyChars ) { original . value = value ; } // Otherwise, the keys diverge, so create a new intermediate node with // no value mapping but that points to both the old original node and // a new node that contains the new value else { int prefixStart = indexOfStartOfOverlap + numOverlappingCharacters + 1 ; char mappingKey = key . charAt ( indexOfStartOfOverlap + numOverlappingCharacters ) ; char [ ] remainingKey = new char [ key . length ( ) - prefixStart ] ; for ( int i = 0 ; i < remainingKey . length ; ++ i ) { remainingKey [ i ] = key . charAt ( prefixStart + i ) ; } Node < V > newMapping = new Node < V > ( remainingKey , value ) ; original . addChild ( mappingKey , newMapping ) ; original . value = null ; } }
Creates a series of children under the provided node moving the value that was mapped to this node to the appropriate terminal node in the series and finally creating a new node at the end to hold the new key - value mapping .