use std::env;
use std::path::PathBuf;
use std::io;
use std::cmp::Ordering;

// Command line args are names of dirs, recursively list all files and
// dirs them
fn main() -> io::Result<()> {
    for dirname in env::args().skip(1) {
        let tree = DirTree::new(&dirname);
        for entry in tree {
            println!("{}", entry.path());
        }
    }
    Ok(())
}


// A filesystem entry: directory, file, symlink, etc
#[derive(Debug)]
struct Entry {
    path: PathBuf,
}

impl Entry {
    fn new(path: &PathBuf) -> Entry {
        Entry {
            path: path.clone(),
        }
    }

    fn path(&self) -> String {
        self.path.to_string_lossy().to_string()
    }
}

impl Eq for Entry {}

impl PartialEq for Entry {
    fn eq(&self, other: &Entry) -> bool {
        self.path == other.path
    }
}

impl Ord for Entry {
    fn cmp(&self, other: &Entry) -> Ordering {
        self.path.cmp(&other.path)
    }
}

impl PartialOrd for Entry {
    fn partial_cmp(&self, other: &Entry) -> Option<Ordering> {
        Some(self.path.cmp(&other.path))
    }
}


// Keep two stacks of Entry values, sorted in ascending order. The
// first stack has non-directories. When we iterate, we return a
// directory, then of its non-dirs, then recurse each of its subdirs.
#[derive(Debug)]
struct DirTree {
    entries: Vec<Entry>,
    dirs: Vec<Entry>,
}


impl DirTree {
    fn empty() -> DirTree {
        DirTree {
            entries: Vec::new(),
            dirs: Vec::new(),
        }
    }

    fn new(path: &str) -> DirTree {
        let mut dt = DirTree::empty();
        dt.add_dir(&PathBuf::from(path));
        dt
    }

    fn add_dir(&mut self, path: &PathBuf) {
        let entry = Entry::new(path);
        self.dirs.push(entry);
    }

    fn add_entries(&mut self, path: &PathBuf) -> io::Result<()> {
        let mut entries = Vec::new();
        let mut dirs = Vec::new();
        for dir_entry in path.read_dir()? {
            let dir_entry = dir_entry?;
            let metadata = dir_entry.metadata()?;
            let entry = Entry::new(&dir_entry.path());
            if metadata.is_dir() {
                dirs.push(entry);
            } else {
                entries.push(entry);
            }
        }

        entries.sort();
        entries.reverse();
        for e in entries {
            self.entries.push(e);
        }

        dirs.sort();
        dirs.reverse();
        for e in dirs {
            self.dirs.push(e);
        }

        Ok(())
    }
}

impl Iterator for DirTree {
    type Item = Entry;

    fn next(&mut self) -> Option<Entry> {
        if let Some(e) = self.entries.pop() {
            Some(e)
        } else if let Some(e) = self.dirs.pop() {
            if let Ok(_) = self.add_entries(&e.path) {
                // We ignore any errors from adding entries. Boo. Not
                // sure how I'd propagate errors, from a next method.
            }
            Some(e)
        } else {
            None
        }
    }
}