1 52 53 package com.go.trove.util; 54 55 import java.util.*; 56 57 71 public class SortedArrayList extends ArrayList { 72 73 77 private Comparator mComparator = null; 78 79 84 public SortedArrayList(Comparator c) { 85 mComparator = c; 86 } 87 88 public SortedArrayList() { 89 } 90 91 public SortedArrayList(Collection c) { 92 addAll(c); 93 } 94 95 98 public Comparator comparator() { 99 return mComparator; 100 } 101 102 107 public boolean add(Object o) { 108 int idx = 0; 111 if(!isEmpty()) { 112 idx = findInsertionPoint(o); 113 } 114 115 try { 116 super.add(idx, o); 117 } 118 catch(IndexOutOfBoundsException e) { 119 return false; 120 } 121 return true; 122 } 123 124 129 public boolean addAll(Collection c) { 130 Iterator i = c.iterator(); 131 boolean changed = false; 132 boolean ret; 133 while(i.hasNext()) { 134 ret = add(i.next()); 135 if(!changed) { 136 changed = ret; 137 } 138 } 139 return changed; 140 } 141 142 146 public Object lastElement() throws NoSuchElementException { 147 if(isEmpty()) { 148 throw new NoSuchElementException(); 149 } 150 151 return get(size()-1); 152 } 153 154 159 public int findInsertionPoint(Object o) { 160 return findInsertionPoint(o, 0, size()-1); 161 } 162 163 167 170 public void add(int index, Object element) { 171 System.out.println("add"); 172 throw new UnsupportedOperationException ("add(int index, Object element is not Supported"); 173 } 174 175 178 public Object set(int index, Object element) { 179 throw new UnsupportedOperationException ("set(int index, Object element) is not Supported"); 180 } 181 182 185 public boolean addAll(int index, Collection c) { 186 throw new UnsupportedOperationException ("addAll(int index, Collection c) is not Supported"); 187 } 188 189 193 201 private int compare(Object k1, Object k2) { 202 return (mComparator==null ? ((Comparable )k1).compareTo(k2) 203 : mComparator.compare(k1, k2)); 204 } 205 206 214 private int findInsertionPoint(Object o, int startIndex, int endIndex) { 215 216 int halfPt = ((endIndex - startIndex)/2) + startIndex; 217 int delta = compare(get(halfPt), o); 218 219 if(delta < 0) { 220 endIndex = halfPt; 221 } 222 else if(delta > 0) { 223 startIndex = halfPt; 224 } 225 else { 226 return halfPt; 228 } 229 230 if((endIndex - startIndex) <= 1) { 232 return endIndex+1; 234 } 235 236 return findInsertionPoint(o, startIndex, endIndex); 237 } 238 } 239 | Popular Tags |