← Back to branch summary

~vcs-imports/xena/trunk

« back to all changes in this revision

Viewing changes to ext/src/javahelp/jhMaster/JSearch/client/com/sun/java/help/search/.svn/text-base/HitStore.java.svn-base

  • Committer: matthewoliver
  • Date: 2009-12-10 03:18:07 UTC
  • Revision ID: vcs-imports@canonical.com-20091210031807-l086qguzdlljtkl9
Merged Xena Testing into Xena Stable for the Xena 5 release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/src/javahelp/jhMaster/JSearch/client/com/sun/java/help/search/.svn/text-base/HitStore.java.svn-base
 
1
/*
 
2
 * @(#)HitStore.java    1.7 06/10/30
 
3
 * 
 
4
 * Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
 
5
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 
6
 * 
 
7
 * This code is free software; you can redistribute it and/or modify it
 
8
 * under the terms of the GNU General Public License version 2 only, as
 
9
 * published by the Free Software Foundation.  Sun designates this
 
10
 * particular file as subject to the "Classpath" exception as provided
 
11
 * by Sun in the LICENSE file that accompanied this code.
 
12
 * 
 
13
 * This code is distributed in the hope that it will be useful, but WITHOUT
 
14
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 
15
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 
16
 * version 2 for more details (a copy is included in the LICENSE file that
 
17
 * accompanied this code).
 
18
 * 
 
19
 * You should have received a copy of the GNU General Public License version
 
20
 * 2 along with this work; if not, write to the Free Software Foundation,
 
21
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 
22
 * 
 
23
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 
24
 * CA 95054 USA or visit www.sun.com if you need additional information or
 
25
 * have any questions.
 
26
 */
 
27
 
 
28
/**
 
29
 * @date   1/13/98
 
30
 * @author Jacek R. Ambroziak
 
31
 * @group  Sun Microsystems Laboratories
 
32
 */
 
33
 
 
34
package com.sun.java.help.search;
 
35
 
 
36
import java.util.Vector;
 
37
 
 
38
class HitStoreNode
 
39
{
 
40
  private int           _free = 0;
 
41
  private int           _size;
 
42
  private QueryHit[]    _array;
 
43
  private int           _hitCount = 0;
 
44
  private double         _divider = 0.0;
 
45
  private double         _min = 10000000.0;
 
46
  private double         _max = 0.0;
 
47
  private HitStoreNode[] _children = new HitStoreNode[2]; // left & right
 
48
  private int           _index = 0;
 
49
 
 
50
  public HitStoreNode(int size) {
 
51
    _array = new QueryHit[_size = size];
 
52
  }
 
53
  
 
54
  public QueryHit getNextHit() {
 
55
    return _index < _free ? _array[_index++] : null;
 
56
  }
 
57
  
 
58
  private void fastAdd(QueryHit hit)
 
59
  {
 
60
    _hitCount++;
 
61
    _divider += hit.getScore();
 
62
    if (hit.getScore() > _max)
 
63
      _max = hit.getScore();
 
64
    if (hit.getScore() < _min)
 
65
      _min = hit.getScore();
 
66
    _array[_free++] = hit;
 
67
  }
 
68
 
 
69
  public boolean add(QueryHit hit)
 
70
  {
 
71
    if (_array != null)
 
72
      {
 
73
        if (_free < _size)
 
74
          {
 
75
            fastAdd(hit);
 
76
            return false;
 
77
          }
 
78
        else if (_min != _max)
 
79
          {
 
80
            split();
 
81
            _hitCount++;
 
82
            _children[hit.getScore() > _divider ? 1 : 0].fastAdd(hit);
 
83
            return true;
 
84
          }
 
85
        else
 
86
          {
 
87
            QueryHit[] newArray = new QueryHit[_size *= 2];
 
88
            System.arraycopy(_array, 0, newArray, 0, _free);
 
89
            _array = newArray;
 
90
            fastAdd(hit);
 
91
            return true;
 
92
          }
 
93
      }
 
94
    else
 
95
      {
 
96
        _hitCount++;
 
97
        return _children[hit.getScore() > _divider ? 1 : 0].add(hit);
 
98
      }
 
99
  }
 
100
 
 
101
  private void split()
 
102
  {
 
103
    _children[0] = new HitStoreNode(_size);
 
104
    _children[1] = new HitStoreNode(_size);
 
105
    _divider /= _hitCount;      // becomes average
 
106
    for (int i = 0; i < _free; i++)
 
107
      _children[_array[i].getScore() > _divider ? 1 : 0].fastAdd(_array[i]);
 
108
    _array = null;                      // becomes internal
 
109
  }
 
110
  public int getCount() {
 
111
    return _hitCount;
 
112
  }
 
113
  public double getDivider() {
 
114
    return _divider;
 
115
  }
 
116
  public HitStoreNode getLChild() {
 
117
    return _children[0];
 
118
  }
 
119
  public HitStoreNode getRChild() {
 
120
    return _children[1];
 
121
  }
 
122
  public void setLChild(HitStoreNode node) {
 
123
    _children[0] = node;
 
124
  }
 
125
  public void setRChild(HitStoreNode node) {
 
126
    _children[1] = node;
 
127
  }
 
128
  public void decrementCount(int delta) {
 
129
    _hitCount -= delta;
 
130
  }
 
131
  public boolean isLeaf() {
 
132
    return _array != null;
 
133
  }
 
134
  
 
135
  public void sort() {
 
136
    quicksort(0, _free - 1);
 
137
  }
 
138
 
 
139
  public void gatherLeaves(Vector vector)
 
140
  {
 
141
    if (isLeaf())
 
142
      vector.addElement(this);
 
143
    else
 
144
      {
 
145
        getLChild().gatherLeaves(vector);
 
146
        getRChild().gatherLeaves(vector);
 
147
      }
 
148
  }
 
149
  
 
150
  // part of quicksearch
 
151
  private int partition(int p, int r)
 
152
  {
 
153
    QueryHit x = _array[p];
 
154
    int i = p - 1, j = r + 1;
 
155
    while (true)
 
156
      {
 
157
        while (x.betterThan(_array[--j]))
 
158
          ;
 
159
        while (_array[++i].betterThan(x))
 
160
          ;
 
161
        if (i < j)
 
162
          {
 
163
            QueryHit t = _array[i];
 
164
            _array[i] = _array[j];
 
165
            _array[j] = t;
 
166
          }
 
167
        else
 
168
          return j;
 
169
      }
 
170
  }
 
171
 
 
172
  private void quicksort(int p, int r)
 
173
  {
 
174
    if (p < r)
 
175
      {
 
176
        int q = partition(p, r);
 
177
        quicksort(p, q);
 
178
        quicksort(q + 1, r);
 
179
      }
 
180
  }
 
181
}
 
182
 
 
183
 
 
184
class HitStore
 
185
{
 
186
  private static final int ArraySize = 128;
 
187
  private static final int DefaultLimit = 300;
 
188
  
 
189
  private HitStoreNode _root = new HitStoreNode(ArraySize);
 
190
  private int           _limit;
 
191
  private double        _standard;
 
192
  private Vector       _leaves = null;
 
193
  private HitStoreNode _current = null;
 
194
 
 
195
  public HitStore(double initialStandard) {
 
196
    this(initialStandard, DefaultLimit);
 
197
  }
 
198
  
 
199
  public HitStore(double initialStandard, int limit)
 
200
  {
 
201
    _limit = limit;
 
202
    _standard = initialStandard;
 
203
  }
 
204
  
 
205
  public void addQueryHit(QueryHit hit) {
 
206
    if(_root.add(hit))
 
207
      adapt();
 
208
  }
 
209
  
 
210
  private HitStoreNode getNextNode()
 
211
  {
 
212
    if (_leaves.size() > 0)
 
213
      {
 
214
        HitStoreNode node = (HitStoreNode)_leaves.firstElement();
 
215
        _leaves.removeElementAt(0);
 
216
        node.sort();
 
217
        return node;
 
218
      }
 
219
    else
 
220
      return null;
 
221
  }
 
222
 
 
223
  public QueryHit firstBestQueryHit()
 
224
  {
 
225
    _leaves = new Vector();
 
226
    _root.gatherLeaves(_leaves);
 
227
    _current = getNextNode();
 
228
    return _current.getNextHit();
 
229
  }
 
230
  
 
231
  public QueryHit nextBestQueryHit()
 
232
  {
 
233
    QueryHit result = _current.getNextHit();
 
234
    if (result != null)
 
235
      return result;
 
236
    else if ((_current = getNextNode()) != null)
 
237
      return _current.getNextHit();
 
238
    else
 
239
      return null;
 
240
  }
 
241
  
 
242
  double getCurrentStandard() {
 
243
    return _standard;
 
244
  }
 
245
  
 
246
  private void adapt()
 
247
  {
 
248
    if (_root.getCount() > _limit)
 
249
      if (!_root.isLeaf())
 
250
        {
 
251
          HitStoreNode ptr = _root;
 
252
          // find rightmost internal
 
253
          while (!ptr.getRChild().isLeaf())
 
254
            ptr = ptr.getRChild();
 
255
      
 
256
          _standard = ptr.getDivider();
 
257
      
 
258
          if (ptr == _root)
 
259
            _root = ptr.getLChild();
 
260
          else
 
261
            {
 
262
              int count = ptr.getRChild().getCount();
 
263
              HitStoreNode ptr2 = _root;
 
264
              while (ptr2.getRChild() != ptr)
 
265
                {
 
266
                  ptr2.decrementCount(count);
 
267
                  ptr2 = ptr2.getRChild();
 
268
                }
 
269
              ptr2.setRChild(ptr.getLChild());
 
270
            }
 
271
          ptr.setLChild(null);
 
272
        }
 
273
  }
 
274
}