001/* 002// This software is subject to the terms of the Eclipse Public License v1.0 003// Agreement, available at the following URL: 004// http://www.eclipse.org/legal/epl-v10.html. 005// You must accept the terms of that agreement to use this software. 006// 007// Copyright (C) 2011-2011 Pentaho and others 008// All Rights Reserved. 009*/ 010package mondrian.util; 011 012import java.util.List; 013import java.util.Set; 014 015/** 016 * A SpatialValueTree is a multidimensional index of values. The data is 017 * organized in a fixed number of dimensions, each of which contain a fixed 018 * number of nodes. The node of an axis is called a bound. Each node might 019 * contain X number of values. 020 * 021 * <p>You can think of a SpatialValueTree as a multi dimensional list where 022 * collections of values are stored in each possible tuple. 023 * 024 * <p> 025 * When performing operations on the tree, such as adding values or retrieving 026 * them, we use a {@link SpatialRegion}. Each region can cover more than one 027 * bound per dimension. 028 * 029 * <p>When evaluating a region, if a dimension is omitted form a region, 030 * this means that the region doesn't overlap the dimension at all. It is not 031 * the same as covering all the values of the dimension axis. 032 * 033 * <p> 034 * Example. A tree of years and states containing a X values per leaf node would 035 * look something like this: 036 * 037 * <p> 038 * year:1997<br /> 039 * state:NY<br /> 040 * value:0x000423<br /> 041 * state:FL<br /> 042 * value:0x000236<br /> 043 * value:0x000423<br /> 044 * year:1998<br /> 045 * state:NY<br /> 046 * value:[EMPTY]<br /> 047 * state:FL<br /> 048 * value:0x000501<br /> 049 * 050 * <p> 051 * A region key consists of a list of dimensions included in the region along 052 * with an array of bounds for each of these dimensions. The boundaries of a 053 * given region along a given dimension axis is specified by an array of 054 * objects. All of these objects must be nodes of the specified dimension for a 055 * region to be valid within a tree context. As an example, the following key: 056 * 057 * <p> 058 * <code>[ {'year', [1997]}, {'state', ['FL']} ]</code> 059 * 060 * <p> 061 * ... would return { [0x000236] [0x000423] }. 062 * 063 *<p> 064 * The region keys can have more than one predicate value per axis. If we use 065 * the same tree as above, and we query it using the following region key: 066 * 067 * <p> 068 * <code>[ {'year', [1997]}, {'state', ['NY','FL']} ] 069 * 070 * <p> 071 * ... would return { [0x000236] [0x000423] }. 072 * 073 * <p> 074 * The region key also supports wildcard values. If you want to represent 075 * all of the values of a given axis, you can put a single reference to 076 * SpatialValueTree#AXIS_WILDCARD. 077 * 078 * <p> 079 * <code>[ {'year', [AXIS_WILDCARD]}, {'state', ['NY','FL']} ]</code> 080 * 081 * <p> 082 * ... would return { [0x000236] [0x000423] [0x000501] }. 083 * 084 * <p> 085 * By convention, implementations are required to compare all generic types 086 * using {@link Object#hashCode()} and {@link Object#equals(Object)}. Users of 087 * this class should also use generic types which implement 088 * {@link Object#hashCode()} and {@link Object#equals(Object)} to avoid 089 * performance and consistency issues. 090 * 091 * @param <K> 092 * Type of the dimensions. 093 * @param <E> 094 * Type of the dimension bounds. 095 * @param <V> 096 * Type of the values to store. 097 */ 098public interface SpatialValueTree 099 <K extends Object, E extends Object, V extends Object> 100{ 101 /** 102 * Used as a token to represent all the values of an axis. 103 * Overrides {@link Object#equals(Object)} and 104 * {@link Object#hashCode()} so that only identity comparison 105 * are used. 106 */ 107 public static final Object AXIS_WILDCARD = 108 new Object() { 109 public int hashCode() { 110 return 42; 111 } 112 }; 113 114 /** 115 * Stores a string value at all points which intersect 116 * with the passed region key. 117 */ 118 void add(SpatialRegion<K, E> regionkey, V value); 119 120 /** 121 * Clears all the values found at the provided region 122 * key. 123 * 124 * @param regionKey The region key of the values to clear. 125 */ 126 void clear(SpatialRegion<K, E> regionKey); 127 128 /** 129 * Looks up all the values registered in nodes intersecting 130 * with the provided region key. 131 * @param regionKey The region key inside of which to search for 132 * value nodes. 133 * @return An unordered set of all the unique values intersecting 134 * with the region. 135 */ 136 Set<V> get(SpatialRegion<K, E> regionKey); 137 138 /** 139 * Looks up all the values registered in nodes intersecting 140 * with the provided region key. If a value is present in all 141 * of the nodes, a unique set of all the values found will be 142 * returned. An empty set is returned if no complete match 143 * could be found. 144 * @param regionKey The region key inside of which to search for 145 * value nodes. 146 * @return An unordered set of all the unique values intersecting 147 * with the region and covering it entirely, or an empty set 148 * otherwise. 149 */ 150 Set<V> match(SpatialRegion<K, E> regionKey); 151 152 /** 153 * Returns a list of all the dimensions present in this tree. 154 * @return A list of dimension unique ids. 155 */ 156 List<K> getDimensions(); 157 158 /** 159 * Tells the number of dimensions in this tree. 160 * @return The number of dimensions. 161 */ 162 int getDimensionality(); 163 164 /** 165 * Describes a spatial region within a {@link SpatialValueTree}. 166 * @param <K> Type of the dimension key. 167 * @param <E> Type of the values along the dimension's axis. 168 */ 169 public interface SpatialRegion 170 <K extends Object, E extends Object> 171 { 172 /** 173 * Provides a list of the dimensions included in this 174 * region. 175 * 176 * @return List of dimensions 177 */ 178 List<K> getDimensions(); 179 /** 180 * Provides an array of objects describing this region's 181 * bounds within the specified dimension's axis. 182 * 183 * @param dimension Dimension 184 * @return An array of the bounds touched by this region. 185 */ 186 E[] getValues(K dimension); 187 } 188} 189// End SpatialValueTree.java