IndirectPriorityQueue


1   package it.unimi.dsi.fastutil;
2   
3   /*       
4    * fastutil: Fast & compact type-specific collections for Java
5    *
6    * Copyright (C) 2003, 2004, 2005, 2006 Paolo Boldi and Sebastiano Vigna 
7    *
8    *  This library is free software; you can redistribute it and/or
9    *  modify it under the terms of the GNU Lesser General Public
10   *  License as published by the Free Software Foundation; either
11   *  version 2.1 of the License, or (at your option) any later version.
12   *
13   *  This library is distributed in the hope that it will be useful,
14   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16   *  Lesser General Public License for more details.
17   *
18   *  You should have received a copy of the GNU Lesser General Public
19   *  License along with this library; if not, write to the Free Software
20   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
21   *
22   */
23  
24  import java.util.Comparator  ;
25  import java.util.NoSuchElementException  ;
26  
27  /** An indirect priority queue.
28   *
29   * <P>An indirect priority queue provides a way to {@linkplain #enqueue(int)
30   * enqueue} by index elements taken from a given <em>reference list</em>,
31   * and to {@linkplain #dequeue() dequeue} them in some specified order.
32   * Elements that are <em>smaller</em> in the specified order are
33   * dequeued first. It
34   * is also possible to get the {@linkplain #first() index of the first element}, that
35   * is, the index that would be dequeued next.
36   *
37   * <P>Additionally, the queue may provide a method to peek at the index of the
38   * element that would be dequeued {@linkplain #last() last}.
39   *
40   * <P>The reference list should not change during queue operations (or, more
41   * precisely, the relative order of the elements in the queue should not
42   * change). Nonetheless, some implementations may give the caller a way to
43   * notify the queue that the {@linkplain #changed() first element has changed its 
44   * relative position in the order}.
45   *
46   * <P>Optionally, an indirect priority queue may even provide methods to notify
47   * {@linkplain #changed(int) the change of <em>any</em> element of the
48   * reference list}, and to {@linkplain #remove(int) remove from the queue} any
49   * element of the reference list presently in the queue. It may even allow to
50   * notify that {@linkplain #allChanged() all elements have changed}.
51   *
52   * <P>It is always possible to enqueue two distinct indices corresponding to
53   * equal elements of the reference list. However, depending on the
54   * implementation, it may or may not be possible to enqueue twice the same
55   * index.
56   *
57   * <P>Note that <em>all element manipulation happens via indices</em>.
58   */
59  
60  public interface IndirectPriorityQueue<K> {
61  
62      /** Enqueues a new element.
63       *
64       * @param index the element to enqueue..
65       */
66  
67      void enqueue( int index );
68  
69      /** Dequeues the {@linkplain #first() first} element from the queue.
70       *
71       * @return the dequeued element.
72       * @throws NoSuchElementException if the queue is empty.
73       */
74  
75      int dequeue();
76  
77      /** Checks whether the queue is empty.
78       *
79       * @return true if the queue is empty.
80       */
81  
82      boolean isEmpty();
83  
84      /** Returns the number of elements in this queue.
85       *
86       * @return the number of elements in this queue.
87       */
88  
89      int size();
90  
91      /** Removes all elements from this queue.
92       */
93  
94      void clear();
95  
96      /** Returns the first element of the queue.
97       *
98       * @return the first element.
99       * @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 
150 }
151
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags