src/main/gov/nasa/jpf/util/ObjectList.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.util;
  19
  20 import gov.nasa.jpf.JPFException;
  21 import gov.nasa.jpf.SystemAttribute;
  22
  23 import java.lang.reflect.InvocationTargetException;
  24 import java.lang.reflect.Method;
  25 import java.util.NoSuchElementException;
  26
  27 /**
  28  * a minimal container API that transparently handles Object lists which can
  29  * degenerate to single values that are stored directly. Value lists are
  30  * implemented by means of a private Node type, which is transparently handled
  31  * through the (static) ObjectList API
  32  *
  33  * No null objects can be stored in the list. No list can only contain a single
  34  * Node object
  35  *
  36  * Conversion between single objects and lists is done transparently if you
  37  * follow a pattern like:
  38  *
  39  *  Object attr; // either a single value or a list
  40  *  ..
  41  *  attr = ObjectList.remove(attr, v);
  42  *
  43  * If there is only one remaining value in a list, the corresponding Node will
  44  * be replaced with this value.
  45  *
  46  * iterators are LIFO.
  47  *
  48  * We assume that attribute collections are small, otherwise retrieval and
  49  * deletion with this API becomes rather inefficient
  50  *
  51  * NOTE: while ObjectList heads are stored in simple Object fields within the
  52  * user (and therefore could be just overwritten by simple assignments)
  53  * YOU SHOULD NOT DO THIS! Other extensions or JPF itself could rely on
  54  * current attributes. In case you have to change the whole list, use
  55  * set(oldAttrs,newAttr), which checks if there currently is a SystemAttribute
  56  * instance in the list, in which case it throws a JPFException unless the
  57  * new attibute value is also a gov.nasa.jpf.SystemAttribute instance. Use
  58  * forceSet(null) if you really have to remove lists with SystemAttributes
  59  *
  60  *
  61  * usage:
  62  *  Object attr;
  63  *  ...
  64  *    attr = AttrContainer.add( newAttr, attr);
  65  *
  66  *    MyAttr a = AttrContainer.getNext( MyAttr.class, attr);
  67  *
  68  *    attr = AttrContainer.remove( a, attr);
  69  *
  70  *    for (MyAttr a = ObjectList.getFirst(MyAttr.class, attr); a != null;
  71  *                a = ObjectList.getNext(MyAttr.class, attr, a)) {..}
  72  *
  73  */
  74 public abstract class ObjectList {
  75
  76   // there are no instances, this class is only a static API
  77   private ObjectList(){}
  78
  79   private static class Node implements Cloneable {
  80     Object data;
  81     Node next;
  82
  83     Node(Object data, Node next) {
  84       this.data = data;
  85       this.next = next;
  86     }
  87
  88     @Override
  89         public boolean equals(Object o){
  90       if (o instanceof Node){
  91         Node n = this;
  92         Node no = (Node)o;
  93         for (; n != null && no != null; n=n.next, no=no.next){
  94           if (!n.data.equals(no.data)){
  95             return false;
  96           }
  97         }
  98         return (n == null) && (no == null);
  99       } else {
 100         return false;
 101       }
 102     }
 103
 104     @Override
 105         protected Node clone(){
 106       try {
 107         return (Node)super.clone();
 108       } catch (CloneNotSupportedException cnsx){
 109         throw new RuntimeException("Node clone failed");
 110       }
 111     }
 112
 113     // recursively clone up to the node with the specified data
 114     public Node cloneWithReplacedData (Object oldData, Object newData){
 115       Node newThis = clone();
 116
 117       if (data.equals(oldData)){
 118         newThis.data = newData;
 119
 120       } else if (next != null) {
 121         newThis.next = next.cloneWithReplacedData(oldData, newData);
 122       }
 123
 124       return newThis;
 125     }
 126
 127     public Node cloneWithRemovedData (Object oldData){
 128       Node newThis = clone();
 129
 130       if (next != null){
 131         if (next.data.equals(oldData)){
 132           newThis.next = next.next;
 133         } else {
 134           newThis.next = next.cloneWithRemovedData( oldData);
 135         }
 136       }
 137
 138       return newThis;
 139     }
 140   }
 141
 142   public static class Iterator implements java.util.Iterator<Object>, Iterable<Object> {
 143     Object cur;
 144
 145     Iterator (Object head){
 146       cur = head;
 147     }
 148
 149     @Override
 150         public boolean hasNext() {
 151       return cur != null;
 152     }
 153
 154     @Override
 155         public Object next() {
 156       if (cur != null){
 157         if (cur instanceof Node){
 158           Node n = (Node)cur;
 159           cur = n.next;
 160           return n.data;
 161
 162         } else { // single attr value
 163           Object n = cur;
 164           cur = null;
 165           return n;
 166         }
 167       } else {
 168         throw new NoSuchElementException();
 169       }
 170     }
 171
 172     @Override
 173         public void remove() {
 174       // we can't remove since that would have to change the head field in the client
 175       throw new UnsupportedOperationException();
 176     }
 177
 178     @Override
 179         public java.util.Iterator<Object> iterator(){
 180       return this;
 181     }
 182   }
 183
 184   static final Iterator emptyIterator = new Iterator(null);
 185
 186   public static Iterator iterator (Object head){
 187     if (head == null){
 188       return emptyIterator;
 189     } else {
 190       return new Iterator(head);
 191     }
 192   }
 193
 194   public static class TypedIterator<A> implements java.util.Iterator<A>, Iterable<A> {
 195     Object cur;
 196     Class<A> type;
 197
 198     TypedIterator (Object head, Class<A> type){
 199       this.type = type;
 200       this.cur = null;
 201
 202       if (head instanceof Node){
 203         for (Node n = (Node)head; n != null; n = n.next){
 204           if (type.isAssignableFrom(n.data.getClass())) {
 205             cur = n;
 206             break;
 207           }
 208         }
 209       } else if (head != null) {
 210         if (type.isAssignableFrom(head.getClass())) {
 211           cur = head;
 212         }
 213       }
 214     }
 215
 216     @Override
 217         public boolean hasNext() {
 218       return cur != null;
 219     }
 220
 221     @Override
 222         public A next() {
 223
 224       if (cur != null){
 225         if (cur instanceof Node){
 226           Node nCur = (Node)cur;
 227           cur = null;
 228           A d = (A)nCur.data;
 229
 230           for (Node n=nCur.next; n != null; n=n.next){
 231             if (type.isAssignableFrom(n.data.getClass())){
 232               cur = n;
 233               break;
 234             }
 235           }
 236
 237           return d;
 238
 239         } else { // single attr value
 240           A d = (A)cur;
 241           cur = null;
 242           return d;
 243         }
 244
 245       } else {
 246         throw new NoSuchElementException();
 247       }
 248     }
 249
 250     @Override
 251         public void remove() {
 252       // we can't remove since that would have to change the head field in the client
 253       throw new UnsupportedOperationException();
 254     }
 255
 256     @Override
 257         public java.util.Iterator<A> iterator(){
 258       return this;
 259     }
 260   }
 261
 262   static final TypedIterator<Object> emptyTypedIterator = new TypedIterator<Object>(null,Object.class);
 263
 264   public static <A> TypedIterator<A> typedIterator (Object head, Class<A> type){
 265     if (head == null){
 266       return (TypedIterator<A>) emptyTypedIterator;
 267     } else {
 268       return new TypedIterator<A>(head, type);
 269     }
 270   }
 271
 272   /**
 273    * this returns either the first value if there is only one element, or
 274    * a Node list containing all the values in the order they are provided
 275    *
 276    * note - elements in the list occur in order of arguments, whereas normal
 277    * add() always adds at the head of the list
 278    */
 279   public static Object createList(Object... values){
 280     if (values.length == 0){
 281       return null;
 282
 283     } else if (values.length == 1){
 284       return values[0];
 285
 286     } else {
 287       Node node = null, next = null;
 288
 289       for (int i=values.length-1; i>=0; i--){
 290         node = new Node(values[i], next);
 291         next = node;
 292       }
 293       return node;
 294     }
 295   }
 296
 297   public static Object valueOf (Object o){
 298     return (o instanceof Node) ? ((Node)o).data : o;
 299   }
 300
 301   public static Object set (Object head, Object newHead){
 302     if (head == null || newHead instanceof SystemAttribute){
 303       return newHead; // Ok to overwrite
 304
 305     } else {
 306       if (head instanceof Node){
 307         // check if there is any SystemAttribute in the list
 308         for (Node n = (Node)head; n != null; n = n.next){
 309           if (n.data instanceof SystemAttribute){
 310             throw new JPFException("attempt to overwrite SystemAttribute with " + newHead);
 311           }
 312         }
 313
 314         return newHead; // Ok to overwrite
 315
 316       } else { // single data attribute
 317         if (head instanceof SystemAttribute){
 318           throw new JPFException("attempt to overwrite SystemAttribute with " + newHead);
 319         } else {
 320           return newHead; // Ok to overwrite
 321         }
 322       }
 323     }
 324   }
 325
 326   /**
 327    * just to provide a way to overwrite SystemAttributes (e.g. with null)
 328    */
 329   public static Object forceSet (Object head, Object newHead){
 330     return newHead;
 331   }
 332
 333
 334   public static Object add (Object head, Object data){
 335     if (head == null){
 336       return data;
 337
 338     } else if (data == null){
 339       return head;
 340
 341     } else {
 342       if (head instanceof Node){
 343         return new Node(data, (Node)head);
 344
 345       } else { // was single value -> turn into list
 346         Node p = new Node(head,null);
 347         return new Node(data, p);
 348       }
 349     }
 350   }
 351
 352   public static Object replace (Object head, Object oldData, Object newData){
 353     if (oldData == null){
 354       return head;
 355     }
 356     if (newData == null){
 357       return remove(head, oldData); // no null data, remove oldData
 358     }
 359
 360     if (head instanceof Node){
 361       // <2do> perhaps we should first check if it is there
 362       return ((Node)head).cloneWithReplacedData(oldData, newData);
 363
 364     } else { // single object
 365       if (oldData.equals(head)){
 366         return newData;
 367       } else {
 368         return head;
 369       }
 370     }
 371   }
 372
 373   public static Object remove (Object head, Object data){
 374     if (head == null || data == null){
 375       return head;
 376     }
 377
 378     if (head instanceof Node) {
 379       Node nh = (Node) head;
 380
 381       Node nhn = nh.next;
 382       if (nhn != null && nhn.next == null) { // 2 node case - reduce if found
 383         if (nh.data.equals(data)) {
 384           return nhn.data;
 385         } else if (nhn.data.equals(data)) {
 386           return nh.data;
 387         } else { // not there
 388           return head;
 389         }
 390       }
 391
 392       return nh.cloneWithRemovedData(data);
 393
 394     } else { // single object
 395       if (head.equals(data)){
 396         return null;
 397       } else {
 398         return head;
 399       }
 400     }
 401   }
 402
 403   public static boolean contains (Object head, Object o){
 404     if (head == null || o == null){
 405       return false;
 406
 407     } else if (head instanceof Node){
 408       for (Node n = (Node)head; n != null; n = n.next){
 409         if (o.equals(n.data)){
 410           return true;
 411         }
 412       }
 413       return false;
 414
 415     } else {
 416       return o.equals(head);
 417     }
 418   }
 419
 420   public static boolean containsType (Object head, Class<?> type){
 421     if (head == null || type == null){
 422       return false;
 423
 424     } else if (head instanceof Node){
 425       for (Node n = (Node)head; n != null; n = n.next){
 426         if (type.isAssignableFrom(n.data.getClass())){
 427           return true;
 428         }
 429       }
 430       return false;
 431
 432     } else {
 433       return type.isAssignableFrom(head.getClass());
 434     }
 435   }
 436
 437   //--- various qualifiers
 438
 439   public static boolean isList (Object head){
 440     return (head instanceof Node);
 441   }
 442
 443   public static boolean isEmpty(Object head){
 444     return head == null;
 445   }
 446
 447   public static int size(Object head){
 448     int len = 0;
 449
 450     if (head instanceof Node){
 451       for (Node n = (Node) head; n != null; n = n.next) {
 452         len++;
 453       }
 454     } else {
 455       if (head != null){
 456         len = 1;
 457       }
 458     }
 459
 460     return len;
 461   }
 462
 463   public static int numberOfInstances (Object head, Class<?> type){
 464     int len = 0;
 465
 466     if (head instanceof Node){
 467       for (Node n = (Node) head; n != null; n = n.next) {
 468         if (type.isInstance(n.data)){
 469           len++;
 470         }
 471       }
 472     } else {
 473       if (head != null){
 474         if (type.isInstance(head)){
 475           len = 1;
 476         }
 477       }
 478     }
 479
 480     return len;
 481
 482   }
 483
 484   public static Object get (Object head, int idx){
 485     if (head instanceof Node){
 486       int i=0;
 487       for (Node n = (Node) head; n != null; n = n.next) {
 488         if (i++ == idx){
 489           return n.data;
 490         }
 491       }
 492     } else {
 493       if (idx == 0){
 494         return head;
 495       }
 496     }
 497
 498     return null;
 499   }
 500
 501   public static Object getFirst(Object head){
 502     if (head instanceof Node){
 503       return ((Node)head).data;
 504     } else {
 505       return head;
 506     }
 507   }
 508
 509   public static Object getNext(Object head, Object prevData){
 510     if (head instanceof Node){
 511       Node n = (Node)head;
 512       if (prevData != null){
 513         for (; n != null && n.data != prevData; n=n.next);
 514         if (n == null){
 515           return null;
 516         } else {
 517           n = n.next;
 518         }
 519       }
 520
 521       return n.data;
 522
 523     } else {
 524       if (prevData == null){
 525         return head;
 526       }
 527     }
 528
 529     return null;
 530   }
 531
 532   public static <A> A getFirst (Object head, Class<A> type){
 533     if (head != null){
 534       if (type.isAssignableFrom(head.getClass())) {
 535         return (A) head;
 536       }
 537
 538       if (head instanceof Node) {
 539         for (Node n = (Node) head; n != null; n = n.next) {
 540           if (type.isAssignableFrom(n.data.getClass())) {
 541             return (A) n.data;
 542           }
 543         }
 544       }
 545     }
 546
 547     return null;
 548   }
 549
 550   public static <A> A getNext (Object head, Class<A> type, Object prevData){
 551     if (head instanceof Node){
 552       Node n = (Node)head;
 553       if (prevData != null){
 554         for (; n != null && n.data != prevData; n=n.next);
 555         if (n == null){
 556           return null;
 557         } else {
 558           n = n.next;
 559         }
 560       }
 561
 562       for (; n != null; n = n.next) {
 563         if (type.isAssignableFrom(n.data.getClass())) {
 564           return (A) n.data;
 565         }
 566       }
 567
 568     } else if (head != null) {
 569       if (prevData == null){
 570         if (type.isAssignableFrom(head.getClass())){
 571           return (A)head;
 572         }
 573       }
 574     }
 575
 576     return null;
 577   }
 578
 579   public static void hash (Object head, HashData hd){
 580     if (head instanceof Node){
 581       for (Node n = (Node) head; n != null; n = n.next) {
 582         hd.add(n.data);
 583       }
 584
 585     } else if (head != null){
 586       hd.add(head);
 587     }
 588   }
 589
 590   public static boolean equals( Object head1, Object head2){
 591     if (head1 != null){
 592       return head1.equals(head2);
 593     } else {
 594       return head2 == null; // both null is treated as equal
 595     }
 596   }
 597
 598   static Object cloneData (Object o) throws CloneNotSupportedException {
 599     if (o instanceof CloneableObject) {
 600       CloneableObject co = (CloneableObject) o;
 601       return co.clone();
 602
 603     } else if (o != null) {
 604       Class<?> cls = o.getClass();
 605       try {
 606         Method m = cls.getMethod("clone");
 607         // it can't be static because this would mask Object.clone()
 608         // since Class.getMethod() only returns publics, we don't have to set accessible
 609         return m.invoke(o);
 610
 611       } catch (NoSuchMethodException nsmx){
 612         // since Object.clone() would throw it (unless this is a Cloneable, in which
 613         // case there most probably is a public clone() and we would not have
 614         // gotten here), there is no use trying to call it
 615         throw new CloneNotSupportedException("no public clone(): " + o);
 616       } catch (InvocationTargetException ix){
 617         throw new RuntimeException( "generic clone failed: " + o, ix.getCause());
 618       } catch (IllegalAccessException iax){
 619         throw new RuntimeException("clone() not accessible: " + o);
 620       }
 621
 622     } else {
 623       return null;
 624     }
 625   }
 626
 627   static Node cloneNode (Node n) throws CloneNotSupportedException {
 628     if (n == null){
 629       return null;
 630     } else {
 631       return new Node( cloneData(n.data), cloneNode(n.next));
 632     }
 633   }
 634
 635   public static Object clone (Object head) throws CloneNotSupportedException {
 636     if (head instanceof Node){
 637       return cloneNode( (Node)head);
 638
 639     } else if (head != null){
 640       return cloneData( head);
 641
 642     } else {
 643       return null;
 644     }
 645
 646   }
 647 }