[PHP] Search a multidimensional array

[diabolo]

$textbook = array(
   'cantonese' => array(
      'class1' => array(
         array('1', 'One - Two', 'Chapter 1 to Chapter 2',
                   'text'),
         array('3', 'Three - Five', 'Chapter 3 to Chapter5',
                   'text'),
         array('6', 'Six - Eight', 'Chapter 6 to Chapter 8',
                   'text'),
      ),
      'class2' => array(
      ),
   ),
   'mandarin' => array(
      'class1'  => array(
      ),
      'class2'  => array(
      )
   )
);

that is the array where I have all the class textbooks. Now I need to be able to search through it and pick up the text from a specified chapter.
i.e. I pass on $_GET variables, ['cls'] and ['ch']

but I can't just do: $textbook[$language][$cls][$ch], because the keys are not the ['ch'] numbers

also, array_search() does not exactly work, because it doesn't search down multiple arrays.

 

[misson]

What do the contents of $_GET['cls'] and $_GET['ch'] look like? "classN" and an integer? Given that each chapter list in each class array is a range of chapters, you'll need to implement your own search. As long as the chapter ranges are in ascending order (as in the sample), you can use binsearch:

function getChapter($textbook, $lang, $cls, $ch) {
    // TODO: add error checking
    $cls = $textbook[$lang][$cls];
    $lo = 0;
    $hi = count($cls);
    $mid = ($lo+$hi)>>1;
    do {
        if ($ch < $cls[$mid][0]) {
            $hi = $mid;
        } else {
            $lo = $mid;
        }
        $mid = ($lo+$hi) >> 1;
    } while ($mid != $lo);
    return $cls[$mid];
}

Alternatively, store the chapter list in a DB. For example,

CREATE TABLE classes (
    id INT PRIMARY KEY  AUTO_INCREMENT,
    name VARCHAR(64) DEFAULT NULL,
    level INT,
    lang ENUM('cantonese', 'mandarin') NOT NULL
) ENGINE=InnoDB;

/* `sections` is denormalized; in normal form, column `class` 
belongs in a separate `textbook` table, and column `content` 
belongs in a `chapters` table.
*/
CREATE TABLE sections (
    id INT PRIMARY KEY AUTO_INCREMENT,
    start INT NOT NULL, -- starting chapter
    end INT NOT NULL, -- ending chapter
    `range` VARCHAR(32), -- e.g. 'Three - Five'
    label VARCHAR(128), -- short description of chapters
    content TEXT NOT NULL,
    class INT NOT NULL,
    FOREIGN KEY (class) REFERENCES classes (id),
    INDEX (start, end)
) ENGINE=InnoDB;

To get a section:

SELECT sect.start, sect.end, sect.label, sect.content 
    FROM sections AS sect 
    JOIN classes AS cl 
      ON sect.class=cl.id AND sect.class=:class
    WHERE cl.lang=:lang AND sect.start <= :ch AND :ch <= sect.end;

Of course, if one textbook can be used for multiple classes, you'll have to redesign the schema.

You might want to create a trigger to prevent sections from overlapping:

DROP TRIGGER IF EXISTS section_nooverlap;
DELIMITER //
CREATE TRIGGER section_nooverlap BEFORE INSERT ON sections
FOR EACH ROW 
BEGIN
    DECLARE dummy INT;
    IF EXISTS(SELECT id FROM sections AS s 
                  WHERE New.class = s.class
                    AND ((New.start <= s.start AND s.start <= New.end) 
                      OR (New.start <= s.end   AND s.end   <= New.end)))
    THEN 
        SELECT `New section overlaps existing section(s).` INTO dummy 
            FROM sections WHERE sections.id=NEW.id;
    END IF ;
END //
DELIMITER ;

Since the `section` table won't likely be updated often, the trigger will have at most a small impact on the speed of your site.

 

[diabolo]

I was thinking about using a db, but I because Im working on an offline copy(localhost)
I hate having to change settings and do everything twice once I put it to a production server

but it would make everything easier,
so I guess Ill will try one of those, and see how things go

 

[t2t2t]

but I can't just do: $textbook[$language][$cls][$ch], because the keys are not the ['ch'] numbers

Restructure it then:

<?php
$textbook = array(
	'cantonese' => array(
		'class1' => array(
			1 => array('One - Two', 'Chapter 1 to Chapter 2', 'text'),
			3 => array('Three - Five', 'Chapter 3 to Chapter 5', 'text'),
			6 => array('Six - Eight', 'Chapter 6 to Chapter 8', 'text'),
		),
		'class2' => array(
			// Follow above
		)
	),
	'mandarin' => array(
		// Follow above
	)
	// And so on
);
// Example:
echo $textbook['cantonese']['class1'][3][0].'<br />'.$textbook['cantonese']['class1'][3][1]; // Three - Five<br />Chapter 3 to Chapter 5
?>

 

[misson]

I was thinking about using a db, but I because Im working on an offline copy(localhost)
I hate having to change settings and do everything twice once I put it to a production server

You shouldn't need to do everything twice. Just set up the design server as a mirror of the production server. Alternatively, have a configuration script that sets DB configuration options, such as user, password, database and table names.

If all you need to do with the data is fetch a single chapter, the binsearch approach should be fine. Any more than that and using a DB is the best choice.

Restructure it then:

What if $_GET['cls']==1 && $_GET['ch'] == 2? Since Diabolo hasn't clarified the legal values of $_GET['ch'], we can't rule out that case.

Of course, if it comes down to altering the input format, he could use section numbers rather than chapter numbers, which would simplify both indexing and error checking.

 

[t2t2t]

What if $_GET['cls']==1 && $_GET['ch'] == 2? Since Diabolo hasn't clarified the legal values of $_GET['ch'], we can't rule out that case.

Of course, if it comes down to altering the input format, he could use section numbers rather than chapter numbers, which would simplify both indexing and error checking.

That value wasn't mentioned in original post . And a simple check for that would be:

if(is_array($textbook['cantonese']['class'.$_GET['cls']][$_GET['ch']])) {
	echo $textbook['cantonese']['class'.$_GET['cls']][$_GET['ch']][0].'<br />'.$textbook['cantonese']['class'.$_GET['cls']][$_GET['ch']][1];
} else {
	echo 'Oopsies!';
}
// Example outputs:

// ?cls=1&ch=3
// Three - Five<br />Chapter 3 to Chapter 5

// ?cls=1&ch=4
// Oopsies!

 

[diabolo]

Restructure it then:

<?php
$textbook = array(
    'cantonese' => array(
        'class1' => array(
            1 => array('One - Two', 'Chapter 1 to Chapter 2', 'text'),
            3 => array('Three - Five', 'Chapter 3 to Chapter 5', 'text'),
            6 => array('Six - Eight', 'Chapter 6 to Chapter 8', 'text'),
        ),
        'class2' => array(
            // Follow above
        )
    ),
    'mandarin' => array(
        // Follow above
    )
    // And so on
);
// Example:
echo $textbook['cantonese']['class1'][3][0].'<br />'.$textbook['cantonese']['class1'][3][1]; // Three - Five<br />Chapter 3 to Chapter 5
?>

I did also try a restructure version of it, but that went haywire after I couldn't figure out how the foreach loops would function

 

[t2t2t]

Here's a small example to show how to loop everything:

<?php
// Just repeating text for example.
$textbook = array(
	'cantonese' => array(
		'class1' => array(
			1 => array('One - Two', 'Chapter 1 to Chapter 2', 'text'),
			3 => array('Three - Five', 'Chapter 3 to Chapter 5', 'text'),
			6 => array('Six - Eight', 'Chapter 6 to Chapter 8', 'text'),
		),
		'class2' => array(
			1 => array('One - Two', 'Chapter 1 to Chapter 2', 'text'),
			3 => array('Three - Five', 'Chapter 3 to Chapter 5', 'text'),
			6 => array('Six - Eight', 'Chapter 6 to Chapter 8', 'text'),
		)
	),
	'mandarin' => array(
		'class1' => array(
			1 => array('One - Two', 'Chapter 1 to Chapter 2', 'text'),
			3 => array('Three - Five', 'Chapter 3 to Chapter 5', 'text'),
			6 => array('Six - Eight', 'Chapter 6 to Chapter 8', 'text'),
		),
		'class2' => array(
			1 => array('One - Two', 'Chapter 1 to Chapter 2', 'text'),
			3 => array('Three - Five', 'Chapter 3 to Chapter 5', 'text'),
			6 => array('Six - Eight', 'Chapter 6 to Chapter 8', 'text'),
		)
	)
);
?>
<!-- Some styling for better understanding -->
<style type="text/css">
	div {
		margin-left: 2em;
	}
</style>
<?php
foreach($textbook as $lang => $langdata) { // Loop languages
	echo '<h2>'.ucfirst($lang).'</h2><div>';
	foreach($langdata as $class => $classdata) { // Loop classes
		echo '<h3>'.ucfirst($class).'</h3><div>';
		foreach($classdata as $chapter => $chapterdata) { // Loop chapters
			echo '<h4>Chapter '.$chapter.' - '.$chapterdata[0].'</h4><div><span style="font-style: italic;">'.$chapterdata[1].'</span><p>'.$chapterdata[2].'</p></div>';
		}
		echo '</div>';
	}
	echo '</div>';
}
?>

Example output

 

[xav0989]

Can't you have a recursive array search?

 

[diabolo]

well here's what I originally had.

function loadClass($dialect, $error=NULL) {
   include ROOT.'sources/bits/textbook.php';
   $i = 0;
   
   foreach ($textbookList[$dialect] as $class => $chapters) {
      $numClasses = count($textbookList[$dialect]);
      $rowClass = 'row';
         if($i == ($numClasses-1)) { $rowClass = 'row lastRow'; }
      $html .= '<div class="'.$rowClass.'" id="'.$class.'">';
      $html .= '<div class="class">'.$class.'</div>';
      $html .= '<div class="chapterContainer">';
         $numChapters = count($chapters);
         $ii = 0;
         while($ii < $numChapters) {
            $html .= '<a href="'.ROOT.'curriculum/'.$dialect.'/textbook.php?cls='.$class.'&ch='.$chapters[$ii]['0'].'"><span class="chapter">'.$chapters[$ii]['1'].'</span></a>';
            $ii++;
         }
      $html .= '</div>';
      $html .= '</div>';
   $i++;
   }
echo $html;   
}

I needed to separate it by classes too. but i've started working on the db version so unless someone can come with an awesome breakthrough that requires no brain work for me other than copy+paste, I think im going to work with the db version

 

[misson]

That value wasn't mentioned in original post . And a simple check for that would be:

Agreed, the original post was underspecified. I also agree your solution works if only first chapters in section are valid input. However, my point was that Diabolo may want (someday, if not today) to allow other chapter numbers to be used as input, since it's more robust. As long as sections are indexed by starting chapter, some form of search is required, though the code could perform the search only when an index doesn't exist. Something like:

$textbook = array(
    'cantonese' => array(
        'class1' => array(
            1 => array('start' => 1, 'range' => 'One - Two', 'label' => 'Chapter 1 to Chapter 2', 'content' => 'text'),
            3 => array('start' => 3, 'range' => 'Three - Five', 'label' => 'Chapter 3 to Chapter 5', 'content' => 'text'),
            6 => array('start' => 6, 'range' => 'Six - Eight', 'label' => 'Chapter 6 to Chapter 8', 'content' => 'text'),
        ),
        'class2' => array(
            // Follow above
        )
    ),
    'mandarin' => array(
        // Follow above
    )
    // And so on
);

function getSection($textbook, $lang, $cls, $ch) {
    if (isset($textbook[$lang][$cls][$ch])) {
        return $textbook[$lang][$cls][$ch];
    }
    // binsearch as before.
    ...
}

getSection is O(1) for starting chapters and O(lg(n)) for other chapters.

Can't you have a recursive array search?

In this case, recursion is unnecessary, since the only array that needs to be searched is one array of chapters. Getting to that point can be done by indexing alone.

 

[Bryon]

Thumbs up for Misson!

 

[xav0989]

In this case, recursion is unnecessary, since the only array that needs to be searched is one array of chapters. Getting to that point can be done by indexing alone.

You're right, I haven't seen it that way... Anyway, nice post!

 

[matthew88]

These type of things give me a headache, but if you work with it long enough im sure you'll figure out what ur looking for. Good luck.

 

[raphman]

that was helpful