Sort an outline at every level: Difference between revisions
m
Added an extra comment.
(J draft) |
m (Added an extra comment.) |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 117:
=={{header|AutoHotkey}}==
<
;-----------------------
; get Delim, Error Check
Line 169:
result.=delim
return result
}</
Examples: "Example of Data_2"<
(
zeta
Line 186:
MsgBox % Sort_an_outline(Data_2)
MsgBox % Sort_an_outline(Data_2, 1)
return</
Output: tabulated for ease of reading, actual output is text only, Error check returns first line with inconsistent delimiter!<pre>
======================================================================================================
Line 221:
Error @ iota ||Error @ gamma
=================================
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
const char DELETE = '\x7f';
// Return the number of characters required to print the given string.
uint32_t print_size(const std::string& text) {
uint32_t size = 0;
for ( const char& ch : text ) {
if ( ch == ' ' ) { size += 1; }
if ( ch == '\t' ) { size += 4; }
}
return size;
}
// Split the given string into a vector of strings separated by the given delimiter.
std::vector<std::string> split_string(const std::string& text, const char& delimiter) {
std::vector<std::string> lines;
std::istringstream stream(text);
std::string line;
while ( std::getline(stream, line, delimiter) ) {
lines.emplace_back(line);
}
return lines;
}
// Return a string consisting of the given string with leading spaces and tabs removed.
std::string trim_left(const std::string& text) {
size_t start = text.find_first_not_of(" \t");
return ( start == std::string::npos ) ? "" : text.substr(start);
}
// Return whether the string 'haystack" contains the string 'needle'.
bool contains(const std::string& haystack, const std::string& needle) {
return haystack.find(needle) != std::string::npos;
}
// Return a string consisting of the given string repeated the given number of times.
std::string repeat(const std::string& text, const uint32_t& multiple) {
std::string result;
result.reserve(multiple * text.size());
for ( uint32_t i = 0; i < multiple; ++i ) {
result += text;
}
return result;
}
// Join a vector of strings into a single string separated by the given delimiter.
std::string join(const std::vector<std::string>& lines, const std::string& delimiter) {
std::stringstream stream;
std::copy(lines.begin(), lines.end(), std::ostream_iterator<std::string>(stream, delimiter.c_str()));
return stream.str();
}
enum Sort { ASCENDING, DESCENDING };
// Correct the given outline if necessary and sort it at every level using the given sort.
void sorted_outline(const std::string& outline, const Sort& sort) {
std::vector<std::string> lines = split_string(outline, '\n');
// Remove any initial empty lines which typical occur in raw strings.
while ( lines[0].empty() ) {
lines.erase(lines.begin());
}
std::string previous_indent = "";
std::vector<std::string> messages = {};
// Correct formatting errors in each line of the outline.
for ( uint32_t i = 0; i < lines.size(); ++i ) {
std::string line = lines[i];
if ( line.starts_with(" ") || line.starts_with("\t") ) {
std::string line_trimmed = trim_left(line);
std::string current_indent = line.substr(0, line.size() - line_trimmed.size());
if ( previous_indent == "" ) {
previous_indent = current_indent;
} else {
bool correction_needed = false;
if ( ( contains(current_indent, "\t") && ! contains(previous_indent, "\t") ) ||
( ! contains(current_indent, "\t") && contains(previous_indent, "\t") ) ) {
messages.emplace_back("Corrected inconsistent whitespace use at line \"" + line + "\"");
correction_needed = true;
}
if ( print_size(current_indent) % print_size(previous_indent) != 0 ) {
messages.emplace_back("Corrected inconsistent indent width at line \"" + line + "\"");
correction_needed = true;
}
if ( correction_needed ) {
const uint32_t multiple =
std::round(static_cast<double>(print_size(current_indent)) / print_size(previous_indent));
lines[i] = repeat(previous_indent, multiple) + line_trimmed;
}
}
}
}
// Determine the level of indent for each line of the outline.
std::vector<uint32_t> levels(lines.size(), 0);
uint32_t level = 1;
std::string margin = previous_indent;
while ( std::any_of(levels.begin(), levels.end(), [](const uint32_t& i) { return i == 0; }) ) {
for ( uint32_t i = 0; i < lines.size(); ++i ) {
if ( levels[i] == 0 ) {
const std::string line = lines[i];
if ( line.starts_with(margin) && line[margin.size()] != ' ' && line[margin.size()] != '\t' ) {
levels[i] = level;
}
}
}
margin += previous_indent;
level += 1;
}
// Prepare the lines of the outline for sorting.
std::vector<std::string> new_lines(lines.size(), "");
new_lines[0] = lines[0];
std::vector<std::string> nodes = {};
for ( uint32_t i = 1; i < lines.size(); ++i ) {
if ( levels[i] > levels[i - 1] ) {
nodes.emplace_back(nodes.empty() ? lines[i - 1] : "\n" + lines[i - 1]);
} else if ( levels[i] < levels[i - 1] ) {
for ( uint32_t j = 1; j <= levels[i - 1] - levels[i]; ++j ) {
nodes.pop_back();
}
}
if ( ! nodes.empty() ) {
new_lines[i] = join(nodes, "") + "\n" + lines[i];
} else {
new_lines[i] = lines[i];
}
}
// Sort the lines of the outline.
if ( sort == Sort::ASCENDING ) {
std::sort(new_lines.begin(), new_lines.end());
} else {
// Pad each line of the outline on the right with 'DELETE' characters.
const uint64_t max_size =
std::ranges::max_element(new_lines, std::ranges::less{}, &std::string::size) -> size();
for ( uint64_t i = 0; i < new_lines.size(); ++i ) {
new_lines[i].insert(new_lines[i].size(), max_size - new_lines[i].size(), DELETE);
}
std::sort(new_lines.begin(), new_lines.end(), std::greater<std::string>());
}
for ( uint32_t i = 0; i < new_lines.size(); ++i ) {
std::vector<std::string> sections = split_string(new_lines[i], '\n');
new_lines[i] = sections.back();
if ( sort == Sort::DESCENDING ) {
// Remove the padding of 'DELETE' characters
const int32_t start = new_lines[i].find_first_of(DELETE);
if ( start > 0 ) {
new_lines[i] = new_lines[i].substr(0, start);
}
}
}
// Display error messages
if ( ! messages.empty() ) {
for ( const std::string& message : messages ) {
std::cout << message << std::endl;
}
}
// Display corrected and sorted outline
std::cout << join(new_lines, "\n") << std::endl;
}
int main() {
std::string outline_spaces = R"(
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon)";
std::string outline_tabs = R"(
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon)";
// All spaces except for the line 'kappa' which contains a tab.
std::string outline_faulty_1 = R"(
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu)";
// All spaces with lines 'gamma' and 'kappa' misaligned.
std::string outline_faulty_2 = R"(
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon)";
std::cout << "Four space indented outline, ascending sort:" << std::endl;
sorted_outline(outline_spaces, Sort::ASCENDING);
std::cout << "Four space indented outline, descending sort:" << std::endl;
sorted_outline(outline_spaces, Sort::DESCENDING);
std::cout << "Tab indented outline, ascending sort:" << std::endl;
sorted_outline(outline_tabs, Sort::ASCENDING);
std::cout << "Tab space indented outline, descending sort:" << std::endl;
sorted_outline(outline_tabs, Sort::DESCENDING);
std::cout << "First faulty outline, ascending sort:" << std::endl;
sorted_outline(outline_faulty_1, Sort::ASCENDING);
std::cout << "First faulty outline, descending sort:" << std::endl;
sorted_outline(outline_faulty_1, Sort::DESCENDING);
std::cout << "Second faulty outline, ascending sort:" << std::endl;
sorted_outline(outline_faulty_2, Sort::ASCENDING);
std::cout << "Second faulty outline, descending sort:" << std::endl;
sorted_outline(outline_faulty_2, Sort::DESCENDING);
}
</syntaxhighlight>
{{ out }}
<pre>
Four space indented outline, ascending sort:
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
Four space indented outline, descending sort:
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
Tab indented outline, ascending sort:
alpha
epsilon
iota
theta
zeta
beta
gamma
kappa
lambda
mu
delta
Tab space indented outline, descending sort:
zeta
delta
beta
mu
lambda
kappa
gamma
alpha
theta
iota
epsilon
First faulty outline, ascending sort:
Corrected inconsistent whitespace use at line " kappa"
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
First faulty outline, descending sort:
Corrected inconsistent whitespace use at line " kappa"
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
epsilon
iota
Second faulty outline, ascending sort:
Corrected inconsistent indent width at line " gamma"
Corrected inconsistent indent width at line " kappa"
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
Second faulty outline, descending sort:
Corrected inconsistent indent width at line " gamma"
Corrected inconsistent indent width at line " kappa"
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
</pre>
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 416 ⟶ 790:
fmt.Println("\nSecond unspecified outline, descending sort:")
sortedOutline(outline4, false)
}</
{{out}}
Line 536 ⟶ 910:
=={{header|Haskell}}==
<
import Data.Tree (Tree(..), foldTree)
Line 692 ⟶ 1,066:
| x <- textLines
, s <- [T.takeWhile isSpace x]
, 0 /= T.length s ]</
{{Out}}
<pre>Four-spaced (A -> Z):
Line 771 ⟶ 1,145:
=={{header|J}}==
Implementation:<
((=<./)y (1 i.~ -.@e.)S:0 m) m {{
({.y),<m parse2^:(*@#)}.y
Line 793 ⟶ 1,167:
sortout=: {{ if. L.y do. u~ ({."1 y),.u sortout each}."1 y else. u~y end. }}
unparse=: {{ ;<S:0 y }}</
Task examples (task data defined below):<
alpha
epsilon
Line 857 ⟶ 1,231:
gamma
delta
</syntaxhighlight>
Data for task examples:
<
zeta
beta
Line 915 ⟶ 1,289:
iota
epsilon
}}</
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public final class SortAnOutlineAtEveryLevel {
public static void main(String[] args) {
Outline outline_4spaces = initialiseOutline("""
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon""");
Outline outline_1tab = initialiseOutline("""
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon""");
System.out.println("Given the text containing spaces: " + outline_4spaces);
System.out.println("The ascending sorted text is: " + outline_4spaces.sort(Sort.ASCENDING));
System.out.println("The descending sorted text is: " + outline_4spaces.sort(Sort.DESCENDING));
System.out.println("Given the text containing tabs: " + outline_1tab);
System.out.println("The ascending sorted text is: " + outline_1tab.sort(Sort.ASCENDING));
System.out.println("The descending sorted text is: " + outline_1tab.sort(Sort.DESCENDING));
try {
System.out.println("Trying to parse the first bad outline:");
@SuppressWarnings("unused")
var outline_bad1 = initialiseOutline("""
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu""");
} catch (AssertionError error) {
System.err.println(error.getMessage());
}
try {
System.out.println("Trying to parse the second bad outline:");
@SuppressWarnings("unused")
var outlinebad2 = initialiseOutline("""
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon""");
} catch (AssertionError error) {
System.err.println(error.getMessage());
}
}
private static Outline initialiseOutline(String text) {
OutlineEntry root = new OutlineEntry("", 0, null);
List<OutlineEntry> children = new ArrayList<OutlineEntry>();
children.addLast(root);
String[] lines = text.split("\n");
String firstIndent = firstIndent(lines);
int parentIndex = 0;
int previousIndent = 0;
if ( firstIndent.contains(" ") && firstIndent.contains("\t") ) {
throw new AssertionError("Mixed tabs and spaces are not allowed");
}
for ( int i = 0; i < lines.length; i++ ) {
List<String> splits = splitLine(lines[i]);
String blank = splits.get(0);
String content = splits.get(1);
final int currentIndent = blank.length() / firstIndent.length();
if ( currentIndent * firstIndent.length() != blank.length() ) {
throw new AssertionError("Invalid indentation on line " + i);
}
if ( currentIndent > previousIndent ) {
parentIndex = i;
} else if ( currentIndent < previousIndent ) {
parentIndex = parentIndex(children, currentIndent);
}
previousIndent = currentIndent;
OutlineEntry entry = new OutlineEntry(content, currentIndent + 1, children.get(parentIndex));
entry.parent.children.addLast(entry);
children.add(entry);
}
return new Outline(root, firstIndent);
}
private static int parentIndex(List<OutlineEntry> children, int parentLevel) {
for ( int i = children.size() - 1; i >= 0; i-- ) {
if ( children.get(i).level == parentLevel ) {
return i;
}
}
return -1;
}
private static String firstIndent(String[] lines) {
for ( String line : lines ) {
String indent = splitLine(line).getFirst();
if ( ! indent.isEmpty() ) {
return indent;
}
}
return " ";
}
private static List<String> splitLine(String line) {
for ( int i = 0; i < line.length(); i++ ) {
final char ch = line.charAt(i);
if ( ch != ' ' && ch != '\t' ) {
return List.of( line.substring(0, i), line.substring(i) );
}
}
return List.of( line, " " );
}
private enum Sort { ASCENDING, DESCENDING }
private static record Outline(OutlineEntry root, String baseIndent) {
public Outline sort(Sort aSort) {
root.sort(aSort, 0);
return this;
}
public String toString() {
return root.toString(baseIndent);
}
}
private static class OutlineEntry implements Comparable<OutlineEntry> {
public OutlineEntry(String aText, int aLevel, OutlineEntry aParent) {
text = aText;
level = aLevel;
parent = aParent;
}
@Override
public int compareTo(OutlineEntry other) {
return text.compareTo(other.text);
}
public OutlineEntry sort(Sort aSort, int aLevel) {
for ( OutlineEntry child : children ) {
child.sort(aSort, aLevel);
}
if ( aLevel == 0 || aLevel == level ) {
switch ( aSort ) {
case ASCENDING -> Collections.sort(children, Comparator.naturalOrder());
case DESCENDING -> Collections.sort(children, Comparator.reverseOrder());
}
}
return this;
}
public String toString(String aBaseIndent) {
String result = aBaseIndent.repeat(level) + text + "\n";
for ( OutlineEntry child : children ) {
result += child.toString(aBaseIndent);
}
return result;
}
private String text;
private int level;
OutlineEntry parent;
List<OutlineEntry> children = new ArrayList<OutlineEntry>();
}
}
</syntaxhighlight>
{{ out }}
<pre>
Given the text containing spaces:
zeta
beta
gamma
lambda
kappa
mu
delta
alpha
theta
iota
epsilon
The ascending sorted text is:
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
The descending sorted text is:
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
Given the text containing tabs:
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
The ascending sorted text is:
alpha
epsilon
iota
theta
zeta
beta
delta
gamma
kappa
lambda
mu
The descending sorted text is:
zeta
gamma
mu
lambda
kappa
delta
beta
alpha
theta
iota
epsilon
Trying to parse the first bad outline:
Invalid indentation on line 2
Trying to parse the second bad outline:
Invalid indentation on line 2
</pre>
=={{header|Julia}}==
A <code>for</code> loop was used in the constructor, and recursive functions for sorting and printing.
<
abstract type Entry end
Line 1,072 ⟶ 1,748:
println(y)
end
</
<pre>
Given the text:
Line 1,182 ⟶ 1,858:
There are several differences between the Julia original and our transcription. Most are due to the fact that Nim way to do some things is different of the Julia way to do it.
<
type
Line 1,346 ⟶ 2,022:
epsilon""")
except ValueError:
echo getCurrentExceptionMsg()</
{{out}}
Line 1,453 ⟶ 2,129:
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Sort_an_outline_at_every_level
Line 1,538 ⟶ 2,214:
theta
iota
epsilon</
{{out}}
<pre>
Line 1,636 ⟶ 2,312:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #000080;font-style:italic;">-- (tab chars are browser kryptonite)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_children</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">bRev</span><span style="color: #0000FF;">)</span>
Line 1,718 ⟶ 2,394:
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 1,783 ⟶ 2,459:
=={{header|Python}}==
<
Line 2,199 ⟶ 2,875:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>4-space indented (A -> Z):
Line 2,278 ⟶ 2,954:
* Routine(s) to output the data structure in the desire sort order.
<syntaxhighlight lang="raku"
zeta
beta
Line 2,383 ⟶ 3,059:
multi pretty-print (Str $struct, :$level = 0, :$ws = ' ', :$desc = False) {
say $ws x $level , $struct;
}</
{{out}}
<pre>=======================================================
Line 2,497 ⟶ 3,173:
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var sortedOutline = Fn.new { |originalOutline, ascending|
Line 2,651 ⟶ 3,327:
System.print("\nSecond unspecified outline, descending sort:")
sortedOutline.call(outline4, false)</
{{out}}
| |||