<?PHP

#
#   FILE:  PersistentDoublyLinkedList.php
#
#   Part of the ScoutLib application support library
#   Copyright 2012 Edward Almasy and Internet Scout
#   http://scout.wisc.edu
#

/**
* Persistent doubly-linked-list data structure, with its data stored in a
* specified database table.  The specified table is usually also being used
* to store other information about the items being referenced by the list.
* Items in the list are assumed to have associated unique IDs, and anywhere
* item objects are passed in as parameters, the objects are assumed to have
* Id() methods that can be used to retrieve their associated IDs.  More
* than one type of item can be included in a list, by use of the (optional)
* item type parameters.  (Item IDs and types are assumed to be positive
* integers.)
*/
class PersistentDoublyLinkedList {

    # ---- PUBLIC INTERFACE --------------------------------------------------

    /**
    * Object constructor.  The specified database table must include an INT
    * field containing IDs for the items being managed, and two other INT
    * fields that have the same name with "Previous" and "Next" prepended
    * to it (e.g. "ItemId", "PreviousItemId", and "NextItemId").  These
    * additional INT fields should have a default value of -1.  If mixed
    * item types are to be included in the list, then the table must also
    * include an INT field for the types of the items being managed, and
    * two other INT fields that have the same name with "Previous" and
    * "Next" prepended ("ItemType", "PreviousItemType", "NextItemType").
    * @param ItemTableName Database table in which to store list information.
    * @param ItemIdFieldName Database field name for item IDs.
    * @param SqlCondition SQL condition for referencing items in database.
    *       (OPTIONAL)  This is intended to be used to specify a conditional
    *       clause to be added to any SQL statements that are used to store
    *       or retrieve information about items within the list, usually
    *       with the goal of information about multiple lists being stored in
    *       the same table in the database.  The condition should not include
    *       a leading WHERE or other leading SQL clause joining operator.
    * @param ItemTypeFieldName Database field name for item types.  (OPTIONAL)
    * @see PersistentDoublyLinkedList::SqlCondition()
    */
    function __construct($ItemTableName, $ItemIdFieldName,
            $SqlCondition = NULL, $ItemTypeFieldName = NULL)
    {
        # grab our own database handle
        $this->DB = new Database();

        # save configuration
        $this->ItemTableName = $ItemTableName;
        $this->ItemIdFieldName = $ItemIdFieldName;
        $this->ItemTypeFieldName = $ItemTypeFieldName;
        $this->SqlCondition($SqlCondition);
    }

    /**
    * Get or set/update SQL condition for referencing items in database.  This
    * is intended to be used to specify a conditional clause to be added to
    * any SQL statements that are used to store or retrieve information about
    * items within the list, usually with the goal of information about
    * multiple lists being stored in the same table in the database.  The
    * condition should not include a leading WHERE or other leading SQL
    * clause joining operator.
    * @param string $Condition New SQL condition clause.  (OPTIONAL)
    * @return string Current SQL condition clause or NULL if no clause set.
    */
    function SqlCondition($Condition = NULL)
    {
        if ($Condition) {  $this->SqlCondition = $Condition;  }
        return $this->SqlCondition;
    }

    /**
    * Insert item into list before specified item.  If the item is already
    * present in the list, it is moved to the new location.  If the target
    * item is not found, the new item is added to the beginning of the list.
    * @param TargetItemOrItemId Item to insert before.
    * @param NewItemOrItemId Item to insert.
    * @param TargetItemType Type of item to insert before.  (OPTIONAL)
    * @param NewItemType Type of item to insert.  (OPTIONAL)
    */
    function InsertBefore($TargetItemOrItemId, $NewItemOrItemId,
            $TargetItemType = NULL, $NewItemType = NULL)
    {
        # retrieve item IDs
        $NewItemId = is_object($NewItemOrItemId)
                ? $NewItemOrItemId->Id() : $NewItemOrItemId;
        $TargetItemId = is_object($TargetItemOrItemId)
                ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;

        # remove source item from current position if necessary
        $this->Remove($NewItemId);

        # retrieve current previous item pointer for target item
        $TargetItemCurrentPreviousId = $this->GetPreviousItemId(
                $TargetItemId, $TargetItemType);

        # if target item not found
        if ($TargetItemCurrentPreviousId === FALSE)
        {
            # add new item to beginning of list
            $this->Prepend($NewItemId, $NewItemType);
        }
        else
        {
            # retrieve target item type if available
            if (is_array($TargetItemCurrentPreviousId))
            {
                $TargetItemCurrentPreviousType = $TargetItemCurrentPreviousId["Type"];
                $TargetItemCurrentPreviousId = $TargetItemCurrentPreviousId["ID"];
            }
            else
            {
                $TargetItemCurrentPreviousType = NULL;
            }

            # update IDs to link in new item
            $this->SetPreviousItemId(
                    $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
            if ($TargetItemCurrentPreviousId != self::LISTEND_ID)
            {
                $this->SetNextItemId($TargetItemCurrentPreviousId,
                        $TargetItemCurrentPreviousType, $NewItemId, $NewItemType);
            }
            $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
                    $TargetItemCurrentPreviousId, $TargetItemCurrentPreviousType,
                    $TargetItemId, $TargetItemType);
        }
    }

    /**
    * Insert item into list after specified item.  If the item is already
    * present in the list, it is moved to the new location.  If the target
    * item is not found, the new item is added to the end of the list.
    * @param TargetItemOrItemId Item to insert after.
    * @param NewItemOrItemId Item to insert.
    * @param TargetItemType Type of item to insert after.  (OPTIONAL)
    * @param NewItemType Type of item to insert.  (OPTIONAL)
    */
    function InsertAfter($TargetItemOrItemId, $NewItemOrItemId,
            $TargetItemType = NULL, $NewItemType = NULL)
    {
        # retrieve item IDs
        $NewItemId = is_object($NewItemOrItemId)
                ? $NewItemOrItemId->Id() : $NewItemOrItemId;
        $TargetItemId = is_object($TargetItemOrItemId)
                ? $TargetItemOrItemId->Id() : $TargetItemOrItemId;

        # remove new item from existing position (if necessary)
        $this->Remove($NewItemId, $NewItemType);

        # retrieve current next item pointer for target item
        $TargetItemCurrentNextId = $this->GetNextItemId(
                $TargetItemId, $TargetItemType);

        # if target item not found
        if ($TargetItemCurrentNextId === FALSE)
        {
            # add new item to end of list
            $this->Append($NewItemId, $NewItemType);
        }
        else
        {
            # retrieve target item type if available
            if (is_array($TargetItemCurrentNextId))
            {
                $TargetItemCurrentNextType = $TargetItemCurrentNextId["Type"];
                $TargetItemCurrentNextId = $TargetItemCurrentNextId["ID"];
            }
            else
            {
                $TargetItemCurrentNextType = NULL;
            }

            # update IDs to link in new item
            $this->SetNextItemId(
                    $TargetItemId, $TargetItemType, $NewItemId, $NewItemType);
            if ($TargetItemCurrentNextId != self::LISTEND_ID)
            {
                $this->SetPreviousItemId(
                        $TargetItemCurrentNextId, $TargetItemCurrentNextType,
                        $NewItemId, $NewItemType);
            }
            $this->SetPreviousAndNextItemIds($NewItemId, $NewItemType,
                    $TargetItemId, $TargetItemType,
                    $TargetItemCurrentNextId, $TargetItemCurrentNextType);
        }
    }

    /**
    * Add item to beginning of list.  If the item is already present in the list,
    * it is moved to the new location.
    * @param ItemOrItemId Item to add.
    * @param ItemType Numerical type of item to add.  (OPTIONAL)
    */
    function Prepend($ItemOrItemId, $ItemType = NULL)
    {
        # get item ID
        $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;

        # remove new item from current position if necessary
        $this->Remove($ItemId, $ItemType);

        # if there are items currently in list
        $ItemIds = $this->GetIds(FALSE);
        if (count($ItemIds))
        {
            # link first item to source item
            if ($this->ItemTypeFieldName)
            {
                $Row = array_shift($ItemIds);
                $FirstItemId = $Row["ID"];
                $FirstItemType = $Row["Type"];
            }
            else
            {
                $FirstItemId = array_shift($ItemIds);
                $FirstItemType = NULL;
            }

            $this->SetPreviousItemId($FirstItemId, $FirstItemType, $ItemId, $ItemType);
            $this->SetPreviousAndNextItemIds(
                    $ItemId, $ItemType, self::LISTEND_ID, self::LISTEND_ID,
                    $FirstItemId, $FirstItemType);
        }
        else
        {
            # add item to list as only item
            $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
                    self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID, self::LISTEND_ID);
        }
    }

    /**
    * Add item to end of list.  If the item is already present in the list,
    * it is moved to the new location.
    * @param ItemOrItemId Item to add.
    * @param ItemType Numerical type of item to add.  (OPTIONAL)
    */
    function Append($ItemOrItemId, $ItemType = NULL)
    {
        # get item ID
        $ItemId = is_object($ItemOrItemId) ? $ItemOrItemId->Id() : $ItemOrItemId;

        # remove item from current position if necessary
        $this->Remove($ItemId, $ItemType);

        # if there are items currently in list
        $ItemIds = $this->GetIds();
        if (count($ItemIds))
        {
            # link last item to source item
            if ($this->ItemTypeFieldName)
            {
                $Row = array_pop($ItemIds);
                $LastItemId = $Row["ID"];
                $LastItemType = $Row["Type"];
            }
            else
            {
                $LastItemId = array_pop($ItemIds);
                $LastItemType = NULL;
            }
            $this->SetNextItemId($LastItemId, $LastItemType, $ItemId, $ItemType);
            $this->SetPreviousAndNextItemIds(
                    $ItemId, $ItemType, $LastItemId, $LastItemType,
                    self::LISTEND_ID, self::LISTEND_ID);
        }
        else
        {
            # add item to list as only item
            $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
                    self::LISTEND_ID, self::LISTEND_ID,
                    self::LISTEND_ID, self::LISTEND_ID);
        }
    }

    /**
    * Retrieve array of IDs of items in list, in the order that they appear
    * in the list.
    * @return Array of item IDs or (if mixed-item-type list) item IDs and types.
    *       When returning IDs and types, each element in the returned array is
    *       an associative array, with the indexes "ID" and "Type".
    */
    function GetIds()
    {
        # assume no items will be found in folder
        $ItemIds = array();

        # if item types are in use
        if ($this->ItemTypeFieldName)
        {
            # retrieve IDs and types of all items in list and links between items
            $this->DB->Query("SELECT * FROM ".$this->ItemTableName
                    .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
                    ." ORDER BY ".$this->ItemIdFieldName." ASC");

            # build up lists of next and previous item pointers
            $PreviousItemIds = array();
            $NextItemIds = array();
            while ($Record = $this->DB->FetchRow())
            {
                $Index = $Record[$this->ItemTypeFieldName]
                        .":".$Record[$this->ItemIdFieldName];
                $KnownItemTypes[$Index] = $Record[$this->ItemTypeFieldName];
                $KnownItemIds[$Index] = $Record[$this->ItemIdFieldName];
                $PreviousItemIds[$Index] = $Record["Previous".$this->ItemTypeFieldName]
                        .":".$Record["Previous".$this->ItemIdFieldName];
                $NextItemIds[$Index] = $Record["Next".$this->ItemTypeFieldName]
                        .":".$Record["Next".$this->ItemIdFieldName];
            }

            # find ID of first item in list
            $ListEndIndex = self::LISTEND_ID.":".self::LISTEND_ID;
            $Index = array_search($ListEndIndex, $PreviousItemIds);

            # if first item was found
            if ($Index !== FALSE)
            {
                # traverse linked list to build list of item types and IDs
                do
                {
                    $ItemIds[$Index] = array(
                            "Type" => $KnownItemTypes[$Index],
                            "ID" => $KnownItemIds[$Index]);
                    $Index = $NextItemIds[$Index];
                }
                # (stop if we've reached the end of the list)
                while (($Index != $ListEndIndex)
                        # (stop if link points to item not in list)
                        && array_key_exists($Index, $NextItemIds)
                        # (stop if link is circular)
                        && !array_key_exists($Index, $ItemIds));
            }
        }
        else
        {
            # retrieve IDs of all items in list and links between items
            $this->DB->Query("SELECT ".$this->ItemIdFieldName
                    .", Previous".$this->ItemIdFieldName
                    .", Next".$this->ItemIdFieldName
                    ." FROM ".$this->ItemTableName
                    .($this->SqlCondition ? " WHERE ".$this->SqlCondition : "")
                    ." ORDER BY ".$this->ItemIdFieldName." ASC");

            # build up lists of next item pointers
            $PreviousItemIds = array();
            $NextItemIds = array();
            while ($Record = $this->DB->FetchRow())
            {
                $Index = $Record[$this->ItemIdFieldName];
                $PreviousItemIds[$Index] = $Record["Previous".$this->ItemIdFieldName];
                $NextItemIds[$Index] = $Record["Next".$this->ItemIdFieldName];
            }

            # find ID of first item in list
            $ItemId = array_search(self::LISTEND_ID, $PreviousItemIds);

            # if first item was found
            if ($ItemId !== FALSE)
            {
                # traverse linked list to build list of item IDs
                do
                {
                    $ItemIds[] = $ItemId;
                    $ItemId = $NextItemIds[$ItemId];
                }
                # (stop if we've reached the end of the list)
                while (($ItemId != self::LISTEND_ID)
                        # (stop if link points to item not in list)
                        && array_key_exists($ItemId, $NextItemIds)
                        # (stop if link is circular)
                        && !in_array($ItemId, $ItemIds));
            }
        }

        # return list of item IDs to caller
        return $ItemIds;
    }

    /**
    * Remove item from list.  If the item is not currently present in the
    * list, then the call has no effect.
    * @param ItemId ID of item to be removed.
    * @param ItemType Numerical type of item to be removed.
    */
    function Remove($ItemId, $ItemType = NULL)
    {
        # retrieve item's "previous" pointer
        $CurrentItemPreviousId = $this->GetPreviousItemId($ItemId, $ItemType);

        # bail out if item was not found
        if ($CurrentItemPreviousId === FALSE) {  return;  }

        # retrieve item's "next" pointer
        $CurrentItemNextId = $this->GetNextItemId($ItemId, $ItemType);
        if ($this->ItemTypeFieldName)
        {
            $CurrentItemPreviousType = $CurrentItemPreviousId["Type"];
            $CurrentItemPreviousId = $CurrentItemPreviousId["ID"];
            $CurrentItemNextType = $CurrentItemNextId["Type"];
            $CurrentItemNextId = $CurrentItemNextId["ID"];
        }
        else
        {
            $CurrentItemPreviousType = NULL;
            $CurrentItemNextType = NULL;
        }

        # if item was not first in list
        if ($CurrentItemPreviousId >= 0)
        {
            # link previous item to item's current next item
            $this->SetNextItemId(
                    $CurrentItemPreviousId, $CurrentItemPreviousType,
                    $CurrentItemNextId, $CurrentItemNextType);
        }

        # if item was not last in list
        if ($CurrentItemNextId >= 0)
        {
            # link next item to item's current previous item
            $this->SetPreviousItemId(
                    $CurrentItemNextId, $CurrentItemNextType,
                    $CurrentItemPreviousId, $CurrentItemPreviousType);
        }

        # set items pointers to indicate it is not part of a list
        $this->SetPreviousAndNextItemIds($ItemId, $ItemType,
                self::UNINITIALIZED_ID, self::UNINITIALIZED_ID,
                self::UNINITIALIZED_ID, self::UNINITIALIZED_ID);
    }


    # ---- PRIVATE INTERFACE -------------------------------------------------

    private $DB;
    private $ItemTableName;
    private $ItemIdFieldName;
    private $ItemTypeFieldName;
    private $SqlCondition = NULL;

    const UNINITIALIZED_ID = -1;
    const LISTEND_ID = -2;

    # get ordering values (return FALSE if specified item not found)
    private function GetPreviousItemId($ItemId, $ItemType)
    {
        if ($this->ItemTypeFieldName)
        {
            $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
                                .", Previous".$this->ItemTypeFieldName
                        ." FROM ".$this->ItemTableName
                        ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                        ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
                        .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
            if (!$this->DB->NumRowsSelected()) {  return FALSE;  }
            $Row = $this->DB->FetchRow();
            if ($Row["Previous".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
                    {  return FALSE;  }
            $ReturnValue["Type"] = $Row["Previous".$this->ItemTypeFieldName];
            $ReturnValue["ID"] = $Row["Previous".$this->ItemIdFieldName];
            return $ReturnValue;
        }
        else
        {
            $ReturnVal = $this->DB->Query("SELECT Previous".$this->ItemIdFieldName
                        ." FROM ".$this->ItemTableName
                        ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                        .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
                    "Previous".$this->ItemIdFieldName);
            return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
        }
    }
    private function GetNextItemId($ItemId, $ItemType)
    {
        if ($this->ItemTypeFieldName)
        {
            $this->DB->Query("SELECT Next".$this->ItemIdFieldName
                                .", Next".$this->ItemTypeFieldName
                        ." FROM ".$this->ItemTableName
                        ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                        ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
                        .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
            if (!$this->DB->NumRowsSelected()) {  return FALSE;  }
            $Row = $this->DB->FetchRow();
            if ($Row["Next".$this->ItemIdFieldName] == self::UNINITIALIZED_ID)
                    {  return FALSE;  }
            $ReturnValue["Type"] = $Row["Next".$this->ItemTypeFieldName];
            $ReturnValue["ID"] = $Row["Next".$this->ItemIdFieldName];
            return $ReturnValue;
        }
        else
        {
            $ReturnVal = $this->DB->Query("SELECT Next".$this->ItemIdFieldName
                        ." FROM ".$this->ItemTableName
                        ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                        .($this->SqlCondition ? " AND ".$this->SqlCondition : ""),
                    "Next".$this->ItemIdFieldName);
            return ($ReturnVal == self::UNINITIALIZED_ID) ? FALSE : $ReturnVal;
        }
    }

    # set ordering values
    private function SetPreviousItemId($ItemId, $ItemType, $NewId, $NewType)
    {
        if ($this->ItemTypeFieldName)
        {
            $this->DB->Query("UPDATE ".$this->ItemTableName
                    ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
                    .", Previous".$this->ItemTypeFieldName." = ".intval($NewType)
                    ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                    ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
                    .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
        }
        else
        {
            $this->DB->Query("UPDATE ".$this->ItemTableName
                    ." SET Previous".$this->ItemIdFieldName." = ".intval($NewId)
                    ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                    .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
        }
    }
    private function SetNextItemId($ItemId, $ItemType, $NewId, $NewType)
    {
        if ($this->ItemTypeFieldName)
        {
            $this->DB->Query("UPDATE ".$this->ItemTableName
                    ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
                            .", Next".$this->ItemTypeFieldName." = ".intval($NewType)
                    ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                    ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
                    .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
        }
        else
        {
            $this->DB->Query("UPDATE ".$this->ItemTableName
                    ." SET Next".$this->ItemIdFieldName." = ".intval($NewId)
                    ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                    .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
        }
    }
    private function SetPreviousAndNextItemIds($ItemId, $ItemType,
            $NewPreviousId, $NewPreviousType, $NewNextId, $NewNextType)
    {
        if ($this->ItemTypeFieldName)
        {
            $this->DB->Query("UPDATE ".$this->ItemTableName
                    ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
                            .", Previous".$this->ItemTypeFieldName." = "
                                    .intval($NewPreviousType)
                            .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
                            .", Next".$this->ItemTypeFieldName." = ".intval($NewNextType)
                    ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                    ." AND ".$this->ItemTypeFieldName." = ".intval($ItemType)
                    .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
        }
        else
        {
            $this->DB->Query("UPDATE ".$this->ItemTableName
                    ." SET Previous".$this->ItemIdFieldName." = ".intval($NewPreviousId)
                            .", Next".$this->ItemIdFieldName." = ".intval($NewNextId)
                    ." WHERE ".$this->ItemIdFieldName." = ".intval($ItemId)
                    .($this->SqlCondition ? " AND ".$this->SqlCondition : ""));
        }
    }
}


?>
