Find the insert point in the left half of the node for a new key.

@param new1  New Object to be inserted
@param point Found insertion point
431470
void findInsertPointInLeft(
    Object           new1,
    NodeInsertPoint  point)
  {
    int endp = endPoint();
    findIndex(0, endp, new1, point);
  }
766754
private void addPoint(int pos, int flag)
    {
        Point point = new Point();

        int len = insertPoints.points.length;
        if (len == 0) {
            insertPoints.points = new Point[FIRSTALLOC];
            len = FIRSTALLOC;
        }
        if (insertPoints.size >= len) { /* no room for new point */
            Point[] savePoints = insertPoints.points;
            insertPoints.points = new Point[len * 2];
            System.arraycopy(savePoints, 0, insertPoints.points, 0, len);
        }
        point.pos = pos;
        point.flag = flag;
        insertPoints.points[insertPoints.size] = point;
        insertPoints.size++;
    }
1090979
private void leftDeleteNoPredecessor(
                                        GBSNode           p,
                                        Object            deleteKey,
                                        DeleteNode        point)
    {
        int idx = p.findDeleteInLeft(deleteKey);
        if (idx >= 0)
            point.setDelete(p, idx);
    }
1171722
public static IntPoint Add(IntPoint point1, IntPoint point2) {
        IntPoint result = new IntPoint(point1);
        result.Add(point2);
        return result;
    }
495960
public void addPoint(double x, double y)
    {
        if (npoints >= xpoints.length)
        {
            final int newLength = npoints * 2;
            xpoints = Arrays.copyOf(xpoints, newLength);
            ypoints = Arrays.copyOf(ypoints, newLength);
        }
        xpoints[npoints] = x;
        ypoints[npoints] = y;
        npoints++;
        updateBounds();
    }
432701
private void insertNode(PatriciaNode<V> node) {
        PatriciaNode<V> current = root.getLeft();
        PatriciaNode<V> parent = root;

        while (parent.getBit() < current.getBit() && current.getBit() < node.getBit()) {
            parent = current;
            if (!keyMapper.isSet(current.getBit(), node.getKey())) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        }

        if (!keyMapper.isSet(node.getBit(), node.getKey())) {
            node.setLeft(node);
            node.setRight(current);
        } else {
            node.setLeft(current);
            node.setRight(node);
        }

        if (!keyMapper.isSet(parent.getBit(), node.getKey())) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
    }
1151339
public Point createPoint(Coordinate coordinate) {
		if (coordinate == null) {
			return new Point(srid, precision);
		}
		return new Point(srid, precision, coordinate.getX(), coordinate.getY());
	}
993381
void setNewNodes() {

        int index = tTable.getIndexCount();

        nPrimaryNode = new NodeAVLMemoryPointer(this);

        NodeAVL n = nPrimaryNode;

        for (int i = 1; i < index; i++) {
            n.nNext = new NodeAVLMemoryPointer(this);
            n       = n.nNext;
        }
    }
962300
protected final void insertNewContent() throws TTException {
        try {
            Stack<Long> leftSiblingKeyStack = new Stack<Long>();

            leftSiblingKeyStack.push(NULL_NODE);
            boolean firstElement = true;
            int level = 0;
            QName rootElement = null;
            boolean endElemReached = false;
            StringBuilder sBuilder = new StringBuilder();

            // Iterate over all nodes.
            while (mReader.hasNext() && !endElemReached) {
                final XMLEvent event = mReader.nextEvent();

                switch (event.getEventType()) {
                case XMLStreamConstants.START_ELEMENT:
                    level++;
                    leftSiblingKeyStack = addNewElement(leftSiblingKeyStack, (StartElement)event);
                    if (firstElement) {
                        firstElement = false;
                        rootElement = event.asStartElement().getName();
                    }
                    break;
                case XMLStreamConstants.END_ELEMENT:
                    level--;
                    if (level == 0 && rootElement != null
                        && rootElement.equals(event.asEndElement().getName())) {
                        endElemReached = true;
                    }
                    leftSiblingKeyStack.pop();
                    mWtx.moveTo(leftSiblingKeyStack.peek());
                    break;
                case XMLStreamConstants.CHARACTERS:
                    if (mReader.peek().getEventType() == XMLStreamConstants.CHARACTERS) {
                        sBuilder.append(event.asCharacters().getData().trim());
                    } else {
                        sBuilder.append(event.asCharacters().getData().trim());
                        leftSiblingKeyStack = addNewText(leftSiblingKeyStack, sBuilder.toString());
                        sBuilder = new StringBuilder();
                    }
                    break;
                default:
                    // Node kind not known.
                }
            }
        } catch (final XMLStreamException e) {
            throw new TTIOException(e);
        }
    }
691160
private char insert(char p, char[] key, int start, char val) {
        int len = strlen(key, start);
        if (p == 0) {
            // this means there is no branch, this node will start a new branch.
            // Instead of doing that, we store the key somewhere else and create
            // only one node with a pointer to the key
            p = freenode++;
            eq[p] = val;           // holds data
            length++;
            hi[p] = 0;
            if (len > 0) {
                sc[p] = 0xFFFF;    // indicates branch is compressed
                lo[p] = (char)kv.alloc(len
                                       + 1);    // use 'lo' to hold pointer to key
                strcpy(kv.getArray(), lo[p], key, start);
            } else {
                sc[p] = 0;
                lo[p] = 0;
            }
            return p;
        }

        if (sc[p] == 0xFFFF) {
            // branch is compressed: need to decompress
            // this will generate garbage in the external key array
            // but we can do some garbage collection later
            char pp = freenode++;
            lo[pp] = lo[p];    // previous pointer to key
            eq[pp] = eq[p];    // previous pointer to data
            lo[p] = 0;
            if (len > 0) {
                sc[p] = kv.get(lo[pp]);
                eq[p] = pp;
                lo[pp]++;
                if (kv.get(lo[pp]) == 0) {
                    // key completely decompressed leaving garbage in key array
                    lo[pp] = 0;
                    sc[pp] = 0;
                    hi[pp] = 0;
                } else {
                    // we only got first char of key, rest is still there
                    sc[pp] = 0xFFFF;
                }
            } else {
                // In this case we can save a node by swapping the new node
                // with the compressed node
                sc[pp] = 0xFFFF;
                hi[p] = pp;
                sc[p] = 0;
                eq[p] = val;
                length++;
                return p;
            }
        }
        char s = key[start];
        if (s < sc[p]) {
            lo[p] = insert(lo[p], key, start, val);
        } else if (s == sc[p]) {
            if (s != 0) {
                eq[p] = insert(eq[p], key, start + 1, val);
            } else {
                // key already in tree, overwrite data
                eq[p] = val;
            }
        } else {
            hi[p] = insert(hi[p], key, start, val);
        }
        return p;
    }
627240
def add(self, point):
        

        current = self
        while True:
            check_dimensionality([point], dimensions=current.dimensions)

            # Adding has hit an empty leaf-node, add here
            if current.data is None:
                current.data = point
                return current

            # split on self.axis, recurse either left or right
            if point[current.axis] < current.data[current.axis]:
                if current.left is None:
                    current.left = current.create_subnode(point)
                    return current.left
                else:
                    current = current.left
            else:
                if current.right is None:
                    current.right = current.create_subnode(point)
                    return current.right
                else:
                    current = current.right
1165291
public void addPoint(Point point, boolean moveClusterCenter) {
        if (moveClusterCenter) {
            if (isInverse()) {
                center.getArray().muli(points.size()).subi(point.getArray()).divi(points.size() + 1);
            } else {
                center.getArray().muli(points.size()).addi(point.getArray()).divi(points.size() + 1);
            }
        }

        getPoints().add(point);
    }
899001
void insertPoint(Point p){
		
		//check if there is enough space in the first bucket
		int cursize = this.buckets[0].cursize;	
		if(cursize >= this.maxBucketsize) {
			//printf("Bucket 0 full \n");
			//start spillover process
			int curbucket  = 0;
			int nextbucket = 1;

			//check if the next bucket is empty
			if(this.buckets[nextbucket].cursize == 0){
				//copy the bucket	
				int i;
				for(i=0; i<this.maxBucketsize; i++){
					this.buckets[nextbucket].points[i] = this.buckets[curbucket].points[i].clone();
					//copyPointWithoutInit: we should not copy coordinates? 
				}
				//bucket is now full
				this.buckets[nextbucket].cursize = this.maxBucketsize;
				//first bucket is now empty
				this.buckets[curbucket].cursize = 0;
				cursize = 0;
			} else {
				//printf("Bucket %d full \n",nextbucket);
				//copy bucket to spillover and continue
				int i;
				for(i=0;i<this.maxBucketsize;i++){
					this.buckets[nextbucket].spillover[i] = this.buckets[curbucket].points[i].clone();
					//copyPointWithoutInit: we should not copy coordinates? 
				}
				this.buckets[0].cursize=0;
				cursize = 0;
				curbucket++;
				nextbucket++;
				/*
				as long as the next bucket is full output the coreset to the spillover of the next bucket
				*/
				while(this.buckets[nextbucket].cursize == this.maxBucketsize){
					//printf("Bucket %d full \n",nextbucket);
					this.treeCoreset.unionTreeCoreset(this.maxBucketsize,this.maxBucketsize,
						this.maxBucketsize,p.dimension, 
						this.buckets[curbucket].points,this.buckets[curbucket].spillover,
						this.buckets[nextbucket].spillover, this.clustererRandom);
					//bucket now empty
					this.buckets[curbucket].cursize = 0;
					curbucket++;
					nextbucket++;
				}
				this.treeCoreset.unionTreeCoreset(this.maxBucketsize,this.maxBucketsize,
						this.maxBucketsize,p.dimension, 
						this.buckets[curbucket].points,this.buckets[curbucket].spillover,
						this.buckets[nextbucket].points, this.clustererRandom);
				this.buckets[curbucket].cursize = 0;
				this.buckets[nextbucket].cursize = this.maxBucketsize;
			}
		}
		//insert point into the first bucket
		this.buckets[0].points[cursize] = p.clone();
		//copyPointWithoutInit: we should not copy coordinates? 
		this.buckets[0].cursize++;
	}
197345
def insert_value(self, keys, value):
        
        self.count += 1
        if not self.key:
            self.__value_reverse_mapping[value] = keys
        if len(keys) == 0:
            self.values.append(value)
        else:
            key = keys[0]
            index = bisect.bisect_left(self.children, TreeNode(key, reversed=self.reversed))
            if index == len(self.children) or self.children[index].key != key:
                new_tree_node = TreeNode(key, list(), reversed=self.reversed)
                new_tree_node.child_inserted = self.child_inserted
                new_tree_node.child_removed = self.child_removed
                new_tree_node.tree_node_updated = self.tree_node_updated
                new_tree_node.__set_parent(self)
                self.children.insert(index, new_tree_node)
                if self.child_inserted:
                    self.child_inserted(self, index, new_tree_node)
            child = self.children[index]
            child.insert_value(keys[1:], value)
            if self.tree_node_updated:
                self.tree_node_updated(child)
591562
@Override
	public boolean add(P polyline, double precision, OutputParameter<P> firstNeighbour, OutputParameter<P> secondNeighbour) {
		assert firstNeighbour != null;
		assert secondNeighbour != null;
		final OutputParameter<GISTreeSetNode<P>> insertionNode = new OutputParameter<>();
		GISTreeSetNode<P> node = null;
		if (ComplexInsertionNodeSelector.computeConnectableInsertion(
				getTree(),
				polyline,
				precision,
				insertionNode, firstNeighbour, secondNeighbour)) {
			node = insertionNode.get();
		} else {
			return false;
		}

		return GISTreeSetUtil.addInside(this, node, polyline, this);
	}
1349101
public Node insertBefore(Node newChild, Node refChild) throws DOMException
  {
  	if(null == refChild)
  	{
  		appendChild(newChild);
  		return newChild;
  	}
  	
  	if(newChild == refChild)
  	{
  		// hmm...
  		return newChild;
  	}

    Node node = m_firstChild; 
    Node prev = null;  
    boolean foundit = false;
    
    while (null != node)
    {
    	// If the newChild is already in the tree, it is first removed.
    	if(newChild == node)
    	{
    		if(null != prev)
    			((ElemTemplateElement)prev).m_nextSibling = 
    				(ElemTemplateElement)node.getNextSibling();
    		else
    			m_firstChild = (ElemTemplateElement)node.getNextSibling();
    		node = node.getNextSibling();
    		continue; // prev remains the same.
    	}
    	if(refChild == node)
    	{
    		if(null != prev)
    		{
    			((ElemTemplateElement)prev).m_nextSibling = (ElemTemplateElement)newChild;
    		}
    		else
    		{
    			m_firstChild = (ElemTemplateElement)newChild;
    		}
    		((ElemTemplateElement)newChild).m_nextSibling = (ElemTemplateElement)refChild;
    		((ElemTemplateElement)newChild).setParentElem(this);
    		prev = newChild;
    		node = node.getNextSibling();
    		foundit = true;
    		continue;
    	}
    	prev = node;
    	node = node.getNextSibling();
    }
    
    if(!foundit)
    	throw new DOMException(DOMException.NOT_FOUND_ERR, 
    		"refChild was not found in insertBefore method!");
    else
    	return newChild;
  }
827657
@SuppressWarnings("unchecked")
    private void comparableDecreaseKey(Node<K, V> n, K newKey) {
        int c = ((Comparable<? super K>) newKey).compareTo(n.key);
        if (c > 0) {
            throw new IllegalArgumentException("Keys can only be decreased!");
        }
        n.key = newKey;
        if (c == 0) {
            return;
        }

        if (n.next == null) {
            throw new IllegalArgumentException("Invalid handle!");
        }

        // if not root and heap order violation
        Node<K, V> y = n.parent;
        if (y != null && ((Comparable<? super K>) n.key).compareTo(y.key) < 0) {
            cut(n, y);
            root.mark = false;
            cascadingRankChange(y);
            if (((Comparable<? super K>) n.key).compareTo(root.key) < 0) {
                root = link(root, n);
            } else {
                link(n, root);
            }
        }
    }