Robust/src/Benchmarks/SingleTM/LeeRouting/WorkQueue.java

   1 /*
   2  * BSD License
   3  *
   4  * Copyright (c) 2007, The University of Manchester (UK)
   5  *
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  *     - Redistributions of source code must retain the above copyright
  13  *       notice, this list of conditions and the following disclaimer.
  14  *     - Redistributions in binary form must reproduce the above
  15  *       copyright notice, this list of conditions and the following
  16  *       disclaimer in the documentation and/or other materials provided
  17  *       with the distribution.
  18  *     - Neither the name of the University of Manchester nor the names
  19  *       of its contributors may be used to endorse or promote products
  20  *       derived from this software without specific prior written
  21  *       permission.
  22
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  29  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  30  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  31  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  32  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  33  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 public class WorkQueue {
  37
  38         public int x1, y1, x2, y2, nn;
  39
  40         public WorkQueue next;
  41
  42         WorkQueue() {
  43                 next = null;
  44         }
  45
  46         WorkQueue(int xx1, int yy1, int xx2, int yy2, int n) {
  47                 x1 = xx1;
  48                 y1 = yy1;
  49                 x2 = xx2;
  50                 y2 = yy2;
  51                 nn = n;
  52         }
  53
  54         public WorkQueue enQueue(int x1, int y1, int x2, int y2, int n) {
  55                 WorkQueue q = new WorkQueue(x1, y1, x2, y2, n);
  56                 q.next = this.next;
  57                 return q;
  58         }
  59
  60         public WorkQueue deQueue() {
  61                 WorkQueue q = this.next;
  62                 this.next = this.next.next;
  63                 return q;
  64         }
  65
  66         public boolean less(int xx1, int yy1, int xx2, int yy2) {
  67                 return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > (xx2 - xx1)
  68                                 * (xx2 - xx1) + (yy2 - yy1) * (yy2 - yy1);
  69         }
  70
  71         public boolean pass() {
  72                 boolean done = true;
  73                 WorkQueue ent = this;
  74                 WorkQueue a = ent.next;
  75                 while (a.next != null) {
  76                         WorkQueue b = a.next;
  77                         if (a.less(b.x1, b.y1, b.x2, b.y2)) {
  78                                 ent.next = b;
  79                                 a.next = b.next;
  80                                 b.next = a;
  81                                 done = false;
  82                         }
  83                         ent = a;
  84                         a = b;
  85                         b = b.next;
  86             // System.out.print("#");
  87                 }
  88                 return done;
  89         }
  90
  91         public void sort() {
  92                 while (!pass())
  93                         ;
  94         }
  95
  96         public WorkQueue enQueue(WorkQueue q) {
  97                 WorkQueue n = new WorkQueue(q.x1, q.y1, q.x2, q.y2, q.nn);
  98                 n.next = this.next;
  99                 return n;
 100         }
 101
 102         public int length() {
 103                 WorkQueue curr = this.next;
 104                 int retval = 0;
 105
 106                 while(curr!=null) {
 107                         retval++;
 108                         curr = curr.next;
 109                 }
 110
 111                 return retval;
 112         }
 113
 114 }