/**

 * Java RTP Library (jlibrtp)

 * Copyright (C) 2006 Arne Kepp

 * 

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 * 

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

 */

package jlibrtp;

/**

 * A PktBuffer stores packets either for buffering purposes,

 * or because they need to be assimilated to create a complete frame.

 * 

 * This behavior can be controlled through rtpSession.pktBufBehavior()

 * 

 * It optionally drops duplicate packets.

 * 

 * Note that newest is the most recently received, i.e. highest timeStamp

 * Next means new to old (from recently received to previously received) 

 * 

 * @author Arne Kepp

 */

public class PktBuffer {

	/** The RTPSession holds information common to all packetBuffers, such as max size */

	RTPSession rtpSession;

	/** SSRC of the the participant that this buffer is for */

	long SSRC;

	/** The parent participant */

	Participant p;

	/** The length of the buffer */

	int length = 0;

	/** The oldest, least recently received, packet */

	PktBufNode oldest = null;

	/** The newest, most recently received, packet */

	PktBufNode newest = null;

	/** The last sequence number received */

	int lastSeqNumber = -1;

	/** The last timestamp */

	long lastTimestamp = -1;

	/** 

	 * Creates a new PktBuffer, a linked list of PktBufNode

	 * 

	 * @param rtpSession the parent RTPSession

	 * @param p the participant to which this packetbuffer belongs.

	 * @param aPkt The first RTP packet, to be added to the buffer 

	 */

	protected PktBuffer(RTPSession rtpSession, Participant p, RtpPkt aPkt) {

		this.rtpSession = rtpSession;

		this.p = p;

		SSRC = aPkt.getSsrc();

		PktBufNode newNode = new PktBufNode(aPkt);

		oldest = newNode;

		newest = newNode;

		//lastSeqNumber = (aPkt.getSeqNumber() - 1);

		//lastTimestamp = aPkt.getTimeStamp();

		length = 1;

	}

	/**

	 * Adds a packet, this happens in constant time if they arrive in order.

	 * Optimized for the case where each pkt is a complete frame.

	 * 

	 * @param aPkt the packet to be added to the buffer.

	 * @return integer, negative if operation failed (see code)

	 */

	protected synchronized int addPkt(RtpPkt aPkt) {

		if(aPkt == null) {

			System.out.println("! PktBuffer.addPkt(aPkt) aPkt was null");

			return -5;

		}

		long timeStamp = aPkt.getTimeStamp();

		if(RTPSession.rtpDebugLevel > 7) {

			System.out.println("-> PktBuffer.addPkt() , length:" + length + " , timeStamp of Pkt: " + Long.toString(timeStamp));

		}

		PktBufNode newNode = new PktBufNode(aPkt);

		if(aPkt.getSsrc() != SSRC) {

			System.out.println("PktBuffer.addPkt() SSRCs don't match!");

		}

		int retVal = 0;

		if(this.rtpSession.pktBufBehavior > 0) {

			retVal = bufferedAddPkt(newNode);

		} else if(this.rtpSession.pktBufBehavior == 0) {

			retVal = filteredAddPkt(newNode);

		} else if(this.rtpSession.pktBufBehavior == -1) {

			retVal = unfilteredAddPkt(newNode);

		}

		if(RTPSession.rtpDebugLevel > 7) {

			if(RTPSession.rtpDebugLevel > 10) {

				this.debugPrint();

			}

			System.out.println("<- PktBuffer.addPkt() , length:" + length + " returning " + retVal);

		}

		return retVal;

	}

	/**

	 * Adds packets in the same order that they arrive,

	 * doesn't do any filering or processing.

	 * 

	 * @param newNode the node to add to the packet buffer

	 * @return 0 if everything is okay, -1 otherwise

	 */

	private int unfilteredAddPkt(PktBufNode newNode) {

		if(RTPSession.rtpDebugLevel > 8) {

			System.out.println("<->    PktBuffer.unfilteredAddPkt()");

		}

		//No magic, just add to the end

		if(oldest != null) {

			oldest.nextFrameQueueNode = newNode;

			newNode.prevFrameQueueNode = oldest; 

			oldest = newNode;

		} else {

			oldest = newNode;

			newest = newNode;

		}

		return 0;

	}

	/**

	 * Takes care of duplicate packets

	 * 

	 * @param newNode the node to add to the packet buffer

	 * @return 0 if everything is okay, -1 otherwise

	 */

	private int filteredAddPkt(PktBufNode newNode) {

		if(RTPSession.rtpDebugLevel > 8) {

			System.out.println("<->    PktBuffer.filteredAddPkt()");

		}

		if(length == 0) {

			// The buffer was empty, this packet is the one and only.

			newest = newNode;

			oldest = newNode;

			length = 1;

		} else {

			// The packetbuffer is not empty.

			if(newNode.timeStamp > newest.timeStamp || newNode.seqNum > newest.seqNum && (newNode.seqNum - newest.seqNum) < 10) {

				// Packet came in order

				newNode.nextFrameQueueNode = newest;

				newest.prevFrameQueueNode = newNode;

				newest = newNode;

				length++;

			} else {

					if(RTPSession.rtpDebugLevel > 2) {

						System.out.println("PktBuffer.filteredAddPkt Dropped a packet due to lag! " +  newNode.timeStamp + " " 

								+ newNode.seqNum + " vs "+ oldest.timeStamp + " " + oldest.seqNum);

					}

					return -1;

			}

		}

		return 0;

	}

	/**

	 * Does most of the packet organization for the application.

	 * Packets are put in order, duplicate packets or late arrivals are discarded

	 * 

	 * If multiple packets make up a frame, these will also be organized

	 * by RTP timestamp and sequence number, and returned as a complete frame.

	 * 

	 * @param newNode the node to add to the packet buffer

	 * @return 0 if everything is okay, -1 otherwise

	 */

	private int bufferedAddPkt(PktBufNode newNode) {

		if(RTPSession.rtpDebugLevel > 8) {

			System.out.println("<->    PktBuffer.bufferedAddPkt()");

		}

		if(length == 0) {

			// The buffer was empty, this packet is the one and only.

			newest = newNode;

			oldest = newNode;

		} else {

			// The packetbuffer is not empty.

			if(newNode.timeStamp > newest.timeStamp || newNode.seqNum > newest.seqNum) {

				// Packet came in order

				newNode.nextFrameQueueNode = newest;

				newest.prevFrameQueueNode = newNode;

				newest = newNode;

			} else {

				//There are packets, we need to order this one right.

				if(! pktOnTime(newNode.timeStamp, newNode.seqNum) && rtpSession.pktBufBehavior > -1) {

					// We got this too late, can't put it in order anymore.

					if(RTPSession.rtpDebugLevel > 2) {

						System.out.println("PktBuffer.addPkt Dropped a packet due to lag! " +  newNode.timeStamp + " " 

								+ newNode.seqNum + " vs "+ oldest.timeStamp + " " + oldest.seqNum);

					}

					return -1;

				}

				//Need to do some real work, find out where it belongs (linear search from the back).

				PktBufNode tmpNode = newest;

				while(tmpNode.timeStamp > newNode.timeStamp) {

					tmpNode = tmpNode.nextFrameQueueNode;

				}

				if( tmpNode.timeStamp == newNode.timeStamp

						&& rtpSession.frameReconstruction

						&& newNode.seqNum != tmpNode.seqNum) {

					//Packet has same timestamp, presumably belongs to frame. Need to order within frame.

					if(RTPSession.rtpDebugLevel > 8) {

						System.out.println("Found pkt with existing timeStamp: " + newNode.timeStamp);

					}

					int ret = addToFrame(tmpNode, newNode);

					if(ret != 0) {

						return ret;

					}

				} else {

					// Check that it's not a duplicate

					if(tmpNode.timeStamp == newNode.timeStamp && newNode.seqNum == tmpNode.seqNum) {

						if(RTPSession.rtpDebugLevel > 2) {

							System.out.println("PktBuffer.addPkt Dropped a duplicate packet! " 

									+  newNode.timeStamp + " " + newNode.seqNum );

						}

						return -1;

					}

					// Insert into buffer

					newNode.nextFrameQueueNode = tmpNode;

					newNode.prevFrameQueueNode = tmpNode.prevFrameQueueNode;

					// Update the node behind

					if(newNode.prevFrameQueueNode != null) {

						newNode.prevFrameQueueNode.nextFrameQueueNode = newNode;

					}

					tmpNode.prevFrameQueueNode = newNode;

					if(newNode.timeStamp > newest.timeStamp) {

						newest = newNode; 

					}

				}

			}

		}

		// Update the length of this buffer

		length++;

		return 0;

	}

	/**

	 * 

	 * @param frameNode the node currently representing the frame in the packet buffer

	 * @param newNode the new node to be added to the frame

	 * @return 0 if no error, -2 if this is a duplicate packet

	 */

	private int addToFrame(PktBufNode frameNode, PktBufNode newNode) {

		// Node has same timeStamp, assume pkt belongs to frame

		if(frameNode.seqNum < newNode.seqNum) {

			// this is not the first packet in the frame

			frameNode.pktCount++;

			// Find the right spot

			while( frameNode.nextFrameNode != null 

					&& frameNode.nextFrameNode.seqNum < newNode.seqNum) {

				frameNode = frameNode.nextFrameNode;

			}

			// Check whether packet is duplicate

			if(frameNode.nextFrameNode != null 

					&& frameNode.nextFrameNode.seqNum == newNode.seqNum) {

				if(RTPSession.rtpDebugLevel > 2) {

					System.out.println("PktBuffer.addPkt Dropped a duplicate packet!");

				}

				return -2;

			}

			newNode.nextFrameNode = frameNode.nextFrameNode;

			frameNode.nextFrameNode = newNode;

		} else {

			// newNode has the lowest sequence number

			newNode.nextFrameNode = frameNode;

			newNode.pktCount = frameNode.pktCount + 1;

			//Update the queue

			if(frameNode.nextFrameQueueNode != null) {

				frameNode.nextFrameQueueNode.prevFrameQueueNode = newNode;

				newNode.nextFrameQueueNode = frameNode.nextFrameQueueNode;

				frameNode.nextFrameQueueNode = null;

			}

			if(frameNode.prevFrameQueueNode != null) {

				frameNode.prevFrameQueueNode.nextFrameQueueNode = newNode;

				newNode.prevFrameQueueNode = frameNode.prevFrameQueueNode;

				frameNode.prevFrameQueueNode = null;

			}

			if(newest.timeStamp == newNode.timeStamp) {

				newest = newNode;

			}

		}

		return 0;

	}

	/** 

	 * Checks the oldest frame, if there is one, sees whether it is complete.

	 * @return Returns null if there are no complete frames available.

	 */

	protected synchronized DataFrame popOldestFrame() {

		if(RTPSession.rtpDebugLevel > 7) {

			System.out.println("-> PktBuffer.popOldestFrame()");

		}

		if(RTPSession.rtpDebugLevel > 10) {

			this.debugPrint();

		}

		if(this.rtpSession.pktBufBehavior > 0) {

			return this.bufferedPopFrame();

		} else {

			return this.unbufferedPopFrame();

		}

	}

	/**

	 * Will return the oldest frame without checking whether it is in

	 * the right order, or whether we should wate for late arrivals.

	 * 

	 * @return the first frame on the queue, null otherwise

	 */

	private DataFrame unbufferedPopFrame() {

		if(oldest != null) {

			PktBufNode retNode = oldest;

			popFrameQueueCleanup(retNode, retNode.seqNum);

			return new DataFrame(retNode, this.p, 

					rtpSession.appIntf.frameSize(retNode.pkt.getPayloadType()));

		} else {

			return null;

		}

	}

	/**

	 * Only returns if the buffer is full, i.e. length exceeds

	 * rtpSession.pktBufBehavior, or if the next packet directly

	 * follows the previous one returned to the application.

	 * 

	 * @return first frame in order, null otherwise

	 */

	private DataFrame bufferedPopFrame() {

		PktBufNode retNode = oldest;

		/**

		 * Three scenarios:

		 * 1) There are no packets available

		 * 2) The first packet is vailable and in order

		 * 3) The first packet is not the next on in the sequence

		 * 		a) We have exceeded the wait buffer

		 * 		b) We wait

		 */

		//System.out.println(" Debug:" +(retNode != null) + " " + (retNode.seqNum == this.lastSeqNumber + 1)

		//		+ " " + ( retNode.seqNum == 0 ) + " " +  (this.length > this.rtpSession.maxReorderBuffer)

		//		+ " " + (this.lastSeqNumber < 0));

		// Pop it off, null all references.

		if( retNode != null && (retNode.seqNum == this.lastSeqNumber + 1 || retNode.seqNum == 0 

					|| this.length > this.rtpSession.pktBufBehavior || this.lastSeqNumber < 0)) {

			//if(tmpNode.pktCount == compLen) {

			if(RTPSession.rtpDebugLevel > 7) {

				System.out.println("<- PktBuffer.popOldestFrame() returns frame");

			}

			DataFrame df = new DataFrame(retNode, this.p, 

					rtpSession.appIntf.frameSize(oldest.pkt.getPayloadType()));

			//DataFrame df = new DataFrame(retNode, this.p, 1);

			popFrameQueueCleanup(retNode, df.lastSeqNum);

			return df;

		} else {

			// If we get here we have little to show for.

			if(RTPSession.rtpDebugLevel > 2) {

				System.out.println("<- PktBuffer.popOldestFrame() returns null " + retNode.seqNum + " " + this.lastSeqNumber);

				this.debugPrint();

			}

			return null;

		}

	}

	/**

	 * Cleans the packet buffer before returning the frame,

	 * i.e. making sure the queue has a head etc.

	 * 

	 * @param retNode the node that is about to be popped

	 * @param highestSeq the highest sequence number returned to the application

	 */

	private void popFrameQueueCleanup(PktBufNode retNode, int highestSeq) {

		if(1 == length) {

			//There's only one frame

			newest = null;

			oldest = null;

		} else {

			//There are more frames

			oldest = oldest.prevFrameQueueNode;

			oldest.nextFrameQueueNode = null;

		}

		// Update counters

		length--;

		//Find the highest sequence number associated with this timestamp

		this.lastSeqNumber = highestSeq;

		this.lastTimestamp = retNode.timeStamp;

	}

	/** 

	 * Returns the length of the packetbuffer.

	 * @return number of frames (complete or not) in packetbuffer.

	 */

	protected int getLength() {

		return length;

	}

	/**

	 * Checks whether a packet is not too late, i.e. the next packet has already been returned.

	 * @param timeStamp the RTP timestamp of the packet under consideration 

	 * @param seqNum the sequence number of the packet under consideration

	 * @return true if newer packets have not been handed to the application

	 */

	protected boolean pktOnTime(long timeStamp, int seqNum) {

		if(this.lastSeqNumber == -1) {

			// First packet

			return true;

		} else {			

			if(seqNum >= this.lastSeqNumber) {

				if(this.lastSeqNumber < 3 && timeStamp < this.lastTimestamp ) {

					return false;

				}

			} else {

				if(seqNum > 3 || timeStamp < this.lastTimestamp) {

					return false;

				}

			}

		}

		return true;

	}

	/** 

	 * Prints out the packet buffer, oldest node first (on top).

	 */

	protected void debugPrint() {

		System.out.println("PktBuffer.debugPrint() : length "+length+" SSRC "+SSRC+" lastSeqNum:"+lastSeqNumber);

		PktBufNode tmpNode = oldest;

		int i = 0;

		while(tmpNode != null) {

			//String str = tmpNode.timeStamp.toString();

			System.out.println("   " + i + " seqNum:"+tmpNode.seqNum+" timeStamp: " + tmpNode.timeStamp + " pktCount:" + tmpNode.pktCount );

			i++;

			tmpNode = tmpNode.prevFrameQueueNode;

		}

	}

}