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.apache.kahadb.util; 018 019 import java.util.ArrayList; 020 021 /** 022 * Provides a list of LinkedNode objects. 023 * 024 * @author chirino 025 */ 026 public class LinkedNodeList<T extends LinkedNode<T>> { 027 028 T head; 029 int size; 030 031 public LinkedNodeList() { 032 } 033 034 public boolean isEmpty() { 035 return head == null; 036 } 037 038 public void addLast(T node) { 039 node.linkToTail(this); 040 } 041 042 public void addFirst(T node) { 043 node.linkToHead(this); 044 } 045 046 public T getHead() { 047 return head; 048 } 049 050 public T getTail() { 051 return head.prev; 052 } 053 054 public void clear() { 055 while (head != null) { 056 head.unlink(); 057 } 058 } 059 060 public void addLast(LinkedNodeList<T> list) { 061 if (list.isEmpty()) { 062 return; 063 } 064 if (head == null) { 065 head = list.head; 066 reparent(list); 067 } else { 068 getTail().linkAfter(list); 069 } 070 } 071 072 public void addFirst(LinkedNodeList<T> list) { 073 if (list.isEmpty()) { 074 return; 075 } 076 if (head == null) { 077 reparent(list); 078 head = list.head; 079 list.head = null; 080 } else { 081 getHead().linkBefore(list); 082 } 083 } 084 085 public T reparent(LinkedNodeList<T> list) { 086 size += list.size; 087 T n = list.head; 088 do { 089 n.list = this; 090 n = n.next; 091 } while (n != list.head); 092 list.head = null; 093 list.size = 0; 094 return n; 095 } 096 097 /** 098 * Move the head to the tail and returns the new head node. 099 * 100 * @return 101 */ 102 public T rotate() { 103 if( head ==null ) 104 return null; 105 return head = head.getNextCircular(); 106 } 107 108 /** 109 * Move the head to the tail and returns the new head node. 110 * 111 * @return 112 */ 113 public void rotateTo(T head) { 114 assert head!=null: "Cannot rotate to a null head"; 115 assert head.list == this : "Cannot rotate to a node not linked to this list"; 116 this.head = head; 117 } 118 119 public int size() { 120 return size; 121 } 122 123 @Override 124 public String toString() { 125 StringBuilder sb = new StringBuilder(); 126 sb.append("["); 127 boolean first=true; 128 T cur = getHead(); 129 while( cur!=null ) { 130 if( !first ) { 131 sb.append(", "); 132 } 133 sb.append(cur); 134 first=false; 135 cur = cur.getNext(); 136 } 137 sb.append("]"); 138 return sb.toString(); 139 } 140 141 /** 142 * Copies the nodes of the LinkedNodeList to an ArrayList. 143 * @return 144 */ 145 public ArrayList<T> toArrayList() { 146 ArrayList<T> rc = new ArrayList<T>(size); 147 T cur = head; 148 while( cur!=null ) { 149 rc.add(cur); 150 cur = cur.getNext(); 151 } 152 return rc; 153 } 154 }