View Javadoc

1   /*******************************************************************************
2    * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2008 Daniel Le Berre
3    *
4    * All rights reserved. This program and the accompanying materials
5    * are made available under the terms of the Eclipse Public License v1.0
6    * which accompanies this distribution, and is available at
7    * http://www.eclipse.org/legal/epl-v10.html
8    *
9    * Alternatively, the contents of this file may be used under the terms of
10   * either the GNU Lesser General Public License Version 2.1 or later (the
11   * "LGPL"), in which case the provisions of the LGPL are applicable instead
12   * of those above. If you wish to allow use of your version of this file only
13   * under the terms of the LGPL, and not to allow others to use your version of
14   * this file under the terms of the EPL, indicate your decision by deleting
15   * the provisions above and replace them with the notice and other provisions
16   * required by the LGPL. If you do not delete the provisions above, a recipient
17   * may use your version of this file under the terms of the EPL or the LGPL.
18   * 
19   * Based on the original MiniSat specification from:
20   * 
21   * An extensible SAT solver. Niklas Een and Niklas Sorensson. Proceedings of the
22   * Sixth International Conference on Theory and Applications of Satisfiability
23   * Testing, LNCS 2919, pp 502-518, 2003.
24   *
25   * See www.minisat.se for the original solver in C++.
26   * 
27   *******************************************************************************/
28  package org.sat4j.specs;
29  
30  import java.io.Serializable;
31  import java.util.Comparator;
32  import java.util.Iterator;
33  
34  /**
35   * An abstraction on the type of vector used in the library.
36   * 
37   * @author leberre
38   */
39  public interface IVec<T> extends Serializable {
40  
41  	/**
42  	 * @return the number of elements contained in the vector
43  	 */
44  	int size();
45  
46  	/**
47  	 * Remove nofelems from the Vector. It is assumed that the number of
48  	 * elements to remove is smaller or equals to the current number of elements
49  	 * in the vector
50  	 * 
51  	 * @param nofelems
52  	 *            the number of elements to remove.
53  	 */
54  	void shrink(int nofelems);
55  
56  	/**
57  	 * reduce the Vector to exactly newsize elements
58  	 * 
59  	 * @param newsize
60  	 *            the new size of the vector.
61  	 */
62  	void shrinkTo(final int newsize);
63  
64  	/**
65  	 * Pop the last element on the stack. It is assumed that the stack is not
66  	 * empty!
67  	 */
68  	void pop();
69  
70  	void growTo(final int newsize, final T pad);
71  
72  	void ensure(final int nsize);
73  
74  	IVec<T> push(final T elem);
75  
76  	/**
77  	 * To push an element in the vector when you know you have space for it.
78  	 * 
79  	 * @param elem
80  	 */
81  	void unsafePush(T elem);
82  
83  	/**
84  	 * Insert an element at the very begining of the vector. The former first
85  	 * element is appended to the end of the vector in order to have a constant
86  	 * time operation.
87  	 * 
88  	 * @param elem
89  	 *            the element to put first in the vector.
90  	 */
91  	void insertFirst(final T elem);
92  
93  	void insertFirstWithShifting(final T elem);
94  
95  	void clear();
96  
97  	/**
98  	 * return the latest element on the stack. It is assumed that the stack is
99  	 * not empty!
100 	 * 
101 	 * @return the last (top) element on the stack
102 	 */
103 	T last();
104 
105 	T get(int i);
106 
107 	void set(int i, T o);
108 
109 	/**
110 	 * Enleve un element qui se trouve dans le vecteur!!!
111 	 * 
112 	 * @param elem
113 	 *            un element du vecteur
114 	 */
115 	void remove(T elem);
116 
117 	/**
118 	 * Delete the ith element of the vector. The latest element of the vector
119 	 * replaces the removed element at the ith indexer.
120 	 * 
121 	 * @param i
122 	 *            the indexer of the element in the vector
123 	 * @return the former ith element of the vector that is now removed from the
124 	 *         vector
125 	 */
126 	T delete(int i);
127 
128 	/**
129 	 * Ces operations devraient se faire en temps constant. Ce n'est pas le cas
130 	 * ici.
131 	 * 
132 	 * @param copy
133 	 */
134 	void copyTo(IVec<T> copy);
135 
136 	<E> void copyTo(E[] dest);
137 
138 	/**
139 	 * Allow to access the internal representation of the vector as an array.
140 	 * Note that only the content of index 0 to size() should be taken into
141 	 * account. USE WITH CAUTION
142 	 * 
143 	 * @return the internal representation of the Vector as an array.
144 	 */
145 	T[] toArray();
146 
147 	/**
148 	 * Move the content of the vector into dest. Note that the vector become
149 	 * empty. The content of the vector is appended to dest.
150 	 * 
151 	 * @param dest
152 	 *            the vector where top put the content of this vector
153 	 */
154 	void moveTo(IVec<T> dest);
155 
156 	/**
157 	 * Move elements inside the vector. The content of the method is equivalent
158 	 * to: <code>vec[dest] = vec[source]</code>
159 	 * 
160 	 * @param dest
161 	 *            the index of the destination
162 	 * @param source
163 	 *            the index of the source
164 	 */
165 	void moveTo(int dest, int source);
166 
167 	/*
168 	 * @param comparator
169 	 */
170 	void sort(Comparator<T> comparator);
171 
172 	void sortUnique(Comparator<T> comparator);
173 
174 	/**
175 	 * To know if a vector is empty
176 	 * 
177 	 * @return true iff the vector is empty.
178 	 * @since 1.6
179 	 */
180 	boolean isEmpty();
181 
182 	Iterator<T> iterator();
183 
184 	/**
185 	 * 
186 	 * @param element
187 	 *            an object
188 	 * @return true iff element is found in the vector.
189 	 * @since 2.1
190 	 */
191 	boolean contains(T element);
192 
193 	/**
194 	 * @param element
195 	 *            an object
196 	 * @return the index of the element if it is found in the vector, else -1.
197 	 * @since 2.2
198 	 */
199 	int indexOf(T element);
200 }