Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
Node.cs
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 using System;
19 using System.Collections.Generic;
20 using System.Collections.ObjectModel;
21 using System.Diagnostics;
22 using System.Runtime.CompilerServices;
23 using Spatial4n.Core.Shapes;
24 
25 namespace Lucene.Net.Spatial.Prefix.Tree
26 {
27  public abstract class Node : IComparable<Node>
28  {
29  public static byte LEAF_BYTE = (byte)'+';//NOTE: must sort before letters & numbers
30 
31  // /*
32  //Holds a byte[] and/or String representation of the cell. Both are lazy constructed from the other.
33  //Neither contains the trailing leaf byte.
34  // */
35  //private byte[] bytes;
36  //private int b_off;
37  //private int b_len;
38 
39  private String token;//this is the only part of equality
40 
41  protected SpatialRelation shapeRel;//set in getSubCells(filter), and via setLeaf().
43 
44  protected Node(SpatialPrefixTree spatialPrefixTree, String token)
45  {
46  this.spatialPrefixTree = spatialPrefixTree;
47  this.token = token;
48  if (token.Length > 0 && token[token.Length - 1] == (char)LEAF_BYTE)
49  {
50  this.token = token.Substring(0, token.Length - 1);
51  SetLeaf();
52  }
53 
54  if (GetLevel() == 0)
55  GetShape();//ensure any lazy instantiation completes to make this threadsafe
56  }
57 
58  public virtual void Reset(string newToken)
59  {
60  Debug.Assert(GetLevel() != 0);
61  this.token = newToken;
62  shapeRel = SpatialRelation.NULL_VALUE;
63  b_fixLeaf();
64  }
65 
66  private void b_fixLeaf()
67  {
68  if (GetLevel() == spatialPrefixTree.GetMaxLevels())
69  {
70  SetLeaf();
71  }
72  }
73 
74  public SpatialRelation GetShapeRel()
75  {
76  return shapeRel;
77  }
78 
79  public bool IsLeaf()
80  {
81  return shapeRel == SpatialRelation.WITHIN;
82  }
83 
84  public void SetLeaf()
85  {
86  Debug.Assert(GetLevel() != 0);
87  shapeRel = SpatialRelation.WITHIN;
88  }
89 
90  /*
91  * Note: doesn't contain a trailing leaf byte.
92  */
93  public String GetTokenString()
94  {
95  if (token == null)
96  throw new InvalidOperationException("Somehow we got a null token");
97  return token;
98  }
99 
100  ///// <summary>
101  ///// Note: doesn't contain a trailing leaf byte.
102  ///// </summary>
103  ///// <returns></returns>
104  //public byte[] GetTokenBytes()
105  //{
106  // if (bytes != null)
107  // {
108  // if (b_off != 0 || b_len != bytes.Length)
109  // {
110  // throw new IllegalStateException("Not supported if byte[] needs to be recreated.");
111  // }
112  // }
113  // else
114  // {
115  // bytes = token.GetBytes(SpatialPrefixTree.UTF8);
116  // b_off = 0;
117  // b_len = bytes.Length;
118  // }
119  // return bytes;
120  //}
121 
122  public int GetLevel()
123  {
124  return token.Length;
125  //return token != null ? token.Length : b_len;
126  }
127 
128  //TODO add getParent() and update some algorithms to use this?
129  //public Cell getParent();
130 
131  /*
132  * Like {@link #getSubCells()} but with the results filtered by a shape. If that shape is a {@link com.spatial4j.core.shape.Point} then it
133  * must call {@link #getSubCell(com.spatial4j.core.shape.Point)};
134  * Precondition: Never called when getLevel() == maxLevel.
135  *
136  * @param shapeFilter an optional filter for the returned cells.
137  * @return A set of cells (no dups), sorted. Not Modifiable.
138  */
139  public IList<Node> GetSubCells(Shape shapeFilter)
140  {
141  //Note: Higher-performing subclasses might override to consider the shape filter to generate fewer cells.
142  var point = shapeFilter as Point;
143  if (point != null)
144  {
145 #if !NET35
146  return new ReadOnlyCollectionBuilder<Node>(new[] {GetSubCell(point)}).ToReadOnlyCollection();
147 #else
148  return new List<Node>(new[]{GetSubCell(point)}).AsReadOnly();
149 #endif
150 
151  }
152 
153  var cells = GetSubCells();
154  if (shapeFilter == null)
155  {
156  return cells;
157  }
158  var copy = new List<Node>(cells.Count);//copy since cells contractually isn't modifiable
159  foreach (var cell in cells)
160  {
161  SpatialRelation rel = cell.GetShape().Relate(shapeFilter);
162  if (rel == SpatialRelation.DISJOINT)
163  continue;
164  cell.shapeRel = rel;
165  copy.Add(cell);
166  }
167  cells = copy;
168  return cells;
169  }
170 
171  /*
172  * Performant implementations are expected to implement this efficiently by considering the current
173  * cell's boundary.
174  * Precondition: Never called when getLevel() == maxLevel.
175  * Precondition: this.getShape().relate(p) != DISJOINT.
176  */
177  public abstract Node GetSubCell(Point p);
178 
179  //TODO Cell getSubCell(byte b)
180 
181  /*
182  * Gets the cells at the next grid cell level that cover this cell.
183  * Precondition: Never called when getLevel() == maxLevel.
184  *
185  * @return A set of cells (no dups), sorted. Not Modifiable.
186  */
187  public abstract IList<Node> GetSubCells();
188 
189  /*
190  * {@link #getSubCells()}.size() -- usually a constant. Should be >=2
191  */
192  public abstract int GetSubCellsSize();
193 
194  public abstract Shape GetShape();
195 
196  public virtual Point GetCenter()
197  {
198  return GetShape().GetCenter();
199  }
200 
201 
202  public int CompareTo(Node o)
203  {
204  return System.String.CompareOrdinal(GetTokenString(), o.GetTokenString());
205  }
206 
207  public override bool Equals(object obj)
208  {
209  return !(obj == null || !(obj is Node)) && GetTokenString().Equals(((Node) obj).GetTokenString());
210  }
211 
212  public override int GetHashCode()
213  {
214  return GetTokenString().GetHashCode();
215  }
216 
217  public override string ToString()
218  {
219  return GetTokenString() + (IsLeaf() ? new string(new[] {(char) LEAF_BYTE}) : string.Empty);
220  }
221  }
222 }