001 /** 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.fusesource.hawtdb.util.list; 018 019 import java.util.ArrayList; 020 import java.util.Iterator; 021 022 /** 023 * Provides a list of LinkedNode objects. 024 * 025 * @author <a href="http://hiramchirino.com">Hiram Chirino</a> 026 */ 027 public class LinkedNodeList<T extends LinkedNode<T>> implements Iterable<T> { 028 029 T head; 030 int size; 031 032 public LinkedNodeList() { 033 } 034 035 public boolean isEmpty() { 036 return head == null; 037 } 038 039 public void addLast(T node) { 040 node.linkToTail(this); 041 } 042 043 public void addFirst(T node) { 044 node.linkToHead(this); 045 } 046 047 public T getHead() { 048 return head; 049 } 050 051 public T getTail() { 052 if( head==null ) { 053 return null; 054 } 055 return head.prev; 056 } 057 058 public void clear() { 059 while (head != null) { 060 head.unlink(); 061 } 062 } 063 064 public void addLast(LinkedNodeList<T> list) { 065 if (list.isEmpty()) { 066 return; 067 } 068 if (head == null) { 069 head = list.head; 070 reparent(list); 071 } else { 072 getTail().linkAfter(list); 073 } 074 } 075 076 public void addFirst(LinkedNodeList<T> list) { 077 if (list.isEmpty()) { 078 return; 079 } 080 if (head == null) { 081 reparent(list); 082 head = list.head; 083 list.head = null; 084 } else { 085 getHead().linkBefore(list); 086 } 087 } 088 089 public T reparent(LinkedNodeList<T> list) { 090 size += list.size; 091 T n = list.head; 092 do { 093 n.list = this; 094 n = n.next; 095 } while (n != list.head); 096 list.head = null; 097 list.size = 0; 098 return n; 099 } 100 101 /** 102 * Move the head to the tail and returns the new head node. 103 * 104 * @return 105 */ 106 public T rotate() { 107 if( head ==null ) 108 return null; 109 return head = head.getNextCircular(); 110 } 111 112 /** 113 * Move the head to the tail and returns the new head node. 114 * 115 * @return 116 */ 117 public void rotateTo(T head) { 118 assert head!=null: "Cannot rotate to a null head"; 119 assert head.list == this : "Cannot rotate to a node not linked to this list"; 120 this.head = head; 121 } 122 123 public int size() { 124 return size; 125 } 126 127 @Override 128 public String toString() { 129 StringBuilder sb = new StringBuilder(); 130 sb.append("["); 131 boolean first=true; 132 T cur = getHead(); 133 while( cur!=null ) { 134 if( !first ) { 135 sb.append(", "); 136 } 137 sb.append(cur); 138 first=false; 139 cur = cur.getNext(); 140 } 141 sb.append("]"); 142 return sb.toString(); 143 } 144 145 /** 146 * Copies the nodes of the LinkedNodeList to an ArrayList. 147 * @return 148 */ 149 public ArrayList<T> toArrayList() { 150 ArrayList<T> rc = new ArrayList<T>(size); 151 T cur = head; 152 while( cur!=null ) { 153 rc.add(cur); 154 cur = cur.getNext(); 155 } 156 return rc; 157 } 158 159 /** 160 * Copies the nodes of the LinkedNodeList to the specified array. 161 * @return the passed array. 162 */ 163 public T[] toArray(T[] array) { 164 int pos = 0; 165 ArrayList<T> rc = new ArrayList<T>(size); 166 T cur = head; 167 while( cur!=null ) { 168 array[pos] = cur; 169 pos ++; 170 cur = cur.getNext(); 171 } 172 return array; 173 } 174 175 /** 176 * Copies the nodes of the LinkedNodeList to an ArrayList in reverse order. 177 * @return 178 */ 179 public ArrayList<T> toArrayListReversed() { 180 ArrayList<T> rc = new ArrayList<T>(size); 181 if( head != null ) { 182 T cur = getTail();; 183 while( cur!=null ) { 184 rc.add(cur); 185 cur = cur.getPrevious(); 186 } 187 } 188 return rc; 189 } 190 191 public Iterator<T> iterator() { 192 return new Iterator<T>() { 193 T next = getHead(); 194 private T last; 195 196 public boolean hasNext() { 197 return next!=null; 198 } 199 200 public T next() { 201 last = next; 202 next = last.getNext(); 203 return last; 204 } 205 206 public void remove() { 207 if( last==null ) { 208 throw new IllegalStateException(); 209 } 210 last.unlink(); 211 last=null; 212 } 213 }; 214 } 215 }