← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/clusterers/forOPTICSAndDBScan/Utils/UpdateQueue.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/clusterers/forOPTICSAndDBScan/Utils/UpdateQueue.java
 
1
/*
 
2
 *    This program is free software; you can redistribute it and/or modify
 
3
 *    it under the terms of the GNU General Public License as published by
 
4
 *    the Free Software Foundation; either version 2 of the License, or
 
5
 *    (at your option) any later version.
 
6
 *
 
7
 *    This program is distributed in the hope that it will be useful,
 
8
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 *    GNU General Public License for more details.
 
11
 *
 
12
 *    You should have received a copy of the GNU General Public License
 
13
 *    along with this program; if not, write to the Free Software
 
14
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 *    Copyright (C) 2004
 
19
 *    & Matthias Schubert (schubert@dbs.ifi.lmu.de)
 
20
 *    & Zhanna Melnikova-Albrecht (melnikov@cip.ifi.lmu.de)
 
21
 *    & Rainer Holzmann (holzmann@cip.ifi.lmu.de)
 
22
 */
 
23
 
 
24
package weka.clusterers.forOPTICSAndDBScan.Utils;
 
25
 
 
26
import java.util.ArrayList;
 
27
import java.util.TreeMap;
 
28
 
 
29
/**
 
30
 * <p>
 
31
 * UpdateQueue.java <br/>
 
32
 * Authors: Rainer Holzmann, Zhanna Melnikova-Albrecht, Matthias Schubert <br/>
 
33
 * Date: Aug 27, 2004 <br/>
 
34
 * Time: 5:36:35 PM <br/>
 
35
 * $ Revision 1.4 $ <br/>
 
36
 * </p>
 
37
 *
 
38
 * @author Matthias Schubert (schubert@dbs.ifi.lmu.de)
 
39
 * @author Zhanna Melnikova-Albrecht (melnikov@cip.ifi.lmu.de)
 
40
 * @author Rainer Holzmann (holzmann@cip.ifi.lmu.de)
 
41
 * @version $Revision: 1.2 $
 
42
 */
 
43
public class UpdateQueue {
 
44
 
 
45
    /**
 
46
     * Used to store the binary heap
 
47
     */
 
48
    private ArrayList queue;
 
49
 
 
50
    /**
 
51
     * Used to get efficient access to the stored Objects
 
52
     */
 
53
    private TreeMap objectPositionsInHeap;
 
54
 
 
55
    // *****************************************************************************************************************
 
56
    // constructors
 
57
    // *****************************************************************************************************************
 
58
 
 
59
    /**
 
60
     * Creates a new PriorityQueue (backed on a binary heap) with the ability to efficiently
 
61
     * update the priority of the stored objects in the heap. The ascending (!) queue is
 
62
     * dynamically growing and shrinking.
 
63
     */
 
64
    public UpdateQueue() {
 
65
        queue = new ArrayList();
 
66
        objectPositionsInHeap = new TreeMap();
 
67
    }
 
68
 
 
69
    // *****************************************************************************************************************
 
70
    // methods
 
71
    // *****************************************************************************************************************
 
72
 
 
73
    /**
 
74
     * Adds a new Object to the queue
 
75
     * @param priority The priority associated with the object (in this case: the reachability-distance)
 
76
     * @param objectKey The key for this object
 
77
     * @param o
 
78
     */
 
79
    public void add(double priority, Object o, String objectKey) {
 
80
        int objectPosition = 0;
 
81
 
 
82
        if (objectPositionsInHeap.containsKey(objectKey)) {
 
83
            objectPosition = ((Integer) objectPositionsInHeap.get(objectKey)).intValue();
 
84
            if (((UpdateQueueElement) queue.get(objectPosition)).getPriority() <= priority) return;
 
85
            queue.set(objectPosition++, new UpdateQueueElement(priority, o, objectKey));
 
86
        } else {
 
87
            queue.add(new UpdateQueueElement(priority, o, objectKey));
 
88
            objectPosition = size();
 
89
        }
 
90
        heapValueUpwards(objectPosition);
 
91
    }
 
92
 
 
93
    /**
 
94
     * Returns the priority for the object at the specified index
 
95
     * @param index the index of the object
 
96
     * @return priority
 
97
     */
 
98
    public double getPriority(int index) {
 
99
        return ((UpdateQueueElement) queue.get(index)).getPriority();
 
100
    }
 
101
 
 
102
    /**
 
103
     * Restores the heap after inserting a new object
 
104
     */
 
105
    private void heapValueUpwards(int pos) {
 
106
        int a = pos;
 
107
        int c = a / 2;
 
108
 
 
109
        UpdateQueueElement recentlyInsertedElement = (UpdateQueueElement) queue.get(a - 1);
 
110
 
 
111
        /** ascending order! */
 
112
        while (c > 0 && getPriority(c - 1) > recentlyInsertedElement.getPriority()) {
 
113
            queue.set(a - 1, queue.get(c - 1));       //shift parent-node down
 
114
            objectPositionsInHeap.put(((UpdateQueueElement) queue.get(a - 1)).getObjectKey(), new Integer(a - 1));
 
115
            a = c;                                    //(c <= 0) => no parent-node remains
 
116
            c = a / 2;
 
117
        }
 
118
        queue.set(a - 1, recentlyInsertedElement);
 
119
        objectPositionsInHeap.put(((UpdateQueueElement) queue.get(a - 1)).getObjectKey(), new Integer(a - 1));
 
120
    }
 
121
 
 
122
    /**
 
123
     * Restores the heap after removing the next element
 
124
     */
 
125
    private void heapValueDownwards() {
 
126
        int a = 1;
 
127
        int c = 2 * a;           //descendant
 
128
 
 
129
        UpdateQueueElement updateQueueElement = (UpdateQueueElement) queue.get(a - 1);
 
130
 
 
131
        if (c < size() && (getPriority(c) < getPriority(c - 1))) c++;
 
132
 
 
133
        while (c <= size() && getPriority(c - 1) < updateQueueElement.getPriority()) {
 
134
            queue.set(a - 1, queue.get(c - 1));
 
135
            objectPositionsInHeap.put(((UpdateQueueElement) queue.get(a - 1)).getObjectKey(), new Integer(a - 1));
 
136
            a = c;
 
137
            c = 2 * a;
 
138
            if (c < size() && (getPriority(c) < getPriority(c - 1))) c++;
 
139
        }
 
140
        queue.set(a - 1, updateQueueElement);
 
141
        objectPositionsInHeap.put(((UpdateQueueElement) queue.get(a - 1)).getObjectKey(), new Integer(a - 1));
 
142
    }
 
143
 
 
144
    /**
 
145
     * Returns the queue's size
 
146
     * @return size
 
147
     */
 
148
    public int size() {
 
149
        return queue.size();
 
150
    }
 
151
 
 
152
    /**
 
153
     * Tests, if the queue has some more elements left
 
154
     * @return true, if there are any elements left, else false
 
155
     */
 
156
    public boolean hasNext() {
 
157
        return !(queue.size() == 0);
 
158
    }
 
159
 
 
160
    /**
 
161
     * Returns the element with the lowest priority
 
162
     * @return next element
 
163
     */
 
164
    public UpdateQueueElement next() {
 
165
        UpdateQueueElement next = (UpdateQueueElement) queue.get(0);
 
166
        queue.set(0, queue.get(size() - 1));
 
167
        queue.remove(size() - 1);
 
168
        objectPositionsInHeap.remove(next.getObjectKey());
 
169
        if (hasNext()) {
 
170
            heapValueDownwards();
 
171
        }
 
172
        return next;
 
173
    }
 
174
 
 
175
    // *****************************************************************************************************************
 
176
    // inner classes
 
177
    // *****************************************************************************************************************
 
178
 
 
179
}