<?php
/*
 * $Horde: imp/lib/Tree.php,v 1.46.2.11 2003/01/16 22:29:06 jan Exp $
 *
 * Copyright 2000-2003 Chuck Hagenbuch <chuck@horde.org>
 * Copyright 2000-2003 Jon Parise <jon@horde.org>
 * Copyright 2000-2003 Anil Madhavapeddy <avsm@horde.org>
 *
 * See the enclosed file COPYING for license information (GPL). If you
 * did not receive this file, see http://www.fsf.org/copyleft/gpl.html.
 */

/* constants for mailboxElt attributes */
define('TreeElt_HAS_CHILDREN', 16);
define('TreeElt_IS_DISCOVERED', 32);
define('TreeElt_IS_OPEN', 64);

/**
 * The IMP_tree class provides a tree view of the folders in an
 * IMAP repository.  It provides access functions to iterate
 * through this tree and query information about individual
 * mailboxes.
 *
 * @author  Chuck Hagenbuch <chuck@horde.org>
 * @author  Jon Parise <jon@horde.org>
 * @author  Anil Madhavapeddy <avsm@horde.org>
 * @version $Revision: 1.46.2.11 $
 * @since   IMP 2.3
 * @package imp
 */
class IMP_Tree {

    var $tree;                          // associative array containing the mailbox tree.
    var $cur = '';                      // key of current element in the tree.
    var $first = '';                    // key of the first (top?) element in the tree (for traversal)
    var $delimiter = '/';               // hierarchy delimiter
    var $listcmd = 'imap_getmailboxes'; // default mailbox listing command
    var $prefix = '';                   // where we start listing folders
    var $dotfiles = true;               // show files beginning with a '.'?
    var $hierarchies = array();         // any additional hierarchies to show, such as UW's #shared/.

    function IMP_Tree($dotfiles = true, $hierarchies = array())
    {
        $this->dotfiles = $dotfiles;
        $this->hierarchies = $hierarchies;
    }

    /**
     * Update the cached folder information such as total and unread messages
     * It acts on the current folder only.
     */
    function updateMessageInfo()
    {
        global $imp;
        if (isset($this->tree) && is_array($this->tree) && !empty($this->cur)) {
            $sts = imap_status($imp['stream'], $this->cur, SA_MESSAGES | SA_UNSEEN);
            $this->tree[$this->cur]['messages'] = $sts->messages;
            if (isset($this->tree[$this->cur]['unseen'])) {
                $this->tree[$this->cur]['newmsg'] = $sts->unseen - $this->tree[$this->cur]['unseen'];
            }
            $this->tree[$this->cur]['unseen'] = isset($sts->unseen) ? $sts->unseen : 0;
        }
    }

    /**
     * Flush the cached folder information such as total and unread messages
     * to reset the cache.  It acts on the current folder only.
     */
    function flushMessageInfo()
    {
        if (isset($this->tree) && is_array($this->tree) && !empty($this->cur)) {
            foreach (array('messages','unseen','newmsg') as $field) {
                unset($this->tree[$this->cur][$field]);
            }
        }
    }

    /**
     * Iterate through the folder tree and expand every folder that has children
     * This function resets the folder pointer, so do not use it in the middle
     * of another iteration of the same IMAP_folder object
     */
    function expandAllFolders()
    {
        $mailbox = $this->head();
        while (isset($mailbox) && is_array($mailbox)) {
            if ($this->hasChildren($mailbox) && !$this->isOpen($mailbox)) {
                $this->expand($this->server . $mailbox['value']);
            }
            $mailbox = $this->next();
        }
    }

    /**
     * Iterate through the folder tree and expand every folder that has children
     * and is marked to be expanded in the preferences.
     * This function resets the folder pointer, so do not use it in the middle
     * of another iteration of the same IMAP_folder object
     */
    function expandAsLast()
    {
        $expanded = unserialize($GLOBALS['prefs']->getValue('expanded_folders'));
        $mailbox = $this->head();
        while (isset($mailbox) && is_array($mailbox)) {
            if ($this->hasChildren($mailbox) && !$this->isOpen($mailbox) && isset($expanded[$this->server . $mailbox['value']])) {
                $this->expand($this->server . $mailbox['value']);
            }
            $mailbox = $this->next();
        }
    }

    /**
     * Iterate through and expand every folder below a given starting
     * point.
     */
    function expandMailbox($root)
    {
        if (!isset($this->tree[$root])) {
            return false;
        }
        $oldcur = $this->cur;
        $this->cur = $root;

        $mailbox = $this->tree[$root];
        $startlevel = $mailbox['level'];
        if (!$this->hasChildren($mailbox)) {
            $this->cur = $oldcur;
            return;
        }
        if (!$this->isOpen($mailbox)) {
            $this->expand($this->server . $mailbox['value']);
        }
        $mailbox = $this->next();
        while (isset($mailbox) && is_array($mailbox) && $mailbox['level'] > $startlevel) {
            if ($this->hasChildren($mailbox) && !$this->isOpen($mailbox)) {
                $this->expand($this->server . $mailbox['value']);
            }
            $mailbox = $this->next();
        }

        $this->cur = $oldcur;
    }

    /**
     * Iterate through the folder tree and collapse every folder that has
     * children.  However, since each folder might not have been discovered,
     * it first expands them all.  This is a hack to get it working; to do
     * it properly it should check for the discovered bit, and if it is not
     * discovered, then ignore that heirarchy of folders.
     */
    function collapseAllFolders()
    {
        // This is a hack to ensure all folders are discovered, and opened.
        // ought to be corrected with proper discovery checking.
        $this->expandAllFolders();

        $mailbox = $this->head();
        while (isset($mailbox) && is_array($mailbox)) {
            if ($this->prefix != '' && $mailbox['level'] == 0) {
                // We have a folder prefix, don't collapse the first
                // level.
            } else if ($this->hasChildren($mailbox)) {
                $this->collapse($this->server . $mailbox['value']);
            }
            $mailbox = $this->next();
        }
    }

    function getList($path)
    {
        global $imp;

        $cmd = $this->listcmd;
        $newboxes = $cmd($imp['stream'], $this->server, $path);
        $unique = array();
        if (is_array($newboxes)) {
            $found = array();
            foreach ($newboxes as $box) {
                if (!empty($box->name) && empty($found[$box->name])) {
                    $unique[$box->name] = $box;
                    $found[$box->name] = true;
                }
            }
        }

        return $unique;
    }

    function getMailbox($path)
    {
        global $imp;

        $box = imap_getmailboxes($imp['stream'], $this->server, $path);
        return $box[0];
    }

    function makeMailboxTreeElt($name, $attributes, $delimiter, $level = 0,
                                $children = false, $discovered = false,
                                $open = false, $next = '')
    {
        $elt['level'] = $level;
        $elt['attributes'] = $attributes;
        $this->setChildren($elt, $children);
        $this->setDiscovered($elt, $discovered);
        $this->setOpen($elt, $open);
        $elt['next'] = $next;

        // computed values
        preg_match('|^{[^}]*}(.*)|', $name, $regs);
        $elt['value'] = $regs[1];
        if (!empty($delimiter)) {
            $tmp = explode($delimiter, $elt['value']);
            $elt['label'] = $tmp[count($tmp) - 1];
        } else {
            $elt['label'] = $elt['value'];
        }
        $elt['label'] = IMP::utf7Decode($elt['label']);

        return $elt;
    }


    /* Initialization */

    // init the list at the top level of the hierarchy
    function init($subscribed = false)
    {
        global $imp;

        // reset all class variables to the defaults
        if ($subscribed) {
            $this->listcmd = 'imap_getsubscribed';
        } else {
            $this->listcmd = 'imap_getmailboxes';
        }

        $this->prefix = $imp['folders'];
        $this->tree = array();
        $this->cur = '';
        $this->first = '';
        $this->delimiter = '/';
        $this->server = IMP::serverString();

        // this *should* always get the right delimiter
        $tmp = $this->getMailbox('INBOX');

        // Don't overwrite the default with an empty delimiter; a
        // guess is better than nothing.
        if (!empty($tmp->delimiter)) {
            $this->delimiter = $tmp->delimiter;
        }

        preg_match('|^({[^}]*})(.*)|', $tmp->name, $regs);
        $this->server = $regs[1];

        if ($this->prefix == '') {
            $boxes = $this->getList('%');
            if (!isset($boxes[$this->server . 'INBOX'])) {
                $boxes[$this->server . 'INBOX'] = $this->getMailbox('INBOX');
            }

            $nextlevel = $this->getList("%$this->delimiter%");
        } else {
            $boxes[$this->server . 'INBOX'] = $this->getMailbox('INBOX');

            // make sure that the name does NOT have a trailing
            // delimiter; otherwise we won't be able to find it when
            // we need to use it as a parent object.
            $tmp = $this->getMailbox($this->noTrailingDelimiter($this->prefix));
            $tmp->name = $this->noTrailingDelimiter($tmp->name);

            // don't re-insert the INBOX element for Cyrus,
            // Courier-imapd, etc.
            if (!isset($boxes[$tmp->name])) {
                if (empty($tmp->name)) {
                    $tmp = new stdClass;
                    $tmp->name = $this->server . $this->noTrailingDelimiter($this->prefix);
                    $tmp->attributes = 0;
                    $tmp->delimiter = '';
                }
                $boxes[$this->server . $this->prefix] = $tmp;
            }

            $nextlevel = $this->getList($this->prefix . '%');
        }

        // If we have any additional hierarchies, add them in.
        foreach ($this->hierarchies as $hierarchy) {
            $tmp = $this->getMailbox($hierarchy);
            if ($tmp) {
                $tmp->name = $this->noTrailingDelimiter($tmp->name);
                $boxes[$tmp->name] = $tmp;
            }
        }

        $this->feedList($boxes);
        if (is_array($nextlevel) && count($nextlevel) > 0) {
            $this->addLevel($nextlevel);
        }

        // If we have a folder prefix, automatically expand the first
        // level under it.
        if ($this->prefix != '') {
            $this->expand($this->server . $this->noTrailingDelimiter($this->prefix));
        }

        // If there are hierarchies, add the level under them.
        foreach ($this->hierarchies as $hierarchy) {
            if (isset($this->tree[$this->server . $this->noTrailingDelimiter($hierarchy)])) {
                $nextlevel = $this->getList($this->noTrailingDelimiter($hierarchy) . $this->delimiter . '%');
                if (is_array($nextlevel) && count($nextlevel) > 0) {
                    $this->addLevel($nextlevel);
                }
            }
        }
    }

    function noTrailingDelimiter($mailbox)
    {
        if (substr($mailbox, -1) == $this->delimiter) {
            $mailbox = substr($mailbox, 0, strlen($mailbox) - 1);
        }
        return $mailbox;
    }

    /* Hierarchy sorting functions */

    function hsort($list)
    {
        usort($list, array($this, 'tree_cmp'));
        return $list;
    }

    function tree_cmp($a, $b)
    {
        $aname = preg_replace('|^{[^}]*}|', '', $a->name);
        $bname = preg_replace('|^{[^}]*}|', '', $b->name);

        // always return INBOX as "smaller"
        if ($aname == 'INBOX') {
            return -1;
        } else if ($bname == 'INBOX') {
            return 1;
        }

        $a_parts = explode($this->delimiter, $aname);
        $b_parts = explode($this->delimiter, $bname);

        for ($i = 0; $i < min(count($a_parts), count($b_parts)); $i++) {
            if ($a_parts[$i] != $b_parts[$i]) {
                return strnatcasecmp($a_parts[$i], $b_parts[$i]);
            }
        }

        return count($a_parts) - count($b_parts);
    }


    /* Storage functions */

    // return a serialized version of the tree
    function pickle()
    {
        $pickle['tree'] = serialize($this->tree);
        $pickle['cur'] = $this->cur;
        $pickle['first'] = $this->first;
        $pickle['delimiter'] = $this->delimiter;
        $pickle['listcmd'] = $this->listcmd;
        $pickle['prefix'] = $this->prefix;
        $pickle['server'] = $this->server;

        return $pickle;
    }

    // rebuild oneself from a serialized string
    function unpickle($pickle)
    {
        $this->tree = unserialize($pickle['tree']);
        $this->cur = $pickle['cur'];
        $this->first = $pickle['first'];
        $this->delimiter = $pickle['delimiter'];
        $this->listcmd = $pickle['listcmd'];
        $this->prefix = $pickle['prefix'];
        $this->server = $pickle['server'];
    }


    /**
     ** Expand/Collapse functions
     **/

    function expand($folder)
    {
        global $prefs;

        if (!isset($this->tree[$folder])) {
            return;
        }

        $this->setOpen($this->tree[$folder], true);

        // merge in next level of information if we don't already have it
        if (!$this->isDiscovered($this->tree[$folder])) {
            $newlevel = $this->getList($folder . $this->delimiter . '%' . $this->delimiter . '%');
            if ($newlevel) {
                $this->addLevel($newlevel);
            }
            $this->setDiscovered($this->tree[$folder], true);
        }

        $serialized = $prefs->getValue('expanded_folders');
        if ($serialized) {
            $expanded = unserialize($serialized);
        } else {
            $expanded = array();
        }
        $expanded[$folder] = true;
        $prefs->setValue('expanded_folders', serialize($expanded));
        $prefs->store();
    }

    function collapse($folder)
    {
        global $prefs;

        if (!isset($this->tree[$folder])) {
            $this->init();
            if (!isset($this->tree[$folder])) {
                return;
            }
        }
        $this->setOpen($this->tree[$folder], false);

        $serialized = $prefs->getValue('expanded_folders');
        if ($serialized) {
            $expanded = unserialize($serialized);
        } else {
            $expanded = array();
        }
        unset($expanded[$folder]);
        $prefs->setValue('expanded_folders', serialize($expanded));
        $prefs->store();
    }


    /**
     ** Navigation functions
     **/

    // sets the internal array pointer to the next element, and returns the next object
    function next()
    {
        if (empty($this->cur)) {
            $this->cur = $this->first;
        } else {
            $old = $this->tree[$this->cur];
            if (empty($old['next'])) {
                return false;
            }
            $this->cur = $old['next'];
        }

        return $this->current();
    }

    function head()
    {
        $this->cur = $this->first;
        if (isset($this->tree[$this->cur])) {
            return $this->tree[$this->cur];
        } else {
            return false;
        }
    }

    function reset()
    {
        $this->cur = $this->first;
    }

    // return the next element after $this->cur that is on the save level as $this->cur
    // OR a higher level (0 == highest). So you don't fall off a cliff if you should be dropping back up
    // to the next level.
    function nextOnLevel()
    {
        $elt = $this->tree[$this->cur];
        $level = $elt['level'];
        $next = $this->next();
        if (!is_array($next)) {
            return false;
        }
        while ($next['level'] > $level) {
            $next = $this->next();
            if (!is_array($next)) {
                return false;
            }
        }
        return $this->current();
    }

    // return the current object
    function current()
    {
        if (isset($this->tree[$this->cur]) && is_array($this->tree[$this->cur])) {
            return $this->tree[$this->cur];
        } else {
            return false;
        }
    }


    /* Insertion functions */

    // insert an element, and return the key it was inserted as.
    // NB: This does not take care of updating any next pointers!
    // use insertInto() or update them manually.
    // ALSO NB: $elt must be an object that has a "name" field.
    function insert($elt, $id)
    {
        $this->tree[$id] = $elt;
        return $id;
    }

    function delete($id)
    {
        if (!isset($this->tree[$id])) {
            return false;
        }
        $elt = $this->tree[$id];
        $tmp = explode($this->delimiter, $elt['value']);
        if (count($tmp) == 1) {
            $pkey = $this->first;
        } else {
            $pkey = $this->server . substr($elt['value'], 0, strlen($elt['value']) - strlen($tmp[count($tmp) - 1]) - 1);
        }

        // find the element before $elt
        $cid = $pkey;

        // Make sure the folder we are deleting exists in the tree
        if (!isset($this->tree[$cid])) {
            // raise message here?
            return;
        }

        $cur = $this->tree[$cid];
        $level = $cur['level'];
        while ($cur['next'] != $id && $cid != '' && $cur['level'] >= $level) {
            $cid = $cur['next'];
            $cur = $this->tree[$cid];
        }

        if ($cur['next'] == $id) {
            $cur['next'] = $elt['next'];
            $this->tree[$cid] = $cur;
            unset($this->tree[$id]);
            return true;
        } else {
            return false;
        }
    }

    function insertInto($elt, $id)
    {
        $tmp = explode($this->delimiter, $elt['value']);
        if (count($tmp) == 1) {
            $pkey = $this->first;
        } else {
            $pkey = $this->server . substr($elt['value'], 0, strlen($elt['value']) - strlen($tmp[count($tmp) - 1]) - 1);
        }

        $parent = $this->tree[$pkey];
        $cid = $parent['next'];
        $cur = $this->tree[$cid];
        if ($this->tree_cmp($elt, $cur) == -1) {
            $cid = $pkey;
            $cur = $parent;
            $elt['level'] = $cur['level'] + 1;
        } else {
            $level = $cur['level'];
            while ($cur['level'] == $level && $this->tree_cmp($elt, $cur) > 0) {
                $prev = $cid;
                $cid = $cur['next'];
                $cur = $this->tree[$cid];
            }
            $cid = $prev;
            $cur = $this->tree[$cid];
            $elt['level'] = $cur['level'];  // insert on the same level
        }

        $tmp = $cur['next'];        // save the next; this will be the next of the inserted element.
        $nid = $this->insert($elt, $id); // stick the new element into the tree.
        $cur['next'] = $nid;        // have the element we found point to it.
        $this->tree[$cid] = $cur;   // make sure that element is current in the tree.
        $elt['next'] = $tmp;        // set the new elements next to cur's old next, closing the loop.
        $this->tree[$nid] = $elt;   // update the new element in the tree.
    }

    // insert a level of hierarchy. NB: $list is assumed to be in the form returned by
    // imap_getmailboxes()/imap_getsubscribed().
    function insertMailboxListAt($list, $id)
    {
        // first get the element we're inserting after and save its next attribute
        $old = $this->tree[$id];
        $tmp = $old['next'];
        $level = $old['level'] + 1;
        $oid = $id;

        // now loop through the list inserting all of the elements in order
        foreach ($list as $value) {
            $elt = $this->makeMailboxTreeElt($value->name, $value->attributes, $value->delimiter, $level);
            if ($this->dotfiles || ($elt['label'][0] != '.')) {
                $nid = $this->insert($elt, $value->name);
                $old['next'] = $nid;
                $this->tree[$oid] = $old;
                $oid = $nid;
                $old = $this->tree[$oid];
            }
        }

        // close the loop, making the next of the last elt in the list the old next of the orig element
        $old['next'] = $tmp;
        $this->tree[$oid] = $old;
    }

    // start the list. Calling this with an existing list will simply fail, since that would
    // create two lists in the same array with no links to each other.
    function feedList($list)
    {
        $level = 0;
        $list = $this->hsort($list); // make sure we're sorted correctly
        foreach ($list as $value) {
            $elt = $this->makeMailboxTreeElt($value->name, $value->attributes, $value->delimiter, $level);
            if ($this->dotfiles ||
                ($elt['label'][0] != '.') ||
                ($this->noTrailingDelimiter($this->prefix) == $elt['label'])) {
                $nid = $this->insert($elt, $value->name);
                if ($this->first == '') {
                    $this->first = $nid;
                } else {
                    $old['next'] = $nid;
                    $this->tree[$oid] = $old;
                }
                $oid = $nid;
                $old = $this->tree[$oid];
            }
        }
    }

    // Add another level of hierarchy to the tree. The logic for this
    // took a while to get right.
    function addLevel($list)
    {
        // first, since we're really adding one level below what we're displaying, we need
        // to get the information we need from what we're displaying: namely which nodes in
        // the level we *are* displaying actually have children
        $prefixes = $this->filter($list);
        foreach ($prefixes as $key => $junk) {
            if (array_key_exists($key, $this->tree)) {
                $this->setChildren($this->tree[$key], true);
            }
        }

        // sort the list
        $list = $this->hsort($list);

        // toss them all in. stir well.
        $lastpid = '';
        foreach ($list as $key => $value) {
            $elt = $this->makeMailboxTreeElt($value->name, $value->attributes, $value->delimiter);

            // Don't include the parent directories that UW passes
            // back in %/% lists; also filter out dotfiles if
            // requested.
            if (($elt['label'] != '') &&
                ($this->dotfiles || ($elt['label'][0] != '.'))) {
                $tmp = explode($this->delimiter, $elt['value']);
                if (count($tmp) == 1) {
                    // this case is broken. why?
                    $pkey = $value->name;
                } else {
                    $pkey = $this->server . substr($elt['value'], 0, strlen($elt['value']) - strlen($tmp[count($tmp) - 1]) - 1);
                }
                if ($pkey == $lastpid) {
                    $prev = $this->tree[$lastid];             // the element we want to put this one right after
                    $next = $prev['next'];                    // store what *was* its next element
                    $elt['level'] = $prev['level'];           // we're on the same level
                    $elt['next'] = $next;                     // make the new elements next element what was the old elements next
                    $nid = $this->insert($elt, $value->name); // actually insert the new element into the tree
                    $prev['next'] = $nid;                     // make the old elements next element the element we just inserted
                    $this->tree[$lastid] = $prev;             // update the value inside the tree array
                    $lastid = $nid;                           // update the last inserted id
                } elseif (array_key_exists($pkey, $this->tree)) {
                    $parent = $this->tree[$pkey];             // the parent element is what we want to insert after
                    $next = $parent['next'];                  // save what was its next element
                    $elt['level'] = $parent['level'] + 1;     // we're going one level deeper
                    $elt['next'] = $next;                     // make the new elts next pointer what the parent's next pointer was
                    $nid = $this->insert($elt, $value->name); // put the new element into the tree
                    $parent['next'] = $nid;                   // close the gap by setting the parent's next pointer to the new element
                    $this->tree[$pkey] = $parent;             // update the parent value in the tree array
                    $lastpid = $pkey;                         // update the last parent id
                    $lastid = $nid;                           // update the last inserted id
                }
            }
        }
    }


    /* Utility functions */

    function filter($mboxlist)
    {
        if ($mboxlist) {
            foreach ($mboxlist as $box) {
                $prefixes[substr($box->name, 0, strlen($box->name) - strlen(strrchr($box->name, $this->delimiter)))] = true;
            }
            return $prefixes;
        }
        return false;
    }

    function hasChildren($elt)
    {
        return $elt['attributes'] & TreeElt_HAS_CHILDREN;
    }

    function setChildren(&$elt, $bool)
    {
        if ($bool != $this->hasChildren($elt)) {
            if ($bool) {
                $elt['attributes'] |= TreeElt_HAS_CHILDREN;
            } else {
                $elt['attributes'] &= ~TreeElt_HAS_CHILDREN;
            }
        }
    }

    function isDiscovered($elt)
    {
        return $elt['attributes'] & TreeElt_IS_DISCOVERED;
    }

    function setDiscovered(&$elt, $bool)
    {
        if ($bool != $this->isDiscovered($elt)) {
            if ($bool) {
                $elt['attributes'] |= TreeElt_IS_DISCOVERED;
            } else {
                $elt['attributes'] &= ~TreeElt_IS_DISCOVERED;
            }
        }
    }

    function isOpen($elt)
    {
        return $elt['attributes'] & TreeElt_IS_OPEN;
    }

    function setOpen(&$elt, $bool)
    {
        if ($bool != $this->isOpen($elt)) {
            if ($bool) {
                $elt['attributes'] |= TreeElt_IS_OPEN;
            } else {
                $elt['attributes'] &= ~TreeElt_IS_OPEN;
            }
        }
    }

}
?>
