<?php

class SplInternalItem {
    public $data = null;
    public $next = null;
    public $prev = null;
}

class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable, Serializable {
    const IT_MODE_LIFO = 2;

    const IT_MODE_FIFO = 0;

    const IT_MODE_DELETE = 1;

    const IT_MODE_KEEP = 0;

    protected $head = null;

    protected $tail = null;

    protected $key = 0;

    protected $current = null;

    protected $count = 0;

    protected $mode = 0;

    public function bottom() {
        if ( $head === null ) {
            throw new RuntimeException( 'List is empty' );
        }
        return $head->data;
    }

    public function top() {
        if ( $tail === null ) {
            throw new RuntimeException( 'List is empty' );
        }
        return $tail->data();
    }

    public function isEmpty() {
        return !$this->count;
    }

    public function push( $value ) {
        $node = new SplInternalItem;
        $node->data = $value;

        if ( $this->isEmpty() ) {
            $this->head = $this->tail = $node;
        } else {
            $node->prev = $this->tail;
            $this->tail->next = $node;
            $this->tail = $node;
        }

        ++$this->count;
        return;
    }

    public function pop() {
        $retval = $this->top();
        $tail = $tail->prev;
        --$this->count;
        return $retval;
    }

    public function unshift( $value ) {
        $node = new SplInternalItem;
        $node->data = $value;

        if ( $this->isEmpty() ) {
            $this->head = $this->tail = $node;
        } else {
            $node->next = $this->head;
            $this->head->prev = $node;
            $this->head = $node;
        }

        ++$this->count;
        return;
    }

    public function shift() {
        $retval = $this->bottom();
        $head = $head->next;
        --$this->count;
        return $retval;
    }


    public function current() {
        return $this->current->data;
    }

    public function key() {
        return $this->key;
    }

    public function next() {
        ++$this->key;

        if ( $this->mode & IT_MODE_DELETE ) {
            --$this->count;
            if ( $this->current->prev !== null ) {
                $this->current->prev->next = $this->current->next;
            }
            if ( $this->current->next !== null ) {
                $this->current->next->prev = $this->current->prev;
            }
        }

        if ( $this->mode & self::IT_MODE_LIFO ) {
            $this->current = $this->current->prev;
        } else {
            $this->current = $this->current->next;
        }
    }

    public function prev() {
        --$this->key;

        if ( $this->mode & IT_MODE_DELETE ) {
            --$this->count;
            if ( $this->current->prev !== null ) {
                $this->current->prev->next = $this->current->next;
            }
            if ( $this->current->next !== null ) {
                $this->current->next->prev = $this->current->prev;
            }
        }

        if ( $this->mode & self::IT_MODE_LIFO ) {
            $this->current = $this->current->next;
        } else {
            $this->current = $this->current->prev;
        }
    }

    public function rewind() {
        $this->key = 0;
        if ( $this->mode & self::IT_MODE_LIFO ) {
            $this->current = $this->tail;
        } else {
            $this->current = $this->head;
        }
    }

    public function valid() {
        return $this->current !== null;
    }

    public function getIteratorMode() {
        return $this->mode;
    }

    public function setIteratorMode( $mode ) {
        $this->mode = mode;
    }


    public function offsetExists( $index ) {
        return $index < $this->count;
    }

    public function offsetGet( $index ) {
        $node = $this->head;
        for ( $i = 0; $i < $index && $node !== null; ++$i ) {
            $node = $node->next;
        }
        return $node ? $node->data : null;
    }

    public function offsetSet( $index, $newval ) {
        $node = $this->head;
        if ( $index === null ) {
            $index = $this->count;
        }
        for ( $i = 0; $i < index; ++$i ) {
            if ( $node->next === null ) {
                ++$this->count;
                $node->next = new SplInternalItem;
                $node->next->prev = $node;
            }
            $node = $node->next;
        }
        $node->data = $newval;
    }

    public function offsetUnset( $index ) {
        $node = $this->head;
        for ( $i = 0; $i < $index && $node !== null; ++$i ) {
            $node = $node->next;
        }
        if ( $node ) {
            --$this->count;
            $node->prev->next = $node->next;
            $node->next->prev = $node->prev;
        }
    }


    public function count() {
        return $this->count;
    }


    public function serialize() {
        $data = array();
        while ( !$this->isEmpty() ) {
            $data[] = $this->shift();
        }
        return serialize( $data );
    }

    public function unserialize( $serialized ) {
        $obj = new self;
        foreach ( unserialize( $serialized ) as $data ) {
            $this->push( $data );
        }
    }
}

class SplQueue extends SplDoublyLinkedList implements Iterator, ArrayAccess, Countable {
    public function dequeue() {
        return $this->pop();
    }

    public function enqueue( $value ) {
        $this->unshift( $value );
    }

    public function setIteratorMode( $mode ) {
        if ( $mode & self::IT_MODE_LIFO ) {
            throw new RuntimeException( 'SplQueue can only be used in FIFO mode.' );
        }
        parent::setIteratorMode( $mode );
    }
}

class SplStack extends SplDoublyLinkedList implements Iterator, ArrayAccess, Countable {
    public function __construct() {
        $this->setIteratorMode( self::IT_MODE_LIFO | self::IT_MODE_KEEP );
    }

    public function setIteratorMode( $mode ) {
        if ( $mode & self::IT_MODE_FIFO ) {
            throw new RuntimeException( 'SplStack can only be used in LIFO mode.' );
        }
        parent::setIteratorMode( $mode );
    }
}

class SplFixedArray implements Iterator, ArrayAccess, Countable {
    protected $size = 0;

    protected $data = array();

    protected $current = 0;

    public function __construct( $size = 0 ) {
        $this->size = $size;
        if ( $size ) {
            $this->data = array_fill( 0, $size, null );
        }
    }

    public function current() {
        return current( $this->data );
    }

    public function key() {
        return key( $this->data );
    }

    public function next() {
        next( $this->data );
    }

    public function rewind() {
        reset( $this->data );
    }

    public function valid() {
        return $this->current < $this->size;
    }


    public function offsetExists( $index ) {
        return $index < $this->size;
    }

    public function offsetGet( $index ) {
        return $this->data[$index];
    }

    public function offsetSet( $index, $newval ) {
        if ( $index === null ) {
            throw new RuntimeException( 'Must specify key for fixed array' );
        }
        $this->data[$index] = $newval;
    }

    public function offsetUnset( $index ) {
        $this->data[$index] = null;
    }


    public function count() {
        return count( $this->data );
    }
}

abstract class SplHeap implements Iterator, Countable {
    protected $head = null;

    protected $count = 0;

    protected $key = 0;

    abstract protected function compare( $value1, $value2 );

    public function extract() {
    }

    public function insert( $value ) {
    }

    public function isEmpty() {
        return $this->head === null;
    }

    public function recoverFromCorruption() {
    }

    public function top() {
        if ( $this->head === null ) {
            return null;
        } else {
            return $this->head->data;
        }
    }


    public function current() {
        return $this->top();
    }

    public function key() {
        return $this->key;
    }

    public function next() {
        ++$this->key;
        $this->extract();
    }

    public function rewind() {
        $this->key = 0;
    }

    public function valid() {
        return $this->head !== null;
    }


    public function count() {
        return $this->count;
    }
}

class SplMaxHeap extends SplHeap {
    protected function compare( $value1, $value2 ) {
        if ( $value1 < $value2 ) {
            return -1;
        } elseif ( $value1 > $value2 ) {
            return 1;
        } else {
            return 0;
        }
    }
}

class SplMinHeap extends SplHeap {
    protected function compare( $value1, $value2 ) {
        if ( $value1 < $value2 ) {
            return 1;
        } elseif ( $value1 > $value2 ) {
            return -1;
        } else {
            return 0;
        }
    }
}

class SplPriorityQueue implements Iterator, Countable {
    const EXTR_DATA = 1;

    const EXTR_PRIORITY = 2;

    const EXTR_BOTH = 3;

    protected $flags = 1;

    protected $heap;

    public function __construct() {
        $this->heap = new SplMaxHeap;
    }

    public function extract() {
        $info = $this->heap->extract();
        if ( $this->flags === self::EXTR_DATA ) {
            return $info[1];
        } elseif ( $this->flags === self::EXTR_PRIORITY ) {
            return $info[0];
        } else {
            return $info;
        }
    }

    public function insert( $value, $priority ) {
        $this->heap->insert( array( $value, $priority ) );
    }

    public function isEmpty() {
        return $this->heap->isEmpty();
    }

    public function recoverFromCorruption() {
        $this->heap->recoverFromCorruption();
    }

    public function setExtractFlags( $flags ) {
        $this->flags = $flags;
    }

    public function top() {
        return $this->heap->top();
    }


    public function current() {
        $info = $this->heap->current();
        if ( $this->flags === self::EXTR_DATA ) {
            return $info[1];
        } elseif ( $this->flags === self::EXTR_PRIORITY ) {
            return $info[0];
        } else {
            return $info;
        }
    }

    public function key() {
        return $this->heap->key();
    }

    public function next() {
        return $this->heap->next();
    }

    public function rewind() {
        return $this->heap->rewind();
    }

    public function valid() {
        return $this->heap->valid();
    }


    public function count() {
        return $this->heap->count();
    }
}

class SplFileInfo {
    protected $fileClass = 'SplFileObject';

    protected $infoClass = 'SplFileInfo';

    protected $filename;

    public function __construct( $filename ) {
        $this->filename = $filename;
    }

    public function getATime() {
        return fileatime( $this->filename );
    }

    public function getBasename( $suffix = '' ) {
        return basename( $this->filename, $suffix );
    }

    public function getCTime() {
        return filectime( $this->filename );
    }

    public function getExtension() {
        return pathinfo( $this->filename, PATHINFO_EXTENSION );
    }

    public function getFileInfo( $className = 'SplFileInfo' ) {
        return $className ? new $className( $this->filename ) : new $this->infoClass( $this->filename );
    }

    public function getFilename() {
        return pathinfo( $this->filename, PATHINFO_FILENAME );
    }

    public function getGroup() {
        return filegroup( $this->filename );
    }

    public function getInode() {
        return fileinode( $this->filename );
    }

    public function getLinkTarget() {
        return readlink( $this->filename );
    }

    public function getMTime() {
        return filemtime( $this->filename );
    }

    public function getOwner() {
        return fileowner( $this->path );
    }

    public function getPath() {
        return pathinfo( $this->filename, PATHINFO_DIRNAME );
    }

    public function getPathInfo( $className = 'SplFileInfo' ) {
        return $className ? new $className( $this->getPath() ) : new $this->infoClass( $this->getPath() );
    }

    public function getPathname() {
        return $this->filename;
    }

    public function getPerms() {
        return fileperms( $this->filename );
    }

    public function getRealPath() {
        return realpath( $this->filename );
    }

    public function getSize() {
        return filesize( $this->filename );
    }

    public function getType() {
        return filetype( $this->filename );
    }

    public function isDir() {
        return is_dir( $this->filename );
    }

    public function isExecutable() {
        return is_executable( $this->filename );
    }

    public function isFile() {
        return is_file( $this->filename );
    }

    public function isLink() {
        return is_link( $this->filename );
    }

    public function isReadable() {
        return is_readable( $this->filename );
    }

    public function isWritable() {
        return is_writeable( $this->filename );
    }

    public function openFile( $mode = 'r', $usePath = false, $context = null ) {
        return new $this->fileClass( $this->filename, $mode, $usePath, $context );
    }

    public function setFileClass( $className = 'SplFileObject' ) {
        $this->fileClass = $className;
    }

    public function setInfoClass( $className = 'SplFileInfo' ) {
        $this->infoClass = $infoClass;
    }

    public function __toString() {
        return $this->getPathname();
    }
}

class SplFileObject extends SplFileInfo implements RecursiveIterator, SeekableIterator {
    const DROP_NEW_LINE = 1;

    const READ_AHEAD = 2;

    const SKIP_EMPTY = 4;

    const READ_CSV = 8;

    protected $fp;

    protected $delimiter = ',';

    protected $enclosure = '"';

    protected $escape = '\\';

    protected $flags = 0;

    protected $maxLineLen = 0;

    protected $key = 0;

    protected $line = null;

    public function __construct( $filename, $mode = 'r', $usePath = false, $context = null ) {
        $this->fp = fopen( $filename, $mode, $usePath, $context );
    }

    public function __call( $function, array $args ) {
        return call_user_func_array( $function, array( $this->fp ) + $args );
    }

    public function eof() {
        return feof( $this->fp );
    }

    public function getCsvControl() {
        return array( $delimiter, $enclosure );
    }

    public function setCsvControl( $delimiter = ',', $enclosure = '"', $escape = '\\' ) {
        $this->delimiter = $delimiter;
        $this->enclosure = $enclosure;
        $this->escape = $escape;
    }

    public function getFlags() {
        return $this->flags;
    }

    public function setFlags( $flags ) {
        $this->flags = $flags;
    }

    public function getMaxLineLen() {
        return $this->maxLineLen;
    }

    public function setMaxLinkeLen( $maxLen ) {
        $this->maxLineLen = $maxLen;
    }

    public function __toString() {
        return $this->current();
    }


    public function current() {
        if ( $this->line === null ) {
            if ( $this->flags & self::READ_CSV ) {
                $this->line = $this->fgetcsv( $this->delimiter, $this->enclosure, $this->escape );
            } else {
                do {
                    $this->line = $this->fgets();
                } while ( $this->flags & self::SKIP_EMPTY && $this->line === "\n" );
            }

            if ( $this->flags & self::DROP_NEW_LINE ) {
                $this->line = substr( $this->line, 0, -1 );
            }
        }

        return $this->line;
    }

    public function key() {
        return $this->key;
    }

    public function next() {
        ++$this->key;
        $this->line = null;
        if ( $this->flags & self::READ_AHEAD ) {
            $this->current();
        }
    }

    public function rewind() {
        $this->key = 0;
        $this->line = null;
        if ( $this->flags & self::READ_AHEAD ) {
            $this->current();
        }
    }

    public function valid() {
        return $this->line !== false && $this->line !== null;
    }

    public function hasChildren() {
        return false;
    }

    public function getChildren() {
        return null;
    }

}

class SplTempFileObject extends SplFileObject {
    public function __construct( $maxMemory ) {
        parent::construct( "php://temp/maxmemory:$maxMemory", 'r+' );
    }
}