Adjusts the knn distance in the subtree of the specified root entry.
427976
@Override
  protected void kNNdistanceAdjustment(MkMaxEntry entry, Map<DBID, KNNList> knnLists) {
    MkMaxTreeNode<O> node = getNode(entry);
    double knnDist_node = 0.;
    if (node.isLeaf()) {
      for (int i = 0; i < node.getNumEntries(); i++) {
        MkMaxEntry leafEntry = node.getEntry(i);
        leafEntry.setKnnDistance(knnLists.get(leafEntry.getRoutingObjectID()).getKNNDistance());
        knnDist_node = Math.max(knnDist_node, leafEntry.getKnnDistance());
      }
    } else {
      for (int i = 0; i < node.getNumEntries(); i++) {
        MkMaxEntry dirEntry = node.getEntry(i);
        kNNdistanceAdjustment(dirEntry, knnLists);
        knnDist_node = Math.max(knnDist_node, dirEntry.getKnnDistance());
      }
    }
    entry.setKnnDistance(knnDist_node);
  }
61569
@SuppressWarnings("unchecked")
    private void updateSuffixMin(RootListNode<K, V> t) {
        if (comparator == null) {
            while (t != null) {
                if (t.next == null) {
                    t.suffixMin = t;
                } else {
                    RootListNode<K, V> nextSuffixMin = t.next.suffixMin;
                    if (((Comparable<? super K>) t.root.cKey).compareTo(nextSuffixMin.root.cKey) <= 0) {
                        t.suffixMin = t;
                    } else {
                        t.suffixMin = nextSuffixMin;
                    }
                }
                t = t.prev;
            }
        } else {
            while (t != null) {
                if (t.next == null) {
                    t.suffixMin = t;
                } else {
                    RootListNode<K, V> nextSuffixMin = t.next.suffixMin;
                    if (comparator.compare(t.root.cKey, nextSuffixMin.root.cKey) <= 0) {
                        t.suffixMin = t;
                    } else {
                        t.suffixMin = nextSuffixMin;
                    }
                }
                t = t.prev;
            }
        }
    }
454413
protected void adjustTree(IndexTreePath<E> subtree) {
    final Logging log = getLogger();
    if(log.isDebugging()) {
      log.debugFine("Adjust tree " + subtree);
    }

    // get the root of the subtree
    N node = getNode(subtree.getEntry());

    // overflow in node
    if(hasOverflow(node)) {
      // treatment of overflow: reinsertion or split
      N split = overflowTreatment(node, subtree);

      // node was split
      if(split != null) {
        // if root was split: create a new root that points the two
        // split nodes
        if(isRoot(node)) {
          IndexTreePath<E> newRootPath = createNewRoot(node, split);
          height++;
          adjustTree(newRootPath);
        }
        // node is not root
        else {
          // get the parent and add the new split node
          N parent = getNode(subtree.getParentPath().getEntry());
          if(log.isDebugging()) {
            log.debugFine("parent " + parent);
          }
          parent.addDirectoryEntry(createNewDirectoryEntry(split));

          // adjust the entry representing the (old) node, that has
          // been split

          // This does not work in the persistent version
          // node.adjustEntry(subtree.getEntry());
          node.adjustEntry(parent.getEntry(subtree.getIndex()));

          // write changes in parent to file
          writeNode(parent);
          adjustTree(subtree.getParentPath());
        }
      }
    }
    // no overflow, only adjust parameters of the entry representing the
    // node
    else {
      if(!isRoot(node)) {
        N parent = getNode(subtree.getParentPath().getEntry());
        E entry = parent.getEntry(subtree.getIndex());
        boolean changed = node.adjustEntryIncremental(entry, lastInsertedEntry);
        if(changed) {
          // node.adjustEntry(parent.getEntry(index));
          // write changes in parent to file
          writeNode(parent);
          adjustTree(subtree.getParentPath());
        }
      }
      // root level is reached
      else {
        node.adjustEntry(getRootEntry());
      }
    }
  }
1186655
def preprocess_tree(self, tree):
        """"""
        visitor = RinohTreePreprocessor(tree, self)
        tree.walkabout(visitor)
1264242
private void updateHeap(final double distance, final int iid) {
    final double prevdist = kdist;
    final int previd = heap.peekValue();
    heap.replaceTopElement(distance, iid);
    kdist = heap.peekKey();
    // If the kdist improved, zap ties.
    if(kdist < prevdist) {
      numties = 0;
    }
    else {
      addToTies(previd);
    }
  }
412907
def distanceTo(self, tree):
        '''
        
        '''
        return ViewClient.distance(ViewClient.__pickleable(self.views), tree)
144873
private void secondWalk(TreeNode v, double m, int level, double levelStart) {
		// construct the position from the prelim and the level information

		// The rootLocation affects the way how x and y are changed and in what
		// direction.
		double levelChangeSign = getLevelChangeSign();
		boolean levelChangeOnYAxis = isLevelChangeInYAxis();
		double levelSize = getSizeOfLevel(level);

		double x = getPrelim(v) + m;

		double y;
		AlignmentInLevel alignment = configuration.getAlignmentInLevel();
		if (alignment == AlignmentInLevel.Center) {
			y = levelStart + levelChangeSign * (levelSize / 2);
		} else if (alignment == AlignmentInLevel.TowardsRoot) {
			y = levelStart + levelChangeSign * (getNodeThickness(v) / 2);
		} else {
			y = levelStart + levelSize - levelChangeSign
					* (getNodeThickness(v) / 2);
		}

		if (!levelChangeOnYAxis) {
			double t = x;
			x = y;
			y = t;
		}

		positions.put(v, new NormalizedPosition(x, y));

		// update the bounds
		updateBounds(v, x, y);

		// recurse
		if (!tree.isLeaf(v)) {
			double nextLevelStart = levelStart
					+ (levelSize + configuration.getGapBetweenLevels(level + 1))
					* levelChangeSign;
			for (TreeNode w : tree.getChildren(v)) {
				secondWalk(w, m + getMod(v), level + 1, nextLevelStart);
			}
		}
	}
1280453
private void expandNodes(DeLiCluTree index, SpatialPrimitiveDistanceFunction<V> distFunction, SpatialObjectPair nodePair, DataStore<KNNList> knns) {
    DeLiCluNode node1 = index.getNode(((SpatialDirectoryEntry) nodePair.entry1).getPageID());
    DeLiCluNode node2 = index.getNode(((SpatialDirectoryEntry) nodePair.entry2).getPageID());

    if(node1.isLeaf()) {
      expandLeafNodes(distFunction, node1, node2, knns);
    }
    else {
      expandDirNodes(distFunction, node1, node2);
    }

    index.setExpanded(nodePair.entry2, nodePair.entry1);
  }
813781
private void treeShap(R feat, float[] phi,
                        N node, S nodeStat, int unique_depth,
                        PathPointer parent_unique_path,
                        float parent_zero_fraction,
                        float parent_one_fraction, int parent_feature_index,
                        int condition, int condition_feature,
                        float condition_fraction) {

    // stop if we have no getWeight coming down to us
    if (condition_fraction == 0) return;

    // extend the unique path
    PathPointer unique_path = parent_unique_path.move(unique_depth);

    if (condition == 0 || condition_feature != parent_feature_index) {
      extendPath(unique_path, unique_depth, parent_zero_fraction,
              parent_one_fraction, parent_feature_index);
    }
    final int split_index = node.getSplitIndex();

    // leaf node
    if (node.isLeaf()) {
      for (int i = 1; i <= unique_depth; ++i) {
        final float w = unwoundPathSum(unique_path, unique_depth, i);
        final PathElement el = unique_path.get(i);
        phi[el.feature_index] += w * (el.one_fraction - el.zero_fraction)
                * node.getLeafValue() * condition_fraction;
      }

      // internal node
    } else {
      // find which branch is "hot" (meaning x would follow it)
      final int hot_index = node.next(feat);
      final int cold_index = hot_index == node.getLeftChildIndex() ? node.getRightChildIndex() : node.getLeftChildIndex();
      final float w = nodeStat.getWeight();
      final float hot_zero_fraction = stats[hot_index].getWeight() / w;
      final float cold_zero_fraction = stats[cold_index].getWeight() / w;
      float incoming_zero_fraction = 1;
      float incoming_one_fraction = 1;

      // see if we have already split on this feature,
      // if so we undo that split so we can redo it for this node
      int path_index = 0;
      for (; path_index <= unique_depth; ++path_index) {
        if (unique_path.get(path_index).feature_index == split_index)
          break;
      }
      if (path_index != unique_depth + 1) {
        incoming_zero_fraction = unique_path.get(path_index).zero_fraction;
        incoming_one_fraction = unique_path.get(path_index).one_fraction;
        unwindPath(unique_path, unique_depth, path_index);
        unique_depth -= 1;
      }

      // divide up the condition_fraction among the recursive calls
      float hot_condition_fraction = condition_fraction;
      float cold_condition_fraction = condition_fraction;
      if (condition > 0 && split_index == condition_feature) {
        cold_condition_fraction = 0;
        unique_depth -= 1;
      } else if (condition < 0 && split_index == condition_feature) {
        hot_condition_fraction *= hot_zero_fraction;
        cold_condition_fraction *= cold_zero_fraction;
        unique_depth -= 1;
      }

      treeShap(feat, phi, nodes[hot_index], stats[hot_index], unique_depth + 1, unique_path,
              hot_zero_fraction * incoming_zero_fraction, incoming_one_fraction,
              split_index, condition, condition_feature, hot_condition_fraction);

      treeShap(feat, phi, nodes[cold_index], stats[cold_index], unique_depth + 1, unique_path,
              cold_zero_fraction * incoming_zero_fraction, 0,
              split_index, condition, condition_feature, cold_condition_fraction);
    }
  }
677850
protected void batchNN(AbstractRStarTreeNode<?, ?> node, Map<DBID, KNNHeap> knnLists) {
    if(node.isLeaf()) {
      for(int i = 0; i < node.getNumEntries(); i++) {
        SpatialEntry p = node.getEntry(i);
        for(Entry<DBID, KNNHeap> ent : knnLists.entrySet()) {
          final DBID q = ent.getKey();
          final KNNHeap knns_q = ent.getValue();
          double knn_q_maxDist = knns_q.getKNNDistance();

          DBID pid = ((LeafEntry) p).getDBID();
          // FIXME: objects are NOT accessible by DBID in a plain R-tree
          // context!
          double dist_pq = distanceFunction.distance(relation.get(pid), relation.get(q));
          tree.statistics.countDistanceCalculation();
          if(dist_pq <= knn_q_maxDist) {
            knns_q.insert(dist_pq, pid);
          }
        }
      }
    }
    else {
      ModifiableDBIDs ids = DBIDUtil.newArray(knnLists.size());
      for(DBID id : knnLists.keySet()) {
        ids.add(id);
      }
      List<DoubleDistanceEntry> entries = getSortedEntries(node, ids);
      for(DoubleDistanceEntry distEntry : entries) {
        double minDist = distEntry.distance;
        for(Entry<DBID, KNNHeap> ent : knnLists.entrySet()) {
          final KNNHeap knns_q = ent.getValue();
          double knn_q_maxDist = knns_q.getKNNDistance();

          if(minDist <= knn_q_maxDist) {
            SpatialEntry entry = distEntry.entry;
            AbstractRStarTreeNode<?, ?> child = tree.getNode(((DirectoryEntry) entry).getPageID());
            batchNN(child, knnLists);
            break;
          }
        }
      }
    }
  }
354471
def expand(self, msgpos):
        """"""
        MT = self._tree[msgpos]
        MT.expand(MT.root)
1078803
private void forceDecreaseKeyToMinimum(Node<K, V> n) {
        Node<K, V> y = n.parent;
        if (y != null) {
            cut(n, y);
            root.mark = false;
            cascadingRankChange(y);
            root = link(root, n);
        }
    }
1048144
@Override
  public boolean adjustEntry(MkMaxEntry entry, DBID routingObjectID, double parentDistance, AbstractMTree<O, MkMaxTreeNode<O>, MkMaxEntry, ?> mTree) {
    super.adjustEntry(entry, routingObjectID, parentDistance, mTree);
    // adjust knn distance
    entry.setKnnDistance(kNNDistance());
    return true; // TODO: improve
  }
204025
protected void bicoUpdate(double[] x) {
		assert (!this.bufferPhase && this.numDimensions == x.length);
		// Starts with the global root node as the current root node
		ClusteringTreeNode r = this.root;
		int i = 1;
		while (true) {
			ClusteringTreeNode y = r.nearestChild(x);
			// Checks if the point can not be added to the current level
			if (r.hasNoChildren()
					|| y == null
					|| Metric.distanceSquared(x, y.getCenter()) > calcRSquared(i)) {
				// Creates a new node for the point and adds it to the current
				// root node
				r.addChild(new ClusteringTreeNode(x, new ClusteringFeature(x, calcR(i))));
				this.rootCount++;
				break;
			} else {
				// Checks if the point can be added to the nearest node without
				// exceeding the global threshold
				if (y.getClusteringFeature().calcKMeansCosts(y.getCenter(), x) <= this.T) {
					// Adds the point to the ClusteringFeature
					y.getClusteringFeature().add(1, x, Metric.distanceSquared(x));
					break;
				} else {
					// Navigates one level down in the tree
					r = y;
					i++;
				}
			}
		}
		// Checks if the number of nodes in the tree exceeds the maximum number
		if (this.rootCount > this.maxNumClusterFeatures) {
			rebuild();
		}
	}
1233975
def updateRasterBounds(self):
        """"""
        yrange = self.viewRange()[1]
        yrange_size = yrange[1] - yrange[0]
        rmax = self.rasterTop*yrange_size + yrange[0]
        rmin = self.rasterBottom*yrange_size + yrange[0]
        self.rasterYslots = np.linspace(rmin, rmax, self.nreps)
        self.rasterBoundsUpdated.emit((self.rasterBottom, self.rasterTop), self.getTitle())
913414
private void doBulkReverseKNN(RdKNNNode node, DBIDs ids, Map<DBID, ModifiableDoubleDBIDList> result) {
    if(node.isLeaf()) {
      for(int i = 0; i < node.getNumEntries(); i++) {
        RdKNNLeafEntry entry = (RdKNNLeafEntry) node.getEntry(i);
        for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
          DBID id = DBIDUtil.deref(iter);
          double distance = distanceQuery.distance(entry.getDBID(), id);
          if(distance <= entry.getKnnDistance()) {
            result.get(id).add(distance, entry.getDBID());
          }
        }
      }
    }
    // node is a inner node
    else {
      for(int i = 0; i < node.getNumEntries(); i++) {
        RdKNNDirectoryEntry entry = (RdKNNDirectoryEntry) node.getEntry(i);
        ModifiableDBIDs candidates = DBIDUtil.newArray();
        for(DBIDIter iter = ids.iter(); iter.valid(); iter.advance()) {
          DBID id = DBIDUtil.deref(iter);
          double minDist = distanceQuery.minDist(entry, id);
          if(minDist <= entry.getKnnDistance()) {
            candidates.add(id);
          }
          if(!candidates.isEmpty()) {
            doBulkReverseKNN(getNode(entry), candidates, result);
          }
        }
      }
    }
  }
212450
def add_root(cls, **kwargs):
        """"""

        if len(kwargs) == 1 and 'instance' in kwargs:
            # adding the passed (unsaved) instance to the tree
            newobj = kwargs['instance']
            if newobj.pk:
                raise NodeAlreadySaved("Attempted to add a tree node that is "\
                    "already in the database")
        else:
            newobj = cls(**kwargs)

        newobj._cached_depth = 1
        if not cls.node_order_by:
            try:
                max = get_result_class(cls).objects.filter(
                    parent__isnull=True).order_by(
                    'sib_order').reverse()[0].sib_order
            except IndexError:
                max = 0
            newobj.sib_order = max + 1
        newobj.save()
        return newobj