Source code: com/port80/util/struct/IntList.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.util.struct;
6
7 import java.util.Arrays;
8
9 import com.port80.util.msg;
10 import com.port80.util.sprint;
11
12 public class IntList {
13
14 public static final int CAPACITY = 4;
15 private int[] list;
16 private int capacity = CAPACITY;
17 private int size = 0;
18
19 public IntList() {
20 list = new int[capacity];
21 }
22 public IntList(int cap) {
23 capacity = cap;
24 list = new int[capacity];
25 }
26 public void add(int v) {
27 list[size++] = v;
28 if (size == capacity)
29 expand();
30 }
31 public void set(int index, int value) throws IndexOutOfBoundsException {
32 if (index >= size)
33 throw new IndexOutOfBoundsException();
34 list[index] = value;
35 }
36 public int get(int index) {
37 return list[index];
38 }
39 public void remove(int index) {
40 --size;
41 for (int i = index; i < size; i++) {
42 list[i] = list[i + 1];
43 }
44 }
45 public int size() {
46 return size;
47 }
48 public int[] toArray() {
49 int[] ret = new int[size];
50 System.arraycopy(list, 0, ret, 0, size);
51 return ret;
52 }
53
54 public void sort() {
55 Arrays.sort(list, 0, size);
56 }
57
58 /** @return As in Arrays.binarySearch(). */
59 public int binarySearch(int x) {
60 return msg.binarySearch(list, 0, size, x);
61 }
62
63 /** @return Insert point x such that get(x-1)<=x<get(x). */
64 public int insertionIndex(int x) {
65 return msg.insertionIndex(list, 0, size, x);
66 }
67
68 public void pack() {
69 int[] ret = new int[size];
70 System.arraycopy(list, 0, ret, 0, size);
71 list = ret;
72 capacity = size;
73 }
74 public void clear() {
75 size = 0;
76 }
77 public String toString() {
78 StringBuffer buf=new StringBuffer();
79 for(int i=0; i<size; ++i) {
80 buf.append(sprint.f("%8d ").a(list[i]).end());
81 if((i%8)==7) buf.append("\n");
82 }
83 if((size%8)!=0) buf.append("\n");
84 return buf.toString();
85 }
86
87 ////////////////////////////////////////////////////////////////////////
88
89 private void expand() {
90 int[] ret = new int[capacity * 2];
91 System.arraycopy(list, 0, ret, 0, size);
92 capacity *= 2;
93 list = ret;
94 }
95
96 ////////////////////////////////////////////////////////////////////////
97
98 public static void main(String[] args) {
99 IntList a = new IntList();
100 a.add(100);
101 a.add(200);
102 a.add(300);
103 a.add(400);
104 a.add(500);
105 a.remove(2);
106 System.out.println("### 1");
107 for (int i = 0; i < a.size(); ++i) {
108 System.out.println("" + a.get(i));
109 }
110 try {
111 a.set(18, 1800);
112 } catch (Exception e) {
113 System.out.println("OK: Out of bound as expected.");
114 }
115 a.pack();
116 int[] b = a.toArray();
117 System.out.println("### 2");
118 for (int i = 0; i < b.length; ++i) {
119 System.out.println(b[i]);
120 }
121 //
122 // Test sort(), binarySearch() and InsertionIndex()
123 //
124 int[] data = new int[] { 0, 0, 1, 3, 3, 10, 50, 5, 3, 4, 8, 11 };
125 a.clear();
126 for (int i = 0; i < data.length; ++i)
127 a.add(data[i]);
128 a.sort();
129 msg.println("sorted a="+a);
130 int ret;
131 if ((ret = a.binarySearch(5)) != 7)
132 msg.err("binarySearch(5): expected=7, actual=" + ret);
133 if ((ret = a.insertionIndex(5)) != 8)
134 msg.err("insertionIndex(5): expected=8, actual=" + ret);
135 }
136
137 ////////////////////////////////////////////////////////////////////////
138
139 }