View Javadoc

1   /**
2    * Copyright (c) 2012, University of Konstanz, Distributed Systems Group
3    * All rights reserved.
4    * 
5    * Redistribution and use in source and binary forms, with or without
6    * modification, are permitted provided that the following conditions are met:
7    * * Redistributions of source code must retain the above copyright
8    * notice, this list of conditions and the following disclaimer.
9    * * Redistributions in binary form must reproduce the above copyright
10   * notice, this list of conditions and the following disclaimer in the
11   * documentation and/or other materials provided with the distribution.
12   * * Neither the name of the University of Konstanz nor the
13   * names of its contributors may be used to endorse or promote products
14   * derived from this software without specific prior written permission.
15   * 
16   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18   * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19   * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
20   * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21   * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26   */
27  package org.perfidix.example.list;
28  
29  import java.util.Arrays;
30  
31  /**
32   * This is a simple container for native integers.
33   * 
34   * @author BaseX Team 2005-11, BSD License
35   * @author Christian Gruen
36   */
37  public class IntList extends ElementList {
38      /** Element container. */
39      protected int[] list;
40  
41      /**
42       * Default constructor.
43       */
44      public IntList() {
45          this(CAP);
46      }
47  
48      /**
49       * Constructor, specifying an initial array capacity.
50       * 
51       * @param c
52       *            array capacity
53       */
54      public IntList(final int c) {
55          list = new int[c];
56      }
57  
58      /**
59       * Constructor.
60       * 
61       * @param f
62       *            resize factor
63       */
64      public IntList(final double f) {
65          this();
66          factor = f;
67      }
68  
69      /**
70       * Constructor, specifying an initial array.
71       * 
72       * @param a
73       *            initial array
74       */
75      public IntList(final int[] a) {
76          list = a;
77          size = a.length;
78      }
79  
80      /**
81       * Adds an entry to the array.
82       * 
83       * @param e
84       *            entry to be added
85       */
86      public final void add(final int e) {
87          if (size == list.length)
88              list = Arrays.copyOf(list, newSize());
89          list[size++] = e;
90      }
91  
92      /**
93       * Returns the element at the specified index position.
94       * 
95       * @param i
96       *            index
97       * @return element
98       */
99      public final int get(final int i) {
100         return list[i];
101     }
102 
103     /**
104      * Sets an element at the specified index position.
105      * 
106      * @param i
107      *            index
108      * @param e
109      *            element to be set
110      */
111     public final void set(final int i, final int e) {
112         if (i >= list.length)
113             list = Arrays.copyOf(list, newSize(i + 1));
114         list[i] = e;
115         size = Math.max(size, i + 1);
116     }
117 
118     /**
119      * Checks if the specified element is found in the list.
120      * 
121      * @param e
122      *            element to be found
123      * @return result of check
124      */
125     public final boolean contains(final int e) {
126         for (int i = 0; i < size; ++i)
127             if (list[i] == e)
128                 return true;
129         return false;
130     }
131 
132     /**
133      * Inserts elements at the specified index position.
134      * 
135      * @param i
136      *            index
137      * @param e
138      *            elements to be inserted
139      */
140     public final void insert(final int i, final int[] e) {
141         final int l = e.length;
142         if (l == 0)
143             return;
144         if (size + l > list.length)
145             list = Arrays.copyOf(list, newSize(size + l));
146         Array.move(list, i, l, size - i);
147         System.arraycopy(e, 0, list, i, l);
148         size += l;
149     }
150 
151     /**
152      * Deletes the specified element.
153      * 
154      * @param i
155      *            element to be deleted
156      */
157     public final void delete(final int i) {
158         Array.move(list, i + 1, -1, --size - i);
159     }
160 
161     /**
162      * Adds a difference to all elements starting from the specified index.
163      * 
164      * @param e
165      *            difference
166      * @param i
167      *            index
168      */
169     public final void move(final int e, final int i) {
170         for (int a = i; a < size; a++)
171             list[a] += e;
172     }
173 
174     /**
175      * Returns the uppermost element from the stack.
176      * 
177      * @return the uppermost element
178      */
179     public final int peek() {
180         return list[size - 1];
181     }
182 
183     /**
184      * Pops the uppermost element from the stack.
185      * 
186      * @return the popped element
187      */
188     public final int pop() {
189         return list[--size];
190     }
191 
192     /**
193      * Pushes an element onto the stack.
194      * 
195      * @param val
196      *            element
197      */
198     public final void push(final int val) {
199         add(val);
200     }
201 
202     /**
203      * Searches the specified element via binary search. Note that all elements
204      * must be sorted.
205      * 
206      * @param e
207      *            element to be found
208      * @return index of the search key, or the negative insertion point - 1
209      */
210     public final int sortedIndexOf(final int e) {
211         return Arrays.binarySearch(list, 0, size, e);
212     }
213 
214     /**
215      * Returns an array with all elements.
216      * 
217      * @return array
218      */
219     public final int[] toArray() {
220         return Arrays.copyOf(list, size);
221     }
222 
223     /**
224      * Sorts the data.
225      * 
226      * @return self reference
227      */
228     public IntList sort() {
229         Arrays.sort(list, 0, size);
230         return this;
231     }
232 
233 }