001: package it.unimi.dsi.fastutil;
002:
003: /*
004: * fastutil: Fast & compact type-specific collections for Java
005: *
006: * Copyright (C) 2003-2008 Paolo Boldi and Sebastiano Vigna
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: */
023:
024: import java.util.Comparator;
025: import java.util.NoSuchElementException;
026:
027: /** An indirect priority queue.
028: *
029: * <P>An indirect priority queue provides a way to {@linkplain #enqueue(int)
030: * enqueue} by index elements taken from a given <em>reference list</em>,
031: * and to {@linkplain #dequeue() dequeue} them in some specified order.
032: * Elements that are <em>smaller</em> in the specified order are
033: * dequeued first. It
034: * is also possible to get the {@linkplain #first() index of the first element}, that
035: * is, the index that would be dequeued next.
036: *
037: * <P>Additionally, the queue may provide a method to peek at the index of the
038: * element that would be dequeued {@linkplain #last() last}.
039: *
040: * <P>The reference list should not change during queue operations (or, more
041: * precisely, the relative order of the elements in the queue should not
042: * change). Nonetheless, some implementations may give the caller a way to
043: * notify the queue that the {@linkplain #changed() first element has changed its
044: * relative position in the order}.
045: *
046: * <P>Optionally, an indirect priority queue may even provide methods to notify
047: * {@linkplain #changed(int) the change of <em>any</em> element of the
048: * reference list}, and to {@linkplain #remove(int) remove from the queue} any
049: * element of the reference list presently in the queue. It may even allow to
050: * notify that {@linkplain #allChanged() all elements have changed}.
051: *
052: * <P>It is always possible to enqueue two distinct indices corresponding to
053: * equal elements of the reference list. However, depending on the
054: * implementation, it may or may not be possible to enqueue twice the same
055: * index.
056: *
057: * <P>Note that <em>all element manipulation happens via indices</em>.
058: */
059:
060: public interface IndirectPriorityQueue<K> {
061:
062: /** Enqueues a new element.
063: *
064: * @param index the element to enqueue..
065: */
066:
067: void enqueue(int index);
068:
069: /** Dequeues the {@linkplain #first() first} element from the queue.
070: *
071: * @return the dequeued element.
072: * @throws NoSuchElementException if the queue is empty.
073: */
074:
075: int dequeue();
076:
077: /** Checks whether the queue is empty.
078: *
079: * @return true if the queue is empty.
080: */
081:
082: boolean isEmpty();
083:
084: /** Returns the number of elements in this queue.
085: *
086: * @return the number of elements in this queue.
087: */
088:
089: int size();
090:
091: /** Removes all elements from this queue.
092: */
093:
094: void clear();
095:
096: /** Returns the first element of the queue.
097: *
098: * @return the first element.
099: * @throws NoSuchElementException if the queue is empty.
100: */
101:
102: int first();
103:
104: /** Returns the last element of the queue, that is, the element the would be dequeued last (optional operation).
105: *
106: * @return the last element.
107: * @throws NoSuchElementException if the queue is empty.
108: */
109:
110: int last();
111:
112: /** Notifies the queue that the {@linkplain #first() first element} has changed (optional operation).
113: *
114: */
115:
116: void changed();
117:
118: /** Returns the comparator associated with this queue, or <code>null</code> if it uses its elements' natural ordering.
119: *
120: * @return the comparator associated with this sorted set, or <code>null</code> if it uses its elements' natural ordering.
121: */
122: Comparator<? super K> comparator();
123:
124: /** Notifies the queue that the specified element has changed (optional operation).
125: *
126: * <P>Note that the specified element must belong to the queue.
127: *
128: * @param index the element that has changed.
129: * @throws NoSuchElementException if the specified element is not in the queue.
130: */
131:
132: public void changed(int index);
133:
134: /** Notifies the queue that the all elements have changed (optional operation).
135: */
136:
137: public void allChanged();
138:
139: /** Removes the specified element from the queue (optional operation).
140: *
141: * <P>Note that the specified element must belong to the queue.
142: *
143: * @param index the element to be removed.
144: * @throws NoSuchElementException if the specified element is not in the queue.
145: */
146:
147: public void remove(int index);
148:
149: /** Retrieves the front of the queue in a given array (optional operation).
150: *
151: * <p>The <em>front</em> of an indirect queue is the set of indices whose associated elements in the reference array
152: * are equal to the element associated to the {@linkplain #first() first index}. These indices can be always obtain by dequeueing, but
153: * this method should retrieve efficiently such indices in the given array without modifying the state of the queue.
154: *
155: * @param a an array large enough to hold the front (e.g., at least long as the reference array).
156: * @return the number of elements actually written (starting from the first position of <code>a</code>).
157: */
158:
159: public int front(final int[] a);
160:
161: }
|