Algorithms PHP

Sorted Frequency List

This PHP Reference section displays the code for an example program that demonstrates a sorted frequency list.

CFrequencyList.php

<?php

// A list class that maintains the order of data elements by frequency
class CFrequencyList {
  private $mqaData = [];
  private $mqaFrequencies = [0];
  public function __construct() {
  }

  public function Debug() {
    print_r($this->mqaData);
    echo '<br />';
    print_r($this->mqaFrequencies);
    echo '<br />';
  }

  public function Add(&$rsaToBeAdded) {
    foreach($rsaToBeAdded as &$rsToAdd) {
      $iLocation = array_search($rsToAdd, $this->mqaData);
      if ($iLocation === false) {
        // If is was not already in the list, add it the end and increment count of single-valued entries
        $this->mqaData[] = $rsToAdd;
        ++$this->mqaFrequencies[0];
      } else {
        // If it is in the array, remove it and move it to the top of the higher list
        array_splice($this->mqaData, $iLocation, 1);
        $iFreqCount = count($this->mqaFrequencies);
        $iFrequency = 1;
        while ($iFrequency < $iFreqCount && $iLocation < $this->mqaFrequencies[$iFrequency]) {
          ++$iFrequency;
        }
        // If it is a new most frequent element
        if ($iFrequency == $iFreqCount) {
          // Extend the frequency array
          $this->mqaFrequencies[] = 1;
          // Add the new element to the beginning of the array
          array_unshift($this->mqaData, $rsToAdd);
        } else {
          array_splice($this->mqaData, $this->mqaFrequencies[$iFrequency], null, $rsToAdd);
          ++$this->mqaFrequencies[$iFrequency];
        }
      }
    }
  }

  public function Remove(&$rsaToBeRemoved) {
    // For each element in the removal array
    foreach($rsaToBeRemoved as &$rsToRemove) {
      // Locate the value to be removed
      $iLocation = array_search($rsToRemove, $this->mqaData);
      if ($iLocation !== false) {
        // Find the frequency
        $iFrequency = count($this->mqaFrequencies) - 1;
        while ($iLocation >= $this->mqaFrequencies[$iFrequency]) {
          --$iFrequency;
        }
        // If the frequency is greater than 1, reduce that frequency by one.
        --$this->mqaFrequencies[$iFrequency];
        if ($iFrequency > 0) {
          if ($this->mqaFrequencies[$iFrequency] > 0) {
            // Then move the entry to the end of the frequency range
            while ($iLocation < $this->mqaFrequencies[$iFrequency]) {
              $this->mqaData[$iLocation] = $this->mqaData[$iLocation + 1];
              ++$iLocation;
            }
            $this->mqaData[$iLocation] = $rsToRemove;
          } else {
            // If the number in that frequency is now zero, remove the frequency
            // It must be the highest frequency, so reduce the array by popping it
            array_pop($this->mqaFrequencies);
          }
        } else {
          // Otherwise, reduce the first frequency and remove the element
          array_splice($this->mqaData, $iLocation, 1);
        }
      }
    }
  }
}

$qFreqlist = new CFrequencyList();

$saaNames = [["James", "John"],
  ["David", "Cyrus", "Jesus", "James"],
  ["Mark", "James", "Judas", "Mary", "John"],
  ["Judas", "Jerome", "Augustine", "Paul", "John", "Ignatius"],
  ["Peter", "Mary", "John"],
  ["Mary", "Joseph"]];
  foreach($saaNames as &$saNameToAdd) {
    $qFreqlist->Add($saNameToAdd);
    $qFreqlist->Debug();
  }
  $iIndex = count($saaNames) - 1;
  while ($iIndex >= 0) {
    $qFreqlist->Remove($saaNames[$iIndex]);
    $qFreqlist->Debug();
    --$iIndex;
  }

?>
 

Output

 
 

© 2007–2024 XoaX.net LLC. All rights reserved.