|
1
21 package org.jacorb.collection.util;
22
23 import java.util.Enumeration  ;
24
25 public class SortedVector {
26 private DynArray data;
27 private ObjectComparator cmpr;
28
29 public SortedVector( ObjectComparator cmpr ) {
30 data = new DynArray();
31 this.cmpr = cmpr;
32 }
33
34 public SortedVector( ObjectComparator cmpr, int capacity ) {
35 data = new DynArray( capacity );
36 this.cmpr = cmpr;
37 }
38
39 public int addElement( Object obj ) throws ObjectInvalid {
40 cmpr.element( obj );
41 int pos = find_nearest();
42 if ( pos > -1 && cmpr.compare_with( data.elementAt(0) ) >= 0 ) {
43 while( pos < data.size() && cmpr.compare_with( data.elementAt(pos) ) >= 0 ) {
44 pos++;
45 }
46 } else {
47 pos = 0;
48 }
49 data.insertElementAt( obj, pos );
50 return pos;
51 }
52
53 public int size() {
54 return data.size();
55 }
56
57 public Object elementAt( int index ) {
58 return data.elementAt( index );
59 }
60
61 public Enumeration elements() {
62 return data.elements();
63 }
64
65 public Object removeElementAt( int index ){
66 Object obj = data.elementAt( index );
67 data.removeElementAt( index );
68 return obj;
69 }
70
71 public void removeAllElements() {
72 data.removeAllElements();
73 }
74
75 public int indexOf( Object obj ) throws ObjectInvalid {
76 cmpr.element( obj );
77 int i = find_nearest();
78 if( i == data.size() ) {
79 i--;
80 }
81 if( i >= data.size() || i<0 ){
82 return -1;
83 }
84 int j = i;
85 while( j >= 0 && cmpr.compare_with( data.elementAt(j) ) <= 0 ){
86 if( cmpr.equal( data.elementAt( j ) ) ){
87 return j;
88 }
89 j--;
90 }
91 j = i+1;
92 while( j < data.size() && cmpr.compare_with( data.elementAt(j) ) >= 0 ){
93 if( cmpr.equal( data.elementAt( j ) ) ){
94 return j;
95 }
96 j++;
97 }
98 return -1;
99 }
100
101 public void setElementAt( Object obj, int index ) throws ObjectInvalid {
102 if( !isIndexValid( index, obj ) ) {
103 throw new ObjectInvalid();
104 }
105 data.setElementAt( obj, index );
106 }
107
108 public boolean isIndexValid( int index, Object obj ) throws ObjectInvalid {
109 cmpr.element( obj );
110 if( data.size() == 0 ){
111 return true;
112 }
113 int i = find_nearest();
114 if( cmpr.equal( data.elementAt(i) ) ){
115 return true;
116 } else if( ( i==0 || cmpr.compare_with( data.elementAt(i-1) ) >= 0 )
117 && ( i==data.size() || cmpr.compare_with( data.elementAt(i) ) <= 0 ) ){
118 return true;
119 }
120 return false;
121 }
122
123 public boolean insertElementAt( Object obj, int index ) throws ObjectInvalid {
124 if( isIndexValid( index, obj ) ){
125 data.insertElementAt( obj, index );
126 }
127 return false;
128 }
129
130 private int find_nearest() throws ObjectInvalid {
131 if( data.size() == 0 ){
132 return -1;
133 }
134 int first = 0;
135 if( cmpr.compare_with( data.elementAt(first) ) <= 0 ){
136 return first;
137 }
138 int last = data.size()-1;
139 if( cmpr.compare_with( data.elementAt(last) ) >= 0 ){
140 return data.size();
141 }
142
143 if ( first == last ) {
144 if ( cmpr.compare_with( data.elementAt(last) ) <= 0 ) {
145 return first;
146 } else {
147 return first+1;
148 }
149 }
150
151 int result = 0;
152 int pos = first;
153 while( first < last ){
154 pos = (first+last)/2;
155 if ( pos == first ) {
156 return ++pos;
157 }
158 if ( pos == last ) {
159 return ++pos;
160 }
161 result = cmpr.compare_with( data.elementAt(pos) );
162 if( result == 0 ){
163 return ++pos;
164 } else if( result > 0 ){
165 first = pos;
166 } else {
167 last = pos;
168 }
169 }
170 return pos;
171 }
172
173 }
174
175
176
177
178 |
Popular Tags |
Java API By Example, From Geeks To Geeks.