Сортировка таблицы средствами JavaScript
,
Достаточно часто пользователям интернет приходится сталкиваться с большим объемом информации, представленным в виде таблицы. Не менее часто требуется получить результаты в ином порядке, чем они представлены первоначально. Большинство web-мастеров решает эту проблему применением сортировки на сервере, для чего используется перезагрузка страницы. Действительно, серверные языки предоставляют гораздо больше возможностей отсортировать многомерный массив по определенному значению, чем скриптовые языки, выполняющиеся непосредственно на стороне клиента. Решение сортировать данные на стороне сервера вполне оправданно с точки зрения трудозатрат программиста, так как многие серверные языки имеют встроенные функции сортировки многомерных массивов, и поэтому не требуется вдумываться в алгоритмы сортировки, что-то изобретать или перестраивать алгоритм под свои нужды. Но все-таки такое решение не оправдано, если подходить к этой проблеме с точки зрения пользователя. Вначале посетителю сайта требуется дождаться достаточно длительной загрузки страницы, просмотреть результаты, нажать на кнопку "Отсортировать" и... опять дожидаться, пока сервер закончит работу и вернет результат. Такие множественные перезагрузки страницы никак не способствуют популярности сайта у посетителя. В конце-концов, устав дожидаться очередной загрузки страницы, или испугавшись лишнего траффика, он покинет сайт в поисках более лояльного к нему web-мастера. Решением данной проблемы, а именно эффективной сортировки данных и формирования результирующей таблицы, я и предлагаю заняться в этой статье. А в качестве примера данных будет выступать информация о книгах: дата написания, название книги и ее автор.
Начнем с функции fillArray, которая и будет эмулировать многомерный массив, а вернее создать класс-объект с членами - данными многомерного массива. Приведем ее код:
Листинг 1:
1 function fillArray( years, books, authors ) { 2 authors = upCs( authors, " " ); 3 authors = upCs( authors, "-" ); 4 books = upCs( books, "" ); 5 6 this.years = years; 7 this.yweight = weight( years ); 8 this.books = books; 9 this.bweight = weight( books ); 10 this.authors = authors; 11 this.aweight = weight( authors ); 12 }
Разберем данные по строкам. Во второй строке вызывается функция upCs с параметром authors и пробелом в качестве второго параметра. Функция upCs создает заглавные буквы в начале строки и перед каждым вхождением второго аргумента. Эта функция была написана исключительно потому, что не все обрабатывают данные должным образом и вполне могут написать имя писателя, например, с маленькой буквы. Применение такой функции устраняет возможную ошибку программиста в заполнении массива данными, а также позволяет быть уверенным, что в функции сортировки не будет неверного сравнения заглавных букв со строчными. Впрочем, если вы уверены в том, что данные будут занесены верно, можете убрать вызовы этой функции:
Листинг 2:
1 function upCs( str, param ) { 2 var tmpStr = str.substring( 0, 1 ).toUpperCase() + str.substring( 1 ); 3 if( !param ) 4 return tmpStr; 5 var separator = tmpStr.indexOf( param ); 6 var retStr = tmpStr; 7 if( separator != -1 ) 8 retStr = tmpStr.substring( 0, separator ); 9 10 while( separator != -1 ) { 11 tmpStr = tmpStr.substr( separator + 1, 1 ).toUpperCase() + tmpStr.substring( separator + 2 ); 12 separator = tmpStr.indexOf( param ); 13 if( separator != -1 ) 14 retStr += param + tmpStr.substring( 0, separator ); 15 else 16 retStr += param + tmpStr; 17 } 18 19 return retStr; 20 }
Эта же функция, вызванная с пустым вторым аргументом, возвращает результат с заглавной буквой только в начале строки. Теперь обратимся к строке 7, листинга 1. Здесь вызывается функция weight, которая возвращает числовые значения каждого символа аргумента в виде массива. Для чего я ее написал? Дело в том, что коды символов русского алфавита в браузере идут последовательно, кроме кода символа буквы "ё". Код этого символа больше кодов символов остального алфавита, поэтому приходится присваивать такое "весовое" значение этому символу, которое соответствовало бы его позиции в алфавите. Вот код этой функции:
Листинг 3:
1 function weight( str ) { 2 var retArray = new Array(); 3 4 for( var i = 0; i < str.length; i++ ) { 5 var tmp = str.charCodeAt( i ); 6 if( tmp >= 1046 && tmp < 1078 ) 7 tmp++; 8 else if( tmp == 1025 ) 9 tmp = 1046; 10 else if( tmp >= 1078 ) 11 tmp++; 12 else if( tmp == 1105 ) 13 tmp = 1078; 14 retArray[ i ] = tmp; 15 } 16 17 return retArray; 18 }
Ну что же, функции, необходимые для создания нашего многомерного массива готовы. Осталось создать массив и заполнить его данными:
Листинг 4:
1 var txt = []; 2 txt[ 0 ] = new fillArray( "1959", "фрейд", "сартр жан-поль" ); 3 txt[ 1 ] = new fillArray( "1940", "подростки", "сэлинджер джером" ); 4 txt[ 2 ] = new fillArray( "1946", "пена дней", "виан борис" ); 5 txt[ 3 ] = new fillArray( "1948", "осадное положение", "камю альбер" ); 6 txt[ 4 ] = new fillArray( "1899", "об иноческой жизни", "рильке райнер мария" ); 7 txt[ 5 ] = new fillArray( "1849", "аннабель Ли", "по эдгар" ); 8 txt[ 6 ] = new fillArray( "1917", "дагон", "лавкрафт говард" ); 9 txt[ 7 ] = new fillArray( "1915", "процесс", "кафка франц" ); 10 txt[ 8 ] = new fillArray( "1989", "египет Рамсесов", "монтэ пьер" ); 11 txt[ 9 ] = new fillArray( "1932", "мастер и Маргарита", "булгаков михаил" );
Обратить внимание стоит лишь на то, что года, когда были написаны книги, я передаю в функцию в качестве строкового параметра, а не числового. Делается это для того, чтобы не писать несколько функций сортировки.
Насколько быстр такой метод заполнения массива? На компьютере со средней производительностью загрузка 1000 элементов происходит за 450 - 800 миллисекунд. Но поскольку пользователь будет получать массив такого размера не сразу, а по частям, и размер этих частей будет сильно зависеть от скорости его соединения с интернет, то время, затрачиваемое на создание элемента массива и определение весовых значений его данных, будет незаметно пользователю.
Я подошел к самой интересной части данной статьи, а именно - к непосредственной работе с данными. В качестве функции сортировки данных я выбрал сортировку Хоара, которая, как мне кажется, наиболее соответствует поставленной задаче в начале статьи. Вот ее код, нюансы которого рассмотрю несколько более подробно.
Листинг 5 :
1 function quickSort( l, h, type ) { 2 var low = l; 3 var high = h; 4 var rt = eval( "txt[ " + Math.round( ( l + h ) / 2 ) + " ]" ); 5 var middle = new fillArray( rt.years, rt.books, rt.authors ); 6 7 do { 8 9 while( isLow( eval( "txt[ " + low + " ]" ), middle, type ) ) 10 low++; 11 12 while( isLow( middle, eval( "txt[ " + high + " ]" ), type ) ) 13 high--; 14 15 if( low <= high ) { 16 var temp = txt[ low ]; 17 txt[ low++ ] = txt[ high ] 18 txt[ high-- ] = temp; 19 } 20 } while( low <= high ); 21 22 if( l < high ) 23 quickSort( l, high, type ); 24 if( low < h ) 25 quickSort( low, h, type ); 26 }
В листинге 5 приведена классическая сортировка Хоара, но с небольшими модификациями. На этих модификациях я и хочу обратить внимание прежде всего. ИтаК, посмотрим на строки 4-5. Здесь создается новый элемент на основании данных элемента массива, который берется как среднее значение между границами цикла сортировки. Почему пришлось внести такую модификацию? Почему нельзя было написать классически, как и положено в сортировке Хоара: var middle = eval( "txt[ " + Math.round( ( l + h ) / 2 ) + " ]" );? Дело в том, что здесь не получено значения элемента массива, как в классической сортировке, а есть только ссылка на него (хотя слово ссылка здесь не совсем уместно). При таком подходе дальнейшие действия теряют смысл. Немного отклонюсь от темы моей статьи и разъясню этот момент. Приведу следующий листинг:
Листинг 6 :
1 function cls() { 2 this.member = "value"; 3 } 4 5 var x = new cls(); 6 var y = x; 7 alert( "x.member = " + x.member + ", y.member = " + y.member ); 8 x.member = "new value"; 9 alert( "x.member = " + x.member + ", y.member = " + y.member );
Что происходит после того, как на восьмой строке было присвоено члену класса новое значение? Изменится ли только значение в переменной x? Нет, изменится значение в обеих переменных. Дело в том, что присваивания значения созданного пользовательского класса не происходит. Попробую провести похожую аналогию со ссылками в языке С++. Я не получу автономного значения, которое было бы независимо от оригинала. А получу своего рода ссылку на значение, которое подвержено изменениям из оригинальной переменной. Такая ссылка разрушает всю семантику сортировки Хоара, поскольку алгоритм требует сравнения в процессе сортировки с опорным значением середины диапазона элементов, а сам алгоритм в процессе работы может заменять значение, находящееся по адресу опорного элемента другим значением. Именно поэтому мне пришлось создать отдельное значение через оператор new. Конечно, это влечет дополнительные затраты процессорного времени на повторное определение "весовых" значений данных, но эти затраты достаточно минимальны. Впрочем, если у вас есть желание, вы можете модифицировать функцию fillArray так, чтобы она принимала шесть аргументов. В качестве трех последних аргументов можно заносить уже полученные ранее данные о "весовом" значении членов массива.
Итак, я выяснил зачем требуется создавать новый элемент в сортировке Хоара. Перейду теперь к строкам 9 и 12. Здесь в качестве сравнения значений элементов вызывается функция isLow, которая принимает в качестве аргументов два объекта для сравнения и третий аргумент - имя члена класса, по которому производится сортировка (внимательный читатель уже заметил этот третий непонятный аргумент в алгоритме Хоара). Приведу эту функцию сравнения:
Листинг 7 :
1 function isLow( low, high, type ) { 2 var len1 = low[ type ].length; 3 var len2 = high[ type ].length; 4 var length = len1 < len2 ? len1 : len2; 5 6 for( var i = 0; i < length; i++ ) { 7 var str1 = low[ type ][ i ]; 8 var str2 = high[ type ][ i ]; 9 if( str1 < str2 ) 10 return true; 11 if( str1 > str2 ) 12 return false; 13 } 14 15 if( len1 < len2 ) 16 return true; 17 return false; 18 }
Как видите, кроме принципа работы с самими элементами, ничего необычного не происходит. Здесь для обращения к членам класса используются квадратные скобки, как в массиве. Подробнее о таком способе работы с пользовательскими объектами можно прочитать у Дмитрия Котерова на http://dklab.ru в статье "Маленькие хитрости JavaScript". Упомяну лишь то, что касается непосредственно работы нашей функции. Следует обратить внимание на строки 7 - 8. Здесь используется необычный способ адресации элемента. Предположу, что значение аргумента type равно "yweight", то есть хочу отсортировать по годам и обращаюсь к массиву-члену класса, который содержит данные о "весовом" значении строки с числом года. То есть фактически я буду обращаться так: low.yweight[ i ]. В этой функции больше никаких сложностей не вижу, поэтому пойду дальше.
Во всем остальном функция сортировки полностью соответствует своему классическому варианту, о реализации которого написано большое количество статей, поэтому больше никаких вопросов, касающихся этой функции, здесь рассматриваться не будет. Я же перейду к заключающей части своей статьи и рассмотрю функцию создания таблицы на основе DOM (Document Object Model), а также функции выбора сортировки. Сразу возьму код, который должен быть между тегами body:
Листинг 8 :
1 <table id="table"> 2 <tr> 3 <td><a href="javascript:allocator( 'yweight' )">Год</a></td> 4 <td><a href="javascript:allocator( 'bweight' )">Книга</a></td> 5 <td><a href="javascript:allocator( 'aweight' )">Автор</a></td> 6 </tr> 7 <tbody id="tablebody"></tbody> 8 </table>
Здесь нет ничего сложного: в таблице присутствует аттрибут id = "table", чтобы из функции можно было обратиться к этому узлу. Также присутствуют строка с именами колонок и вызовом функции выбора сортировки и tbody с id = "tablebody". Зачем необходим tbody? Netscape Navigator 7.1 и вообще все браузеры на движке Gecko, а также Opera, не требуют этого элемента при динамическом создании таблицы. Но только вот этот элемент жизненно необходим, если вы хотите увидеть результат в браузере Internet Explorer. Если, создавая таблицу функциями DOM, вы пропустите создание такого элемента, то результата не увидите. Как создается таблица? Вот эта функция: Листинг 9 :
1 function createTable( cStart, cType, cSize, cChange ) { 2 var tabbd = document.getElementById( "tablebody" ); 3 4 if( !tabbd ) { 5 var table = document.getElementById( "table" ); 6 var tbody = document.createElement( "tbody" ); 7 tbody.id = "tablebody"; 8 table.appendChild( tbody ); 9 tabbd = document.getElementById( "tablebody" ); 10 } 11 12 while( tabbd.hasChildNodes() ) { 13 var tmp = tabbd.childNodes[ 0 ]; 14 tabbd.removeChild( tmp ); 15 } 16 17 for( var counter = cStart; eval( counter + cType + cSize ); eval( "counter" + cChange ) ) { 18 var tr = document.createElement( "tr" ); 19 20 var td = document.createElement( "td" ); 21 var tdtxt = document.createTextNode( txt[ counter ].years ); 22 td.appendChild( tdtxt ); 23 tr.appendChild( td ); 24 td = document.createElement( "td" ); 25 tdtxt = document.createTextNode( txt[ counter ].books ); 26 td.appendChild( tdtxt ); 27 tr.appendChild( td ); 28 td = document.createElement( "td" ); 29 tdtxt = document.createTextNode( txt[ counter ].authors ); 30 td.appendChild( tdtxt ); 31 tr.appendChild( td ); 32 tabbd.appendChild( tr ); 33 } 34 }
Целью этой статьи не является объяснение основ DOM. Поэтому я остановлюсь только на наиболее важном моменте - необычном условии цикла for. Итак, createTable принимает четыре аргумента. Первый из них (cStart) - определяет значение счетчика в цикле for. Второй (cType) - тип сравнения, то есть значения ">", "<" и т.д. Третий аргумент ( cSize ) определяет значение, при сравнении с которым прекращается цикл. Четвертое же значение (cChange) может становиться инкрементом или декрементом, в зависимости от требования сортировки. Желательно подробно разобраться в этой строке кода, она достаточно важна. Без этих четырех аргументов пришлось бы писать несколько отдельных функций, которые бы различались только в этой строке. Этот прием достаточно удобный для общего применения, и я не исключаю возможности, что вы захотите его использовать в своих функциях.
Осталась последняя функции - allocator, которая, собственно, и управляет всеми сортировками и созданием таблицы. Листинг 10 :
