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    }